5 ms·

> Faster Benchmarks?

vvanders 6y ago
Yeah, would be curious as well. There's two really awesome things about radix sort: 1. It scans in linear order, so if you tune your radix size to L1/L2 cache it will happily beat other "faster" algorithms thanks to the prefetcher. 2. If preserves ordering for keys with the same value. #2 makes is a really good depth-sorting algorithm for alpha rendering, and #1 just makes it darn fast. There's a nice floating point implementation out there for it as well.
- moonchild 6y ago
  > It preserves ordering for keys with the same value That's called a stable sort, and it's a standard property present in many sorting algorithms.
- corysama 6y ago
  vvanders, I believe you’ve worked in games so you might already know about how the PlayStation 1 kindof had radix sort baked into the hardware. The hardware had no Z buffer, so all polygons had to be ordered back-to-front using the Painter’s Algorithm for visibility. The hardware understood a linked list of polygons; as odd as that sounds. And, the standard practice presented by the API was to have a pre-allocated linear array of NOP list nodes forming a radix as the starting point for inserting sorted polys.
- beagle3 6y ago
  > it will happily beat other "faster" algorithms When it applies, there are essentially no faster algorithms - it’s O(n) if the word size is constant (it often is), which cannot be beat asymptotically. kr sort is only asymptotically better if word size is considered variable. It’s irrelevant if you have no radix to sort on - comparison sort is provably at least O(n log n) which is slower.
zem 6y ago
faster in the algorithmic rather than the performance sense
- rumanator 6y ago
  That's not what "faster" means. Computational complexity means expected asymptotic behaviour followig certain assumptions. More often than not don't happen in the real world, or don't take in consideration real-world properties such as tiered cache and the impact of cache misses.
  - MaxBarraclough 6y ago
    You're being downvoted, but it seems like a fair point. My favourite example: multiplication of very large square matrices. The algorithms with the best time complexity are never used in the real world. Under no realistic circumstances would they offer the best performance. In that case, it's not cache behaviour or branch-prediction that dooms the algorithm, but very intensive steps in the algorithm that are nonetheless constant-time, and so don't impact the complexity theoretic properties. Do we describe such algorithms as the 'fastest'? I wouldn't. They have the lowest time complexity. Not the same thing. https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm
    - cycomanic 6y ago
      TIL that the fastest way to multiply two numbers is by using a 1729-dimensional Fourier transform. Thanks!
      - MaxBarraclough 6y ago
        For a less impractical but still mind-bending algorithm, see Strassen's algorithm for large matrix multiplication. https://www.geeksforgeeks.org/strassens-matrix-multiplication/ https://www.geeksforgeeks.org/strassens-matrix-multiplicatio... , see also https://youtube.com/watch?v=ORrM-aSNZUs https://youtube.com/watch?v=ORrM-aSNZUs
    - 6y ago
beagle3 6y ago
In the big-Oh algorithmic complexity sense; in a loose sense, for any pair of implementations (radix sort, kr sort) there exists a word size w and a list size n such that If either w or n increases, the time for radix sort would increase more quickly than for Kr sort - and this, eventually kr would be faster and keep getting faster. (Assuming that the hash can indeed yield average O(1) access, which is probabilistically but not deterministically true) That said, word size w is, in almost all integer dieting problems, bounded by 128 (by 64 or even 32 with high probability) which makes it acceptable to regard as “constant” in which case both sorts are essentially O(n) and it all depends on specific implementations (with radix sort likely significantly faster in practice)
- adrianN 6y ago
  Big-O as commonly used in the CS literature sometimes doesn't translate to Big-O on actual computers. For example virtual memory translation can add a log term where you wouldn't expect it: https://pdfs.semanticscholar.org/1e90/c55362cf7793dc0b2521f61752f2d0135e12.pdf https://pdfs.semanticscholar.org/1e90/c55362cf7793dc0b2521f6...
  - jnxx 6y ago
    Yeah. I am wondering since a while whether well-known algorithms like the binary heap are still efficient on modern architectures, because their random memory access patterns.
    - lorenzhs 6y ago
      For priority queues, which implementation is optimal depends a lot on your workload (do you need addressability, i.e., a decreaseKey operation? What is the typical ratio of insertions to deletions? Are your keys integers?). I found some slide decks that are mostly in English with some German in between that might go some way to answering your question: [1] https://algo2.iti.kit.edu/sanders/courses/algen20/vorlesung.pdf https://algo2.iti.kit.edu/sanders/courses/algen20/vorlesung.... slide 180-207, there are some up-to-date measurements on slide 204 [2] https://nms.kcl.ac.uk/stefan.edelkamp/lectures/ae/slide/AE-AllgemeineVorrangwarteschlangen.pdf https://nms.kcl.ac.uk/stefan.edelkamp/lectures/ae/slide/AE-A... There are also parallel priority queues which might be useful depending on your problem, especially if it can be reformulated to operate on batches ("give me the 20 smallest items", "insert these 50 items").

