13 ms·
Safety vs. Performance. A case study of C, C++ and Rust sort implementations
- dahfizz 3y agoTLDR: C is fastest, Rust is safest.
- xeonmc 3y agoand C++ would be easiest?
- morning-coffee 3y agoeasiest to blow your foot off with, yes.
- belter 3y agoeasier to blow your whole leg off according to Bjarne Stroustrup
- huhtenberg 3y agoIs the plussest.
- Voultapher 3y agoI'm kind of sad that's your takeaway :(
- verdagon 3y agoI don't think the article made that conclusion? I see this in there: > As seen in the benchmarks, the current Rust standard library unstable sort implementation outperforms the C++ standard library counterparts And I can't find any generalizations like that from the author, though I may have missed it.
- hawski 3y agoYou're talking about C++, he is talking about C.
- Ar-Curunir 3y agoLiterally the second paragraph : “ Overall no correlation between performance and safety could be found, nor whether safe or unsafe internal abstractions are used.”
- kobalsky 3y agoYou could replace Rust for almost any language in that assertion and it would be true, so it would be good to clarify that Rust does not trail of behind C much, and it's even faster than C on 4 out of 14 tests.
- queuebert 3y agoI feel like these tests are really testing the ability of the language to give hints to the compiler in its attempt to generate efficient machine code.
- dralley 3y agoThe comparison involved different and not completely overlapping sort algorithms. If you want to say this you have to first prove it's not just the algorithm.
- ape4 3y ago"As seen in the benchmarks, the current Rust standard library unstable sort implementation outperforms the C++ standard library counterparts. "
- Voultapher 3y agoAuthor 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.
- teunispeters 3y agoGlad to C doing so well at what it's best at - efficiency and size. I worked in embedded space for years. Rust does not suit that environment. Different tools for different needs! I appreciate this, as looking for better tools in embedded space is welcome. Just pity that so many of them come with so many dependencies and large library sizes.
- morning-coffee 3y ago> I worked in embedded space for years. Rust does not suit that environment. It seems to be getting better though. For example... https://tweedegolf.nl/en/blog/65/async-rust-vs-rtos-showdown https://tweedegolf.nl/en/blog/65/async-rust-vs-rtos-showdown
- AlotOfReading 3y agoHonestly, Rust is a lot closer to ready in the embedded space than you probably think. It's perfectly adequate to replace most of the embedded C++ out there today and coexist with the remaining C.
- uxp100 3y agoI kept hearing rust was ready for embedded pretty early on (like 2018), and I fooled with it for a bit in 2021 and it definitely was not, on the platform I chose at least. Updating compiler version (minor update) broke existing code, I was relying on one guys hobby to support the relatively popular (though fading) mcu I pulled out of my parts bin. What about rust today makes it suitable for replacing some code but not all of it? What’s better, what still isn’t there yet? I guess from my limited experience register fiddling ergonomics in rust were miserable, but I was blessed with working with an extremely safe and ergonomic set of c macros at work (you could do something like rmw(i2s, clockconfig, enable, set) and know if it compiled that such a value corresponded to a valid value in a field that existed in such a register in such a peripheral) and I know some vendors provided c “pac” equivalents that were pretty sloppy and error prone, if still nicer than all the punctuation needed to set a bit in a register in rust. How is HAL quality for popular platforms? How much does that matter? The stm provided c HAL is extremely limiting in my experience, anything fancy requires bypassing it, and I worked places without touching the vendor provided libraries ever but I guess having it as an option for popular platforms is important.
- verdagon 3y ago> 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". 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). We know that in certain situations, borrow checking works really well and allows us to guarantee safety with minimal friction and no overhead. 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 https://verdagon.dev/blog/myth-zero-overhead-memory-safety https://verdagon.dev/blog/myth-zero-overhead-memory-safety, I concluded that there's no general approach that always has zero overhead, at least not yet. So perhaps the best interpretation from this study is that often, for small enough programs/areas, there is no conflict between safety and performance. For larger programs with more complex requirements and data interrelationships, the question becomes much more interesting. > I see no reason why a straight port from Rust to C++ wouldn't have been possible while satisfying their requirements. 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.
- wredue 3y agoSorry, but you are just assuming that the borrow checker is an authority of safety, when, even stated by rust lang developers, it is not. The borrow checker is known to be far in to “overly cautious” territory.
- verdagon 3y agoI made no assumption like that, though do let me know if I've said something that could be interpreted that way. Rather, I think that the static analysis we see in today's languages just isn't powerful/flexible enough to reason about safety in a lot of the patterns that we know are safe. I'm also uncertain if it can _ever_ catch up to what we know to be safe, but I wouldn't be surprised if we get there in a few hundred years. For example, borrow checking is a step forward and can guarantee safety, but does nothing about the other half of correctness, specifically liveness. [0] Linear types (like in Austral [1] and Vale's higher RAII [2]) can help guarantee liveness, but we still have further to go. Both are based on single-ownership (in the C++ sense) like Rust, which introduces errors that e.g. Haskell would not. But even Haskell (and LiquidHaskell which has linear types) don't go far enough; Coq goes even further. So yes, like you say, we have a long way to go w.r.t. correctness, even past the borrow checker though it is a big step forward. To my original point though, even all of these tools put together will put restrictions on a program such that it sometimes won't be allowed to take the most optimal approach. Perhaps someday we'll get there! [0] https://en.wikipedia.org/wiki/Safety_and_liveness_properties https://en.wikipedia.org/wiki/Safety_and_liveness_properties [1] https://austral-lang.org/linear-types https://austral-lang.org/linear-types [2] https://verdagon.dev/blog/higher-raii-7drl https://verdagon.dev/blog/higher-raii-7drl
- natsucks 3y agocan we just move on from C/C++ already
- jimbob45 3y agoWe can't even move past FORTRAN and Cobol, let alone C/++.
- petschge 3y agoWhy would we want to move away from them? Fortran is VERY good at what it is intended for (implementing formulas in code).
- bee_rider 3y agoFortran added the most important OO feature, methods bound to types, around 2003. Therefore, it is a more modern object oriented language than C++, in the sense that the object oriented features were Frankensteind on more recently. So maybe we could move past C++ to it.
- mgaunard 3y agowhy? is there a real alternative? (no there isn't)
- LAC-Tech 3y agoZig is getting there. Very ergonomic at doing the kind of bit bashing stuff people might reach to C for. It's about as easy to use C libraries in Zig as it is in C++.
- fluoridation 3y ago>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. 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.
- prosqlinjector 3y ago> that argues it's the users responsibility to be careful, If you try to sort with a function that's not a valid comparison operator, I don't know what to tell you. What should it do? Semantics cannot be validated at compile time. The best that can be done is to annotate the function as "yes this should have the right semantics" as is done in Rust and C++ concepts, but that's still not a guarantee.
- fluoridation 3y agoThere are still ways for a sort function to not work properly with the comparer, even if the criterion is correct. As mentioned in the article, the comparer might have internal state that the sorter duplicates during intermediate steps, thus breaking assumptions made by the caller. The example the article gives is a comparer that increments a variable each time it's called, to count the number of comparisons. Depending on how this is done and how the sorter is implemented, copying the comparer may break this behavior.
- deleted 3y ago[deleted]
- jeffbee 3y agoIn C++ your relational operators can return std::partial_ordering etc which is a bit more semantically meaningful, for the reader and the compiler.
- xeonmc 3y agoZig comptime will yield the fastest result ;P
- j-pb 3y agoBut will it be correct and not encounter a compiler bug? ;P
- littlestymaar 3y agocompiler miscompiles and outputs a noop Fastest program ever.
- 1980phipsi 3y agoThat would only work for data known at compile-time...
- wredue 3y agoAny language that reifies types at compile time should have reasonably similar performance characteristics given similar code. Zig, though, should still end up being easier to make faster simply because it’s not RAII heavy, and doesn’t push you over in to dynamic dispatch whenever it feels like it. The reason I responded to you though, is because comptime is not strictly for performing business logic at comptime. Most comptime uses are for the reification of code.
- insanitybit 3y agoWhat is the connection between RAII and dynamic dispatch?
- wredue 3y agoI don’t believe I implied that there was one? Dynamic dispatch is slow for usually no reason. RAII encourages patterns that are slow.
- gpderetta 3y agoIt 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++).
- Voultapher 3y agoFor what it's worth, rust_std_unstable is mostly a port of cpp_pdqsort_unstable.
- dgb23 3y agoInteresting work! I haven’t ever even thought about the issues laid out here in such detail. At first I was scratching my head, but the strength of a sorting guarantee actually might matter a lot more than I first thought. Assuming that something is sorted can have quite substantial effects on code. It’s a very strong assumption in a sense.
- thaliaarchi 3y agoI'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. https://github.com/Voultapher/sort-research-rs/tree/main/ipnsort https://github.com/Voultapher/sort-research-rs/tree/main/ipn...
- Voultapher 3y agoIt's designed as the new `slice::sort_unstable` stay tuned.
- kibwen 3y agoIs there a PR or internals discussion that we can follow?
- Voultapher 3y agoNo PR yet, still have to do some things before that. Sorry for being so vague.
- jithesh 3y agoWhat is @stjepang (author of Rust's unstable sort, and many other contributions) doing now?
- deleted 3y ago[deleted]
- voxl 3y agoThis work is significant enough that it should be published in an academic venue.
- insanitybit 3y agoWhat would the purpose of that be? Genuinely wondering as a very non-academic person. Surely academics can just read this document?
- davrosthedalek 3y agoDiscoverability. They will not find this document. If it's in a journal (or maybe only on the arXiv), it's much much easier to find.
- insanitybit 3y agoAh, got it, thanks.
- Voultapher 3y agoYou are not the first person to tell me that. Honestly I'd like to but the limiting factor is time. I'm doing all this in my personal time.
- voxl 3y agoIf you don't have the time then it is what it is, though to be honest you've basically written the paper already in Markdown. I would guess the bigger issue is that you don't really get a lot out of it, and reviewers could potentially give you a hard time + travel time.
- devit 3y ago"Unspecified order" seems a poor guarantee. 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. An even better guarantee is that the subset should be the whole set of comparison calls.
- deleted 3y ago[deleted]
- wffurr 3y agoIs there any existing sort implementation that does this? The closest I can think of is stable sorts which aren’t quite what you described.
- Someone 3y ago> 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. > An even better guarantee is that the subset should be the whole set of comparison calls. For consistent comparator functions, all decent implementations “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”, because that’s the definition of sorting. They also have the added feature that that subset is the full set of the comparison calls they make. Why would they make more calls than necessary? For buggy comparator functions, once you hit even a single inconsistency it can’t be the whole set of comparison calls. Also, for a buggy comparator function, you can’t count on the comparator function to be antisymmetric, so it may both say that a < b and b < a, and you can’t even count on it returning the same value when called twice with the same arguments (a comparator could return a coin flip, for example) However, if you’re willing to make all the n × (n - 1) comparison calls, it seems reasonable to me that you can find a subset that defines an ordering. I can only think of an heuristic argument for that, though, not of a proof. That argument is that there are n! possible orderings you can return, and each has a ‘chance’ of 1/2^(n-1) of only containing links that are consistent with the comparator function, and the former is way larger than the latter. Given that chances are at least one would be consistent, and define the order. However, I don’t see what good that would do. If your code can detect that the comparator function is buggy, it’s better to signal that than to spend time finding some semi-random ordering that partially satisfies the comparator function.
- deleted 3y ago[deleted]