[boost] Sparse tables and perfect hashing [ was: multidimensional arrays (was Boost Mathematicians) ]

From: Joel de Guzman (joel_at_[hidden])
Date: 2004-08-04 23:40:15

Larry Evans wrote:

> I'd be very interested.  I'm thinking about using a sparse matrix
> where T is symbol_set, where symbol_set is the set of terminal
> and non-terminal symbols in a grammar.  This could be used by
> spirit in deriving LL(k) parser as described in:
> 
>   http://facweb.cs.depaul.edu/tchristopher/llkppr.pdf

Larry, I've recently experimented on perfect hashing (minimal
and non-minimal) where the input is a char or wchar_t or int.
What's interesting is that, based on my tests, I exceeded the
speed of C++'s switch-case.

I did a test on perfect hashing of integers and tested it against
a switch in a loop:

     int test(int i)
     {
         switch (i)
         {
             case 1: return 0;
             case 4: return 1;
             case 9: return 2;
             case 16: return 3;
             case 25: return 4;
             case 36: return 5;
             case 49: return 6;
             default: return -1;
         }
      }

vs. a corresponding perfect hash table. I got 6.6 secs (switch)
vs. 0.422 (perfect hash) secs on VC7.1. G++'s switch was faster
(i got 2.2) but still  4X slower than the perfect hash. The perfect
hash generation can be done at runtime using metaprogramming. I
based the algorithms on Bob Jenkin's perfact hash stuff:

     http://burtleburtle.net/bob/hash/perfect.html

I think I've got the makings of an extremelely fast LL(1) engine.
See attached test.

Regards,
-- 
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net