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

Groups > comp.lang.c > #58632 > unrolled thread

no stack

Back to article view | Back to comp.lang.c

Contents

  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

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#58658

On Sun, 22 Mar 2015 05:06:27 -0700 (PDT)
fir <profesor.fir@gmail.com> wrote:

> W dniu niedziela, 22 marca 2015 12:38:03 UTC+1 użytkownik Melzzzzz
> napisał:
> > On Sun, 22 Mar 2015 02:09:00 -0700 (PDT)
> > fir <profesor.fir@gmail.com> wrote:
> > 
> > > 'no stack' is a bit hype/slogan (could be good to easier
> > > remembering the subject postulate)
> > > 
> > > I mean here that i wonder if c compiler 
> > > would just not use stack for args and locals 
> > > and just used static data everywhere by default (axcept the rere
> > > thing where you explicitely will denote some data as auto
> > > and such variable would be created/dropped on stack) - if it will
> > > not make 1) significently simpler 
> > 
> > No. Stack managing is simpler
> > 
> 
> why? i dont see it .. 

There is no linking problems with stack management.
One only adjust stack pointer.

> 
> > > 2) faster
> > 
> > Show example where global data is faster?
> > Actually stack is almost all the time in cache.
> > 
> stack has its cost of its managment,

but far less than managing global variables...
That's why it is preferred.

> also if you use the same ram lines for
> reading and writing one args/locals 
> a while later for other args/locals 
> you must revrite it etc (acceses are 
> dependant in time), with static you
> may just leave one and go to another
> not waiting

You forgot that accessing cache is much
more faster than DRAM.

> 
> thode local and args areas probably 
> willbe also in cache, some differences my
> differ but i dont see right now clear reason 
> for this to work worse

Nope. They will not be in cache.

> 
> > > 3) smaller
> > 
> > Nope. Maintaining global variables is bigger.
> > 
>  weak answer, (almost like untorelably weak as on my standards of
> discussion) (do you counted it to say "nope"? do you forget about the
> push pop in your calulation ?

You forgot that executable will be bloated with large amount
of data.

 (you do not mention it)), also how
> bigger you get it by adresing not a big amount of .bss (for very
> small system it could be sparing of couple hundreds of ints - but
> this is special case you can explicitely make args and locals work on
> stack by u8sing 'auto')

Complexity of linking and finding right address far outweighs
anything even remotely ...

> 
> > 
> > > 4) more potent for some usable techniques
> > 
> > What are these?
> > 
> probably many techniques that could 
> work only when you have locals/args
> static, this is side depth topic here
> and i probably will say on this but
> on another ocassion

Name one?

> 
> > > 
> > > executables
> > > 
> > > (stack would be used for call ret adresses
> > > and for rare data explicitely denoted as auto (though i wonder if
> > > such auto data shouldnt be placed on speparate stack, not the
> > > same as ret/call one)
> > 
> > Why? This is almost surely slower.
> > 
> > > 
> > > I seem to being convinced that this static no stack version
> > > should be considered as a default implementation in c programs)
> > > (nearly sure that this would be better options, though test
> > > should be done to prove this, and such test are burdensome a bit)
> > 
> > Hm, what about reentrancy and threads?
> > 
> what do you mean exactly?

I mean multi threaded programs, how they would work with static locals
and god forbid args?

> 
> > > 
> > > [fir]
> > >

[toc] | [prev] | [next] | [standalone]

#58661

W dniu niedziela, 22 marca 2015 13:23:25 UTC+1 użytkownik Melzzzzz napisał:
> On Sun, 22 Mar 2015 05:06:27 -0700 (PDT)
> fir <profesor.fir@gmail.com> wrote:
> 
> > W dniu niedziela, 22 marca 2015 12:38:03 UTC+1 użytkownik Melzzzzz
> > napisał:
> > > On Sun, 22 Mar 2015 02:09:00 -0700 (PDT)
> > > fir <profesor.fir@gmail.com> wrote:
> > > 
> > > > 'no stack' is a bit hype/slogan (could be good to easier
> > > > remembering the subject postulate)
> > > > 
> > > > I mean here that i wonder if c compiler 
> > > > would just not use stack for args and locals 
> > > > and just used static data everywhere by default (axcept the rere
> > > > thing where you explicitely will denote some data as auto
> > > > and such variable would be created/dropped on stack) - if it will
> > > > not make 1) significently simpler 
> > > 
> > > No. Stack managing is simpler
> > > 
> > 
> > why? i dont see it .. 
> 
> There is no linking problems with stack management.
> One only adjust stack pointer.
> 
what linking problems? i do not understand

one not only adjust stack pointer but make couple of pushes, adjust stack pointer, usualy uses esp, then deadjust 
stack pointer - this is noticable work
at any call 
 


> > 
> > > > 2) faster
> > > 
> > > Show example where global data is faster?
> > > Actually stack is almost all the time in cache.
> > > 
> > stack has its cost of its managment,
> 
> but far less than managing global variables...
> That's why it is preferred.
> 

