[PD-dev] Re: is namecanvas obsolete or not?

[Tim Blechmann]

> i'd strongly suggest to enlarge the hash-table any try to find a
> better solution for symbols ...
something like:
--- m_class.c.~1.3.4.4.~        2004-11-24 19:25:03.000000000 +0100
+++ m_class.c   2005-01-02 14:13:33.086810696 +0100
@@ -501,7 +501,15 @@
 
 /* ---------------- the symbol table ------------------------ */
 
+/* tb: new 16 bit hash table: multiplication hash */
+#define NEWHASH
+
+#ifndef NEWHASH
 #define HASHSIZE 1024
+#else 
+#define HASHSIZE 65536
+#define HASHFACTOR 40503 /* donald knuth: (sqrt(5) - 1)/2*pow(2,16) */
+#endif
 
 /* tb: made dogensym() threadsafe */
 t_symbol *dogensym(char *s, t_symbol *oldsym)
@@ -512,7 +520,11 @@
 #endif
        
        t_symbol **sym1, *sym2;
+#ifdef NEWHASH
+    unsigned short hash1 = 0, hash2 = 0;
+#else
     unsigned int hash1 = 0,  hash2 = 0;
+#endif
     int length = 0;
     char *s2 = s;
     while (*s2)
@@ -522,7 +534,12 @@
         length++;
         s2++;
     }
+#ifdef NEWHASH 
+       hash2 = hash2 * HASHFACTOR;
+       sym1 = symhash + hash2;
+#else
     sym1 = symhash + (hash2 & (HASHSIZE-1));
+#endif
     while (sym2 = *sym1)
     {
         if (!strcmp(sym2->s_name, s)) return(sym2);

after massively generating symbols in the (attached) patch, you can see
that the new approach is much faster for systems with lots of symbols
...

drawbacks: big (very big) hash table 262kb for 16 bit hash

cheers ... tim

-- 
mailto:TimBlechmann at gmx.de    ICQ: 96771783
http://www.mokabar.tk

After one look at this planet any visitor from outer space 
would say "I want to see the manager."
				      William S. Burroughs
-------------- next part --------------
A non-text attachment was scrubbed...
Name: hash.pd
Type: application/octet-stream
Size: 277 bytes
Desc: not available
URL: <http://lists.puredata.info/pipermail/pd-dev/attachments/20050102/d314d279/attachment.obj>