Are there good discussions of how cache pressure impacts large 64k-ish lookup tables used in erasure coding and sometimes signature verification?
I'll focus on erasure coding in small characteristic and small degree, which gives a clean extremely performance sensitive application, and avoids off-topic side-channel discussion.
There is a classical log and exp table trick for doing multiplications in small extensions of fields of small characteristic, especially GF(2^8).
let ab_log = LOG_TABLE[a] + LOG_TABLE[b]; let ab = EXP_TABLE[(ab_log & ((1 << FIELD_BITS)-1)) + (ab_log >> FIELD_BITS)];
This works well in GF(2^4) and GF(2^8) where the lookup tables have size 16 and 256, respectively. We'd have two 128k tables of the form
[u16; 1 << 16] in GF(2^16) though, which blows the L1 cache.
We therefore always build GF(2^16) as an extension field, either of (a) GF(2^4) implemented by small multiplication tables, or else (b) of GF(2^8) implemented by a few 64k multiplication table, or perhaps another pattern. You could employ a "carry-less multiplication" instruction PCMUL instead, but it supposedly runs slower due to being designed for larger fields.
I'm confused by the anecdotal advise and benchmarks that (b) makes sense. Yes, 64k just fits into L1 cache, but any machine doing GF(2^16) work does many other tasks too, probably making (a) more robust under different applications.
In short, why do large tables win as many benchmarks as they do? Are benchmarks simply being run in a vacuum and not in production? Or is the memory bandwidth often not that starved when the CPU can pipeline everything well?