I think the reason it's slower for you is that the CPU pipeline is starved for data... even when it is in the same cache line.
Since we are geeking out on binary search on a Saturday night, here's an approach I developed for traversing multiple binary trees in parallel with SIMD instructions, no branches and data prefetching. It's used at Bing to calculate the document score that ranks Web search results, and traverses thousands of Machine Learning derived decision trees. It resulted in a 4x speedup over the naive approach.
Since we are geeking out on binary search on a Saturday night, here's an approach I developed for traversing multiple binary trees in parallel with SIMD instructions, no branches and data prefetching. It's used at Bing to calculate the document score that ranks Web search results, and traverses thousands of Machine Learning derived decision trees. It resulted in a 4x speedup over the naive approach.
http://web.cse.ohio-state.edu/~ren/papers/CGO13_BinRen.pdf