ntpq quirk

[Eric S. Raymond]

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>