I would love some logarithmic y axes on these plots. As is, the faster versions are basically horizontal lines, making one think whether perhaps something might be wrong with the benchmark and the compiler just optimised everything away to an empty function.<p>Sinilarly, what's going on with the performance of bisect_left_c? (Second graph.) Why is the graph completely flat at first, only to then ramp up with a perfectly straight line? If you add some measurement points in between, will it turn out the high measurement on the right of the graph is actually a measurement error?<p>If this works it would make a nice python lib.
I was inspired by this article[0] to see if I could beat the Python standard library implementation of "bisect_left" using C-extensions.<p>[0] <a href="https://probablydance.com/2023/04/27/beautiful-branchless-binary-search/" rel="nofollow">https://probablydance.com/2023/04/27/beautiful-branchless-bi...</a>
If "execution time (s)" reads 0 for one of your measured cases, I become extremely skeptical of your measurements. I get that the measurement probably just rounded down but that alongside a perfectly straight horizontal line just makes me go "what's going on here? What conclusion can I draw from this other than that the algorithm is somehow O(1)?"<p>Is the value being plotted the average time per execution? You ran each test scenario for a while, not once, I assume.<p>It's also worth considering whether you should measure against the same dataset and value every time, or have a bunch of different ones. If it's the same dataset and value it's possible you're priming the branch predictor tables, or worse, favoring one algorithm by accident due to the layout of the data.
If anyone has the time & energy to put into figuring out a production quality open source version of this, one place that could benefit is numpy's searchsorted function<p><a href="https://github.com/numpy/numpy/blame/main/numpy/core/src/npysort/binsearch.cpp">https://github.com/numpy/numpy/blame/main/numpy/core/src/npy...</a>