Re: plists, alists, and hashtables

[Pascal J. Bourguignon]

Ted Zlatanov <tzz@lifelogs.com> writes:

> 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. 

DUH!  What did I just do to write the benchmark?

So you're not discussing about hash-tables, but about how to provide
high level abstractions.  Well DUH, just program them! functions,
macros.

> 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.

And yes, if you had readtables and reader macros, also a reader macro.

Don't ask for a dictionary abtraction.  Ask for readtables and reader
macros!  So that you may implement your own syntax for your own
abstractions!



>
> 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?

Well, for small dictionaries, (about 8 entries), it's still faster to
copy the keys from a-lists than from a hash-table.


> 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.

Yes, you're asking about an abstraction and a nice API and syntax for
it.  

I'm saying ok, implement it, lisp is good for that. (It could be better
with reader macros).

I'm also saying, beware anyways, because even with adaptative data
structures abstracted away, you will aways have some (usage) complexity
coming up, from the fact that your abstract operations will have some
overhead and some time and space complexity that may not be what is the
best in some specific cases.



(let ((sizes '()))
 (mapatoms (lambda (s)
             (when (boundp s)
               (let ((table (symbol-value s)))
                 (when (hash-table-p table)
                   (push (hash-table-count table) sizes))))))
  (sort sizes '<))

Here are the results on three different emacs instances doing different
things: CL develoment with slime, erc, gnus:

--> (0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 3 4 4 5 15 18 19 23 23 28 36 54 108 252 
253 366 709 978 1013)
--> (0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 4 4 5 8 19 19 22 23 23 28 54 108 252 253 366 
604 752 871 894 978)
--> (0 0 0 0 0 0 0 0 0 0 1 2 4 4 4 5 9 19 19 23 23 26 28 30 54 108 252 253 366 
562 752 894 978 1638)

(length '(0 0 0 0 0 0 0 0 0 0 0))                    --> 11
(length '(1 2 4 4 4 5 9))                            -->  7
(length '(19 19 23 23 26 28 30))                     -->  7             
(length '(54 108 252 253 366 562 752 894 978 1638))  --> 10

So about half of those hash-table are too small, and should have been
implemented as a-lists, one quarter is around the break even, and only
one quarter should definitelhy be hash-tables.

You could improve this, by implementing a better data walker, here we
only look at the hash-tables directly bounds to variables.


-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk