Direction of Stack Growth - DSP

On Tue, 23 Oct 2007 17:21:21 -0400, Jerry Avins <jya@ieee.org> wrote:

>karthikbalaguru wrote:
>
> ...
>
>> Reading through this and thinking about heap mechanism. I got some
>> query.
>> Why do we need the stack as the heap appears flexible ?
>
>Manipulating a heap requires software. Some stacks are implemented
>entirely in hardware (PUSH, POP; CALL, RETURN). It would be very hard to
>create or maintain a heap on a machine with no stack.

The stack simplifies many things, such as re-entrancy. There have been
architectures without an ordinary stack mechanism as the IBM S/360
mentioned in other posts. The TI TMS9900 had all the general purpose
registers in the RAM and starting a subroutine could use a new
register set, which included a link to the previous register set so
you knew how to return.

In the 1960's for instance the DDP516 (later Honeywell) stored the
return address at the first word of the subroutine and the actual
subroutine code started at the next word. To return from the
subroutine, an indirect jump was performed through the first word of
the routine (which now contained the return address). This required
that the code space was writable and the routine was not re-entrant,
so recursion had to implemented in different way 8if ever used those
days).

Paul

> Why do we need the stack as the heap appears flexible ?
>
A heap needs addresses, Variables om a stack is can be addressed
automatically (e.g. with 1 byte commands on an x86).

-Michael

In article <ccrth3d405s6q5r7moev12730d3i2dnrf4@4ax.com>,
Paul Keinanen <keinanen@sci.fi> writes:
|> On Tue, 23 Oct 2007 17:21:21 -0400, Jerry Avins <jya@ieee.org> wrote:
|> >karthikbalaguru wrote:
|> >
|> >> Reading through this and thinking about heap mechanism. I got some
|> >> query.
|> >> Why do we need the stack as the heap appears flexible ?
|> >
|> >Manipulating a heap requires software. Some stacks are implemented
|> >entirely in hardware (PUSH, POP; CALL, RETURN). It would be very hard to
|> >create or maintain a heap on a machine with no stack.
|>
|> The stack simplifies many things, such as re-entrancy. There have been
|> architectures without an ordinary stack mechanism as the IBM S/360
|> mentioned in other posts. ...

Not just that. During my spells at IBM, I tried very hard to persuade
the Fortran people that using a stack would IMPROVE performance, based
on my experiences on the System/370 with many languages.

They were wedded to static allocation, because it enabled many of the
address constants to be calculated by the compiler, which also eased
pressure on the registers. This was Fortran 77, of course, and didn't
support reentrancy. That argument is a good one, but I was arguing
that the better locality properties of a stack gave MORE of a gain.

As some people know, I have been banging on about double stacks for
years. I first encountered them in Algol 68, was suspicious, but
discovered that they need negligible extra code, stack space and
register use, and vastly improve locality. Now, in these days of
90% of performance being due to cachability, why does nobody pick
them up again?

It's insane.


Regards,
Nick Maclaren.

Nick Maclaren wrote:

> As some people know, I have been banging on about double stacks for
> years. I first encountered them in Algol 68, was suspicious, but
> discovered that they need negligible extra code, stack space and
> register use, and vastly improve locality. Now, in these days of
> 90% of performance being due to cachability, why does nobody pick
> them up again?

If I've understood the "double stack" method correctly, it is like
the "secondary stack" method that is used in some current Ada
compilers, including the GNU Ada compiler GNAT, to manage
dynamically sized stack-allocated objects.

--
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
. @ .

In article <471f03bc$0$3501$39db0f71@news.song.fi>,
Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
|>
|> > As some people know, I have been banging on about double stacks for
|> > years. I first encountered them in Algol 68, was suspicious, but
|> > discovered that they need negligible extra code, stack space and
|> > register use, and vastly improve locality. Now, in these days of
|> > 90% of performance being due to cachability, why does nobody pick
|> > them up again?
|>
|> If I've understood the "double stack" method correctly, it is like
|> the "secondary stack" method that is used in some current Ada
|> compilers, including the GNU Ada compiler GNAT, to manage
|> dynamically sized stack-allocated objects.

