static, global variable memory allocation
fdmf...@gmail.com
please check for me?
Q. What are the memory allocation for static variable in a function,
an automatic variable and global variable?
My answer: static variable in function and global variable are
allocated in head, and automatic variable is allocated in stack.
Right?
jacob navia
Maybe you mean "heap" not "head" ???
If that is the case, you are mostly right, it depends on the
implementation and OS running, etc.
A program has a fixed area with the initial data of the program.
This is not the heap in the traditional sense but just a RAM space
filled with tables, strings, double data, etc.
The heap is a variable area used to allocate space for data
dynamically during program execution. That data can be
local to a function, or be global. You are confusing the scope
of a variable, and the place where it is allocated, what is
not the same.
{
char *m = malloc(2678);
// use of m
free(m);
}
m is allocated from the heap, but it is local to that block
since it is freed before the block is finished. The varible
"m", of pointer type, is local to that block, and is active
only when that block is active.
Mostly, local variables are allocated from the stack, but some
people here say there are machines without stack that implement
C. I do not know, I have never seen one of those. In any
case in most systems, the stack exists and it is used to
allocate local variables.
Richard Tobin
fdmf...@gmail.com <fdmf...@gmail.com> wrote:
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.)
-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
Ben Pfaff
> My answer: static variable in function and global variable are
> allocated in head, and automatic variable is allocated in stack.
Many answers could possibly be right. This one is wrong.
--
Ben Pfaff
b...@cs.stanford.edu
http://benpfaff.org
Richard Heathfield
<snip>
> {
> char *m = malloc(2678);
> // use of m
> free(m);
> }
>
> m is allocated from the heap, but it is local to that block
> since it is freed before the block is finished.
No, that's wrong. In fact, m is an auto object, and it has function
scope. 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.
> The varible
> "m", of pointer type, is local to that block, and is active
> only when that block is active.
Well, m only *exists* when that block is active.
> Mostly, local variables are allocated from the stack, but some
> people here say there are machines without stack that implement
> C.
Right.
> I do not know, I have never seen one of those. In any
> case in most systems, the stack exists and it is used to
> allocate local variables.
How do you know that "most systems" have a stack?
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
jacob navia
> jacob navia said:
>
> <snip>
>
>
>>{
>>char *m = malloc(2678);
>>// use of m
>>free(m);
>>}
>>
>>m is allocated from the heap, but it is local to that block
>>since it is freed before the block is finished.
>
>
> No, that's wrong. In fact, m is an auto object, and it has function
> scope. 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.
>
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.
>>Mostly, local variables are allocated from the stack, but some
>>people here say there are machines without stack that implement
>>C.
>
>
> Right.
>
>
>>I do not know, I have never seen one of those. In any
>>case in most systems, the stack exists and it is used to
>>allocate local variables.
>
>
> How do you know that "most systems" have a stack?
>
Because there is a LONG list of very popular microprocessors,
from the Motorola to the x86, from the power pc to the 16 bit
Analog devices DSP, that all have a stack.
Since most modern microprocessors use some of those
processors, I would say that most systems have a stack.
A stack is a natural organization for building activation
records. Since C supports recursion, either the machine
has a stack or some behind the scenes software must implement
one.
Flash Gordon
Firstly the C standard does not define where the variable are allocated
only how long they last and where their names are visible.
Secondly that could be a bit problematic on a ship where the head is the
place you go to relieve yourself. You would just have to keep your legs
crossed if someone is running a program with logs of globals and statics
filling up the head.
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.
In other words it depends entirely on the implementation but you are
wrong for all the implementations I know of.
--
Flash Gordon
fdmf...@gmail.com
> fdmfdm...@gmail.com wrote, On 06/02/07 16:00:
Well, I meant to say "heap". OK, for your opinion, if you were asked
by this question, you will say all these variables will be allocated
on stack? Is there a "correct" answer for this question?
Richard Tobin
Flash Gordon <sp...@flash-gordon.me.uk> wrote:
>> My answer: static variable in function and global variable are
>> allocated in head, and automatic variable is allocated in stack.
>In other words it depends entirely on the implementation but you are
>wrong for all the implementations I know of.
I think you must be interpreting "heap" in a narrow sense then. On
many unix implementations for example, the memory returned by malloc()
follows on directly from the area in which static data is stored, and
it is not unreasonable to use the term "heap" to refer to that entire
area. Presumably that is what the original poster had in mind.
Eric Sosman
> On Feb 6, 9:41 am, Flash Gordon <s...@flash-gordon.me.uk> wrote:
>
>>fdmfdm...@gmail.com wrote, On 06/02/07 16:00:
>>
>>
>>>This is an interview question and I gave out my answer here, could you
>>>please check for me?
>>
>>>Q. What are the memory allocation for static variable in a function,
>>>an automatic variable and global variable?
>
>
> Well, I meant to say "heap". OK, for your opinion, if you were asked
> by this question, you will say all these variables will be allocated
> on stack? Is there a "correct" answer for this question?
One correct answer goes something like this: "The
implementation can allocate memory in any way it likes,
so long as the allocations satisfy the requirements of
the C language." In answering the obvious follow-up,
the phrases "static storage duration" and "automatic
storage duration" may be useful (pedantry: variables
don't use "dynamic storage duration").
<off-topic>
Is it my imagination, or has somebody unleashed a
flood of inane interview questions recently? Half the
newsgroups I follow are being submerged with postings a
lot like fdmfdmfdm's, posing questions of similar, er,
depth. Is there book with a title like "1001 Moronic
Interview Questions" in circulation?
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?
"It's not enough to keep the mind alive."
-- Peter Cook in "Beyond the Fringe"
</off-topic>
Jack Klein
<fdmf...@gmail.com> wrote in comp.lang.c:
The correct answer is that there is no "correct" answer for the C
language itself. There might be a "correct" answer if they specified
a particular compiler generating an executable for a particular OS, or
even "common" compilers for "common" desktop operating systems.
There is actually no "correct" answer for where "global" objects are
located, since the concept does not actually exist in the C standard.
External linkage comes close to what most people commonly mean by that
term, but it is by no means the same thing as, for example, a global
variable in BASIC.
--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://c-faq.com/
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
santosh
What a pointless interview question!
Well, I suppose you meant to say heap instead of head. The more proper
term is free store. There's really no one correct answer to such a
question, since C has been implemented on a very wide variety of
machines. The C standard doesn't specify where objects are allocated.
It specifies their scope and visibility and some other information.
Implementations are free to allocate objects however they wish, as
long as they respect these conditions.
santosh
> On Feb 6, 9:41 am, Flash Gordon <s...@flash-gordon.me.uk> wrote:
> > fdmfdm...@gmail.com wrote, On 06/02/07 16:00:
> >
> > > This is an interview question and I gave out my answer here, could you
> > > please check for me?
> >
> > > Q. What are the memory allocation for static variable in a function,
> > > an automatic variable and global variable?
> >
> > > My answer: static variable in function and global variable are
> > > allocated in head, and automatic variable is allocated in stack.
> >
> > > Right?
> >
> > Firstly the C standard does not define where the variable are allocated
> > only how long they last and where their names are visible.
> >
> > Secondly that could be a bit problematic on a ship where the head is the
> > place you go to relieve yourself. You would just have to keep your legs
> > crossed if someone is running a program with logs of globals and statics
> > filling up the head.
> >
> > 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.
> Well, I meant to say "heap". OK, for your opinion, if you were asked
> by this question, you will say all these variables will be allocated
> on stack? Is there a "correct" answer for this question?
The correct answer is that it's implementation specific.
Flash Gordon
> In article <annm94x...@news.flash-gordon.me.uk>,
> Flash Gordon <sp...@flash-gordon.me.uk> wrote:
>>> My answer: static variable in function and global variable are
>>> allocated in head, and automatic variable is allocated in stack.
>
>> In other words it depends entirely on the implementation but you are
>> wrong for all the implementations I know of.
>
> I think you must be interpreting "heap" in a narrow sense then.
Quite possible. This shows another problem in using terminology outside
the standard without making it clear what you are referring to ;-)
> On
> many unix implementations for example, the memory returned by malloc()
> follows on directly from the area in which static data is stored, and
> it is not unreasonable to use the term "heap" to refer to that entire
> area. Presumably that is what the original poster had in mind.
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?
Also, I thought that it was common for the static/global data that is
not const to be allocated in a bss (or similar) section that is defined
as being zeroed and that historically at least the section the heap (as
I would use the term) was allocated in would not since it did not need
zeroing. Of course, I accept that security considerations could have
made this academic.
In any case, note the weasel words "I know of" which can certainly be
interpreted to mean the systems I know the details of, and thus as I was
not aware of what you have said it was still accurate ;-)
--
Flash Gordon
Flash Gordon
> On Feb 6, 9:41 am, Flash Gordon <s...@flash-gordon.me.uk> wrote:
>> fdmfdm...@gmail.com wrote, On 06/02/07 16:00:
>>
>>> This is an interview question and I gave out my answer here, could you
>>> please check for me?
>>> Q. What are the memory allocation for static variable in a function,
>>> an automatic variable and global variable?
>>> My answer: static variable in function and global variable are
>>> allocated in head, and automatic variable is allocated in stack.
>>> Right?
>> Firstly the C standard does not define where the variable are allocated
>> only how long they last and where their names are visible.
>>
>> Secondly that could be a bit problematic on a ship where the head is the
<snip>
>> If, on the other hand, you meant heap, then it would be wrong for a lot
<snip>
>> In other words it depends entirely on the implementation but you are
>> wrong for all the implementations I know of.
>> --
>> Flash Gordon
Please do not quote peoples signatures (the bit after the "-- " unless
you are commenting on them.
> Well, I meant to say "heap". OK, for your opinion, if you were asked
> by this question, you will say all these variables will be allocated
> on stack? Is there a "correct" answer for this question?
There is no one correct answer since as I said it depends on the
implementation. So my answer would depend on what sort of job the
interview was for and my opinion of the interviewer. If Richard
Heathfield was interviewing my I might well say something like, "as the
C standard does not define where the variables are stored only the
lifetime and the visibility of the names it depends entirely on the
implementation and it is extremely rare that one needs to know unless
either writing the loader or defining a linker command script for an
embedded system. On typical stack based systems automatic variables will
be stored on a stack, although it may not be the same stack as is used
for return addresses. Static data may if it is also const be stored in
ROM or a RAM that is flagged as read only, non-const data will typically...
If I considered the interviewer to be less knowledgeable I might give a
simpler answer, and the answer might well depend on what targets the
company tended to be producing software for. If the target was a
TMS320C2x I might well mention register AR7 for instance, since that
processor has a HW stack that is only used for program return addresses,
and is only 7 deep IIRC, and conventionally AR7 is used to implement a
stack, although you could just as easily use AR1, AR2 ...
--
Flash Gordon
Richard Heathfield
<snip>
> What a pointless interview question!
>
> Well, I suppose you meant to say heap instead of head. The more proper
> term is free store.
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?
Mark McIntyre
<ja...@jacob.remcomp.fr> wrote:
>Richard Heathfield a écrit :
>>
>> How do you know that "most systems" have a stack?
>
>Because there is a LONG list of very popular microprocessors,
>from the Motorola
Just to point out that Motorola is a chip maker, not a CPU, and some
of their chips have no stack.
>to the x86, from the power pc
ppc is an example of a Motorola chip (once upon a time...).
> to the 16 bit Analog devices DSP, that all have a stack.
I guess by 'most' in this case we mean "largest number of shipped
physical units". I'd probably agree on that basis. It is worth
stressing however, and I'm aware you mentioned in your original post,
that a stack is not required or expected by C.
--
Mark McIntyre
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan
Mark McIntyre
Heathfield <r...@see.sig.invalid> wrote:
>santosh said:
>
><snip>
>
>> What a pointless interview question!
>>
>> Well, I suppose you meant to say heap instead of head. The more proper
>> term is free store.
>
>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).
Heap, stack and free store are not mentioned anywhere in the PDF od
C99.
>Does anyone know why "free store" is given canonical status?
Wikipedia consider heap and free store synonyms. Meanwhile Herb Sutter
specifically differentiates between them on the Guru of the Week
website, by saying that malloc uses one, and new uses the other. Hm!
My guess is that free store was invented to differentiate from "heap"
as in a structured tree.
Eric Sosman
> santosh said:
>
> <snip>
>
>
>>What a pointless interview question!
>>
>>Well, I suppose you meant to say heap instead of head. The more proper
>>term is free store.
>
>
> 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?
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)?
Ben Pfaff
> 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)?
The plain English word "heap" is just a pile, so the word heap is
more suggestive for a big bucket of bytes than for a carefully
organized data structure, in my opinion.
--
"C has its problems, but a language designed from scratch would have some too,
and we know C's problems."
--Bjarne Stroustrup
matevzb
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?
--
WYCIWYG - what you C is what you get
Eric Sosman
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
Flash Gordon <sp...@flash-gordon.me.uk> wrote:
>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 Tobin
Eric Sosman <Eric....@sun.com> wrote:
> 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.
Eric Sosman
> In article <1170794418.973717@news1nwk>,
> Eric Sosman <Eric....@sun.com> wrote:
>
>
>> 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.
According to Knuth, Heapsort dates from 1964.
CBFalconer
> fdmf...@gmail.com <fdmf...@gmail.com> wrote:
>
... snip ...
>>
>> My answer: static variable in function and global variable are
>> allocated in head, and automatic variable is allocated in stack.
>
> 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
Keith Thompson
> Richard Heathfield a écrit :
>> jacob navia said:
>> <snip>
>>
>>>{
>>>char *m = malloc(2678);
>>>// use of m
>>>free(m);
>>>}
>>>
>>>m is allocated from the heap, but it is local to that block
>>>since it is freed before the block is finished.
>> No, that's wrong. In fact, m is an auto object, and it has function
>> scope. 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.
>
> 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.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Flash Gordon
> In article <octm94x...@news.flash-gordon.me.uk>,
> Flash Gordon <sp...@flash-gordon.me.uk> wrote:
>
>> 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.
:-)
--
Flash Gordon
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.
Ark
<snip>
> 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?
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)?
>
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.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
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
<r...@see.sig.invalid> wrote in comp.lang.c:
> santosh said:
>
> <snip>
>
> > What a pointless interview question!
> >
> > Well, I suppose you meant to say heap instead of head. The more proper
> > term is free store.
>
> 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
> On Tue, 06 Feb 2007 19:03:22 +0000, Richard Heathfield
> <r...@see.sig.invalid> wrote in comp.lang.c:
>
>> 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++.
So presumably there's nothing to stop us using "grocery store" instead.
Good.
Richard Heathfield
> Keith Thompson wrote:
>>
> ... 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).
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
<snip>
> 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.
<snip>
>
> 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
> On Feb 6, 8:41 am, Flash Gordon <s...@flash-gordon.me.uk> wrote:
>
> <snip>
>> 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.
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.
> <snip>
>> 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 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."
>> 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.
Almost tight is not right, therefore according to your statistics he was
wrong got at least 78% of the processor market share.
--
Flash Gordon
Nishu
.
.
>
> > 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."
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
Flash Gordon
> On Feb 7, 1:37 am, Flash Gordon <s...@flash-gordon.me.uk> wrote:
>> Nishu wrote, On 07/02/07 08:07:
> .
> .
> .
>>> 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."
>
> You may be right about static/global allocation.
The OP asked about variables declared static in functions, globals, and
automatic variables, so that is what I focused on.
> 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,
I stated it could be not that it is on any current system. Others stated
that it was declared on the heap, which depending on the definition of
heap I would dispute, and one person at least agreed I had a point.
> AFAIK, dynamic memory
> allocations are termed as heap which must be freed before execution
> gets over. (i.e, alloc/malloc/realloc)
If that is your definition of heap then by definition *alloc/free use a
heap ;-)
Actually, my usage of the word heap corresponds with yours which is why
I said that static/global data is not stored on the heap in my
experience. However, I can conceive of a system effectively using
malloc/calloc to allocate space for statics/globals before calling main,
just as I can conceive of the space being allocated on a stack calling main.
--
Flash Gordon
Charlton Wilbur
ES> And the bigger issue: If you faced and aced a string of
ES> such questions in an interview and were offered the job, would
ES> you take it? Or would you flee?
I have, and I fled.
Charlton
--
Charlton Wilbur
cwi...@chromatico.net
Eric Sosman
> On Feb 6, 8:41 am, Flash Gordon <s...@flash-gordon.me.uk> wrote:
>
> <snip>
>> 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.
One alternative arises from the fact that "the stack" can
be implemented in different ways. Nowadays it is common to use
sequential allocation: You reserve a special array somewhere,
initialize a pointer to point to one end of it, and let the
pointer wander up and down in the array as functions come and
go. Pretty simple design, and pretty cheap.
But it's not the only way, and not necessarily the "best"
way in all circumstances. One problem is that you either need
to guess how much stack space you'll need before starting the
program (this is probably equivalent to the Halting Problem)
or else come up with extra mechanisms to detect stack overflow
and make adjustments. Sometimes this isn't too bad, but if
memory is scarce or if you have a lot of stacks (multi-threaded
program) there can be difficulties.
So, another way is to allocate "stack frames" from a source
similar to what malloc() uses, and to chain them together in a
linked list. A stack built this way need not be contiguous, so
you need not reserve a contiguous chunk of memory to hold it
and you need not worry about exhausting that contiguous chunk.
A particular memory area could be a stack frame at one moment,
then be claimed by malloc() and released by free(), and then
wind up as part of an entirely different stack. Perhaps someone
with IBM zSeries (S/390) experience can say whether C on that
machine uses this sort of strategy; its ancestor the S/360 did
not have a "stack pointer register" nor stack-oriented call and
return instructions.
There could also be a mixed-mode strategy: Allocate a small
sequential stack to begin with, and when it overflows expand it
by allocating and linking in a fresh "super-frame." Such a
stack would be "locally contiguous" but "globally discontiguous."
I haven't heard of anyone using this approach, but it might make
sense in some circumstances.
--
Eric Sosman
eso...@acm-dot-org.invalid
santosh
> Richard Heathfield <r...@see.sig.invalid> writes:
> [...]
> > 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.
Can a perverse but conforming implementation use the "heap" for
automatic objects. 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.
> 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 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);
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.
> 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?
> If so, what and why? Are there even any *theoretical* systems for
> which the term "heap" would be in appropriate; if so, why?
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.
Keith Thompson
> Keith Thompson wrote:
[...]
>> 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. As long as their properties, as dictated by the
> standard, are honoured, I don't see why they should be allocated from
> a stack.
Sure. It's not even necessarily perverse; I think that some IBM
mainframe systems do this.
>> 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.
From a computer science point of view, yes, a "stack" is simply a LIFO
data structure, which can be implemented in any number of ways
(contiguous array, linked list, etc.). But if you're talking about a
specific CPU architecture, the phrase "the stack" typically refers to
the CPU-specific structure I described above. If someone says that
automatic variables are allocated on "the stack", that tends to imply
the CPU-specific structure -- at least, it does to me.
>> 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.
Sure, but knowing something about the underlying architecture can be
helpful in understanding *why* C defines things the way it does.
Though the standard doesn't use the word "stack", the way automatic
objects are allocated and deallocated is almost certainly motivated in
part by the kind of CPU-specific stack implementation described above.
If you have this kind of system stack, meeting the standard's
requirements for automatic objects is straightforward. If you don't,
you have to go to some extra effor to "fake it". The danger is
assuming that "all the world's a <whatever>".
By contrast, consider the way Perl works. Much of Perl's syntax is
borrowed from C, and it has functions and things that look, and
*usually* act, very much like C automatic objects. But they're not
necessarily allocated and deallocated in a stack-like manner. For
example, the equivalent of:
int *create_new_int(void)
{
int local;
return &local; /* BAD! */
}
actually works in Perl; the object isn't deallocated on exit from the
function as long as anything refers to it. In effect, everything is
heap-allocated and garbage-collected. Some knowledge of CPU
architecture is helpful in understanding *why* C doesn't work this
way.
>> 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);
>
> 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.
Ok. In that case, I'd say that "the heap" could refer to the region
of memory currently allocated for management by malloc and free; this
region may grow or shrink over time (in, ironically enough, a
stack-like manner).
>> 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.
Then that's an argument *against* talking about "the heap" in general.
I was speculating that, unlike the phrase "the stack", the phrase "the
heap" might be generic enough to refer to the malloc/free mechanism of
any possible C implementation. But if some such implementations have
multiple things they call "heaps", then "the heap" becomes ambiguous
and/or misleading.
[...]
Gordon Burditt
>>
>> 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.
Christopher Layne
> If that is your definition of heap then by definition *alloc/free use a
> heap ;-)
>
> Actually, my usage of the word heap corresponds with yours which is why
> I said that static/global data is not stored on the heap in my
> experience. However, I can conceive of a system effectively using
> malloc/calloc to allocate space for statics/globals before calling main,
> just as I can conceive of the space being allocated on a stack calling main.
Also, a non-standard function, but alloca() goes against the grain of all this
as well.
Dave Vandervies
Gordon Burditt <gordon...@burditt.org> wrote:
[without attribution]
>>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.
If there is a stack[1], then the direction in which it grows is trivially
reducible to a Simple Matter Of orienting your system appropriately.
dave
[1] In this context, "stack" refers to something known to grow
unidirectionally. In contexts where this can not be assumed, the
direction in which it grows is a rather less simple matter.
--
Dave Vandervies dj3v...@csclub.uwaterloo.ca
Sheesh! Everyone here takes everything so literally, you'd think they
worked with computers all day or something...
--Matt Roberds in the scary devil monastery
Nishu
> One alternative arises from the fact that "the stack" can
> be implemented in different ways. Nowadays it is common to use
> sequential allocation: You reserve a special array somewhere,
> initialize a pointer to point to one end of it, and let the
> pointer wander up and down in the array as functions come and
> go. Pretty simple design, and pretty cheap.
Yes, It is common. Systems can either have Top-down or bottom-up
approach for this kind of implementation. Top down approach is
preferred implementation for stack. We can have sequential memory(A
very big array) whose one end is used to allocate heap and other end
is used as stack (say decrementing stack) and we have an idea how much
is the system's maximum (stack + heap) requirement, so stack overflow
is somewhat avoided.
> So, another way is to allocate "stack frames" from a source
> similar to what malloc() uses, and to chain them together in a
> linked list. A stack built this way need not be contiguous, so
> you need not reserve a contiguous chunk of memory to hold it
> and you need not worry about exhausting that contiguous chunk.
> A particular memory area could be a stack frame at one moment,
> then be claimed by malloc() and released by free(), and then
> wind up as part of an entirely different stack. Perhaps someone
> with IBM zSeries (S/390) experience can say whether C on that
> machine uses this sort of strategy; its ancestor the S/360 did
> not have a "stack pointer register" nor stack-oriented call and
> return instructions.
>
> There could also be a mixed-mode strategy: Allocate a small
> sequential stack to begin with, and when it overflows expand it
> by allocating and linking in a fresh "super-frame." Such a
> stack would be "locally contiguous" but "globally discontiguous."
> I haven't heard of anyone using this approach, but it might make
> sense in some circumstances.
This is interesting.
Thanks,
Nishu
Keith Thompson
> On Feb 7, 5:30 am, Eric Sosman <esos...@acm-dot-org.invalid> wrote:
>
>> One alternative arises from the fact that "the stack" can
>> be implemented in different ways. Nowadays it is common to use
>> sequential allocation: You reserve a special array somewhere,
>> initialize a pointer to point to one end of it, and let the
>> pointer wander up and down in the array as functions come and
>> go. Pretty simple design, and pretty cheap.
>
> Yes, It is common. Systems can either have Top-down or bottom-up
> approach for this kind of implementation. Top down approach is
> preferred implementation for stack.
There is no reason (as far as standard C is concerned) to prefer a
top-down stack over a bottom-up stack. (There may be CPU-specific
reasons.)
Nishu
> > 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. As long as their properties, as dictated by the
> standard, are honoured, I don't see why they should be allocated from
> a stack.
IMO, stack suits the requirement of auto variables at best. As soon a
leaf function is called from parent function, stack is used to store
the status of registers, passing arguments, etc and this scope is
defined till the control stays in leaf function. Similar is the case
with auto/local variables of leaf function. Scope is defined till the
control is in leaf function.
You have to free (to tell system that you can re-write it) "Heap"
every time, you use it for local variable.
> > 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.
It makes life easier. Simply one HW (may/maynot be memroy mapped)
stack pointer is required to refer it across all functions. (when you
are using single stack 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.
I think, There is misnomer in C. C storage classes. I don't understand
why "storage" word is required when it just defines the life of
variable.
-Nishu
Flash Gordon
> "Nishu" <naresh...@gmail.com> writes:
>> On Feb 7, 5:30 am, Eric Sosman <esos...@acm-dot-org.invalid> wrote:
>>
>>> One alternative arises from the fact that "the stack" can
>>> be implemented in different ways. Nowadays it is common to use
>>> sequential allocation: You reserve a special array somewhere,
>>> initialize a pointer to point to one end of it, and let the
>>> pointer wander up and down in the array as functions come and
>>> go. Pretty simple design, and pretty cheap.
>> Yes, It is common. Systems can either have Top-down or bottom-up
>> approach for this kind of implementation. Top down approach is
>> preferred implementation for stack.
> [...]
>
> There is no reason (as far as standard C is concerned) to prefer a
> top-down stack over a bottom-up stack. (There may be CPU-specific
> reasons.)
On some processors I have used there was no HW reason to prefer one
direction over the other. There was no specific reason in terms of HW
for which of the 7 general purpose address registers you used either.
--
Flash Gordon
Chris Dollin
> On Feb 6, 8:41 am, Flash Gordon <s...@flash-gordon.me.uk> wrote:
>
> <snip>
>> 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.
You could put them in whatever region of store was used for mallocated
memory.
--
Chris "/could/ doesn't mean /should/" Dollin
"Who are you? What do you want?" /Babylon 5/
David Thompson
Burditt) wrote:
> >Can a perverse but conforming implementation use the "heap" for
> >automatic objects.
>
> I'm not so sure it would be that perverse. OS/360 <snip>
> 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.
>
PL/I also had a68-style nesting with downward closure, and was much
more popular on S/360+. FORTRAN did not, nor did COBOL of the day,
although since '85 it does, although I'm not sure it has recursion.
Fortran since '90 has (only) one nesting level, and recursion.
<snip much good>
- formerly david.thompson1 || achar(64) || worldnet.att.net