Re: Is Minimal Perfect Hashing the wrong algorithm

bobduff@world.std.com (Robert A Duff)
8 Apr 1996 23:19:33 -0400

          From comp.compilers

Related articles
Is Minimal Perfect Hashing the wrong algorithm? cef@geodesic.com (Charles Fiterman) (1996-04-02)
Re: Is Minimal Perfect Hashing the wrong algorithm chase@centerline.com (1996-04-08)
Re: Is Minimal Perfect Hashing the wrong algorithm bobduff@world.std.com (1996-04-08)
| List of all articles for this month |

From: bobduff@world.std.com (Robert A Duff)
Newsgroups: comp.compilers
Date: 8 Apr 1996 23:19:33 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 96-04-012 96-04-045
Keywords: theory, symbols

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
--


Post a followup to this message

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