On Friday 24 April 2009 00:52:21 Shlomi Fish wrote:
> The Freecell Solver's internal hash (which lives in fcs_hash.c and
> fcs_hash.h) has gone through several modifications and tweaks in its
> history. At one time, I replaced Perl's hash function with the one from
> http://burtleburtle.net/bob/ , but then decided to also store the two hash
> values (generated by the old and new hash functions) next to the actual
> item, so one can compare them. So naturally, I had to run the two hash
> functions in order to computer the two distinct hash values for each
> element that I'd like to insert.
[snipped]
>
> These are huge gains for so little effort. I'm quite surprised they were so
> substantial. It seems that a lot of time was unnecessarily spent dealing
> with the secondary hash. I have a few other hash details in mind that I'd
> like to benchmark and see which one is better.
Next I covered the optimize_for_caching run-time flag of the hash. What it
does is promote entries that were found to the beginning of the chain in the
hash table. Eliminating it (first in run-time, then in compile-time) also
turned out to have a positive effect on the solver's speed, but this time
relatively small. Still - we saved a second or two.
I haven't made the no-secondary-hash option the default yet, but I plan to.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Understand what Open Source is - http://xrl.us/bjn82
God gave us two eyes and ten fingers so we will type five times as much as we
read.
Received on Sat Apr 25 2009 - 07:21:32 IDT