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

Am 09.02.10 02:47, schrieb Donal K. Fellows:
> On 08/02/2010 18:45, Eric Melski wrote:>> That's very impressive, but with only three hash entries you can hardly>> say that's a representative test case.
...
> FWIW, with a focussed test that *just* does comparison of the hashing> speed (see attached; the contents of the two hashing functions were> copied directly from HashStringKey in Tcl 8.5 and the HEAD) we find that> on x86 the old algorithm is indeed faster. 
indeed,  the attached program shows me that the hashing speed of the
old function is constantly faster than FNV (when compiled with
-Os like Tcl, intel mac, 64bit, 10.6.2).

old: 2137177 us    (1517306493d)
new: 2296518 us    (3684793705d)

(i just added an outer loop with 500 iterations to obtain more
precise timings). By using the function in tcl 8.5.7 for HashStringKey(),
i could not get the 15% speedup, but i see a rather larger slowdown
for the first test.

proc foo {} {set x(foobar) [set x(barfoo) [set x(ballyhoo) 1]];return}
puts [time {time { foo } 10000} 1000]
proc foo {} {set x [set y [set z 1]]; return}
puts [time {time { foo } 10000} 1000]

# classic
# 9105.318082 microseconds per iteration
# 4686.419043 microseconds per iteration

# fnv
# 9367.280143 microseconds per iteration
# 4684.1961710000005 microseconds per iteration

Btw, the old function could be made slightly faster by avoiding one
incr operation

     for (c = *string ; c ; c = *++string) {
         result += (result<<3) + c;
     }

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.

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

-gn


------------------------------------------------------------------------------
The Planet: dedicated and managed hosting, cloud storage, colocation
Stay online with enterprise data centers and the best network in the business
Choose flexible plans and management services without long-term contracts
Personal 24x7 support from experience hosting pros just a phone call away.
http://p.sf.net/sfu/theplanet-com
_______________________________________________
Tcl-Core mailing list
Tcl-...@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/tcl-core