[NCLUG] Re: [Python-Dev] Judy for replacing internal dictionaries?

[Doug Lea]

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

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


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

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