How far can stack [LIFO] solve do automatic garbage collection and prevent memory leak ?
spinoza1111 at yahoo.com
Wed Aug 18 12:09:14 CEST 2010
On Aug 18, 1:21 am, Standish P <stnd... at gmail.com> wrote:
> > Garbage collection doesn't use a stack. It uses a "heap", which is in
> > the abstract a collection of memory blocks of different lengths,
> > divided into two lists, generally represented as linked lists:
> > 1. A list of blocks that are free and may be used to store new data
> > 2. A list of blocks that are in use, or haven't been freed (yet)
> Is this all that a heap is or is there more to it ? I have been
> looking for simple but complete explanation of heap for a while and
> not gotten to it. I think I am looking for a stack allocation on the
> same pattern. In a disk, a file is fragmented in many contiguous
> blocks and is accessed automatically.
> > There is no way you could do memory management of all but the most
> > trivial and fixed-length data chunks using a stack. Sure, you could
> > reserve thousands of bytes on the stack for an array but suppose your
> > language allows arrays to grow or shrink. To keep its property of
> > being adjacent, you'd have to do something horrible such as move
> > unrelated data allocated later, which raises all sorts of security
> > issues, doesn't it.
> > A stack, or something which works like a stack (that is, a stack) is a
> > necessary but not sufficient condition for a working C runtime because
> > C functions can call themselves recursively, whether directly or
> > indirectly. If this last condition did not obtain, each function could
> > give the functions it calls some of its own memory and the called
> > function could save a fixed set of non-stacked general registers in
> > that area; this was in fact the practice on IBM 370 and in assembler
> > language at a time when many "data processing managers" though
> > recursion was a Communist plot.
> > However, data structures of variable size, or data structures that
> > merely take up a lot of space, don't play nice with others on the
> > stack, so, we place their address on the stack and store them in
> > another place, which was named the heap, probably, as a sort of
> > witticism.
> > Gilbert and Sullivan:
> > If anyone anything lacks
> > He'll find it all ready in stacks
> This you might want to take this to the Forth people because they are
> marketing their language as a cure for all that plagues programming
No, they're not. Stack based languages have seen better days and Forth
(and the SL/1 language I supported with compilers at Bell-Northern
Research) were last in fashion in the 1970s. Processors seldom could
multitask, so it wasn't recognized that the stack could be a
performance bottleneck, where stack operations cannot be pipelined or
executed in parallel.
John Hennessy of Stanford and MIPS made the stack must die case at ACM
ASPLOS in 1987. Niklaus Wirth was also at this conference at which I
was a fly on the wall, maintaining that the stack was good for
reliability and verifiability of software.
Forth had a snowball's chance because it forces ordinary programmers
to think in Reverse Polish notation and is for the above reasons hard
to pipeline, although of course it can be pipelined.
> > was wrong, and needs to be brought up to date:
> > You cannot do everything in a stack
> > Unless you code an almighty hack
> > If you're a coding Knight who says, "Neep",
> > You'll probably need to implement a heap
> > A pile a heap of benefits you'll reap
> > If only my advice in your brain you'll keep
> > And avoid memory leaks from which data doth seep
> > By using a well-implemented, well structured, and well-documented
> > Heap!
> > [Chorus of Sailors]
> > We will to heart your advice take, and always use a heap!
> > [Soloist]
> > Oh thank you do
> > To this be true
> > And always my sage advice do keep
> > That you always need to use a heap!- Hide quoted text -
> > - Show quoted text -
More information about the Python-list