ruricolist / cl-murmurhash Goto Github PK

As implemented, murmurhash will loop or recur infinitely if any type of circular data is encountered. For comparison, sxhash appears to detect circularity.

(let ((hashes))
    (dotimes (x 1000000)
      (push (cl-murmurhash:murmurhash (list :emp-no x)) hashes))
    
    (format t "Hashes created ~A~%" (length hashes))
    (setf hashes (remove-duplicates hashes))
    (format t "Hash duplicates removed ~A~%" (length hashes)))

Hashes created 1000000
Hash duplicates removed 999998

Is this to be expected or is it a bug?

CL-USER(7): (ql:quickload :cl-murmurhash)
To load "cl-murmurhash":
Load 1 ASDF system:
cl-murmurhash
; Loading "cl-murmurhash"
; in (DEFMACRO ~> ...)

; Caught STYLE-WARNING:
; ; Note: deleting unused local function FLET ENLIST
................................................
#<THREAD "interpreter" {51B1AA}>: Debugger invoked on condition of type STORAGE-CONDITION
Stack overflow.
Restarts:
0: RETRY Retry compiling #<ASDF/LISP-ACTION:CL-SOURCE-FILE "cl-murmurhash" "cl-murmurhash">.
1: ACCEPT Continue, treating compiling #<ASDF/LISP-ACTION:CL-SOURCE-FILE "cl-murmurhash" "cl-murmurhash"> as having been successful.
2: RETRY Retry ASDF operation.
3: CLEAR-CONFIGURATION-AND-RETRY Retry ASDF operation after resetting the configuration.
4: RETRY Retry ASDF operation.
5: CLEAR-CONFIGURATION-AND-RETRY Retry ASDF operation after resetting the configuration.
6: ABORT Give up on "cl-murmurhash"
7: TOP-LEVEL Return to top level.

(murmurhash 0.0) returns implementation-dependent value, because it uses integer-decode-float, which is allowed to return an arbitrary exponent for zero.
SBCL 1.4.16: (integer-decode-float 0d0) => 0 0 1
SBCL 1.4.15: (integer-decode-float 0d0) => 0 -1075 1

http://cl-test-grid.appspot.com/blob?key=6022aeohen

;;; Compiling (DEFUN SNARF-WORD ...).
;;; Error:
;;;   in file cl-murmurhash.lisp, position 6017
;;;   at (DEFUN SNARF-WORD ...)
;;;   * Syntax error in declaration ((INTEGER 0 4) I)

P.S. You can review build status of cl-murmurhash on various Lisps/OSes here:
http://common-lisp.net/project/cl-test-grid/library/cl-murmurhash.html
The tests are run for every quicklisp release.

The test sources refer to fiveam but the system definition does not explicitly depend on it.

Dependence on package-symbol for computing hashes throws an error for symbols with no package, e.g. '#:x . May not matter in practice. Clojure's jvm implementation in Util.java treats (hash nil) as 0.

Possible naive solution is to detect lack of package and return empty string or similar constant:

(defmethod murmurhash ((s symbol) &key (seed *default-seed*) mix-only)
  (let ((hash seed)
        (pkg (let ((p (symbol-package s)))
               (if p  (package-name p) "")))
        (sym (symbol-name s)))
    (mixf hash pkg)
    (mixf hash sym)
    (if mix-only
        hash
        (finalize hash (+ (length pkg) (length sym))))))

Unsure if this has broader implications (e.g. toward distribution of hashes), but it seems plausible to this layman.

Proposed diff attached (github doesn't support diff format...):
patch.diff.txt

With this implemented, we get:

MURMURHASH> (murmurhash '#:x)
4207307701
MURMURHASH> (murmurhash 'x)
1349100184

Thanks for providing this library.

Here's one example of a full warning that's busting the build process:

; file: /home/xach/quicklisp-controller/dist/build-cache/cl-murmurhash/ac38dbf682aeb73298f963868d6482b727266376/cl-murmurhash-20130111-git/cl-murmurhash.lisp
; in: DEFUN MIX/128
;     (CL-MURMURHASH::SEED CL-MURMURHASH::H1 CL-MURMURHASH::H2 CL-MURMURHASH::H3
;      CL-MURMURHASH::H4 CL-MURMURHASH::SEED)
; --> BLOCK LABELS ETYPECASE LET COND IF PROGN CL-MURMURHASH::RET 
; ==>
;   (CL-MURMURHASH::SEED (CL-MURMURHASH::MAKE-SEED))
; 
; caught WARNING:
;   The function was called with one argument, but wants at least four.

More of the log available at http://report.quicklisp.org/cl-murmurhash/2013-01-11/failtail.txt

Please add test cases so one can ensure the hashing is correct and done to spec. That way one can ensure it works across multiple implementations.

New version of cl-murmurhash depends on fast-io, which depends on static-vectors, which is not portable. In result cl-murmurhash now builds only with a subset of lisps.