fanf | (Reply)

From:

I was focussing on things that might matter for git's performance. So my array sizes ranged from 2^7 to 2^24, which is roughly one page worth of index entries up to the largest pack file size you might see. I was counting number of iterations because that corresponds fairly directly to page faults; when you are short on memory or when your buffer cache is empty is when index lookups can be slow. So I haven't looked at really small arrays, but certainly the secant method requires fewer memory accesses for the whole range I examined. I also haven't looked at timings, so I don't know what the relative performance is for in-memory searches. Designing a good secant method search is harder than a binary search because it relies on subtraction rather than comparison, and you have to keep two differences (between your min and max points, and your target and mid points) whereas a bisection method only needs comparisons between the target and mid points. So if you are working with an API like bsearch(3) then it will make two indirect function calls per iteration instead of one. If you can customise the code to the specific context then I expect it would be more likely to win.