[NCLUG] Re: dlmalloc fix

[Douglas Baskins]

> > [Doug Baskins] 
> > However, the free() is another story.  I found all mallocs (that
> > coalesce memory) have very serious problems in this area.  I found the
> > dlmalloc was the best of the bunch, but had a flaw.  I investigated why.
> > The problem occurs when a huge flurry of small blocks (3..65 words) are
> > freed to produce large (coalesced) internal blocks of several Kbytes.
> > Dlmalloc may put thousands of these "several Kbytes" blocks of slightly
> > different sizes on the SAME free list.
> 
> [Doug Lea]
> Release 2.7.1 (A minor update released recently) has a tuning
> threshold for leaving bins unsorted. See FIRST_SORTED_BIN_SIZE in
>   http://gee.cs.oswego.edu/pub/misc/malloc.c

Thanks, I will give it a try.  It may do the trick.

> 
> 
> >   Solutions may include
> > making the list a skiplist, or make many more lists in the Kbyte sizes.
> 
> One of these days, I'll release a version that includes a ternary trie
> that works really well here, but slows down the average case. I'm
> hoping to have a flash of insight someday that will make average case
> enough faster to justify putting it in.

How bout maintain the number of items in the list and converting to a
tree, skiplist or whatever, when the list length gets past some threshold.
I am sure that could be done in a couple nano-seconds in a modern machine.

I really want to get this problem fixed for the whole world.  It is
really bad on 64 bit programs. (sometimes a 1000 to 1 slowdown).
I have lots of experiments and data.

Thanks in advance,
Doug Baskins <doug at sourcejudy.com>

> 
> -- 
> Doug Lea, Computer Science Department, SUNY Oswego, Oswego, NY 13126 USA
> dl at cs.oswego.edu 315-312-2688 FAX:315-312-5424 http://gee.cs.oswego.edu/  
>