Looking for free memory pool software

[Kelsey Bjarnason]

[snips]

No. But one also learns that to nitpick with nOObs is nothing more than
posturing and complicating issues.

You'd rather we teach them incorrect things? Maybe you would; we
wouldn't.

Big deal. Stacks ARE used and nOObs here use system WITH stacks.

Stacks are used, frequently, for many things. Whether they're used for a
given implementation is not within the scope of the language or the
group, and nothing in either mandates the use of such a structure.

Don't be such a knob jockey. The concept of a stack is paramount to
understanding various C like programming constructs

Really? Like what? How about, oh, recursion? Nope, not necessary at
all. Any FIFO data structure would work - a queue, for example.

bits.

Typo. Sue me.

"stack" has a general meaning.

"Stack" has at least two general meanings; one being a hardware memory
system used to track nested function calls and the like, the other being a
generalized FIFO data structure independent of the hardware.

Note that Malcolm - who started all this - used terms such as "the main C
stack"; there is no such thing, but of the two, the only one which
arguably fits is the hardware version - and no such critter is defined or
required to even exist.

And I would suggest to you that its
impossible to teach recursion or pretty much anything without
considering a concept like or similar to a "stack".

Again, any FIFO structure will do, and whatever is used - hardware,
software stack, software queue or something else - is an implementation
detail, not part of the language as asserted.

Why do you have to complicate simple issues?

The proper question to ask is why does he persist in asserting things
which are simply not true, forcing others to correct them so that newbies
*don't* get confused into thinking his assertions are valid?

 

[Kelsey Bjarnason]

[snips]

Here I think you're using the word "stack" to mean a hardware stack,
not a last-in first-out data structure.

Indeed. Note Malcolm's "the main C stack" and "A stack the only way of
implementing a conforming C compiler."

The former strikes me as only sensibly applicable to a hardware stack or
equivalent; the latter could go either way, but given the former suggests
he is thinking exclusively of something like an x86 machine - a
stack-oriented architecture.

Even if he is speaking of the data structure, C mandates no such thing.

Objects with automatic storage duration are allocated and deallocated in
a strict last-in first-out (i.e., stack-like) manner.

Correct. However, one could readily use a queue; "stack" is not required
anywhere.

The fact that the
standard doesn't use the word "stack" doesn't mean that it isn't one.

Actually, it does mean that. More specifically, it means that one simply
cannot know, ahead of time, how an implementation manages such details -
as a stack, as a queue, as a database if it wants.

The C standard doesn't use the word "subroutine", but if someone asked
whether C supports suboutines, it would be absurd to say that it
doesn't.

Well, what is a subroutine? One needs define the term. If we mean
something akin to blocks of code, callable from arbitrary points of
program execution such that on completion, execution returns to the
instruction immediately following the call, barring termination or other
exceptional events, then obviously it does have them - it calls them
"functions". If one means something else, it may or may not have them.

 

[Eric Sosman]

Hi Keith,

I could not find anything in the ISO/IEC 9899:1999 standard that
specified anything about the order of allocation and deallocation of
objects with automatic storage duration. I thought section 6.2.4 would
have been relevant, but the allocation/deallocation order seems to be
unspecified. Similarly, in the C89 standard, I thought 6.1.2.4 would
be relevant, but again it leaves the order unspecified. Could you
point me to the relevant section please? Is there any way of
determining (in standard C) what the order of deallocation is for
objects with automatic storage duration?

An automatic variable becomes accessible when the flow
of execution enters its block, and ceases to be accessible
when the flow leaves the block. It's not possible to say
exactly when they are "allocated" or "deallocated." Indeed,
some automatic variables may never be allocated at all:

int foo(void) {
int result = rand();
return result - 42;
}

