Date: Sat, 06 Mar 2004 22:31:14 +0000 From: Colin Percival <colin.percival@wadham.ox.ac.uk> To: Chris Pressey <cpressey@catseye.mine.nu> Cc: freebsd-chat@freebsd.org Subject: Re: FreeBSD Most wanted Message-ID: <6.0.1.1.1.20040306221435.03a97e20@imap.sfu.ca> In-Reply-To: <20040306141742.4f41ba27.cpressey@catseye.mine.nu> References: <Pine.LNX.4.43.0403011839470.3269-100000@pilchuck.reedmedia.net> <EABDE846-6EF2-11D8-AE09-000A95DA58FE@jimz.net> <20040306005744.T38020@haldjas.folklore.ee> <20040305153505.74061868.cpressey@catseye.mine.nu> <20040306013914.D38020@haldjas.folklore.ee> <404A465A.1040009@stephanmantler.com> <6.0.1.1.1.20040306214526.08c5ed70@imap.sfu.ca> <20040306141742.4f41ba27.cpressey@catseye.mine.nu>
next in thread | previous in thread | raw e-mail | index | archive | help
At 22:17 06/03/2004, Chris Pressey wrote: >Colin Percival <colin.percival@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.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?6.0.1.1.1.20040306221435.03a97e20>