Re: "Heap" (was Re: static, global variable memory allocation)

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.

Can a perverse but conforming implementation use the "heap" for
automatic objects.

I'm not so sure it would be that perverse. OS/360 linkage conventions
used a linked list of save areas instead of a stack. The save area
could be allocated in static storage (if the function is guaranteed
not to be re-entered), or it could be obtained with GETMAIN (the
system call likely to be used by malloc() to obtain storage from
the system).

A C compiler would have to assume that a C function COULD BE called
directly or indirectly from itself unless it could prove that it
wasn't. Functions that didn't call any other functions could
dispense with allocating a save area at all. Extending the save
area could provide space for auto variables. Dealing with
variable-length arrays might get a little tricky.

Now, when I was using this, C didn't exist. Other languages like
PL/1 and Pascal did. Pascal has a more complex setup than C (the
equivalent of an "auto" variable in an outer function can be referred
to in an inner function, even in the presence of recursion). There's
no reason C couldn't use this technique.

As long as their properties, as dictated by the
standard, are honoured, I don't see why they should be allocated from
a stack.

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 may be wrong, but it was my impression that a stack is simply a LIFO
data structure. It doesn't have to have any specific hardware support.
On stackless architectures, a LIFO may have to be simulated by the C
implementation, for auto objects.

You need some rough equivalent to a "stack pointer" regardless.
Something has to let you find the last-in objects and keep track
of how much is on the LIFO. It might be a pointer or a counter or
something else. It's likely to be put in a CPU hardware register
(if there are any) even if there are no "PUSH" or "POP" instructions
or auto-increment/auto-decrement addressing modes to directly provide
a stack.

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.

Yes. It curious why so many students of C are bursting to know where C
objects are stored. I would've thought that an assembly language or
machine architecture course would be the proper place to recieve such
information.

The answer seems to be: homework.

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);

I prefer to think of it as "that place from which malloc() obtains
its storage", which doesn't rule out the possibility that there is
only one place from which memory is allocated, all intermixed.


In many architectures the same memory is used for both the stack and
the heap. The former typically grows down from the high end of the
address space, while the latter grows in the opposite direction.

Contrary to popular assumptions, the stack (if there is one) does
not always grow north.

there is at most a weak impliciation that it's
contiguous.

I don't think so. For example in x86's segmented memory model, we can
have multiple heaps which are not contiguous. Even multiple objects
needn't be contiguous with one another.

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.

Yes, it could be used, atleast for the lack of a better term, which
would be both concise and easily understood. CBFalconer recently used
the term "memory arena". I wonder how appropriate that is?

Are there any real-world systems (with C implementations supporting
malloc() and free()) for which the term "heap" would be inappropriate?

I *DEFINE* "heap" as "that place from which malloc() obtains its
storage", and unless you're going to argue that in some implementation
there is no such place, but malloc() still works, it's hard to see
where it 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've pretty much defined this problem out of existence.

Many embedded devices like the PIC and other chips often don't have
access to the main system memory. Presumably, implementations for such
systems might forego *alloc() and free() and hence "heap" would be
irrelevant.



.

Relevant Pages

  • Re: Struct inside class
    ... The compiler figures computes the ... including anything derived from "Object": Heap pointer ... memory leaks and why the .NET good garbage collector is required. ... If GC_ALLOCATE can't allocate the requested ...
    (microsoft.public.dotnet.framework)
  • Re: Huge pages and small pages. . .
    ... >> what looks like contiguous memory and away you go. ... you need to have them cached in the TLB; if the TLB runs out of ... > low end of the heap, until someone figures out a way to tell the system ... When you allocate memory, the kernel just marks a promised ...
    (Linux-Kernel)
  • Re: run-time vs compile-time
    ... > offset related to some location (like stack base) somewhere. ... > offset from heap to pi. ... When you allocate an int on the heap, it is allocated at address 1. ... application has a given amount of memory it can use as it wishes. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: run-time vs compile-time
    ... > offset related to some location (like stack base) somewhere. ... > offset from heap to pi. ... When you allocate an int on the heap, it is allocated at address 1. ... application has a given amount of memory it can use as it wishes. ...
    (comp.lang.cpp)
  • Re: Doubt on Stack variables.
    ... Will it allocate memory for all the char's together or allocate for ... this only second char in the function gets memory. ... As other posters have pointed out, the notion of a "stack" does not appear ... the stack limits) would run into these limits. ...
    (comp.lang.c)