Safety vs. Performance. A case study of C, C++ and Rust sort implementations
github.com
github.com
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.
It seems to be getting better though. For example... https://tweedegolf.nl/en/blog/65/async-rust-vs-rtos-showdown
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.
Could you elaborate on that? That's not something that's supposed to happen and if it has, I would like to make sure we register it in our issue tracker.
[0] https://users.rust-lang.org/t/psa-breaking-change-panic-fmt-...
https://github.com/tock/tock/blob/3a0527d586702b8ae8cb242391...
Reads and writes turn into volatile reads, so everything works out under the hood. You get the benefits of everything having good names, declared sizes, and proper typing on your register accesses. You can extend that to bit accesses as well.
Rust still has a few areas it isn't competitive in, like your hyper limited or obscure chips (e.g. 8051s, XAP), mature tooling around formal methods, and a certification story for safety critical code. People are working on these latter two issues (e.g. ferrocene) and supposedly very close to public delivery, but you know how slow the industry is to adopt new things even then.
I know several easy ways to boost ipnsort's performance by 10% but don't because they don't align with my binary-size and compile-time goals.
https://esp-rs.github.io/book/ https://github.com/avr-rust/ruduino
Rust also has a "core" library which is the absolute minimum the compiler assumes. It's well defined, well documented and how you use it is standardised. All C implementations have a similar library. For gcc you get it with -lgcc. But it is not "well defined, well documented, with standardised usage".
So I'd disagree with you. I've done it, and avoiding libc for in different C implementations is tricker than Rust.
Support outside of ARM is a bit rough, but it's improving for RISC-V and Espressif.
* The number of items being sorted must be a power of 2 (2^n).
* The number of comparisons it makes is larger than other sorting algorithms like merge sort, which will make it slower in non-parallel environments in many cases.
Bitonic sort has the advantage that it can be implemented to run in highly parallel environments (hardware, FPGAs, etc.), where the cost of comparisons is offset by them operating in parallel, so the sort completes faster even though more comparisons are occurring.
The power of 2 requirement only applies to the core kernel.
All CPUs in usage today are parallel (in 3 to 4 different ways), and bitonic sort is the best performing sort on both amd64 and aarch64.
The obvious thing is to use SIMD.
Intel publishes its own fast library for this, which isn't even in the benchmark list.
Vqsort performance on M1 is indeed about half that of AVX-512. The NEON instruction set is missing some important operations for Quicksort, including Compress and popcount of vector masks.
Regarding `ValWithPtr` my goal was to make it as close semantically as I could to the Rust code while keeping the example to a minimum to avoid distracting from the main point. If you have a concrete idea how `ValWithPtr` could have been modeled better given these criteria, please let me know.
How does this differ from implementing GC in C++ then showing how much better Java does?
No one sane would mutate elements, free memory or throw exceptions in a sort comparison function. To demonstrate fairness, you therefore need to at least also show how you could use Rust "unsafe" to break the sort, which is also a language feature you probably wouldn't want to use in this context.
No one sane would intentionally do so, but we are not talking about that. The OP has a section that links to a blog post by Danila Kutenin, which mentions `std::sort` often just segfaults if a comparator doesn't satisfy irreflexivity or asymmetry, yet such comparators were found in the wild, even passing all reviews and even tests (!) because this behavior greatly depends on the number of elements. Given this occurrence of the actual bug in user comparators, it should be no surprise that they may also contain mutations, memory deallocations and exception throws (all of which can easily be a side effect from internal routines).
It is great that rust can prevent them those additional issues, but in the grand scheme of things it is not something I lose sleep about.
1. How do you compile the C++ code? E.g. what flags do you use with GCC, clang and MSVC
2. How exactly is C++ binary run through a Rust benchmark suite? FFI?
3. Is it possible for rust code-under-test to be at any advantage here because it is run and built natively from the benchmark written in the rust itself?
What I find questionable though is the actual C++ code found in the benchmark:
1. Exception-handling code around std::sort and std::stable_sort - nobody does that. What problem are you trying to solve with this? Comparators do not throw exceptions.
2. Using function pointers for the comparators - surprising to see such code in C++ benchmark - it's very non-idiomatic and essentially making it impossible for a compiler to inline the code. std::sort is rarely used like that.
3. Passing over some magical third argument to the comparator function - ?
4. Passing over the context to the comparator "function" - I fail to see if "ctx" has been used anywhere?
5. "Making" the comparator function with make_compare_fn which in turn instantiates a lambda that, again, throws an exception from its body.
6. Storing a comparison result - why? You only need to return true or false from a comparator.
7. Modeling rust "panics" by storing a boolean is_panic plus exception-handling code plus throwing exceptions when is_panic is "ON" - why?
8. Confusing exceptions with rust panics - even if you wanted to do so, which still would be an arguable thing to do, std::abort or std::terminate is a replacement for std::panic. Not throwing exceptions and implementing the is_panic logic around it.
9. What is https://github.com/Voultapher/sort-research-rs/blob/main/src... being used for?
I think you're making a bit dishonest representation here for the reasons above. And I have not delved very much into depth nor have I covered all the code but just the fragment of it. Also, it is not quite clear how everything is put together and run because, ideally, you would want to have multiple binaries built with their representative toolchains/scripts _regardless_ of your benchmarking framework. And only then I would want to point the benchmarking framework to the respective binary to run the test. Here, it seems it's the other way around.
For ValWithPtr to make sense it needs its semantics defined. Correct C++ types can be deep copying, move only, reference counted, singleton instance etc. For example typed deep copy version without attempting any verification (link to compiler explorer): https://godbolt.org/z/3sesYY8of
If it is not helpful for you please feel free to ignore all of the above.
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, 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.
The borrow checker is known to be far in to “overly cautious” territory.
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
Yes. You literally did assume that the borrow checker is an authority, as seen here.
To be frank with you, given that zig is 95% of the way there, I feel that you are “diving off the deep end” when stating things like “Haskell doesn’t go far enough”. Haskell typing system is a nice experiment, but I don’t believe to be good in any capacity, let alone “not going far enough”.
Haskell, in my opinion, a great case of “solving a problem before even asking what the problem really is”.
Seems to have done pretty damn well IMO. Not that I've used it for 25 years, but I liked it and it introduced me to FP which totally changed how I thought of programming. I guess we have to differ on this.
Whereas I believe that concepts are tools for programmers to reach for when appropriate, functional programmers believe concepts are rules and reaching for them should be mandatory, no matter how much bullshit they force you to add for no reason other than you accepted from the get go that, for example, immutability should be mandatory.
This is a massive fundamental problem with Haskell and all language that take hardline stances on things that are better left to the users. In this regard, I’d say it’s a complete failure. It’s horrible for teaching. You need to know more than you need to know for Java just to use it. It’s horrible for research. It has hardline fundamental stances that rejects exploration, and therefor is research averse. It is horrible for industrial applications as there are massive ranges of industry that simply cannot give to the whims of Haskell for one reason or another, but probably multiple reasons cause Haskell is terrible.
Thank you. This is completely and utterly true.
Based on what? It’s almost like “functional programmer” is not a single entity controlled by Big Haskell - you are just spewing bullshit about a made up boogeyman.
Could you give some examples of such concepts? It's rather hard to understand what you mean in the abstract.
However the current state of this is absolutely terrible. A lot of work needs to be done to improve the development experience with this model if it is to be used effectively in this way.
https://github.com/Voultapher/sort-research-rs/tree/main/ipn...
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.
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.
If I'm reading the article correctly, the user can be informed at runtime with little to no performance impact. That certainly sounds preferable to returning an unsorted list (that may not even match the input).
Almost every Rust sort does this, but no C/C++ sorts do. That appears to support that author's conclusion that this is a cultural thing.
It's not possible to verify a function is a strict weak ordering without enumerating the entire domain.
The idea is that the implementation doesn't promise it will detect a strict weak ordering violation, but it has code that will detect the effects of such violations with a high probability. It's not a sampled approach, but rather as part of the small-sort a bi-directional merge is performed and if the pointers don't line up, the only explanation is a strict weak ordering violation, the result of the merge is discarded and a panic is raised.
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.
> 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.
It is absolutely possible to write a comparator that evaluates things in a circle e.g. 1<2 && 2<3 && 3<1.
At that point it is impossible to "do your best" there is no correct answers only wrong ones. (You have to violate a comparison here)
Rather, it can ask for two comparisons and act according to the results (e.g. it learns that 1 < 2 and 2 < 3 and returns [1, 2, 3]).
This makes the output unspecified in general, but it will be consistent with the information received and the calls made even if the comparator doesn't form an ordering, which is what one would expect.
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.
> 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.
“ Overall no correlation between performance and safety could be found, nor whether safe or unsafe internal abstractions are used.”
No one will ever take it seriously.
C++ yes, there is no real reason to use C++ anymore outside of big libraries that require it.
Some of us like C++ because it gives us a the freedom to work at the lowest level when we need to, while also giving us plenty of higher level APIs for most day to day situations, while having great compatibility with tons of software that is already out there. It seems we are at peak Rust fanboyism these days. I have nothing against Rust but the idea that Rust has already replaced C++, or will certainly do so in the future, is ludicrous. C++ has a ton of activity in the standards committee and has very interesting developments like cppfront. It is a vibrant community that continues to reinvent itself and in all likelihood is a lot larger than the Rust community.
Mixing of these two is why nobody really takes C++ seriously anymore.
If C++ dissalowed C style memory accessors, removed <reinterpret_cast> and everything was done through stdlib and smart pointers, it would probably be above Rust right now. A good portion of Rust borrow semantics were already built to the smart pointer system.
But with mixing, you not only have to deal with all the typing syntax, you also have no idea if you are just going to segfault because there is a C style dereference somewhere to a null pointer.
Hell everything only works by interoping with those languages given the OS is written in one of them.
Fastest program ever.
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.
Dynamic dispatch is slow for usually no reason.
RAII encourages patterns that are slow.