eg, If you measure it, tree performance will often be much improved by storing slightly less than one cache line's worth of data at each node. The CPU can pipeline and predict the shit out of the linear search at each node to the point that all the theoretical O(1) or O(log N) lookups in the world get demolished by a CS101 scan of the array. This makes a relatively good general use cache aware data structure because small collections tend to fit into a single cache line while large data structures have relatively few pointers to chase.
Of course as the OP demonstrates, optimizing for your specific use case can yield even more dramatic improvements.
If I'm getting called a trillion times on a hot-path, but only a million of those times I'm receiving a module name (search string) I'm interested in, then it behooves me to have the fastest negative match logic possible.
As it stands, the final assembly version can negative match in about 6 cycles, prefix match in about 14 cycles, and worst-case false-positive negative match (where three strings need to be compared, but there is no match) in 21 cycles. The CPI for the final routine is reported as around 0.266, which is pretty close to the optimal of 0.25.
I think you'd struggle to meet that performance with anything that relies on pointer chasing. I do comment on the likelihood of a log(n)-based algorithm overtaking performance when the data set is large enough here: http://trent.me/is-prefix-of-string-in-table/#other-applicat...
This particular use case wasn't intended for prefix matching against large data sets though, and thus, wasn't optimized for that.
Some constructive feedback: move that information up to the "Goal" section, maybe with a motivating example. The fact that the set size is <= 16 is important to know before discussing cycle counts.
> A SIMD-friendly C structure called STRING_TABLE was derived. It is optimized for up to 16 strings, ideally of length less than or equal 16 characters.
(Not a naive binary search using strcmp, but the trick where you find the lower and upper bounds given index 0, refine it using index 1, etc. until your input is exhausted.)