GNU bug report logs - #56255
28.1.50; sxhash-equal does not change when object is modified

Previous Next

Full log

View this message in rfc822 format

From: Ihor Radchenko <yantar92 <at> gmail.com>
To: Lars Ingebrigtsen <larsi <at> gnus.org>
Cc: 56255 <at> debbugs.gnu.org
Subject: bug#56255: 28.1.50; sxhash-equal does not change when object is modified
Date: Wed, 29 Jun 2022 20:56:31 +0800

Lars Ingebrigtsen <larsi <at> gnus.org> writes:

> Ihor Radchenko <yantar92 <at> gmail.com> writes:
>
>> The original idea was to detect changed objects in most generic way, as
>> a part of persistent storage library. Oh well.
>
> We could make SXHASH_MAX_DEPTH into a defvar -- or pass the depth in to
> `sxhash-equal'.  However, the hash it's computing is geared towards hash
> tables, so collisions are OK -- it's not a cryptographic hash, so I'm
> not sure it would fit your use case anyway.  I.e., our sxhash_combine is
> very simple.

Well. In my scenario, the object structure creates so bad case that
_all_ the hashes for _all possible_ avl-tree structures collide
(actually, I use plists containing avl-tree structures).

As for the hash tables and collisions. Are you sure that collisions are
OK? Consider the following example:

(setq a (avl-tree--create #'org-element--cache-compare))
(avl-tree-enter a '(headline (:begin 2)))
(setq tbl (make-hash-table :test #'equal))
(puthash a 'value tbl)
(gethash a tbl)
(plist-put (nth 1 (avl-tree-first a)) :begin 10)
(gethash a tbl) ;; the value does not change!

Best,
Ihor

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.