[Python-Dev] Judy for replacing internal dictionaries?

[Tim Peters]

[Sean Reifschneider]
> Recently at a Hacking Society meeting someone was working on
> packaging Judy for Debian.  Apparently, Judy is a data-structure
> designed by some researchers at Hewlett-Packard.  It's goal is to
> be a very fast implementation of an associative array or
> (possibly sparse) integer indexed array.
>
> Judy has recently been released under the LGPL.
>
> After reding the FAQ and 10 minute introduction, I started wondering
> about wether it could improve the overall performance of Python by
> replacing dictionaries used for namespaces, classes, etc...

Sorry, almost certainly not.  In a typical Python namespace lookup, the pure
overheads of calling and returning from the lookup function cost more than
doing the lookup.  Python dicts are more optimized for this use than you
realize.  Judy looks like it would be faster than Python dicts for large
mappings, though (and given the boggling complexity of Judy's data
structures, it damn well better be <wink>).

As a general replacement for Python dicts, it wouldn't fly because it
requires a total ordering on keys, and an ordering explicitly given by
bitstrings, not implicitly via calls to an opaque ordering function.

Looks like it may be an excellent alternative to in-memory B-Trees keyed by
manifest bitstrings (like ints and character strings or even addresses).