«

In article <fi1c6s$pvc$>, jacob navia <> wrote
on Wednesday 21 Nov 2007 7:05 pm:

> cr88192 wrote:
>> "jacob navia" <> wrote in message
>> news:fi13tb$rbr$...

<snip>

>> but, it is maybe interesting from a theoretical perspective, aka:
>> a C-implementation allocating all the call frames on a heap.
>>
>> so, we want a call frame?
>> grab it from a free-list (or, somehow, allocate more if needed).
>>
>> need to store locals? grab a chunk of memory for this and attach to
>> call frame.
>> need space for args? likewise, grab a chunk of memory, evaluate and
>> store in the args, and attach it to the (newly created) call frame of
>> the function being called.
>>
>
> So, you are implementig the stack in software. Instead of doing a
> single register subtract, you allocate memory, put that in the list
> of active frames, etc etc!
>
> That would be really bad for performance

I think that with a lot of restrictions on usage a software stack can
compete reasonably well with a hardware one. The actual memory is very
likely to be held in the CPU caches and the machine instructions to
manipulate the stack are also likely to be very similar.

Of course, using a software stack when dedicated hardware support is
available is probably unnecessary unless special flexibility is needed.

And it's not within the spirit of C, as I understand it, to chose
inefficient means to do what _can_ be done more efficiently, time and
space wise.

<snip>

"jacob navia" <> wrote in message
news:fi1c6s$pvc$...
> cr88192 wrote:
>> "jacob navia" <> wrote in message
>> news:fi13tb$rbr$...
>>> cr88192 wrote:
>>>> "CBFalconer" <> wrote in message
>>>> news:...
>>>>> Paul Hsieh wrote:
>>>>> ... snip ...
>>>>>> It forces call stack uniformity (the EH needs to be able to crawl up
>>>>>> the stack and unwind the stack in a uniform way.) So for example,
>>>>> To bring things back to reality, there is no reason to have a stack
>>>>> in any C system.
>>>>>
>>>> errm?...
>>>>
>>>> what kind of 'reality' is it you are living in?...
>>>>
>>>>
>>> Mr Falconer has his own world, as many people here around.
>>>
>>> A stack is not necessary, one complement or sign magnitude
>>> representations rule the world, etc etc.
>>>
>>> I think we have touched a trap representation
>>>
>>>
>>
>> yes, ok.
>>
>>
>> but, it is maybe interesting from a theoretical perspective, aka:
>> a C-implementation allocating all the call frames on a heap.
>>
>> so, we want a call frame?
>> grab it from a free-list (or, somehow, allocate more if needed).
>>
>> need to store locals? grab a chunk of memory for this and attach to call
>> frame.
>> need space for args? likewise, grab a chunk of memory, evaluate and store
>> in the args, and attach it to the (newly created) call frame of the
>> function being called.
>>
>
> So, you are implementig the stack in software. Instead of doing a
> single register subtract, you allocate memory, put that in the list
> of active frames, etc etc!
>
> That would be really bad for performance

yes, as noted in the prev post, a notable performance hit...

a special purpse allocator would be needed hopefully to keep the performance
from being too horrible (in this case, allocating each frame would consist
of a few operations to grab the pieces from the appropriate free-lists).

for example:
;grab a frame
mov ecx, [__magic_frame_free_list]
mov eax, [ecx]
mov [__magic_frame_free_list], eax
;grab args
mov edx, [__magic_args_free_list2]
mov eax, [edx]
mov [__magic_args_free_list2], eax
;do other stuff
....

note that, some means would be needed to make sure free-lists are never
empty (that, or, insert code to check, but this is worse...).


though, it may not be worthwhile in terms of supporting continuations, it
could be worthwhile in allowing an implementation which allows lexical
scoping and closures (assuming some more explicit and cheaper means were not
used in implementing closures instead).


>> ...
>>
>> afaik, this particular approach is used in many scheme implementations,
>> for the reason that it makes implementing call/cc really fast and easy
>> (we can jump outword to some enclosing call frame, do stuff, or jump
>> right back into a call frame we had previously jumped out of).
>>
>
> call/cc is completely UNREADABlE. You do not see in the program text
> where the program is going, you have to figure out what is the current
> continuation!!!!!
>
> That was something completely NUTS!
>

