4 ms·

Vectorized and performance-portable Quicksort (2022)

171 points by mococa 10d ago

brrrrrm 10d ago
only sorts numbers? wouldn't radix be much better?
deleted 10d ago
[deleted]
glouwbug 10d ago
Very nice. Let's see Paul Allen's quicksort
moralestapia 10d ago
[flagged]
sciencesama 10d ago
this was made like 4 years back most of the current algorithms use this already !
kg 10d ago
(2022) If you're curious why you would want a vectorized way to sort lists of numbers, one use case is building histograms - it's much easier to build a histogram if you've sorted all your samples first
- mcdonje 10d ago
  >(2002) I wonder what apps have implemented this now that a few years have passed.
  - mcdonje 9d ago
    oops, 2022
  - janwas 9d ago
    VQSort users include numpy, XLA (for sparse tensors), ScaNN: https://sourcegraph.com/search?q=context:global+hwy/contrib/sort/+-repo:google/highway+-path:hwy/contrib/sort+-path:highway/hwy/+-file:CMakeLists.txt+-file:filelist+-path:g3doc/+-f:meson.build+-f:patch%24+-path:/hwy/&patternType=keyword&sm=0 https://sourcegraph.com/search?q=context:global+hwy/contrib/...
tucnak 10d ago
[flagged]
- sigbottle 10d ago
  Honestly part of me feels that way about way too many things in retrospect about my own life and interests.
- Flex247A 10d ago
  time to log off
  - trueno 10d ago
    i read that and thought the same. actual based idea its even inspired me to log off
deleted 10d ago
[deleted]
deleted 10d ago
[deleted]
minitech 10d ago
Actual title: “Vectorized and performance-portable Quicksort” (2022). Actual sense in which it’s first: > Happily, modern instruction sets (Arm SVE, RISC-V V, x86 AVX-512) include a special instruction suitable for partitioning. Given a separate input of yes/no values (whether an element is less than the pivot), this "compress-store" instruction stores to consecutive memory only the elements whose corresponding input is "yes". We can then logically negate the yes/no values and apply the instruction again to write the elements to the other partition. This strategy has been used in an AVX-512-specific Quicksort. But what about other instruction sets such as AVX2 that don't have compress-store? Previous work has shown how to emulate this instruction using permute instructions. > We build on these techniques to achieve the first vectorized Quicksort that is portable to six instruction sets across three architectures, and in fact outperforms prior architecture-specific sorts.
mixologic 10d ago
> Our implementation uses Highway's portable SIMD functions, so we do not have to re-implement about 3,000 lines of C++ for each platform. Would they do the same thing today or have an LLM re-implement those 3000 lines of c++ ?
- glouwbug 10d ago
  Guys, remember when language features allowed re-usability?
  - shadowgovt 10d ago
    Barely, and rarely for C++ specifically. I think software engineering in general is in a bit of a discoverability crisis. So many problems actually have solutions implemented... Somewhere. If you know about them. And are speaking the same vocabulary as the original implementer to realize the solution might be applicable to your problem. It's one of the reasons that jokes exist about microservice frameworks (https://www.youtube.com/watch?v=y8OnoxKotPQ https://www.youtube.com/watch?v=y8OnoxKotPQ) and how "We use Hadoop to store the output from our Kafka pipe, that's populated from our Traefik layer, all monitored with Grafana in front of Loki and Prometheus, of course" is a real sentence that has actual meaning and not a fever-dream. LLMs are actually pretty impressive at being able to pull together disparate information from various domains into one place.
    - glouwbug 8d ago
      I'm not sure I follow. C++ just added a SIMD library for this exact problem. And even then, SIMD-intrinsic-free C++ with the right data structures and some basic hardware understanding gets you mostly there in a hardware agnostic portable way.
      - shadowgovt 8d ago
        They've added a new library to a language and stdlib so crammed full of features that its specification exceeds the size of the King James Bible by wordcount. That's what I mean about "discoverability crisis." This post is how I learned about the existence of the SIMD library.
bee_rider 10d ago
Well, it came out a while ago, so maybe we can be a bit silly: There’s something sort of beautiful about mergesort and heapsort. Their names tell you what their main idea is, and how they work is immediately obvious. Quicksort, on the other hand, has nothing beautiful about it and is named after it’s one redeeming feature (that it is quick for a lot of cases).
- thesz 10d ago
  The beauties of quicksort are that it sorts in-place and that it is embarrassingly simple. The in-place property can be utilized to make it very close to cache-oblivious algorithm.
