Date: Sun, 7 Mar 2004 20:42:59 +0200 (EET) From: Narvi <narvi@haldjas.folklore.ee> To: Colin Percival <colin.percival@wadham.ox.ac.uk> Cc: freebsd-chat@freebsd.org Subject: Re: FreeBSD Most wanted Message-ID: <20040307202336.K68396@haldjas.folklore.ee> In-Reply-To: <6.0.1.1.1.20040306221435.03a97e20@imap.sfu.ca> References: <Pine.LNX.4.43.0403011839470.3269-100000@pilchuck.reedmedia.net> <20040306005744.T38020@haldjas.folklore.ee> <20040306013914.D38020@haldjas.folklore.ee> <6.0.1.1.1.20040306214526.08c5ed70@imap.sfu.ca> <20040306141742.4f41ba27.cpressey@catseye.mine.nu> <6.0.1.1.1.20040306221435.03a97e20@imap.sfu.ca>
next in thread | previous in thread | raw e-mail | index | archive | help
On Sat, 6 Mar 2004, Colin Percival wrote: > 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. :-) > Yes, but this is unlikely to be efficent in any but the rarest cases, and should the number be in some cases large, you get corner cases where your perfomance suddenly sucks for mysterious reasons. > 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. If you know the max number of elements, use an array of pointers + counter instead of list. scanning an array is much nicer than scanning a list - this is also the reson why you have to work hard to make say chained hash tables be as efficent as liner probing. > > >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. I think the problem is that they don't have a course on how to select data structures at all AFAICT. And I don't think this is a problem that is restricted to undergraduates either. > > 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?20040307202336.K68396>