Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > [Q] How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

Reply
Thread Tools

[Q] How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ?

 
 
Malcolm McLean
Guest
Posts: n/a
 
      08-16-2010
On Aug 16, 3:14*pm, spinoza1111 <(E-Mail Removed)> wrote:
>
> To build an explicit stack in this program would have been folly, for
> it would have been necessary to either preallocate the stack and thus
> legislate the maximum complexity of source code, or use a lot of
> memory management in the pre-existing runtime heap.
>

The problem is that if you reallocate the stack, you invalidate all
pointers to objects on it. So you have to use handles instead. At
which point you might as well admit that you are no longer programming
in C.
>
>
> You didn't tell us you published a book. Can you identify the
> publisher?- Hide quoted text -
>

It's a print on demand, by Lulu. O'Reilley said they liked it but they
couldn't sell books on C. (I've an open invitation to write a computer
book for them in another language).

I don't really recommend print on demand. The nice thing is that you
can sell the book for about half the price it would cost under a
traditional publishing model. The problem is that people still use
acceptance by a traditional publisher as a filter.


 
Reply With Quote
 
 
 
 
Standish P
Guest
Posts: n/a
 
      08-16-2010
On Aug 16, 12:38*am, "Alf P. Steinbach /Usenet" <alf.p.steinbach
(E-Mail Removed)> wrote:
> * Standish P, on 16.08.2010 09:20:
>
> > [garble garble]

>
> Nonsense article "We look for an exogenous stack" cross-posted to
>
> * *[comp.lang.c],
> * *[comp.lang.c++],
> * *[comp.theory],
> * *[comp.lang.python],
> * *[comp.lang.forth].
>
> Please refrain from following up on Standish' article.


I am sorry that I did not post one of those porn baiting spams
featuring YOUR MOTHER NUDE that you so like for others to see - AND -
that you never complain about. Go and continue with your work and dont
mess in my threads.

Cheers,
Standish

>
> Cheers,
>
> - Alf
>
> --
> blog at <url:http://alfps.wordpress.com>


 
Reply With Quote
 
 
 
 
Lawrence D'Oliveiro
Guest
Posts: n/a
 
      08-16-2010
In message
<(E-Mail Removed)>, Standish
P wrote:

> We envisage an exogenous stack which has malloc() associated
> with a push and free() associated with a pop.


Since when are malloc(3) and free(3) exogenous?
 
Reply With Quote
 
Torben Ęgidius Mogensen
Guest
Posts: n/a
 
      08-17-2010
Standish P <(E-Mail Removed)> writes:

> [Q] How far can stack [LIFO] solve do automatic garbage collection and
> prevent memory leak ?
>
> Because a stack has push and pop, it is able to release and allocate
> memory. We envisage an exogenous stack which has malloc() associated
> with a push and free() associated with a pop.


See


http://citeseerx.ist.psu.edu/viewdoc...10.1.1.23.5498

http://portal.acm.org/citation.cfm?doid=174675.177855

http://www.springerlink.com/content/m2074884n6gt612h/

Torben
 
Reply With Quote
 
Standish P
Guest
Posts: n/a
 
      08-17-2010
On Aug 16, 4:20*am, Malcolm McLean <(E-Mail Removed)>
wrote:
> On Aug 16, 10:20*am, Standish P <(E-Mail Removed)> wrote:> [Q] How far can stack [LIFO] solve do automatic garbage collection and
> > prevent memory leak ?

>
> Most programs can be written so that most of their memory allocations
> are matched by destructors at the same level.
>
> However the allocations that can't be written this way typically tend
> to be the small frequently-called ones used for nodes in dynamic graph
> objects, or small resizeable buffers to hold strings and the like.
> This is where you get the performance hit with repeated calls to
> malloc() and free().
>
> So generally it's not worthwhile writing a stack allocator for a
> normal program. That's not to say there aren't a few individual cases
> where it can help performance. (See the chapter "Memory games" in my
> book Basic Agorithms for details about memory allocation strategies).