whats is that cost? (of managing static variables)


> > also if you use the same ram lines for
> > reading and writing one args/locals 
> > a while later for other args/locals 
> > you must revrite it etc (acceses are 
> > dependant in time), with static you
> > may just leave one and go to another
> > not waiting
> 
> You forgot that accessing cache is much
> more faster than DRAM.
> 
why do you think i forgot it? i do not understand


> > 
> > thode local and args areas probably 
> > willbe also in cache, some differences my
> > differ but i dont see right now clear reason 
> > for this to work worse
> 
> Nope. They will not be in cache.
> 

why?

> > 
> > > > 3) smaller
> > > 
> > > Nope. Maintaining global variables is bigger.
> > > 
> >  weak answer, (almost like untorelably weak as on my standards of
> > discussion) (do you counted it to say "nope"? do you forget about the
> > push pop in your calulation ?
> 
> You forgot that executable will be bloated with large amount
> of data.
> 
bloated by large amount of what data?

>  (you do not mention it)), also how
> > bigger you get it by adresing not a big amount of .bss (for very
> > small system it could be sparing of couple hundreds of ints - but
> > this is special case you can explicitely make args and locals work on
> > stack by u8sing 'auto')
> 
> Complexity of linking and finding right address far outweighs
> anything even remotely ...
> 
what exact complexity? right now linkers
link module external variables and they are able to do that, seem not to be such hard (though i may overlooked something i was not thinking to much about linking stuff here)


> > 
> > > 
> > > > 4) more potent for some usable techniques
> > > 
> > > What are these?
> > > 
> > probably many techniques that could 
> > work only when you have locals/args
> > static, this is side depth topic here
> > and i probably will say on this but
> > on another ocassion
> 
> Name one?
> 

probably will write on this other day
(do you overloked "this is side depth topic here and i probably will say on this but on another ocassion" ?

those possibilities may be itself a bit
complex and not stright related thing so i dont want to confuse two topics) (in general when you use such static way
you for example can (possibly) read and
write local variables on "large depth distances" thru code branches - something like sending signals etc) something that is inposible with stack implementation..
you could possibly base some interesting language feature on this -- this is partially why i consider this static implementation as a more natural)





> > 
> > > > 
> > > > executables
> > > > 
> > > > (stack would be used for call ret adresses
> > > > and for rare data explicitely denoted as auto (though i wonder if
> > > > such auto data shouldnt be placed on speparate stack, not the
> > > > same as ret/call one)
> > > 
> > > Why? This is almost surely slower.
> > > 
> > > > 
> > > > I seem to being convinced that this static no stack version
> > > > should be considered as a default implementation in c programs)
> > > > (nearly sure that this would be better options, though test
> > > > should be done to prove this, and such test are burdensome a bit)
> > > 
> > > Hm, what about reentrancy and threads?
> > > 
> > what do you mean exactly?
> 
> I mean multi threaded programs, how they would work with static locals
> and god forbid args?
> 

bitt different topic, i was not considered it to much.. there are
multiple options here (like compiler
making static copies for additional 
branches etc, or other).. also side topic so i would prefer to talk on this at another ocassion (not to confuse topics)

> > 
> > > > 
> > > > [fir]
> > > >

[toc] | [prev] | [next] | [standalone]

#58677

ps as to 'linking' i forgot to mention (i mentioned it in other thread) that in general i consider probably best option
to pass args is only send one pointer
to ram structure containing args (placed on caller side) [[[- [send thru register like edx, something like that] -- only some
internal functions can be optimised to stone immediate references its, in general
passing a pointer is needed ]]] + mixing this with fastcall cases if function has few args could be passed by value by registers (++ some rare cases when two pointers to ram structures are pased can be also considered if usefull in rare cases for optimistations etc, but base is send one pointer to args thru register] - thats how i see this convention i got on my mind

[toc] | [prev] | [next] | [standalone]

#58749

W dniu niedziela, 22 marca 2015 13:48:44 UTC+1 użytkownik fir napisał:
> W dniu niedziela, 22 marca 2015 13:23:25 UTC+1 użytkownik Melzzzzz napisał:
> > On Sun, 22 Mar 2015 05:06:27 -0700 (PDT)
> > fir <profesor.fir@gmail.com> wrote:
> > 
> > > W dniu niedziela, 22 marca 2015 12:38:03 UTC+1 użytkownik Melzzzzz
> > > napisał:
> > > > On Sun, 22 Mar 2015 02:09:00 -0700 (PDT)
> > > > fir <profesor.fir@gmail.com> wrote:

> > > > 
> > > > > 4) more potent for some usable techniques
> > > > 
> > > > What are these?
> > > > 
> > > probably many techniques that could 
> > > work only when you have locals/args
> > > static, this is side depth topic here
> > > and i probably will say on this but
> > > on another ocassion
> > 
> > Name one?
> > 
> 
> probably will write on this other day
> (do you overloked "this is side depth topic here and i probably will say on this but on another ocassion" ?
> 
> those possibilities may be itself a bit
> complex and not stright related thing so i dont want to confuse two topics) (in general when you use such static way
> you for example can (possibly) read and
> write local variables on "large depth distances" thru code branches - something like sending signals etc) something that is inposible with stack implementation..
> you could possibly base some interesting language feature on this -- this is partially why i consider this static implementation as a more natural)
> 
> 

