Hacker News Reader

Comment by zephen | Hacker News Reader

I was wondering the same thing.

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).

View on HN

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]

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.

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.

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.

> 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.

Reply on news.ycombinator.com