Wojciech Muła

> Lookup tables are always faster than calculation - is that true?

Maybe on the Z80. Contemporary RAM was quite fast compared to it, by our sad standards.

A table lookup per byte will see you hit a pretty hard limit of about 1 cycle per byte on all x86 CPUs of the last decade. If you’re doing a state machine or a multistage table[1] where the next table index depends on both the next byte and the previous table value, you’ll be lucky to see half that. Outracing your SSD[2] you’re not, with this approach.

If instead you can load a 64-bit chunk (or several!) at a time, you’ll have quite a bit of leeway to do some computation to it before you’re losing to the lookup table, especially considering you’ve got fast shifts and even multiplies (another difference from the Z80). And if you’re doing 128- or 256-bit vectors, you’ve got even more compute budget—but you’re also going to spend a good portion of it just shuffling the right bytes into the right positions. Ultimately, though, one of your best tools there is going to be ... an instruction that does 16 resp. 32 lookups in a 16-entry table at a time[3].

So no, if you want to be fast on longer pieces of data, in-memory tables are not your friend. On smaller data, with just a couple of lookups, they could be[4]. In any case, you need to be thinking about your code’s performance in detail for these things to matter—I can’t think of a situation where “prefer a lookup table” is a useful heuristic. “Consider a lookup table” (then…

> Ah, Highway is C++ so that won't work for you then. And indeed CMPISTR is quite nonportable. I'm curious whether you are getting good performance from CMPISTR relative to AVX2 or even AVX-512, for those who have it? Wider vectors might reduce the advantage of specialized instructions.

The main advantage of pcmpistrm is that it doesn't need preprocessing. You can beat its raw speed just fine, e.g. using the Muła/Langdale algorithm (http://0x80.pl/articles/simd-byte-lookup.html), but that algorithm requires costly preprocessing of the set to be matched. For string functions, input strings are usually very short and algorithms have to be optimised for that case; the steady state of a tight main loop is rarely reached and not the primary goal of optimisation. So as a result, any preprocessing before we can get started walking down the string gets really expensive.

In fact, the benchmarks I wrote and whose results the Phoronox page has shamelessly ripped off use strings of just 64 bytes on average, which I believe is more representative for real-world cases than the very long strings other implementations seemed to have been optimised for. This is also the reason why I ended up using just SSE: not only do the instructions provided by SSE2 largely suffice for the job, but also is the advantage of longer vectors severely reduced when your input is unlikely to be longer than one or two of them. Plus for AVX and later, we have to do a VZEROUPPER before return (to ensure…

x86 doesn't have thousands. That's overstating it by quite a bit. The assembler I wrote contains 1095 encodings. It's from ~2004 but 100% complete at the time, so sure new instructions have been added since. But those are encodings. SAL has like 8 encodings, SAR has 12, CMP has 14, etc. These encodings are just different ways to use the same opcode but with different source/target parameters (8/16/32-bit immediates or registers, etc.)

Someone wrote a script that disassembled all the binaries on their Linux machine and counted the number of actual instructions used (mostly by gcc, of course). Only a tiny fraction of the total instructions were used:

http://0x80.pl/notesen/2014-01-01-instruction-utilization.html

Just take the top 30 of that chart and learn those. The x86 contains a lot of instructions that no one needs to worry about. Things related to the ancient segment mode or x87 floating point, OS-privileged instructions (context switching, HLT/LIDT/etc.), AMD-only 3DNow, etc.

The ISA is not the hard part anyway. Dealing with the ABI (System V on Linux) to interface with C/C++ code, the kernel syscall interface, position independent code/executable (PIC/PIE) are somewhat bigger concerns and are going to apply to RISC as well.

When you add prefetching (that is, compare against the middle element and fetch both the middle of the left half and the middle of the right half ahead of time) you are essentially doing radix-4 search, just with fewer actual comparisons.

(You can prefetch k layers ahead for radix-2^k search, but searching in small arrays will become more expensive this way.)

I didn't benchmark it, but I guess on mid-to-large arrays it would actually work somewhat slower than prefetching because it is more instruction-heavy, and, more importantly, prefetches are "cancelable": if the memory bus is too busy with actual requests, they will be skipped, while in explicit radix-k search you would have to wait for all (k-1) elements even if the middle element happened to be already cached and you already know which elements you need next.

That said, it could probably work with small arrays where caching is not a concern and especially if you optimize for latency and not throughput. You can also try to do the comparisons with SIMD (Wojciech Mula tried something similar and got a small boost: http://0x80.pl/articles/simd-search.html).

I would expect it depends on where the lookup table enters the picture. If the table lookup is at the end of a dependency chain, it's not going to stall anything and then you're putting less strain on the branch predictor/reordering machinery.

The article is using pext, which is different from a regular table lookup. While it has horrible latency and overhead on older chips, on Zen3 it appears to decode to a single uop with a latency of 3, and on Haswell it also decodes to one uop with a latency of 3. So it's not as bad as a regular table lookup as long as you're on a new enough processor.

It's also possible to do vectorized lookup table loads if your lookup table is small enough and you have a modern CPU, see http://0x80.pl/notesen/2016-03-13-simd-lookup-pshufb.html and http://0x80.pl/notesen/2019-02-03-simd-switch-implementation.html (there's a more generalized version of this I can't remember the URL of...)

use the popcnt instruction or the popcnt intrinsic function.

It counts how many bits are set to 1, you’re looking for 0.

You can also cast it into a uint64_t integer and do an equality test. There might be a way to use fused multiply add.

Also are you mmaping the file so you can just read it directly as a single buffer? You should be able to madvise to free pages after they’ve been checked.

PUSHFB can also be used. http://0x80.pl/articles/sse-popcount.html

Essentially you want to vectorize this tho memcmp may already be vectorized and do the cpu detection.

Edit: also…
You should be able to load 15 x 256 bits and then test them.
Try VPTEST
https://www.intel.com/content/www/us/en/develop/documentation/cpp-compiler-developer-guide-and-reference/top/compiler-reference/intrinsics/intrinsics-for-intel-advanced-vector-extensions/intrinsics-for-packed-test-operations/mm256-testz-si256.html