3 ms·

There's something wrong in the comparison calculation. To begin with, when n is exactly 2^k-1, I would expect all the functions to show k comparisons, includin

There's something wrong in the comparison calculation. To begin with, when n is exactly 2^k-1, I would expect all the functions to show k comparisons, including Skarupke's. In the plot, all the curves overlap at 64, 127 and 255 except Skarupke's which is off by 1. When n is not 2^k-1, again Skarupke's curve is nearly always 1 above the green one (lower_bound_overlap). That can't be correct: analyzing lower_bound_skarupke() and lower_bound_overlap(), I expect the former to never perform more comparisons than the latter. In fact if, after the first compare, the target value lays in the left partition, they both perform other k compares, k being log2(bit_floor(n)). However if the target value lays in the right partition, then lower_bound_overlap() performs again k compares, while lower_bound_skarupke() recalculates k based on the size of the right partition. Since the right partition can never be bigger than n/2, the new k can't be larger than the previous one. For this reason I expect the blue curve to copy the green one for all values of n right of the midpoint between two powers of 2, e.g. between 64+32 and 128, or between 128+64 and 255, and to perform better for the other values of n.

orlp 3y ago
> To begin with, when n is exactly 2^k-1, I would expect all the functions to show k comparisons, including Skarupke's. In the plot, all the curves overlap at 64, 127 and 255 except Skarupke's which is off by 1. I'm afraid you misread the plot, although I admit it is hard to see. All the curves overlap at 31, 63, 127, etc, except Skarupke's. This is the raw data: https://gist.github.com/orlp/782369f5c047447bbaa924c13bdc6b35 https://gist.github.com/orlp/782369f5c047447bbaa924c13bdc6b3... The reason Skarupke's method is less efficient is because it does not take into account that the optimal size for binary search is 2^k - 1, so it is comparing at powers of two. This causes it to need an extra comparison, note the final line of the algorithm: return begin + comp(*begin, value); None of my methods have this extra comparison at the end. For simplicity, let's analyze n = 7 for Skarupke's method: size_t step = bit_floor(length); // step = 4 // First comparison. if (step != length && comp(begin[step], value)) { // For simplicity, let's assume the comparison fails. } // Second comparison. step /= 2; // step = 2 if (comp(begin[step], value)) begin += step; // Third comparison. step /= 2; // step = 1 if (comp(begin[step], value)) begin += step; step /= 2; // step = 0, break loop // Four comparison. return begin + comp(*begin, value); Oops, that's four comparisons instead of the optimal three.
- teo_zero 3y ago
  > I'm afraid you misread the plot No, I misread Skarupke's algorithm: I completely missed the last comparison. You're right. Now, I wonder if your "overlap" algorithm, but with Skarupke's partitioning scheme, wouldn't perform even better, on average?

orlp 3y ago

> To begin with, when n is exactly 2^k-1, I would expect all the functions to show k comparisons, including Skarupke's. In the plot, all the curves overlap at 64, 127 and 255 except Skarupke's which is off by 1. I'm afraid you misread the plot, although I admit it is hard to see. All the curves overlap at 31, 63, 127, etc, except Skarupke's. This is the raw data: https://gist.github.com/orlp/782369f5c047447bbaa924c13bdc6b35 https://gist.github.com/orlp/782369f5c047447bbaa924c13bdc6b3... The reason Skarupke's method is less efficient is because it does not take into account that the optimal size for binary search is 2^k - 1, so it is comparing at powers of two. This causes it to need an extra comparison, note the final line of the algorithm: return begin + comp(*begin, value); None of my methods have this extra comparison at the end. For simplicity, let's analyze n = 7 for Skarupke's method: size_t step = bit_floor(length); // step = 4 // First comparison. if (step != length && comp(begin[step], value)) { // For simplicity, let's assume the comparison fails. } // Second comparison. step /= 2; // step = 2 if (comp(begin[step], value)) begin += step; // Third comparison. step /= 2; // step = 1 if (comp(begin[step], value)) begin += step; step /= 2; // step = 0, break loop // Four comparison. return begin + comp(*begin, value); Oops, that's four comparisons instead of the optimal three.

teo_zero 3y ago
> I'm afraid you misread the plot No, I misread Skarupke's algorithm: I completely missed the last comparison. You're right. Now, I wonder if your "overlap" algorithm, but with Skarupke's partitioning scheme, wouldn't perform even better, on average?