6 ms·

I think I will copy/paste my comment from a thread from yesterday (https://news.ycombinator.com/item?id=31098822 https://news.ycombinator.com/item?id=31098822),

by orlp 5y ago

I think I will copy/paste my comment from a thread from yesterday (https://news.ycombinator.com/item?id=31098822 https://news.ycombinator.com/item?id=31098822), which incidentally was also referring to pdqsort, as it is just as relevant here: Hi all, I'm the author of pdqsort. I recently held a talk at my institute on efficient in-memory sorting and the ideas in pdqsort, in case you're interested in hearing some of the theory behind it all: https://www.youtube.com/watch?v=jz-PBiWwNjc https://www.youtube.com/watch?v=jz-PBiWwNjc Next week I will hold another talk in the Dutch seminar on data systems design (https://dsdsd.da.cwi.nl/ https://dsdsd.da.cwi.nl/) on glidesort, a new stable sorting algorithm I've been working on. It is a combination of adaptive quicksort (like pdqsort, fully adaptive for many equal elements) and an adaptive mergesort (like timsort, fully adaptive for long pre-sorted runs). It is the first practical implementation of an algorithm I'm aware of that's fully adaptive for both. Like pdqsort it uses modern architecture aware branchless sorting, and it can use an arbitrary buffer size, becoming faster as you give it more memory (although if given a constant buffer size it will degrade to O(n (log n)^2) in theory, in practice for realistic workloads it's just a near-constant factor (c ~<= 3-5) slower). The source code isn't publish-ready yet, I have to still do some extra correctness vetting and testing, and in particular exception-safety is still not yet fully implemented. This is important because I wrote it in Rust where we must always give back a valid initialized array, even if a comparison operator caused a panic. But I do have some performance numbers to quote, that won't significantly change. For sorting 2^24 randomly shuffled distinct u32s using a buffer of 2^23 elements (n/2), glidesort beats Rust's stdlib slice::sort (which is a classic timsort also using a buffer of n/2) by a factor of 3.5 times. When stably sorting the same numbers comparing only their least significant 4 bits, it beats stdlib slice::sort by 12.5 times using 6.5 times fewer comparisons, both numbers on my Apple M1 Macbook. All of this is just using single-threaded code with a generic comparison function. No SIMD, no threads, no type-specific optimizations. Finally, glidesort with a buffer size of >= n/2 is faster than pdqsort.

aerowalk 5y ago
Amazing to see a former gg2 player do this :)
account-5 5y ago
Hats off to you. I remember doing an algorithms and data structures course a number of years ago and I could barely understand (merge|quick)sort.
xavxav 5y ago
>I have to still do some extra correctness vetting and testing, and in particular exception-safety is still not yet fully implemented. This is important because I wrote it in Rust where we must always give back a valid initialized array, even if a comparison operator caused a panic. But I do have some performance numbers to quote, that won't significantly change. Do you make extensive use of `unsafe` Rust? What other features do you use? I ask this as my PhD thesis is building a deductive verifier for (safe) Rust, and I'm always looking out for interesting challenges. If you would ever be interested in a collaboration proving your algorithm correct let me know :)
- orlp 5y ago
  > Do you make extensive use of `unsafe` Rust? Yes. Glidesort moves data back and forth between partially initialized buffers a lot, so unsafe code is unavoidable. I also need to concatenate slices that are adjacent in memory, which is impossible to do with safe slices (due to pointer provenance). Mixing pointers/slices in general is just a bad idea, so for the most part I simply use pointers. I use no other special (unstable) features, just pointers and ptr::copy(_nonoverlapping). > If you would ever be interested in a collaboration proving your algorithm correct let me know :) I might take you up on that, or at least ask you to take a look once I'm done polishing the code.
  - xavxav 5y ago
    > Yes. Glidesort moves data back and forth between partially initialized buffers a lot, so unsafe code is unavoidable. I also need to concatenate slices that are adjacent in memory, which is impossible to do with safe slices (due to pointer provenance). Mixing pointers/slices in general is just a bad idea, so for the most part I simply use pointers. Ah, that's frustrating, my tool Creusot is meant for the verification of safe code, though I also worked on unsafe code verification as part of the RustHornBelt project (upcoming PLDI paper). I'd still love to chat and see how far we can push verification, you can reach me via email at xldenis @ lri . fr
gavinray 5y ago
How is it that programmers are still discovering state-of-the-art algorithms? I just assumed Einstein-tier people had discovered all the optimal ways to do things by now. Do you have a process for coming up with these improved algorithms, or does it just start from a passing thought in your mind?
- wongarsu 5y ago
  The field of computer science is at best 180 years old, and the first compiler is a mere 70 years old. Based on the history of every other field of science it seems safe to assume that the majority of notable algorithms are still undiscovered. And that's ignoring that "optimal" is a shifting target. What's optimal on a 1960s computer where RAM is as fast as registers may not be optimal on a modern CPU with instruction-level parallelism and RAM that's orders of magnitude slower than registers.
  - throwaway894345 5y ago
    I'm of the impression that computer science isn't considered a "science" field despite the name. Anyway, stuff like this is largely just math; other science fields often move slower because you're at the mercy of natural experiments and expensive instruments (e.g., waiting for some burst of gravitational waves to arrive from some black hole collision that happened billions of years ago).
    - orlp 5y ago
      Computer Science is neither a science, nor is it about computers. It is an awful name. Computational mathematics would be significantly better. The worst part is that most people pursuing a computer science degree actually want to learn about software engineering, so most curricula nowadays disappoint both the people that want to become software engineers ("why do I have to learn about formal grammar automata") and those that want to become computational mathematicians ("why do I have to do a course on agile?").
    - wongarsu 5y ago
      Most of our day jobs are closer to engineering, but there is a very theoretical side of computer science, and algorithm design certainly fits there. As you said it has a lot of similarities to math, and there's no consensus on whether math is a science, so I won't comment on the "science-ness" of computer science. But I can say that mathematics is an ancient "science" which has been studied by great scholars for millennia, but many of the things we take for granted today are relatively recent: modern set theory was introduced 150 years ago by Cantor and Dedekind, meaning things like Russel's Paradox [1], Gödel's Incompleteness Theorem [2] and the Peano Axioms [3] have all been discovered after that, despite being taught in many (university-level) introductory math courses today. Rings are also relatively young [4]. In comparison, imaginary numbers are about 500 years old. 1: https://brilliant.org/wiki/russells-paradox/ https://brilliant.org/wiki/russells-paradox/ 2: https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_... 3: https://en.wikipedia.org/wiki/Peano_axioms https://en.wikipedia.org/wiki/Peano_axioms 4: https://en.wikipedia.org/wiki/Ring_(mathematics) https://en.wikipedia.org/wiki/Ring_(mathematics)

