From: "Mauricio Fernández" Date: 2002-08-28T11:25:10+09:00 Subject: Re: ANN: RJudy-0.1 - Judy Arrays for Ruby --n8g4imXOkfNTN/H1 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline On Tue, Aug 27, 2002 at 02:41:19PM +0900, Lyle Johnson wrote: > All, > > I've just uploaded RJudy, an extension module that provides a Ruby > interface to the Judy arrays library. This extension exposes four new > classes to Ruby (Judy1, JudyL, JudySL and JudyHash). The first three are > more-or-less direct wrappers of the current Judy API. The last is a > first cut at a more general replacement for Ruby's Hash (i.e. with > arbitrary-type keys), based on the approach described in the Judy > application note "Scalable Hashing". > > The RDoc documentation for all this stuff is here: > > http://www.knology.net/~lyle/rjudy > > and the source tarball (which also includes those docs) is here: > > http://www.knology.net/~lyle/rjudy-0.1.tar.gz > > Very interesting stuff indeed (Judy, not my personal work). The > "JudyHash" class is still pretty rough by anyone's measure (i.e. > probably lots of opportunities for optimization) but it's already > consistently beating Ruby's Hash (in my admittedly limited benchmarking > tests). If you're interested in playing with this, I could use your help > in coming up with more challenging and meaningful benchmarks, as well as > examples. Also note that I haven't implemented all of Hash's methods > yet, so it's not yet a "drop-in" replacement for Hash. I've replicated most of your code for the last several hours to use JudyL inside the internal hash (st_*). This way, all of Ruby could potentially be faster (including method lookups and of course builtin hashes). It's as rough as your code and then some more, but it already challenges JudyHash's speed in some situations. It is little more than JudyHash's code inside st_*, but hey, you can't expect much more from such a quick hack :-)! BTW, while testing my hashes against JudyHash I found some flaws in the way you do the admittedly simple benchmarks in words.rb: * GC.start should be done between each test to make things a little more fair, otherwise the first to run has the advantage as the GC will be called more frequently in the last ones... * your code uses calloc instead of alloc(), so the Ruby GC heuristics don't work and no GC is called inside JudyHash * in Ruby hashes, a String key is duplicated if it isn't used in the hash already; JudyHash doesn't do that. This is why my Hash seemed to suck badly against JudyHash (9us against 3us to insert, about the same, 2.5us, to lookup) in words.rb, for the keys are new each time, and the associated values are never updated. This means a new String object is created in each insertion... In my hash, insertion will be much faster when the key doesn't need to be replicated. To test this behavior even /usr/share/dict/word could work... head -10000 /usr/share/dict/word > /tmp/data cat /tmp/data /tmp/data /tmp/data /tmp/data > /tmp/data2 cat /tmp/data2 /tmp/data2 /tmp/data2 /tmp/data2 > /tmp/data3 for n in /tmp/data*; do ./ruby -I/usr/local/lib/site_ruby/1.6/i386_linux \ words.rb $n; done I'm attaching a diff, please be indulgent: it's about 4:30AM in my locale and I'm really in need of some sleep. Got no time to find a place to upload all this, plus it's small... Please take a look at the small attached patch... I've had it build in 1.7.2 and I have had it running for some time, seemingly OK, but I'm too tired now to do unit testing :-) Some results here: batsman@kodos:~/src/cvs/ruby-judy$ wc /tmp/data* 10000 10000 122880 /tmp/data 40000 40000 491520 /tmp/data2 160000 160000 1966080 /tmp/data3 640000 640000 7864320 /tmp/data4 850000 850000 10444800 total doneman@kodos:~/src/cvs/ruby-judy$ for n in /tmp/data*; do ./ruby -1@1PI1@ /usr/local/lib/site_ruby/1.6/i386-linux/jwords2.rb $n; Time to insert 10000 words into a JudySL array: 28592 usec. => Average insertion time: 2.8592 usec/insertion. Time to look up 10000 words in a JudySL array: 17007.0 usec. => Average lookup time: 1.7007 usec/word. ================== Time to insert 10000 words into a JudyHash: 53110.99999999999 usec. => Average insertion time: 5.3111 usec/insertion. Time to look up 10000 words in a JudyHash: 16263.0 usec. => Average lookup time: 1.6263 usec/word. ================== Time to insert 10000 words into a Ruby Hash: 30890 usec. => Average insertion time: 3.089 usec/insertion. Time to look up 10000 words in a Ruby Hash: 16794.0 usec. => Average lookup time: 1.6794 usec/word. Time to insert 40000 words into a JudySL array: 91143.0 usec. => Average insertion time: 2.278575 usec/insertion. Time to look up 40000 words in a JudySL array: 63044.0 usec. => Average lookup time: 1.5761 usec/word. ================== Time to insert 40000 words into a JudyHash: 93122.00000000004 usec. => Average insertion time: 2.328050000000001 usec/insertion. Time to look up 40000 words in a JudyHash: 80944.0 usec. => Average lookup time: 2.0236 usec/word. ================== Time to insert 40000 words into a Ruby Hash: 101690.0 usec. => Average insertion time: 2.54225 usec/insertion. Time to look up 40000 words in a Ruby Hash: 70016.0 usec. => Average lookup time: 1.7504 usec/word. Time to insert 160000 words into a JudySL array: 352922.0000000001 usec. => Average insertion time: 2.205762500000001 usec/insertion. Time to look up 160000 words in a JudySL array: 256844 usec. => Average lookup time: 1.605275 usec/word. ================== Time to insert 160000 words into a JudyHash: 399579.0 usec. => Average insertion time: 2.49736875 usec/insertion. Time to look up 160000 words in a JudyHash: 353830.0 usec. => Average lookup time: 2.2114375 usec/word. ================== Time to insert 160000 words into a Ruby Hash: 397741.0 usec. => Average insertion time: 2.48588125 usec/insertion. Time to look up 160000 words in a Ruby Hash: 285617.0 usec. => Average lookup time: 1.78510625 usec/word. Time to insert 640000 words into a JudySL array: 1390958.0 usec. => Average insertion time: 2.173371875 usec/insertion. Time to look up 640000 words in a JudySL array: 1023863.0 usec. => Average lookup time: 1.5997859375 usec/word. ================== Time to insert 640000 words into a JudyHash: 1636917.0 usec. => Average insertion time: 2.5576828125 usec/insertion. Time to look up 640000 words in a JudyHash: 1491516 usec. => Average lookup time: 2.33049375 usec/word. ================== Time to insert 640000 words into a Ruby Hash: 1741098.0 usec. => Average insertion time: 2.720465625 usec/insertion. Time to look up 640000 words in a Ruby Hash: 1309702 usec. => Average lookup time: 2.046409375000001 usec/word. batsman@kodos:~/src/cvs/ruby-judy$ -- _ _ | |__ __ _| |_ ___ _ __ ___ __ _ _ __ | '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \ | |_) | (_| | |_\__ \ | | | | | (_| | | | | |_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_| Running Debian GNU/Linux Sid (unstable) batsman dot geo at yahoo dot com Why use Windows when you can have air conditioning? Why use Windows, when you can leave through the door? -- Konrad Blum --n8g4imXOkfNTN/H1 Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="ruby-judy-0.0.1.patch" diff -rwdu ruby/configure.in ruby-judy/configure.in --- ruby/configure.in Sun Aug 11 23:43:24 2002 +++ ruby-judy/configure.in Tue Aug 27 17:46:42 2002 @@ -281,6 +281,7 @@ AC_CHECK_LIB(crypt, crypt) AC_CHECK_LIB(dl, dlopen) # Dynamic linking for SunOS/Solaris and SYSV AC_CHECK_LIB(dld, shl_load) # Dynamic linking for HP-UX +AC_CHECK_LIB(Judy, JudyLIns) # Judy dnl Checks for header files. AC_HEADER_DIRENT diff -rwdu ruby/hash.c ruby-judy/hash.c --- ruby/hash.c Wed Jul 31 00:30:17 2002 +++ ruby-judy/hash.c Wed Aug 28 03:15:01 2002 @@ -125,11 +125,10 @@ { int status; st_table *tbl = RHASH(arg->hash)->tbl; - struct st_table_entry **bins = tbl->bins; if (key == Qundef) return ST_CONTINUE; status = (*arg->func)(key, value, arg->arg); - if (RHASH(arg->hash)->tbl != tbl || RHASH(arg->hash)->tbl->bins != bins){ + if (RHASH(arg->hash)->tbl != tbl){ rb_raise(rb_eIndexError, "rehash occurred during iteration"); } return status; diff -rwdu ruby/st.c ruby-judy/st.c --- ruby/st.c Wed Jul 31 00:30:20 2002 +++ ruby-judy/st.c Wed Aug 28 03:38:02 2002 @@ -11,27 +11,16 @@ #include #endif +#include + typedef struct st_table_entry st_table_entry; struct st_table_entry { - unsigned int hash; char *key; char *record; st_table_entry *next; }; -#define ST_DEFAULT_MAX_DENSITY 5 -#define ST_DEFAULT_INIT_TABLE_SIZE 11 - - /* - * DEFAULT_MAX_DENSITY is the default for the largest we allow the - * average number of items per bin before increasing the number of - * bins - * - * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins - * allocated initially - * - */ static int numcmp(); static int numhash(); static struct st_hash_type type_numhash = { @@ -66,73 +55,14 @@ #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0) #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key)) -#define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins) - -/* - * MINSIZE is the minimum size of a dictionary. - */ - -#define MINSIZE 8 - -/* -Table of prime numbers 2^n+a, 2<=n<=30. -*/ -static long primes[] = { - 8 + 3, - 16 + 3, - 32 + 5, - 64 + 3, - 128 + 3, - 256 + 27, - 512 + 9, - 1024 + 9, - 2048 + 5, - 4096 + 3, - 8192 + 27, - 16384 + 43, - 32768 + 3, - 65536 + 45, - 131072 + 29, - 262144 + 3, - 524288 + 21, - 1048576 + 7, - 2097152 + 17, - 4194304 + 15, - 8388608 + 9, - 16777216 + 43, - 33554432 + 35, - 67108864 + 15, - 134217728 + 29, - 268435456 + 3, - 536870912 + 11, - 1073741824 + 85, - 0 -}; +#define do_hash_bin(key,table) (do_hash(key, table) % HASHSIZE) -static int -new_size(size) - int size; -{ - int i; +#define HASHARRAY(table,code) ((table)->PJLArray[(code) % HASHSIZE]) +#define HASHINDEX(code) ((code)/HASHSIZE) +#define HASHNODE(ppv) (* (st_table_entry **)ppv) +#define NEWNODE(ppv) *(ppv) = calloc(1, sizeof(st_table_entry)) -#if 0 - for (i=3; i<31; i++) { - if ((1< size) return 1< size) return primes[i]; - } - /* Ran out of polynomials */ - return -1; /* should raise exception */ -#endif -} #ifdef HASH_LOG static int collision = 0; @@ -153,6 +83,12 @@ int size; { st_table *tbl; + int i; + + tbl = alloc(st_table); + //FIXME: optimize + for ( i = 0; i < HASHSIZE; i++ ) + tbl->PJLArray[i] = 0; #ifdef HASH_LOG if (init_st == 0) { @@ -161,13 +97,8 @@ } #endif - size = new_size(size); /* round up to prime number */ - - tbl = alloc(st_table); tbl->type = type; tbl->num_entries = 0; - tbl->num_bins = size; - tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*)); return tbl; } @@ -211,21 +142,28 @@ { register st_table_entry *ptr, *next; int i; + PPvoid_t PValue; + Word_t Index; + st_table_entry *pNode, *pTmp; - for(i = 0; i < table->num_bins; i++) { - ptr = table->bins[i]; - while (ptr != 0) { - next = ptr->next; - free(ptr); - ptr = next; + for(i = 0; i < HASHSIZE; i++) { + Index = 0; + PValue = JudyLFirst(table->PJLArray[i], &Index, PJE0); + while (PValue) { + // go through all the positions inside the Judy array + pNode = HASHNODE(PValue); + while (pNode) { // clear the collision list + pTmp = pNode; + pNode = pNode->next; + free(pTmp); } + PValue = JudyLNext(table->PJLArray[i], &Index, PJE0); } - free(table->bins); - free(table); + JudyLFreeArray(&table->PJLArray[i], PJE0); } -#define PTR_NOT_EQUAL(table, ptr, hash_val, key) \ -((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key))) + free(table); +} #ifdef HASH_LOG #define COLLISION collision++ @@ -234,14 +172,17 @@ #endif #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\ - bin_pos = hash_val%(table)->num_bins;\ - ptr = (table)->bins[bin_pos];\ - if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\ - COLLISION;\ - while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\ - ptr = ptr->next;\ + PPvoid_t PValue;\ + \ + bin_pos = HASHINDEX(hash_val);\ + PValue = JudyLGet(HASHARRAY(table,hash_val), bin_pos, PJE0);\ + if (PValue) {\ + for ( ptr = HASHNODE(PValue); ptr; ptr = ptr->next)\ + if ( EQUAL(table, ptr->key, key) ) \ + break;\ }\ - ptr = ptr->next;\ + else {\ + ptr = 0;\ }\ } while (0) @@ -269,18 +210,15 @@ #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\ do {\ st_table_entry *entry;\ - if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\ - rehash(table);\ - bin_pos = hash_val % table->num_bins;\ - }\ + PPvoid_t PValue;\ \ - entry = alloc(st_table_entry);\ + PValue = JudyLIns(&HASHARRAY(table,hash_val), bin_pos, PJE0);\ \ - entry->hash = hash_val;\ + entry = alloc(st_table_entry);\ entry->key = key;\ entry->record = value;\ - entry->next = table->bins[bin_pos];\ - table->bins[bin_pos] = entry;\ + entry->next = HASHNODE(PValue);\ + *PValue = entry;\ table->num_entries++;\ } while (0) @@ -292,17 +230,32 @@ { unsigned int hash_val, bin_pos; register st_table_entry *ptr; + PPvoid_t PValue; - hash_val = do_hash(key, table); - FIND_ENTRY(table, ptr, hash_val, bin_pos); - if (ptr == 0) { - ADD_DIRECT(table, key, value, hash_val, bin_pos); + hash_val = do_hash(key, table); + PValue = JudyLIns( &HASHARRAY(table, hash_val), HASHINDEX(hash_val), PJE0); + if ( *PValue ) { + for ( ptr = HASHNODE(PValue); ptr; ptr = ptr->next ) + if ( EQUAL(table, ptr->key, key) ) { + ptr->record = value; + return 1; + } + ptr = alloc(st_table_entry); + ptr->key = key; + ptr->record = value; + ptr->next = *PValue; + *PValue = ptr; + ++table->num_entries; return 0; } else { - ptr->record = value; - return 1; + *PValue = alloc(st_table_entry); + HASHNODE(PValue)->key = key; + HASHNODE(PValue)->record = value; + HASHNODE(PValue)->next = 0; + ++table->num_entries; + return 0; } } @@ -315,72 +268,47 @@ unsigned int hash_val, bin_pos; hash_val = do_hash(key, table); - bin_pos = hash_val % table->num_bins; + bin_pos = HASHINDEX(hash_val); ADD_DIRECT(table, key, value, hash_val, bin_pos); } -static void -rehash(table) - register st_table *table; -{ - register st_table_entry *ptr, *next, **new_bins; - int i, old_num_bins = table->num_bins, new_num_bins; - unsigned int hash_val; - - new_num_bins = new_size(old_num_bins+1); - new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*)); - - for(i = 0; i < old_num_bins; i++) { - ptr = table->bins[i]; - while (ptr != 0) { - next = ptr->next; - hash_val = ptr->hash % new_num_bins; - ptr->next = new_bins[hash_val]; - new_bins[hash_val] = ptr; - ptr = next; - } - } - free(table->bins); - table->num_bins = new_num_bins; - table->bins = new_bins; -} - st_table* st_copy(old_table) st_table *old_table; { st_table *new_table; - st_table_entry *ptr, *entry; - int i, num_bins = old_table->num_bins; + st_table_entry *oldptr, *ptr, **entry; + PPvoid_t PValue; + Word_t Index; + int i; - new_table = alloc(st_table); + new_table = st_init_table( old_table->type ); if (new_table == 0) { return 0; } - *new_table = *old_table; - new_table->bins = (st_table_entry**) - Calloc((unsigned)num_bins, sizeof(st_table_entry*)); + new_table->num_entries = old_table->num_entries; - if (new_table->bins == 0) { - free(new_table); - return 0; + for(i = 0; i < HASHSIZE; i++) { + Index = 0; + PValue = JudyLFirst(old_table->PJLArray[i], &Index, PJE0); + while( PValue ) { + if ( *PValue ) { + entry = (st_table_entry **) JudyLIns(&new_table->PJLArray[i], Index, PJE0 ); + *entry = alloc(st_table_entry); + (*entry)->key = HASHNODE(PValue)->key; + (*entry)->record = HASHNODE(PValue)->record; + (*entry)->next = 0; + for (oldptr = HASHNODE(PValue)->next; oldptr; oldptr = oldptr->next) { + ptr = alloc(st_table_entry); + // FIXME: check error in memory allocation + ptr->key = ptr->key; + ptr->record = ptr->record; + ptr->next = *entry; + *entry = ptr; } - - for(i = 0; i < num_bins; i++) { - new_table->bins[i] = 0; - ptr = old_table->bins[i]; - while (ptr != 0) { - entry = alloc(st_table_entry); - if (entry == 0) { - free(new_table->bins); - free(new_table); - return 0; } - *entry = *ptr; - entry->next = new_table->bins[i]; - new_table->bins[i] = entry; - ptr = ptr->next; + PValue = JudyLNext(old_table->PJLArray[i], &Index, PJE0); } } return new_table; @@ -394,33 +322,27 @@ { unsigned int hash_val; st_table_entry *tmp; - register st_table_entry *ptr; + register st_table_entry **ptr, *ptr2; hash_val = do_hash_bin(*key, table); - ptr = table->bins[hash_val]; - + ptr = (st_table_entry **) JudyLGet(HASHARRAY(table, hash_val), + HASHINDEX(hash_val), PJE0); if (ptr == 0) { if (value != 0) *value = 0; return 0; } - if (EQUAL(table, *key, ptr->key)) { - table->bins[hash_val] = ptr->next; - table->num_entries--; - if (value != 0) *value = ptr->record; - *key = ptr->key; - free(ptr); - return 1; - } - - for(; ptr->next != 0; ptr = ptr->next) { - if (EQUAL(table, ptr->next->key, *key)) { - tmp = ptr->next; - ptr->next = ptr->next->next; - table->num_entries--; - if (value != 0) *value = tmp->record; - *key = tmp->key; - free(tmp); + for( tmp = 0, ptr2 = *ptr; ptr2; tmp = ptr2, ptr2 = ptr2->next ) { + if (EQUAL(table, ptr2->key, *key)) { + if(value) *value = ptr2->record; + if(tmp) + tmp->next = ptr2->next; + else // head of the list + *ptr = ptr2->next; + free( ptr2 ); + if ( ! *ptr ) + JudyLDel(&HASHARRAY(table,hash_val), HASHINDEX(hash_val), PJE0); + --table->num_entries; return 1; } } @@ -437,15 +359,17 @@ { unsigned int hash_val; register st_table_entry *ptr; + PPvoid_t pValue; hash_val = do_hash_bin(*key, table); - ptr = table->bins[hash_val]; + pValue = JudyLGet(HASHARRAY(table,hash_val), HASHINDEX(hash_val), PJE0); - if (ptr == 0) { + if (pValue == 0) { if (value != 0) *value = 0; return 0; } + ptr = HASHNODE(pValue); for(; ptr != 0; ptr = ptr->next) { if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) { table->num_entries--; @@ -485,12 +409,20 @@ char *arg; { st_table_entry *ptr, *last, *tmp; + PPvoid_t PValue; + Word_t Index; enum st_retval retval; int i; - for(i = 0; i < table->num_bins; i++) { + for(i = 0; i < HASHSIZE; i++) { last = 0; - for(ptr = table->bins[i]; ptr != 0;) { + Index = 0; + if ( table->PJLArray[i] == 0 ) // empty JudyL array + continue; + PValue = JudyLFirst(table->PJLArray[i], &Index, PJE0); + while ( PValue ) { + ptr = HASHNODE(PValue); + while ( ptr != 0 ) { retval = (*func)(ptr->key, ptr->record, arg); switch (retval) { case ST_CONTINUE: @@ -502,7 +434,7 @@ case ST_DELETE: tmp = ptr; if (last == 0) { - table->bins[i] = ptr->next; + HASHNODE(PValue) = ptr->next; } else { last->next = ptr->next; @@ -510,9 +442,11 @@ ptr = ptr->next; free(tmp); table->num_entries--; - } - } - } + } // switch + } // while to scan collision list + PValue = JudyLNext(table->PJLArray[i], &Index, PJE0); + } // while to scan Judy array + } // for } static int diff -rwdu ruby/st.h ruby-judy/st.h --- ruby/st.h Wed Jan 5 05:37:12 2000 +++ ruby-judy/st.h Wed Aug 28 01:19:43 2002 @@ -6,6 +6,8 @@ #define ST_INCLUDED +#include + typedef struct st_table st_table; struct st_hash_type { @@ -13,11 +15,14 @@ int (*hash)(); }; +#define HASHSIZE 256 +#define LOG_HASHSIZE 8 +// make these coherent + struct st_table { struct st_hash_type *type; - int num_bins; int num_entries; - struct st_table_entry **bins; + Pvoid_t PJLArray[HASHSIZE]; }; #define st_is_member(table,key) st_lookup(table,key,(char **)0) --n8g4imXOkfNTN/H1--