Is there utility in making hash-table-{keys, values} built-in functions?

Is there utility in making hash-table-{keys, values} built-in functions?

[Shankar Rao]

[-- Attachment #1: Type: text/plain, Size: 432 bytes --]

Hello all,

I noticed that the functions hash-table-keys and hash-table-values are just
wrappers around maphash. This means that there is no way to iterate over a
hash-table without using a lambda.

Would it be useful or worthwhile to implement these directly in C? I don't
know much about low-level Emacs development, but having these as built-ins
could make iteration of a hash-table a little faster and easier to debug.

Shankar

[-- Attachment #2: Type: text/html, Size: 545 bytes --]

Re: Is there utility in making hash-table-{keys, values} built-in functions?

[Mattias Engdegård]

28 nov. 2024 kl. 12.53 skrev Shankar Rao <shankar.rao@gmail.com>:

> I noticed that the functions hash-table-keys and hash-table-values are just wrappers around maphash. This means that there is no way to iterate over a hash-table without using a lambda.
> 
> Would it be useful or worthwhile to implement these directly in C? I don't know much about low-level Emacs development, but having these as built-ins could make iteration of a hash-table a little faster and easier to debug.

It's unlikely that it would be faster to make a list just for the purpose of a single iteration; the allocation costs alone would be too high. Other ways of iterating through hash-tables have been tried with mostly disappointing results, although there might be some value in avoiding use of the C stack in some cases.

If you tell us what you are trying to accomplish, it would be easier for us to help you.

Re: Is there utility in making hash-table-{keys, values} built-in functions?

[Gerd Möllmann]

Shankar Rao <shankar.rao@gmail.com> writes:

> Hello all,
>
> I noticed that the functions hash-table-keys and hash-table-values are
> just wrappers around maphash. This means that there is no way to
> iterate over a hash-table without using a lambda.

If this is about syntax, cl-loop has support for hash tables. For
example

  for x being the hash-keys of something using (hash-value y)

Re: Is there utility in making hash-table-{keys, values} built-in functions?

[Shankar Rao]

[-- Attachment #1: Type: text/plain, Size: 1500 bytes --]

This isn't about syntax, as changing hash-table-{keys,values} to be
built-in functions wouldn't change their syntax.

I was curious about this because there doesn't seem to be a way to iterate
over a hash-table without either explicitly or implicitly using a lambda.
For example, if we macro expand the following cl-loop

(cl-loop for key being hash-keys of tables using (hash-values v)
         collect (func k v))

we obtain:

(cl-block nil
  (cl-block --cl-finish--
    (maphash
     (lambda
       (key v)
       (func k v))
     tables))
  nil)

Most languages that provide a hash-table data structure provide methods for
directly accessing the hash keys and values. I'm trying to understand if it
would be beneficial for elisp to provide these as well. Would it provide a
significant enough speed boost for code that frequently iterates over hash
keys/values? Is there some complication implementing these functions in C
directly?

Shankar Rao

On Thu, Nov 28, 2024 at 7:40 PM Gerd Möllmann <gerd.moellmann@gmail.com>
wrote:

> Shankar Rao <shankar.rao@gmail.com> writes:
>
> > Hello all,
> >
> > I noticed that the functions hash-table-keys and hash-table-values are
> > just wrappers around maphash. This means that there is no way to
> > iterate over a hash-table without using a lambda.
>
> If this is about syntax, cl-loop has support for hash tables. For
> example
>
>   for x being the hash-keys of something using (hash-value y)
>
>
>

[-- Attachment #2: Type: text/html, Size: 2092 bytes --]

Re: Is there utility in making hash-table-{keys, values} built-in functions?

[Gerd Möllmann]

Shankar Rao <shankar.rao@gmail.com> writes:

> This isn't about syntax, as changing hash-table-{keys,values} to be
> built-in functions wouldn't change their syntax.
>
> I was curious about this because there doesn't seem to be a way to
> iterate over a hash-table without either explicitly or implicitly
> using a lambda. For example, if we macro expand the following cl-loop

Yes, I understood that, and I thought maybe you were asking this because
you were annoyed by having to write a lambda and so on, which using
cl-loop would avoid.

>
> (cl-loop for key being hash-keys of tables using (hash-values v)
>          collect (func k v))
>
> we obtain:
>
> (cl-block nil
>   (cl-block --cl-finish--
>     (maphash
>      (lambda
>        (key v)
>        (func k v))
>      tables))
>   nil)
>
> Most languages that provide a hash-table data structure provide
> methods for directly accessing the hash keys and values. I'm trying to
> understand if it would be beneficial for elisp to provide these as
> well. Would it provide a significant enough speed boost for code that
> frequently iterates over hash keys/values? Is there some complication
> implementing these functions in C directly?

I think Matthias said something like that already: It would be consing
up lists, that we otherwise don't need, and that's far from free.

My own gut feeling is that it might well be more expensive than maphash,
depending on the hash table size, of course. The least I would say is
that it's not a clear win.

Re: Is there utility in making hash-table-{keys, values} built-in functions?

[Shankar Rao]

[-- Attachment #1: Type: text/plain, Size: 1629 bytes --]

I've been reading about the tradeoffs between different iteration methods,
and the consensus seems to be that dolist, dotimes, and cl-loop are more
efficient than mapc and seq-do, because the former methods macro-expand (in
almost all cases) to a while loop, while the latter require a lambda, which
are generally slower and harder to debug.

I see what you're saying that allocating a list of keys just to iterate
once over a hash table would be wasteful. And I suppose it also wouldn't
make sense to have a built-in just for iterating over hash-tables.

Shankar Rao

On Thu, Nov 28, 2024 at 6:31 PM Mattias Engdegård <
mattias.engdegard@gmail.com> wrote:

> 28 nov. 2024 kl. 12.53 skrev Shankar Rao <shankar.rao@gmail.com>:
>
> > I noticed that the functions hash-table-keys and hash-table-values are
> just wrappers around maphash. This means that there is no way to iterate
> over a hash-table without using a lambda.
> >
> > Would it be useful or worthwhile to implement these directly in C? I
> don't know much about low-level Emacs development, but having these as
> built-ins could make iteration of a hash-table a little faster and easier
> to debug.
>
> It's unlikely that it would be faster to make a list just for the purpose
> of a single iteration; the allocation costs alone would be too high. Other
> ways of iterating through hash-tables have been tried with mostly
> disappointing results, although there might be some value in avoiding use
> of the C stack in some cases.
>
> If you tell us what you are trying to accomplish, it would be easier for
> us to help you.
>
>

[-- Attachment #2: Type: text/html, Size: 2084 bytes --]

Re: Is there utility in making hash-table-{keys, values} built-in functions?

[Tomas Hlavaty]

On Fri 29 Nov 2024 at 15:25, Shankar Rao <shankar.rao@gmail.com> wrote:
> while the latter require a lambda, which are generally slower and
> harder to debug.

If that is the case then it would be better to improve the debuger.

>> This means that there is no way to iterate over a hash-table without
>> using a lambda.

Iterating over a hash-table using a callback is not such a problem.

More interesting is that it is not possible to suspend and resume the
iteration.  And even more interesting is that it is generally undefined
to change the hash-table inside map-hash callback.  hash-tables are
complex objects compared to lists or arrays and map-hash hides a lot of
complexity trying to provide reasonable interface.

Even worse is the lisp interface to list directory,
e.g. directory-files, directory-files-and-attributes,
directory-files-recursively.  Here one gets the whole thing as a list
all at once.  And the filter is quite limited and not programable.  So
if I want something uncommon or faster, an external program is likely a
better choice.  Compare that to C/POSIX interface which provides a way
to iterate over the directory.  Or maybe instead of worrying about
closing files, a map-hash like interface, e.g. map-directory, would be
better?