FreeBSD Most wanted

[Colin Percival]

At 22:17 06/03/2004, Chris Pressey wrote:
>Colin Percival <colin.percival at wadham.ox.ac.uk> wrote:
> > Nobody
> > quite understands why hash tables are not a perfect data structure
> > until they've tried to implement one in assembly language.  (And,
> > after performing such a task, few people will use hash tables without
> > asking themselves, at least for a moment, if there might be a cheaper
> > solution to the problem at hand.)
>
>Not sure what you mean here... surely it's no easier to implement (say)
>an AVL tree or a red-black tree in assembly?

   Perhaps not, but it's much easier to implement an unsorted list. :-)

   I've often seen people using hash tables to keep track of very small
numbers of objects, where a simple sequential scan will be much faster
than a hash table lookup; I also see people using hash tables for data
where the keys rarely, if ever, change.

>In fact, I'd think a hash function would often be a good candidate for
>hand-coded assembly - if you want to play "Beat the Compiler" :)

   Quite likely, yes[0].  But the act of writing usually makes people
realize just how much work the processor does every time a hashlookup()
call is made.  The amount of work the programmer does isn't really
important.  (You're not planning on assembly-coding a hash table more
than once, are you?)

   Of course, part of the problem is that most undergraduate courses
still teach the myth that random access memory is, err, random access.

Colin Percival
[0] With the exception of cryptographic hash functions, which tend to
be constructed in such a way that any half-decent compiler will output
exactly the same code as a human would.