by orlp 5y ago

aerowalk 5y ago

Amazing to see a former gg2 player do this :)

account-5 5y ago

Hats off to you. I remember doing an algorithms and data structures course a number of years ago and I could barely understand (merge|quick)sort.

xavxav 5y ago

>I have to still do some extra correctness vetting and testing, and in particular exception-safety is still not yet fully implemented. This is important because I wrote it in Rust where we must always give back a valid initialized array, even if a comparison operator caused a panic. But I do have some performance numbers to quote, that won't significantly change. Do you make extensive use of `unsafe` Rust? What other features do you use? I ask this as my PhD thesis is building a deductive verifier for (safe) Rust, and I'm always looking out for interesting challenges. If you would ever be interested in a collaboration proving your algorithm correct let me know :)

orlp 5y ago
> Do you make extensive use of `unsafe` Rust? Yes. Glidesort moves data back and forth between partially initialized buffers a lot, so unsafe code is unavoidable. I also need to concatenate slices that are adjacent in memory, which is impossible to do with safe slices (due to pointer provenance). Mixing pointers/slices in general is just a bad idea, so for the most part I simply use pointers. I use no other special (unstable) features, just pointers and ptr::copy(_nonoverlapping). > If you would ever be interested in a collaboration proving your algorithm correct let me know :) I might take you up on that, or at least ask you to take a look once I'm done polishing the code.
- xavxav 5y ago
  > Yes. Glidesort moves data back and forth between partially initialized buffers a lot, so unsafe code is unavoidable. I also need to concatenate slices that are adjacent in memory, which is impossible to do with safe slices (due to pointer provenance). Mixing pointers/slices in general is just a bad idea, so for the most part I simply use pointers. Ah, that's frustrating, my tool Creusot is meant for the verification of safe code, though I also worked on unsafe code verification as part of the RustHornBelt project (upcoming PLDI paper). I'd still love to chat and see how far we can push verification, you can reach me via email at xldenis @ lri . fr

gavinray 5y ago

How is it that programmers are still discovering state-of-the-art algorithms? I just assumed Einstein-tier people had discovered all the optimal ways to do things by now. Do you have a process for coming up with these improved algorithms, or does it just start from a passing thought in your mind?

wongarsu 5y ago
The field of computer science is at best 180 years old, and the first compiler is a mere 70 years old. Based on the history of every other field of science it seems safe to assume that the majority of notable algorithms are still undiscovered. And that's ignoring that "optimal" is a shifting target. What's optimal on a 1960s computer where RAM is as fast as registers may not be optimal on a modern CPU with instruction-level parallelism and RAM that's orders of magnitude slower than registers.
- throwaway894345 5y ago
  I'm of the impression that computer science isn't considered a "science" field despite the name. Anyway, stuff like this is largely just math; other science fields often move slower because you're at the mercy of natural experiments and expensive instruments (e.g., waiting for some burst of gravitational waves to arrive from some black hole collision that happened billions of years ago).
  - orlp 5y ago
    Computer Science is neither a science, nor is it about computers. It is an awful name. Computational mathematics would be significantly better. The worst part is that most people pursuing a computer science degree actually want to learn about software engineering, so most curricula nowadays disappoint both the people that want to become software engineers ("why do I have to learn about formal grammar automata") and those that want to become computational mathematicians ("why do I have to do a course on agile?").
  - wongarsu 5y ago
    Most of our day jobs are closer to engineering, but there is a very theoretical side of computer science, and algorithm design certainly fits there. As you said it has a lot of similarities to math, and there's no consensus on whether math is a science, so I won't comment on the "science-ness" of computer science. But I can say that mathematics is an ancient "science" which has been studied by great scholars for millennia, but many of the things we take for granted today are relatively recent: modern set theory was introduced 150 years ago by Cantor and Dedekind, meaning things like Russel's Paradox [1], Gödel's Incompleteness Theorem [2] and the Peano Axioms [3] have all been discovered after that, despite being taught in many (university-level) introductory math courses today. Rings are also relatively young [4]. In comparison, imaginary numbers are about 500 years old. 1: https://brilliant.org/wiki/russells-paradox/ https://brilliant.org/wiki/russells-paradox/ 2: https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_... 3: https://en.wikipedia.org/wiki/Peano_axioms https://en.wikipedia.org/wiki/Peano_axioms 4: https://en.wikipedia.org/wiki/Ring_(mathematics) https://en.wikipedia.org/wiki/Ring_(mathematics)