Thoughts on memory freeing
S James S Stapleton
memory, and the other kind (I don't know the term off the top of my head,
but it's seen in C/C++ and done by directly calling the memory deallocation
function).
There's arguments as to which is better for a program, and a lot of what
I've seen points to the GC methods. If you are using a language where GC is
nontrivial, would it be advantage to have a memory deallocation thread? By
that I mean, rather than directly deallocate (i.e. a free call), call
something which will put the memory free'ing on another thread (either by
placing it on a to-be-deleted queue - which would have delays due to
locks/mutexes, or by running each deallocation in it's own thread - which
would have the thread creation overhead).
Does anyone have any thoughts (or better yet, suggestions for good reading,
preferably of the dead-tree kind, that I could pick up at the library) on
this?
Thanks.
santosh
> In languages, you end up having 'garbage collecting' methods for
> freeing memory, and the other kind (I don't know the term off the top
> of my head, but it's seen in C/C++ and done by directly calling the
> memory deallocation function).
One term you can use is manual memory management, as opposed to Garbage
Collection whose whole purpose is to automate the task of deallocation.
> There's arguments as to which is better for a program, and a lot of
> what I've seen points to the GC methods.
If your language supports GC and you can accept some of it's
shortcomings, then GC certainly frees you from what would otherwise be
tedious accounting and not directly related to the problem that the
program tries to solve.
> If you are using a language
> where GC is nontrivial, would it be advantage to have a memory
> deallocation thread? By that I mean, rather than directly deallocate
> (i.e. a free call), call something which will put the memory free'ing
> on another thread (either by placing it on a to-be-deleted queue -
> which would have delays due to locks/mutexes, or by running each
> deallocation in it's own thread - which would have the thread creation
> overhead).
You would be reimplementing a lot of the functionality of your
language's "free" routine by doing this, unless of course your language
is primitive enough to not provide them in the first place.
For some applications which have a complex pattern of allocation and
deallocation it might indeed benefit from a customised memory manager.
Such examples are quite common in many large programs. But I would
stick to the functionality provided by the language unless such need is
really felt, since a good memory allocator is no trivial task,
particularly with the advent of multi-threading.
> Does anyone have any thoughts (or better yet, suggestions for good
> reading, preferably of the dead-tree kind, that I could pick up at the
> library) on this?
<http://search.barnesandnoble.com/Memory-as-a-Programming-Concept-in-C-and-C/
Frantisek-Franek/e/9780521520430/?itm=3>
<http://search.barnesandnoble.com/Garbage-Collection/Richard-Jones/e/
9780471941484/?itm=2>
<http://www.memorymanagement.org/>
<http://portal.acm.org/citation.cfm?id=582419.582421>
<http://g.oswego.edu/dl/html/malloc.html>
<http://www.hoard.org/>
<http://www.fourmilab.ch/bget/>
and
Section 2.5 in Knuth's Fundamental Algorithms.
Also various language specific books (for example The Standard C Library
by PJ Plauger and C Unleashed by Heathfield, Kirby et al for C) devote
sections to consider memory allocation for their languages.
S James S Stapleton
"santosh" <santo...@gmail.com> wrote in message
news:g6nd3o$omb$1...@registered.motzarella.org...
>S James S Stapleton wrote:
>
>> In languages, you end up having 'garbage collecting' methods for
>> freeing memory, and the other kind (I don't know the term off the top
>> of my head, but it's seen in C/C++ and done by directly calling the
>> memory deallocation function).
>
> One term you can use is manual memory management, as opposed to Garbage
> Collection whose whole purpose is to automate the task of deallocation.
>
>> There's arguments as to which is better for a program, and a lot of
>> what I've seen points to the GC methods.
>
> If your language supports GC and you can accept some of it's
> shortcomings, then GC certainly frees you from what would otherwise be
> tedious accounting and not directly related to the problem that the
> program tries to solve.
>
>> If you are using a language
>> where GC is nontrivial, would it be advantage to have a memory
>> deallocation thread? By that I mean, rather than directly deallocate
>> (i.e. a free call), call something which will put the memory free'ing
>> on another thread (either by placing it on a to-be-deleted queue -
>> which would have delays due to locks/mutexes, or by running each
>> deallocation in it's own thread - which would have the thread creation
>> overhead).
>
> You would be reimplementing a lot of the functionality of your
> language's "free" routine by doing this, unless of course your language
> is primitive enough to not provide them in the first place.
Oh, I was thinking of just calling 'free' in it's own thread as the main
implementation idea. I take it the system's free implementation probably
already does this?
> <http://search.barnesandnoble.com/Memory-as-a-Programming-Concept-in-C-and-C/
> Frantisek-Franek/e/9780521520430/?itm=3>
> <http://search.barnesandnoble.com/Garbage-Collection/Richard-Jones/e/
> 9780471941484/?itm=2>
> <http://www.memorymanagement.org/>
> <http://portal.acm.org/citation.cfm?id=582419.582421>
> <http://g.oswego.edu/dl/html/malloc.html>
> <http://www.hoard.org/>
> <http://www.fourmilab.ch/bget/>
>
> and
>
> Section 2.5 in Knuth's Fundamental Algorithms.
>
> Also various language specific books (for example The Standard C Library
> by PJ Plauger and C Unleashed by Heathfield, Kirby et al for C) devote
> sections to consider memory allocation for their languages.
Thanks. Time to see which my library has. I was looking more for the
theoretical than the language specific, but I guess language specific would
have insight into implementations and how they handled memory management. I
never considered that 'free' might already take this approach.
Thanks for the reading list.
gremnebulin
> "santosh" <santosh....@gmail.com> wrote in message
You need to track what needs freeing. Free() is uncodinitional. Some
implemetnations crash if
you free the same memeory twice, too.
Chris M. Thomasson
news:g6n71s$8ld$1...@charm.magnus.acs.ohio-state.edu...
> In languages, you end up having 'garbage collecting' methods for freeing
> memory, and the other kind (I don't know the term off the top of my head,
> but it's seen in C/C++ and done by directly calling the memory
> deallocation function).
>
> There's arguments as to which is better for a program, and a lot of what
> I've seen points to the GC methods. If you are using a language where GC
> is nontrivial, would it be advantage to have a memory deallocation thread?
> By that I mean, rather than directly deallocate (i.e. a free call), call
> something which will put the memory free'ing on another thread (either by
> placing it on a to-be-deleted queue - which would have delays due to
> locks/mutexes, or by running each deallocation in it's own thread - which
> would have the thread creation overhead).
You don't need to use mutexs to implement the queue.
Chris M. Thomasson
Its usually much better to free memory to the same thread which allocated
it. Several memory allocators use per-thread heaps such that allocations can
be accomplished without using _any_ synchronization whatsoever. Also,
freeing memory which belongs to the calling threads heap is a
synchronization free operation. However, if you free memory to a thread that
did not allocate it, then the free operation needs to pass the memory back
to the thread which owns it. This does require a synchronization operation.
For an example of such a memory allocator you can take a look at the
following algorithm I invented:
http://groups.google.com/group/comp.arch/browse_frm/thread/24c40d42a04ee855
(the first link points to the pseudo-code...)
As you can see, if the free operation needs to pass memory back to the owner
thread it uses an atomic CAS instruction. When the owner threads private
memory is exhausted, it uses an atomic SWAP instruction to reclaim foreign
free operations.
thomas...@gmx.at
> In languages, you end up having 'garbage collecting' methods for freeing
> memory, and the other kind (I don't know the term off the top of my head,
> but it's seen in C/C++ and done by directly calling the memory deallocation
> function).
There are several technics to manage memory, and the destinction
into GC and 'doing it by hand' is too simple. If you look only at
languages which create new values with the 'new' (or some similar)
operator this classification might be adequate, but in general there
are more memory management technics:
- Global data which exists as long as the program runs
(E.g.: An array which contains a conversion table or a string to
which lines are appended and which is written to a file before
the program ends). This needs no management but it could be feed
automatically (by processing the list of global declared data).
- Local data which exists as long as a function or block executes
(E.g.: Integer or string variables or value parameters declared
in a function). When the function or block is left it is easily
possible to free local data, even if it is complicated like an
array of structs with strings as elements. It is clear that
carrying pointers into such local data outside of the function is
something illegal, but the compiler could check for such things
by comparing the lifetime of the pointer and the lifetime of the
data.
Note that although this is stack oriented technic, the actual values
can be at the program stack or at the heap and they can also grow in
size (Strings with variable size can be implemented with this
technic).
The technic above assumes that there is a 1:1 relationship between
the variable (or constant or parameter) and its value. But not
everything can be described this way. Sometimes it is necessary
that several variables can refer to the same value. Most programming
languages solve this problem by using pointers (or references). The
variable points to the value which is at the heap.
- When it is possible to differentiate between one owning pointer
and several non-owning pointers aggain a stack oriented
management can be done, using the owning pointers. The non-owning
pointers would not cause any memory management. This concept
of two pointer categorys is natural when there is a hierarchical
data structure which is processed with non-owning pointers.
- When no pointer can be identified as owner, and no pointer cycles
exist (the data structure is a tree), reference counting can be
used. File classes can be implemented this way, as a 'write' to
a file which ends up writing recursively to itself (in a cyclic
data structure) would be very unusual.
More complicated situations must be managed by hand or with a GC.
If there are enough containers present many uses of pointers (to
manage lists, trees, hash tables, etc.) are not necessary. This
further reduces the need for manual memory management or GC.
If a GC concentrates on data which cannot be managed in a simpler
way it is probably much faster. Therefore I see the philosopy to
let the GC manage all data as the wrong way of doing something.
Greetings Thomas Mertes
Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.