undefined | Better HN

0 pointsresource0x3y ago0 comments

Maybe nicer, but slower. And I'm not even sure about the former.

0 comments

Lookup tables can be slower. Do not assume that memory is fast. Even if the table is small and fits in cache, it will still be displacing other useful things from the cache. If you can have a small sequence of fast instructions using only registers and no branches, that's very likely to be faster -if not much faster- than lookup tables. Just one L1 cache miss could take much longer to resolve than computing this particular sequence of instructions.

smallpipe3y ago

The example is literally one cache line, which probably won't affect the rest of the program too much. But given the average L1 throughput, I'd bet the bitwise version is faster

Matheus283y ago

Probably faster: no memory loads, no cache pressure

cornholio3y ago

Cache pressure is not really relevant, the result can be represented in 3 bits, so the entire table can fit in three 64 bit ints. It's uglier and you still need to do bitshifts, but much easier to write.

vanderZwan3y ago

The method in the blog post uses two bit shifts and two additions. I don't really see how to beat that with this.

You can fit twenty-one 3-bit entries in a 64 bit int, with one bit to spare.

So naively you get:

   table[nlz / 21] >> (nlz % 21)

Which involves a division and a modulo. And that's assuming 63 entries in total, I'm not even trying to handle fitting the 64th entry in those three leftover bits somehow, or spread them across the three ints (again, I don't see how to do that without division).

Alternatively, each integer could contain one bit of the output, so:

   ((table[0] >> nlz) << 2) + ((table[1] >> nlz) << 1) + (table[1] >> nlz)

Which is five shifts and two additions, so more work plus lookup.

If you see another method I overlooked please tell me.

2 more replies

j / k navigate · click thread line to collapse