Re: Why are variables stored on the stack?

Malcolm McLean wrote:
"CJ" <cj@xxxxxxxxxx> wrote in message

2) I believe the argument about it being more efficient to use
the stack than the heap is spurious - if I recall, both are O(N)
data structures.

A stack is O(1) to allocate a chunk, and chunk sizes can be
variable. O(N) to fill the chunk with useful data, where N is
chunk size. A heap is O( f(N) ) to allocate a chunk, where f(N)
is some complex and platform dependent function of the number of
chunks allocated. Typically it will be about logarithmic,
certainly under N. You can look up broken stick distributions
and the like if you are interested in problems of fragmentation
and how they impact on block search.

A heap is O(N) to fill with useful data, where N is the chunk
size.

So you are not really correct, unless chunk size is very large
in comparision to the number of blocks allocated, in which case
that term will dominate.

You are in error about heaps. For an example where all calls to
malloc, realloc, free are O(1) see nmalloc.zip, available at:

<http://cbfalconer.home.att.net/download/>

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.



--
Posted via a free Usenet account from http://www.teranews.com

.

Relevant Pages

  • Re: P-Source: A Guide to the Apple Pascal System
    ... having a stack instead, but for Java that's not an option. ... heap regions. ... the heap allocator can force a collection if it needs more ... Activation frames will be allocated from these chunks until it is full, then allocate another chunk and link to it. ...
    (comp.sys.apple2)
  • [NT] Apple Quicktime FLIC File Heap Overflow (Technical Details)
    ... The following security advisory is sent to the securiteam mailing list, and can be found at the SecuriTeam web site: http://www.securiteam.com ... Apple Quicktime FLIC File Heap Overflow ... "COLOR_64 chunk" Quicktime parser. ... text:679FE4DA mov eax, ...
    (Securiteam)
  • Re: Heap fragmentation (2nd attempt)
    ... heap fragmentation depends on the malloc package much ... C> is the source code to your own malloc package. ... a new memory location from the OS. ... Why is free Oisn't it just simply adding the freed chunk at the end ...
    (comp.arch.embedded)
  • Re: Why are variables stored on the stack?
    ... A stack is Oto allocate a chunk, and chunk sizes can be variable. ... A heap is O) to allocate a chunk, where fis some complex and platform dependent function of the number of chunks allocated. ... Typically it will be about logarithmic, certainly under N. You can look up broken stick distributions and the like if you are interested in problems of fragmentation and how they impact on block search. ...
    (comp.lang.c)
  • classes, pointers, vectors, and memory allocation
    ... ptr1 and ptr2 will be dynamically allocated in the heap, ... does A's memory get enlarged as a whole chunk? ... is not enough space for the whole chunk, will A get copied into another ...
    (comp.lang.cpp)