Yes, it is. I had forgotten about those. Thanks for the correction.
The "nobody" should be "nobody except the Ada community"!


Regards,
Nick Maclaren.

Nick Maclaren wrote:

...

> As some people know, I have been banging on about double stacks for
> years. I first encountered them in Algol 68, was suspicious, but
> discovered that they need negligible extra code, stack space and
> register use, and vastly improve locality. Now, in these days of
> 90% of performance being due to cachability, why does nobody pick
> them up again?
>
> It's insane.

Ayup! The Forths I use have three stacks.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

In article <_uGdnTqXWaEPHYLanZ2dnUVZ_hWdnZ2d@rcn.net>,
Jerry Avins <jya@ieee.org> writes:
|>
|> > As some people know, I have been banging on about double stacks for
|> > years. I first encountered them in Algol 68, was suspicious, but
|> > discovered that they need negligible extra code, stack space and
|> > register use, and vastly improve locality. Now, in these days of
|> > 90% of performance being due to cachability, why does nobody pick
|> > them up again?
|> >
|> > It's insane.
|>
|> Ayup! The Forths I use have three stacks.

Up, down and sideways? I always knew that Forth was a bizarre
language :-)


Regards,
Nick Maclaren.

nmm1@cus.cam.ac.uk (Nick Maclaren) writes:
> Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
> |>
> |> > As some people know, I have been banging on about double stacks for
> |> > years. I first encountered them in Algol 68, was suspicious, but
> |> > discovered that they need negligible extra code, stack space and
> |> > register use, and vastly improve locality. Now, in these days of
> |> > 90% of performance being due to cachability, why does nobody pick
> |> > them up again?
> |>
> |> If I've understood the "double stack" method correctly, it is like
> |> the "secondary stack" method that is used in some current Ada
> |> compilers, including the GNU Ada compiler GNAT, to manage
> |> dynamically sized stack-allocated objects.
>
> Yes, it is. I had forgotten about those. Thanks for the correction.
> The "nobody" should be "nobody except the Ada community"!

If you're talking about separate stacks for return addresses and data,
there are C compilers extant using that method under the hood.

While on the subject of return addresses, isn't the ARM a throwback
to the old BALR days? It's granted that you can save a push operation
for leaf functions, but otherwise you spend the same or more operations
saving the return address than just having the hardware do it
automagically.

In article <20071024.7937158.8D09@mojaveg.lsan.mdsg-pacwest.com>,
mojaveg@mojaveg.lsan.mdsg-pacwest.com (Everett M. Greene) writes:
|> nmm1@cus.cam.ac.uk (Nick Maclaren) writes:
|> > Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
|> > |>
|> > |> > As some people know, I have been banging on about double stacks for
|> > |> > years. I first encountered them in Algol 68, was suspicious, but
|> > |> > discovered that they need negligible extra code, stack space and
|> > |> > register use, and vastly improve locality. Now, in these days of
|> > |> > 90% of performance being due to cachability, why does nobody pick
|> > |> > them up again?
|> > |>
|> > |> If I've understood the "double stack" method correctly, it is like
|> > |> the "secondary stack" method that is used in some current Ada
|> > |> compilers, including the GNU Ada compiler GNAT, to manage
|> > |> dynamically sized stack-allocated objects.
|> >
|> > Yes, it is. I had forgotten about those. Thanks for the correction.
|> > The "nobody" should be "nobody except the Ada community"!
|>
|> If you're talking about separate stacks for return addresses and data,
|> there are C compilers extant using that method under the hood.

No, we aren't. The method isn't much use for C89 or C++, but is
for C99.


Regards,
Nick Maclaren.