[Python-Dev] The memo of pickle

[Tim Peters]

[Greg Ewing]
> Is there perhaps a more memory-efficient data structure that
> could be used here instead of a dict? A b-tree, perhaps,
> which with a suitable bucket size could use no more than
> about 8 byte per entry -- 4 for the object reference and
> 4 for the integer index that it maps to.

The code to support BTrees would be quite a burden.  Zope already has that,
so it wouldn't be a new burden there, except to get away from comparing keys
via __cmp__ we'd have to use IIBTrees, and those map 4-byte ints to 4-byte
ints (i.e., they wouldn't work right for this purpose on a 64-bit box --
although Yet Another Flavor of BTree could be compiled that would).

Judy tries look perfect for "this kind of thing" (fast, memory-efficient,
and would likely get significant compression benefit from that the high bits
of user-space addresses tend to be the same):

    http://sf.net/projects/judy/