5 ms·

I was able to get glidesort running as part of the Robin Hood sort benchmark[1]. See [0]; it's a lot slower than fluxsort on random data. Wondering if I did som

I was able to get glidesort running as part of the Robin Hood sort benchmark[1]. See [0]; it's a lot slower than fluxsort on random data. Wondering if I did something wrong. Is cargo build --release with rustc 1.64.0 enough? Tried lto = "thin" in .cargo/config as well, which is ever so slightly faster. Also tried passing in a buffer one, then two, times the input length which didn't change things. Was this tested on x86? Commands to run to replicate my results are below. Clone rhsort and run them in that directory. The res/*.txt results are human-readable but you have to install my programming language[2] to generate the plot. Hey, you made me program in Rust. [0] https://gist.github.com/mlochbaum/7664a046d294dcce2f6cdb1db6ab4600 https://gist.github.com/mlochbaum/7664a046d294dcce2f6cdb1db6... [1] https://github.com/mlochbaum/rhsort https://github.com/mlochbaum/rhsort [2] https://github.com/mlochbaum/BQN https://github.com/mlochbaum/BQN ./wolfbench.sh mkdir res gcc -O3 -D NOTEST bench.c && ./a.out l > res/r_rh.txt gcc -O3 -D FLUXSORT -D NOTEST bench.c && ./a.out l > res/r_flux.txt gcc -O3 -D WOLFSORT -D NOTEST bench.c && ./a.out l > res/r_wolf.txt g++ -w -fpermissive -O3 -D SKACOPY -D NOTEST bench.c && ./a.out l > res/r_ska_.txt cd glide && cargo build --release && cd .. gcc -O3 -D GLIDESORT -D NOTEST bench.c -Lglide/target/release -lglide LD_LIBRARY_PATH=glide/target/release ./a.out l > res/r_glide.txt images/line.bqn res/r_{flux,wolf,ska_,glide,rh}.txt > images/rand_glide.svg

orlp 4y ago
Try running with the latest nightly Rust (`rustup update nightly`) and with `cargo +nightly build --release`. EDIT: I'm sorry, you need to specify this in your Cargo.toml, my earlier command was incorrect: glidesort = { version = "0.1.1", features = ["unstable"] } To get the best performance I use specialization for Copy types (such as integers) to compete with the assumptions that fluxsort and such can make, which is not available on stable Rust (unless glidesort were to be merged into the standard library). Without that I have to be more conservative with bounds checks. And even then there's a variety of places where I sacrifice performance compared to fluxsort and such in the name of safety, and the limitations that Rust gives me (in particular panic safety has cost me 10-15% performance). Also when you say x86, I assume you mean x86-64? I have not tested raw x86. What is your actual processor? EDIT 2: I believe this should also go in the Cargo.toml of glide in your repository, not in a .cargo/config [profile.release] lto = "thin"
- mlochbaum 4y ago
  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...
      - 4y ago
scandum 4y ago
I recently upgraded fluxsort, you might want to give v1.1.5.4 a spin. I also updated the benchmark to use actual natural runs and be less favorable to rhsort, sorry. ;-) I'm not surprised fluxsort is slightly faster, it's heavily optimized for gcc -O3. Since the primary techniques that give glidesort it's speed were copied from fluxsort and quadsort I'm expecting very similar performance, and possibly significantly worse performance on strings due to accessing 4 memory regions. Have you gotten it working with the wolfsort benchmark?
- mlochbaum 4y ago
  I did actually test out 1.1.5.4 in advance of this. I just used saved results instead of the new version for comparison because performance appears very similar on random inputs. I do see a lot of improvement in quadsort and most of the special-case benchmarks. I was planning to update my repository to grab the appropriate files from the fluxsort repository but if you'd update the wolfsort repo I wouldn't have to. Although maybe I should switch over to cloning fluxsort instead.
  - scandum 4y ago
    I'm planning to update wolfsort soon-ish. I did some work on a dropsort hybrid, like rhsort, though it's slower overall because I'm not quite brave enough to match the level of insanity (I mean this in a good way) that rhsort engages in. The latest fluxsort is probably identical on random, the new analyzer might perform slightly better on modern hardware. Probably safer to stick with wolfsort as I do tend to make sure that works with rhsort when I update.
  - scandum 4y ago
    I went ahead and updated bench.c for the wolfsort github.
    - mlochbaum 4y ago
      I get an error about goto small_range_test jumping over a lot of declarations. If I remove that goto/label, it all works very nicely, just have to link rhsort and modify sorts. Thanks!

orlp 4y ago

Try running with the latest nightly Rust (`rustup update nightly`) and with `cargo +nightly build --release`. EDIT: I'm sorry, you need to specify this in your Cargo.toml, my earlier command was incorrect: glidesort = { version = "0.1.1", features = ["unstable"] } To get the best performance I use specialization for Copy types (such as integers) to compete with the assumptions that fluxsort and such can make, which is not available on stable Rust (unless glidesort were to be merged into the standard library). Without that I have to be more conservative with bounds checks. And even then there's a variety of places where I sacrifice performance compared to fluxsort and such in the name of safety, and the limitations that Rust gives me (in particular panic safety has cost me 10-15% performance). Also when you say x86, I assume you mean x86-64? I have not tested raw x86. What is your actual processor? EDIT 2: I believe this should also go in the Cargo.toml of glide in your repository, not in a .cargo/config [profile.release] lto = "thin"

mlochbaum 4y ago
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...
    - 4y ago

scandum 4y ago

I recently upgraded fluxsort, you might want to give v1.1.5.4 a spin. I also updated the benchmark to use actual natural runs and be less favorable to rhsort, sorry. ;-) I'm not surprised fluxsort is slightly faster, it's heavily optimized for gcc -O3. Since the primary techniques that give glidesort it's speed were copied from fluxsort and quadsort I'm expecting very similar performance, and possibly significantly worse performance on strings due to accessing 4 memory regions. Have you gotten it working with the wolfsort benchmark?

mlochbaum 4y ago
I did actually test out 1.1.5.4 in advance of this. I just used saved results instead of the new version for comparison because performance appears very similar on random inputs. I do see a lot of improvement in quadsort and most of the special-case benchmarks. I was planning to update my repository to grab the appropriate files from the fluxsort repository but if you'd update the wolfsort repo I wouldn't have to. Although maybe I should switch over to cloning fluxsort instead.
- scandum 4y ago
  I'm planning to update wolfsort soon-ish. I did some work on a dropsort hybrid, like rhsort, though it's slower overall because I'm not quite brave enough to match the level of insanity (I mean this in a good way) that rhsort engages in. The latest fluxsort is probably identical on random, the new analyzer might perform slightly better on modern hardware. Probably safer to stick with wolfsort as I do tend to make sure that works with rhsort when I update.
- scandum 4y ago
  I went ahead and updated bench.c for the wolfsort github.
  - mlochbaum 4y ago
    I get an error about goto small_range_test jumping over a lot of declarations. If I remove that goto/label, it all works very nicely, just have to link rhsort and modify sorts. Thanks!