maphash

maphash

[Helmut Eller]

The documentation states that puthash and remhash are only "allowed" to
use the current key while a maphash is in progress.  (Interestingly, it
says nothing about gethash.)

However, the code in comp.el uses puthash with other keys.  E.g
comp--add-cond-cstrs-simple iterates over a hashtable of basic blocks
and while the iteration is in progress, it calls
comp--add-cond-cstrs-target-block which puts new basic blocks into the
hashtable.

(With the current implementation, inserting may rehash the table which
can cause maphash to "skip" some entries or visit some entries twice.)

Should the hashtable implementation detect such situations and perhaps
signal an error or a warning?

Re: maphash

[Mattias Engdegård]

10 sep. 2024 kl. 17.52 skrev Helmut Eller <eller.helmut@gmail.com>:

> The documentation states that puthash and remhash are only "allowed" to
> use the current key while a maphash is in progress.  (Interestingly, it
> says nothing about gethash.)

That is correct. The purpose of these rules is to avoid us being shackled to a specific behaviour if a user breaks them; we don't want any more implementation restrictions than necessary.

We still protect Lisp abstractions so the user shouldn't fear segfaults, but there are no promises when it comes to the iteration order, whether iteration will encounter added elements, the same element twice or some none at all, etc.

> However, the code in comp.el uses puthash with other keys.  E.g
> comp--add-cond-cstrs-simple iterates over a hashtable of basic blocks
> and while the iteration is in progress, it calls
> comp--add-cond-cstrs-target-block which puts new basic blocks into the
> hashtable.

This sounds like a bug in nativecomp then, even if it happens not to have any bad consequences right now.

> Should the hashtable implementation detect such situations and perhaps
> signal an error or a warning?

Not unless it can be done at basically no cost. This is not a very common mistake and letting all correct code pay for it wouldn't be a good trade-off.

Re: maphash

[Andrea Corallo]

Mattias Engdegård <mattias.engdegard@gmail.com> writes:

> 10 sep. 2024 kl. 17.52 skrev Helmut Eller <eller.helmut@gmail.com>:
>
>> The documentation states that puthash and remhash are only "allowed" to
>> use the current key while a maphash is in progress.  (Interestingly, it
>> says nothing about gethash.)
>
> That is correct. The purpose of these rules is to avoid us being shackled to a specific behaviour if a user breaks them; we don't want any more implementation restrictions than necessary.
>
> We still protect Lisp abstractions so the user shouldn't fear
> segfaults, but there are no promises when it comes to the iteration
> order, whether iteration will encounter added elements, the same
> element twice or some none at all, etc.
>
>> However, the code in comp.el uses puthash with other keys.  E.g
>> comp--add-cond-cstrs-simple iterates over a hashtable of basic blocks
>> and while the iteration is in progress, it calls
>> comp--add-cond-cstrs-target-block which puts new basic blocks into the
>> hashtable.
>
> This sounds like a bug in nativecomp then, even if it happens not to have any bad consequences right now.

Ops! Will look at thanks

  Andrea

Re: maphash

[Eli Zaretskii]

Ping!  Andrea, did you have time to look at this?

> From: Andrea Corallo <acorallo@gnu.org>
> Cc: Helmut Eller <eller.helmut@gmail.com>,  emacs-devel@gnu.org
> Date: Wed, 11 Sep 2024 18:45:16 -0400
> 
> Mattias Engdegård <mattias.engdegard@gmail.com> writes:
> 
> > 10 sep. 2024 kl. 17.52 skrev Helmut Eller <eller.helmut@gmail.com>:
> >
> >> The documentation states that puthash and remhash are only "allowed" to
> >> use the current key while a maphash is in progress.  (Interestingly, it
> >> says nothing about gethash.)
> >
> > That is correct. The purpose of these rules is to avoid us being shackled to a specific behaviour if a user breaks them; we don't want any more implementation restrictions than necessary.
> >
> > We still protect Lisp abstractions so the user shouldn't fear
> > segfaults, but there are no promises when it comes to the iteration
> > order, whether iteration will encounter added elements, the same
> > element twice or some none at all, etc.
> >
> >> However, the code in comp.el uses puthash with other keys.  E.g
> >> comp--add-cond-cstrs-simple iterates over a hashtable of basic blocks
> >> and while the iteration is in progress, it calls
> >> comp--add-cond-cstrs-target-block which puts new basic blocks into the
> >> hashtable.
> >
> > This sounds like a bug in nativecomp then, even if it happens not to have any bad consequences right now.
> 
> Ops! Will look at thanks
> 
>   Andrea
> 
> 

Re: maphash

[Andrea Corallo]

Eli Zaretskii <eliz@gnu.org> writes:

> Ping!  Andrea, did you have time to look at this?

No sorry, hope this week to have time to tackle my todolist.

  Andrea

Re: maphash

[Andrea Corallo]

Andrea Corallo <acorallo@gnu.org> writes:

> Eli Zaretskii <eliz@gnu.org> writes:
>
>> Ping!  Andrea, did you have time to look at this?
>
> No sorry, hope this week to have time to tackle my todolist.

Okay should be fixed with 372ce6adbf3 in master.

Thanks

  Andrea

Re: maphash

[Mattias Engdegård]

1 okt. 2024 kl. 18.31 skrev Andrea Corallo <acorallo@gnu.org>:

> Okay should be fixed with 372ce6adbf3 in master.

Thank you! Would you also take a look at the four DOHASH_SAFE uses in comp.c, and see if there is any possibility of mutation of the tables iterated over? Then they could be changed to DOHASH.

Re: maphash

[Andrea Corallo]

Mattias Engdegård <mattias.engdegard@gmail.com> writes:

> 1 okt. 2024 kl. 18.31 skrev Andrea Corallo <acorallo@gnu.org>:
>
>> Okay should be fixed with 372ce6adbf3 in master.
>
> Thank you! Would you also take a look at the four DOHASH_SAFE uses in
> comp.c, and see if there is any possibility of mutation of the tables
> iterated over? Then they could be changed to DOHASH.

Thanks I think the use of DOHASH_SAFE is correct there.

  Andrea

Re: maphash

[Mattias Engdegård]

1 okt. 2024 kl. 20.36 skrev Andrea Corallo <acorallo@gnu.org>:

>> Would you also take a look at the four DOHASH_SAFE uses in
>> comp.c, and see if there is any possibility of mutation of the tables
>> iterated over? Then they could be changed to DOHASH.
> 
> Thanks I think the use of DOHASH_SAFE is correct there.

Mind explaining why? Note that DOHASH does attempt to catch some table mutations when checking is enabled.

DOHASH_SAFE is intended for Fmapcar, where there may be mutations and we mustn't crash because of them but we don't care about semantics in that case.

Re: maphash

[Andrea Corallo]

Mattias Engdegård <mattias.engdegard@gmail.com> writes:

> 1 okt. 2024 kl. 20.36 skrev Andrea Corallo <acorallo@gnu.org>:
>
>>> Would you also take a look at the four DOHASH_SAFE uses in
>>> comp.c, and see if there is any possibility of mutation of the tables
>>> iterated over? Then they could be changed to DOHASH.
>> 
>> Thanks I think the use of DOHASH_SAFE is correct there.
>
> Mind explaining why? Note that DOHASH does attempt to catch some table mutations when checking is enabled.
>
> DOHASH_SAFE is intended for Fmapcar, where there may be mutations and we mustn't crash because of them but we don't care about semantics in that case.

Sorry from your prev message I understood the opposit.  With abb932290df
we now use DOHASH (not that I expect any measurable perf impact).

Thanks

  Andrea

Re: maphash

[Mattias Engdegård]

3 okt. 2024 kl. 13.18 skrev Andrea Corallo <acorallo@gnu.org>:

> Sorry from your prev message I understood the opposit.  With abb932290df
> we now use DOHASH (not that I expect any measurable perf impact).

