[uClibc]Re: uclibc malloc (`malloc') borked?

Miles Bader miles at lsi.nec.co.jp
Fri Jul 19 01:21:42 UTC 2002


Erik Andersen <andersen at codepoet.org> writes:
> I ran a quick check doing 20 million malloc/frees of various
> sizes.  Using "malloc-simple" it took 2 min 10 sec on my Athlon
> workstation.  Using your new malloc it took just 24 seconds.
> Using malloc-930716 it took 3.9 seconds (but since that is using
> brk() it really isn't comparable).

Hmmm, I tried mostly to reduce space usage, not make it fast, but 24
seconds seems a bit pathetic, and I wouldn't think mmap vs. sbrk makes
_that_ much difference.  I think a bit of profiling is in order to see
if there are any obvious hot-spots.

In particular, I'll be there's a bunch of heap fragmentation going on,
especially if you're really doing things in random order.  If the heap
gets fragmented, it's particularly bad for this implementation, since it
always does a linear scan from the beginning of the heap.

For the malloc function, this might be alleviated by just using a
circular list and starting the scan from the last successful spot (I
think malloc-930716 does this), but the free routines can't really do
this, so something to reduce the fragmentation is needed.

One thing that particularly bugs me is that if your mmap doesn't return
blocks in order, the heap will end up being a list of disconnected
free-areas; it will remove free-areas if they are entirely allocated,
but if you don't do many small allocations, you might end up with each
free area looking like:

+--------------------+---------------------+---------------------+------+
| ALLOC              | ALLOC               | ALLOC               | FREE |
+--------------------+---------------------+---------------------+------+

with `FREE' unable to be used because it's too small for your
allocations, but still occupying a place in the free-area list.

It currently will attach the extra tail-end of the free-area to an
allocated block if it's very small, which allows the free-area to be
removed, but that only helps if the size of the tail-end (`FREE') is
particularly small.  One idea I had was that it should use the size of
the current allocation to make this decision rather than a small
constant, which should help it adapt better to a consistent allocation
pattern (of course, it would have to have an upper limit too, to avoid
wastefully increasing the size of very big allocations).

Also, maybe it should use sbrk to extend the heap on MMU platforms
(this needn't even increase the code size, as it use #ifdef to decide), 
since that's faster, and guaranteed to return contiguous memory, which
should help avoid fragmentation too.

Can you send me your test program?

Thanks,

-Miles
--
Somebody has to do something, and it's just incredibly pathetic that it
has to be us.  -- Jerry Garcia



More information about the uClibc mailing list