Re: Is Minimal Perfect Hashing the wrong algorithm

David Chase <chase@centerline.com> wrote:
>Nowadays, whenever I need a hash table, any hash table, I use the one
>that I wrote back in 1986.
>[good stuff deleted]


Ah, truly reusable code! Cool. One sees a lot of hype about reusable
code, but not a whole lot of reusable code. ;-)


A couple of questions:


1. I'm interested in more details. Especially on your swap-to-front
algorithm. Would you like to post your code, or else describe it in
more detail?


2. Is hashing still a good idea these days? Caches are becoming more
and more important, as CPUs get faster faster than memory access gets
faster. A hash table (deliberately) destroys locality of reference,
so should compilers these days be using B trees or some such thing
instead of hash tables?


>I noodled around a little bit with perfect hashing once, but the
>benefits didn't seem to be worth the effort.


I agree with you, and with our moderator: if you're going to hash
reserved words, use the same hash table that's used for identifiers.
And, as somebody pointed out, explicit code in the lexer is even more
efficient (although it's less maintainable, if hand-written). As far
as I can tell, perfect hashing is only useful if you're dealing with a
non-extensible language, where the set of things you want to look up
is fixed.


- Bob
--

Return to the comp.compilers page.
Search the comp.compilers archives again.