yes...

well, in some of my previous VMs, I generally ended up preferring stacks
over heap-based frames, since function calls are all the time, but
continuations are rare...

it is then acceptable to allow call/cc to do some pretty drastic stuff
(stack cloning, ...), but otherwise have fairly fast execution...

actually, in my last lang which still had continuations, I ended up
initially spliting full and partial continuations, allowing much faster
exit-only continuations (since, IME, this is about the only way I ever
really used them).

I think in this case I may have neglected to fully implement full
continuations.


>
>> some people have used call/cc as a way of implementing multithreading
>> from within scheme itself, ...
>>
>
> Fine... When it works. When it doesn't, I would not like to be
> the one debugging that stuff.
>

yeah, I had typically implemented more traditional threading.


>>
>>
>> interesting? maybe.
>> practical? probably not.
>
> I agree with that!
>

yes.


> --
> jacob navia
> jacob at jacob point remcomp point fr
> logiciels/informatique
> http://www.cs.virginia.edu/~lcc-win32

"santosh" <> wrote in message
news:fi1dn0$gca$...
> In article <fi1c6s$pvc$>, jacob navia <> wrote
> on Wednesday 21 Nov 2007 7:05 pm:
>
>> cr88192 wrote:
>>> "jacob navia" <> wrote in message
>>> news:fi13tb$rbr$...
>
> <snip>
>
>>> but, it is maybe interesting from a theoretical perspective, aka:
>>> a C-implementation allocating all the call frames on a heap.
>>>
>>> so, we want a call frame?
>>> grab it from a free-list (or, somehow, allocate more if needed).
>>>
>>> need to store locals? grab a chunk of memory for this and attach to
>>> call frame.
>>> need space for args? likewise, grab a chunk of memory, evaluate and
>>> store in the args, and attach it to the (newly created) call frame of
>>> the function being called.
>>>
>>
>> So, you are implementig the stack in software. Instead of doing a
>> single register subtract, you allocate memory, put that in the list
>> of active frames, etc etc!
>>
>> That would be really bad for performance
>
> I think that with a lot of restrictions on usage a software stack can
> compete reasonably well with a hardware one. The actual memory is very
> likely to be held in the CPU caches and the machine instructions to
> manipulate the stack are also likely to be very similar.
>
> Of course, using a software stack when dedicated hardware support is
> available is probably unnecessary unless special flexibility is needed.
>
> And it's not within the spirit of C, as I understand it, to chose
> inefficient means to do what _can_ be done more efficiently, time and
> space wise.
>

yes, I agree...

what I was writing about was actually, something a little odd, namely
compiling C in a way very much unlike C...
in effect, it would be compiling C like it were scheme.

as for "special flexibility", at least in scheme implementations, where this
kind of thing is often done, this adds in features like easy support for
continuations and lexical scoping (neither of which are traditionally
present in C).

this is because, with a non-linear memory structure, we can determine, for
example, that something in a function will "capture" the state from that
function (such as the current continuation, part of the lexical scope, ...).
as a result, when the function returns (after this capture has occured), the
call or environment frames are not released (this is possible to determine
statically because things like 'lambda' or 'call/cc' are visible lexically,
though special considerations exist for call/cc).

this is not too terrible of a problem, since, the memory layout is
non-linear, later calls simply use different frames and different memory.


of course, probably a better approach performance-wise would be to switch
out the approach, and only really use call-frames in the case where closures
or continuations are used (closures are easier than continuations, because
although closures are always visible lexically, the use of a continuation
may not be).

luckily, the most common use of a continuation is to implement something
analogous to longjmp (said 'partial' or 'exit-only' continuations). these do
not require as much in terms of special treatment.

but, usage of full continuations are a problem, since they apply potentially
to the entire call graph.

another common approach, makes code itself fast, but call/cc very expensive.
this is an approach focusing around saving/restoring the stack (call/cc
saves the stack, and using a continuation restores it). another approach I
have heard of, is to implement each continuation as a seperate thread (how
this is done in practice I am less certain of, the basic idea is that
call/cc either forks or spawns duplicate threads, and invoking a
continuation causes executon to continue from that thread, or something...).

or such...


> <snip>
>

cr88192 wrote:
> "Tor Rustad" <> wrote in message
> news:...
>> cr88192 wrote:
>>> "Tor Rustad" <> wrote in message
>> [...]
>>
>>>> IMO, the main domain of C is system and embedded development. Even if
>>>> extending this domain by including communication, security development
>>>> and DB engine development, a GC seems neither important, or of much
>>>> interest.
>>>>
>>> errm, are you trying to claim that all of us good old desktop-pc
>>> developers are all off using stuff like Java and C# or something?...
>> No, I say that C1X should focus on the main domain of C, and try to keep
>> the language small and simple. The C99 variable-length arrays was a step
>> too far. Adding GC to Standard C, would IMO be a major mistake.
>>
>
> I will agree to a point here:
> those kind of arrays, IMO, do not belong within the main language.
>
> but, GC is a runtime feature, and it is very sensible that it be left out
> for embedded targets.

Yes, perhaps the fragmentation of memory issue when using GC has been
solved these days, but not long ago, it wasn't AFAIK. Besides, my MISRA
C copy, prohibits non-deterministic memory allocations anyway.


> I was not arguing for standardized GC though, only that GC, itself, has
> value. where and for who it has value, are the people who use it.

Well, we do discuss in the context of Standard C here, so when a
non-existing features is the subject, particularly when OP is J.N. (!)
-- I assume he want it added.

>>> must of us are in a land where we still want things like GC, but don't
>>> feel like selling our souls to some proprietary VM framework to get it.
>> Nobody is stopping you from using the Boehm GC.
>>
>
> what do you think I was arguing through most of the thread?...
>
> this is what I was arguing, that using Boehm is a very valid and sensible
> option (however, certain other people were opposing that GC has use in C
> land, ever...).

I have never used GC myself, but has no strong feelings against some
high-level applications using such libraries, but I wouldn't like to see
a GC during audit, in security and/or safety related software.

--
Tor < | tr i-za-h a-z>

On Nov 20, 6:51 pm, CBFalconer <cbfalco...@yahoo.com> wrote:
> Paul Hsieh wrote:
> ... snip ...
> > It forces call stack uniformity (the EH needs to be able to crawl up
> > the stack and unwind the stack in a uniform way.) So for example,
>
> To bring things back to reality, there is no reason to have a stack
> in any C system.

Not only are you wrong, but you preface it in a way that makes you
even wronger. Amazing.

Functions calls are to push as return is to pop. It might not be
*called* a stack, but it *IS* a stack, and this has nothing to do with
system implementation details. The C *STANDARD* implicitly implements
a stack.

And as long as we are talking about reality, we should note that most
C implementations use a literal common stack for both return/link
addresses and autos.

You may have meant that you don't need a particular implementation of
a hardware stack. But that's irrelevant to the point I am making. To
run an exception the system, one way or another needs to implement
"pop (return) until catch found" at runtime without actually executing
the returns, which means that a uniform "pseudo-return" has to exist
outside of implicit execution.

Using longjmp is insufficient because you can set catch #1, then call
into something, then set catch #2, then return enough times to make
catch #2 no longer in the call stack scope, thus re-enabling catch
#1. If you throw/raise at this point, you expect catch #1 to be
triggered -- not catch #2, and not vacated entirely (and simply
leading to a runtime error.) That means these catches must exist at
each level of the call stack.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

(This is now about "stack unwinding", as in throw in C++ or longjmp
in C, rather than GC.)

In article <9cf1f1cc-7eab-409d-be77->
Paul Hsieh <> wrote:
>Functions calls are to push as return is to pop. It might not be
>*called* a stack, but it *IS* a stack ...

