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.
> Often safety and performance are characterized as a set of zero sum tradeoffs, yet often it's possible to find better tradeoffs who's holistic properties improve upon a previously seen "either or".<p>There is truth in this, but I'm not sure whether the reader can/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://verdagon.dev/blog/myth-zero-overhead-memory-safety" rel="nofollow noreferrer">https://verdagon.dev/blog/myth-zero-overhead-memory-safety</a>, I concluded that there'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/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>> I see no reason why a straight port from Rust to C++ wouldn't have been possible while satisfying their requirements.<p>Like the author, I also don't see a reason for this, but I've never tried myself. I'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.
I'm surprised to see that the author'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://github.com/Voultapher/sort-research-rs/tree/main/ipnsort">https://github.com/Voultapher/sort-research-rs/tree/main/ipn...</a>
>To me the Results across all tested implementations is indicative of a pervasive mindset in the C and C++ world, that argues it'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's impossible to use it incorrectly, the user is still programming in C/++. 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.
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++).
"Unspecified order" 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.
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.