static, global variable memory allocation

[CBFalconer]

.... snip ...

This is right for common implementations, but it doesn't have to
work like that. And auto variables are commonly stored in
registers as well as on the stack.

(I assume you mean "heap" rather than "head", though the idea of
allocating variables in the user's brain appeals.)

The OPs nomenclature works quite well with my favorite malloc
implementation, which consists of assignment of small boys with
slates and chalk.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[matevzb]

Richard Heathfield wrote On 02/06/07 14:03,:






I've got the opposite question: Does anyone know why
"heap" has come to mean just a big bucket of bytes, while
once upon a time it meant a specific kind of binary tree
(c.f. Heapsort)?

Presumably to differentiate it from the stack - which is an ordered
pile and the heap isn't. Interestingly, stack seems to be mentioned
more often than heap, e.g. B reference manuals contain... erm... heaps
of stack?

 

[Eric Sosman]

matevzb wrote On 02/06/07 16:30,:

Presumably to differentiate it from the stack - which is an ordered
pile and the heap isn't. Interestingly, stack seems to be mentioned
more often than heap, e.g. B reference manuals contain... erm... heaps
of stack?

The first time I encountered what we now call a "stack,"
it was called a "roll." That seems to have been an unusual
term; the more common phrase was "push-down list," usually
abbreviated "PDL" and pronounced "puddle." (When you ran out
of what we call "stack space," you had a "puddle overflow.")

Knuth also lists "reversion storage," "nesting store,"
"pile," "last-in-first-out list," and "yo-yo list" as terms
that have been used for "stack." Of these, the only one I
ever personally encountered was "LIFO list" (or sometimes
"LIFO stack," which nowadays seems redundant).

As for "heap," it had its "specially-structured binary
tree" meaning at least as far back as 1964 when Williams
invented Heapsort. Can anyone cite a pre-1964 computer-
related use of "heap" in the "big bag of bytes" sense? Or
has a once-precise term been stripped of its precision?

 

[Richard Tobin]

I was now specifically aware of that, to be hones I gave up caring
before I started programming on Unix, but given:
static const char var[]="Static array";
Would you expect var to be in that area you refer to as a heap or, as I
would hope, in a separate memory region that was set to read only?

I'm not sure that the semantics of const allow it to be read-only, but
supposing it does, I'm not sure you couldn't say that part of the
heap was read-only. Equally part of it could be autmoatically zeroed.

On reflection, I agree it's probably better not to call the
statically-allocated data part of the heap.

-- Richard

 

[Richard Tobin]

I've got the opposite question: Does anyone know why
"heap" has come to mean just a big bucket of bytes, while
once upon a time it meant a specific kind of binary tree
(c.f. Heapsort)?

I'm not convinced that it actually happened in that order. For
example, Algol 68 used the word "heap" to mean storage with indefinite
(rather than stack-like) extent.

-- Richard

 

[Eric Sosman]

Richard Tobin wrote On 02/06/07 17:45,:

I'm not convinced that it actually happened in that order. For
example, Algol 68 used the word "heap" to mean storage with indefinite
(rather than stack-like) extent.

According to Knuth, Heapsort dates from 1964.

 

[Keith Thompson]

Richard Heathfield a écrit :

Yes, I should have said:
"the memory area returned by malloc, and assigned to m"
In the next sentence I explained "m", and I should have
make it clear.

[...]

As long as we're being precise, malloc does not return a memory area,
and the memory area is not assigned to m. malloc returns *a pointer
to* a memory area, and that pointer is assigned to m. I know that's
what you meant, but it's helpful to newbies to describe it correctly,
especially in a followup correcting an earler imprecise statement.
The distinction between a pointer and what it points to is a common
source of confusion.

 

[Flash Gordon]

Richard Tobin wrote, On 06/02/07 22:37:

I was now specifically aware of that, to be hones I gave up caring
before I started programming on Unix, but given:
static const char var[]="Static array";
Would you expect var to be in that area you refer to as a heap or, as I
would hope, in a separate memory region that was set to read only?

I'm not sure that the semantics of const allow it to be read-only, but
supposing it does,

I believe modifying a const qualified objects invokes undefined
behaviour so it does.

> I'm not sure you couldn't say that part of the
heap was read-only. Equally part of it could be autmoatically zeroed.

On reflection, I agree it's probably better not to call the
statically-allocated data part of the heap.

 

[Keith Thompson]

The memory allocated by malloc (if any) is taken from the free
store, for which the term "heap" may or may not be applicable on any
particular platform. Note also that m is not freed. What is freed is
the memory (if any) that was allocated by malloc.

[...]

That raises an interesting question about the word "heap".

The words "stack" and "heap" occur nowhere in the C standard. It's
(too) common to refer to the area used to allocate automatic objects
as the "stack", but I think most of us agree that this is misleading
and incorrect. The word "stack", in this context, implies a
CPU-specific region of memory that grows linearly in one direction,
controlled by a "stack pointer" that is typically (but not always) a
dedicated CPU register. Clearly there are C implementations that
don't use this mechanism. On the other hand, automatic objects are
certainly allocated and deallocated in a stack-like (last-in
first-out) manner, so in that sense, the term "stack" might be
appropriate. But the CPU-specific meaning is so strong that this is
misleading, at least when we're talking about the requirements of the
C language rather than the details of a particular implementation.

The word "heap" on the other hand, doesn't seem to carry the same kind
of semantic baggage. In my understanding, the term "heap" refers to a
region of memory used for dynamic allocation (malloc/free, new/delete,
or whatever); there is at most a weak impliciation that it's
contiguous. Though the standard doesn't use the word "heap", I'm
beginning to think that it's reasonable to use that word informally to
refer to the <whatever> from which malloc() allocates memory, and to
which free() returns it. In other word's I see the word "heap" as
having just the right level of vagueness to describe the general
underlying mechanism used by malloc and free.

Are there any real-world systems (with C implementations supporting
malloc() and free()) for which the term "heap" would be inappropriate?
If so, what and why? Are there even any *theoretical* systems for
which the term "heap" would be in appropriate; if so, why?

I'm aware of the other meaning of "heap" as a particular kind of tree
data structure; IMHO that's sufficiently distinct that it's (almost)
always easy to determine which is meant from the context.

Thoughts?

 

[CBFalconer]

.... snip ...

I'm aware of the other meaning of "heap" as a particular kind of
tree data structure; IMHO that's sufficiently distinct that it's
(almost) always easy to determine which is meant from the context.

It's also used to refer to:

1. A pile of hot steaming dung (horse or cow).
2. A quantity of whipped cream on hot apple pie.
3. A task load.

and I'm sure the fertile minds around here can find more. 1 and 2
are manipulated with forks. Possibly also 3.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Ark]