all the page numbers in your books TOC have a little varying offset
from actual, pictures are nice for kids ..
 
Reply With Quote
 
Standish P
Guest
Posts: n/a
 
      08-17-2010

> 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
today.

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


 
Reply With Quote
 
Standish P
Guest
Posts: n/a
 
      08-17-2010
On Aug 16, 11:09*am, Elizabeth D Rather <(E-Mail Removed)> wrote:
> On 8/15/10 10:33 PM, Standish P wrote:


>
> >>> If Forth is a general processing language based on stack, is it
> >>> possible to convert any and all algorithms to stack based ones and
> >>> thus avoid memory leaks since a pop automatically releases memory when
> >>> free is an intrinsic part of it.

>
> Forth uses two stacks. *The "data stack" is used for passing parameters
> between subroutines ("words") and is completely under the control of the
> programmer. *Words expect parameters on this stack; they remove them,
> and leave only explicit results. *The "return stack" is used primarily
> for return addresses when words are called, although it is also
> available for auxiliary uses under guidelines which respect the primary
> use for return addresses.
>
> Although implementations vary, in most Forths stacks grow from a fixed
> point (one for each stack) into otherwise-unused memory. *The space
> involved is allocated when the program is launched, and is not managed
> as a heap and allocated or deallocated by any complicated mechanism. *On
> multitasking Forth systems, each task has its own stacks. *Where
> floating point is implemented (Forth's native arithmetic is
> integer-based), there is usually a separate stack for floats, to take
> advantage of hardware FP stacks.
>
> >> * * - is forth a general purpose language? Yes
> >> * * - are all algorithms stack based? No

>
> > Does Forth uses stack for all algorithms ? Does it use pointers , ie
> > indirect addressing ? If it can/must use stack then every algorithm
> > could be made stack based.

>
> Forth uses its data stack for parameter passing and storage of temporary
> values. *It is also possible to define variables, strings, and arrays in
> memory, in which case their addresses may be passed on the data stack.
>
> Forth is architecturally very simple. *Memory allocations for variables,
> etc., are normally static, although some implementations include
> facilities for heaps as needed by applications.


> although some implementations include facilities for heaps as needed by applications.


How are these heaps being implemented ? Is there some illustrative
code or a book showing how to implement these heaps in C for example ?

Are dictionaries of forth and postscript themselves stacks if we
consider them as nested two column tables which lisp's lists are in
essence, but only single row. Multiple rows would just be multiple
instances of it at the same level inside parens.

we can peek into stacks which is like car. if it is not unusually
costly computation, why not allow it ? there is no need to restrict to
push and pop.

roll( stack_name, num)

itself can give all those postfix permutations that push and pop cant
generate with a single stack. Can we use dictionaries to generate
multiple stacks inside one global stack ?

 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      08-17-2010
On Aug 17, 6:21 pm, Standish P <(E-Mail Removed)> 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 ?


There are many different ways to implement a heap. The above is
not a good one, and I doubt that it's really used anywhere.

> I have been looking for simple but complete explanation of
> heap for a while and not gotten to it.


Complete in what sense? The basic principle of how to use it is
simple. As for how to implement it, there are many different
algorithms that can be used.

> I think I am looking for a stack allocation on the same
> pattern.


Stack allocation is far, far simpler (usually).

> In a disk, a file is fragmented in many contiguous blocks and
> is accessed automatically.


At the system level, the same thing holds for memory, and the
actual physical memory is "fragmented" into contiguous blocks,
each the size of a page. The MMU (hardware) makes this
transparent to user programs, however.

> > There is no way you could do memory management of all but the most
> > trivial and fixed-length data chunks using a stack.


