From owner-freebsd-chat@FreeBSD.ORG Sat Mar 6 15:50:14 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 256D816A4D2 for ; Sat, 6 Mar 2004 15:50:14 -0800 (PST) Received: from priv-edtnes12-hme0.telusplanet.net (outbound03.telus.net [199.185.220.222]) by mx1.FreeBSD.org (Postfix) with ESMTP id C181843D1D for ; Sat, 6 Mar 2004 15:50:13 -0800 (PST) (envelope-from cpressey@catseye.mine.nu) Received: from catseye.biscuit.boo ([154.5.85.228]) by priv-edtnes12-hme0.telusplanet.netSMTP <20040306235013.HPYG3453.priv-edtnes12-hme0.telusplanet.net@catseye.biscuit.boo>; Sat, 6 Mar 2004 16:50:13 -0700 Date: Sat, 6 Mar 2004 15:55:13 -0800 From: Chris Pressey To: Colin Percival Message-Id: <20040306155513.6a75e264.cpressey@catseye.mine.nu> In-Reply-To: <6.0.1.1.1.20040306221435.03a97e20@imap.sfu.ca> 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> <6.0.1.1.1.20040306221435.03a97e20@imap.sfu.ca> Organization: Cat's Eye Technologies X-Mailer: Sylpheed version 0.9.9 (GTK+ 1.2.10; i386-portbld-freebsd4.9) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit 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 23:50:14 -0000 On Sat, 06 Mar 2004 22:31:14 +0000 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. > :-) > > 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. Ah, yes, that's a good point. Modern high-level languages do tend to just give you these things on the strictly black-box ADT level, like dictionaries... and with all the guts abstracted away, programmers do tend to let themselves get a bit carried away. It Does What I Want, it Must Be What I Need. And, yeah. A hash table is really nothing by itself. It's just a way of taking a long list (or other structure) and splitting it up into N smaller structures. If your lists are never that long in the first place, there's no point. > >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?) If I am, rest assured it's only for my own entertainment. > Of course, part of the problem is that most undergraduate courses > still teach the myth that random access memory is, err, random access. :-) -Chris