Re: plists, alists, and hashtables

[Ted Zlatanov]

On Wed, 05 Aug 2015 19:24:31 +0200 "Pascal J. Bourguignon" 
<pjb@informatimago.com> wrote: 

PJB> Ted Zlatanov <tzz@lifelogs.com> writes:
>> Yes, I think the implicit advantage of everything being a list is well
>> understood amongst us.  But so is the disadvantage of treating
>> everything as a list.  The question is whether hashtables, an existing
>> ELisp map data type, could become more popular.

PJB> Why?

To have a true native map data type.

PJB> How would that be good?

Because a true native map data type avoids the complexity of lists in
many cases.

PJB> Seriously, hash-tables have a lot of drawbacks.
PJB> They use much more memory,
PJB> they are much slower (on small dictionaries),

I think these details are easily optimized at the C level. Clearly an
alist is better as the *backend* hashtable implementation for up to 10,
possibly up to 100 entries (depending on caching, pipelining, hashing
function, and other factors). But the frontend presentation is what I'm
concerned about. I think a better reader syntax for hashtables would
make them easier to write and read in code and would error out if they
are malformed. That's an improvement over alists and plists I think.

PJB> they are much restrictive on the possible key equivalence function.

Like I said, 95% of the cases only need eql and equal. For the rest,
users can use `make-hash-table' directly instead of through the shortcut
syntax.

PJB> The only advantage they have, is on speed of access in big dictionaries.

PJB> But even when you need a O(1) access on a big dictionary, you will find
PJB> you keep converting between hash-table and lists or vectors, of only to
PJB> sort the entries out to present them to the user!

That's no different than looping over alists and plists to collect and
sort the entries, is it?

PJB> If you achieved your goal of having unwashed masses use hash-tables

"unhashed masses"? :)

PJB> instead of a-list/p-lists, the only result you'd attain would be to
PJB> slow down emacs. Run your own benchmark. On my computer, I notice
PJB> that until the size of the dictionary reaches 20-30, a-lists are
PJB> performing better than hash-table. (And even, I call assoc on set,
PJB> while for a-list it is customary to just do acons, so inserting or
PJB> reseting entries would be even much faster).

Absolutely, but I mentioned already that this is easily fixed on the
back end. I think it's clear that while hashtables *can* scale, alists
and plists *can't* because their backend and frontend are the same.
Hashtables are only accessible through an API, their backend is
hidden.

PJB> Nonetheless, this argument is the reason why the print/read syntax for
PJB> hash-tables is:

>> #s(hash-table size 65 test eql rehash-size 1.5 rehash-threshold 0.8 data ())

PJB> This extends easily to any other data structure for which you'd want a
PJB> literal representation.

OK, but still, I'm not interested in heaps, trees, graphs, skip lists,
or other data structures.  I'm interested in improving the accessibility
and popularity of hashtables in order to avoid the complexity and
ambiguity of alists and plists when dealing with maps.

Ted