5 ms·

Updating my system, going to take a little while... Partner in crime dzaima has tested (nightly, unstable, lto) and found it is somewhat better. Eyeballing, sti

Updating my system, going to take a little while... Partner in crime dzaima has tested (nightly, unstable, lto) and found it is somewhat better. Eyeballing, still ~20% slower than fluxsort. We're on fairly old Intel x86-64 CPUs, i5-6200U for me and i3-4160 for him. Does panic safety really cost 10-15% when sorting integers according to default comparison?

orlp 4y ago
I get these results for your benchmark on my machine: https://gist.github.com/orlp/d7123ede0143e15ab0f8a435b7dd10b4 https://gist.github.com/orlp/d7123ede0143e15ab0f8a435b7dd10b... Either way, I am not surprised that glidesort is a bit slower than fluxsort on older machines. They're less likely to take advantage of the interleaving techniques I use. > Does panic safety really cost 10-15% when sorting integers according to default comparison? Yes :( At least yes, if you don't want to duplicate your entire codebase. Look into the code of glidesort if you want to, all algorithm state has to be encoded inside structs at all times, to allow for recovery in case a comparator panics using the destructor. This negatively affects the optimizer for reasons I can't fully explain compared to having the state be in simple local variables.
- mlochbaum 4y ago
  Makes sense regarding instruction-level parallelism; someone else with an M2 measured and found performance near identical to fluxsort. What did you take those results on? Collected graphs below. Orson: https://matrix.org/_matrix/media/r0/download/matrix.org/ldcdlOgPlomyQQkOZfJJYFTT https://matrix.org/_matrix/media/r0/download/matrix.org/ldcd... i3-4160: https://matrix.org/_matrix/media/r0/download/matrix.org/OBwSggTQOxzTRgiKqPuCuTCu https://matrix.org/_matrix/media/r0/download/matrix.org/OBwS... (edit) i5-6200U update: https://matrix.org/_matrix/media/r0/download/matrix.org/vzDrAiRipacENfnTHbfSUHpa https://matrix.org/_matrix/media/r0/download/matrix.org/vzDr... M2: https://matrix.org/_matrix/media/r0/download/matrix.org/ZRTjgFvqKwPsUiQkAaDbAxJi https://matrix.org/_matrix/media/r0/download/matrix.org/ZRTj...
  - orlp 4y ago
    My results are on a 2021 Apple M1 MacBook Pro. And I'd like to reiterate it's not 100% apples to apples comparing fluxsort and glidesort directly. One would need to either completely implement glidesort in unsafe C throwing Rust-isms as move-only types and panic safety out of the window, or implement fluxsort in Rust with the move-only restrictions and with the ability to restore all data in case of a panic. Only then could you truly compare the algorithms 100% fairly.
    - nurettin 4y ago
      In this particular case it sounds like Rust is just making things more tedious rather than providing value.
      - kzrdude 4y ago
        The end result is a generic sorting algorithm for Rust, which can be used for a lot of things /in Rust/, so it adds value to the Rust ecosystem. The sorting algorithm doesn't add anything without users :) so for non-academic implementations, maybe using it in Rust projects is what the author wants. Rust is also quite open to contributions, so it might be exciting if there's a chance to have it in Rust std.
        nurettin 4y ago
        I understand that it is written in Rust for Rust's sake, but in this case it looks like it doesn't really provide any benefit to implement such an algorithm particularly in Rust due to Rust's memory model making it harder to sort integers efficiently.
        kzrdude 4y ago
        I think such issues can be resolved with some collaboration, it's too early to say right now at least.
- orf 4y ago
  Why does it matter if a comparator panics “using the destructor”? It’s unclear what this means
  - kzrdude 4y ago
    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).
    - orf 4y ago
      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)
      - jules 4y ago

orlp 4y ago

I get these results for your benchmark on my machine: https://gist.github.com/orlp/d7123ede0143e15ab0f8a435b7dd10b4 https://gist.github.com/orlp/d7123ede0143e15ab0f8a435b7dd10b... Either way, I am not surprised that glidesort is a bit slower than fluxsort on older machines. They're less likely to take advantage of the interleaving techniques I use. > Does panic safety really cost 10-15% when sorting integers according to default comparison? Yes :( At least yes, if you don't want to duplicate your entire codebase. Look into the code of glidesort if you want to, all algorithm state has to be encoded inside structs at all times, to allow for recovery in case a comparator panics using the destructor. This negatively affects the optimizer for reasons I can't fully explain compared to having the state be in simple local variables.

mlochbaum 4y ago
Makes sense regarding instruction-level parallelism; someone else with an M2 measured and found performance near identical to fluxsort. What did you take those results on? Collected graphs below. Orson: https://matrix.org/_matrix/media/r0/download/matrix.org/ldcdlOgPlomyQQkOZfJJYFTT https://matrix.org/_matrix/media/r0/download/matrix.org/ldcd... i3-4160: https://matrix.org/_matrix/media/r0/download/matrix.org/OBwSggTQOxzTRgiKqPuCuTCu https://matrix.org/_matrix/media/r0/download/matrix.org/OBwS... (edit) i5-6200U update: https://matrix.org/_matrix/media/r0/download/matrix.org/vzDrAiRipacENfnTHbfSUHpa https://matrix.org/_matrix/media/r0/download/matrix.org/vzDr... M2: https://matrix.org/_matrix/media/r0/download/matrix.org/ZRTjgFvqKwPsUiQkAaDbAxJi https://matrix.org/_matrix/media/r0/download/matrix.org/ZRTj...
- orlp 4y ago
  My results are on a 2021 Apple M1 MacBook Pro. And I'd like to reiterate it's not 100% apples to apples comparing fluxsort and glidesort directly. One would need to either completely implement glidesort in unsafe C throwing Rust-isms as move-only types and panic safety out of the window, or implement fluxsort in Rust with the move-only restrictions and with the ability to restore all data in case of a panic. Only then could you truly compare the algorithms 100% fairly.
  - nurettin 4y ago
    In this particular case it sounds like Rust is just making things more tedious rather than providing value.
    - kzrdude 4y ago
      The end result is a generic sorting algorithm for Rust, which can be used for a lot of things /in Rust/, so it adds value to the Rust ecosystem. The sorting algorithm doesn't add anything without users :) so for non-academic implementations, maybe using it in Rust projects is what the author wants. Rust is also quite open to contributions, so it might be exciting if there's a chance to have it in Rust std.
      - nurettin 4y ago
        I understand that it is written in Rust for Rust's sake, but in this case it looks like it doesn't really provide any benefit to implement such an algorithm particularly in Rust due to Rust's memory model making it harder to sort integers efficiently.
        kzrdude 4y ago
        I think such issues can be resolved with some collaboration, it's too early to say right now at least.
orf 4y ago
Why does it matter if a comparator panics “using the destructor”? It’s unclear what this means
- kzrdude 4y ago
  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).
  - orf 4y ago
    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)
    - jules 4y ago