Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #58738

Re: no stack

Show all headers | View raw

On 22/03/15 21:01, Malcolm McLean wrote:
> On Sunday, March 22, 2015 at 2:40:09 PM UTC, David Brown wrote:
>>
>> I assume Bart's interpreter project is written in C, and it therefore 
>> /is/ relevant.  He has simply taken an example of a fairly large C 
>> program, made a few steps towards simulating your stackless model (by 
>> making some local variables "static"), and found that already he was 
>> down 3%.
>>
>> This gives a sample point showing that stackless C is unlikely to give 
>> any speed advantages, and will almost certainly lead to bigger and 
>> slower programs (in most cases).
>>
> A stack must maintain the stack pointer. 

Such "maintenance" is seldom more than just adding or subtracting an
immediate value to the stack pointer as you enter and leave a function.
 If you need to use the stack for temporary storage in a function (as
distinct from local variables or argument passing), then you already
have the "stack pointer maintenance" in place.  Even if you are placing
such temporaries at static addresses rather than a stack, the cost of
creating and destroying the stack frame (for those functions that need
it) is normally going to be much smaller than the cost of storing and
loading from statically allocated data.

> So it's inherently a little
> bit shower than direct memory access. 

No (see above).  And note also that when you talk about "slower" on
modern cpus, you need to consider cache, pipelining, and scheduling
effects - adding an immediate value to the stack pointer will be easily
pipelined and run in parallel with most instructions, while access to
static memory is going to involve stalls and waits (even if it is in the
cache already).

> However the chip and the compiler
> are both designed on the assumption that most programs will use
> stacks. So, for example, the cache mechanism is tweaked so that
> stacks have the optimal working environment.

True.

> As a result, Bart's non-stack based equivalent is very marginally
> slower than the stack-based one.

He made a /few/ of his variables "static" instead of on stack.  He did
not make them all static, nor did he try to make parameter passing work
statically, and he certainly didn't make temporaries static (that would
have required modifying the compiler).  We can also expect that the
compiler made local copies of the "static" locals on the stack when it
improves the code - disallowing that would also need compiler
modification.  And yet with those small changes, the difference was
measurable (3%, IIRC).

> However that wouldn't be the case 
> if programmers generally abandoned stacks.

I agree that this would make a difference.  If we look at an
architecture that could work well here, like the PPC (and unlike the
x86), and considered a compiler that was optimised to avoid data on the
stack (but kept the stack for return addresses), then the performance of
the cpu itself would be very similar - the same instructions (reg +
16-bit offset) would be used to access local data as is used for stack
data access.

However, even then the stack is far more cache-friendly - it is much
more efficient to use the stack for run-time multiplexing of arguments
and locals than trying to figure out safe and efficient multiplexing at
compile time (as done by some embedded compilers for cpus like the
8051).  And without such multiplexing (which would ruin any possible
debugging advantages of stackless data), you would need many times as
much cache space.

> A Fortran 77 compiler disallows recursion, so it can implement 
> programs without a stack, and it can optimise extremely aggressively,
> partly for this reason. 

Disabling recursion (or more precisely, re-entrancy) allows for a number
of optimisations, completely independently of the use of a stack for
data.  The most efficient code generation and run-time size and speed is
to make "normal" use of a stack but have no recursion or re-entrancy.

But while recursion may be relatively rare for a lot of types of code,
re-entrancy is increasingly important - it is essential in
multi-threaded code.

> The main advantage is the lack of pointer
> aliasing, however. 

Yes, that's an advantage Fortran compilers have - and is independent of
stacks.

> Stacks are extremely efficient, and the gains from
> eliminating them will usually be small.
> 

In all but a few cases on suitable cpus, I think you'll find stackless
implementations will be significantly bigger and slower, with much more
cache bottlenecks.

However, there are certainly situations where stackless behaviour can
give new features or possibilities.  It would make co-routine
programming more efficient, and works well with massively scaled
light-weight threading.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

no stack fir <profesor.fir@gmail.com> - 2015-03-22 02:09 -0700
  Re: no stack wssimms@gmail.com - 2015-03-22 02:52 -0700
    Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 03:04 -0700
      Re: no stack Richard Heathfield <rjh@cpax.org.uk> - 2015-03-22 13:15 +0000
        Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 07:37 -0700
  Re: no stack Lőrinczy Zsigmond <nospam@for.me> - 2015-03-22 11:10 +0100
    Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 03:30 -0700
  Re: no stack jacob navia <jacob@jacob.remcomp.fr> - 2015-03-22 11:15 +0100
    Re: no stack jacob navia <jacob@jacob.remcomp.fr> - 2015-03-22 11:23 +0100
      Re: no stack jacob navia <jacob@jacob.remcomp.fr> - 2015-03-22 11:24 +0100
      Re: no stack jacob navia <jacob@jacob.remcomp.fr> - 2015-03-22 11:41 +0100
        Re: no stack Keith Thompson <kst-u@mib.org> - 2015-03-22 12:18 -0700
          Re: no stack Melzzzzz <mel@zzzzz.com> - 2015-03-22 20:25 +0100
      Re: no stack Stephen Sprunk <stephen@sprunk.org> - 2015-03-23 12:17 -0500
      Re: no stack James Kuyper <jameskuyper@verizon.net> - 2015-03-23 13:22 -0400
  Re: no stack Bartc <bc@freeuk.com> - 2015-03-22 11:13 +0000
    Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 04:29 -0700
    Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 04:33 -0700
    Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 04:39 -0700
    Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 04:46 -0700
      Re: no stack Bartc <bc@freeuk.com> - 2015-03-22 12:16 +0000
        Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 05:25 -0700
          Re: no stack Bartc <bc@freeuk.com> - 2015-03-22 12:59 +0000
            Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 07:15 -0700
              Re: no stack David Brown <david.brown@hesbynett.no> - 2015-03-22 15:39 +0100
                Re: no stack Bartc <bc@freeuk.com> - 2015-03-22 19:47 +0000
                Re: no stack fir <profesor.fir@gmail.com> - 2015-03-23 02:18 -0700
                Re: no stack Bartc <bc@freeuk.com> - 2015-03-23 11:21 +0000
                Re: no stack Richard Heathfield <rjh@cpax.org.uk> - 2015-03-23 11:35 +0000
                Re: no stack fir <profesor.fir@gmail.com> - 2015-03-23 07:07 -0700
                Re: no stack fir <profesor.fir@gmail.com> - 2015-03-23 07:28 -0700
                Re: no stack Bartc <bc@freeuk.com> - 2015-03-23 14:56 +0000
                Re: no stack fir <profesor.fir@gmail.com> - 2015-03-23 08:13 -0700
                Re: no stack Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-03-22 13:01 -0700
                Re: no stack David Brown <david.brown@hesbynett.no> - 2015-03-23 13:14 +0100
        Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 05:30 -0700
        Re: no stack David Brown <david.brown@hesbynett.no> - 2015-03-22 14:15 +0100
    Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 04:49 -0700
  Re: no stack Melzzzzz <mel@zzzzz.com> - 2015-03-22 12:37 +0100
    Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 05:06 -0700
      Re: no stack Melzzzzz <mel@zzzzz.com> - 2015-03-22 13:23 +0100
        Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 05:48 -0700
          Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 08:51 -0700
          Re: no stack fir <profesor.fir@gmail.com> - 2015-03-23 07:39 -0700
            Re: no stack fir <profesor.fir@gmail.com> - 2015-03-23 07:54 -0700
      Re: no stack David Brown <david.brown@hesbynett.no> - 2015-03-22 14:45 +0100
        Re: no stack Richard Heathfield <rjh@cpax.org.uk> - 2015-03-22 14:20 +0000
          Re: no stack David Brown <david.brown@hesbynett.no> - 2015-03-22 15:43 +0100
          Re: no stack Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-03-22 13:09 -0700
            Re: no stack Bartc <bc@freeuk.com> - 2015-03-22 20:38 +0000
              Re: no stack Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-03-22 13:54 -0700
                Re: no stack fir <profesor.fir@gmail.com> - 2015-03-23 02:08 -0700
                Re: no stack Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-03-23 12:07 +0000
                Re: no stack fir <profesor.fir@gmail.com> - 2015-03-23 07:13 -0700
              Re: no stack Kaz Kylheku <kaz@kylheku.com> - 2015-03-22 20:59 +0000
        Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 07:35 -0700
          Re: no stack David Brown <david.brown@hesbynett.no> - 2015-03-22 16:27 +0100
    Re: no stack fir <profesor.fir@gmail.com> - 2015-03-22 05:10 -0700
  Re: no stack David Brown <david.brown@hesbynett.no> - 2015-03-22 13:56 +0100
  Re: no stack John Bode <jfbode1029@gmail.com> - 2015-03-24 09:01 -0700
    Re: no stack Keith Thompson <kst-u@mib.org> - 2015-03-24 12:30 -0700
      Re: no stack David Brown <david.brown@hesbynett.no> - 2015-03-25 09:16 +0100
        Re: no stack Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-25 09:00 -0700
          Re: no stack David Brown <david.brown@hesbynett.no> - 2015-03-25 17:33 +0100
            Re: no stack James Kuyper <jameskuyper@verizon.net> - 2015-03-25 13:35 -0400
            Re: no stack Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-25 16:22 -0700
              Re: no stack David Brown <david.brown@hesbynett.no> - 2015-03-26 08:54 +0100
                Re: no stack Keith Thompson <kst-u@mib.org> - 2015-03-26 08:48 -0700
                Re: no stack David Brown <david.brown@hesbynett.no> - 2015-03-26 23:00 +0100
                Re: no stack Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-28 09:15 -0700
                Re: no stack David Brown <david.brown@hesbynett.no> - 2015-03-28 18:17 +0100
                Re: no stack Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-03-28 12:36 -0700
                Re: no stack Richard Damon <Richard@Damon-Family.org> - 2015-03-28 17:33 -0400
                Re: no stack Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-30 08:04 -0700
                Re: no stack David Brown <david.brown@hesbynett.no> - 2015-04-07 00:39 +0200
              Re: no stack fir <profesor.fir@gmail.com> - 2015-03-26 01:21 -0700
        Re: no stack Keith Thompson <kst-u@mib.org> - 2015-03-25 10:57 -0700
          Re: no stack David Brown <david.brown@hesbynett.no> - 2015-03-25 21:55 +0100

csiph-web