The length isn't the issue. The order of allocation and freeing
is. (For many specific uses, stack based allocators can and
have been used, but they don't work for generally allocation.)

--
James Kanze
 
Reply With Quote
 
Standish P
Guest
Posts: n/a
 
      08-17-2010
On Aug 17, 1:17*am, (E-Mail Removed) (Torben Ęgidius Mogensen) wrote:
> Standish P <(E-Mail Removed)> writes:
> > [Q] How far can stack [LIFO] solve do automatic garbage collection and
> > prevent memory leak ?

>
> > Because a stack has push and pop, it is able to release and allocate
> > memory. We envisage an exogenous stack which has malloc() associated
> > with a push and free() associated with a pop.

>
> See


How many programmers have applied the ideas of these papers in their
programming practice ? I paste the abstract for convenience

> http://citeseerx.ist.psu.edu/viewdoc...10.1.1.23.5498


Abstract:
This paper describes a memory management discipline for programs that
perform dynamic memory allocation and de-allocation. At runtime, all
values are put into regions. The store consists of a stack of regions.
All points of region allocation and deallocation are inferred
automatically, using a type and effect based program analysis. The
scheme does not assume the presence of a garbage collector. The scheme
was first presented by Tofte and Talpin (1994); subsequently, it has
been tested in The ML Kit with Regions, a region-based, garbage-
collection free implementation of the Standard ML Core language, which
includes recursive datatypes, higher-order functions and updatable
references (Birkedal et al. 96, Elsman and Hallenberg 95). This paper
defines a region-based dynamic semantics for a skeletal programming
language extracted from Standard ML. We present the inference system
which specifies where regions can be allocated and de-allocated and a
detailed proof that the system is sound wi...

>
> http://portal.acm.org/citation.cfm?doid=174675.177855


ABSTRACT
We present a translation scheme for the polymorphically typed call-by-
value &lgr;-calculus. All runtime values, including function closures,
are put into regions. The store consists of a stack of regions. Region
inference and effect inference are used to infer where regions can be
allocated and de-allocated. Recursive functions are handled using a
limited form of polymorphic recursion. The translation is proved
correct with respect to a store semantics, which models as a region-
based run-time system. Experimental results suggest that regions tend
to be small, that region allocation is frequent and that overall
memory demands are usually modest, even without garbage collection.

>
> http://www.springerlink.com/content/m2074884n6gt612h/
>


Abstract
We report on our experience with designing, implementing, proving
correct, and evaluating a region-based memory management system.
dynamic storage management - regions - Standard ML



> * * * * Torben


 
Reply With Quote
 
Brad
Guest
Posts: n/a
 
      08-17-2010
On Aug 17, 10:34*am, Standish P <(E-Mail Removed)> wrote:
> On Aug 16, 11:09*am, Elizabeth D Rather <(E-Mail Removed)> wrote:
>
> How are these heaps being implemented ? Is there some illustrative
> code or a book showing how to implement these heaps in C for example ?
>

Forth does not use a heap, except maybe to implement malloc/free which
many Forth apps do not use. The dictionary is a linked list structure.
Now seems like a good time for you to teach yourself Forth (by
studying the best commercial implementation you can find) since you
seem to be working with a clean slate. But I will say a few things
about stacks in general.

There are many ways to implement stacks. The simplest is to declare
some space for the stack and then post-increment or pre-decrement a
stack pointer depending on whether you're pushing or popping. Normally
you make the memory for them big enough that they don't overflow.

If you are concerned about stack overflow you can change the
implementation. Add bounds checking, for example.

Another trick is to use an 8-bit stack pointer. Then you will have a
circular stack. If there is underflow or overflow it at least will not
step on other data. It will only return bad data, which you may find
preferable to an ugly crash. OTOH, bugs that cause spectacular
failures tend to be discovered. You can also initialize the stack
memory with a pattern like 0xDEAD and then after sufficiently
exercising the code, examine the memory contents to see the "high
water mark" of the stack pointer.

-Brad
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
[Q] How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ? Standish P C++ 87 08-26-2010 08:44 PM
[Q] How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ? Standish P C Programming 52 08-25-2010 02:43 PM
C/C++ compilers have one stack for local variables and return addresses and then another stack for array allocations on the stack. Casey Hawthorne C Programming 3 11-01-2009 08:23 PM
OT: Problem no one can solve so far peace to all A+ Certification 11 07-05-2003 03:00 PM



Advertisments