Subject: RE: bug#28753: 25.3; Functions to get alist from hash table and vice versa

From: Drew Adams <[email-masked]>
Date: Sun, 4 Mar 2018 16:01:53 -0800 (PST)

>> Order is quite important for alists, generally.
>> Is there some reason we should not be able to count on
>> this `maphash' behavior?
>
> Order in hashtables is not guaranteed. If anything relies
> on the order, it's buggy.
 
Emacs hash tables don't fall from the sky.  They are not
shadows of some Platonic ideal.  This is a design choice.
Emacs Lisp can implement hash tables any way it wants.

>> I don't know whether it is guaranteed, but this use case
>> involving conversion to alist looks like a good argument
>> for some guarantee wrt order.
>
> No. Ordering guarantees require additional complexity and
> overhead, and are almost never needed.

Neither of those assertions has been demonstrated.  Feel
free to do so (how much overhead, how infrequent).

And infrequency of use is not, alone, a good reason not
to support something.  Infrequent does not mean unimportant.

>> Another possibility (?): Allow _optional_ creation of
>> a hash table that does preserve such ordering (even if
>> just by recording order of entry and making that
>> available to `maphash').  E.g., add a keyword arg for
>> `make-hash-table' that does just that.
>>
>> Even if it turned out that this consistently or occasionally
>> detracted from performance, it could be a useful option.
>> Conversion to an alist would be a case in point.
>
> I don't think it would be worth the additional complexity.

Why?  How much additional complexity?

> Hash tables have been available for ages in most programming
> languages, and almost never does anybody ask for ordering
> guarantees. (For example, I have never seen somebody using
> LinkedHashMap in Java.)

Emacs Lisp has lots of features that are not in "most
programming languages".  Propertized strings, for one
trivial example.

> Even for alists, most of the time maintaining insertion
> order is an irrelevant detail,

What time maintaining insertion order?  I can't imagine
what you mean by that.

> most users care only about get/put/remove.

Not demonstrated.  But even if it were true, it wouldn't
follow that Lisp alist order is unimportant.

Next you'll be suggesting that because lists are mutated
relatively infrequently it is unimportant to be able to
modify list structure or test cons equality with `eq'.
Or that because true lists are used most of the time we
might as well drop support of dotted lists.

----

Naive google search -

https://www.javaspecialists.eu/archive/Issue073.html

https://stackoverflow.com/questions/12998568/hashmap-vs-linkedhashmap-performance-in-iteration-over-values/12998878

https://stackoverflow.com/questions/26623129/when-to-use-linkedhashmap-over-hashmap-in-java