for example some things as a long jumps
probably could work better, with such static approach you easily can "cut down"
(long ret) whole branch, do any amount of  side code then resume the branch, and all branch state will be untouched

(right now it is not so easy you would have memcopy some part of the stack
or something like that)

I think many more elaborate microtechniques could be probably
used easily here, for example if you pas some value couple of levels deep down the branch it could be optimised etc etc

[toc] | [prev] | [next] | [standalone]

#58750

W dniu poniedziałek, 23 marca 2015 15:39:54 UTC+1 użytkownik fir napisał:
> W dniu niedziela, 22 marca 2015 13:48:44 UTC+1 użytkownik fir napisał:
> > W dniu niedziela, 22 marca 2015 13:23:25 UTC+1 użytkownik Melzzzzz napisał:
> > > On Sun, 22 Mar 2015 05:06:27 -0700 (PDT)
> > > fir <profesor.fir@gmail.com> wrote:
> > > 
> > > > W dniu niedziela, 22 marca 2015 12:38:03 UTC+1 użytkownik Melzzzzz
> > > > napisał:
> > > > > On Sun, 22 Mar 2015 02:09:00 -0700 (PDT)
> > > > > fir <profesor.fir@gmail.com> wrote:
> 
> > > > > 
> > > > > > 4) more potent for some usable techniques
> > > > > 
> > > > > What are these?
> > > > > 
> > > > probably many techniques that could 
> > > > work only when you have locals/args
> > > > static, this is side depth topic here
> > > > and i probably will say on this but
> > > > on another ocassion
> > > 
> > > Name one?
> > > 
> > 
> > probably will write on this other day
> > (do you overloked "this is side depth topic here and i probably will say on this but on another ocassion" ?
> > 
> > those possibilities may be itself a bit
> > complex and not stright related thing so i dont want to confuse two topics) (in general when you use such static way
> > you for example can (possibly) read and
> > write local variables on "large depth distances" thru code branches - something like sending signals etc) something that is inposible with stack implementation..
> > you could possibly base some interesting language feature on this -- this is partially why i consider this static implementation as a more natural)
> > 
> > 
> 
> for example some things as a long jumps
> probably could work better, with such static approach you easily can "cut down"
> (long ret) whole branch, do any amount of  side code then resume the branch, and all branch state will be untouched
> 

well, forgot that call ret adresses need to be stored , so some memcopy is also
needed, though smaller*, and locals and args state are at least not destroyed

except you will not provide such feature of forward-call x() thru f() g() h()
that would rebuild this small stack path ;/



> (right now it is not so easy you would have memcopy some part of the stack
> or something like that)
> 
> I think many more elaborate microtechniques could be probably
> used easily here, for example if you pas some value couple of levels deep down the branch it could be optimised etc etc

[toc] | [prev] | [next] | [standalone]

#58668

On 22/03/15 13:06, fir wrote:
> W dniu niedziela, 22 marca 2015 12:38:03 UTC+1 użytkownik Melzzzzz napisał:
>> On Sun, 22 Mar 2015 02:09:00 -0700 (PDT)
>> fir <profesor.fir@gmail.com> wrote:
>>
>>> 'no stack' is a bit hype/slogan (could be good to easier remembering
>>> the subject postulate)
>>>
>>> I mean here that i wonder if c compiler
>>> would just not use stack for args and locals
>>> and just used static data everywhere by default (axcept the rere
>>> thing where you explicitely will denote some data as auto
>>> and such variable would be created/dropped on stack) - if it will not
>>> make 1) significently simpler
>>
>> No. Stack managing is simpler
>>
>
> why? i dont see it ..
>

Stack access is done using reg+offset addressing modes, typically 8-bit 
offsets on an x86 machine.  It can also be done using push/pop 
instructions, which are highly optimised for speed and instruction size 
on most cpus.  Stack "management" is rarely more complex than 
occasionally adding to or subtracting from the stack point register as 
frames are entered and left.

Accessing statically allocated data means working with absolute 
addresses, perhaps dealing with segments, global address tables, or 
other more complex memory arrangements (depending on the cpu 
architecture and ABI).  It may involve linking and loading issues, or 
mean larger executable files to hold the information.

At best, if you can afford a dedicated register to allow reg+offset 
addressing modes, then the access to static data takes no more 
instruction space or time (excluding cache issues - see below) than 
accessing stack data.  However, on a register-poor cpu like the x86 
(even amd64), dedicating an extra register is costly - and the lack of 
reg + 16-bit offset (if I understood BartC correctly) means most 
accesses will be bigger and slower.

