Basics of Rust ownership semantics. Let's say you sort T values. T is generic, so you don't really know what it is, but maybe it's strings for example (allocated String values.)
The sorting algorithm moves around these values in memory to sort them.
Panic is implemented by unwinding: this means destructors of live values are called in each scope and the unwinding steps up into the calling frame and repeats the same thing. Eventually you might reach some place where other code (an "external observer") inspects the vector and values you were just sorting. So a panic in the middle of your algorithm risks exposing any temporarily out of order state to the world.
Thus, you can't put any state out of order, if it might become visible externally. Or - you setup a destructor of your own - that puts it back into order if a panic happens, so that it's not visible outside.
Unsafe blocks in Rust allows violating invariants temporarily in some cases. But all exits out of the function - those successful as well as any unwinding/panicking exits, need to present datastructures and values that are "in order".
Examples of ownership rules: can't copy these values, they need to exist exactly once inside the vector (not zero times, then they never drop (not invalid but a serious code smell), not multiple times, then we violate ownership).
Thank you for your reply :), I understand now - you can avoid some of the overhead by not worrying about this for some types (i.e simple ones like i32 without any custom drop/comparators) but there isn’t a way to generalise this and so you’d need to duplicate the implementation.
Interesting. Are you sure the trade-off is worth it? This seems like quite a specialist sorting implementation, restricting it to primitive types or even adding a “please don’t panic” caveat for a 15% performance improvement seems like it would be an OK trade off (even if it’s not very rusty)
But not everything can be fit into that. But there's a lot that can be done. And a lot of generic code can be omitted when instantiated for simpler types, etc.
The sorting algorithm moves around these values in memory to sort them.
Panic is implemented by unwinding: this means destructors of live values are called in each scope and the unwinding steps up into the calling frame and repeats the same thing. Eventually you might reach some place where other code (an "external observer") inspects the vector and values you were just sorting. So a panic in the middle of your algorithm risks exposing any temporarily out of order state to the world.
Thus, you can't put any state out of order, if it might become visible externally. Or - you setup a destructor of your own - that puts it back into order if a panic happens, so that it's not visible outside.
Unsafe blocks in Rust allows violating invariants temporarily in some cases. But all exits out of the function - those successful as well as any unwinding/panicking exits, need to present datastructures and values that are "in order".
Examples of ownership rules: can't copy these values, they need to exist exactly once inside the vector (not zero times, then they never drop (not invalid but a serious code smell), not multiple times, then we violate ownership).