How does this packing/unpacking scheme compare to just using a lookup table?
Ironically, x86 has an instruction, XLATB, that does almost exactly this (looking up a byte in a 256-byte table) -- but using it is actually slower than using an equivalent MOVZX RAX,AL; MOV AL,[RBX+RAX] sequence on modern CPUs.
Obviously, it partly depends on the implementation machine, how big a hole the tables blow in your cache, how fast the multiplies are, etc.
But it probably also hugely depends on the format that you want your trits in. If you use them unpacked, e.g. one trit per byte, then even if you're using tables, you still have to do a lot of manipulation (e.g. either shifting and oring, or having different tables, and a table lookup per trit and adding together to get the binary).
ETA: If you're prepared to waste a byte per entry so that entries are 4 bytes wide, on x86 you can use effective address calculation to do the multiplication for you, letting you decode 3 trits in 1 CPU instruction:
MOV EAX,[RBX+RCX*4]In any case, if there were 3 trits, I'm not sure what the practical difference between a single table you describe and 3 different 256 byte tables, again depending on the architecture.
Yes a single table would have better cache effects for a single read, but presumably? you're doing a lot of reads in an unpacking phase.
You can do a full unpacking-via-lookup with a uint16[256] and then do bit shifting and masking to extract the individual trits, but using an extra byte in each entry (or 3 tables) would let you extract with just two shifts.
This starts to vary a lot with the microarchitecture, and there’s the added dimension of SIMD vectorization, so accurate timing in a realistic context becomes important.
But then, I'm pretty sure you haven't said anything different than what I said in the great-great-grandparent of your comment, other than slightly fleshing it out for a couple of particular scenarios.
But you haven't covered the packing, which is the primary thing I was suggesting you might need multiple tables for if you really wanted to use tables and really didn't want to do shifting or multiplication.
Whoops, of course!
I think storing 5 consecutive bytes per entry in a size-1280 table will still be faster than 5 single-byte lookups in separate size-256 tables, since it only requires 1 (unaligned) dword MOV and 1 byte MOV.