What's the specification for sxhash?

[Philippe Schnoebelen <schnoebelen.ph@gmail.com>]

[-- Attachment #1.1: Type: text/plain, Size: 3488 bytes --]

Some of my elisp code broke down when I ran it on a newer emacs because
the values returned by sxhash are different from what they were in the
old version.

I had assumed without thinking that sxhash'es of Lisp objects were fixed
one and for all, a bit like the shasum of some file.

Probably the doc string should be more explicit about what is/is not
guaranteed. Is consistency only guaranteed inside the current running
emacs thread/process?


Looking at the source code in src/fns.c, it seems that the change of
sxhash values was caused by the recent change allowing emacs lisp
integers of arbitrary size. These numbers are hashed differently, and
hashing itself has to truncate large integers that are now a different
data type. (However, I have also found changes in sxhash values between
v26.1 and v26.2, before the move to arbitrary large integers in v27, see
examples below.)

Looking at the source code, one would think that sxhash values are meant
to only depend on the structure of the Lisp object itself, not the
hardware or the emacs version, but of course this view may have to yield
when the C data type for Lisp objects is modified. Is this what the
developers had in mind?


Today the elisp manual reads

— Function: *sxhash-equal*obj

    This function returns a hash code for Lisp object obj. This is an
    integer which reflects the contents of obj and the other Lisp
    objects it points to.

    If two objects obj1 and obj2 are |equal|, then |(sxhash-equal
    |obj1|)| and |(sxhash-equal |obj2|)| are the same integer.

    If the two objects are not |equal|, the values returned by
    |sxhash-equal| are usually different, but not always; once in a rare
    while, by luck, you will encounter two distinct-looking objects that
    give the same result from |sxhash-equal|.

This does not address the consistency issue, and is a bit misleading
about collisions with its "once in a rare while, by luck".  Without
trying, I stumbled upon many collisions in my test. Is sxhash really
intended to avoid collisions?

Many thanks for your time,

--philippe


Here is what I obtained by running emacs -Q --batch -l  sxhash-report.el
(.el file attached below) on 3 different versions of emacs:

in GNU Emacs 26.1 (build 1, x86_64-apple-darwin18.6.0, NS appkit-1671.50
Version 10.14.5 (Build 18F132))
 of 2019-05-28
1 is hash for 1
0 is hash for 0
0 is hash for nil
11484 is hash for t
0 is hash for (0 . 0)
0 is hash for ""
2030 is hash for "ab"
517809 is hash for "abcd"
93076 is hash for (1 2 3 4 5)
1608904915 is hash for (a b c)
5457926 is hash for ab
5457938 is hash for abcd
5457950 is hash for :misc

in GNU Emacs 26.2 (build 1, x86_64-apple-darwin18.2.0, NS appkit-1671.20
Version 10.14.3 (Build 18D109))
 of 2019-04-13
1 is hash for 1
0 is hash for 0
0 is hash for nil
11616 is hash for t
0 is hash for (0 . 0)
0 is hash for ""
2030 is hash for "ab"
517809 is hash for "abcd"
93076 is hash for (1 2 3 4 5)
6307170282 is hash for (a b c)
10938216 is hash for ab
10938228 is hash for abcd
10938240 is hash for :misc

in GNU Emacs 27.0.50 (build 1, x86_64-apple-darwin18.6.0, NS
appkit-1671.50 Version 10.14.5 (Build 18F132))
 of 2019-06-06
1 is hash for 1
0 is hash for 0
0 is hash for nil
11784 is hash for t
0 is hash for (0 . 0)
0 is hash for ""
2030 is hash for "ab"
517809 is hash for "abcd"
93076 is hash for (1 2 3 4 5)
238969789 is hash for (a b c)
35167434275996 is hash for ab
35167434276008 is hash for abcd
35167434276020 is hash for :misc



[-- Attachment #1.2: Type: text/html, Size: 4791 bytes --]

[-- Attachment #2: sxhash-report.el --]
[-- Type: text/plain, Size: 317 bytes --]

;;;; File: sxhash-report.el -*- lexical-binding: t; -*-

(defvar some-lisp-objects
  (list 1 0 nil t 
	(cons 0 0)
	"" "ab" "abcd"
	'(1 2 3 4 5)  '(a b c)
	'ab 'abcd :misc
	))


(princ (format "in %s\n" (emacs-version)))
(dolist (obj some-lisp-objects)
  (princ (format "%S is hash for %S\n" (sxhash-equal obj) obj)))