J
jacob navia
Everybody knows that hash tables are fast.
What is less known is that perfect hash tables are even faster.
A perfect hash table has a hash function and a table layout that
avoids collisions completely. You can lookup a key in the table
with a single hash function call.
What is even less known is that there is a perfect software
for generating perfect hash tables called "gperf" offered by
GNU INC.
This software will take a bunch of strings (the keys), and generate
a hash table layout and a hash function for it in C. You add
the generated file to your project and you gain a LOT of speed
with static table lookups. This is very useful for tables that
are known in advance of course, since you can't modify the
perfect hash table at run time by adding or deleting elements.
What is even less known, is that you can hack gperf to generate
code to call a function of you directly instead of returning the
character string...
I used that last twist in an assembler I wrote for the PowerPC
AIX system earlier this year. The hacked gperf output called
directly the function "add" when it saw the opcode "add",
making for an incredible fast lookup.
Gperf is easy to hack, it is just C (with some C++ crafted to it
but this happens even in the best families) ...
Gperf is a very good solution for static tables. It can mean a lot when
you have a performance bottleneck in a table lookup.
Recommended!
jacob
What is less known is that perfect hash tables are even faster.
A perfect hash table has a hash function and a table layout that
avoids collisions completely. You can lookup a key in the table
with a single hash function call.
What is even less known is that there is a perfect software
for generating perfect hash tables called "gperf" offered by
GNU INC.
This software will take a bunch of strings (the keys), and generate
a hash table layout and a hash function for it in C. You add
the generated file to your project and you gain a LOT of speed
with static table lookups. This is very useful for tables that
are known in advance of course, since you can't modify the
perfect hash table at run time by adding or deleting elements.
What is even less known, is that you can hack gperf to generate
code to call a function of you directly instead of returning the
character string...
I used that last twist in an assembler I wrote for the PowerPC
AIX system earlier this year. The hacked gperf output called
directly the function "add" when it saw the opcode "add",
making for an incredible fast lookup.
Gperf is easy to hack, it is just C (with some C++ crafted to it
but this happens even in the best families) ...
Gperf is a very good solution for static tables. It can mean a lot when
you have a performance bottleneck in a table lookup.
Recommended!
jacob