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