Indeed, function call and return -- and exception-handling or nested
setjmp() operations -- function as a kind of stack. There are some
significant differences between C and C++ here though, including
the fact that in C, the onus of "using longjmp only in a stack-like
manner" is placed entirely on the C programmer. A C++ programmer
using "throw" cannot accidentally pass an invalid goto-label-buffer
(C's "jmp_buf").

>And as long as we are talking about reality, we should note that most
>C implementations use a literal common stack for both return/link
>addresses and autos.

Most, but not all. Significantly, many modern compilers optimize
"leaf" procedures to avoid separate stack frames, and some (probably
not as many) will use both "fake" and "real" frame pointers (as on
MIPS CPUs, where a frame pointer is generally used only if the size
of the stack frame varies, e.g., due to C99 VLAs).

>... To run an exception the system, one way or another needs to implement
>"pop (return) until catch found" at runtime without actually executing
>the returns, which means that a uniform "pseudo-return" has to exist
>outside of implicit execution.

One should, however, note that "uniform" can apply only after a
sort of union operation. The stack-unwind code might, for instance,
read something like this (here target_frame is assumed to be given
directly via longjmp; for exceptions it has to be calculated):

target_frame = jmpbuf_info[0]; /* or whatever index */
while (curframe != target_frame) {
switch (calculate_frame_type(curframe)) {
case FRAME_IN_LEAF_FUNCTION: /* can only happen once */
prevframe = jmpbuf_info[1]; /* or whatever */
break;
case FRAME_WITH_REAL_FRAME_POINTER:
prevframe = curframe->prev;
break;
case FRAME_WITH_VIRTUAL_FRAME_POINTER:
prevframe = curframe + compute_offset(curframe);
break;
default:
__panic("longjmp");
/* NOTREACHED */
}
}

>Using longjmp is insufficient because you can set catch #1, then call
>into something, then set catch #2, then return enough times to make
>catch #2 no longer in the call stack scope, thus re-enabling catch
>#1.

Indeed. However, longjmp() is *also* insufficient simply because
it just does not work properly: it may trash any non-"volatile"-qualified
variables local to the target of the longjmp()[*]. But if the compiler
is clever enough (i.e., so that setjmp/longjmp do not destroy local
variable values; and note that longjmp() is provided by the
compiler-writer, who can decide whether his compiler is sufficiently
clever), the same kinds of innards used in longjmp() *can* be used
to implement exceptions, as long as "catch" records something about
the call stack and "throw" can use that to decide whether catch-#2
is "active", for instance.

In the case of several real GCC implementations, throw really does
work a lot like the above, with the target frame being computed
somewhat dynamically and calculate_type_frame() and compute_offset()
being rather complicated operations that match the "instruction
pointer" (PC or IP register, typically) of the supplied frame[%]
against large "exception info" tables, all so that ordinary function
call and return need not manipulate the current catch stack. (In
other words, the compiler throws code-space at the problem, to
avoid a time penalty.)

[* If I had been writing the C standard, I think I would have
forced compiler-writers to handle setjmp/longjmp non-local "goto"
operations "correctly". In other words, I would have put the
burden on compiler-writers instead of C programmers, so that C
programmers would not have to mark variables "volatile" to get
predictable behavior when using longjmp.]

[% Even worse, the return-PC is often not in that frame, but rather
one frame away and/or "adjusted" somehow. Some CPUs save the PC
of the "call" instruction, some save the PC of the "next" instruction.
Some even have funny special-case frames in which multiple PCs are
saved. If longjmp and/or throw are to work across "exception"
frames, including Unix-like signal handlers, these also must be
handled.]
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

Paul Hsieh wrote:

> On Nov 20, 4:31 am, Chris Dollin <chris.dol...@hp.com> wrote:

>> It might not be zero, unless there's a way to tell the compiler to
>> compile compilation units assuming that they'll be used in an EH-free
>> program: it's possible that code that might execute in an EH
>> environment might suffer optimisation penalties. On the other hand,
>> I don't see that they'd be much different from any penalties already
>> paid for set/longjmp.
>
> The set/longjmp storage is handled by the programmer. With EH, it has
> to dynamically be stored somewhere -- presumably in the stack itself
> (this seems to be the only solution that would make sense in multi-
> threaded environments.)

I meant optimisation opportunities for the non-exceptional code, not mere
storage for the jmp_buf equivalent.

When you have exceptions, there are (possibly) more places at which the
behaviour of the code is constrained, and hence more places where an
optimisation cannot be applied.

Working out a specification [and implementation] for exceptions-in-C
which is effective /and/ doesn't mess C up for the microoptimisationophiles
is, I believe, non-trivial, and (bringing me back to my earlier position
statement) significantly harder than namespaces would be. IMAO.

--
Chris "glad I don't have to do it" Dollin

Hewlett-Packard Limited Cain Road, Bracknell, registered no:
registered office: Berks RG12 1HN 690597 England

cr88192 wrote:

> as for "special flexibility", at least in scheme implementations, where this
> kind of thing is often done, this adds in features like easy support for
> continuations and lexical scoping (neither of which are traditionally
> present in C).

Nitpick: C /is/ lexically scoped. What C doesn't have is /full/ lexical
scoping, across nested functions, because it doesn't have nested functions
at all.

[One of the benefits of garbage collection being built-in to a language
is that it can handle the really full bits of lexical scoping where a
function that refers to a local variable from an enclosing function
/can be exported/ as a fully-fledged function object. Doing that with
neither GC nor storage leaks is ... harder.]

--
Chris "seeking a life of ease and comfort" Dollin

Hewlett-Packard Limited registered no:
registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England

"Tor Rustad" <> wrote in message
news:-5-...
> cr88192 wrote:
>> "Tor Rustad" <> wrote in message
>> news:...
>>> cr88192 wrote:
>>>> "Tor Rustad" <> wrote in message
>>> [...]
>>>
>>>>> IMO, the main domain of C is system and embedded development. Even if
>>>>> extending this domain by including communication, security development
>>>>> and DB engine development, a GC seems neither important, or of much
>>>>> interest.
>>>>>
>>>> errm, are you trying to claim that all of us good old desktop-pc
>>>> developers are all off using stuff like Java and C# or something?...
>>> No, I say that C1X should focus on the main domain of C, and try to keep
>>> the language small and simple. The C99 variable-length arrays was a step
>>> too far. Adding GC to Standard C, would IMO be a major mistake.
>>>
>>
>> I will agree to a point here:
>> those kind of arrays, IMO, do not belong within the main language.
>>
>> but, GC is a runtime feature, and it is very sensible that it be left out
>> for embedded targets.
>
> Yes, perhaps the fragmentation of memory issue when using GC has been
> solved these days, but not long ago, it wasn't AFAIK. Besides, my MISRA C
> copy, prohibits non-deterministic memory allocations anyway.
>

ok.


>
>> I was not arguing for standardized GC though, only that GC, itself, has
>> value. where and for who it has value, are the people who use it.
>
> Well, we do discuss in the context of Standard C here, so when a
> non-existing features is the subject, particularly when OP is J.N. (!) --
> I assume he want it added.
>

ok.

well, I have not been reading his posts long enough to know what he thinks.


>>>> must of us are in a land where we still want things like GC, but don't
>>>> feel like selling our souls to some proprietary VM framework to get it.
>>> Nobody is stopping you from using the Boehm GC.
>>>
>>
>> what do you think I was arguing through most of the thread?...
>>
>> this is what I was arguing, that using Boehm is a very valid and sensible
>> option (however, certain other people were opposing that GC has use in C
>> land, ever...).
>
> I have never used GC myself, but has no strong feelings against some
> high-level applications using such libraries, but I wouldn't like to see a
> GC during audit, in security and/or safety related software.
>

yes, it is not the best idea, everywhere.

I don't expect it to be a magic bullet everywhere or anything. so, for some
subsystems I use it, and for others, I don't.

for example, I have certain libraries in my projects which, very simply,
don't use GC...


a lot depends on the specific design philosophy of that particular
subsystem.
some subsystems are very single-tasked, and generally follow a "closed"
design, and generally do not use any GC or other features (and are very
strict and do not allow any dependency on external code, or, for one of my
libs, severely limits allowed internal access as well).

other libs are a lot more open, and depend on many other subsystems, and
tend to rely fairly heavily on GC.


> --
> Tor < | tr i-za-h a-z>

On 19 Nov 2007 08:54:05 GMT, (Richard Tobin)
wrote:

> In article <>,
> Ben Bacarisse <> wrote:
>
> >You miss my point. Conservative GC is always "safe" since anything that
> >even looks like a reference will prevent memory from being freed
>
> In C, you do have to keep pointers as things that look like a

IRRTYM you _don't_ have to.

> reference. You can memcpy() the bits of a pointer and shuffle them
> up, wait a while, then unshuffle them and store them back in a
> pointer. You can even print them out to a file. No GC is going to
> handle that unaided.
>
- formerly david.thompson1 || achar(64) || worldnet.att.net