Count Uint8s

The Challenge

The challenge is to count the number of bytes equal to 127 from a stream of 250,000,000 uint8s as fast as possible.

The Solution

The base algorithm is quite simple. It processes 32 uint8s at a time, reading the data with an aligned load, cmpeq to a vector of all 127s, and then adding the mask to an accumulator (a mask lane looks like 0xFF=-1 so the accumulator grows negatively, but that can just be flipped at the end of the algorithm).

In terms of further optimizations, it is mainly messing around with tuning various knobs. I did things like software prefetching, processing 64 bytes at a time, and widening from the accumulator from an 8 bit lane vector to 16 bit lane vectors every BATCH_SIZE iterations and then 16 bit lane vectors to a final uint64 every BIG_BATCH_SIZE*BATCH_SIZE iterations.

Getting more ILP through having multiple pointers walk the stream at once is also very important. It is best to have them all be decently close together, a BLOCK_SIZE apart, and then when they get to the end of their section the whole group moves forward to the next NUM_WALKERS*BLOCKS_SIZE section. This, as opposed to something like splitting the entire stream into NUM_WALKERS huge chunks, is better for L2/L3 reuse and hardware prefetching.

Results and Thoughts

My final solution got me a score of 4339 and 14th place. The leaderboard is super tight, just a hundred points slower would put you at 30th. I think this was a pretty chill challenge that lets you focus more on tuning, unrolling, and ILP rather than a more complex algorithm like Parse Integers or Unique Strings. Overall, I would recommend this as one of the first challenges you do such that in other problems you can focus more on the algorithm and worry less about whether you have the basics down and are missing tons of performance over something simple.