From ffa4337909898f3a54469bee1baf0294b7bcffa3 Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Fri, 2 Sep 2022 22:35:56 -0400 Subject: Notes on linear searches (including vector binary) and vector 256-bit tables --- docs/implementation/primitive/search.html | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'docs') diff --git a/docs/implementation/primitive/search.html b/docs/implementation/primitive/search.html index dcbe6704..08140eb3 100644 --- a/docs/implementation/primitive/search.html +++ b/docs/implementation/primitive/search.html @@ -7,10 +7,19 @@

Implementation of search functions

This page covers the search functions, dyadic ⊐⊒∊, and self-search functions, monadic ⊐⊒∊⍷. Generally speaking, hash tables or plain lookup tables are the fastest way to implement these functions, because they transform the problem of searching into random access, which is something computers specialize in. In some edge cases, and when the search becomes large enough that caches can't speed up random access, other methods can be relevant.

Searching is closely related to sorting. I've found it helpful to think of a search function as an ordered lookup according to an unspecified order. The advantage over a predefined order is that the order can be shuffled with a hash function to randomize the distribution. The fact that the wanted result is in the original argument order, not sorted, also means that sparse tables are more effective—there is never any need to traverse the table to pack ordered values as in sorting.

+

Small arguments

+

When one argument to a search function is small, it's best to use a linear-time method—that is, linear in both arguments, O(mn). The simplest versions:

+ +

Each of these easily allows for SIMD comparison. A more effective use of SIMD (unless the size of the small argument is 1, up to maybe 3) is a vector binary search as presented in the first half of my "Sub-nanosecond Searches" talk (video, slides). This search of sorted values is performed by using shuffle instructions to independently select a pivot for each value, and adding a pivot index bit based on the result of comparing. It can be used as a reverse lookup as well, performing a non-SIMD update whenever a match is found. Multiple registers can be searched, but each one has to be touched at every step leading to O(mn) asymptotic performance despite the binary search.

Lookup tables

For the purposes of these notes, a lookup table is storage, indexed by some key, that contains at most one entry per key. This means reading the value for a given key is a simple load—differing from a hash table, which might have collisions where multiple keys indicate the same entry. Lookup table operations are very fast, but they need to cache table accesses to be fast. So they're useful when the number of possible values (that is, size of the table) is small: a 1-byte or 2-byte type, or small-range integers. You might expect the entire table has to be initialized, but it doesn't always: see sparse lookups.

For example, a lookup table algorithm for dyadic ⊐ might traverse 𝕨, writing each value's index to the table. Doing this step in reverse index order makes sure the lowest index "wins". Similarly, empty entries must be initialized to ≠𝕨 beforehand. Then the result is 𝕩⊏t where t is the table constructed this way. A nonzero minimum value can be handled for free by subtracting it from the table pointer.

Set operations can be handled with a packed bit table, but reading a bit is slower so this should be done only if the space savings are really needed.

+

A 1-byte lookup can be packed into vector registers for extra-fast searching. To look up a byte, select the appropriate byte from the table with the top 5 bits, and a mask from another table with the bottom 3. Put these together and pack into bits with compare-movemask.

Hash tables

A hash table is a more sophisticated design where there are more possible keys than table entries. For good performance it depends on not having too many actual keys packed into a small space, which is why this method is named after the hash function. If the data is expected to be random then no hash function is needed (the identity function can be used), but I don't think that happens much with searching. Hash tables generally degrade to the performance of a linear lookup if the hash is defeated, so it's ideal to have a way to escape and use a sorting-based method if too many hashes collide.

Hashing is really the only way to get a performant lookup on arbitrary data. For 2-byte and small-range data, lookups are better, and in several 4-byte cases, lookup with partitioning is competitive for smaller arrays and much better for large ones as the hash table outgrows the cache (>1e5 elements to be hashed or so).

-- cgit v1.2.3