Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

On 09/02/2010 16:15, Gustaf Neumann wrote:
> The output of Donal showing the buckets indicates certainly> that FNV leads to less collisions. However, since from my experience,> we have in tcl many hash tables with only a few items.> I would not be surprised if most programs run rather slower> with FNV than with the old tcl hash function.

It depends critically on the operation mix, what keys are being used,
etc., and it's hard to test in situ because it's typically used in
conjunction with other (much more expensive) operations like memory
allocation. Given that, keeping bucket chains short is probably the best
metric of all.

For truly small tables, a Lisp-style alist would actually be cheaper.
Not that they scale...

> maybe, some handcoded inline assembly could speed up the function.

Maybe, but then we'd have to maintain it on all our supported platforms.
:-( The only time we've ever used assembly in Tcl's implementation was
because there was *no* other way to do it (and was for dealing with
particularly odd parts of Windows on x86 only).

Donal.

begin:vcard
fn:Donal K. Fellows
n:Fellows;Donal
org:The University of Manchester;Research Computing Services
adr:;;Oxford Road;Manchester;;M13 9PL;United Kingdom
email;internet:dona...@manchester.ac.uk
version:2.1
end:vcard

------------------------------------------------------------------------------
SOLARIS 10 is the OS for Data Centers - provides features such as DTrace,
Predictive Self Healing and Award Winning ZFS. Get Solaris 10 NOW
http://p.sf.net/sfu/solaris-dev2dev