What's the specification for sxhash?

[Philippe Schnoebelen]

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

sxhash-report.el
Description: Text document