Branchless wc in C

Runtimes for counting a 10,000,000 word file.
Averaged over 100 runs

Example call of the original program

Example call of the optimized  program

A couple days ago I was inspired by this post: https://www.greyblake.com/blog/branchless-rust/. The author explains how branch prediction works and how incstruction pipelining can be improved if the correct branch is predicted.  As an aside, a good ago I while implemented a perceptron based branch predictor for the ESESE CPU simulator. It was based on this paper which treats branch prediction as a learnable linear seperation between take/not take paths. (cool!)

Anyways, today someone on HN posted about their C project about implementing the wc program.  They had  a big caveat about this not being LLM generated. Okay cool, good for you. No really. This is exactly how you should learn how to code.  

Anyways, after I gave some comments and got to the core logic of the word count program and realized this is a perfect example of applying branchless optimization. 

This branchless version was developed without AI assistance. Just brain and whiteboard ;)

Details

In the original program, the file was access by repated fgetc calls. Since file IO is the obvious bottle neck I adjusted the original main.c to load the input file into memory. Now the actual algorithm can be compared. 

In the original code, the logic is an implicit branched edge detector over words.  

To optimize you need to realize the input stream provided by isalnum() is really a stream of 0's and >0 values. You can edge detect the transition from 0 values (spaces) to words (>0) by using a 2 sample kernel as a psudo-filter over a 2-sample sliding window. 

Adding the kernel to the window gives us 4 cases: