Q:

Beating binary search using CPU cache line

For educational purposes, I am trying to beat binary search using CPU cache line. 
https://github.com/nmmmnu/beating_binsearch/blob/master/improved.h
If you uncomment #define EXIT_ONLY, the search works like normal binary search, except if there are few elements, the search became linear search. 
As expected this performs faster than binary search. 
However I want to improve future, so if you comment #define EXIT_ONLY, then "small" linear search is made instead of accessing just the "middle" element. 
In theory the values for linear search must be in CPU cache line and access must be "free of charge". 
However in practice this search is way too slow than the normal binary search. 
If I hardcode CACHE_COUNT_2 to be equal to 1, then speed is comparable, but still slower. 
Note I never tried to unroll the for cycle in _linear(). 
What could be explanation of the slower execution? 
Repo with all files is here:
https://github.com/nmmmnu/beating_binsearch

A:

There are some problems in your code.   For example, this code does not consider cache line boundaries. 
while (end - start > CACHE_COUNT_MIN){
//  uint64_t mid = start + ((end - start) /  2);
uint64_t mid = start + ((end - start) >> 1);

etc...
char cmp = _linear(mid - CACHE_COUNT_2, mid + CACHE_COUNT_2, data, key, mid);

Cache lines are allocated on addresses modulo the line size.   So, to scan an entire cache line you would want to mask out the relevant bits of the address.   Even if it is a cache hit though, you will still spend cycles accessing the line (more the higher it is in the hierarchy). 
Binary search is already one of the more cache efficient algorithms for comparison based search though so improving it through cache awareness may be difficult.   You eliminate half the search space at each iteration, which already avoids most cache misses, and it's a linear space, and you increase locality with each search.   Prediction can even hide some of the misses. 
You may want to use perf to sample performance events in your code.   Also, to get an idea of how cache awareness is sometimes used to optimize algorithms, you might also want to take a look at some of the existing aware ones like hopscotch hashing.