Eric S. Raymond
esr at thyrsus.com
Mon Nov 28 20:48:46 UTC 2016
Mark Atwood <fallenpegasus at gmail.com>:
> On Sun, Nov 27, 2016 at 1:00 AM Achim Gratz <Stromeko at nexgo.de> wrote:
> > Eric S. Raymond writes:
> > > OK, there are two ways we can handle this.
> > The third way is building a hash table that maps each possible unique
> > prefix to the actual full-length command.
> I was on a project years ago that did that (minimal length matching of
> command strings).
> Someone on team dug up an amazing little utility that ingested a list of
> strings, and emitted a human-unreadable table-driven maximally efficient C
> function that implemented some computer science magic state machine
> character parser that took as a parameter char* and returned a integer or
> enum that designated one of the target strings that was minimal matched by
> the input.
> We then made running this code generator a Makefile production, and
> compiled the generator itself as another dependent Makefile production.
> I'm struggling now to remember it's name...
Wow, does *that* take me back.
The technique is called "perfect hashing", and used to be part of the
standard bag of tricks for writing compilers. I rember reading an
article about this 40-odd years ago in one of my dad's Communications of
the ACM. This was a few years before I was an actual programmer.
I've tripped over it a few times since, but it's almost never used anymore.
It made sense in a world of v e r y s l o w p r o c e s s o r s but the
tradeoffs are wrong for modern systems - you lose more in code weight
than you gain in execution speed.
It's a cute trick, though.
<a href="http://www.catb.org/~esr/">Eric S. Raymond</a>
More information about the devel