Re: plists, alists, and hashtables

["Pascal J. Bourguignon" <pjb@informatimago.com>]

Ted Zlatanov <tzz@lifelogs.com> writes:

> So you have to do
>
> (delq nil (mapcar #'car-safe '((a) (b 1) (c . 2) d)))
>
> When the backend implementation is also the frontend, as with alists,
> you have to go through the whole alist to collect the keys. That's the
> access-time looping and parsing I mean. By contrast, the hashtable
> implementation (whether it does it now or not) can keep the list of keys
> and update it only when the data is modified.  At access time, the keys
> are instantly available.

Only they are NOT instantly available.  First it has to compute the hash
value, then it has to compute a division to find the modulo, and finally
it still has to walk a list or an array when there are collisions.

All this takes time, so much time that it's faster to walk 100 cons
cells and perform 50 comparisons of the keys in an a-list, that doing
all that in a hash-table!  Benchmarks prove it!

Now, I should mention that emacs lisp is an implementation where the
difference is the biggest.

In clisp (similar to emacs lisp, compiles to a bytecode VM), the
break-even point is at 35 entries, and in other CL implementations
compiling to native code, the break-even point is at 5 or 6 entries.

That means that there's room to optimize hash-tables in emacs lisp.

Nonetheless, there's an incompressible minimum break-even of half a
dozen, and most dictionaries ARE that small.
 


> Maybe the macro is good enough, but I think the keys and values have to
> be clearly separated from each other and from other cells to make it
> visually useful.  

I understand that, and I cannot advise more strongly that you add
newlines and indent your data to clearly show it.

         (hash-table  k1      v1
                      kkkk2   v2
                      k3      vvvvvv3)

(use M-x align-cols)

Notice that often keys are keywords:

         (hash-table  :k1      v1
                      :kkkk2   v2
                      :k3      vvvvvv3)

and emacs fontifies them nicely.


Also, I would admit that using parentheses around the entries could help
editing the data structure, since that allows adding or removing entries
easily with a structural editor like emacs+paredit.

        (mhash-table  (k1      v1)
                      (kkkk2   v2)
                      (k3      vvvvvv3))

It works well enough for a macro (eg. let), but for a function it is a
real bother:

        (fhash-table  '(k1      v1)
                      (list 'kkkk2  (+ 3 4))
                      (list 'k3     (f 'k3)))

Therefore I wouldn't advise to use anything more complex than a even
number of arguments,  alternating keys and values, to a function
constructor.



> The key for me is that I'm not looking to make
> hashtables themselves more prominent, but to give ELisp users a way to
> read and write maps more clearly and in a way that maps more closely to
> a true map data type (which I thought the hashtable was).
>
> The second part of my question was whether Customize support for
> hashtables would make them more approachable and useful.

This could definitely help.


> SM> More importantly, mathematical maps are persistent, whereas your
> SM> apparently favorite implementation (the hash-table) is not persistent,
> SM> contrary to (e.g.) alists.
>
> I am not sure what you mean.  Perhaps it's a problem with the
> terminology.  Could you explain?

SM means immutable.

And indeed, contrarily to the benchmark code I presented earlier, the
natural usage of a-lists is:

Is a key present?    (assoc key alist)            ; O(n)
 
Value for the key:   (cdr (assoc key alist))      ; O(n)

Add a key/value:     (acons key value alist)      ; O(1)

Remove a key:        now, if you use the "Is a key present?" above, 
                     you will need:

                     (remove key alist :key 'car) ; O(n)

                     otherwise (ie. when no value can be nil)
                     you can just do:

                     (acons key nil alist)        ; O(1)

The a-lists are therefore not mutated, and can be shared as the tail of
several variablt a-lists.

(defvar *defaults*   '((:move . walk) (:eat . swallow)))
(defvar *bird*       (acons :move 'fly *defaults*))
(defvar *mouse*      (acons :eat 'chew *defaults*))
(defvar *dead-mouse* (acons :move nil *mouse*))

(list *dead-mouse* *mouse* *bird* *defaults*)
--> (((:move) . #1=((:eat . chew) . #2=((:move . walk) (:eat . swallow))))
     #1# 
     ((:move . fly) . #2#)
     #2#)

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