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

科技回声

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

GitHubTwitter

首页

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

资源链接

HackerNews API原版 HackerNewsNext.js

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

Safety vs. Performance. A case study of C, C++ and Rust sort implementations

172 点作者 bubblehack3r超过 1 年前

12 条评论

Voultapher超过 1 年前
Author here, I've spent the last 1.5ish years researching sort implementations. While developing a test suite and understanding prior art, I've accumulated a list of results and properties I thought would be insightful to share. Feel free to ask me questions.
评论 #37782463 未加载
评论 #37783209 未加载
评论 #37782628 未加载
verdagon超过 1 年前
&gt; Often safety and performance are characterized as a set of zero sum tradeoffs, yet often it&#x27;s possible to find better tradeoffs who&#x27;s holistic properties improve upon a previously seen &quot;either or&quot;.<p>There is truth in this, but I&#x27;m not sure whether the reader can&#x2F;should extrapolate this to larger situations (not that the author implied we should, but it was my first interpretation).<p>We know that in certain situations, borrow checking works really well and allows us to guarantee safety with minimal friction and no overhead.<p>But there are other cases where safety and performance _are_ in contention, and we must choose one or the other. Anyone who has been forced to satisfy the borrow checker by using a .clone(), using Rc, or refactoring objects into a hash map and referred to them by an ID (that must be hashed to exchange with a reference), has felt this contention. In <a href="https:&#x2F;&#x2F;verdagon.dev&#x2F;blog&#x2F;myth-zero-overhead-memory-safety" rel="nofollow noreferrer">https:&#x2F;&#x2F;verdagon.dev&#x2F;blog&#x2F;myth-zero-overhead-memory-safety</a>, I concluded that there&#x27;s no general approach that always has zero overhead, at least not yet.<p>So perhaps the best interpretation from this study is that often, for small enough programs&#x2F;areas, there is no conflict between safety and performance.<p>For larger programs with more complex requirements and data interrelationships, the question becomes much more interesting.<p>&gt; I see no reason why a straight port from Rust to C++ wouldn&#x27;t have been possible while satisfying their requirements.<p>Like the author, I also don&#x27;t see a reason for this, but I&#x27;ve never tried myself. I&#x27;ve always thought that with the restrict keyword, one could make any C++ as performant as any Rust code. Perhaps something else got in the way there.
评论 #37785024 未加载
评论 #37783318 未加载
评论 #37782272 未加载
thaliaarchi超过 1 年前
I&#x27;m surprised to see that the author&#x27;s ipnsort is not published on crates.io, even though it performs at first or second place on most of the benchmarks for unstable sorts and it passes all the safety and correctness criteria, all while also being able to deterministically panic to inform the user of a logic bug in their comparison function.<p><a href="https:&#x2F;&#x2F;github.com&#x2F;Voultapher&#x2F;sort-research-rs&#x2F;tree&#x2F;main&#x2F;ipnsort">https:&#x2F;&#x2F;github.com&#x2F;Voultapher&#x2F;sort-research-rs&#x2F;tree&#x2F;main&#x2F;ipn...</a>
评论 #37783432 未加载
fluoridation超过 1 年前
&gt;To me the Results across all tested implementations is indicative of a pervasive mindset in the C and C++ world, that argues it&#x27;s the users responsibility to be careful, even if that has been proven impossible at scale.<p>I mean, even if the sort function is implemented in such a way that it&#x27;s impossible to use it incorrectly, the user is still programming in C&#x2F;++. Yes, all else being equal, the harder it is to introduce bugs the better, but if the user is not careful they will shoot themselves in the foot one way or another.
评论 #37783487 未加载
voxl超过 1 年前
This work is significant enough that it should be published in an academic venue.
评论 #37783928 未加载
评论 #37794149 未加载
gpderetta超过 1 年前
It is an interesting comparison, but it would be nice to compare the same algorithms to understand the cost of each language (genericity of c++ over C, safety of rust over C++).
评论 #37794172 未加载
devit超过 1 年前
&quot;Unspecified order&quot; seems a poor guarantee.<p>I think a sort implementation should return elements in an order consistent with a subset of the comparison calls it makes, and that subset should be such that it fully determines the order.<p>An even better guarantee is that the subset should be the whole set of comparison calls.
评论 #37785142 未加载
评论 #37784802 未加载
评论 #37784732 未加载
评论 #37784722 未加载
dgb23超过 1 年前
Interesting work!<p>I haven’t ever even thought about the issues laid out here in such detail.<p>At first I was scratching my head, but the strength of a sorting guarantee actually might matter a lot more than I first thought.<p>Assuming that something is sorted can have quite substantial effects on code. It’s a very strong assumption in a sense.
jithesh超过 1 年前
What is @stjepang (author of Rust&#x27;s unstable sort, and many other contributions) doing now?
dahfizz超过 1 年前
TLDR: C is fastest, Rust is safest.
评论 #37782320 未加载
评论 #37782228 未加载
评论 #37782278 未加载
评论 #37782780 未加载
评论 #37782851 未加载
评论 #37782258 未加载
评论 #37782132 未加载
natsucks超过 1 年前
can we just move on from C&#x2F;C++ already
评论 #37782334 未加载
评论 #37785152 未加载
评论 #37783751 未加载
评论 #37783170 未加载
评论 #37782656 未加载
xeonmc超过 1 年前
Zig comptime will yield the fastest result ;P
评论 #37782749 未加载
评论 #37782490 未加载