Boost logo

Boost :

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:

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:

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


Joel de Guzman

Boost list run by bdawes at, gregod at, cpdaniel at, john at