3 ms·
Fun safety problems. Towards the end of this post, the author mentions a bunch of places where std::sort() blows up if your data or your sort rule doesn't exhi
by tialaramex 5y ago
Fun safety problems.
Towards the end of this post, the author mentions a bunch of places where std::sort() blows up if your data or your sort rule doesn't exhibit strict weak ordering. In some cases you get a bad sort, which feels fair enough since you violated the rules the sort algorithm is relying on, but in others it literally has Undefined Behaviour in C++.
Notably Rust's sort() and unstable_sort() do not have this problem, because of course these are safe Rust, and safe Rust doesn't have Undefined Behaviour. But why can this work?
First up, one bullet which gets dodged is that Rust's floating point types (f32 and f64) are not Ord. Rust acknowledges that NaN != NaN and therefore we can't expect to go around sorting a slice of floating point values. In C++ that's on the programmer, in C++ the fact you can write a < b means that type counts as ordered, even though it trivially isn't for several built-in types. So if you simply naively try to sort an [f32] Rust says you can't because it isn't Ord, you will need to write a lambda or whatever to Order these f32s and then if some of them are NaN your lambda is responsible for deciding what to do about that.
But even if we insist on getting in harm's way, safe Rust promises to protect us anyway. For example if I make an array of a thousand misfortunate::OnewayGreater<u8>s they're only one byte each, yet they all insist they're Ordered greater than each other and even than themselves, Rust's sort() doesn't cause Undefined Behaviour on this input. It may never succeed, since all the elements to be "sorted" insist they're greater than each other, but it definitely won't segfault, trash unrelated memory or cause chaos.
- nullc 5y ago> or cause chaos Running forever is pretty chaotic.
- ElectricalUnion 5y agoRunning forever is pretty stable. Halting is chaotic.
- tialaramex 5y agoA trivial infinite loop is Undefined Behaviour in C++ but it is a completely reasonable thing to write in Rust and works fine, in fact Rust's underlying loop is an infinite loop unless you explicitly provide some way to break out of it, which you usually will.
- mytherin 5y ago> But even if we insist on getting in harm's way, safe Rust promises to protect us anyway. For example if I make an array of a thousand misfortunate::OnewayGreater<u8>s they're only one byte each, yet they all insist they're Ordered greater than each other and even than themselves, Rust's sort() doesn't cause Undefined Behaviour on this input. It may never succeed, since all the elements to be "sorted" insist they're greater than each other, but it definitely won't segfault, trash unrelated memory or cause chaos. This argument feels like a difference in semantics, rather than any actual added safety. Rust will happily let you run the sort with an unstable comparator, which then leads to undefined behavior in the sense that the final sorting order, or whether the sort completes at all, is not defined by the standard and is instead dependent on the internal implementation. The fact that this is not called "undefined behavior" in Rust is a difference in semantics only. Added safety would be if Rust could detect the fact that the comparator is unstable and tell the user so they could fix the bug in their comparator. What is perhaps more relevant here than any safety provided by the Rust language is that there is only one Rust compiler. Relying on internal implementation details of that compiler is much more accepted, and the distinction between "internal compiler implementation detail" and "behavior defined by the standard" is a lot less relevant than it is in C or C++, which have many different implementations.
- quietbritishjim 5y ago"Undefined behaviour" has a very specific meaning (perhaps ironically) in programming language design. It means anything could happen, including crashing during the undefined operation (i.e. crashing during the sort() in this case), appearing to work but then crashing afterwards, or even crashing before the undefined operation starts! (Or doing other weird things, not just crashing - but a time travelling crash is already plenty weird enough for this discussion.) If Rust is able to define its sort() as only ever affecting the array passed to it, with the possibility of looping forever, then that is very well defined behaviour in comparison.
- FartyMcFarter 5y agoYup. If the only potential variation is on the resulting ordering, C/C++ would call this implementation-defined or unspecified than undefined. One example of unspecified behaviour is the order in which function call parameters are evaluated (meaning any order is OK, and it could vary from call to call). One example of implementation-defined behaviour is the value of sizeof(int).