From: Florian Weimer <fw@de...>  20030309 18:13:28

I've stumbled across a phenomenon I can't explain. While EQ hash tables scale almost linearly in terms of hash tables size, EQUAL hash tables do not. Compile and load the following test code: ;  (evalwhen (:compiletoplevel :loadtoplevel) (let ((currentbitvector #32*00000000000000000000000001)) (defun makebitvector () (declare (values simplebitvector) (optimize (speed 3))) (loop for j from 0 do (cond ((= (sbit currentbitvector j) 0) (setf (sbit currentbitvector j) 1) (returnfrom makebitvector (copyseq currentbitvector))) (t (setf (sbit currentbitvector j) 0))))) (defun resetbitvector () (setq currentbitvector #32*00000000000000000000000001)))) (defun testeq (n) (let ((table (makehashtable))) (resetbitvector) (time (loop for j from 1 to n do (setf (gethash (makebitvector) table) 0))))) (defun testequal (n) (let ((table (makehashtable :test 'equal))) (resetbitvector) (time (loop for j from 1 to n do (setf (gethash (makebitvector) table) 0))))) ;  Now look at the following results. The first ones are not too bad. * (testeq 10000) Evaluation took: 0.065 seconds of real time 0.07 seconds of user run time 0.0 seconds of system run time 0 page faults and 874440 bytes consed. NIL * (testequal 10000) Evaluation took: 3.269 seconds of real time 3.27 seconds of user run time 0.0 seconds of system run time [Run times include 0.02 seconds GC run time.] 725 page faults and 890824 bytes consed. NIL Now let's add another 0: * (testeq 100000) Evaluation took: 0.764 seconds of real time 0.76 seconds of user run time 0.01 seconds of system run time [Run times include 0.07 seconds GC run time.] 0 page faults and 9667440 bytes consed. NIL The same call to testequal does not terminate within a couple of minutes. How can I debug this problem? Is there some way to count collisions? Maybe it's just the hash function that's extraordinarily bad... 