TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Beating Bisect with Branchless Binary Search

62 点作者 juliusgeo大约 2 年前

7 条评论

tomsmeding大约 2 年前
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&#x27;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.
评论 #35766049 未加载
juliusgeo大约 2 年前
I was inspired by this article[0] to see if I could beat the Python standard library implementation of &quot;bisect_left&quot; using C-extensions.<p>[0] <a href="https:&#x2F;&#x2F;probablydance.com&#x2F;2023&#x2F;04&#x2F;27&#x2F;beautiful-branchless-binary-search&#x2F;" rel="nofollow">https:&#x2F;&#x2F;probablydance.com&#x2F;2023&#x2F;04&#x2F;27&#x2F;beautiful-branchless-bi...</a>
评论 #35767518 未加载
评论 #35765385 未加载
kevingadd大约 2 年前
If &quot;execution time (s)&quot; 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 &quot;what&#x27;s going on here? What conclusion can I draw from this other than that the algorithm is somehow O(1)?&quot;<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&#x27;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&#x27;s the same dataset and value it&#x27;s possible you&#x27;re priming the branch predictor tables, or worse, favoring one algorithm by accident due to the layout of the data.
评论 #35768931 未加载
shoo大约 2 年前
If anyone has the time &amp; energy to put into figuring out a production quality open source version of this, one place that could benefit is numpy&#x27;s searchsorted function<p><a href="https:&#x2F;&#x2F;github.com&#x2F;numpy&#x2F;numpy&#x2F;blame&#x2F;main&#x2F;numpy&#x2F;core&#x2F;src&#x2F;npysort&#x2F;binsearch.cpp">https:&#x2F;&#x2F;github.com&#x2F;numpy&#x2F;numpy&#x2F;blame&#x2F;main&#x2F;numpy&#x2F;core&#x2F;src&#x2F;npy...</a>
alexmolas大约 2 年前
I don&#x27;t know if it&#x27;s a problem on my side, but images are not rendering. Besides from that the implementation is very cool!
评论 #35765640 未加载
评论 #35765325 未加载
评论 #35765866 未加载
评论 #35765365 未加载
exebook大约 2 年前
I guess while Python interprets this branchless code it still can do some branching? Or am I missing something here?
评论 #35765321 未加载
xeromal大约 2 年前
I first read this as &quot;Eating Bistec with...&quot; and got hungry.
评论 #35765338 未加载