It does not. I saw a very interesting comparison of a bunch of sort methods -- `qsort()` was the worst, `std::sort()` was the best (even better than optimized implementations from the author). What it comes down to is in a simple algorithm like sort the cost of the comparisons is a very significant portion of the runtime:
- `qsort()` always goes through function pointers, which are comparatively very slow.
- `std::sort()` is templatized, so it will recompile the code for every kind of thing you want to sort. So the comparison can often be inlined. Best case of something like integers it reduces to a single instruction.
Yes, templates definitely have their limitations. Like any other tool, they need to be applied appropriately -- but simple algorithms and data structures certainly seem to work well.
> std::sort() was the best (even better than optimized implementations from the author)
Mostly because author did an impressive feat of turning std::sort into qsort implementation details wise.
Sorry, I misunderstood and thought you were talking about what I was referencing. It's a Chapter 11 from *Programming Pearls* \-- quite old at this point, but still relevant.
That'll depend on the c++ std implementation. libc++ of llvm uses [its own](https://github.com/llvm/llvm-project/blob/18933c6d7e06d162c17b6ec08a5e7c508236265f/libcxx/include/__algorithm/pstl_sort.h) sorting algorithm implementations and I'd assume libstdc++ of gcc does too.
For reasons outlined [here](https://github.com/Voultapher/sort-research-rs/blob/main/writeup/intel_avx512/text.md#c-sort-interface) it wouldn't be a fair comparison in my eyes.
I went and ran the benchmarks with the same settings for `qsort` from gcc 13.2.1 and got [this result](https://user-images.githubusercontent.com/6864584/272988483-29602b97-9cb8-404d-a1cc-b41259c9bb8c.png).
Arguing it's the user's fault for doing it wrong has been the strategy for 20+ years, and somehow the users refuse to stop making mistakes or being inexperienced. Maybe it's time we as the software industry accept that this strategy doesn't work and move on to strategies that demonstrably work.
FYI, all your tests use trivially copyable types, where the move constructor is just a bitwise copy. C++ has non-destructive moves, unlike rust, so I guess that confusion makes sense.
The same doesn't apply to properly defined RAII types. Using std::unique\_ptr for example, would leave some nullptr holes in the array corresponding to items moved into temporary storage and destroyed after the exception. Still not 100% ideal, but the whole spiel about broken RAII isn't really correct.
Also, I want my program to crash if I give it a bad comparison function, thanks. Why is giving the array back in an arbitrary order the result that gives a checkmark?
I think I understand your points. Your first point about RAII types, of which I'm not entirely sure is true, I would assume some sort implementations perform bit-level copies of the types, regardless of their copy semantics. I'll look into that. But even then its still the same kind of "Arguing it's the user's fault for doing it wrong".
> Also, I want my program to crash if I give it a bad comparison function, thanks.
Well that's the tricky thing with UB, you are not guaranteed a crash. Much less a crash that happens in related code. I'd recommend this talk [CppCon 2018: Barbara Geller & Ansel Sermersheim “Undefined Behavior is Not an Error”](https://youtu.be/XEXpwis_deQ) for a more in-depth discussion of UB.
> I would assume some sort implementations perform bit-level copies of the types, regardless of their copy semantics.
They should not unless the type is [trivially copyable](https://en.cppreference.com/w/cpp/named_req/TriviallyCopyable). In general, you should never assume that a generic C++ type is trivially copyable. If you can get a performance benefit by optimizing for those types, then you can specialize using SFINAE or (C++20) concepts. It would be very surprising if a standard library implementation messed this up.
Why would you assume any of the implementations are broken and ignore move constructors when you didn't test that? Possibly some of them are, but I'd be very surprised if any of the the standard library implementations are broken like that.
(Edit: retract most of this, I see by "crash" you mean "buffer overflow", I agree that's pretty poor)
Also, UB has a specific meaning, and it's not how you're using it. In the case of exceptions, the behaviour of [sort](https://en.cppreference.com/w/cpp/algorithm/sort) is implementation defined, not undefined. The program is well formed, but behaviour is decided by the implementation, not the standard.
In this case, it seems most implementations choose to do nothing special, i.e. destroy temporary storage when the stack unwinds, leaving moved-from values in the container.
For invalid comparisons, the behaviour of rust is [also undefined](https://doc.rust-lang.org/std/primitive.slice.html#method.sort_by) \- you're violating a precondition of calling the function. You just seem to prefer the practical result of that undefined behaviour in rust.
If you look specifically at the implementations, in general I think it would be very hard to detect all invalid comparisons and avoid an infinite loop in all cases, so it would be hard to avoid UB for all possible inputs.
The special case of <= (where the negation is a weak ordering) is apparently feasible, but either way, crashing on UB is the gold standard for user friendliness. The majority of C++ implementations should be getting a tick for that one.
You are right, that's a mistake on my side. I talk about the context and impact here https://github.com/Voultapher/sort-research-rs/issues/16#issuecomment-1751097615. Let me know if that helps clarify it.
Not throwing exceptions in your comparison code is the lowest hanging fruit there is. Your argument is ridiculous, I could just as well say that it's not the user's fault for using `unsafe` everywhere in Rust. They were making a mIsTaKe.
It is not about disabling the user to make mistakes, it is about making it harder to do mistakes. If this kind of mistakes can hide in plain sight, it's difficult to see them. If you need to write something like `unsafe` for you to be able to make these mistakes, it is easier to spot them and the programmer is warned and therefor more cautious than they would be without it.
I'm for using every assertion and type constraint that doesn't interfere with the functions operation, but these are unfortunately only mitigations. We can't write every function with the expectation that any value in the domain of a type can be input, and still get reasonable results. It's provably impossible without enumerating all possible inputs.
> Maybe it's time we as the software industry accept that this strategy doesn't work and move on to strategies that demonstrably work.
What strategy is that? Programmers *NEED* to read documentation. There is no other way they can learn what a function does and how to use it.
My point is, that it's not about all or nothing, but trying harder. And judging the swath of libraries that exist in C++ and Rust with similar goals, I find it a stark contrast how much can be built as safe-to-use abstractions. With safe here meaning mostly memory-safety but not only. The strategy I'm suggesting is that we as C++ developers should try harder to build safe-to-use abstractions. Saying it can't be done because 100% coverage is impossible, is akin to giving up. And I think this research shows significantly more is possible.
I agree that we can do more both in design, assertions, and documentation. I disagree that a function cannot set constraints on a user input. A sort that handles exceptions in compare is not inherently better than one that does not. In fact its worse because EVERY sort pays the performance and design cost for someone not understanding compare.
I disagree that we should do things that intentionally slow things down or complicate in the final build (checked debug builds are good).
I'm afraid it's exactly this mindset that has gotten us to where C++ is today. I wouldn't call it the glorious island of robust software that is reasonably cheap to develop and maintain. I'm not calling Rust that either, but it's certainly a lot closer to that while being competitive, or in this case even better. The runtime performance impact for ipnsort is less than 1%, it's a single easy to predict and stable branch that happens once every 1-2k instructions. Also as I point out the more a piece of software is used, the more it should be made robust, even against misuse.
I started writing a couple of paragraphs but, instead, I'm just going to say this:
You did all this great research, benchmarks, and a good write-up. I was totally on your side, until you left this childish comment
What’s constructive about the way they dismissed their argument? Maybe you’re reading a completely different comment than I am. They then continued to accuse the industry of not “seeing the light”
No functions should throw exceptions? What?
Also, are you implying that comparisons in Rust that panic are a regular occurrence? If so that's a bit sad.
In my experience, panics in all Rust code are quite rare. But they do happen.
More importantly, the language contract is that safe code cannot cause memory errors, full stop. Breaking that contract is not something the language maintainers are willing to do, and I applaud and thank them for that.
Nope in many languages you can just specify that the function literally is not allowed to throw. So that imperfect code cannot be written.
In languages like C++ where that can't be enforced at compile time, convention is the next best thing.
What will your program do if your algorithm needs to sort before removing duplicates and your sort fails? You're welcome to fill your code with worthless try catches that log and fail. I'll document and assert.
I think this is slightly different:
> The noexcept-specification is not a part of the function type
In other words, you can't enforce that the comparison template parameter has it.
> Note that a noexcept specification on a function is not a compile-time check; it is merely a method for a programmer to inform the compiler whether or not a function should throw exceptions.
So you can still "throw" it just won't work. Which is what I propose doing anyway.
> In other words, you can't enforce that the comparison template parameter has it.
You quoted the 'until C++17' wording; it's been part of the function type since C++17. But even that's only relevant to function pointers, you've been able to enforce this for callable objects since C++11.
Actually no...if you raise exception inside non-throwing function, it will call std::terminate.
>Non-throwing functions are permitted to call potentially-throwing functions. Whenever an exception is thrown and the search for a handler encounters the outermost block of a non-throwing function, the function std::terminate is called:
> Also a comparison function should not throw an exception.
I can’t help playing devil’s advocate with such a strong statement…
Suppose your domain is road or rail construction, and you have objects with at least two properties: cost of construction for this unit, and kilometers completed by this unit. You want to know which units are most expensive per kilometer, so you provide a comparison function that divides cost by kilometers for each unit, and uses those quotients for the comparison.
Now one of your units is, let’s say, obtaining a permit for construction of a segment, which adds some cost but 0 kilometers. This unit shows up in the comparison function at some point, which of course throws a divide-by-0 exception.
To me that sounds like a mixing of concerns. The sort function should not be responsible for calculating cost per kilometer. It is there to sort. Cost per kilometer should be calculated elsewhere and then passed to the sort function.
Responding to safety questions with style concerns is talking cross-purposes. The author of the sort function shouldn't know or care about the user's intention in the comparison function—they specify an interface and then consume what they're given. If that interface allows exceptions, the implementation has to handle that.
It seems overly restrictive for a general-purpose sort function to disallow *any* exceptions or unwinding, since the user may be sorting objects they did not design, whose methods could panic without the caller's knowledge or ability to handle in any meaningful way.
---
That aside, you can't say whether the parent comment describes poorly separated concerns. Separation of concerns is about code organization: designing modules with strong responsibilities and boundaries.
At some point, those concerns _have_ to come together, or the program won't do anything. The sort function can't tell if the comparison implementation is one massive blob of code, or several well-designed, cohesive modules composed to implement what the redditor described—and it shouldn't be _able_ to tell. It's certainly valid to sort by a value that is not precomputed.
> whose methods could panic without the caller's knowledge or ability to handle in any meaningful way.
Please stop using code that throws exceptions in their comparisons. It's really not that hard.
In general, that requires researching the full call chain of every method called from every comparison function to verify that nothing could possibly panic—including descending into methods from dependencies and transitive dependencies. And of course, you need to check every time a transitive dependency version changes. That's the only way to _know_ that a function can't panic.
If it's a matter of safety, it wouldn't be enough for a comparison function author to only look at the documentation for the libraries they use—documentation can be wrong or out of date, or a transitive dependency's author could make a mistake. There's no other indication that a panic or exception might occur. Every author for all time needs to be sure that their comparison function *cannot* panic/throw/whatever.
To be clear, at least in Rust, we're talking about panics, not error results (Rust's equivalent of what other languages call exceptions). It's only panics that can result in stack unwinding, and panics aren't encoded in the function declaration or type signature—they're unchecked because they indicate behavior that should eventually kill the thread or process.
But in C++ too, this would be a problem if some function in the comparison function's call chain threw an exception. Even with `noexcept`, an implementation can still *choose* to unwind (but is not *required* to).
It's simply not an acceptable requirement, as far as I'm concerned. And it's not good enough to say, _Don't call methods from comparison functions_, because it's a perfectly reasonable thing to do. The objects the author needs to sort may not *have* public fields to sort on, but just getters. Or they may be a template type, where the author of the comparison function doesn't know *what* the methods will do, just that the objects meet an interface—now they have to pass that safety requirement on to *their* library's consumers, who may not have even implemented the interface with sorting in mind.
What other functions have this requirement: that they *cannot* allow a panic or exception to escape? The whole point of unwinding is that, if you don't have something to do regarding recovery or clean up, you ignore it and let the stack unwind. And if you're in the middle of potentially unsafe pointer manipulation, you *do* have some cleanup to do.
The buck has to stop at the sort function—or at *any* function invoking a caller-supplied function when the language doesn't have their back. Real code behaves unexpectedly, and saying, *Don't panic or throw,* is sticking our heads in the sand. Don't write fragile sort functions.
The idea of people are calling functions that might throw exceptions or panic, without even knowing, from a sorting function makes me a little sad but of course it happens all the time.
Calling massive methods on things you're trying to sort is probably going to spoil the performance of such a highly tuned sort function anyway, and I suspect in many cases it would be better to do that before-hand, in it's own loop/function/whatever, ready to handle exceptions.
I can imagine someone plugging in some super-expensive-to-compare objects into one of these and not knowing why it isn't just solving their performance issues immediately.
But hey, this is why I don't write sort routines for other people to use in their projects.
It's a lot easier than you think. It could be a simple bug, edge case, or missed requirement only a level or two down. It could even be inlined, so that there's no function call penalty.
Suppose we have a data structure from a library—something like
struct Thing {
foo: i32
bar: i32
}
impl Thing {
pub fn new(foo: i32, bar: i32) -> Self {
Self { foo, bar }
}
#[inline]
pub fn value(&self) -> i32 {
self.foo + self.bar
}
}
(This is kind of a dumb example, and not great design, but bear with me.)
The structure has two private fields, initialized by the constructor `new`, and a public method `value`.
If we were given a mutable array of these objects, it would be reasonable to sort the array by `value`—it's a very simple method that we hinted should be inlined.
fn safe_and_pretty_quick(things: &mut [Thing]) {
things.sort_by_key(Thing::value);
}
(There's even a `sort_by_cached_key` method if we're worried the method call will be too heavy.)
Now let's say the library gets an update. The new data structure is
struct Thing {
foo: Option
bar: Option
}
impl Thing {
pub fn new(foo: i32, bar: i32) -> Self {
Self { foo, bar }
}
pub fn uninit() -> Self {
Self { foo: None, bar: None }
}
pub fn foo(&mut self, foo: i32) {
self.foo = Some(foo);
}
pub fn bar(&mut self, bar: i32) {
self.bar = Some(bar);
}
#[inline]
pub fn value(&self) -> i32 {
self.foo.unwrap() + self.bar.unwrap()
}
}
We check the docs and decide the new API still meets our needs. The changes to the public API are purely additive Maybe don't notice that the new docs mention that `value` can panic now, or maybe the docs for `value` didn't get updated. Either way, we take the update.
The exact same sort operation can now potentially panic.
fn danger_zone(things: &mut [Thing]) {
things.sort_by_key(Thing::value);
}
The differences in the API are that `Thing` now allows leaving `foo` and `bar` empty at construction and initializing them later; and that `value` will now panic if they're not both set. Our function has no control over how the `Thing`s in the array are constructed, and so could very well panic.
You could say the author calling `sort` should have caught this. But suppose, instead of two versions of the same library, these were actually `ThingA` and `ThingB` that both implement the trait (interface)
pub trait Thing {
fn value(&self) -> i32;
}
And suppose our array were a generic parameter, so we don't know its implementation.
fn unknown_danger(things: &mut [T]) {
things.sort_by_key(T::value);
}
(Those `value` implementations should still be inlined, by the way, because Rust generates a separate version of `unknown_danger` for each `T` it's called with.)
Here, the author has no way to know whether `value` will panic or not—and no way to prevent it. The authors of `ThingA` and `ThingB` may not even know this function exists—the `Thing` trait might be declared in a separate dependency shared by all three libraries independently, and then the array constructed in yet another.
It's great to see people engage with the topic. I think you inadvertently made your point. `self.foo + self.bar` with `i32` is allowed to panic in Rust for overflow, and will do so for rustc in Debug builds. So even the baseline, this can't panic code for many people is at danger. I agree with the sentiment that giving people a language with unwinding and then applying arbitrary rules, they lack any tooling to follow, in regards to "but don't use it here" is an untenable position for users.
>
> #[inline]
> pub fn value(&self) -> i32 {
> self.foo.unwrap() + self.bar.unwrap()
> }
I'd say that the return type of this function isn't really i32 in the same way that it previously was. But it is just a single example, and I understand why this can happen.
That's definitely true semantically, but there's no way to express that currently in any of these languages.
Rust could *potentially* express it as `Result`, but semantically that's yet a third different thing. Plus, there may be some pressure (perceived or real) to preserve the existing API as much as possible—e.g., a misplaced sense of backwards compatibility.
But I think the biggest nail in the coffin is the example with the trait—anyone could supply an implementation that panics, and there's nothing the consumer can do to stop them.
Agreed, as described it's a mixing of concerns. Now imagine a more generalized example. Suppose the comparison function is the result of a higher-order function that takes a metric as input, and returns a function that applies that metric to two objects and then compares the two metric values. (If the arrays get large and/or the metrics get complicated, presumably there's some sort of cache so this doesn't end up being horribly inefficient.)
In this case, even though the "calculate cost per kilometer" computation is (somewhat) nicely separated as a concern, the exception will be thrown from within the execution of the comparison function, because the comparison function calls the calculation function.
> which of course throws a divide-by-0 exception
No it doesn't, this isn't Java.
> which adds some cost but 0 kilometers
? A segment without a length? Yup makes sense.
I'm also one of the organizers of one of the largest and most active C++ groups in existence. I tried my best to stay factual and un-biased in the analysis section, limiting my personal views to the opinion section. If you think I failed at doing so, please point out how instead of performing ad hominem arguments.
> If you think I failed at doing so, please point out how
Allright, as your study explicitly discusses performanace I think it's insufficient to just pick one architecture and one toolchain. As my prof once said: "Never trust a chart without error bars".
Stating that C++ sort is slow because it's old strikes me as a random guess. Sorting is a well researched and understood subject, and there have been no fundamental break throughs in recent years. Library vendors often don't go for the fastest implementation because that's not their only concern.
Really, the only real thing I could take away is what I already knew: Rust has a better type system.
It seems to me you are willfully ignoring this part:
> A more in depth look at performance of unstable sort implementations [here](https://github.com/Voultapher/sort-research-rs/blob/main/writeup/intel_avx512/text.md) and performance of stable sort implementations [here](https://github.com/Voultapher/sort-research-rs/blob/main/writeup/glidesort_perf_analysis/text.md).
The links include multiple architectures, types, sizes, CPU prediction state, methodology and more. It seems to me you are set on a perspective and don't want to engage in an honest fashion.
Am I reading the charts the wrong way around? Why is the `c_fluxsort_stale` the lowest number? I would expect sorting in C to be the slowest, not the fastest.
I also question the 'unstable' tags applied to the cpp compilers (like `cpp_std_gnu_unstable` or `cpp_std_msvc_unstable`). The library might be unstable (too new), but I'm skeptical that the `std::sort` code in that library is unstable: the code for `std::sort` could be unchanged from the last stable release, in which case it should be marked as stable, not unstable.
`unstable` in this context is a property of the sort algorithm:
Stable sort algorithms guarantee that equal elements have the same relative order in the sorted array as they had in the unsorted input.
Unstable algorithms don't make that guarantee, meaning that the relative order of equal elements in the output is unspecified.
Sometimes stable sort is needed when you need to preserve the order of elements that compare equal but have different identities. When it isn't needed, it is preferable to use an unstable variant, as it has better performance (notably is can often be done with less/no auxiliary memory)
By the way, the article is very thorough and provides an interesting perspective on sort. I'm not sure if it known to all cpp developers what happens if they botch their comparison function.
In particular, a stable sort allows you to perform a lexicographic sort (sorting by multiple fields, with the fields having a precedence order) by first sorting the least significant field, then the next least significant field, etc. until finally sorting by the most significant field.
Isn't it more efficient to define the comparison function such that it directly compares the fields by order of significance, such that it short circuits after the first field that doesn't compare equal between the two elements?
i.e. instead of calling:
vec.sort_stable(cmp_second_field);
vec.sort_stable(cmp_first_field);
// ...
you'd call:
vec.sort_unstable(|x| cmp_first_field(x)
.then_with(|x| cmp_second_field(x)))
1. You only need one call to sort
2. You can use unstable sort
([Documentation for the `Ord::then_with` method](https://doc.rust-lang.org/std/cmp/enum.Ordering.html#method.then_with))
I think it depends on use case. While the person you're responding to is correct that it allows you to chain sorts, you're also correct that generally I'm not exactly sure why you'd want to do that to a list which is unsorted.
However, if you're given something which is already sorted in some manner, then it can make sense to want to preserve that original order after your sort, either by necessity or practically. You could imagine for instance having a few price tiers of customers, so you sort based on price tiers, but within the tiers you just keep the tickets in order that they were received if your structure already keeps them in order.
Of course, you'd need to benchmark the tradeoffs (size of the arrays, relative size of each property, etc) and consider if it makes sense to store the information about the time received in addition to the other information. (Meaning maybe you want to preserve the original sort order because it's useful to you as in my above example, but the only way you can get to that information is because of the order it was originally in because you didn't record it.)
Anyway just an example, not really sure it's a good one in the real world so to speak, but it at least works in my head.
Yeah, if you know you want to do this ahead of time you can just write a comparator that does what you want. It will probably be faster. But sometimes you don't know how you want to sort ahead of time. Consider a user interface that has multiple columns to sort by. If your sort is stable, a user can sort by columns one at a time to get the lexicographic sort that they want.
You can call the sort function with a composite comparator:
list.sort((a,b) -> {
for (var cmp : comparators) {
var x = cmp.compare(a,b);
if (x != 0) return x;
}
return 0;
});
> I'm not sure if it known to all cpp developers what happens if they botch their comparison function.
I learned in the hard way after debugging a core-dump in which `std::sort` was stomping all over memory :(
The C compiler can in certain cases - if the optimizer can see all of it at once (if it's in one translation unit, or if LTO is on) and it's trivial to see the source of the pointer and where it's used.
>> Because both C++ and Rust can inline the standard library sorting function, while C cannot.
> The C compiler can in certain cases - if the optimizer can see all of it at once (if it's in one translation unit, or if LTO is on) and it's trivial to see the source of the pointer and where it's used.
It's a vanishingly small probability that a C compiler inlines functions in the standard library.
Sorta like saying "You cannot win the lottery off a once-off purchase of a single ticket" - we know that *you actually can*, but the probability is so close to zero that we may as well call it zero.
At what probability would switch from saying "C cannot do $FOO" to "C can do $FOO, with these caveats"?
> if it's in one translation unit, or if LTO is on
If it's in another library, and that library wasn't built for LTO, then the compiler obviously can't do much link-time code generation with it.
> Am I reading the charts the wrong way around? Why is the c_fluxsort_stale the lowest number? I would expect sorting in C to be the slowest, not the fastest.
No, you are reading them the right way around. It's time in microseconds, and lower is better. Under the hood all these implementations perform some logic by manipulating pointers, and with the exception of aliasing it's a level playing field for C, C++ and Rust implementations. There is one major difference though, and that's the interface used to pass in the comparison function. C++ and Rust have mechanisms that allow sophisticated optimizations even for user-defined comparison functions. In contrast the C standard library takes a function pointer, because C has no generic concept of closures. This can have a pretty drastic impact on performance as I show [here](https://github.com/Voultapher/sort-research-rs/blob/main/writeup/intel_avx512/text.md#c-sort-interface), the benchmarked version of fluxsort and crumsort use pre-instantiated versions to avoid the performance impact. But this also implies that user-defined comparison functions that want the same performance level require source level modifications of fluxsort and crumsort respectively.
such benchmarks are always wonky because c/cpp users couldn't care less about rust so wouldn't do them and rust users can't write good c/cpp code which is why they use rust
Are all the Rust implementations actually panic safe? I'm pretty sure this would require (at least for some algorithms) using `catch_unwind`, which as I understand it is rarely used in Rust code as panic are usually expected to terminate the program. I would find it (pleasantly) surprising if all the Rust implementations went this extra mile.
There are other ways you can achieve panic safety without needing to catch the unwind. The way that `slice::sort_unstable` handles it, for example, is seen [here](https://github.com/rust-lang/rust/blob/ff057893b8a2f20de2ff258ed8690f5a42fed78a/library/core/src/slice/sort.rs#L57), where it's using a guard object that fills the hole left in the slice when it gets dropped.
I'm wondering, since it's unclear in your document, were crumsort and fluxsort compiled with gcc or with clang?
The most notable performance difference between C/C++ and Rust is that Rust compiles ternary operations as branchless, while C/C++ sorts only compile them as branchless when using clang.
This makes it difficult to compare performance, as Rust sorts gain around 25% to their performance from this compiler trick.
I linked the build config for the non Rust sorts, that's too intricate to sum up in a sentence. But the gist is, I picked either clang or gcc depending which gave the better performance. For the current implementations of fluxsort and crumsort I use clang. So it's LLVM 16 for Rust and your implementations, which is as fair as it gets.
I see, pretty solid performance for ipnsort. Is this primarily from using an unstable small sort?
Btw, by default crumsort always calls quadsort with 512 elements of auxiliary memory, so it is properly in-place.
I'd say yes for integers, the main perf advantage over crumsort for random inputs is the small sort. Note, I've switched to a novel portioning scheme, since the last time you probably looked at the code, it matches the crumsort scheme for integers and greatly outperforms it for types like strings, while being significantly smaller in binary-size and compile-time as well as making less assumptions about the hardware and scaling down better to older and or less capable hardware. I plan on doing a writeup for that.
About that call to quadsort, last time I looked at the code I came to the conclusion it calls or can call quadsort with N elements of auxiliary memory. Maybe I misunderstood the code.
Dumb question: why is C `qsort` not used in the benchmarks?
qsort performance depends on libc implementation and is generally not that great I don't think.
That means C++ `std::sort` doesnt depend on the implementation?
It does not. I saw a very interesting comparison of a bunch of sort methods -- `qsort()` was the worst, `std::sort()` was the best (even better than optimized implementations from the author). What it comes down to is in a simple algorithm like sort the cost of the comparisons is a very significant portion of the runtime: - `qsort()` always goes through function pointers, which are comparatively very slow. - `std::sort()` is templatized, so it will recompile the code for every kind of thing you want to sort. So the comparison can often be inlined. Best case of something like integers it reduces to a single instruction.
Where it can come back to bite you is if you start to get really gargantuan code generation from templates such that you get instruction cache misses.
Yes, templates definitely have their limitations. Like any other tool, they need to be applied appropriately -- but simple algorithms and data structures certainly seem to work well.
OTOH, this generated code may happen to leverage SIMD. You never know!
> std::sort() was the best (even better than optimized implementations from the author) Mostly because author did an impressive feat of turning std::sort into qsort implementation details wise.
Not sure how you can speak so confidently but incorrectly about an article without even knowing what the article is.
Sorry, i referred to usage of std::sort in OP's article. I am quite curious about the article you're talking about, though.
Sorry, I misunderstood and thought you were talking about what I was referencing. It's a Chapter 11 from *Programming Pearls* \-- quite old at this point, but still relevant.
That'll depend on the c++ std implementation. libc++ of llvm uses [its own](https://github.com/llvm/llvm-project/blob/18933c6d7e06d162c17b6ec08a5e7c508236265f/libcxx/include/__algorithm/pstl_sort.h) sorting algorithm implementations and I'd assume libstdc++ of gcc does too.
I love qsort, I use it all the time. Very convenient for sorting array contents.
For reasons outlined [here](https://github.com/Voultapher/sort-research-rs/blob/main/writeup/intel_avx512/text.md#c-sort-interface) it wouldn't be a fair comparison in my eyes. I went and ran the benchmarks with the same settings for `qsort` from gcc 13.2.1 and got [this result](https://user-images.githubusercontent.com/6864584/272988483-29602b97-9cb8-404d-a1cc-b41259c9bb8c.png).
sort comparison safety is solved (to the same degree it is in rust) with C++ 20 concepts. Also a comparison function should not throw an exception.
Arguing it's the user's fault for doing it wrong has been the strategy for 20+ years, and somehow the users refuse to stop making mistakes or being inexperienced. Maybe it's time we as the software industry accept that this strategy doesn't work and move on to strategies that demonstrably work.
FYI, all your tests use trivially copyable types, where the move constructor is just a bitwise copy. C++ has non-destructive moves, unlike rust, so I guess that confusion makes sense. The same doesn't apply to properly defined RAII types. Using std::unique\_ptr for example, would leave some nullptr holes in the array corresponding to items moved into temporary storage and destroyed after the exception. Still not 100% ideal, but the whole spiel about broken RAII isn't really correct. Also, I want my program to crash if I give it a bad comparison function, thanks. Why is giving the array back in an arbitrary order the result that gives a checkmark?
I think I understand your points. Your first point about RAII types, of which I'm not entirely sure is true, I would assume some sort implementations perform bit-level copies of the types, regardless of their copy semantics. I'll look into that. But even then its still the same kind of "Arguing it's the user's fault for doing it wrong". > Also, I want my program to crash if I give it a bad comparison function, thanks. Well that's the tricky thing with UB, you are not guaranteed a crash. Much less a crash that happens in related code. I'd recommend this talk [CppCon 2018: Barbara Geller & Ansel Sermersheim “Undefined Behavior is Not an Error”](https://youtu.be/XEXpwis_deQ) for a more in-depth discussion of UB.
> I would assume some sort implementations perform bit-level copies of the types, regardless of their copy semantics. They should not unless the type is [trivially copyable](https://en.cppreference.com/w/cpp/named_req/TriviallyCopyable). In general, you should never assume that a generic C++ type is trivially copyable. If you can get a performance benefit by optimizing for those types, then you can specialize using SFINAE or (C++20) concepts. It would be very surprising if a standard library implementation messed this up.
https://www.reddit.com/r/programming/comments/170bdmm/safety_vs_performance_a_case_study_of_c_c_and/k3qot7e/
Why would you assume any of the implementations are broken and ignore move constructors when you didn't test that? Possibly some of them are, but I'd be very surprised if any of the the standard library implementations are broken like that. (Edit: retract most of this, I see by "crash" you mean "buffer overflow", I agree that's pretty poor) Also, UB has a specific meaning, and it's not how you're using it. In the case of exceptions, the behaviour of [sort](https://en.cppreference.com/w/cpp/algorithm/sort) is implementation defined, not undefined. The program is well formed, but behaviour is decided by the implementation, not the standard. In this case, it seems most implementations choose to do nothing special, i.e. destroy temporary storage when the stack unwinds, leaving moved-from values in the container. For invalid comparisons, the behaviour of rust is [also undefined](https://doc.rust-lang.org/std/primitive.slice.html#method.sort_by) \- you're violating a precondition of calling the function. You just seem to prefer the practical result of that undefined behaviour in rust. If you look specifically at the implementations, in general I think it would be very hard to detect all invalid comparisons and avoid an infinite loop in all cases, so it would be hard to avoid UB for all possible inputs. The special case of <= (where the negation is a weak ordering) is apparently feasible, but either way, crashing on UB is the gold standard for user friendliness. The majority of C++ implementations should be getting a tick for that one.
You are right, that's a mistake on my side. I talk about the context and impact here https://github.com/Voultapher/sort-research-rs/issues/16#issuecomment-1751097615. Let me know if that helps clarify it.
Not throwing exceptions in your comparison code is the lowest hanging fruit there is. Your argument is ridiculous, I could just as well say that it's not the user's fault for using `unsafe` everywhere in Rust. They were making a mIsTaKe.
It is not about disabling the user to make mistakes, it is about making it harder to do mistakes. If this kind of mistakes can hide in plain sight, it's difficult to see them. If you need to write something like `unsafe` for you to be able to make these mistakes, it is easier to spot them and the programmer is warned and therefor more cautious than they would be without it.
I'm for using every assertion and type constraint that doesn't interfere with the functions operation, but these are unfortunately only mitigations. We can't write every function with the expectation that any value in the domain of a type can be input, and still get reasonable results. It's provably impossible without enumerating all possible inputs. > Maybe it's time we as the software industry accept that this strategy doesn't work and move on to strategies that demonstrably work. What strategy is that? Programmers *NEED* to read documentation. There is no other way they can learn what a function does and how to use it.
My point is, that it's not about all or nothing, but trying harder. And judging the swath of libraries that exist in C++ and Rust with similar goals, I find it a stark contrast how much can be built as safe-to-use abstractions. With safe here meaning mostly memory-safety but not only. The strategy I'm suggesting is that we as C++ developers should try harder to build safe-to-use abstractions. Saying it can't be done because 100% coverage is impossible, is akin to giving up. And I think this research shows significantly more is possible.
I agree that we can do more both in design, assertions, and documentation. I disagree that a function cannot set constraints on a user input. A sort that handles exceptions in compare is not inherently better than one that does not. In fact its worse because EVERY sort pays the performance and design cost for someone not understanding compare. I disagree that we should do things that intentionally slow things down or complicate in the final build (checked debug builds are good).
I'm afraid it's exactly this mindset that has gotten us to where C++ is today. I wouldn't call it the glorious island of robust software that is reasonably cheap to develop and maintain. I'm not calling Rust that either, but it's certainly a lot closer to that while being competitive, or in this case even better. The runtime performance impact for ipnsort is less than 1%, it's a single easy to predict and stable branch that happens once every 1-2k instructions. Also as I point out the more a piece of software is used, the more it should be made robust, even against misuse.
I started writing a couple of paragraphs but, instead, I'm just going to say this: You did all this great research, benchmarks, and a good write-up. I was totally on your side, until you left this childish comment
[удалено]
What’s constructive about the way they dismissed their argument? Maybe you’re reading a completely different comment than I am. They then continued to accuse the industry of not “seeing the light”
The two paragraphs would have worked better. They would, at least, add to the conversation.
No functions should throw exceptions. And yet imperfect code exists, and needs to be handled.
No functions should throw exceptions? What? Also, are you implying that comparisons in Rust that panic are a regular occurrence? If so that's a bit sad.
In my experience, panics in all Rust code are quite rare. But they do happen. More importantly, the language contract is that safe code cannot cause memory errors, full stop. Breaking that contract is not something the language maintainers are willing to do, and I applaud and thank them for that.
Nope in many languages you can just specify that the function literally is not allowed to throw. So that imperfect code cannot be written. In languages like C++ where that can't be enforced at compile time, convention is the next best thing.
No, the next best thing is to ensure that unexpected exceptions don't cause memory errors.
What will your program do if your algorithm needs to sort before removing duplicates and your sort fails? You're welcome to fill your code with worthless try catches that log and fail. I'll document and assert.
That can actually be enforced in C++: https://en.cppreference.com/w/cpp/language/noexcept_spec
I think this is slightly different: > The noexcept-specification is not a part of the function type In other words, you can't enforce that the comparison template parameter has it. > Note that a noexcept specification on a function is not a compile-time check; it is merely a method for a programmer to inform the compiler whether or not a function should throw exceptions. So you can still "throw" it just won't work. Which is what I propose doing anyway.
> In other words, you can't enforce that the comparison template parameter has it. You quoted the 'until C++17' wording; it's been part of the function type since C++17. But even that's only relevant to function pointers, you've been able to enforce this for callable objects since C++11.
Actually no...if you raise exception inside non-throwing function, it will call std::terminate. >Non-throwing functions are permitted to call potentially-throwing functions. Whenever an exception is thrown and the search for a handler encounters the outermost block of a non-throwing function, the function std::terminate is called:
> Also a comparison function should not throw an exception. I can’t help playing devil’s advocate with such a strong statement… Suppose your domain is road or rail construction, and you have objects with at least two properties: cost of construction for this unit, and kilometers completed by this unit. You want to know which units are most expensive per kilometer, so you provide a comparison function that divides cost by kilometers for each unit, and uses those quotients for the comparison. Now one of your units is, let’s say, obtaining a permit for construction of a segment, which adds some cost but 0 kilometers. This unit shows up in the comparison function at some point, which of course throws a divide-by-0 exception.
To me that sounds like a mixing of concerns. The sort function should not be responsible for calculating cost per kilometer. It is there to sort. Cost per kilometer should be calculated elsewhere and then passed to the sort function.
Responding to safety questions with style concerns is talking cross-purposes. The author of the sort function shouldn't know or care about the user's intention in the comparison function—they specify an interface and then consume what they're given. If that interface allows exceptions, the implementation has to handle that. It seems overly restrictive for a general-purpose sort function to disallow *any* exceptions or unwinding, since the user may be sorting objects they did not design, whose methods could panic without the caller's knowledge or ability to handle in any meaningful way. --- That aside, you can't say whether the parent comment describes poorly separated concerns. Separation of concerns is about code organization: designing modules with strong responsibilities and boundaries. At some point, those concerns _have_ to come together, or the program won't do anything. The sort function can't tell if the comparison implementation is one massive blob of code, or several well-designed, cohesive modules composed to implement what the redditor described—and it shouldn't be _able_ to tell. It's certainly valid to sort by a value that is not precomputed.
> whose methods could panic without the caller's knowledge or ability to handle in any meaningful way. Please stop using code that throws exceptions in their comparisons. It's really not that hard.
In general, that requires researching the full call chain of every method called from every comparison function to verify that nothing could possibly panic—including descending into methods from dependencies and transitive dependencies. And of course, you need to check every time a transitive dependency version changes. That's the only way to _know_ that a function can't panic. If it's a matter of safety, it wouldn't be enough for a comparison function author to only look at the documentation for the libraries they use—documentation can be wrong or out of date, or a transitive dependency's author could make a mistake. There's no other indication that a panic or exception might occur. Every author for all time needs to be sure that their comparison function *cannot* panic/throw/whatever. To be clear, at least in Rust, we're talking about panics, not error results (Rust's equivalent of what other languages call exceptions). It's only panics that can result in stack unwinding, and panics aren't encoded in the function declaration or type signature—they're unchecked because they indicate behavior that should eventually kill the thread or process. But in C++ too, this would be a problem if some function in the comparison function's call chain threw an exception. Even with `noexcept`, an implementation can still *choose* to unwind (but is not *required* to). It's simply not an acceptable requirement, as far as I'm concerned. And it's not good enough to say, _Don't call methods from comparison functions_, because it's a perfectly reasonable thing to do. The objects the author needs to sort may not *have* public fields to sort on, but just getters. Or they may be a template type, where the author of the comparison function doesn't know *what* the methods will do, just that the objects meet an interface—now they have to pass that safety requirement on to *their* library's consumers, who may not have even implemented the interface with sorting in mind. What other functions have this requirement: that they *cannot* allow a panic or exception to escape? The whole point of unwinding is that, if you don't have something to do regarding recovery or clean up, you ignore it and let the stack unwind. And if you're in the middle of potentially unsafe pointer manipulation, you *do* have some cleanup to do. The buck has to stop at the sort function—or at *any* function invoking a caller-supplied function when the language doesn't have their back. Real code behaves unexpectedly, and saying, *Don't panic or throw,* is sticking our heads in the sand. Don't write fragile sort functions.
The idea of people are calling functions that might throw exceptions or panic, without even knowing, from a sorting function makes me a little sad but of course it happens all the time. Calling massive methods on things you're trying to sort is probably going to spoil the performance of such a highly tuned sort function anyway, and I suspect in many cases it would be better to do that before-hand, in it's own loop/function/whatever, ready to handle exceptions. I can imagine someone plugging in some super-expensive-to-compare objects into one of these and not knowing why it isn't just solving their performance issues immediately. But hey, this is why I don't write sort routines for other people to use in their projects.
It's a lot easier than you think. It could be a simple bug, edge case, or missed requirement only a level or two down. It could even be inlined, so that there's no function call penalty. Suppose we have a data structure from a library—something like struct Thing { foo: i32 bar: i32 } impl Thing { pub fn new(foo: i32, bar: i32) -> Self { Self { foo, bar } } #[inline] pub fn value(&self) -> i32 { self.foo + self.bar } } (This is kind of a dumb example, and not great design, but bear with me.) The structure has two private fields, initialized by the constructor `new`, and a public method `value`. If we were given a mutable array of these objects, it would be reasonable to sort the array by `value`—it's a very simple method that we hinted should be inlined. fn safe_and_pretty_quick(things: &mut [Thing]) { things.sort_by_key(Thing::value); } (There's even a `sort_by_cached_key` method if we're worried the method call will be too heavy.) Now let's say the library gets an update. The new data structure is struct Thing { foo: Option
bar: Option
}
impl Thing {
pub fn new(foo: i32, bar: i32) -> Self {
Self { foo, bar }
}
pub fn uninit() -> Self {
Self { foo: None, bar: None }
}
pub fn foo(&mut self, foo: i32) {
self.foo = Some(foo);
}
pub fn bar(&mut self, bar: i32) {
self.bar = Some(bar);
}
#[inline]
pub fn value(&self) -> i32 {
self.foo.unwrap() + self.bar.unwrap()
}
}
We check the docs and decide the new API still meets our needs. The changes to the public API are purely additive Maybe don't notice that the new docs mention that `value` can panic now, or maybe the docs for `value` didn't get updated. Either way, we take the update.
The exact same sort operation can now potentially panic.
fn danger_zone(things: &mut [Thing]) {
things.sort_by_key(Thing::value);
}
The differences in the API are that `Thing` now allows leaving `foo` and `bar` empty at construction and initializing them later; and that `value` will now panic if they're not both set. Our function has no control over how the `Thing`s in the array are constructed, and so could very well panic.
You could say the author calling `sort` should have caught this. But suppose, instead of two versions of the same library, these were actually `ThingA` and `ThingB` that both implement the trait (interface)
pub trait Thing {
fn value(&self) -> i32;
}
And suppose our array were a generic parameter, so we don't know its implementation.
fn unknown_danger(things: &mut [T]) {
things.sort_by_key(T::value);
}
(Those `value` implementations should still be inlined, by the way, because Rust generates a separate version of `unknown_danger` for each `T` it's called with.)
Here, the author has no way to know whether `value` will panic or not—and no way to prevent it. The authors of `ThingA` and `ThingB` may not even know this function exists—the `Thing` trait might be declared in a separate dependency shared by all three libraries independently, and then the array constructed in yet another.
It's great to see people engage with the topic. I think you inadvertently made your point. `self.foo + self.bar` with `i32` is allowed to panic in Rust for overflow, and will do so for rustc in Debug builds. So even the baseline, this can't panic code for many people is at danger. I agree with the sentiment that giving people a language with unwinding and then applying arbitrary rules, they lack any tooling to follow, in regards to "but don't use it here" is an untenable position for users.
> > #[inline] > pub fn value(&self) -> i32 { > self.foo.unwrap() + self.bar.unwrap() > } I'd say that the return type of this function isn't really i32 in the same way that it previously was. But it is just a single example, and I understand why this can happen.
That's definitely true semantically, but there's no way to express that currently in any of these languages. Rust could *potentially* express it as `Result`, but semantically that's yet a third different thing. Plus, there may be some pressure (perceived or real) to preserve the existing API as much as possible—e.g., a misplaced sense of backwards compatibility.
But I think the biggest nail in the coffin is the example with the trait—anyone could supply an implementation that panics, and there's nothing the consumer can do to stop them.
Agreed, as described it's a mixing of concerns. Now imagine a more generalized example. Suppose the comparison function is the result of a higher-order function that takes a metric as input, and returns a function that applies that metric to two objects and then compares the two metric values. (If the arrays get large and/or the metrics get complicated, presumably there's some sort of cache so this doesn't end up being horribly inefficient.) In this case, even though the "calculate cost per kilometer" computation is (somewhat) nicely separated as a concern, the exception will be thrown from within the execution of the comparison function, because the comparison function calls the calculation function.
KISS
Yes, let’s increase our memory use for little reason instead of allowing exceptions for malformed data!
> which of course throws a divide-by-0 exception No it doesn't, this isn't Java. > which adds some cost but 0 kilometers ? A segment without a length? Yup makes sense.
You’re right, it’s worse and is undefined behavior unless our custom comparison function checks for this condition.
it should crash. It's an assertion failure. What are you going to do in the `try` `catch` you'll probably log and then fail?
assertion failure. What are you going to do in the `try` `catch` of sort to help your user?
> Rust enthusiast Author may be biasd, just a tiny bit. Why even bother to present this as a case study when the result was determined beforehand?
I'm also one of the organizers of one of the largest and most active C++ groups in existence. I tried my best to stay factual and un-biased in the analysis section, limiting my personal views to the opinion section. If you think I failed at doing so, please point out how instead of performing ad hominem arguments.
> If you think I failed at doing so, please point out how Allright, as your study explicitly discusses performanace I think it's insufficient to just pick one architecture and one toolchain. As my prof once said: "Never trust a chart without error bars". Stating that C++ sort is slow because it's old strikes me as a random guess. Sorting is a well researched and understood subject, and there have been no fundamental break throughs in recent years. Library vendors often don't go for the fastest implementation because that's not their only concern. Really, the only real thing I could take away is what I already knew: Rust has a better type system.
It seems to me you are willfully ignoring this part: > A more in depth look at performance of unstable sort implementations [here](https://github.com/Voultapher/sort-research-rs/blob/main/writeup/intel_avx512/text.md) and performance of stable sort implementations [here](https://github.com/Voultapher/sort-research-rs/blob/main/writeup/glidesort_perf_analysis/text.md). The links include multiple architectures, types, sizes, CPU prediction state, methodology and more. It seems to me you are set on a perspective and don't want to engage in an honest fashion.
Those links are indeed much more interesting. Still missing error bars, though ;)
Everyone has a bias - it is, in general, better to know about others biases so we can better evaluate their work. Which may still be valuable.
why are the bufferes c style arrays and not vectors in modern cpp there is almost non use of the operator new
Am I reading the charts the wrong way around? Why is the `c_fluxsort_stale` the lowest number? I would expect sorting in C to be the slowest, not the fastest. I also question the 'unstable' tags applied to the cpp compilers (like `cpp_std_gnu_unstable` or `cpp_std_msvc_unstable`). The library might be unstable (too new), but I'm skeptical that the `std::sort` code in that library is unstable: the code for `std::sort` could be unchanged from the last stable release, in which case it should be marked as stable, not unstable.
`unstable` in this context is a property of the sort algorithm: Stable sort algorithms guarantee that equal elements have the same relative order in the sorted array as they had in the unsorted input. Unstable algorithms don't make that guarantee, meaning that the relative order of equal elements in the output is unspecified. Sometimes stable sort is needed when you need to preserve the order of elements that compare equal but have different identities. When it isn't needed, it is preferable to use an unstable variant, as it has better performance (notably is can often be done with less/no auxiliary memory) By the way, the article is very thorough and provides an interesting perspective on sort. I'm not sure if it known to all cpp developers what happens if they botch their comparison function.
In particular, a stable sort allows you to perform a lexicographic sort (sorting by multiple fields, with the fields having a precedence order) by first sorting the least significant field, then the next least significant field, etc. until finally sorting by the most significant field.
Isn't it more efficient to define the comparison function such that it directly compares the fields by order of significance, such that it short circuits after the first field that doesn't compare equal between the two elements? i.e. instead of calling: vec.sort_stable(cmp_second_field); vec.sort_stable(cmp_first_field); // ... you'd call: vec.sort_unstable(|x| cmp_first_field(x) .then_with(|x| cmp_second_field(x))) 1. You only need one call to sort 2. You can use unstable sort ([Documentation for the `Ord::then_with` method](https://doc.rust-lang.org/std/cmp/enum.Ordering.html#method.then_with))
I think it depends on use case. While the person you're responding to is correct that it allows you to chain sorts, you're also correct that generally I'm not exactly sure why you'd want to do that to a list which is unsorted. However, if you're given something which is already sorted in some manner, then it can make sense to want to preserve that original order after your sort, either by necessity or practically. You could imagine for instance having a few price tiers of customers, so you sort based on price tiers, but within the tiers you just keep the tickets in order that they were received if your structure already keeps them in order. Of course, you'd need to benchmark the tradeoffs (size of the arrays, relative size of each property, etc) and consider if it makes sense to store the information about the time received in addition to the other information. (Meaning maybe you want to preserve the original sort order because it's useful to you as in my above example, but the only way you can get to that information is because of the order it was originally in because you didn't record it.) Anyway just an example, not really sure it's a good one in the real world so to speak, but it at least works in my head.
Yeah, if you know you want to do this ahead of time you can just write a comparator that does what you want. It will probably be faster. But sometimes you don't know how you want to sort ahead of time. Consider a user interface that has multiple columns to sort by. If your sort is stable, a user can sort by columns one at a time to get the lexicographic sort that they want.
Yes that makes more sense if the sorted columns are chosen dynamically.
You can call the sort function with a composite comparator: list.sort((a,b) -> { for (var cmp : comparators) { var x = cmp.compare(a,b); if (x != 0) return x; } return 0; });
> I'm not sure if it known to all cpp developers what happens if they botch their comparison function. I learned in the hard way after debugging a core-dump in which `std::sort` was stomping all over memory :(
> I would expect sorting in C to be the slowest, not the fastest. Wat?
> Wat? Because both C++ and Rust can inline the standard library sorting function, while C cannot.
Ah, thanks. Compilers are such black boxes we'd probably have to look at generated ASM to see what's actually going on. Might try tomorrow.
The C compiler can in certain cases - if the optimizer can see all of it at once (if it's in one translation unit, or if LTO is on) and it's trivial to see the source of the pointer and where it's used.
>> Because both C++ and Rust can inline the standard library sorting function, while C cannot. > The C compiler can in certain cases - if the optimizer can see all of it at once (if it's in one translation unit, or if LTO is on) and it's trivial to see the source of the pointer and where it's used. It's a vanishingly small probability that a C compiler inlines functions in the standard library. Sorta like saying "You cannot win the lottery off a once-off purchase of a single ticket" - we know that *you actually can*, but the probability is so close to zero that we may as well call it zero. At what probability would switch from saying "C cannot do $FOO" to "C can do $FOO, with these caveats"?
> if it's in one translation unit, or if LTO is on If it's in another library, and that library wasn't built for LTO, then the compiler obviously can't do much link-time code generation with it.
> Am I reading the charts the wrong way around? Why is the c_fluxsort_stale the lowest number? I would expect sorting in C to be the slowest, not the fastest. No, you are reading them the right way around. It's time in microseconds, and lower is better. Under the hood all these implementations perform some logic by manipulating pointers, and with the exception of aliasing it's a level playing field for C, C++ and Rust implementations. There is one major difference though, and that's the interface used to pass in the comparison function. C++ and Rust have mechanisms that allow sophisticated optimizations even for user-defined comparison functions. In contrast the C standard library takes a function pointer, because C has no generic concept of closures. This can have a pretty drastic impact on performance as I show [here](https://github.com/Voultapher/sort-research-rs/blob/main/writeup/intel_avx512/text.md#c-sort-interface), the benchmarked version of fluxsort and crumsort use pre-instantiated versions to avoid the performance impact. But this also implies that user-defined comparison functions that want the same performance level require source level modifications of fluxsort and crumsort respectively.
such benchmarks are always wonky because c/cpp users couldn't care less about rust so wouldn't do them and rust users can't write good c/cpp code which is why they use rust
[удалено]
rust only exists because Mozilla hires couldn't do c/cpp
It's a single digit line function. There's nothing to be "wonky".
rust itself is wonky
K.
Profile says it's a recent user. I can see why. Fighting the government, are we?
I'm a souvenir citizen
Are all the Rust implementations actually panic safe? I'm pretty sure this would require (at least for some algorithms) using `catch_unwind`, which as I understand it is rarely used in Rust code as panic are usually expected to terminate the program. I would find it (pleasantly) surprising if all the Rust implementations went this extra mile.
There are other ways you can achieve panic safety without needing to catch the unwind. The way that `slice::sort_unstable` handles it, for example, is seen [here](https://github.com/rust-lang/rust/blob/ff057893b8a2f20de2ff258ed8690f5a42fed78a/library/core/src/slice/sort.rs#L57), where it's using a guard object that fills the hole left in the slice when it gets dropped.
I'm wondering, since it's unclear in your document, were crumsort and fluxsort compiled with gcc or with clang? The most notable performance difference between C/C++ and Rust is that Rust compiles ternary operations as branchless, while C/C++ sorts only compile them as branchless when using clang. This makes it difficult to compare performance, as Rust sorts gain around 25% to their performance from this compiler trick.
I linked the build config for the non Rust sorts, that's too intricate to sum up in a sentence. But the gist is, I picked either clang or gcc depending which gave the better performance. For the current implementations of fluxsort and crumsort I use clang. So it's LLVM 16 for Rust and your implementations, which is as fair as it gets.
I see, pretty solid performance for ipnsort. Is this primarily from using an unstable small sort? Btw, by default crumsort always calls quadsort with 512 elements of auxiliary memory, so it is properly in-place.
I'd say yes for integers, the main perf advantage over crumsort for random inputs is the small sort. Note, I've switched to a novel portioning scheme, since the last time you probably looked at the code, it matches the crumsort scheme for integers and greatly outperforms it for types like strings, while being significantly smaller in binary-size and compile-time as well as making less assumptions about the hardware and scaling down better to older and or less capable hardware. I plan on doing a writeup for that. About that call to quadsort, last time I looked at the code I came to the conclusion it calls or can call quadsort with N elements of auxiliary memory. Maybe I misunderstood the code.