>>> 2) faster
>>
>> Show example where global data is faster?
>> Actually stack is almost all the time in cache.
>>
> stack has its cost of its managment,
> also if you use the same ram lines for
> reading and writing one args/locals
> a while later for other args/locals
> you must revrite it etc (acceses are
> dependant in time), with static you
> may just leave one and go to another
> not waiting

Reading and re-writing the same lines is the ideal situation as far as 
the cache is concerned.  In modern cpus, access to stack data often 
doesn't even make it as far as the cache - there are cpu buffers 
optimised for stack access so that the data gets read from and written 
to the buffers rather than the cache itself.

Using different addresses, and therefore different cache lines, for your 
arguments and locals is the worst choice from the cache viewpoint - it 
means more lines are needed for the program's critical data.

>
> thode local and args areas probably
> willbe also in cache, some differences my
> differ but i dont see right now clear reason
> for this to work worse
>
>>> 3) smaller
>>
>> Nope. Maintaining global variables is bigger.
>>
>   weak answer, (almost like untorelably weak as on my standards of discussion) (do you counted it to say "nope"? do you forget about the push pop in your calulation ? (you do not mention it)), also how bigger you get it by adresing not a big amount of .bss (for very small system it could be sparing of couple hundreds of ints - but this is special case you can explicitely make args and locals work on stack by u8sing 'auto')
>

Please don't make comments like that - you are already considered a 
pretentious fool by many people here, and telling people that they write 
"weak answers" that are "intolerably weak by my standards" simply 
re-enforces the low opinions.

It is obvious that statically allocated locals and arguments will take 
more data space than a stack, since there is no re-use of the space 
(excluding the case of very smart compilers for very limited embedded 
systems, which work hard to multiplex the data and space).  It is clear 
(as shown above) that using statically allocated locals and arguments 
will typically take more code space.

If you don't understand this, go back and think through this whole idea. 
  Make some samples, and see how it would really work in practice.  Then 
you can come back with evidence and examples, rather than blind statements.


>>
>>> 4) more potent for some usable techniques
>>
>> What are these?
>>
> probably many techniques that could
> work only when you have locals/args
> static, this is side depth topic here
> and i probably will say on this but
> on another ocassion

In other words, you have no idea what "techniques" might be possible here.

>
>>>
>>> executables
>>>
>>> (stack would be used for call ret adresses
>>> and for rare data explicitely denoted as auto (though i wonder if
>>> such auto data shouldnt be placed on speparate stack, not the same as
>>> ret/call one)
>>
>> Why? This is almost surely slower.
>>
>>>
>>> I seem to being convinced that this static no stack version should be
>>> considered as a default implementation in c programs) (nearly sure
>>> that this would be better options, though test should be done to
>>> prove this, and such test are burdensome a bit)
>>
>> Hm, what about reentrancy and threads?
>>
> what do you mean exactly?
>

Do you know what "re-entrancy" means?

<http://en.wikipedia.org/wiki/Reentrancy_%28computing%29>

(Note that I agree with your statement before about recursive functions 
being relatively rare, though perhaps not as rare as you think. 
Re-entrant functions are more common, however, and thread-safe functions 
are becoming the norm on many systems.)

I assume you know what "threads" are, and understand that using static 
allocation for locals, temporaries and arguments means that code cannot 
be shared across threads.


Let me point you towards this:

<http://www.keil.com/support/man/docs/c51/c51_le_reentrantfuncs.htm>

