Association List

For small numbers of elements in an assoc list we know that a simple list assoc search is faster than a hash table lookup. The question is can we improve on the association list? First of all we could search a vector in stead of a list or even lay it out as

$$ ASSOC = [K1,H1,K2,H2,K3,H3,...], $$

where $K1$ is a calculated hash and $H1$ is the handle. This can be pushed to C without knowing about the hash function or equality predicate and would be a nice addition to guile internals. Now for small list this is about the best you can get, but it turns out that we can improve on this track and show that a simple list is faster than a hash table for quite large association lists.

The trick is to note that we can compare many hashes at once using 128 bit SIMD instructions and essentially scan a list in the order of 10 elements each ns.

An implementation is done in C_CODE, see the stis_a_search and stis_a_set.

Anyhow the idea is to lay it out as

$$ FASTLIST = [HA_1,HB_1,V_{1,1},\ldots,V_{1,16},HA_2,HB_2,V_{2,1},\ldots,V_{2,16},\ldots], $$

with $HA$ of 16 bytes representing the first 8 bits of the hash. Then similarly $HB$ is the next 8 bits in all we code the first 16 bits by doing this and hence for order of 1000 elements the risk for clashes are not that high. Finally the $V$ is the key value conses or handles that is returned at a match and should be verified as a true match by the equal predicate.

So what's the performance? We have the table over the time it takes to randomly search alist of $N$ elements 100,000,000 times,

\begin{array}{l|l|l} N & ASSOC & FASTLIST\\ \hline 2 & 1.40s & 1.60s \\ 4 & 1.48s & 1.60s \\ 8 & 1.70s & 1.61s \\ 16 & 2.21s & 1.65s \\ 32 & 3.54s & 1.62s \\ 64 & 6.0s & 1.65s \\ 128 & 10.0s & 1.80s \\ 256 & 18.2s & 2.06s \\ 512 & 34.2 & 2.86s \\ 1024 & 66.8s & 5.1s \\ \end{array}

A hash lookup takes about 3-4s and we see that break even for the fastlist around 512 elements. For assocs that's are around 20 elements which is kind of known fact. So this means that a hash implementation should dispatch between a hash table and this kind of association list as the application size is quite large where the FASTLIST is more power full than the hash. We also note that a pure assoc only beats the FASTLIST for very few elements around 6 seam to be the turning point but still not too terrible difference for 4 elements.

This benchmark is with a negligible hash function and fast equal check. But the C code is general and we create custimizable association lists and not need to push everything to C for speed.

Next effort will be to make a higher order library for the assoc lists and make them behave much like a hash tables and finally dispatch between the new hash table implementation and this association list implementation of hash tables.

links

social