Switch from custom hash tables to list (set) ?

[Ambrevar]

Initially it was decided to encode the set of unique entries as a hash-table for performance reasons. The reasoning was that hash-tables have constant-time access to their elements as opposed to the more practical Lisp lists, for which access is in linear time.

It turns out that element access in a list is extremely fast with SBCL, and a quick benchmark shows that it's only when exceeding about 10.000.000 entries that hash tables start becoming more interesting. So maybe hash tables were not the best choice for a set that's unlikely to have more than 100.000--1.000.000 entries.

Previously we explained how the uniqueness is customizable. In standard Common Lisp, hash tables accept only eq, eql, equal or equalp as test function. So to allow full customizability as in the previous example, we resort to the cl-custom-hash-table library.

Custom hash tables have restricted the design somewhat. For instance, the entries hash table values are the entries themselves, so that we have a way to access the stored keys in constant time. (Indeed, when you call (gethash my-web-page entries), there is no guarantee that the matched key is identical to my-web-page.)