I recommend you read a fair bit of the manual for Keil's 8051 compiler. 
  (Although Keil was bought by ARM a number of years ago, this compiler 
and the 8051 core has nothing to do with ARM's cpu cores.)  It might 
help you understand about a case where static allocation of locals and 
arguments /is/ a useful idea, and the extraordinary effort needed by the 
programmer and the compiler in order to make the whole thing work safely 
and efficiently.

[toc] | [prev] | [next] | [standalone]

#58670

On 22/03/15 13:45, David Brown wrote:

<snip>


> (Note that I agree with your statement before about recursive functions
> being relatively rare,

Even a stopped clock is right twice a day.

> though perhaps not as rare as you think.

I checked three sources at random from my code base - almost 4000 lines 
of code in 93 functions, of which 14 were recursive. Clearly recursive 
functions are in a minority in my code base, but equally clearly it 
isn't an insignificant minority by any means.

<snip>

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#58674

On 22/03/15 15:20, Richard Heathfield wrote:
> On 22/03/15 13:45, David Brown wrote:
>
> <snip>
>
>
>> (Note that I agree with your statement before about recursive functions
>> being relatively rare,
>
> Even a stopped clock is right twice a day.
>
>> though perhaps not as rare as you think.
>
> I checked three sources at random from my code base - almost 4000 lines
> of code in 93 functions, of which 14 were recursive. Clearly recursive
> functions are in a minority in my code base, but equally clearly it
> isn't an insignificant minority by any means.
>

It's going to vary enormously according to the type of code.  If you are 
writing code that uses a lot of tree structures, recursive functions 
turn up all over the place.  But for small embedded systems, recursive 
functions are very rare - they make it much harder to reason about 
maximum stack usage.  Re-entrant functions (called from interrupts or 
multiple threads) are more common than recursive functions in such systems.

[toc] | [prev] | [next] | [standalone]

#58687

On Sunday, March 22, 2015 at 2:20:45 PM UTC, Richard Heathfield wrote:
>
> I checked three sources at random from my code base - almost 4000 lines 
> of code in 93 functions, of which 14 were recursive. Clearly recursive 
> functions are in a minority in my code base, but equally clearly it 
> isn't an insignificant minority by any means.
> 
In C, unless it's written by functional programming addicts, it's
rare to want a recursive function. Really only for walking trees,
and a few "divide and conquer" algorithms that are easier to write
recursively than using a "to do" list.
However if you measure by run time rather than lines of code, often
the recursive functions will be in the majority. Where you need 
them, you usually get an exponential increase with depth. So 
they need to be very tightly coded and efficient.
    

[toc] | [prev] | [next] | [standalone]

#58689

On 22/03/2015 20:09, Malcolm McLean wrote:
> On Sunday, March 22, 2015 at 2:20:45 PM UTC, Richard Heathfield wrote:
>>
>> I checked three sources at random from my code base - almost 4000 lines
>> of code in 93 functions, of which 14 were recursive. Clearly recursive
>> functions are in a minority in my code base, but equally clearly it
>> isn't an insignificant minority by any means.
>>
> In C, unless it's written by functional programming addicts, it's
> rare to want a recursive function. Really only for walking trees,
> and a few "divide and conquer" algorithms that are easier to write
> recursively than using a "to do" list.

It depends on the application and the data it works with.

In my case, with compilers, expression parsers and such, the input is 
language source code which is hierarchical and tree-like (and therefore 
recursion is used extensively). (With interpreters, not so much, but 
there, functions can be re-entrant so that you have take the same care.)

I've also worked with 3D graphics where the display data was 
hierarchical, so the the rendering/processing needed to be recursive. 
And of course file systems are tree-like. Then there are the algorithms 
you mentioned.

In short, recursive code is everywhere. It would be a nuisance to have 
to mark functions as recursive or not.

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#58690

On Sunday, March 22, 2015 at 8:39:08 PM UTC, Bart wrote:
> On 22/03/2015 20:09, Malcolm McLean wrote:
> 
> > In C, unless it's written by functional programming addicts, it's
> > rare to want a recursive function. Really only for walking trees,
> > and a few "divide and conquer" algorithms that are easier to write
> > recursively than using a "to do" list.
> 
> It depends on the application and the data it works with.
> 
> In my case, with compilers, expression parsers and such, the input is 
> language source code which is hierarchical and tree-like (and therefore 
> recursion is used extensively). (With interpreters, not so much, but 
> there, functions can be re-entrant so that you have take the same care.)
> 
> I've also worked with 3D graphics where the display data was 
> hierarchical, so the the rendering/processing needed to be recursive. 
> And of course file systems are tree-like. Then there are the algorithms 
> you mentioned.
> 
> In short, recursive code is everywhere. It would be a nuisance to have 
> to mark functions as recursive or not.
> 
Ironically (or is a fundamental mathematical principle?), structured
programs are tree-like. To make them deal with trees, you have to
break the tree structure by introducing recursion.
 
I find that tree are the most common type of graph, except maybe
for linked lists. But you don't have all that many of them. Most data
comes as nested arrays of structures containing variable-length
members which are arrays of smaller structures. So it's tree-like,
but not really a tree, because each level is different, you
don't have fractal self-similarity. 

I should have remembered parsers, being the proud author of
MiniBasic.

[toc] | [prev] | [next] | [standalone]

#58724

W dniu niedziela, 22 marca 2015 21:54:31 UTC+1 użytkownik Malcolm McLean napisał:
> On Sunday, March 22, 2015 at 8:39:08 PM UTC, Bart wrote:
> > On 22/03/2015 20:09, Malcolm McLean wrote:
> > 
> > > In C, unless it's written by functional programming addicts, it's
> > > rare to want a recursive function. Really only for walking trees,
> > > and a few "divide and conquer" algorithms that are easier to write
> > > recursively than using a "to do" list.
> > 
> > It depends on the application and the data it works with.
> > 
> > In my case, with compilers, expression parsers and such, the input is 
> > language source code which is hierarchical and tree-like (and therefore 
> > recursion is used extensively). (With interpreters, not so much, but 
> > there, functions can be re-entrant so that you have take the same care.)
> > 
> > I've also worked with 3D graphics where the display data was 
> > hierarchical, so the the rendering/processing needed to be recursive. 
> > And of course file systems are tree-like. Then there are the algorithms 
> > you mentioned.
> > 
> > In short, recursive code is everywhere. It would be a nuisance to have 
> > to mark functions as recursive or not.
> > 
> Ironically (or is a fundamental mathematical principle?), structured
> programs are tree-like. To make them deal with trees, you have to
> break the tree structure by introducing recursion.
>  
> I find that tree are the most common type of graph, except maybe
> for linked lists. But you don't have all that many of them. Most data
> comes as nested arrays of structures containing variable-length
> members which are arrays of smaller structures. So it's tree-like,
> but not really a tree, because each level is different, you
> don't have fractal self-similarity. 
> 
> I should have remembered parsers, being the proud author of
> MiniBasic.

besides the fact that flat hand implementation of such tree-recursion 
(in one function made in loop on arrays etc)
(against the function call one)
would be probably always faster
and also more safe

(i could use call form if being lazy
one day but probably revrite it to 
faster form a bit later) (at least for check - i was not writing recursive function for years, once i wrote a quicksort on calls (for test, if data would be crafted instead of log depth level calls i would have N depth calls
(like couple of milion elements to sort
ant there i would have crash, being serious i would need to revrite it on loop and arrays )
, other day A* with cloning front lines of the distance cells in right array-loop
form proof on overflow

so?

(besides im not against natural recursion 
but as i said i would like stack populated-depopulated variables to be noted explicitely (and a gobal flag in compiler allowing compilation of all
stack like today or static as im postulating)

[toc] | [prev] | [next] | [standalone]

#58737

fir <profesor.fir@gmail.com> writes:

> W dniu niedziela, 22 marca 2015 21:54:31 UTC+1 użytkownik Malcolm McLean napisał:
>> On Sunday, March 22, 2015 at 8:39:08 PM UTC, Bart wrote:
>> > On 22/03/2015 20:09, Malcolm McLean wrote:
>> > 
>> > > In C, unless it's written by functional programming addicts, it's
>> > > rare to want a recursive function. Really only for walking trees,
>> > > and a few "divide and conquer" algorithms that are easier to write
>> > > recursively than using a "to do" list.
>> > 
>> > It depends on the application and the data it works with.
>> > 
>> > In my case, with compilers, expression parsers and such, the input is 
>> > language source code which is hierarchical and tree-like (and therefore 
>> > recursion is used extensively).

Another is searching a naturally recursive space -- for example, finding
optimal moves in a game.

<snip>
>> Ironically (or is a fundamental mathematical principle?), structured
>> programs are tree-like. To make them deal with trees, you have to
>> break the tree structure by introducing recursion.

Again I feel obliged to point out that this not a widely held view.  In
fact it is probable a Malcolm-only view.  Recursive algorithms are not
at odds with structured programming.

<snip>
> besides the fact that flat hand implementation of such tree-recursion 
> (in one function made in loop on arrays etc)
> (against the function call one)
> would be probably always faster
> and also more safe

That sounds all wrong to me.  Can you give an example?

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#58745

W dniu poniedziałek, 23 marca 2015 13:07:34 UTC+1 użytkownik Ben Bacarisse napisał:
> fir <profesor.fir@gmail.com> writes:
> 
> > W dniu niedziela, 22 marca 2015 21:54:31 UTC+1 użytkownik Malcolm McLean napisał:
> >> On Sunday, March 22, 2015 at 8:39:08 PM UTC, Bart wrote:
> >> > On 22/03/2015 20:09, Malcolm McLean wrote:
> >> > 
> >> > > In C, unless it's written by functional programming addicts, it's
> >> > > rare to want a recursive function. Really only for walking trees,
> >> > > and a few "divide and conquer" algorithms that are easier to write
> >> > > recursively than using a "to do" list.
> >> > 
> >> > It depends on the application and the data it works with.
> >> > 
> >> > In my case, with compilers, expression parsers and such, the input is 
> >> > language source code which is hierarchical and tree-like (and therefore 
> >> > recursion is used extensively).
> 
> Another is searching a naturally recursive space -- for example, finding
> optimal moves in a game.
> 
> <snip>
> >> Ironically (or is a fundamental mathematical principle?), structured
> >> programs are tree-like. To make them deal with trees, you have to
> >> break the tree structure by introducing recursion.
> 
> Again I feel obliged to point out that this not a widely held view.  In
> fact it is probable a Malcolm-only view.  Recursive algorithms are not
> at odds with structured programming.
> 
> <snip>
> > besides the fact that flat hand implementation of such tree-recursion 
> > (in one function made in loop on arrays etc)
> > (against the function call one)
> > would be probably always faster
> > and also more safe
> 
> That sounds all wrong to me.  Can you give an example?
> 

right now i cant, to burdensome it would take me at least 3 hours to provide two 
versions.. maybe some other day

or if you veru interested try to get some example (dont now, for example dijkstra 
sorthest path on 2d tile map or maybe quicksort of table of ints or something)
in two version call.ret recursion and
one in for loop and arrays - then i can see and comment on this (imo loop and array version should be faster and more safe)






> <snip>
> -- 
> Ben.

[toc] | [prev] | [next] | [standalone]

#58691

On 2015-03-22, Bartc <bc@freeuk.com> wrote:
> In short, recursive code is everywhere. It would be a nuisance to have 
> to mark functions as recursive or not.

Recursion is required in computer science in order to define the
class of "partial recursive functions". This is important because
partial recursive functions are Turing complete: they can compute anything
that a Turing machine can compute.

Any language that requires recursive functions to be specially blessed would
immediately signal to the world "I'm designed by a fucking CS dropout".

[toc] | [prev] | [next] | [standalone]

#58671

W dniu niedziela, 22 marca 2015 14:45:18 UTC+1 użytkownik David Brown napisał:
> On 22/03/15 13:06, fir wrote:
> > W dniu niedziela, 22 marca 2015 12:38:03 UTC+1 użytkownik Melzzzzz napisał:
> >> On Sun, 22 Mar 2015 02:09:00 -0700 (PDT)
> >> fir <profesor.fir@gmail.com> wrote:
> >>
> >>> 'no stack' is a bit hype/slogan (could be good to easier remembering
> >>> the subject postulate)
> >>>
> >>> I mean here that i wonder if c compiler
> >>> would just not use stack for args and locals
> >>> and just used static data everywhere by default (axcept the rere
> >>> thing where you explicitely will denote some data as auto
> >>> and such variable would be created/dropped on stack) - if it will not
> >>> make 1) significently simpler
> >>
> >> No. Stack managing is simpler
> >>
> >
> > why? i dont see it ..
> >
> 
> Stack access is done using reg+offset addressing modes, typically 8-bit 
> offsets on an x86 machine.  It can also be done using push/pop 
> instructions, which are highly optimised for speed and instruction size 
> on most cpus.  Stack "management" is rarely more complex than 
> occasionally adding to or subtracting from the stack point register as 
> frames are entered and left.
> 
> Accessing statically allocated data means working with absolute 
> addresses, perhaps dealing with segments, global address tables, or 
> other more complex memory arrangements (depending on the cpu 
> architecture and ABI).  It may involve linking and loading issues, or 
> mean larger executable files to hold the information.
> 
> At best, if you can afford a dedicated register to allow reg+offset 
> addressing modes, then the access to static data takes no more 
> instruction space or time (excluding cache issues - see below) than 
> accessing stack data.  However, on a register-poor cpu like the x86 
> (even amd64), dedicating an extra register is costly - and the lack of 
> reg + 16-bit offset (if I understood BartC correctly) means most 
> accesses will be bigger and slower.
> 
> >>> 2) faster
> >>
> >> Show example where global data is faster?
> >> Actually stack is almost all the time in cache.
> >>
> > stack has its cost of its managment,
> > also if you use the same ram lines for
> > reading and writing one args/locals
> > a while later for other args/locals
> > you must revrite it etc (acceses are
> > dependant in time), with static you
> > may just leave one and go to another
> > not waiting
> 
> Reading and re-writing the same lines is the ideal situation as far as 
> the cache is concerned.  In modern cpus, access to stack data often 
> doesn't even make it as far as the cache - there are cpu buffers 
> optimised for stack access so that the data gets read from and written 
> to the buffers rather than the cache itself.
> 
> Using different addresses, and therefore different cache lines, for your 
> arguments and locals is the worst choice from the cache viewpoint - it 
> means more lines are needed for the program's critical data.
> 
> >
> > thode local and args areas probably
> > willbe also in cache, some differences my
> > differ but i dont see right now clear reason
> > for this to work worse
> >
> >>> 3) smaller
> >>
> >> Nope. Maintaining global variables is bigger.
> >>
> >   weak answer, (almost like untorelably weak as on my standards of discussion) (do you counted it to say "nope"? do you forget about the push pop in your calulation ? (you do not mention it)), also how bigger you get it by adresing not a big amount of .bss (for very small system it could be sparing of couple hundreds of ints - but this is special case you can explicitely make args and locals work on stack by u8sing 'auto')
> >
> 
> Please don't make comments like that - you are already considered a 
> pretentious fool by many people here, and telling people that they write 


huh, thats enough, you will not change any word more with me (big gain as i am a bit bored reading this bore of yours, join your club and make fun, but it is not main club 'pretentious fool' )

[toc] | [prev] | [next] | [standalone]

#58676

On 22/03/15 15:35, fir wrote:

>
> huh, thats enough, you will not change any word more with me (big
> gain as i am a bit bored reading this bore of yours, join your club
> and make fun, but it is not main club 'pretentious fool' )
>

When you post here, do you have any interest at all in reading the 
replies?  Or is it just because you like the sound of your own voice so 
much?

I gave you a great deal of information on the topic you started, with 
counter-arguments to your ideas along with examples of cases where 
stackless C is relevant.

Yet the only point that you replied to is when I asked you to stop your 
"holier than thou" comments - and you reply with more of the same.

[toc] | [prev] | [next] | [standalone]

#58656

W dniu niedziela, 22 marca 2015 12:38:03 UTC+1 użytkownik Melzzzzz napisał:
> On Sun, 22 Mar 2015 02:09:00 -0700 (PDT)
> fir <profesor.fir@gmail.com> wrote:
> 
> > 
> > (stack would be used for call ret adresses
> > and for rare data explicitely denoted as auto (though i wonder if
> > such auto data shouldnt be placed on speparate stack, not the same as
> > ret/call one)
> 
> Why? This is almost surely slower.
> 
not quite sure if slower and how much, 
maybe yes,.. but i consider this for some other reason (you could make more stacks, those stacks would be cleen (not interleaved return adresses with arg/local data), this could be maybe usefull for some reasons, but this is side topic here and i will say more on this probably some day later not today

[toc] | [prev] | [next] | [standalone]

#58662

On 22/03/15 10:09, fir wrote:
> 'no stack' is a bit hype/slogan (could be good to easier remembering the subject postulate)
>
> I mean here that i wonder if c compiler
> would just not use stack for args and locals
> and just used static data everywhere by default (axcept the rere thing where you
> explicitely will denote some data as auto
> and such variable would be created/dropped on stack) - if it will not make
> 1) significently simpler
> 2) faster
> 3) smaller
> 4) more potent for some usable techniques
>
> executables
>
> (stack would be used for call ret adresses
> and for rare data explicitely denoted as auto (though i wonder if such auto data shouldnt be placed on speparate stack, not the same as ret/call one)
>
> I seem to being convinced that this static no stack version should be considered as a default implementation in c programs)
> (nearly sure that this would be better
> options, though test should be done to prove this, and such test are burdensome a bit)
>

You are almost completely wrong on almost all counts - which is why 
almost all implementations of C use a stack.  Feel free to post any 
evidence for your claims - with enough evidence and justification, you 
might change people's minds.


There is two areas of computing where stackless operation is desirable, 
and outweighs the very significant advantages of the simple, fast and 
efficient stack that is used in most languages.

One is for very limited embedded processors, for which access to stack 
data may be inefficient.  A good example is the 8051 - it is a hideous 
design, and was poor and old-fashioned on the day it was released.  Yet 
for various reasons, it has been a staple choice of core in 
microcontrollers and SoC's for over three decades (fortunately it is now 
rare in new devices).  Accessing data on the stack is slow and awkward, 
requiring multiple instructions - therefore compilers work hard to 
replace stack accesses by static data accesses.  This is not "simpler" 
for the compiler - the toolchains are very complex in order to achieve 
this, and use "whole program" analysis and optimisation to ensure that 
it is safe to make such changes, and to know when functions may be 
recursive or re-entrant.  The techniques do not scale well to bigger 
systems, but are successful for devices with a few tens of K of program 
and typically less than 1 K of data.

