How does table size impact table lookup speed?

Question

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?

Answer 1

To answer a specific question:

Are benchmarks simply being run in a vacuum and not in production?

Well, yes, pretty much. If you are running a serious performance test on a specific routine, you deliberately don't run anything else (because whatever else the computer is doing at the time will jitter the timing of the routine you'll looking at, making the results less reliable). And, yes, this gives an advantage to solutions which use a large amount of shared resources (such as cache space), over how they would perform in a more realistic environment.