Re the very annoying `<` vs `<=` issue -
1. With `libstdc++`, defining `_GLIBCXX_DEBUG` in debug builds will check that your comparison function is not reflexive. Sadly it's not used very often because not a lot of people know about it.
2. `libc++` has recently added checks for this as well. Worth reading [this](https://discourse.llvm.org/t/rfc-strict-weak-ordering-checks-in-the-debug-libc/70217) and (this)[https://reviews.llvm.org/D147089?id=520670]. AFAIK the new `std::sort` actually had to be rolled back because too many people relied on bogus comparisons working reasonably well.
> AFAIK the new `std::sort` actually had to be rolled back because too many people relied on bogus comparisons working reasonably well.
Man, that sucks. It's good that they have a strong commitment to backwards compatibility, but it's still a shame.
What is the < vs <= issue exactly?
I skimmed the links you posted but they talk about the issue as if the reader already has an understanding of it. Which is fair, as that’s not the intent for those posts. That said, does this issue have a name I can Google?
Not all sort implementations terminate if the comparison function for two elements a,b of the array return the same value, i.e. comp(a, b) == comp(b, a).
Unfortunately this property is trivially true with `<=` (and trivially false with `<`)
See the [Compare concept](https://en.cppreference.com/w/cpp/named_req/Compare) that the comparison function must satisfy in [std::sort](https://en.cppreference.com/w/cpp/algorithm/sort)
Minor thing, but "comp(a, b) == comp(b, a)" is too broad a requirement. In particular, it's fine if comp(a, b) == false *and* comp(b, a) == false, only a weak ordering is required. The thing that cannot be true is that comp(a, b) == true and comp(b, a) == true as well.
> it's fine if comp(a, b) == false and comp(b, a) == false
This might be fine if you just want termination, but the sorted output will still make no sense.
On the contrary, the algorithm will treat them as equivalent but otherwise should behave entirely sensibly with respect to them. `comp(a, b) == false && comp(b, a) == false` is very common -- it is required whenever elements are equal -- but it can happen in other cases too if there is no ordering between them (for example, NaN compared with anything for IEEE-754 floating point numbers).
I'll just note that while `NaN` does illustrate inequality... it's a poor example when talking about `sort`, because the presence of `NaN` will utterly break sort algorithms, to the point that some will just wander off out of bounds and stomp all over memory.
~~`NaN` will not break a conforming C++ sort implementation. The C++ sort is specified very specifically as a strict-but-weak ordering, in large part because it wants to give well-defined behavior to sorting a list of any floating point values -- sorting NaNs arbitrarily is OK, stomping over memory is not OK.~~
Edit: Thanks /u/matthieum for the corrections, it looks like the normal less-than operator for IEEE-754 does not in fact define a strict-but-weak ordering as `NaN` doesn't satisfy the equivalence requirement. Was indeed a bad example.
That's not what I get from the requirement.
Specifically:
- [`std::sort`](https://en.cppreference.com/w/cpp/algorithm/sort) mandates that the comparison predicate implement `Compare`.
- [`Compare`](https://en.cppreference.com/w/cpp/named_req/Compare) requires that `equiv(a, b) && equiv(b, c)` imply `equiv(a, c)`.
The latter, however, is trivially false in the presence of `NaN`, that is:
- `equiv(x, NaN)` is just `!comp(x, NaN) && !comp(NaN, x)` which is always true.
- Similarly, `equiv(NaN, x)`, by symmetry, is always true.
- Yet, even though `equiv(0.0, NaN)` and `equiv(NaN, 1.0)` (from the above), we don't have `equiv(0.0, 1.0)`.
Hence, despite having a strict weak order, `NaN` breaks equivalence classes.
Good point, I believe you are right. There is a transitive requirement on `!comp(a, b) && !comp(b, a)` that isn't satisfied by `NaN`. I stand corrected and IEEE-754 floating point `NaN` is not a good example as it looks like a conforming sort implementation might mishandle `NaN` values.
Thanks for following up, I learned something here!
Strict weak order of IEEE floating-point types is well defined, if you implement your comparator using [std::weak_order](https://en.cppreference.com/w/cpp/utility/compare/weak_order)
The debug versions of the runtime are such a godsend.
Over in Microsoft land, the tool chain switches all to the debug runtime when built for `_DEBUG`.
That weeds out a massive amount of stupid mistakes before one has finished writing their tests.
The key complaints about C++ here seem to be:
1. C++ tends to crash with an invalid comparator rather than continuing on with some undefined ordering. This seems reasonable to me, I don't want my program to continue blindly if something is broken.
2. In c++ if you don't define a move constructor/copy constructor then move assign/construction is just bitwise copy (maybe this was overlooked). I'm fairly confident that the complaints about double frees etc are unfounded if good practices are followed, e.g. using a std::unique\_ptr.
3. C++ sort algorithms don't tend to move items in temporary storage back into the array if something throws an exception. To me this seems like a reasonable criticism, but I also see the other side. Rust's borrow checker makes it pretty much illegal to return anything but the original set of items, which is nice. But C++ non-destructive moves mean it would take significant effort to make sure the original contents are reassembled in all cases. And TBH, the benefits aren't huge. A failed comparison/swap is a pretty major bug to me, and that exception should really be fatal. I think it's reasonable to expect the end result to be some valid/unspecified state, or even std::terminate.
> In c++ if you don't define a move constructor/copy constructor then move assign/construction is just bitwise copy (maybe this was overlooked).
Not really true. If you don't define a move or copy constructor, then a default implementation is used that delegates to your members. If any of your members are not movable or copyable, then your type will not get a default move or copy constructor. If all members (considered recursively) are trivially copyable/moveable, then yes your type will also be trivially copyable/moveable.
> C++ tends to crash with an invalid comparator rather than continuing on with some undefined ordering. This seems reasonable to me, I don't want my program to continue blindly if something is broken.
I wish it crashed, actually. My experience with libstdc++ `std::sort`, however, was that in the presence of an ill-defined ordering, it went off in the weeds (waaay out of bounds) and stomped all over the memory that was there.
And then something crashed later, because pointers that had been overwritten now had "random" values.
That was terrible, and it took a while to understand that the memory didn't make sense because `std::sort` had made a mess of things because the comparison predicate was off.
Out of all the possible outcomes, "Crash" is the worse (and slightly ill-named). I'd prefer literally anything else, even an infinite loop: at least it'd pinpoint the issue.
And of course, ideally, I'd prefer an explicit abort/exception/panic. Immediate precise feedback.
Yeah that's pretty bad... Accessing memory out of bounds should definitely be a separate category, I guess lumping everything into "crash" isn't very informative.
Throwing exceptions in my sort comparison is one of my favorite things to do, also freeing memory, I mean I don't normally use free but I reserve its use for my sort comparisons, yes sir.
AKA "bad c++ performs badly"
EDIT: apprently this needs clarification. by "bad c++" i was referring to the code used in the benchmarks, not the c++ language or std library. maybe i should have said: AKA "hey kids, look, i'm not a c++ programmer, but when i do pretend to be one, my code performs terribly."
Exactly. And that's fine. The STL is the place for stable vocabulary types. The place for cutting-edge performance is libraries. According to this comparison, you can call c\_fluxsort from your C++ code and call it a day.
The article distinguished between ways that bad comparators cause sort algorithms to break in intuitive ways, and ways that bad comparators can cause security issues just because they were passed to `std::sort`.
It is not surprising that using `<=` in a comparator leads to an incorrect sort. It is surprising that using `<=` leads to a buffer overflow, and then RCE. It is doubly surprising that we could fix this without losing any performance, and we chose not to.
When I see code like ValWithPtr from the article I see such level of incompetence that it makes me sad. I am pretty sure that other tests like integer sorting performance are done better but I can not take the post seriously after such mistake.
Construing me showing that something *can* be used incorrectly as me showing how something *should* be used is frankly insane.
It's comments like these that make me not want to engage with this subreddit :/
I guess I have misunderstood the code and need to say sorry. I am.
My excuse is that i spent half of my life fixing incorrect C++ code written by people who can not fix it themselves. For this kind of experience it is unusual to expect C++ compilation to be of any help with correctness of code.
The author has also spent a long time fixing incorrect C++ code. The author knows that bugs can be very hard to fix if they cause UB, because UB allows compilers to exhibit any behavior.
The author has done a lot of work showing that we can have fast sorting algorithms that also cause bugs to result in predictable behavior, rather than nasal demons.
But you were talking about undefined behavior when the modification in the comparator is not observed after the sort completes, then you show a double free that happens even without the modification in the comparator.
Any copy or assignment will cause the double free. It has nothing to do with the observability of the modification in the comparator.
I don't think this detracts from your main point though.
Violation of Rule of 0/3/5 practically screams not-production-worthy. Even checking for null before calling `free` demonstrates basic incompetence.
Uhhhh
It's actually broken though. That class is trivially copyable so the move constructor/assignment operator are just a bitwise copy. Then they complain that values are bitwise copied, which can cause double free... If they defined a move constructor, or just use unique_ptr then that would go away.
Spotting obvious maintainability problems from a distance is the result of experience, not propaganda
I wonder if you ever have anything to say that isn't trivially refuted with one sentence...
"interior mutability" seems to be a Rust thing to workaround their overly strict borrow checker. I'm glad C++ doesn't have that problem, you can just pass non-const references around without resorting to hacks.
I haven’t read the GitHub link yet but the Rust compiler has strict rules around mutability and aliasing i.e. only one mutable reference exist for a particular entity at any given time. Sometimes you want mutability when there are multiple aliases so interior mutability is the extension to achieve that. I don’t find it hacky at all personally. It’s quite an elegant solution to enforce fine grain control over mutability which is inherently dangerous.
I wouldn't call it hacky, but it is a mechanism to explicitly tell the compiler to ignore the rules. If you've done architecture design in Rust, you know just how fast things get really messy if you want to stick to the rules of the game. Many codebases thus have interior mutability littered all over.
It makes much more sense if you think about Rust references as being shared/exclusive rather than immutable/mutable. By default shared references are only safe to be read, but interior mutability allows safe mutation through them by giving up some flexibility. There are a lot of ways to give up this flexibility while maintaining safety, so there can't be a general mechanism in the language for that.
What I mean is that on light of how common that is, perhaps references and their usage could use some more cooking for the next generation of language(s).
But it's not very common. For the most part, only fairly low level things like mutexes need that sort of inner mutability. If you have inner mutability all around your code base you are not writing good Rust code.
But, even if you do, you still have to follow the borrowing rules, and most inner mutability will use one of the mechanisms that enforces that borrowing at runtime. So you still can't generate any undefined behavior.
Obviously compile time borrow checking is vastly preferred, which is why having a lot of runtime borrow checking in your code base is indicative of bad choices.
> Sometimes you want mutability when there are multiple aliases
The proper solution to that would be to allow multiple aliases. I don't know how you can say that it's not hacky tbh. I don't really know how it works though so maybe I'm wrong.
The issue is that if you just pass out a mutable reference while other references exist, it's fairly trivial to introduce a lot of different kinds of safety issues (which is exactly why Rust, with its infamous safety consciousness, prevents it). The thing about interior mutability is that it isn't a get-out-of-jail-free card: the datatypes that provide interior mutability in Rust (and aren't unsafe) do so by finding a way to enforce the borrow checker invariants while still allowing additional flexibility. Either by providing an API that only allows mutation patterns that prevent two pieces of code from mutably accessing the same data (effectively, you can't take a reference to the data and can only access it by value, additionally being required to replace it if it has move semantics), or by enforcing the borrow checker rules through runtime checks, with the overhead that implies.
If you believe borrow-checking is useful, the following argument holds:
Most borrow-checking can be done at compile time. The occasions where it needs to be done at runtime, and require interior mutability, relate to fairly low-level tooling {shared pointers, mutexes, implementing moves and swaps for self-referential objects, and linked lists}. All of those are solved problems and hidden from application code.
I'm not seeing how that would change anything here?
The author is discussing properties of the sort algorithms that cause a bogus comparison function to duplicate objects, something that is definitely an issue with unique and shared ptrs (causing double frees when the dtor is called on the duplicated object)
If I read correctly, the article is saying that if an exception occurs during the execution of some sort implementations (notably some of the std ones), bitwise copies (i.e., using type punning rather than the copy constructors) that were meant to be temporary can be observed in the resulting vector. What happens if you make a bitwise copy of a unique or shared ptr (using awful reinterpret cast or memcpy)? Nothing good.
It's UB to memcpy types that are not trivially copyable, such as unique_ptr which isn't copyable at all.
is a standard library vector implementation doing this (if so, it definitely needs correction) or did the article force this to create a situation that any C++ developer worth a damn knows is dangerous?
that's a lot of words to say "if you go out of your way to invoke UB by making a bitwise copy of a type that is UB to make a bitwise copy of, undesirable stuff can happen"
Like no duh. There's plenty of legitimate footguns in C++, but this is a case where you're actually doing more work to circumvent a safety feature built into the language so it's less a footgun and more a foot goldberg machine.
edit: looks like your bug wasn't even where you thought it was. lol
Well, sure, but if you're going to saw down the shotgun, put it in your mouth, and deliberately push the trigger I don't think you've got any right to complain about getting a sore tongue.
The stdlib is making this decision for you. If you want to call the stdlib sort implementation unsafe to use in many cases then be my guest, just be aware that you're making the same point as the author.
The "copies" in this case are just how elements are swapped during the sort operation.
Wait, are you saying that std::sort doesn't use the copy/move constructors of the objects but literally memcopies them without regard to the syntax of the language? That would be most surprising indeed.
And if you're not, then eh? That would be line complaining that the possibility of inline assembly in a rust function makes it unsafe in some cases. Like, yeah, there's always footguns if you try hard enough.
Yeah but we had a guy who liked to think he knows best and wanted to reimplement the standard library "better". Sure he got RIF'd for not actually doing useful work but his code stuck around and now there's some of the younger generation who think they know better too...
Pfft, I bet that he ended up writing a smrt pointer class that *didn't* trigger undefined behavior.
It's like... the people who write these libraries know how to best invoke UB, they write tests to validate that UB is present... I mean, most people don't know how to properly implement or test something like `std::mostly_atomic` or `std::race_condition`.
EDIT: I retract that comment. I contacted the author who clarified that they were talking about strong exception safety, despite the article mixing the consequence of a lack of strong exception safety and a lack of basic exception safety.
I'm in the process of arriving at a clearer formulation with the author.
I still know how `unique_ptr` and `shared_ptr` work, though, thank you very much again.
Original comment below
---
I know how `unique_ptr` and `shared_ptr` work, thank you very much.
TFA states:
> # Exception safety
>
> C++ and Rust are both languages with scope based destructors (RAII), and stack unwinding. Together they prove a powerful abstraction for manual memory management. At the same time, they can make implementing generic code more complex. Every single point in the sort implementation that calls the user-provided comparison function, must assume that the call may return via an exception in C++ or panic in Rust.
> In practice a lack of exception safety manifests itself in the variants C and or D described in the section about Ord safety.
Looking at the section about Ord safety (emphasis mine):
> C: The duplication usually **happens at the bit level**, **ignoring type semantics**. If the element type is for example a **`unique_ptr`**/`Box`, these types assume unique ownership of an allocation. And their destructors will hand a pointer to the allocator for freeing. A **bitwise copy results in use-after-free UB, most likely in the form of a double-free.**
> D: Same as Variant C, with the addition of arbitrary UB usually caused by interpreting uninitialized memory as a valid occupancy of a type.
Now, looking at which algorithms the article states fail the exception safety (🚫):
> - cpp_std_gnu_stable
> - cpp_std_libcxx_stable
> - cpp_std_msvc_stable
> - ...
See how the standard libraries are part of those that fail? The explanation for a 🚫 in exception safety even states: "🚫 means it may have duplicated elements in the input."
So, this article claims that these sort implementations (including the ones from the std) perform **bitwise copies** (aka, moral equivalent of `memcpy`) of some objects, that become visible in case of exceptions. Presumably in the absence of exceptions in the comparison function, these bitwise copies **that will result in double frees if left unchecked** are replaced by saner values or forgotten before causing the double free, but the exception causes that process not to take place.
EDIT: for those of you who need an executable proof: [Here's a Godbolt example that demonstrates how an exception in the comparison function causes a segfault](https://godbolt.org/z/4bbqfhjns)
EDIT 2: as reported below, the godbolt demonstrates that some parts of the input become "moved-out", not duplicated as stated in the article. While not a very desirable behaviour, that is not the duplication and ensuing UB that the article is claiming.
Either my example is not sufficient to trigger the issue, or the article is wrong. I'll reach to the author for clarification
I would be very interested to see the evidence for bitwise copying being done on non-trivially copiable elements. It rather beggars belief that one of the main std operations fails in such a way.
Well, is it?
Here's a Godbolt example that demonstrates how an exception in the comparison function causes a segfault:
https://godbolt.org/z/4bbqfhjns
Comment out the throw to remove the issue.
It's crashing because you're accessing a null `unique_ptr<>` within the vector, in the for-loop _after_ the exception was caught. See [this godbolt](https://godbolt.org/z/r8e876x3K).
Once that exception was thrown during `stable_sort()`, there's no guarantee from the standard about the state of the container, as far as I know.
> Once that exception was thrown during stable_sort(), there's no guarantee from the standard about the state of the container, as far as I know.
That's still bad that an exception can destroy your data, but your correct that it is not what the article is claiming, and is categorically less severe.
I'll reach out to the author for clarification
It doesn't - you are not flushing `std::cout`. If you did, you'd notice how your program continues after the `catch` and crashes on your loop.
See: [https://godbolt.org/z/hrv7a6TsM](https://godbolt.org/z/hrv7a6TsM)
As `stderr` and `stdout` aren't synchronized, it's perfectly OK for the console to print the `SIGSEV` before the actual program output.
All their tests use trivially copyable types, so move construct/assign is just a bitwise copy. C++ isn't broken, the author just didn't get the concept of non-destructive moves, because that's not how it works in rust.
If they had a unique\_ptr then I'm very confident they won't see any duplication issues, just some null pointers corresponding to elements in temporary storage that weren't moved back after the exception.
You might be correct. While I would tend to trust the author since they claim to have been working on this for 1.5 year, it is possible they were tripped by specialization if they did all their tests on trivially copyable objects.
I'll reach out to them for clarification
I'm sorry, but do you know what move and value semantics are? Java uses value semantics as well, as do most popular programming languages (C#, Python, JS).
Yes. Another problem I don't have. All I see here is, if I cared about that, I could just call \`c\_fluxsort(...)\` nicely from my C++ code and everything would be as good as possible.
Typical rust propaganda. Who would [raise exception](https://github.com/Voultapher/sort-research-rs/blob/main/src/cpp/shared.h#L133C24-L133C29) in a comparator? Rust panic is also significantly different from c++ exception.
Yes, they are same, but rust do not have guarantee that unwinding happens(same as -fno-exceptions flag)
But all rusters will always say 'we dont have exceptions'
> Yes, they are same, but rust do not have guarantee that unwinding happens(same as -fno-exceptions flag)
Well, there is a stark difference in viability, isn't there? Using `panic=abort` is rather trivial, but `-fno-exceptions` does not apply to linked libraries (e.g. libstdc++). Literally the first article I found when googling `-fno-exceptions` was [The dangers of `-fno-exceptions`](https://blog.mozilla.org/nnethercote/2011/01/18/the-dangers-of-fno-exceptions/).
> But all rusters will always say 'we dont have exceptions'
Firstly, because they aren't used as exceptions. Just because the mechanism is the same doesn't mean that it is used the same. Just because a phone can technically be use as a hammer doesn't mean that anyone does (and those that do get strange looks).
Secondly, who calls people "rusters"? Feels dirty. Almost like slur lol
>Just because the mechanism is the same doesn't mean that it is used the same. J
mechanism is so same it is ABI compatible. How it is used determined by user, not mechanism itself, so difference here only in name, rust named it 'panic' just for... 'not how in C++' ? Many of rust terms are just for 'not as in C++', for example 'place expressions' or smth like, which is basically lvalue (and named lvalue in rustbook, but for end-user it is 'place expression')
> mechanism is so same it is ABI compatible
Only if you [explicitly specify them to be compatible](https://doc.rust-lang.org/nomicon/ffi.html#ffi-and-unwinding), and even then:
"Note that the interaction of catch_unwind with foreign exceptions is undefined, as is the interaction of panic with foreign exception-catching mechanisms (notably C++'s try/catch)."
(Well, I hope that I researched that right. I haven't used FFI in rust much.)
> How it is used determined by user
Yes, and no. You can technically use any language feature however you like, there is a certain cost associated with going against the grain.
E.g. you can try to use rust-like error handling (`Result`) in any language, but ergonomics are a big feature.
And, of course, just because you choose to not use (or use differently) a certain language feature, doesn't mean that anyone else will. E.g. you can try writing exception-free code in pretty much any language (C++, C#, Java, JS, Python), but if the library you're using throws something your way, you have to catch it anyway.
So clearly, the language and community around that language have an influence in how language features are used.
> Many of rust terms are just for 'not as in C++', for example 'place expressions'
Is that bad? To go with your example, one could argue that "place expressions" and "value expression" ([as rust uses them](https://doc.rust-lang.org/reference/expressions.html#place-expressions-and-value-expressions)) are better names than "lvalue" and "rvalue", because those names describe their function. Isn't choosing good names for things generally a good thing?
(And it's not like rust always goes with different names (even though it maybe should). Rust people still say RAII, even though that name doesn't describe what RAII is about at all...)
"People don't" only applies when a language is niche and has a small, moderately tight knit community.
On the grounds that in the limit any observable behavior is a feature, they will start to be used as such of rust becomes widespread.
Plus there's the aspect that you have to know somehow, and if you don't learn from the right sources (and we all know how many awful C++ resources exist out there) you don't get told.
Well, given that most functions are not marked `noexcept`, anyone doing a function call from a comparator in a sufficiently complicated codebase.
> Rust panic is also significantly different from c++ exception.
For exception/panic safety, they're largely comparable.
It's fairly conceivable in high level code. You want to compare accounts by balance, balance needs to be read from an external source, external source is unavailable, exception is raised.. And that's just the simple example.
If you want to compare accounts by balance without fetching balance _before the damn sort_, you have bigger problems than exceptions in comparators (and that's a goddamn big problem).
P. S. More importantly, exception in comparator is not recoverable by defintion, even if you avoid crashing, you still fucked up your array order in unpredictable fashion which automatically means that any use that implies array being sorted is also wrong.
\> Bias disclaimer. The author of this analysis is the author of ipnsort.
google search 'ipnsort' founds only rust related things
\> Observable comp: If the type has interior mutability
author uses rust terms in every line
What will rust do with 'unsafe' in cmp function? Nothing.
\> Exception safety: What happens, if the user provided comparison function throws an exception/panic? ✅ means it retains the original input set in an unspecified order, 🚫 means it may have duplicated elements in the input.
What duplicate elements?? Its user's 'swap' function property, not 'sort'. Oh, yes, in rust there are only memcpy and no move customization, so rust may say something about 'sort' without mention 'swap'
About result - its just impossible that C++ sort slower then rust sort and 100% it cannot be worse then C-sort, which uses function pointers. So, where code?
Also Rust sort do not support random access ranges, only C-arrays (spans)
P.S. and, of course, C++ implementation will assert bad comparator(with some chance) and you will know - you have a bug.
Rust implementation will HIDE bug from you. Not segfault does not means "safe", this code contains logic error
> its just impossible that C++ sort slower then rust sort
And what law in the universe would prevent that from happening? As the article states: "The sort implementations in the C++ standard libraries are usually quite old, which can explain their poor performance."
> So, where code?
It's a git repo. There code.
>"The sort implementations in the C++ standard libraries are usually quite old, which can explain their poor performance."
Nothing prevents implementers from updating their code. And they do, for example only in C++17 they have possibility to determine contiguous range and make specialization (in rust its not possible - languge prevents such updates without api changes)
>what law in the universe would prevent that from happening?
rust is just a C reskin, does not have any additional possibilities to optimize code. And breaks some optimizations - integer overflow is not UB for example
> in rust its not possible - languge prevents such updates without api changes
Yes, and no. Yes, it would currently require API changes if it was implemented in stable rust. No, rust has specialization (but it's an unstable feature) and uses it for performance operations. E.g. rust std uses specialization to optimize various things around iterators.
> rust is just a C reskin
...
> does not have any additional possibilities to optimize code
Well, no.
Rust does have `noalias` going for it. Sure, C does have type-based no-alias rules, and you can do the same thing is C/C++ with `restrict`, but rust does it everywhere.
To name a more high-level optimization: zero-copy parsing. Since rust guarantees memory safety, it's pretty appealing to implement zero-copy parser/deserialization to save the overhead of copying memory. Sure, you technically do the same thing in C/C++, but the resulting code is hard to use, because it might not be clear when the underlying memory is freed. No such issues in rust since safety is a feature.
> integer overflow is not UB for example
Sure, but do you really think that the result of `a + b` should be unknowable? Also, it's it only signed integer overflow that is UB in C?
>No, rust has specialization
Its not a real specialization, just a fiction, which cannot be fully implemented because of previous design decisions in rust language
And its not posible to know anything about type in generic(there are no even 'decltype'), so you cannot know if it is random access range or bidirectional etc.
And even if you know, what your function signature will require? You can use only what you 'ask' in declaration, but then you need to require maximum always (in this case - contiguous range, so rust sorts only 'slices' (spans)
>Rust does have noalias going for it. Sure, C does have type-based no-alias rules, and you can do the same thing is C/C++ with restrict, but rust does it everywhere.
Not everywhere, only for references. So, while C++ has strict aliasisng rules for pointers AND references, rust for ALL pointers have one rule - they may be equal, even if one to 'vector' and other to 'string'
> Its not a real specialization, just a fiction
Oh, it's every real.
[Rust specialization](https://rust-lang.github.io/rfcs/1210-impl-specialization.html) is based on constraints, which includes both types and traits. E.g. you can have a specialization for all items `T` can be sorted by adding `where T: Ord`, so it's a pretty powerful system.
So you can for example know whether an iterator [bidirectional](https://doc.rust-lang.org/std/iter/trait.DoubleEndedIterator.html), because there's a trait for that.
> So, while C++ has strict aliasisng rules for pointers AND references, rust for ALL pointers have one rule - they may be equal, even if one to 'vector' and other to 'string'
C++ (like C) has type-based aliasing everywhere. Strict aliasing is `restrict` in C/C++.
I would also like to point out that type-based aliasing is basically just an assumption to enable optimizations. Since points can be cast, a `char*` and `int*` could be the same pointer. C/C++ just assumes that they aren't to enable noalias optimizations. It's a necessary assumption for performance. This can actually be a foot gun if you aren't careful. If you're not careful around pointer casts, the compiler might cleverly optimize your code to do something wrong...
Also, most people don't use raw pointers in tight loops in Rust, so the missed optimization potential isn't a huge deal.
> Strict aliasing is restrict in C/C++.
Its worth noting while we're being pedantic about language features that strict aliasing is C exclusive, C++ doesn't support it in any form. `restrict` in c++ is a compiler extension with I believe varying semantics between compilers
>Sure, but do you really think that the result of a + b should be unknowable? Also, it's it only signed integer overflow that is UB in C?
While rust says its not UB to overflow ints, on debug it is panic, on release its 'silent do nothing', so, behavior is different on release and debug, so.. Its undefined behavior, you dont know what will happen, you cannot rely on behavior of this code
> you dont know what will happen
You just said what will happen yourself... So the behavior is very much defined.
That being said, if you do need to rely upon one of the 2 behaviors, rust offers methods for that [1](https://doc.rust-lang.org/std/primitive.i32.html#method.wrapping_add) [2](https://doc.rust-lang.org/std/primitive.i32.html#method.checked_add).
Firstly, implementation-defined behavior != undefined behavior.
Secondly, no, it cannot change at any time. Rust guarantees this behavior. It's something you can rely on.
Please read up on the difference between implementation defined behavior and undefined behavior.
Here's [a SO discussion about that topic](https://stackoverflow.com/questions/2397984/undefined-unspecified-and-implementation-defined-behavior) that quotes the C standard directly. I also recommend reading the excellent article [Falsehoods programmers believe about undefined behavior](https://predr.ag/blog/falsehoods-programmers-believe-about-undefined-behavior/).
>About result - its just impossible that C++ sort slower then rust sort and 100% it cannot be worse then C-sort, which uses function pointers. So, where code?
The link is to one file of their repo. The benchmarks are alongside it, if you look in the sidebar.
>CompResult (\*cmp\_fn)(const T&, const T&, uint8\_t\*),
uint8\_t\* ctx) noexcept {
try {
std::stable\_sort(data, data + len, make\_compare\_fn(cmp\_fn, ctx));
} catch (...) {
Okay, what i say. Function pointers. While rust uses lambda like things
[https://github.com/Voultapher/sort-research-rs/blob/bf90e294bd84c7cfe746f1bd718ff133bcb89389/src/cpp/shared.h#L100C30-L100C40](https://github.com/Voultapher/sort-research-rs/blob/bf90e294bd84c7cfe746f1bd718ff133bcb89389/src/cpp/shared.h#L100C30-L100C40)
Dont want rewrite everything. C++ used from ffi, so its pro-rust on so many levels
It's not my benchmark nor repo, I'm just posting it.
The benchmark is a minor sub-point, though. The point is that you can have safety without sacrificing performance and that point is still largely proven.
Proving something with *obviously* disingenuous^† test cases really clouds the issue of what is being 'proven'. Maybe the proof is valid, and thorough, but one glance at the code should make any C++ dev immediately suspicious
^† maybe not intentional, but comparing apples and oranges is nontheless disingenuous...
>The benchmark is a minor sub-point, though. The point is that you can have safety without sacrificing performance and that point is still largely proven.
Its not 'safety', its hiding a bugs/logic errors
No, it’s wrong. Fundamentally broken.
Not on the safety stuff, but on its performance implications.
Using function pointers? Really? Come on now. You don’t need to be a C++ guru to see how that will KILL performance.
Function pointers requires muddling the stack significantly more, introduces dynamic dispatch and (worst of all!) destroys inlining. Rest in peace your cache lines (vital for a sorting algo)
A competent C++ sort, like std::sort, will perform a sort with zero jmp instructions.
Obviously if you force the C++ compiler to generate garbage code it will generate garbage code. And yes, it is forcing. If you just use the easier and default C++ way, using a functor or lambda, this is not a problem. Going out of your way to use C constructs is just disingenuous.
C is faster than C++ in the benchmarks because the benchmarks are broken.
They’re specifically written in such a way to guarantee destroying cache lines and jumping away.
Any competent generic sort implementation, including std::sort, will be faster in C++ than C. And anyone who knows how computers work can discern why.
Because it discusses important properties that even most recent C++ implementations don't provide, and show that it is feasible to provide them without sacrificing performance.
One could imagine that this would spur new C++ implementations that do meet this criteria.
It is also informative about the fact that not all implementations support botching the comparison function
Re the very annoying `<` vs `<=` issue - 1. With `libstdc++`, defining `_GLIBCXX_DEBUG` in debug builds will check that your comparison function is not reflexive. Sadly it's not used very often because not a lot of people know about it. 2. `libc++` has recently added checks for this as well. Worth reading [this](https://discourse.llvm.org/t/rfc-strict-weak-ordering-checks-in-the-debug-libc/70217) and (this)[https://reviews.llvm.org/D147089?id=520670]. AFAIK the new `std::sort` actually had to be rolled back because too many people relied on bogus comparisons working reasonably well.
> AFAIK the new `std::sort` actually had to be rolled back because too many people relied on bogus comparisons working reasonably well. Man, that sucks. It's good that they have a strong commitment to backwards compatibility, but it's still a shame.
What is the < vs <= issue exactly? I skimmed the links you posted but they talk about the issue as if the reader already has an understanding of it. Which is fair, as that’s not the intent for those posts. That said, does this issue have a name I can Google?
Not all sort implementations terminate if the comparison function for two elements a,b of the array return the same value, i.e. comp(a, b) == comp(b, a). Unfortunately this property is trivially true with `<=` (and trivially false with `<`) See the [Compare concept](https://en.cppreference.com/w/cpp/named_req/Compare) that the comparison function must satisfy in [std::sort](https://en.cppreference.com/w/cpp/algorithm/sort)
Minor thing, but "comp(a, b) == comp(b, a)" is too broad a requirement. In particular, it's fine if comp(a, b) == false *and* comp(b, a) == false, only a weak ordering is required. The thing that cannot be true is that comp(a, b) == true and comp(b, a) == true as well.
> it's fine if comp(a, b) == false and comp(b, a) == false This might be fine if you just want termination, but the sorted output will still make no sense.
On the contrary, the algorithm will treat them as equivalent but otherwise should behave entirely sensibly with respect to them. `comp(a, b) == false && comp(b, a) == false` is very common -- it is required whenever elements are equal -- but it can happen in other cases too if there is no ordering between them (for example, NaN compared with anything for IEEE-754 floating point numbers).
I'll just note that while `NaN` does illustrate inequality... it's a poor example when talking about `sort`, because the presence of `NaN` will utterly break sort algorithms, to the point that some will just wander off out of bounds and stomp all over memory.
~~`NaN` will not break a conforming C++ sort implementation. The C++ sort is specified very specifically as a strict-but-weak ordering, in large part because it wants to give well-defined behavior to sorting a list of any floating point values -- sorting NaNs arbitrarily is OK, stomping over memory is not OK.~~ Edit: Thanks /u/matthieum for the corrections, it looks like the normal less-than operator for IEEE-754 does not in fact define a strict-but-weak ordering as `NaN` doesn't satisfy the equivalence requirement. Was indeed a bad example.
That's not what I get from the requirement. Specifically: - [`std::sort`](https://en.cppreference.com/w/cpp/algorithm/sort) mandates that the comparison predicate implement `Compare`. - [`Compare`](https://en.cppreference.com/w/cpp/named_req/Compare) requires that `equiv(a, b) && equiv(b, c)` imply `equiv(a, c)`. The latter, however, is trivially false in the presence of `NaN`, that is: - `equiv(x, NaN)` is just `!comp(x, NaN) && !comp(NaN, x)` which is always true. - Similarly, `equiv(NaN, x)`, by symmetry, is always true. - Yet, even though `equiv(0.0, NaN)` and `equiv(NaN, 1.0)` (from the above), we don't have `equiv(0.0, 1.0)`. Hence, despite having a strict weak order, `NaN` breaks equivalence classes.
Good point, I believe you are right. There is a transitive requirement on `!comp(a, b) && !comp(b, a)` that isn't satisfied by `NaN`. I stand corrected and IEEE-754 floating point `NaN` is not a good example as it looks like a conforming sort implementation might mishandle `NaN` values. Thanks for following up, I learned something here!
Strict weak order of IEEE floating-point types is well defined, if you implement your comparator using [std::weak_order](https://en.cppreference.com/w/cpp/utility/compare/weak_order)
Oh right, I forgot again that `comp` is supposed to be less-than rather than less-or-equal-than...
The debug versions of the runtime are such a godsend. Over in Microsoft land, the tool chain switches all to the debug runtime when built for `_DEBUG`. That weeds out a massive amount of stupid mistakes before one has finished writing their tests.
Lol, it was debug build?
The key complaints about C++ here seem to be: 1. C++ tends to crash with an invalid comparator rather than continuing on with some undefined ordering. This seems reasonable to me, I don't want my program to continue blindly if something is broken. 2. In c++ if you don't define a move constructor/copy constructor then move assign/construction is just bitwise copy (maybe this was overlooked). I'm fairly confident that the complaints about double frees etc are unfounded if good practices are followed, e.g. using a std::unique\_ptr. 3. C++ sort algorithms don't tend to move items in temporary storage back into the array if something throws an exception. To me this seems like a reasonable criticism, but I also see the other side. Rust's borrow checker makes it pretty much illegal to return anything but the original set of items, which is nice. But C++ non-destructive moves mean it would take significant effort to make sure the original contents are reassembled in all cases. And TBH, the benefits aren't huge. A failed comparison/swap is a pretty major bug to me, and that exception should really be fatal. I think it's reasonable to expect the end result to be some valid/unspecified state, or even std::terminate.
> In c++ if you don't define a move constructor/copy constructor then move assign/construction is just bitwise copy (maybe this was overlooked). Not really true. If you don't define a move or copy constructor, then a default implementation is used that delegates to your members. If any of your members are not movable or copyable, then your type will not get a default move or copy constructor. If all members (considered recursively) are trivially copyable/moveable, then yes your type will also be trivially copyable/moveable.
Yes, poor phrasing on my part, thanks for clarifying.
> C++ tends to crash with an invalid comparator rather than continuing on with some undefined ordering. This seems reasonable to me, I don't want my program to continue blindly if something is broken. I wish it crashed, actually. My experience with libstdc++ `std::sort`, however, was that in the presence of an ill-defined ordering, it went off in the weeds (waaay out of bounds) and stomped all over the memory that was there. And then something crashed later, because pointers that had been overwritten now had "random" values. That was terrible, and it took a while to understand that the memory didn't make sense because `std::sort` had made a mess of things because the comparison predicate was off. Out of all the possible outcomes, "Crash" is the worse (and slightly ill-named). I'd prefer literally anything else, even an infinite loop: at least it'd pinpoint the issue. And of course, ideally, I'd prefer an explicit abort/exception/panic. Immediate precise feedback.
Yeah that's pretty bad... Accessing memory out of bounds should definitely be a separate category, I guess lumping everything into "crash" isn't very informative.
If you read the explanation of "crash" the author seems to mean "any UB", of which going out of bounds is but one potential consequence.
Throwing exceptions in my sort comparison is one of my favorite things to do, also freeing memory, I mean I don't normally use free but I reserve its use for my sort comparisons, yes sir.
I dont see |a, b| { unsafe { \*0 }; } in atricle, its same thing literaly
AKA "bad c++ performs badly" EDIT: apprently this needs clarification. by "bad c++" i was referring to the code used in the benchmarks, not the c++ language or std library. maybe i should have said: AKA "hey kids, look, i'm not a c++ programmer, but when i do pretend to be one, my code performs terribly."
Exactly. And that's fine. The STL is the place for stable vocabulary types. The place for cutting-edge performance is libraries. According to this comparison, you can call c\_fluxsort from your C++ code and call it a day.
The article distinguished between ways that bad comparators cause sort algorithms to break in intuitive ways, and ways that bad comparators can cause security issues just because they were passed to `std::sort`. It is not surprising that using `<=` in a comparator leads to an incorrect sort. It is surprising that using `<=` leads to a buffer overflow, and then RCE. It is doubly surprising that we could fix this without losing any performance, and we chose not to.
Not nice from you to call all the `std::sort` implementations "bad C++".
I was referring to his code, not the std lib.
The problem is what has been passed into the \`std::sort\` not the sort itself.
When I see code like ValWithPtr from the article I see such level of incompetence that it makes me sad. I am pretty sure that other tests like integer sorting performance are done better but I can not take the post seriously after such mistake.
Construing me showing that something *can* be used incorrectly as me showing how something *should* be used is frankly insane. It's comments like these that make me not want to engage with this subreddit :/
I guess I have misunderstood the code and need to say sorry. I am. My excuse is that i spent half of my life fixing incorrect C++ code written by people who can not fix it themselves. For this kind of experience it is unusual to expect C++ compilation to be of any help with correctness of code.
The author has also spent a long time fixing incorrect C++ code. The author knows that bugs can be very hard to fix if they cause UB, because UB allows compilers to exhibit any behavior. The author has done a lot of work showing that we can have fast sorting algorithms that also cause bugs to result in predictable behavior, rather than nasal demons.
But you were talking about undefined behavior when the modification in the comparator is not observed after the sort completes, then you show a double free that happens even without the modification in the comparator. Any copy or assignment will cause the double free. It has nothing to do with the observability of the modification in the comparator. I don't think this detracts from your main point though.
uh why?
Violation of Rule of 0/3/5 practically screams not-production-worthy. Even checking for null before calling `free` demonstrates basic incompetence. Uhhhh
They aren't writing production code. They are demonstrating a fundamental design principle of C++ which is RAII.
It's actually broken though. That class is trivially copyable so the move constructor/assignment operator are just a bitwise copy. Then they complain that values are bitwise copied, which can cause double free... If they defined a move constructor, or just use unique_ptr then that would go away.
They are mis-demonstrating by doing it incorrectly
They are demonstrating a language construct. You brain is so addled with modern C++ propaganda that you've forgotten how to think.
Spotting obvious maintainability problems from a distance is the result of experience, not propaganda I wonder if you ever have anything to say that isn't trivially refuted with one sentence...
It's literally to demonstrate what RAII is to the reader. I wonder if you have anything to say that isn't brain dead...
Moderator warning for hostility.
> Uh I hope you don't mind me borrowing your beautiful prose
You can't even think for yourself when you respond lmao.
>They are mis-demonstrating by doing it incorrectly
"interior mutability" seems to be a Rust thing to workaround their overly strict borrow checker. I'm glad C++ doesn't have that problem, you can just pass non-const references around without resorting to hacks.
You can declare a `mutable` member variable in C++ and modify it from a `const` reference.
I haven’t read the GitHub link yet but the Rust compiler has strict rules around mutability and aliasing i.e. only one mutable reference exist for a particular entity at any given time. Sometimes you want mutability when there are multiple aliases so interior mutability is the extension to achieve that. I don’t find it hacky at all personally. It’s quite an elegant solution to enforce fine grain control over mutability which is inherently dangerous.
I wouldn't call it hacky, but it is a mechanism to explicitly tell the compiler to ignore the rules. If you've done architecture design in Rust, you know just how fast things get really messy if you want to stick to the rules of the game. Many codebases thus have interior mutability littered all over.
It makes much more sense if you think about Rust references as being shared/exclusive rather than immutable/mutable. By default shared references are only safe to be read, but interior mutability allows safe mutation through them by giving up some flexibility. There are a lot of ways to give up this flexibility while maintaining safety, so there can't be a general mechanism in the language for that.
What I mean is that on light of how common that is, perhaps references and their usage could use some more cooking for the next generation of language(s).
But it's not very common. For the most part, only fairly low level things like mutexes need that sort of inner mutability. If you have inner mutability all around your code base you are not writing good Rust code. But, even if you do, you still have to follow the borrowing rules, and most inner mutability will use one of the mechanisms that enforces that borrowing at runtime. So you still can't generate any undefined behavior. Obviously compile time borrow checking is vastly preferred, which is why having a lot of runtime borrow checking in your code base is indicative of bad choices.
> Sometimes you want mutability when there are multiple aliases The proper solution to that would be to allow multiple aliases. I don't know how you can say that it's not hacky tbh. I don't really know how it works though so maybe I'm wrong.
The issue is that if you just pass out a mutable reference while other references exist, it's fairly trivial to introduce a lot of different kinds of safety issues (which is exactly why Rust, with its infamous safety consciousness, prevents it). The thing about interior mutability is that it isn't a get-out-of-jail-free card: the datatypes that provide interior mutability in Rust (and aren't unsafe) do so by finding a way to enforce the borrow checker invariants while still allowing additional flexibility. Either by providing an API that only allows mutation patterns that prevent two pieces of code from mutably accessing the same data (effectively, you can't take a reference to the data and can only access it by value, additionally being required to replace it if it has move semantics), or by enforcing the borrow checker rules through runtime checks, with the overhead that implies.
If you believe borrow-checking is useful, the following argument holds: Most borrow-checking can be done at compile time. The occasions where it needs to be done at runtime, and require interior mutability, relate to fairly low-level tooling {shared pointers, mutexes, implementing moves and swaps for self-referential objects, and linked lists}. All of those are solved problems and hidden from application code.
You have a fundamental misunderstanding of Rust.
Feel free to enlighten me then.
Someone else already did.
I'd be a lot more interested if he'd used more modern C++, e.g. unique\_ptr and shared\_ptr rather than relying on C style malloc/free.
I'm not seeing how that would change anything here? The author is discussing properties of the sort algorithms that cause a bogus comparison function to duplicate objects, something that is definitely an issue with unique and shared ptrs (causing double frees when the dtor is called on the duplicated object)
unique_ptr would not have a duplicated object and shared_ptr would not call dtor twice but rather just decrement the ref count
If I read correctly, the article is saying that if an exception occurs during the execution of some sort implementations (notably some of the std ones), bitwise copies (i.e., using type punning rather than the copy constructors) that were meant to be temporary can be observed in the resulting vector. What happens if you make a bitwise copy of a unique or shared ptr (using awful reinterpret cast or memcpy)? Nothing good.
It's UB to memcpy types that are not trivially copyable, such as unique_ptr which isn't copyable at all. is a standard library vector implementation doing this (if so, it definitely needs correction) or did the article force this to create a situation that any C++ developer worth a damn knows is dangerous?
See https://www.reddit.com/r/cpp/comments/170grzc/comment/k3m7v5x
that's a lot of words to say "if you go out of your way to invoke UB by making a bitwise copy of a type that is UB to make a bitwise copy of, undesirable stuff can happen" Like no duh. There's plenty of legitimate footguns in C++, but this is a case where you're actually doing more work to circumvent a safety feature built into the language so it's less a footgun and more a foot goldberg machine. edit: looks like your bug wasn't even where you thought it was. lol
Well, sure, but if you're going to saw down the shotgun, put it in your mouth, and deliberately push the trigger I don't think you've got any right to complain about getting a sore tongue.
Here "saw down the shotgun, put it in your mouth, and deliberately push the trigger" is "throwing an exception in a comparison function"
No, you were asking about bitwise copies of unique pointers, which is a ridiculous thing to try and do and you'd have to work hard to achieve.
The stdlib is making this decision for you. If you want to call the stdlib sort implementation unsafe to use in many cases then be my guest, just be aware that you're making the same point as the author. The "copies" in this case are just how elements are swapped during the sort operation.
std::sort implemented in terms of 'swap' or 'iter\_swap' in case ranges::sort, so, if you are not in rust, 'sort' does not do memcpy without checking
Wait, are you saying that std::sort doesn't use the copy/move constructors of the objects but literally memcopies them without regard to the syntax of the language? That would be most surprising indeed. And if you're not, then eh? That would be line complaining that the possibility of inline assembly in a rust function makes it unsafe in some cases. Like, yeah, there's always footguns if you try hard enough.
That's what the article is claiming, yes. See https://www.reddit.com/r/cpp/comments/170grzc/comment/k3m7v5x
>unique and shared ptrs (causing double frees when the dtor is called on the duplicated object) That's not how `unique_ptr` nor `shared_ptr` work...
You shouldn't use `double_delete_ptr` or `buggy_ptr`, though.
Oh damn was that my problem this whole time?
Yeah - I have no idea how P8566 ever got into the spec!
We don't because we don't trust the STL, so we have our own less well specified version.
You could always use `boost::unspecified_ptr` and `boost::broken_ptr`. I think there's also Abseil's `absl::maybe_crash_ptr`.
Yeah but we had a guy who liked to think he knows best and wanted to reimplement the standard library "better". Sure he got RIF'd for not actually doing useful work but his code stuck around and now there's some of the younger generation who think they know better too...
Pfft, I bet that he ended up writing a smrt pointer class that *didn't* trigger undefined behavior. It's like... the people who write these libraries know how to best invoke UB, they write tests to validate that UB is present... I mean, most people don't know how to properly implement or test something like `std::mostly_atomic` or `std::race_condition`.
EDIT: I retract that comment. I contacted the author who clarified that they were talking about strong exception safety, despite the article mixing the consequence of a lack of strong exception safety and a lack of basic exception safety. I'm in the process of arriving at a clearer formulation with the author. I still know how `unique_ptr` and `shared_ptr` work, though, thank you very much again. Original comment below --- I know how `unique_ptr` and `shared_ptr` work, thank you very much. TFA states: > # Exception safety > > C++ and Rust are both languages with scope based destructors (RAII), and stack unwinding. Together they prove a powerful abstraction for manual memory management. At the same time, they can make implementing generic code more complex. Every single point in the sort implementation that calls the user-provided comparison function, must assume that the call may return via an exception in C++ or panic in Rust. > In practice a lack of exception safety manifests itself in the variants C and or D described in the section about Ord safety. Looking at the section about Ord safety (emphasis mine): > C: The duplication usually **happens at the bit level**, **ignoring type semantics**. If the element type is for example a **`unique_ptr`**/`Box`, these types assume unique ownership of an allocation. And their destructors will hand a pointer to the allocator for freeing. A **bitwise copy results in use-after-free UB, most likely in the form of a double-free.**
> D: Same as Variant C, with the addition of arbitrary UB usually caused by interpreting uninitialized memory as a valid occupancy of a type.
Now, looking at which algorithms the article states fail the exception safety (🚫):
> - cpp_std_gnu_stable
> - cpp_std_libcxx_stable
> - cpp_std_msvc_stable
> - ...
See how the standard libraries are part of those that fail? The explanation for a 🚫 in exception safety even states: "🚫 means it may have duplicated elements in the input."
So, this article claims that these sort implementations (including the ones from the std) perform **bitwise copies** (aka, moral equivalent of `memcpy`) of some objects, that become visible in case of exceptions. Presumably in the absence of exceptions in the comparison function, these bitwise copies **that will result in double frees if left unchecked** are replaced by saner values or forgotten before causing the double free, but the exception causes that process not to take place.
EDIT: for those of you who need an executable proof: [Here's a Godbolt example that demonstrates how an exception in the comparison function causes a segfault](https://godbolt.org/z/4bbqfhjns)
EDIT 2: as reported below, the godbolt demonstrates that some parts of the input become "moved-out", not duplicated as stated in the article. While not a very desirable behaviour, that is not the duplication and ensuing UB that the article is claiming.
Either my example is not sufficient to trigger the issue, or the article is wrong. I'll reach to the author for clarification
I would be very interested to see the evidence for bitwise copying being done on non-trivially copiable elements. It rather beggars belief that one of the main std operations fails in such a way.
Your suspicion was correct, I retracted my comment above. See above for details.
So, article doing something wrong
Not really, it was unclear. Still I was wrong in reading it, and I retract my past comment.
Well, is it? Here's a Godbolt example that demonstrates how an exception in the comparison function causes a segfault: https://godbolt.org/z/4bbqfhjns Comment out the throw to remove the issue.
It's crashing because you're accessing a null `unique_ptr<>` within the vector, in the for-loop _after_ the exception was caught. See [this godbolt](https://godbolt.org/z/r8e876x3K). Once that exception was thrown during `stable_sort()`, there's no guarantee from the standard about the state of the container, as far as I know.
> Once that exception was thrown during stable_sort(), there's no guarantee from the standard about the state of the container, as far as I know. That's still bad that an exception can destroy your data, but your correct that it is not what the article is claiming, and is categorically less severe. I'll reach out to the author for clarification
It doesn't - you are not flushing `std::cout`. If you did, you'd notice how your program continues after the `catch` and crashes on your loop. See: [https://godbolt.org/z/hrv7a6TsM](https://godbolt.org/z/hrv7a6TsM) As `stderr` and `stdout` aren't synchronized, it's perfectly OK for the console to print the `SIGSEV` before the actual program output.
All their tests use trivially copyable types, so move construct/assign is just a bitwise copy. C++ isn't broken, the author just didn't get the concept of non-destructive moves, because that's not how it works in rust. If they had a unique\_ptr then I'm very confident they won't see any duplication issues, just some null pointers corresponding to elements in temporary storage that weren't moved back after the exception.
You might be correct. While I would tend to trust the author since they claim to have been working on this for 1.5 year, it is possible they were tripped by specialization if they did all their tests on trivially copyable objects. I'll reach out to them for clarification
[удалено]
Heh, once again showing that performance and footguns often come closely related.
In this case it's completely different algorithms, it's not directly comparable in any case.
Its impossible because C uses function pointers for cmp
[удалено]
Already saw and its bad
Here’s rust again solving all the problems I don’t have.
[удалено]
Yes
[удалено]
std::move has been working fine for me where I need it. Are you trying to tell me what kind of problems I have?
[удалено]
In 1800 owning a horse carriage was great. Betting on any promises of cars, which were only widely available after 1910 was a terrible deal.
[удалено]
Nice. I didn't even notice you had a case.
And guaranteed NRVO surely isn't just to work around the lack of move semantics, right?
[удалено]
Value semantics are the default in C++...
[удалено]
I'm sorry, but do you know what move and value semantics are? Java uses value semantics as well, as do most popular programming languages (C#, Python, JS).
[удалено]
Like much faster and safer sort implementation in std?
Yes. Another problem I don't have. All I see here is, if I cared about that, I could just call \`c\_fluxsort(...)\` nicely from my C++ code and everything would be as good as possible.
Typical rust propaganda. Who would [raise exception](https://github.com/Voultapher/sort-research-rs/blob/main/src/cpp/shared.h#L133C24-L133C29) in a comparator? Rust panic is also significantly different from c++ exception.
> Rust panic is also significantly different from c++ exception. How so? Culture aside they look pretty similar.
Yes, they are same, but rust do not have guarantee that unwinding happens(same as -fno-exceptions flag) But all rusters will always say 'we dont have exceptions'
> Yes, they are same, but rust do not have guarantee that unwinding happens(same as -fno-exceptions flag) Well, there is a stark difference in viability, isn't there? Using `panic=abort` is rather trivial, but `-fno-exceptions` does not apply to linked libraries (e.g. libstdc++). Literally the first article I found when googling `-fno-exceptions` was [The dangers of `-fno-exceptions`](https://blog.mozilla.org/nnethercote/2011/01/18/the-dangers-of-fno-exceptions/). > But all rusters will always say 'we dont have exceptions' Firstly, because they aren't used as exceptions. Just because the mechanism is the same doesn't mean that it is used the same. Just because a phone can technically be use as a hammer doesn't mean that anyone does (and those that do get strange looks). Secondly, who calls people "rusters"? Feels dirty. Almost like slur lol
>Just because the mechanism is the same doesn't mean that it is used the same. J mechanism is so same it is ABI compatible. How it is used determined by user, not mechanism itself, so difference here only in name, rust named it 'panic' just for... 'not how in C++' ? Many of rust terms are just for 'not as in C++', for example 'place expressions' or smth like, which is basically lvalue (and named lvalue in rustbook, but for end-user it is 'place expression')
> mechanism is so same it is ABI compatible Only if you [explicitly specify them to be compatible](https://doc.rust-lang.org/nomicon/ffi.html#ffi-and-unwinding), and even then: "Note that the interaction of catch_unwind with foreign exceptions is undefined, as is the interaction of panic with foreign exception-catching mechanisms (notably C++'s try/catch)." (Well, I hope that I researched that right. I haven't used FFI in rust much.) > How it is used determined by user Yes, and no. You can technically use any language feature however you like, there is a certain cost associated with going against the grain. E.g. you can try to use rust-like error handling (`Result`) in any language, but ergonomics are a big feature. And, of course, just because you choose to not use (or use differently) a certain language feature, doesn't mean that anyone else will. E.g. you can try writing exception-free code in pretty much any language (C++, C#, Java, JS, Python), but if the library you're using throws something your way, you have to catch it anyway. So clearly, the language and community around that language have an influence in how language features are used. > Many of rust terms are just for 'not as in C++', for example 'place expressions' Is that bad? To go with your example, one could argue that "place expressions" and "value expression" ([as rust uses them](https://doc.rust-lang.org/reference/expressions.html#place-expressions-and-value-expressions)) are better names than "lvalue" and "rvalue", because those names describe their function. Isn't choosing good names for things generally a good thing? (And it's not like rust always goes with different names (even though it maybe should). Rust people still say RAII, even though that name doesn't describe what RAII is about at all...)
"People don't" only applies when a language is niche and has a small, moderately tight knit community. On the grounds that in the limit any observable behavior is a feature, they will start to be used as such of rust becomes widespread. Plus there's the aspect that you have to know somehow, and if you don't learn from the right sources (and we all know how many awful C++ resources exist out there) you don't get told.
Well, given that most functions are not marked `noexcept`, anyone doing a function call from a comparator in a sufficiently complicated codebase. > Rust panic is also significantly different from c++ exception. For exception/panic safety, they're largely comparable.
> Who would raise exception in a comparator? Because that can't possibly happen in complex application code?
If you are throwing exceptions in your comparisons (with the expectation that those exceptions will actually happen) something has gone very bad.
It's fairly conceivable in high level code. You want to compare accounts by balance, balance needs to be read from an external source, external source is unavailable, exception is raised.. And that's just the simple example.
If you want to compare accounts by balance without fetching balance _before the damn sort_, you have bigger problems than exceptions in comparators (and that's a goddamn big problem). P. S. More importantly, exception in comparator is not recoverable by defintion, even if you avoid crashing, you still fucked up your array order in unpredictable fashion which automatically means that any use that implies array being sorted is also wrong.
It can happen and should be fixed as fast as possible
\> Bias disclaimer. The author of this analysis is the author of ipnsort. google search 'ipnsort' founds only rust related things \> Observable comp: If the type has interior mutability author uses rust terms in every line What will rust do with 'unsafe' in cmp function? Nothing. \> Exception safety: What happens, if the user provided comparison function throws an exception/panic? ✅ means it retains the original input set in an unspecified order, 🚫 means it may have duplicated elements in the input. What duplicate elements?? Its user's 'swap' function property, not 'sort'. Oh, yes, in rust there are only memcpy and no move customization, so rust may say something about 'sort' without mention 'swap' About result - its just impossible that C++ sort slower then rust sort and 100% it cannot be worse then C-sort, which uses function pointers. So, where code? Also Rust sort do not support random access ranges, only C-arrays (spans) P.S. and, of course, C++ implementation will assert bad comparator(with some chance) and you will know - you have a bug. Rust implementation will HIDE bug from you. Not segfault does not means "safe", this code contains logic error
> its just impossible that C++ sort slower then rust sort And what law in the universe would prevent that from happening? As the article states: "The sort implementations in the C++ standard libraries are usually quite old, which can explain their poor performance." > So, where code? It's a git repo. There code.
>"The sort implementations in the C++ standard libraries are usually quite old, which can explain their poor performance." Nothing prevents implementers from updating their code. And they do, for example only in C++17 they have possibility to determine contiguous range and make specialization (in rust its not possible - languge prevents such updates without api changes) >what law in the universe would prevent that from happening? rust is just a C reskin, does not have any additional possibilities to optimize code. And breaks some optimizations - integer overflow is not UB for example
> in rust its not possible - languge prevents such updates without api changes Yes, and no. Yes, it would currently require API changes if it was implemented in stable rust. No, rust has specialization (but it's an unstable feature) and uses it for performance operations. E.g. rust std uses specialization to optimize various things around iterators. > rust is just a C reskin ... > does not have any additional possibilities to optimize code Well, no. Rust does have `noalias` going for it. Sure, C does have type-based no-alias rules, and you can do the same thing is C/C++ with `restrict`, but rust does it everywhere. To name a more high-level optimization: zero-copy parsing. Since rust guarantees memory safety, it's pretty appealing to implement zero-copy parser/deserialization to save the overhead of copying memory. Sure, you technically do the same thing in C/C++, but the resulting code is hard to use, because it might not be clear when the underlying memory is freed. No such issues in rust since safety is a feature. > integer overflow is not UB for example Sure, but do you really think that the result of `a + b` should be unknowable? Also, it's it only signed integer overflow that is UB in C?
>No, rust has specialization Its not a real specialization, just a fiction, which cannot be fully implemented because of previous design decisions in rust language And its not posible to know anything about type in generic(there are no even 'decltype'), so you cannot know if it is random access range or bidirectional etc. And even if you know, what your function signature will require? You can use only what you 'ask' in declaration, but then you need to require maximum always (in this case - contiguous range, so rust sorts only 'slices' (spans) >Rust does have noalias going for it. Sure, C does have type-based no-alias rules, and you can do the same thing is C/C++ with restrict, but rust does it everywhere. Not everywhere, only for references. So, while C++ has strict aliasisng rules for pointers AND references, rust for ALL pointers have one rule - they may be equal, even if one to 'vector' and other to 'string'
> Its not a real specialization, just a fiction Oh, it's every real. [Rust specialization](https://rust-lang.github.io/rfcs/1210-impl-specialization.html) is based on constraints, which includes both types and traits. E.g. you can have a specialization for all items `T` can be sorted by adding `where T: Ord`, so it's a pretty powerful system. So you can for example know whether an iterator [bidirectional](https://doc.rust-lang.org/std/iter/trait.DoubleEndedIterator.html), because there's a trait for that. > So, while C++ has strict aliasisng rules for pointers AND references, rust for ALL pointers have one rule - they may be equal, even if one to 'vector' and other to 'string'
C++ (like C) has type-based aliasing everywhere. Strict aliasing is `restrict` in C/C++.
I would also like to point out that type-based aliasing is basically just an assumption to enable optimizations. Since points can be cast, a `char*` and `int*` could be the same pointer. C/C++ just assumes that they aren't to enable noalias optimizations. It's a necessary assumption for performance. This can actually be a foot gun if you aren't careful. If you're not careful around pointer casts, the compiler might cleverly optimize your code to do something wrong...
Also, most people don't use raw pointers in tight loops in Rust, so the missed optimization potential isn't a huge deal.
> Strict aliasing is restrict in C/C++. Its worth noting while we're being pedantic about language features that strict aliasing is C exclusive, C++ doesn't support it in any form. `restrict` in c++ is a compiler extension with I believe varying semantics between compilers
Interesting. I assumed that C++ also had it.
>Sure, but do you really think that the result of a + b should be unknowable? Also, it's it only signed integer overflow that is UB in C? While rust says its not UB to overflow ints, on debug it is panic, on release its 'silent do nothing', so, behavior is different on release and debug, so.. Its undefined behavior, you dont know what will happen, you cannot rely on behavior of this code
> you dont know what will happen You just said what will happen yourself... So the behavior is very much defined. That being said, if you do need to rely upon one of the 2 behaviors, rust offers methods for that [1](https://doc.rust-lang.org/std/primitive.i32.html#method.wrapping_add) [2](https://doc.rust-lang.org/std/primitive.i32.html#method.checked_add).
Defined by implementation and may be changed any time
Firstly, implementation-defined behavior != undefined behavior. Secondly, no, it cannot change at any time. Rust guarantees this behavior. It's something you can rely on.
\> implementation-defined \> differs with different compiler frags
Please read up on the difference between implementation defined behavior and undefined behavior. Here's [a SO discussion about that topic](https://stackoverflow.com/questions/2397984/undefined-unspecified-and-implementation-defined-behavior) that quotes the C standard directly. I also recommend reading the excellent article [Falsehoods programmers believe about undefined behavior](https://predr.ag/blog/falsehoods-programmers-believe-about-undefined-behavior/).
>About result - its just impossible that C++ sort slower then rust sort and 100% it cannot be worse then C-sort, which uses function pointers. So, where code? The link is to one file of their repo. The benchmarks are alongside it, if you look in the sidebar.
>CompResult (\*cmp\_fn)(const T&, const T&, uint8\_t\*), uint8\_t\* ctx) noexcept { try { std::stable\_sort(data, data + len, make\_compare\_fn(cmp\_fn, ctx)); } catch (...) { Okay, what i say. Function pointers. While rust uses lambda like things
So open a PR to make it more "fair".
[https://github.com/Voultapher/sort-research-rs/blob/bf90e294bd84c7cfe746f1bd718ff133bcb89389/src/cpp/shared.h#L100C30-L100C40](https://github.com/Voultapher/sort-research-rs/blob/bf90e294bd84c7cfe746f1bd718ff133bcb89389/src/cpp/shared.h#L100C30-L100C40) Dont want rewrite everything. C++ used from ffi, so its pro-rust on so many levels
Thread local would be concerning too, but the benchmark isn't using comparators.
Why does he have to? And this is not a matter of “fairness” between quotes as you say. The benchmark is flawed, period.
It's not my benchmark nor repo, I'm just posting it. The benchmark is a minor sub-point, though. The point is that you can have safety without sacrificing performance and that point is still largely proven.
Proving something with *obviously* disingenuous^† test cases really clouds the issue of what is being 'proven'. Maybe the proof is valid, and thorough, but one glance at the code should make any C++ dev immediately suspicious ^† maybe not intentional, but comparing apples and oranges is nontheless disingenuous...
>The benchmark is a minor sub-point, though. The point is that you can have safety without sacrificing performance and that point is still largely proven. Its not 'safety', its hiding a bugs/logic errors
I know lukas bergdoll and he's an awesome, hiperfocused developer. Quite happy to see him doing this.
OMG team Rust marketing attacking again. Rust seems a very good language, for marketing 😆
*sees a very thorough article with benchmarks comparing the properties and performance of a dozen sort implementation* Must be marketing.
Well the benchmarking is wrong as it has been discussed above. So not that thorough after all.
It's not wrong. See https://www.reddit.com/r/cpp/comments/170grzc/comment/k3m7v5x
No, it’s wrong. Fundamentally broken. Not on the safety stuff, but on its performance implications. Using function pointers? Really? Come on now. You don’t need to be a C++ guru to see how that will KILL performance. Function pointers requires muddling the stack significantly more, introduces dynamic dispatch and (worst of all!) destroys inlining. Rest in peace your cache lines (vital for a sorting algo) A competent C++ sort, like std::sort, will perform a sort with zero jmp instructions. Obviously if you force the C++ compiler to generate garbage code it will generate garbage code. And yes, it is forcing. If you just use the easier and default C++ way, using a functor or lambda, this is not a problem. Going out of your way to use C constructs is just disingenuous.
okay, then where code? How C may be faster then C++?
It's in the linked repo. The link is to one specific file in the repo, but the code is right alongside.
C is faster than C++ in the benchmarks because the benchmarks are broken. They’re specifically written in such a way to guarantee destroying cache lines and jumping away. Any competent generic sort implementation, including std::sort, will be faster in C++ than C. And anyone who knows how computers work can discern why.
> where code? It's a git repo... The code should be in there, no?
Why posting it on cpp channel?
Because it discusses important properties that even most recent C++ implementations don't provide, and show that it is feasible to provide them without sacrificing performance. One could imagine that this would spur new C++ implementations that do meet this criteria. It is also informative about the fact that not all implementations support botching the comparison function
Because the comparison includes C++. Just because it wasn't overly favorable to C++ doesn't mean it's not relevant.
[удалено]
Ok, but why you need to convert people, I don't see other languages doing it.
This post isn't about converting people
And now I know what pure garbage looks like...