[ILUG] Re: thoughts on malloc...

[kevin lyda]

suberic.net is currently down, so i'm replying from what i've read
on linux.ie.

first, other languages and/or memory allocation schemes.  yes, some
other languages handle memory allocation better.  and yes there are
alternatives to malloc even in c - boehm's gc being one of the better
known.  and that's fine.  that's another tangent, i'm just covering
this tangent.

second, paul's comment about what i said, as well as some others,
demonstrates i wasn't very clear (or assumed more knowledge about the
internals of malloc then people have).

malloc returns memory locations.  each call to malloc may, or may not
make calls to sbrk (or whatever os routine increases the heap - in fact
gnu's malloc will use mmap on occasion).  let's say i make the following
malloc calls:

    malloc(10) ==> 20
    malloc(10) ==> 30
    malloc(10) ==> 40
    malloc(10) ==> 50

now i free location 30.  that means there's a 10 byte hole in the heap.
now different malloc implementations work different ways, but let's say
this one will return 30 and 35 the next time i reserve two 5 byte chunks.
no sbrk calls.  in addition, since only 40 bytes were allocated, chances
are malloc actually allocated an entire page on the first call.

now for free to work, malloc has to do accounting.  so each call
requires malloc to record each location returned and the size of each.
so somewhere there's a table that says 20(10), 30(5), 35(5), 40(10),
50(10).  it might be an actual table or it might be just before the
block allocated or whatever.

wherever it is, free looks in that "table" and marks the memory as "free."
it's very rare that free actually sends memory back to the os.  in part
because it's probably in a "hole" with still "allocated" memory on
each side.

so, doing a big malloc is a pain, because then i have to do the same
thing in the block i've allocated.  this call signature:

    malloc==>1, malloc==>2, free(1), malloc==>3, malloc==>4, free(3)

would be very hard to implement with a large initial malloc.  and if
you had a linked list that you allocated in sections (10 members here,
5 there, 100 later, and so on) you'd pretty much need to reimplement
the functionality of malloc and free.  my suggestion was just to make it
so that this functionality could be rolled into pretty much any malloc
implementation with no change to other routines.

the extra args to malloc_reserve are there to tell malloc how much room
it will need in its table.  100 mallocs for 1024 bytes will require more
memory then one malloc call for 102400 bytes.

the reserve suggestion wouldn't lead to a greater chance for leaks as
it's just a hint to malloc's internals as to how much memory is about to
be reserved.  it could even be more efficient as it can lead to just one
sbrk call instead of several (which is also why some programs actually
fire off one large malloc and manage the pool themselves).

while reading up on some bits regarding this i came across this paper
which is pretty interesting.  dunno where libfig is, but it would be
nice to use.

    http://www.cs.berkeley.edu/~nks/fig/

kevin

-- 
kevin at suberic.net          buffy: come on, can't you put your foot down?!
fork()'ed on 37058400      giles: it *is* down.
meatspace place: orbit     buffy: one of these days you're going to have to
http://suberic.net/~kevin         get a grown up car.  --inca mummy girl