5 ms·

This is a lot of words about things that probably don't matter. IMO: the bottleneck of lookup tables is concisely described as follows: 2 or 3 lookups in L1 ca

This is a lot of words about things that probably don't matter. IMO: the bottleneck of lookup tables is concisely described as follows: 2 or 3 lookups in L1 cache per cycle on modern CPUs, and 10x fewer to 500x fewer depending on how far away (L2, L3, DDR near, or DDR remote). Meanwhile, modern CPU instructions like AES, Multiply, XOR, ADD and more can effectively operate 3, 4, or even more times per clock tick regardless of circumstances. -------- Don't even talk about cache hierarchies. You are already behind at the L1 cache level due to the relatively few load/store units in modern CPU (or GPU) cores. And hitting L2 or L3 cache gets exponentially worse.

ilyt 3y ago
> Meanwhile, modern CPU instructions like AES, Multiply, XOR, ADD and more can effectively operate 3, 4, or even more times per clock tick regardless of circumstances. I don't think people are making lookup tables to adding or xoring 2 numbers...
- pjz 3y ago
  Here's an in-the-wild, long-standing example of a table used for bit reversals: https://gitlab.com/libtiff/libtiff/-/blob/master/libtiff/tif_swab.c?ref_type=heads#L249 https://gitlab.com/libtiff/libtiff/-/blob/master/libtiff/tif... 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.
  - a1369209993 3y ago
    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).".
  - jeffbee 3y ago
    What about something like https://github.com/abseil/abseil-cpp/blob/master/absl/strings/ascii.cc#L88 https://github.com/abseil/abseil-cpp/blob/master/absl/string... ? ASCII lowercase can be something like auto is_upper= (x > '@') & (x < '['); return is_upper ? x+32 : x; 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.
    - nwellnhof 3y ago
      Yes, this is a good example where LUTs are very likely to be slower, especially if you can avoid branch mispredictions with cmov.
    - dragontamer 3y ago
      Your 8-bit lookup can never be parellized, while the add/cmp/cmov is really easy AVX512 that probably auto-inlines and auto-vectorizes. I dunno, it's ridiculously a benefit to the code by my instinct. While lookup table looks pretty bad.
      - jeffbee 3y ago
        > can never be parellized 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.
        dragontamer 3y ago
        > 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.
  - robocat 3y ago
    Comedy: did you notice that the next static definition is for a 256 byte lookup table for the unreversed bits too: TIFFNoBitRevTable[256] = { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, ... 0xFF } Maybe PSHUFB/VTBL to reverse each nibble and then put the reversed nibbles together would be wayyy faster? I'm guessing portability matters here, and there is not much commercial pressure to actually optimise this TIFF library?
  - ilyt 3y ago
    Which is not simple add or xor, which is why lookup is used... I obviously wasn't talking about it. The most used one is probably sin() on CPUs without hardware math
- dragontamer 3y ago
  Between BMI instructions (PEXT, PDEP, bit reverse, least significant 1s bit, etc. Etc), AES, SHA1, add, xor, rotate, shift, and, or, not, multiply, carryless multiply and... Pshufb (4-bit / 16-byte lookup table) You might be surprised at how many operations can be done without touching the load/store units on CPUs. In my experience, it's usually worth the effort. Then again, it's a LOT of effort needed. If you are just doing things simply and easily? Lookups are almost the easiest solution. But I probably wouldn't reach for lookup tables for a performance based problem today.
jjtheblunt 3y ago
Why exponentially?

ilyt 3y ago

> Meanwhile, modern CPU instructions like AES, Multiply, XOR, ADD and more can effectively operate 3, 4, or even more times per clock tick regardless of circumstances. I don't think people are making lookup tables to adding or xoring 2 numbers...

pjz 3y ago
Here's an in-the-wild, long-standing example of a table used for bit reversals: https://gitlab.com/libtiff/libtiff/-/blob/master/libtiff/tif_swab.c?ref_type=heads#L249 https://gitlab.com/libtiff/libtiff/-/blob/master/libtiff/tif... 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.
- a1369209993 3y ago
  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).".
- jeffbee 3y ago
  What about something like https://github.com/abseil/abseil-cpp/blob/master/absl/strings/ascii.cc#L88 https://github.com/abseil/abseil-cpp/blob/master/absl/string... ? ASCII lowercase can be something like auto is_upper= (x > '@') & (x < '['); return is_upper ? x+32 : x; 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.
  - nwellnhof 3y ago
    Yes, this is a good example where LUTs are very likely to be slower, especially if you can avoid branch mispredictions with cmov.
  - dragontamer 3y ago
    Your 8-bit lookup can never be parellized, while the add/cmp/cmov is really easy AVX512 that probably auto-inlines and auto-vectorizes. I dunno, it's ridiculously a benefit to the code by my instinct. While lookup table looks pretty bad.
    - jeffbee 3y ago
      > can never be parellized 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.
      - dragontamer 3y ago
        > 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.
- robocat 3y ago
  Comedy: did you notice that the next static definition is for a 256 byte lookup table for the unreversed bits too: TIFFNoBitRevTable[256] = { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, ... 0xFF } Maybe PSHUFB/VTBL to reverse each nibble and then put the reversed nibbles together would be wayyy faster? I'm guessing portability matters here, and there is not much commercial pressure to actually optimise this TIFF library?
- ilyt 3y ago
  Which is not simple add or xor, which is why lookup is used... I obviously wasn't talking about it. The most used one is probably sin() on CPUs without hardware math
dragontamer 3y ago
Between BMI instructions (PEXT, PDEP, bit reverse, least significant 1s bit, etc. Etc), AES, SHA1, add, xor, rotate, shift, and, or, not, multiply, carryless multiply and... Pshufb (4-bit / 16-byte lookup table) You might be surprised at how many operations can be done without touching the load/store units on CPUs. In my experience, it's usually worth the effort. Then again, it's a LOT of effort needed. If you are just doing things simply and easily? Lookups are almost the easiest solution. But I probably wouldn't reach for lookup tables for a performance based problem today.

jjtheblunt 3y ago

Why exponentially?