The second place that you find stackless systems is in massively 
parallel setups, especially with large numbers of lightweight threads on 
a single system.  Stackless Python, for example, is a Python virtual 
machine that does not require a stack for each lightweight thread.  This 
makes it suitable for modelling flocks of birds on a PC - each "bird" 
has its own independent thread, but without the system overhead of a 
stack for each of them.  Such systems typically require modified or 
limited versions of the "normal" programming language (for example, 
recursion is not allowed).

[toc] | [prev] | [next] | [standalone]

#58843

On Sunday, March 22, 2015 at 4:09:08 AM UTC-5, fir wrote:
> 'no stack' is a bit hype/slogan (could be good to easier remembering the
>  subject postulate)
> 
> I mean here that i wonder if c compiler 
> would just not use stack for args and locals 
> and just used static data everywhere by default (axcept the rere thing 
> where you
> explicitely will denote some data as auto
> and such variable would be created/dropped on stack) - if it will not make 
> 1) significently simpler 

No.  Function arguments and block-scope variables have lifetimes limited to
their enclosing scope; they should not be accessible outside of that scope.

For example:

    int *globalPtr;

    void foo( void )
    {
      int a = 5;
      ptr = &a;
    }

    void bar( void )
    {
      foo();
      printf( "*ptr = %d\n", *ptr );
      *ptr = 6;
    }