- teiferer 10d ago
  How is it less beautiful? Honest question, curious to hear about what that means to you.
  - drdexebtjl 10d ago
    To me it’s the fact that if you try to do it in real life (sorting a collection of objects in the real world), you just end up doing merge sort by accident. It feels like an optimization of merge sort for computers, rather than a different approach. This is also reflected in the way that it’s usually taught. Normally merge sort is presented first, and quick sort follows from observations about what would happen if you picked different partition points instead of dividing them in half, and how you can reduce the additional space requirements.
  - bee_rider 9d ago
    Just look at the little video on Wikipedia, it is an absolute mess of elements being thrown around. Chaos. Real answer: I tutored beginner programming students for a bit and I guess I just thought quicksort didn’t fit in very well. Mergesort is an elegant and straightforward example of recursion. Heapsort—you can make a priority queue and then if you plop a heap in there, that’s heapsort. I like the story. With quicksort, it isn’t that complicated or anything but it doesn’t feel like it embodies an idea in the way the other two do. And it is annoying that the real big-O cost of the popular sorting algorithm is n^2, and the bad case is really obvious. I guess there’s value to getting over the hump of “well heuristics are a thing and big-O doesn’t tell you everything” but I still don’t like it.
djsavvy 10d ago
Definitely needs (2022) in the title, I was a bit confused!
zX41ZdbW 10d ago
Strange to see it here, the article is quite old. Since pdqsort, vqsort, and glide sort, the current state-of-the-art are driftsort and ipnsort. I've integrated them into ClickHouse: https://github.com/ClickHouse/ClickHouse/pull/106650 https://github.com/ClickHouse/ClickHouse/pull/106650
rvz 10d ago
Just imagine when candidates will get asked by pre-revenue startups to implement a vectorized version of quick-sort in person in 10 mins, just for a SWE job which they do not use this themselves. Only the likes of MAG 7, and a couple of hedge-funds would ask to do it since this problem directly applies to them. But certainly not pre-revenue startups.
starcast2026 10d ago
I didn't like the 9 MB image file in the blog. It took me few seconds to fully render the image.
dang 10d ago
Discussed at the time: Vectorized and performance-portable Quicksort - https://news.ycombinator.com/item?id=31622548 https://news.ycombinator.com/item?id=31622548 - June 2022 (142 comments)
deleted 10d ago
[deleted]
Razengan 9d ago
Something I've wondered about sorting algorithms: Humans can visually spot the smallest and largest item from among 1000s of items, almost instantly (usually, depending on the variance) Could AI be used this way? Just splat a visual representation of each item on a virtual wall and have an AI "visually" pick them out?
- jryan49 9d ago
  I can't imagine inference on an image could be faster that just a sort.

171 points by mococa 10d ago

brrrrrm 10d ago

only sorts numbers? wouldn't radix be much better?

deleted 10d ago

[deleted]

glouwbug 10d ago

Very nice. Let's see Paul Allen's quicksort

moralestapia 10d ago

[flagged]

sciencesama 10d ago

this was made like 4 years back most of the current algorithms use this already !

kg 10d ago

(2022) If you're curious why you would want a vectorized way to sort lists of numbers, one use case is building histograms - it's much easier to build a histogram if you've sorted all your samples first

mcdonje 10d ago
>(2002) I wonder what apps have implemented this now that a few years have passed.
- mcdonje 9d ago
  oops, 2022
- janwas 9d ago
  VQSort users include numpy, XLA (for sparse tensors), ScaNN: https://sourcegraph.com/search?q=context:global+hwy/contrib/sort/+-repo:google/highway+-path:hwy/contrib/sort+-path:highway/hwy/+-file:CMakeLists.txt+-file:filelist+-path:g3doc/+-f:meson.build+-f:patch%24+-path:/hwy/&patternType=keyword&sm=0 https://sourcegraph.com/search?q=context:global+hwy/contrib/...

tucnak 10d ago

[flagged]

sigbottle 10d ago
Honestly part of me feels that way about way too many things in retrospect about my own life and interests.
Flex247A 10d ago
time to log off
- trueno 10d ago
  i read that and thought the same. actual based idea its even inspired me to log off

deleted 10d ago

[deleted]

deleted 10d ago

[deleted]

minitech 10d ago

Actual title: “Vectorized and performance-portable Quicksort” (2022). Actual sense in which it’s first: > Happily, modern instruction sets (Arm SVE, RISC-V V, x86 AVX-512) include a special instruction suitable for partitioning. Given a separate input of yes/no values (whether an element is less than the pivot), this "compress-store" instruction stores to consecutive memory only the elements whose corresponding input is "yes". We can then logically negate the yes/no values and apply the instruction again to write the elements to the other partition. This strategy has been used in an AVX-512-specific Quicksort. But what about other instruction sets such as AVX2 that don't have compress-store? Previous work has shown how to emulate this instruction using permute instructions. > We build on these techniques to achieve the first vectorized Quicksort that is portable to six instruction sets across three architectures, and in fact outperforms prior architecture-specific sorts.

mixologic 10d ago

> Our implementation uses Highway's portable SIMD functions, so we do not have to re-implement about 3,000 lines of C++ for each platform. Would they do the same thing today or have an LLM re-implement those 3000 lines of c++ ?

glouwbug 10d ago
Guys, remember when language features allowed re-usability?
- shadowgovt 10d ago
  Barely, and rarely for C++ specifically. I think software engineering in general is in a bit of a discoverability crisis. So many problems actually have solutions implemented... Somewhere. If you know about them. And are speaking the same vocabulary as the original implementer to realize the solution might be applicable to your problem. It's one of the reasons that jokes exist about microservice frameworks (https://www.youtube.com/watch?v=y8OnoxKotPQ https://www.youtube.com/watch?v=y8OnoxKotPQ) and how "We use Hadoop to store the output from our Kafka pipe, that's populated from our Traefik layer, all monitored with Grafana in front of Loki and Prometheus, of course" is a real sentence that has actual meaning and not a fever-dream. LLMs are actually pretty impressive at being able to pull together disparate information from various domains into one place.
  - glouwbug 8d ago
    I'm not sure I follow. C++ just added a SIMD library for this exact problem. And even then, SIMD-intrinsic-free C++ with the right data structures and some basic hardware understanding gets you mostly there in a hardware agnostic portable way.
    - shadowgovt 8d ago
      They've added a new library to a language and stdlib so crammed full of features that its specification exceeds the size of the King James Bible by wordcount. That's what I mean about "discoverability crisis." This post is how I learned about the existence of the SIMD library.

bee_rider 10d ago

Well, it came out a while ago, so maybe we can be a bit silly: There’s something sort of beautiful about mergesort and heapsort. Their names tell you what their main idea is, and how they work is immediately obvious. Quicksort, on the other hand, has nothing beautiful about it and is named after it’s one redeeming feature (that it is quick for a lot of cases).

thesz 10d ago
The beauties of quicksort are that it sorts in-place and that it is embarrassingly simple. The in-place property can be utilized to make it very close to cache-oblivious algorithm.
teiferer 10d ago
How is it less beautiful? Honest question, curious to hear about what that means to you.
- drdexebtjl 10d ago
  To me it’s the fact that if you try to do it in real life (sorting a collection of objects in the real world), you just end up doing merge sort by accident. It feels like an optimization of merge sort for computers, rather than a different approach. This is also reflected in the way that it’s usually taught. Normally merge sort is presented first, and quick sort follows from observations about what would happen if you picked different partition points instead of dividing them in half, and how you can reduce the additional space requirements.
- bee_rider 9d ago
  Just look at the little video on Wikipedia, it is an absolute mess of elements being thrown around. Chaos. Real answer: I tutored beginner programming students for a bit and I guess I just thought quicksort didn’t fit in very well. Mergesort is an elegant and straightforward example of recursion. Heapsort—you can make a priority queue and then if you plop a heap in there, that’s heapsort. I like the story. With quicksort, it isn’t that complicated or anything but it doesn’t feel like it embodies an idea in the way the other two do. And it is annoying that the real big-O cost of the popular sorting algorithm is n^2, and the bad case is really obvious. I guess there’s value to getting over the hump of “well heuristics are a thing and big-O doesn’t tell you everything” but I still don’t like it.

djsavvy 10d ago

Definitely needs (2022) in the title, I was a bit confused!

zX41ZdbW 10d ago

Strange to see it here, the article is quite old. Since pdqsort, vqsort, and glide sort, the current state-of-the-art are driftsort and ipnsort. I've integrated them into ClickHouse: https://github.com/ClickHouse/ClickHouse/pull/106650 https://github.com/ClickHouse/ClickHouse/pull/106650

rvz 10d ago

Just imagine when candidates will get asked by pre-revenue startups to implement a vectorized version of quick-sort in person in 10 mins, just for a SWE job which they do not use this themselves. Only the likes of MAG 7, and a couple of hedge-funds would ask to do it since this problem directly applies to them. But certainly not pre-revenue startups.

starcast2026 10d ago

I didn't like the 9 MB image file in the blog. It took me few seconds to fully render the image.

dang 10d ago

Discussed at the time: Vectorized and performance-portable Quicksort - https://news.ycombinator.com/item?id=31622548 https://news.ycombinator.com/item?id=31622548 - June 2022 (142 comments)

deleted 10d ago

[deleted]

Razengan 9d ago

Something I've wondered about sorting algorithms: Humans can visually spot the smallest and largest item from among 1000s of items, almost instantly (usually, depending on the variance) Could AI be used this way? Just splat a visual representation of each item on a virtual wall and have an AI "visually" pick them out?

jryan49 9d ago
I can't imagine inference on an image could be faster that just a sort.