#9 is especially stupid because it's so context-dependent. SSE4 gives you a popcount instruction, for example, which would be easily the fastest way to do this, if available.
Yes, but without that instruction, the algorithm mentioned by recruiter is really the quickest way. I coded chess algorithm in the past and this was exactly the method top chess open-source engines used. But imho it is hard to figure that out without prior experience with this problem.
I coded chess algorithm in the past and this was exactly the method top chess open-source engines used.
Your statement is rather vague in time, but for example Stockfish did certainly use the hardware intrinsic at some point. Some of the top closed source engines were using SWAR approaches mixed with loops (when the expected population is 0).
The answer is very dependent on the exact HW architecture and the cache pressure in the surrounding algorithms.
No, the algorithm mentioned by recruiter is among the slowest ways.
I recently tested different approaches. I’ve been working on some code that downsamples large set of 1 bit voxels to get shades of gray on the edges. For that, I had to counts gigabytes of those bits as fast as possible.
Advanced manually-vectorized SIMD code worked several times faster, esp. on the hardware that supports SSSE3 or XOP instructions.
And even when the hardware doesn’t have SSE4, doesn’t have SSSE3, doesn’t have XOP — SSE2-only backup plan is still faster than lookup tables. Here’s the code: http://stackoverflow.com/a/17355341/126995
Yep. Went and tried the lookup method against a 5 step parallel shift and add method (which is the fastest bitwise way I know of without, and the lookup is ~5% faster than the bitwise way.
Which is why you ask follow-up questions instead of just giving the optimal solution for UltraSPARC and rejecting what would be the optimal solution for other CPUs.
