Hacker News Reader

"Of course, I also cheated. I realised that my code spent a huge amount of time counting the set bits on a byte. I could implement that on my side, or get a CPU that implements that as a single instruction."

Why not use a lookup table to memoize the results? There are only 256 possible cases for a single byte. Or is this still considerably slower than a single processor instruction on the i7?

View on HN

With my limited understanding of processors, it seems like a lookup table would be significantly slower. The command itself seems like it can be executed very quickly in hardware. More importantly, the command can operate directly on the registers. Memoizing, at best, would require loading the relevant value from cache. Not only is this slower then registers, but it also pushes 256 bytes out of the cache. Additionally, using a single command may allow the cpu to do some form of out of order execution to get additional benefits.

Reply on news.ycombinator.com