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)
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 http://www.boost-consulting.com http://spirit.sf.net
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk