Rendered at 20:12:39 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
minitech 1 hours 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.
bee_rider 54 minutes 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).
rodrigosetti 19 minutes ago [-]
Maybe if Hoare had called it Partitionsort in 1960, the name wouldn’t have been memorable enough to catch on and become so popular.
thesz 21 minutes 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 21 minutes ago [-]
How is it less beautiful?
Honest question, curious to hear about what that means to you.
zX41ZdbW 48 minutes 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.
Definitely needs (2022) in the title, I was a bit confused!
mixologic 56 minutes 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 47 minutes ago [-]
Guys, remember when language features allowed re-usability?
atiedebee 52 minutes ago [-]
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.
kg 1 hours 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 1 hours ago [-]
>(2002)
I wonder what apps have implemented this now that a few years have passed.
sciencesama 40 minutes ago [-]
this was made like 4 years back most of the current algorithms use this already !
brrrrrm 43 minutes ago [-]
only sorts numbers? wouldn't radix be much better?
53 minutes ago [-]
rvz 40 minutes 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.
glouwbug 1 hours ago [-]
Very nice. Let's see Paul Allen's quicksort
moralestapia 1 hours ago [-]
[flagged]
tucnak 1 hours ago [-]
[flagged]
Flex247A 1 hours ago [-]
time to log off
trueno 58 minutes ago [-]
i read that and thought the same. actual based idea its even inspired me to log off
sigbottle 1 hours ago [-]
Honestly part of me feels that way about way too many things in retrospect about my own life and interests.
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.
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).
The in-place property can be utilized to make it very close to cache-oblivious algorithm.
Honest question, curious to hear about what that means to you.
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
Would they do the same thing today or have an LLM re-implement those 3000 lines of c++ ?
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
I wonder what apps have implemented this now that a few years have passed.
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.