[akoboldfrying]

You can have a single 3x256=768-byte table -- just multiply the input byte by 3 to get the offset into the table, and read out the 3 trits (1 trit per byte) beginning at that offset.

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]

[zephen]

There are 5 trits.

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.

[moregrist]

You wouldn’t need five tables. Each trit takes up two bits when unpacked into 0,1,2 values.

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.

[zephen]

I agree.

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.

[akoboldfrying]

> There are 5 trits.

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.