2
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Any discussion on how a cache deals with a 128k lookup (randomly accessed) would be rather dependent on the cache implementation. I'd personally shy away from it, both because (even if it fit inside the cache) initially loading all 128k will cause a number of cache misses (and which, if you context switch to something else and then switch back, you'd likely need to do the cache load all over again), and in addition you also have cache-based side channel attacks, which you may or may not have to worry about $\endgroup$
    – poncho
    Mar 3, 2021 at 16:39

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.