Even a fairly mild optimizer is likely to eliminate the
`result' variable, allocating and deallocating nothing.

The question seems pointless even for variables that do
get allocated and deallocated, because there is no C-observable
change of state when either happens. Allocation occurs at some
unknown time before initialization (if any) and before the first
access to the variable, and deallocation occurs at some unknown
time after the last access. There is nothing you can observe
about the variable before allocation finishes or after deallocation
begins; there are no "constructors" or "destructors" in C.

 

[Keith Thompson]

I could not find anything in the ISO/IEC 9899:1999 standard that
specified anything about the order of allocation and deallocation of
objects with automatic storage duration. I thought section 6.2.4 would
have been relevant, but the allocation/deallocation order seems to be
unspecified. Similarly, in the C89 standard, I thought 6.1.2.4 would
be relevant, but again it leaves the order unspecified. Could you
point me to the relevant section please? Is there any way of
determining (in standard C) what the order of deallocation is for
objects with automatic storage duration?

I believe it follows from C99 6.2.4p4..6:

4 An object whose identifier is declared with no linkage and without
the storage-class specifier static has automatic storage duration.

5 For such an object that does not have a variable length array
type, its lifetime extends from entry into the block with which it
is associated until execution of that block ends in any
way. (Entering an enclosed block or calling a function suspends,
but does not end, execution of the current block.) If the block is
entered recursively, a new instance of the object is created each
time. The initial value of the object is indeterminate. If an
initialization is specified for the object, it is performed each
time the declaration is reached in the execution of the block;
otherwise, the value becomes indeterminate each time the
declaration is reached.

6 For such an object that does have a variable length array type,
its lifetime extends from the declaration of the object until
execution of the program leaves the scope of the declaration. If
the scope is entered recursively, a new instance of the object is
created each time. The initial value of the object is
indeterminate.

and from the semantics of function calls.

 

[Keith Thompson]

"Stack" has at least two general meanings; one being a hardware memory
system used to track nested function calls and the like, the other being a
generalized FIFO data structure independent of the hardware.

You mean LIFO. A stack is last-in/first-out. A queue is
first-in/first-out.

[...]

Again, any FIFO structure will do, and whatever is used - hardware,
software stack, software queue or something else - is an implementation
detail, not part of the language as asserted.

A queue could not be used to implement recursion, at least not on the
usual C manner.

 

[Keith Thompson]

[snips]

Here I think you're using the word "stack" to mean a hardware stack,
not a last-in first-out data structure.

Indeed. Note Malcolm's "the main C stack" and "A stack the only way of
implementing a conforming C compiler."

The former strikes me as only sensibly applicable to a hardware stack or
equivalent; the latter could go either way, but given the former suggests
he is thinking exclusively of something like an x86 machine - a
stack-oriented architecture.

Even if he is speaking of the data structure, C mandates no such thing.

Objects with automatic storage duration are allocated and deallocated in
a strict last-in first-out (i.e., stack-like) manner.

Correct. However, one could readily use a queue; "stack" is not required
anywhere.

A queue doesn't have the required semantics; a stack does.

We're all agreed that a "hardware stack" is not required, and because
"stack" can easily be taken to mean "hardware stack" using the term in
reference to C is a bad idea.

The other sense of the word "stack" refers to a last-in/first-out data
structure, regardless of how it's implemented. It could be a
contiguous array, or a linked list, or anything else that provides
LIFO semantics.

Actually, it does mean that. More specifically, it means that one simply
cannot know, ahead of time, how an implementation manages such details -
as a stack, as a queue, as a database if it wants.

But the allocation and dellocation of objects with automatic storage
duration occurs in a stack-like manner. The data structure used to
implement this, whatever it may be, is by definition a "stack".

Well, what is a subroutine? One needs define the term.

It's a well-known technical term with a reasonably unambiguous meaning
(at least sufficiently unambiguous for our purposes).

 

[Kelsey Bjarnason]

[snips]

You mean LIFO. A stack is last-in/first-out. A queue is
first-in/first-out.

Yes, I meant LIFO.

A queue could not be used to implement recursion, at least not on the
usual C manner.

My bad. I was thinking FIFO, but obviously it's LIFO. Still, stacks
aren't the only LIFO structure and, as noted, one could do it in a
database if one wanted to be really perverse.

Either way, "stack" as Malcolm used it simply need not apply.

 

[Keith Thompson]

An automatic variable becomes accessible when the flow
of execution enters its block, and ceases to be accessible
when the flow leaves the block. It's not possible to say
exactly when they are "allocated" or "deallocated." Indeed,
some automatic variables may never be allocated at all:

[snip]

Good point. I should have referred to the lifetime of objects rather
than to allocation and deallocation.

 

[SM Ryan]

# [snips]
#
# On Sun, 02 Sep 2007 16:20:44 -0700, Keith Thompson wrote:
#
# > Here I think you're using the word "stack" to mean a hardware stack,
# > not a last-in first-out data structure.
#
# Indeed. Note Malcolm's "the main C stack" and "A stack the only way of
# implementing a conforming C compiler."
#
# The former strikes me as only sensibly applicable to a hardware stack or
# equivalent; the latter could go either way, but given the former suggests
# he is thinking exclusively of something like an x86 machine - a
# stack-oriented architecture.

Languages like C actually use two virtual stacks, a protocol
stack and an operand stack, but the language semantics are such
to allow the stacks to be interleaved onto one physical stack.

The consequences of this is the return of values that don't
fit in registers have to copied from one section of the operand
stack to another section over a section of the protocol stack.
The perceived inefficiencies of this copy are why structs
could not be function results in the beginning. Returning arrays
requires three virtual stacks (protocol, fixed size operands,
and variable sized operands), which is even more complicated
to interleave on one hardware stack.

 

[Keith Thompson]

[snips]

You mean LIFO. A stack is last-in/first-out. A queue is
first-in/first-out.

Yes, I meant LIFO.

A queue could not be used to implement recursion, at least not on the
usual C manner.

My bad. I was thinking FIFO, but obviously it's LIFO. Still, stacks
aren't the only LIFO structure and, as noted, one could do it in a
database if one wanted to be really perverse.

I think this is the basic point on which we disagree.

I've certainly seen both contiguous array implementations and linked
list implementations of LIFO's referred to as "stacks". Based on
that, my presuption is that *anything* that implements a LIFO data
structure may reasonable be referred to as a "stack"; it's not about
how it's implemented, it's about what it does. An implementation of a
LIFO on top of a database is a "stack" in that sense.

Would you argue that a contiguous array implementation and a linked
list implementation are both "stacks", but a database implementation
is not?

A quick Google search for computer dictionaries turned up something
called "Webopedia"; it's first definition of "stack" is

In programming, a special type of data structure in which items
are removed in the reverse order from that in which they are
added, so the most recently added item is the first one
removed. This is also called last-in, first-out (LIFO).

I don't claim that this is definitive, but it's consistent with my
understanding.

Either way, "stack" as Malcolm used it simply need not apply.

I no longer remember how Malcolm used the term; I think his wording
was ambiguous.

 

[Keith Thompson]

Languages like C actually use two virtual stacks, a protocol
stack and an operand stack, but the language semantics are such
to allow the stacks to be interleaved onto one physical stack.

[...]

What is an "operand stack"? Do you mean something that's used for
expression evaluation, so that something like

a = b + c * d;

would be implemented as:

push b
push c
push d
mul
add
pop -> a

? If so, certainly a C implementation *could* use something like
that, but there's no implication in the standard that it must.

 

[Martin Golding]

[snips]

Here I think you're using the word "stack" to mean a hardware stack,
not a last-in first-out data structure.

Indeed. Note Malcolm's "the main C stack" and "A stack the only way of
implementing a conforming C compiler."

The former strikes me as only sensibly applicable to a hardware stack
or equivalent; the latter could go either way, but given the former
suggests he is thinking exclusively of something like an x86 machine -
a stack-oriented architecture.

Even if he is speaking of the data structure, C mandates no such thing.

Objects with automatic storage duration are allocated and deallocated
in a strict last-in first-out (i.e., stack-like) manner.

Correct. However, one could readily use a queue; "stack" is not
required anywhere.

A queue doesn't have the required semantics; a stack does.

We're all agreed that a "hardware stack" is not required, and because
"stack" can easily be taken to mean "hardware stack" using the term in
reference to C is a bad idea.

The other sense of the word "stack" refers to a last-in/first-out data
structure, regardless of how it's implemented. It could be a contiguous
array, or a linked list, or anything else that provides LIFO semantics.

Actually, it does mean that. More specifically, it means that one
simply cannot know, ahead of time, how an implementation manages such
details - as a stack, as a queue, as a database if it wants.

But the allocation and dellocation of objects with automatic storage
duration occurs in a stack-like manner. The data structure used to
implement this, whatever it may be, is by definition a "stack".

If I create a hardware/OS set that implements all functions invocations
as if co-routine calls, all of the live functions (those which had been
invoked but had not yet "returned") would have their stack frame
equivalents ("activation records") on the same logical 'level'. Cs
restricted return-only-whence would be a special case of the general
transfer-to-arbitrary-task, limited to the specific task that activated
the current one, with the side effect of deleting the current activation
record. The data structure(s) that managed activation records would be
heap-like, and capable of any of arbitrary, queue-like or stack-like
behavior. Cs apparent lifo behavior for objects with automatic duration
would be the incidental consequence of mere convention.


<OT>
I once wrote a small test-carrier OS for the PDP-11, inspired by the
TI-9900, which managed functions that way. The hardware stack was
usually empty, scrubbed by the interrupt management function that
transferred to the appropriate (already running) service task.
It worked, and was amusing to write for. It was way too small to
support C.
</OT>

That C functions usually have an effectively fixed-size activation
record (but for variable length arrays) means that stack-like systems
should, in general, be more performant than heap-like systems. That
everybody _will_ implement their systems that way doesn't mean that
everybody _must_ implement that way.

Martin

 

[Charlton Wilbur]

R> No. But one also learns that to nitpick with nOObs is nothing
R> more than posturing and complicating issues.

The thread didn't start with someone nitpicking a novice's post; it
started with someone calling Malcolm on an error, and Malcolm getting
defensive about it.

Charlton

 

[Stephen Sprunk]

Hi Keith,

I could not find anything in the ISO/IEC 9899:1999 standard that
specified anything about the order of allocation and deallocation
of objects with automatic storage duration. I thought section 6.2.4
would have been relevant, but the allocation/deallocation order
seems to be unspecified. Similarly, in the C89 standard, I
thought 6.1.2.4 would be relevant, but again it leaves the order
unspecified. Could you point me to the relevant section please?
Is there any way of determining (in standard C) what the order of
deallocation is for objects with automatic storage duration?

The C standard only specifies the "lifetime" of objects, which is stack-like
with respect to blocks. All objects with automatic storage duration in the
same block have the same lifetime, and common systems will usually allocate
(and later deallocate) all of them at the same time. If they don't, that's
due to optimizations under the "as if" rule (e.g. due to non-overlapping
liveness) and thus cannot be detected by a conforming program.

The wording appears to have been chosen very carefully to convey stack-like
semantics and imply that implementation without actually requiring it in
case there are systems where that is not the most efficient or logical
implementation. There are many things in the standard that are worded that
way -- and programmers get themselves in a lot of trouble by assuming what
the standard implies is actually a guarantee (or not even seeing the
difference).

S

 

[Tony Mc]

An automatic variable becomes accessible when the flow
of execution enters its block, and ceases to be accessible
when the flow leaves the block. It's not possible to say
exactly when they are "allocated" or "deallocated." Indeed,
some automatic variables may never be allocated at all:

[snip]

Good point. I should have referred to the lifetime of objects rather
than to allocation and deallocation.

It was the lifetime question I was trying to get at and Eric Sosman
put it much more clearly than my question. However, I am still puzzled
by your claim that there is a "strict last-in first-out (i.e.,
stack-like)" order to the lifetimes of objects with automatic storage.
Here is a simple example that I hope illustrates my question.

void foo(void) {
int i = 42;
float f = i;

...
}

I have no problem with the "last-in" bit since the declaration of f
can use the fact that i has already been initialized to 42. However,
when the closing brace that ends the function is reached, as far as I
can tell, there is nothing in the standard that requires the lifetime
of f to end before the lifetime of i. That is the strict "first-out"
bit that I cannot find. I recognise that it really doesn't matter
since (as far as I can see) there is no way to tell which of i and f
disappears first, but if that is so then surely the standard is not
requiring a "strict last-in first-out" order, but only a strict
"lifetime begins after declaration and ends sometime before the end of
function is reached" order?

Best,
Tony

 

[Eric Sosman]

An automatic variable becomes accessible when the flow
of execution enters its block, and ceases to be accessible
when the flow leaves the block. It's not possible to say
exactly when they are "allocated" or "deallocated." Indeed,
some automatic variables may never be allocated at all:

[snip]

Good point. I should have referred to the lifetime of objects rather
than to allocation and deallocation.

It was the lifetime question I was trying to get at and Eric Sosman
put it much more clearly than my question. However, I am still puzzled
by your claim that there is a "strict last-in first-out (i.e.,
stack-like)" order to the lifetimes of objects with automatic storage.
Here is a simple example that I hope illustrates my question.

void foo(void) {
int i = 42;
float f = i;

...
}

I have no problem with the "last-in" bit since the declaration of f
can use the fact that i has already been initialized to 42. However,
when the closing brace that ends the function is reached, as far as I
can tell, there is nothing in the standard that requires the lifetime
of f to end before the lifetime of i. That is the strict "first-out"
bit that I cannot find. I recognise that it really doesn't matter
since (as far as I can see) there is no way to tell which of i and f
disappears first, but if that is so then surely the standard is not
requiring a "strict last-in first-out" order, but only a strict
"lifetime begins after declaration and ends sometime before the end of
function is reached" order?

The order is LIFO if you consider all of a block's auto
variables as a single "lump;" their lifetimes come and go
with control flow into and out of the block, and the control
flow is itself LIFO (ignoring things like blocks that call
exit() or in some other way cause an abrupt termination).

In the code you show, there is no notion of separate
lifetimes for `i' and `f': As far as a C program can tell
they come into existence and go out again simultaneously.
On many stack-oriented machines this will in fact be true:
One instruction (or short sequence) will reserve stack space
for all the block's variables at one blow, and one instruction
(or sequence) will reclaim the space when the block ends. On
other machines things may be different -- but C is not able
to observe the differences, so only compiler writers need be
concerned with them. "If a tree falls in a deserted forest ..."

