Loading ...
Sorry, an error occurred while loading the content.
 

Re: Secondary Hash Values Considered Harmful

Expand Messages
  • Shlomi Fish
    ... [snipped] ... 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
    Message 1 of 2 , Apr 25, 2009
      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.
    Your message has been successfully submitted and would be delivered to recipients shortly.