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

Tim Peters tim.one at comcast.net
Tue Jul 30 18:04:17 MDT 2002


Goodness, what an elaborate collection of Cc:s <wink>.

[Douglas Baskins]
> One of my favorite benchmarks is to take a good hash method and replace
> the synonym handling code with the appropriate Judy array.  Since a
> Judy array is allocated with a NULL pointer, this is typically an easy
> thing to do.  Next compare speed and space performance versus population.
> Then change the size of the hash table (in the code using Judy) and
> re-measure.  I have found that a hash table size of 1 is usually the
> preferred choice.
>
> However, there are applications where the working-set (WS) is small
> enough to reside in the CPU's data cache.  In this case a hash table
> size of 256 and a hash method of a simple shift/mask may be the
> preferred choice.  A hash table must inhabit the data cache to maintain
> good performance.

Sean Reifschneider was asking about Judy arrays to speed Python's
namespaces, which are implemented as hashtables now, mapping strings to
arbitrary objects (memory addresses).  Namespaces are typically very small,
with far fewer than 256 slots (the mode is 8 slots; Sean may dispute this,
but I can argue about that with him offline <wink>).  The hash table index
is gotten by masking off the low bits of the hash code; "the strings" used
as namespace keys are typically interned (stored uniquely, and the hash code
is cached at creation time); and then one pointer compare is usually enough
to decide equality.  This is the typical path on a lookup:

static dictentry *
lookdict_string(dictobject *mp, PyObject *key, register long hash)
{
	register int i;
	register unsigned int perturb;
	register dictentry *freeslot;
	register unsigned int mask = mp->ma_mask;
	dictentry *ep0 = mp->ma_table;
	register dictentry *ep;

	i = hash & mask;
	ep = &ep0[i];
	if (ep->me_key == NULL || ep->me_key == key)
		return ep;

For small dicts (<= 8 slots), the hashtable slot memory lives inside the
dictobject struct, so mp->ma_table points into *mp then, and the entire
struct is a self-contained unit, which fits in about 150 bytes.  This is
hard to beat for speed.  There may easily be hundreds of thousands of these
guys alive at one time, though.  It's hard to say anything about "typical"
memory patterns, since Python is a general-purpose programming language, and
just about everything is highly application-dependent.

> Using a large hash table when the WS outgrows the data cache can negate
> its effectiveness for all (including the very important stack).  A good
> hash method can be in direct opposition to the "locality" needs of a
> data cache.  The hierarchical use of memory in Judy is well matched to
> the requirements of an effective data cache.

I read the papers, and I believe you <wink>.  Judy looks great!  There are
places within Python's implementation I'd like to use it, to replace
homegrown solutions that, as you pointed out in one of the papers, were
adequate at the time they were introduced but didn't scale well along with
ambitions.  I'd also like to see a Python wrapper written for Judy, as the
only semi-standard "ordered mapping" object available to Python users now is
the B-Tree implementation from Zope, and that's designed primarily to play
nice with a persistent OO database (so is less concered about in-memory
speed than it is about breaking the structure into pieces that can be
updated independently; for example, you store clues about range counts in
your nodes, but Zope B-Trees don't even store size info at nodes other than
leaves, because adding or deleting a pair would then require mutating a
non-leaf object too, and that would create needless conflicts at transaction
commit time; etc -- nothing's simple anymore <wink>).

For Python's hashtables in general (called "dictionaries"), a class that
wants instances to be usable as keys need only define hash and equality
methods now.  They needn't define a consistent total ordering, nor is there
any notion of "the bits" to be looked at.  So that seems to me to be wholly
outside what Judy is aiming at.  If a Python wrapper for the Judy library
were available, though (it should be easy to make Judy arrays appear to be
first-class Python objects -- Python excels at wrapping external C
libraries), I'm sure many Python applications would find excellent use for
it.




More information about the NCLUG mailing list