This *should* invoke undefined behavior; we're trying to read and update `a`
outside of its lifetime.  If `a` is allocated statically in the
same sense that `ptr` is allocated statically, how would you determine
whether `a` is "live" or not?  You'd have to keep track of what scope you're
in vs. what scope `a` belongs to.  

This does not strike me as "simpler" than using the stack.   

> 2) faster

Probably not; you're trading an increment/decrement on a stack pointer
(which is fast) for a potential page swap (which is not).  

> 3) smaller

Those objects have to be stored *somewhere*, and static objects are usually
stored within the program image itself; you'd be increasing the size
of the executable.

A stack can re-use storage for `auto` objects (provided only one is active
at a time).   

> 4) more potent for some usable techniques

Such as?

> 
> executables
> 
> (stack would be used for call ret adresses
> and for rare data explicitely denoted as auto (though i wonder if such 
> auto data shouldnt be placed on speparate stack, not the same as ret/call 
> one)
> 
> I seem to being convinced that this static no stack version should be 
> considered as a default implementation in c programs)
> (nearly sure that this would be better
> options, though test should be done to prove this, and such test are 
> burdensome a bit)
> 
> [fir]

Why don't you get right on that?

[toc] | [prev] | [next] | [standalone]

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

Back to top | Article view | comp.lang.c

csiph-web