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

[Douglas Baskins]

Tim:

...del

> [Tim Peters]
> 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,

...del

> 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

...del

Ok, you asked... 

I am about to say some perhaps 'controversial' things.  I have illustrative 
benchmarks to support my conclusions and I will welcome critical reviews.

I have spent about 99% of my time in the last 3 years completing Judy1/L 
(while working for Hewlett-Packard).  They are mappings of a word 
(unsigned long) to a bit(Judy1) or word(JudyL).  Judy1 and JudyL are 
basically the same algorithm and share the same source code.  I believe
Judy1/L met the goals of a general, in memory, best speed, best scalability
and a best memory efficiency method.  However, I hope it is not the final 
chapter on sorting and searching and will advance research on this approach.
(Is this too arrogant? -- time will tell).

The remainder of what I am going to say here relates to "mapping strings
to arbitrary objects" as you put it.  The string problem is actually a
different animal.  This is what JudySL does and should not be confused
with Judy1/L.

JudySL started out as an outlandish test of JudyL.  A single JudySL array
can be made up of hundreds of thousands of JudyL arrays.  Until recently,
I had not characterized JudySL.  Stimulated by a recent paper "Burst tries:
A fast, efficient data structure for string keys (ACM Vol. 20, No. 2,
April 2002)", I wrote a benchmark (www.sourcejudy.com/benchmarks/ ->
SLcompare.c) to compare JudySL with fast methods written by one of the 
authors of this paper.  The results lead me to the following conclusions:

1) The string key store/lookup problem is basically "solved".
2) The binary tree is an obsolete method -- they don't scale well.
3) Hashing methods are very near obsolete - due to re-sizing table needs.

Remarkably, JudySL was the fastest "ordered mapping" method by a slight
margin but, was more notable for its memory efficiency.  A hashing method
that scales, requires awkward re-sizing the hashing table.  This would 
likely make the stores slower and disjoint in performance.  Hash lookup
times were generally the fastest by a slim margin over JudySL.

I believe any of the methods in this benchmark (except hashing) would be
an excellent match for use in an interpreter such a Python.  (Of course,
I would prefer you use Judy).  I think memory efficiency and scaleablity
are the most important requirements of an interpreter.

...del
> lookdict_string(dictobject *mp, PyObject *key, register long hash)
...del
> 	if (ep->me_key == NULL || ep->me_key == key) return ep;

I suspect the performance 'shortcut' by comparing the string pointer 
is 'buried' under the expensive subroutine call to lookdict_string().
Does removing this code effect performance?  (If it does, I would be
curious by how much, why and what was the test case?)

I am considering a "persistent" Judy project in the near future.  My
goal would be to obsolete the b-tree.

Also on the plate is a more scalable malloc() (just waiting to be done) 
and a fast, multi-cpu version of Judy.

Thanks for your interest,

Doug Baskins (doug at sourcejudy.com)