Eric Sosman wrote:

And the bigger issue: If you faced and aced a string
of such questions in an interview and were offered the
job, would you take it? Or would you flee?

<snip>

With all due respect...
Not everyone (even in this NG) is certain about jobs.
Yes, I would take it. And then try to convey some thoughts to my newly
acquired boss. In perhaps then, flee

- Ark

 

[Ark]

I've got the opposite question: Does anyone know why
"heap" has come to mean just a big bucket of bytes, while
once upon a time it meant a specific kind of binary tree
(c.f. Heapsort)?

If I am not mistaken, a plausible (and historically, actual)
implementation of malloc was based on the heap data structure.
I guess, the name stuck 'coz feels right.
- Ark

 

[Dik T. Winter]

> The word "stack", in this context, implies a
> CPU-specific region of memory that grows linearly in one direction,
> controlled by a "stack pointer" that is typically (but not always) a
> dedicated CPU register.

I have used at least one implementation that used the term "cactus stack".
Of course parallel execution was the main objective. (Each thread had
its own stack, that is where the terminology comes from.)

> The word "heap" on the other hand, doesn't seem to carry the same kind
> of semantic baggage. In my understanding, the term "heap" refers to a
> region of memory used for dynamic allocation (malloc/free, new/delete,
> or whatever); there is at most a weak impliciation that it's
> contiguous.

Not at all. In threaded applications there could very well be multiple
heaps.

> In other word's I see the word "heap" as
> having just the right level of vagueness to describe the general
> underlying mechanism used by malloc and free.

It can be used. But most people think of it as a single, contiguous,
piece of memory. And that may, or may not, be the case. If you are
going multi-threaded you may have either one heap or multiple heaps.

 

[Christopher Layne]

"pile," "last-in-first-out list," and "yo-yo list" as terms
that have been used for "stack." Of these, the only one I
ever personally encountered was "LIFO list" (or sometimes
"LIFO stack," which nowadays seems redundant).

As for "heap," it had its "specially-structured binary
tree" meaning at least as far back as 1964 when Williams
invented Heapsort. Can anyone cite a pre-1964 computer-
related use of "heap" in the "big bag of bytes" sense? Or
has a once-precise term been stripped of its precision?

I usually just refer to them as either stacks or queues and if the context is
on what order they behave in: FIFO or LIFO.

Aside from that, I use the term heap for what typically, to me atleast, are
categorized as heaps. Mainly priority queues or queues sorted by some other
order than just arrival into it.

 

[Jack Klein]

santosh said:



