Re: master 724af76 2/2: Fix sxhash-equal on bytecodes, markers, etc.

Re: master 724af76 2/2: Fix sxhash-equal on bytecodes, markers, etc.

[Pip Cet]

On Tue, Jan 7, 2020 at 7:29 PM Paul Eggert <eggert@cs.ucla.edu> wrote:
> +       else if (pvec_type == PVEC_MARKER)
> +         {
> +           ptrdiff_t bytepos
> +             = XMARKER (obj)->buffer ? XMARKER (obj)->bytepos : 0;
> +           hash = sxhash_combine ((intptr_t) XMARKER (obj)->buffer, bytepos);
> +           hash = SXHASH_REDUCE (hash);
> +         }

Again, I don't think there's any reason for using markers as keys in
an equal-based hash table. But if you do, what you probably meant was
to use an eq-based hash table, and that used to work; now it doesn't.

(puthash marker value ht)
<...move marker...>
(gethash marker ht)

won't work.

Re: master 724af76 2/2: Fix sxhash-equal on bytecodes, markers, etc.

[Stefan Monnier]

> Again, I don't think there's any reason for using markers as keys in
> an equal-based hash table. But if you do, what you probably meant was
> to use an eq-based hash table, and that used to work; now it doesn't.
>
> (puthash marker value ht)
> <...move marker...>
> (gethash marker ht)

If it hurts don't do that: the same happens with

    (puthash conscell value ht)
    <...setcar conscell...>
    (gethash conscell ht)


-- Stefan

Re: master 724af76 2/2: Fix sxhash-equal on bytecodes, markers, etc.

[Paul Eggert]

On 1/7/20 11:36 AM, Pip Cet wrote:

> I don't think there's any reason for using markers as keys in
> an equal-based hash table. But if you do, what you probably meant was
> to use an eq-based hash table, and that used to work; now it doesn't.
> 
> (puthash marker value ht)
> <...move marker...>
> (gethash marker ht)
> 
> won't work.
> 

In what sense doesn't it work? The following code still works, anyway:

   (with-temp-buffer
     (insert "a")
     (let ((marker (point-marker))
           (ht (make-hash-table :test 'eq))
           (value 27))
       (puthash marker value ht)
       (set-marker marker 0)
       (gethash marker ht)))

It's true that if we change 'eq to 'equal in this example, gethash now 
returns nil where it used to return t. But that's the same thing that 
would happen if one modifies a string key in a equal-based hash table. 
So I don't see the problem.

Re: master 724af76 2/2: Fix sxhash-equal on bytecodes, markers, etc.

[Stefan Monnier]

>> Again, I don't think there's any reason for using markers as keys in
>> an equal-based hash table. But if you do, what you probably meant was
>> to use an eq-based hash table, and that used to work; now it doesn't.
>>
>> (puthash marker value ht)
>> <...move marker...>
>> (gethash marker ht)
>
> If it hurts don't do that: the same happens with
>
>     (puthash conscell value ht)
>     <...setcar conscell...>
>     (gethash conscell ht)

BTW, id we really wanted it, we could make that work as you expect by
making sxhash only return a value that does not depend on the properties
that can be modified (i.e. doesn't depend on the cons's car and car nor
the marker's current position), but it would lead to lots of objects
with equal hash, hence poor hashing performance.


        Stefan

Re: master 724af76 2/2: Fix sxhash-equal on bytecodes, markers, etc.

[Pip Cet]

On Tue, Jan 7, 2020 at 11:37 PM Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> >> Again, I don't think there's any reason for using markers as keys in
> >> an equal-based hash table. But if you do, what you probably meant was
> >> to use an eq-based hash table, and that used to work; now it doesn't.
> >>
> >> (puthash marker value ht)
> >> <...move marker...>
> >> (gethash marker ht)
> >
> > If it hurts don't do that: the same happens with

(It turns out I've already done it. Easy enough to fix in my code, but
then I'm aware of the change in behavior. Others might not be.)

Out of curiosity, though, how would you fix code that uses a cons cell
of two markers, say, as a hash key? I still think it'd be nice to have
an equality predicate which looks at lists but doesn't recurse into
them, but in the absence of it you'd have to use nested hash tables or
your own hash function, right? (My code used to do that, then switched
to a single overlay as hash key, but I forgot to change the hash table
predicate).

> >     (puthash conscell value ht)
> >     <...setcar conscell...>
> >     (gethash conscell ht)

I don't think of inserting text in a buffer "far away" from a marker
as modifying the marker. That's probably because I'm playing around
with some unfinished code which would put markers and buffer text in a
tree-like data structure and wouldn't actually modify the markers upon
insertion at all, but that's just an implementation detail.

> BTW, id we really wanted it, we could make that work as you expect by
> making sxhash only return a value that does not depend on the properties
> that can be modified (i.e. doesn't depend on the cons's car and car nor
> the marker's current position), but it would lead to lots of objects
> with equal hash, hence poor hashing performance.

I think for very volatile objects, such as markers, that's the best
course of action (they could still depend on the marker's buffer). For
explicitly-modified objects, I think the current behavior is something
we're going to have to live with, including some bugs when C code
assumes its hash keys can't change under it.

I personally would prefer not changing the behavior of sxhash/equal
more than necessary, and err on the side of caution. For markers and
overlays, we can just hash the buffer (if you have many markers or
overlays in a single buffer, you'll run into complexity issues
anyway), rather than breaking my badly-written real-world code.