Excellent, thank you. It's mostly about showing clearly that we don't expect anything silly going on in those loops (and getting some extra checking when enabled).

Re: maphash

[Richard Stallman]

    I have discovered by experimentation that maphash actually does what 
    I hoped it would, which is to pass key/value pairs to the mapping 
    function in the same order in which they were added to the table. 

An small anount of experimentation doesn't show you it will always to
do that.  It would be necessary to study the code and construct a
proof, before we could promise this to the users.

Do you want to study the code?

Re: maphash

[Stephen J. Turnbull]

>>>>> "rms" == Richard Stallman <rms@gnu.org> writes:

    I have discovered by experimentation that maphash actually does what 
    I hoped it would, which is to pass key/value pairs to the mapping 
    function in the same order in which they were added to the table. 

    rms> An small anount of experimentation doesn't show you it will
    rms> always to do that.  It would be necessary to study the code
    rms> and construct a proof, before we could promise this to the
    rms> users.

If I understand the OP's description correctly, I can already promise
you that code depending on such a feature won't be portable to XEmacs:

(let ((my-hash (make-hash-table))
      result)
  (puthash "key1" "val1" my-hash)
  (puthash "key2" "val2" my-hash)
  (puthash "key3" "val3" my-hash)
  (maphash (lambda (k v) (setq result (cons k result))) my-hash)
  (reverse result))

=> ("key2" "key3" "key1")


-- 
Institute of Policy and Planning Sciences     http://turnbull.sk.tsukuba.ac.jp
University of Tsukuba                    Tennodai 1-1-1 Tsukuba 305-8573 JAPAN
               Ask not how you can "do" free software business;
              ask what your business can "do for" free software.

Re: maphash

[Greg Hill]

At 4:46 PM +0900 4/24/03, Stephen J. Turnbull wrote:
>  >>>>> "rms" == Richard Stallman <rms@gnu.org> writes:
>
>     I have discovered by experimentation that maphash actually does what
>     I hoped it would, which is to pass key/value pairs to the mapping
>     function in the same order in which they were added to the table.
>
>     rms> An small anount of experimentation doesn't show you it will
>     rms> always to do that.  It would be necessary to study the code
>     rms> and construct a proof, before we could promise this to the
>     rms> users.
>
>If I understand the OP's description correctly, I can already promise
>you that code depending on such a feature won't be portable to XEmacs:
>
>(let ((my-hash (make-hash-table))
>       result)
>   (puthash "key1" "val1" my-hash)
>   (puthash "key2" "val2" my-hash)
>   (puthash "key3" "val3" my-hash)
>   (maphash (lambda (k v) (setq result (cons k result))) my-hash)
>   (reverse result))
>
>=> ("key2" "key3" "key1")

Fortunately for me, in GNU Emacs Stephen's example--and several 
variations thereof--do work the way I described, and not the way they 
work in XEmacs.  Also, fortunately for me, my code does not have to 
be portable.


At 9:51 PM -0400 4/23/03, Richard Stallman wrote:
>Do you want to study the code?

After taking a quick look at the C source code, the simple answer to 
Richard's question is "No, thank you."  I do write code in C, when I 
absolutely have to, but I don't really care for the language.  And in 
general, I don't enjoy the challenge of figuring out how OP's code 
works, especially when it is written in C _and_ chock full of MACROs.

So, I'll just say: That's ok, I understand that you cannot, in good 
faith, make any promises either that this "feature" works relieably 
now, or even that if it happens to now, it always will.  It _is_ 
working for me reliably now, and I'll keep using it as long as it 
does; and I promise I won't complain if my decision to do so comes 
back to haunt me later on.

--Greg

Re: maphash

[Richard Stallman]

    Fortunately for me, in GNU Emacs Stephen's example--and several 
    variations thereof--do work the way I described,
    ...

    After taking a quick look at the C source code, the simple answer to 
    Richard's question is "No, thank you."

We can't document this feature unless we know it can be relied on.  I
took a quick look at the code of maphash and it led me to doubt that
this is generally true, but while I have the know-how to study it
carefully, I do not have the time.