Note that I'm referring to the variables' lifetimes, that
is, to the intervals when they are accessible and able to store
values. Initialization is a different matter. There's no way
to observe differences in the lifetimes of auto variables that
belong to the same block, but sequencing of initialization is
observable. For example:

void foo(void) {
int i = printf("Hello, world ");
int j = printf(" #%d!\n", ++i);
...
}

It is clear that `i' is initialized before `j' and `j' after
`i', even though their lifetimes remain hazy.

 

[Bart van Ingen Schenau]

Languages like C actually use two virtual stacks, a protocol
stack and an operand stack, but the language semantics are such
to allow the stacks to be interleaved onto one physical stack.

[...]

What is an "operand stack"?

As I understand the post, SM Ryan used the terms 'protocol stack'
and 'operand stack' in this way:

Protocol stack: data structure with stack semantics that contains the
return addresses for the currently active functions.

Operand stack: data structure with stack semantics that contains the
arguments and return values of the currently active functions.

I can't tell how common this usage of the terms is. I, at least, had not
heard it before.

This distinction between two stacks can be useful if a system only has
hardware support for, for example, a stack of return addresses.

Bart v Ingen Schenau

 

[Kelsey Bjarnason]

[snips]

Would you argue that a contiguous array implementation and a linked
list implementation are both "stacks", but a database implementation
is not?

Quite possibly. What this has to do with "the C main stack" isn't clear,
and this is the thing Malcolm was going on about. There is no such thing.

 

[Richard]

[snips]

Would you argue that a contiguous array implementation and a linked
list implementation are both "stacks", but a database implementation
is not?

Quite possibly. What this has to do with "the C main stack" isn't clear,
and this is the thing Malcolm was going on about. There is no such
thing.

Yes there is.

Would you also contend that there are "no such things" as global
variables in C?

You can be as clever as you like but everyone KNOWS what is meant be the
C Stack. Whether conceptual or physical. It is there in one form or
another.

Luvaduck.

 

[Kelsey Bjarnason]

[snips]

Would you argue that a contiguous array implementation and a linked
list implementation are both "stacks", but a database implementation
is not?

Quite possibly. What this has to do with "the C main stack" isn't clear,
and this is the thing Malcolm was going on about. There is no such
thing.

Yes there is.

Really? And what exactly would this be?

You can be as clever as you like but everyone KNOWS what is meant be the
C Stack.

I don't. Haven't got a clue what it's supposed to mean. I know the
implementation must meet certain requirements, among which is the ability
to call functions, even recursively, but I don't see anything which
mandates this be done via a stack, either hardware or data structure.
Perhaps you could show us where this is documented?

Would you also contend that there are "no such things" as global
variables in C?

Depends - what's a "global variable"? Is that a variable with file scope,
or is it one which is "automagically" visible to all code in the project?
Or something else?

I think the problem here is that you look at these things and thing "Gee,
this stuff is so simple, how come these guys don't get it?" without
stopping to realize that there just might be very good reasons *why* the
standard uses terms such as "file scope" rather than "global variable",
"header" rather than "header file" and so forth.