Thread

Vectorized and performance-portable Quicksort (2022)

171 points · 31 comments · mococa

Loading the complete thread in the background. This saved snapshot is available now. Refresh

glouwbug · 1789584764 · focus · HN ↗
Very nice. Let's see Paul Allen's quicksort
moralestapia · 1789584774 · focus · HN ↗
[dead]
kg · 1789584907 · focus · HN ↗
(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
1. mcdonje · 1789585471 · focus · HN ↗
  >(2002)
  I wonder what apps have implemented this now that a few years have passed.
  1. mcdonje · 1789604105 · focus · HN ↗
    oops, 2022
  2. janwas · 1789659081 · focus · HN ↗
    VQSort users include numpy, XLA (for sparse tensors), ScaNN:
    <a href="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" rel="nofollow">https://sourcegraph.com/search?q=context:global+hwy/contrib/...
tucnak · 1789584928 · focus · HN ↗
Who would've guessed? SIMD is so boring.
1. sigbottle · 1789585342 · focus · HN ↗
  Honestly part of me feels that way about way too many things in retrospect about my own life and interests.
2. Flex247A · 1789585440 · focus · HN ↗
  time to log off
  1. trueno · 1789586087 · focus · HN ↗
    i read that and thought the same. actual based idea its even inspired me to log off
cs702 · 1789585314 · focus · HN ↗
Open-source. Immediately usable. It will find its way to every place in which it can be used. Very nice! A big THANK YOU to the developers.
bananaflag · 1789585380 · focus · HN ↗
My first thought was "but doesn't quicksort already work with vectors?"
minitech · 1789585888 · focus · HN ↗
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 · 1789586174 · focus · HN ↗
> 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++ ?
1. atiedebee · 1789586456 · focus · HN ↗
  Id say that it is a lot more likely for the in-house, at least half a decade old library to be correct and performant than 3000 lines of an LLMs mediocre regurgitation of that code.
2. glouwbug · 1789586731 · focus · HN ↗
  Guys, remember when language features allowed re-usability?
  1. shadowgovt · 1789589585 · focus · HN ↗
    [delayed]
    glouwbug · 1789751176 · focus · HN ↗
    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 · 1789753087 · focus · HN ↗
    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.
3. janwas · 1789635987 · focus · HN ↗
  (Co-)author here :)
  I'd absolutely still use Highway, and do. My experience is that even two separate implementations diverge over time and I'd have low confidence in bringing the same updates and improvements to all, even with LLM assistance.
  Our programming model is 1) an agent+human to generate the algorithmic approach, 2) a C++ library (Highway) to translate to intrinsics, while filling in gaps + allowing customization, 3) a compiler to generate the actual code with some optimizations.
  Asking the compiler to do #1 is a pipe dream: compiler friends tell me they are not going to devise new shuffles/data layouts (like what VQSort does). Conflating #2 and #3 means a custom compiler/IR which has high engineering costs (ABI boundaries, hard to debug/profile/sanitize). And doing #3 at runtime (JIT), or moving fusions into #3 (MLIR), vastly complicates the compiler. We can still get runtime adaptability thanks to Highway's multi-target support. Fusion has been much easier to implement manually for LLMs than to construct a general fusion infrastructure. Templates hide most data type differences and we see 2-5x speedup vs llama.cpp for 128k prefill+batch decode on Zen5.
  Instead of requiring a compiler to do heroic transforms at runtime, and get it right every time, we can do all kinds of agentic exploration, then verify the result/approach, check in the source code, then we 'just' have a C++ compiler afterwards. And if/when something breaks, it's easy to update centrally, in code we can modify directly, rather than indirectly via updating a compiler.
bee_rider · 1789586334 · focus · HN ↗
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).
1. thesz · 1789588288 · focus · HN ↗
  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.
2. teiferer · 1789588304 · focus · HN ↗
  How is it less beautiful?
  Honest question, curious to hear about what that means to you.
  1. drdexebtjl · 1789592919 · focus · HN ↗
    To me it’s the fact that if you try to do it in real life (i.e. sorting a collection of real items), you just end up doing merge sort.
    So it feels like an optimization of merge sort for computers, rather than a different approach.
  2. bee_rider · 1789600983 · focus · HN ↗
    Just look at the little video on Wikipedia, it is an absolute mess of elements being thrown around. Chaos.
    Real answer: I worked with an intro to programming class as a grad student 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.
3. rodrigosetti · 1789588406 · focus · HN ↗
  Maybe if Hoare had called it Partitionsort in 1960, the name wouldn’t have been memorable enough to catch on and become so popular.
DennisL123 · 1789586371 · focus · HN ↗
Awesome, Jan!
djsavvy · 1789586405 · focus · HN ↗
Definitely needs (2022) in the title, I was a bit confused!
zX41ZdbW · 1789586706 · focus · HN ↗
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: <a href="https://github.com/ClickHouse/ClickHouse/pull/106650" rel="nofollow">https://github.com/ClickHouse/ClickHouse/pull/106650
brrrrrm · 1789586988 · focus · HN ↗
only sorts numbers? wouldn't radix be much better?
rvz · 1789587163 · focus · HN ↗
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.
sciencesama · 1789587179 · focus · HN ↗
this was made like 4 years back most of the current algorithms use this already !
starcast2026 · 1789590275 · focus · HN ↗
I didn't like the 9 MB image file in the blog. It took me few seconds to fully render the image.
dang · 1789592817 · focus · HN ↗
Discussed at the time:
Vectorized and performance-portable Quicksort - <a href="https://news.ycombinator.com/item?id=31622548">https://news.ycombinator.com/item?id=31622548 - June 2022 (142 comments)
Razengan · 1789592847 · focus · HN ↗
Just wondering: Humans can visually spot the smallest and largest items 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?
Razengan · 1789595454 · focus · HN ↗
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?
1. jryan49 · 1789605102 · focus · HN ↗
  I can't imagine inference on an image could be faster that just a sort.

Open on Hacker News to reply ↗

Unofficial Hacker News client; not affiliated with Y Combinator.