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: |
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 (1)
comment:1 Changed 8 years ago by gb
- Resolution set to fixed
- Status changed from new to closed
Note: See
TracTickets for help on using
tickets.
(In [15459]) %%EQUALHASH processes final CDR.
Fixes ticket:1011 in trunk.