From owner-freebsd-chat@FreeBSD.ORG Sat Mar 6 14:31:22 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 40F0316A4CF for ; Sat, 6 Mar 2004 14:31:22 -0800 (PST) Received: from tx0.oucs.ox.ac.uk (tx0.oucs.ox.ac.uk [129.67.1.163]) by mx1.FreeBSD.org (Postfix) with ESMTP id E138643D39 for ; Sat, 6 Mar 2004 14:31:21 -0800 (PST) (envelope-from colin.percival@wadham.ox.ac.uk) Received: from scan0.oucs.ox.ac.uk ([129.67.1.162] helo=localhost) by tx0.oucs.ox.ac.uk with esmtp (Exim 4.24) id 1AzkKG-0008Ec-Fi for freebsd-chat@freebsd.org; Sat, 06 Mar 2004 22:31:20 +0000 Received: from rx0.oucs.ox.ac.uk ([129.67.1.161]) by localhost (scan0.oucs.ox.ac.uk [129.67.1.162]) (amavisd-new, port 25) with ESMTP id 31531-02 for ; Sat, 6 Mar 2004 22:31:20 +0000 (GMT) Received: from gateway.wadham.ox.ac.uk ([163.1.161.253]) by rx0.oucs.ox.ac.uk with smtp (Exim 4.24) id 1AzkKC-0008EE-2b for freebsd-chat@freebsd.org; Sat, 06 Mar 2004 22:31:16 +0000 Received: (qmail 21898 invoked by uid 1004); 6 Mar 2004 22:31:16 -0000 Received: from colin.percival@wadham.ox.ac.uk by gateway by uid 71 with qmail-scanner-1.20 (clamscan: 0.67. sweep: 2.18/3.79. Clear:RC:1(163.1.161.131):. Processed in 0.57497 secs); 06 Mar 2004 22:31:16 -0000 Received: from dhcp1131.wadham.ox.ac.uk (HELO piii600.wadham.ox.ac.uk) (163.1.161.131) by gateway.wadham.ox.ac.uk with SMTP; 6 Mar 2004 22:31:16 -0000 Message-Id: <6.0.1.1.1.20040306221435.03a97e20@imap.sfu.ca> X-Sender: cperciva@imap.sfu.ca (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 6.0.1.1 Date: Sat, 06 Mar 2004 22:31:14 +0000 To: Chris Pressey From: Colin Percival In-Reply-To: <20040306141742.4f41ba27.cpressey@catseye.mine.nu> References: <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> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed 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: Sat, 06 Mar 2004 22:31:22 -0000 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. :-) 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.