So I have always been led to believe, but I can find no reference to
this term in C89 (I didn't check C99, but I certainly recall that "free
store" was the allegedly canonical term well before C99 was ratified).

Does anyone know why "free store" is given canonical status?

The term "free store" has been used by Stroustrup since the early days
of C++, and it is used in the C++ standard.

So it is actually not canonical in C at all, only in two C like
languages, namely the real C++ and the mythical C/C++.

 

[Richard Heathfield]

Jack Klein said:

The term "free store" has been used by Stroustrup since the early days
of C++, and it is used in the C++ standard.

So it is actually not canonical in C at all, only in two C like
languages, namely the real C++ and the mythical C/C++.

So presumably there's nothing to stop us using "grocery store" instead.
Good.

 

[Richard Heathfield]

CBFalconer said:

It's also used to refer to:

1. A pile of hot steaming dung (horse or cow).

I have heard someone say "it's a heap of structured methodology" with
much the same digusted inflection.

"Heap" is also the word the ancient Egyptians used[1] to describe "the
unknown term" in a simple algebraic expression.


[1] Okay, okay - they used a hieroglyph. But it /translates/ to "heap".

 

[Nishu]

Firstly the C standard does not define where the variable are allocated
only how long they last and where their names are visible.

I don't see any other alternatives rather than register/stack
allocation for local variables. I would be happy to know alternative
implementations for it.

If, on the other hand, you meant heap, then it would be wrong for a lot
of common implementations, although it could certainly be implemented
that way. Equally it could be implemented by allocating enough space on
the stack (if there is one) at program startup for all the static and
global data, and this might make sense on some systems. Then there is
static const and "global" const data that on some systems will be
programmed in to ROM and on others in to RAM marked as read only in a
separate place from other static/global data. Also the machines without
a stack will obviously not allocate automatic variables on the stack,
although other implementations tend to.

Heap, as I believe, is large junk of memory which may/may not be
contiguous while doing successive memory allocations using calloc/
malloc. but it is definitely different from stack and can not (If yes,
please tell how) be replaced by stack; as stack is just a method(LIFO)
applied to a particular section of memory.

In other words it depends entirely on the implementation but you are
wrong for all the implementations I know of.

IMO, He's almost right for ARM which has 78% processor(and hence
embedded systems) market share.

Thanks,
Nishu

 

[Flash Gordon]

Nishu wrote, On 07/02/07 08:07:

I don't see any other alternatives rather than register/stack
allocation for local variables. I would be happy to know alternative
implementations for it.

One system I used to work on had a HW stack which you could *not* push
anything other to return addresses (well, not without a lot of work so
it was never done) and you could use an address register to implement a
data stack. On the C implementation I used automatic variables were not
allocated on "the stack" although they were allocated on a stack. At the
point where you need to actually care about where variables were
allocated you would also need to know that as far as the processor was
concerned it was not "the stack" even though it was a stack.

Heap, as I believe, is large junk of memory which may/may not be
contiguous while doing successive memory allocations using calloc/
malloc. but it is definitely different from stack and can not (If yes,
please tell how) be replaced by stack; as stack is just a method(LIFO)
applied to a particular section of memory.

In the text above I was not talking about automatic objects or objects
allocated by *alloc, I was talking about objects with static storage
duration which are a completely different thing. Static objects and
globals (if you want to use that term) are as far as C is concerned
allocated before the program starts and survive until it ends, so they
do not need the attributes of either stack or heap.

Stack like structures can easily be implemented on a heap instead of a
stack. Static objects can easily be implemented on a stack or dedicated
blocks of memory or anywhere else. As to the memory allocated with
*alloc, first fully define the term heap or whatever method of
implementing *alloc/free people come up with you might say, "oh, that's
just a heap."

IMO, He's almost right for ARM which has 78% processor(and hence
embedded systems) market share.

Almost tight is not right, therefore according to your statistics he was
wrong got at least 78% of the processor market share.

 

[Nishu]

Nishu wrote, On 07/02/07 08:07: ..
..
..

In the text above I was not talking about automatic objects or objects
allocated by *alloc, I was talking about objects with static storage
duration which are a completely different thing. Static objects and
globals (if you want to use that term) are as far as C is concerned
allocated before the program starts and survive until it ends, so they
do not need the attributes of either stack or heap.

Stack like structures can easily be implemented on a heap instead of a
stack. Static objects can easily be implemented on a stack or dedicated
blocks of memory or anywhere else. As to the memory allocated with
*alloc, first fully define the term heap or whatever method of
implementing *alloc/free people come up with you might say, "oh, that's
just a heap."

You may be right about static/global allocation. It is placed in zero-
initialized region which can be defined in any part of memory(but
rarely(or never?) on memory which is stack) but, AFAIK, dynamic memory
allocations are termed as heap which must be freed before execution
gets over. (i.e, alloc/malloc/realloc)

Thanks,
Nishu