Ticket #1011 (closed defect: fixed)

Opened 20 months ago

Last modified 20 months ago

Inefficient hash table -- bad hashing

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

Description

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.

Example:

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

Then

(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

comment:1 Changed 20 months ago by gb

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

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

Fixes ticket:1011 in trunk.

Note: See TracTickets for help on using tickets.