diff options
| author | dkf <donal.k.fellows@manchester.ac.uk> | 2010-02-07 09:10:32 (GMT) |
|---|---|---|
| committer | dkf <donal.k.fellows@manchester.ac.uk> | 2010-02-07 09:10:32 (GMT) |
| commit | baafc87e3c7fe20ed29437a7e7b44f9f06f4e974 (patch) | |
| tree | d772606db0a33eea164149ef48f66190338f8673 /ChangeLog | |
| parent | 307233f5f049dea251e0d858e301565c0ed88117 (diff) | |
| download | tcl-baafc87e3c7fe20ed29437a7e7b44f9f06f4e974.zip tcl-baafc87e3c7fe20ed29437a7e7b44f9f06f4e974.tar.gz tcl-baafc87e3c7fe20ed29437a7e7b44f9f06f4e974.tar.bz2 | |
Upgrade Tcl's hash function to use the FNV-32 algorithm. This is marginally
faster and gives a bit better distribution of keys (especially in large hash
tables) but does change hash iteration order.
Diffstat (limited to 'ChangeLog')
| -rw-r--r-- | ChangeLog | 17 |
1 files changed, 17 insertions, 0 deletions
@@ -1,3 +1,20 @@ +2010-02-06 Donal K. Fellows <dkf@users.sf.net> + + * generic/tclHash.c (HashStringKey): Replace Tcl's crusty old hash + * generic/tclObj.c (TclHashObjKey): function with the algorithm + due to Fowler, Noll and Vo. This is slightly faster (assuming the + presence of hardware multiply) and has somewhat better distribution + properties of the resulting hash values. Note that we only ever used + the 32-bit version of the FNV algorithm; Tcl's core hash engine + assumes that hash values are simple unsigned ints. + + ***POTENTIAL INCOMPATIBILITY*** + Code that depends on hash iteration order (especially tests) may well + be disrupted by this. Where a definite order is required, the fix is + usually to just sort the results after extracting them from the hash. + Where this is insufficient, the code that has ceased working was + always wrong and was only working by chance. + 2010-02-05 Donal K. Fellows <dkf@users.sf.net> * generic/tclCompCmds.c (TclCompileErrorCmd): Added compilation of the |