Glidesort
Languages and libraries
sorting library
SHOW HN2023
389points
70comments
#85of 3,109 in 2023
Top 3%of 2023 by points
How HN took it
CuriousMostly questions and neutral comments
7 positive, 17 neutral or asking, 0 mixed, 4 critical, out of 28 comments about the project. Thread score +0.20.
Performance: 1 for, 3 againstIdea: 2 for, 0 againstExecution: 0 for, 1 againstDocs: 1 for, 0 against
The thread, comment by comment
Each row is a top-level comment and its replies, in HN's order. Select a cell to open that comment on HN.
positive neutral or mixed critical about another commenter or something else the maker
What HN said
What people liked
Interesting adaptive, low-memory design
From 2 comments
The ability to work with different memory sizes is pretty intriguing. How does the algorithm decide where and when to allocate?
timerol on HNI'm interested in seeing a comparison with blitsort. Like glidesort, it's stable, adaptive, and can be configured to use constant auxiliary memory.
10000truths on HN
Strong benchmark results, especially on newer hardware
From 1 comment
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?…
mlochbaum on HN
Objections
Slower than fluxsort on older Intel machines in independent benchmarks
From 2 comments
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…
mlochbaum on HNI 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…
mlochbaum on HN
Credit for prior work (fluxsort, quadsort) disputed
From 3 comments
> It is my impression that orlp suggests the only relation between glidesort and fluxsort is that they're both stable quicksorts. So what is the relationship then, in your eyes?…
orlp on HN> Keep in mind that glidesort is partly derived from fluxsort and many of its techniques were directly inspired by fluxsort/quadsort, while several others are implemented in a…
orlp on HNI will retract that you didn't mention memory-level parallelism back then, I lazily looked at the git blame and assumed it was introduced then. That was sloppy of me, sorry. > I…
orlp on HN
Requests
Benchmark source code and comparison against blitsort, pdqsort, fluxsort
From 3 comments
Any source available for your benchmarks here? I'd like to benchmark against pdqsort, fluxsort, etc. but the existing benchmarks use C so I either have to call glidesort from C…
mlochbaum on HNI'm interested in seeing a comparison with blitsort. Like glidesort, it's stable, adaptive, and can be configured to use constant auxiliary memory.
10000truths on HNSo how does this compare to PDQ, Crum, flux, etc? Do you have preliminary results?
nwmcsween on HN
C or C++ port
From 1 comment
Anyone have a C++/C port yet? :) Would love to try this out, though the source looks... difficult for me to do a naive port.
loxias on HN
Questions
How does the allocation and low-memory merging work
From 2 comments
The ability to work with different memory sizes is pretty intriguing. How does the algorithm decide where and when to allocate?
timerol on HNI used the word "allocate" imprecisely. (The plain English description in the README did a good job of explaining the up-front allocation needs.) What I meant to ask: How does…
timerol on HN
What is instruction-level parallelism and how does it help
From 1 comment
Pretty neat! So it looks like you have a few things happening in parallel. What is instruction level paralellism and how does it speed the sort up?
cdiamand on HN
Alternatives named
fluxsort
From 2 comments
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…
mlochbaum on HNMakes 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?…
mlochbaum on HN
pdqsort
From 1 comment
So how does this compare to PDQ, Crum, flux, etc? Do you have preliminary results?
nwmcsween on HN
blitsort
From 1 comment
I'm interested in seeing a comparison with blitsort. Like glidesort, it's stable, adaptive, and can be configured to use constant auxiliary memory.
10000truths on HN
quadsort
From 1 comment
> It is my impression that orlp suggests the only relation between glidesort and fluxsort is that they're both stable quicksorts. So what is the relationship then, in your eyes?…
orlp on HN