Embracing Emacs Lisp hash tables: introducing XHT

They're fast. In fact, faster than alists and plists when beyond a few tens of items.

I found the observation above a few times: in Adam Porter's emacs-package-dev-handbook, which benchmarked them; in the README of Wilfred Hughes's ht library; and in the Emacs Lisp Manual itself, which says:

A hash table is a very fast kind of lookup table, somewhat like an alist in that it maps keys to corresponding values.

and

Lookup in a hash table is extremely fast for large tables — in fact, the time required is essentially independent of how many elements are stored in the table. For smaller tables (a few tens of elements) alists may still be faster because hash tables have a more-or-less constant overhead.

This raises the question: how many "tens"?

According to Adam Porter's benchmarking, hash tables are already faster than plists and alists at 26 pairs, and the difference only gets larger beyond that. But... what about for fewer items?

I gave it a look. Below I use bench-multi-lets, which can be found in emacs-package-dev-handbook.

(bench-multi-lets
  :times 10000 :ensure-equal t
  :lets  (("with 5 pairs"
           ((numseq         (number-sequence 1 5))
            (strings        (--map (format "prefix-%s" it) numseq))
            (strings-alist  (--map (cons it it) strings))
            (strings-ht     (h<-alist strings-alist)) ;or use ht, same here
            (strings-plist  (h->plist strings-ht))))) ;or use ht, same here
  :forms (("strings/alist"
           (let (r)
             (dolist (string strings r)
               (push (cdr (assoc string strings-alist))
                     r))))
          ("strings/plist"
           (let (r)
             (dolist (string strings r)
               (push (plist-get strings-plist string)
                     r))))
          ("strings/hash-table/equal"
           (let (r)
             (dolist (string strings r)
               (push (gethash string strings-ht)
                     r))))))

And since we're on it, I repeated it with other numbers. Results:

Conclusion? For strings, lookups in:

1. alists are way slower than plists and hash tables and it gets worse with size (see the runtime change from 100 to 500?);
   
2. plists are about 20% faster than hash tables for up to 20 pairs; this drops to 10% at about 30 pairs; then at about ~40 pairs hash tables catch up — and from there on they outperform both alists and plists (by ever-widening margins).
   

Should you then opt for plists when below 40 items? I think it depends:

1. If the number of lookups is large, you do it repeatedly, the dataset is unlikely to grow beyond 40 items, and the thing is performance-critical, then I suppose so.
   
2. Otherwise, it makes no difference. We're talking about a few microseconds per lookup. Use whatever you like.
   

Yes, whatever you like. But consider this: if you have to pick one to learn well, hash tables have this advantage, then: fastest option beyond 40 items; and no more than about 24% slower below that — which will likely only matter at all if you'll have to look up this less-than-40-item table thousands of times to get you out of the microseconds scale (and even that will get you to milliseconds: do you care?).

Moreover, it seems that the advantages in speed are asymmetrically larger than the disadvantages in speed. The former can be considerable, whereas it'd rarely be the case where the latter would matter: hash tables' speed seems to be capped at about ~20% slower than plists for 5 items, but already faster than alists.

But we're left with this "whatever you like", and then some questions come up.

• Are Elisp hash tables any... less-likable than these other two fellows?
  
• And if they're "better", then why won't Elispers use them more?
  

Let's try to answer them.

Here are some conjectures about why hash tables might not currently be your first choice for key–value collections in Elisp.

Having finished this introduction, I invite you to check XHT's README.

Explore, use, enjoy!