The function to do the same for a byte is... what? 3 or 4 lines long in C? I guess it takes a couple of temp variables, though, which may dissuade some devs.
That's not "A lookup table is faster than a native bit reversal instruction."; that's "There's no portable way to make the compiler emit a native bit reversal instruction, and a lookup table is (presumably) faster than a couple dozen instructions to do it manually (at least on most target architectures).".
Which boils down to add, add, cmp, cmov on x86. It might save some cache traffic, but the cache traffic is less code since it's only a mov. The version that's code instead of lookups probably exacerbates register pressure problems in large programs? I don't have good intuition for which would be more efficient in practice.
I mean, I'm not skilled enough in those ISA extensions to stick my neck out. It's not totally obvious to me that there is not some shuffle or permute facility that can load 64 bytes at a time from LUTs.
> It's not totally obvious to me that there is not some shuffle or permute facility that can load 64 bytes at a time from LUTs.
You are talking about vgather and/or vscatter, which are well known to be very slow AVX2 or AVX512 instructions.
Maybe a future CPU will make these instructions high performance. But no modern 2023-era CPU has a high-speed vgather.
Like: the vgather does one-at-a-time slow. You basically lose parallelism even if the vgather instruction describes what you want to do, it's not an effective parallel operation today (and may never be)
--------
Pshufb as a 4-bit LUT is an exception and is effectively a high speed (but very very small) lookup table. Like every cycle 64 bytes at a time fast.
You are limited by the 16-byte lookup size (aka the size of an SSE register), maybe a bit bigger if there are new instructions I dunno about.
Although it can't be easily vectorized, it can be pipelined, that can help both hide the access latency and keep the lookup table hot. The code is not going to be pretty thorough.
The example code is a 256-byte lookup table, meaning the original example won't work with Unicode either.
In fact, I'm pretty sure that Unicode cannot be solved with a lookup table due to its variable length, but maybe you can prove me wrong? (Assuming UTF8 here)
Unicode does have a limited space, but it cannot be stored practically in single table. It currently runs up to 0x323AF, a bit over 200k, and most of the characters of course don't have a lower/uppercase mapping. The implementations I've seen do a few comparisons and then delegate to a table.
But: horses for courses. If you have to normalize a lot of Latin-1 text (such transform case, or strip diacritics), you can probably write some vector instructions that runs circles around a simple LUT. But it's not going to be as easy.