Error formatting macro: pagetree: java.lang.NullPointerException

Better hashing

You are viewing an old version of this page. View the current version.

Problem

Clojure’s hashing strategy for numbers, sequences/vectors, sets, and maps mimics Java’s.  In Clojure, however, it is far more common than in Java to use longs, vectors, sets, maps and compound objects comprised of those components (e.g., a map from vectors of longs to sets) as keys in other hash maps.  It appears that Java’s hash strategy is not well-tuned for this kind of usage.  Clojure’s hashing for longs, vectors, sets, and maps each suffer from some weaknesses that can multiply together to create a crippling number of collisions.

For example, Paul Butcher wrote a simple Clojure program that produces a set of solutions to a chess problem.  Each solution in the set was itself a set of vectors of the form [piece-keyword [row-int col-int]].  Clojure 1.5.1's current hash function hashed about 20 million different solutions to about 20 thousand different hash values, for an average of about 1000 solutions per unique hash value.  This causes PersistentHashSet and PersistentHashMap to use long linear searches for testing set/map membership or adding new elements/keys.  There is nothing intentionally pathological about these values – they simply happened to expose this behavior in a dramatic way.  Others have come across similarly bad performance without any obvious reason why, but some of those cases are likely due to this same root cause.

Proposed solutions

Mark Engelberg's document about Clojure's hash function, its behavior, and potential improvements, is here:

A summary of his proposed hash function modifications is:

• Change the hash of integers that fit within a long to the return value of longHashMunge (see Longs section of doc for more details)
• Change the current multiplier of 31 used for vectors, sequences, and queues to a different constant such as -1640531527 or 524287 (see Vectors section).  Also applies to Cons, LazySeq.
• For sets, instead of adding together the hash value of the elements, add together the return value of a function xorShift32 called on the hash value of each element (see Sets section)
• For maps and records, instead of adding together hash(key) ^ hash(val) for each hash,val pair, instead add together hash(key)^xorShift32(hash(val)) (see Maps section)
• No change for any other types, e.g. strings, keywords, symbols, floats, doubles, BigInt's outside of long range, BigDecimal, etc.

Below is a link to a modified version of Paul Butcher's N-queens solver, with extra code for printing stats with several different hash functions.  The README has instructions for retrieving and installing locally a version of Clojure modified with one of Mark's proposed alternate hash functions.  After that is a link to a patch that implements the proposal above.

Here is a summary of results for some program elapsed times and how spread out the hash values are.  Below the table are a few details on how these measurements were made.

Problem

Using Clojure 1.6.0-alpha3 hash (same as Clojure 1.5.1)

Using Mark Engelberg's 2013-11-18 proposed hash
Paul Butcher's N-queens problem with 6x6 board

Elapsed time: 6.7 min (~33 times slower than with 2013-11-18 proposed hash)

180,568 solutions hash to 3,013 distinct hash values

average of 59.9 solutions per hash value (max 2,492)

Elapsed time: 12.2 sec

180,568 solution hash to 180,566 distinct hash values

average of 1.0 solutions per hash value (max 2)

with 6x9 board

Elapsed time: > 8 hours (did not wait for it to finish)

20,136,752 solutions hash to 17,936 distinct hash values

average of 1,122.7 solutions per hash value (max 81,610)

Elapsed time: 11.4 min

20,136,752 solutions hash to 20,089,766 distinct hash values

average of 1.0 solutions per hash value (max 4)

Compile Clojure 1.6.0-alpha3 source with "ant jar", so no tests run

Elapsed time: avg 20.1 sec

(min 19.6, max 20.9)

raw measurements: 19.6, 20.2, 20.9, 19.8, 19.8

Elapsed time: avg 20.0 sec

(min 19.6, max 20.7)

raw measurements: 19.9, 20.2, 19.6, 20.7, 19.7

Compile Clojure 1.6.0-alpha3 source with "ant", which includes running tests, but with generative test duration reduced to 1.0 sec

Elapsed time: avg 48.0 sec

(min 47.3, max 49.5)

raw measurements: 47.6, 49.5, 47.3, 47.4, 48.3

120,353 unique values hash to 113,405 distinct hash values

average of 1.06 values per hash value

Elapsed time: avg 48.0 sec

(min 47.1, max 49.5)

raw measurements: 47.1, 48.2, 47.6, 47.7, 49.5

119,811 unique values hash to 114,329 distinct hash values

average of 1.05 values per hash value

Calc hashes of all integers in (range 100000000) and return sum, using:

(time (hash-of-range 100000000))

See here for definition of hash-of-range

time: avg 3.35 sec

(min 3.31, max 3.39)

time: avg 3.76 sec (12.4% longer)

(min 3.40, max 3.91)

Calc hashes of all vectors [] [0] [0 1], etc. up to [0 1 ... 19999] and return sum, using

(let [cs (doall (reductions conj [] (range 20000)))]

(time (total-hash cs)))

See here for definition of total-hash

time: avg 7.08 sec

(min 6.94, max 7.19)

time: avg 7.32 sec (3.4% longer)

(min 7.27, max 7.36)

Calc hashes of all sets #{} #{0} #{0 1}, etc. up to #{0 1 ... 19999} and return sum, using

(let [cs (doall (reductions conj #{} (range 20000)))]

(time (total-hash cs)))

time: avg 22.11 sec

(min 17.51, max 23.72)

time: avg 22.99 sec (4.0% longer)

(min 22.58, max 23.50)

Calc hashes of all maps {} {0 1} {0 1, 1 2} ... up to {0 1, 1 2, ..., 19999 20000} and return sum, using

(let [cs (doall (reductions (fn [m i] (assoc m i (inc i))) {} (range 20000)))]

(time (total-hash cs)))

time: avg 26.39 sec

(min 24.18, max 28.42)

time: avg 29.77 sec (12.8% longer)

(min 23.33, max 31.59)

Open questions

Possible small changes to the proposal for consideration:

• Add in some magic constant to the hash of all sets and maps (a different constant for sets than for maps), so that the empty set and empty map have non-0 hash values, and thus nested data structures like #{{}} and {#{} #{}} will hash to non-0 values that are different from each other.
• Consider doing something besides the current hash(numerator) ^ hash(denominator) for Ratio values.  Perhaps hash(numerator) + xorShift32(hash(denominator)) ?  That would avoid the hash of 3/7 and 7/3 being the same, and also avoid the current behavior that hash(3/7) "undoes" the longHashMunge proposed for both the numerator and denominator long values.