Opened 8 years ago

Closed 8 years ago

#1011 closed defect (fixed)

Inefficient hash table -- bad hashing

Reported by: dfindlay Owned by:
Priority: normal Milestone:
Component: Performance Version: trunk
Keywords: Cc:


I built a hash table with keys that were simple cons cells of the form

(<type> . <item>)

I had a few <type>s, and lots of atomic <item>s (in particular, strings) for each <type>. The performance was very bad.

Investigation showed that ccl::compute-hash-code was returning a hash code that depended only on the <type> but not on the <item>, meaning that hash table look up was degenerating into a linear search.


(setq h (make-hash-table :test #'equal))


(ccl::compute-hash-code h '(type . "foo") nil)
(ccl::compute-hash-code h '(type . "bar") nil)
(ccl::compute-hash-code h '(type . "baz") nil)
(ccl::compute-hash-code h '(type . pi) nil)
(ccl::compute-hash-code h '(type . nil) nil)

all return exactly the same results.

Change History (1)

comment:1 Changed 8 years ago by gb

  • Resolution set to fixed
  • Status changed from new to closed

(In [15459]) %%EQUALHASH processes final CDR.

Fixes ticket:1011 in trunk.

Note: See TracTickets for help on using tickets.