From owner-freebsd-chat@FreeBSD.ORG Sun Mar 7 10:43:36 2004 Return-Path: Delivered-To: freebsd-chat@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 05AF816A4CE for ; Sun, 7 Mar 2004 10:43:36 -0800 (PST) Received: from haldjas.folklore.ee (Haldjas.folklore.ee [193.40.6.121]) by mx1.FreeBSD.org (Postfix) with ESMTP id 3CA4143D1F for ; Sun, 7 Mar 2004 10:43:35 -0800 (PST) (envelope-from narvi@haldjas.folklore.ee) Received: from haldjas.folklore.ee (localhost [127.0.0.1]) by haldjas.folklore.ee (8.12.10/8.12.10) with ESMTP id i27IgxUA069365; Sun, 7 Mar 2004 20:42:59 +0200 (EET) (envelope-from narvi@haldjas.folklore.ee) Received: from localhost (narvi@localhost)i27IgxMS069362; Sun, 7 Mar 2004 20:42:59 +0200 (EET) (envelope-from narvi@haldjas.folklore.ee) Date: Sun, 7 Mar 2004 20:42:59 +0200 (EET) From: Narvi To: Colin Percival In-Reply-To: <6.0.1.1.1.20040306221435.03a97e20@imap.sfu.ca> Message-ID: <20040307202336.K68396@haldjas.folklore.ee> References: <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> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Spam-Status: No, hits=0.0 required=8.0 tests=none autolearn=no version=2.63 X-Spam-Checker-Version: SpamAssassin 2.63 (2004-01-11) on haldjas.folklore.ee cc: Chris Pressey cc: freebsd-chat@freebsd.org Subject: Re: FreeBSD Most wanted X-BeenThere: freebsd-chat@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Non technical items related to the community List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 07 Mar 2004 18:43:36 -0000 On Sat, 6 Mar 2004, Colin Percival wrote: > At 22:17 06/03/2004, Chris Pressey wrote: > >Colin Percival 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. >