Yeah, would be curious as well. There's two really awesome things about radix sort: 1. It scans in linear order, so if you tune your radix size to L1/L2 cache it will happily beat other "faster" algorithms thanks to the prefetcher. 2. If preserves ordering for keys with the same value. #2 makes is a really good depth-sorting algorithm for alpha rendering, and #1 just makes it darn fast. There's a nice floating point implementation out there for it as well.

moonchild 6y ago
> It preserves ordering for keys with the same value That's called a stable sort, and it's a standard property present in many sorting algorithms.
corysama 6y ago
vvanders, I believe you’ve worked in games so you might already know about how the PlayStation 1 kindof had radix sort baked into the hardware. The hardware had no Z buffer, so all polygons had to be ordered back-to-front using the Painter’s Algorithm for visibility. The hardware understood a linked list of polygons; as odd as that sounds. And, the standard practice presented by the API was to have a pre-allocated linear array of NOP list nodes forming a radix as the starting point for inserting sorted polys.
beagle3 6y ago
> it will happily beat other "faster" algorithms When it applies, there are essentially no faster algorithms - it’s O(n) if the word size is constant (it often is), which cannot be beat asymptotically. kr sort is only asymptotically better if word size is considered variable. It’s irrelevant if you have no radix to sort on - comparison sort is provably at least O(n log n) which is slower.

zem 6y ago

faster in the algorithmic rather than the performance sense

rumanator 6y ago
That's not what "faster" means. Computational complexity means expected asymptotic behaviour followig certain assumptions. More often than not don't happen in the real world, or don't take in consideration real-world properties such as tiered cache and the impact of cache misses.
- MaxBarraclough 6y ago
  You're being downvoted, but it seems like a fair point. My favourite example: multiplication of very large square matrices. The algorithms with the best time complexity are never used in the real world. Under no realistic circumstances would they offer the best performance. In that case, it's not cache behaviour or branch-prediction that dooms the algorithm, but very intensive steps in the algorithm that are nonetheless constant-time, and so don't impact the complexity theoretic properties. Do we describe such algorithms as the 'fastest'? I wouldn't. They have the lowest time complexity. Not the same thing. https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm
  - cycomanic 6y ago
    TIL that the fastest way to multiply two numbers is by using a 1729-dimensional Fourier transform. Thanks!
    - MaxBarraclough 6y ago
      For a less impractical but still mind-bending algorithm, see Strassen's algorithm for large matrix multiplication. https://www.geeksforgeeks.org/strassens-matrix-multiplication/ https://www.geeksforgeeks.org/strassens-matrix-multiplicatio... , see also https://youtube.com/watch?v=ORrM-aSNZUs https://youtube.com/watch?v=ORrM-aSNZUs
  - 6y ago

beagle3 6y ago

In the big-Oh algorithmic complexity sense; in a loose sense, for any pair of implementations (radix sort, kr sort) there exists a word size w and a list size n such that If either w or n increases, the time for radix sort would increase more quickly than for Kr sort - and this, eventually kr would be faster and keep getting faster. (Assuming that the hash can indeed yield average O(1) access, which is probabilistically but not deterministically true) That said, word size w is, in almost all integer dieting problems, bounded by 128 (by 64 or even 32 with high probability) which makes it acceptable to regard as “constant” in which case both sorts are essentially O(n) and it all depends on specific implementations (with radix sort likely significantly faster in practice)

adrianN 6y ago
Big-O as commonly used in the CS literature sometimes doesn't translate to Big-O on actual computers. For example virtual memory translation can add a log term where you wouldn't expect it: https://pdfs.semanticscholar.org/1e90/c55362cf7793dc0b2521f61752f2d0135e12.pdf https://pdfs.semanticscholar.org/1e90/c55362cf7793dc0b2521f6...
- jnxx 6y ago
  Yeah. I am wondering since a while whether well-known algorithms like the binary heap are still efficient on modern architectures, because their random memory access patterns.
  - lorenzhs 6y ago
    For priority queues, which implementation is optimal depends a lot on your workload (do you need addressability, i.e., a decreaseKey operation? What is the typical ratio of insertions to deletions? Are your keys integers?). I found some slide decks that are mostly in English with some German in between that might go some way to answering your question: [1] https://algo2.iti.kit.edu/sanders/courses/algen20/vorlesung.pdf https://algo2.iti.kit.edu/sanders/courses/algen20/vorlesung.... slide 180-207, there are some up-to-date measurements on slide 204 [2] https://nms.kcl.ac.uk/stefan.edelkamp/lectures/ae/slide/AE-AllgemeineVorrangwarteschlangen.pdf https://nms.kcl.ac.uk/stefan.edelkamp/lectures/ae/slide/AE-A... There are also parallel priority queues which might be useful depending on your problem, especially if it can be reformulated to operate on batches ("give me the 20 smallest items", "insert these 50 items").