Branchless Quicksort faster than std:sort and pdqsort with C and C++ API

▲ Branchless Quicksort faster than std:sort and pdqsort with C and C++ API(tiki.li)

47 points by birdculture 2 days ago | 7 comments

▲ orlp an hour ago | parent | next [-]

Since pdqsort (an older project of mine) was mentioned, I felt it wouldn't be entirely inappropriate to mention that I've since then collaborated with Lukas Bergdoll to provide two high-quality sort implementations for the Rust standard library, ipnsort (unstable) and driftsort (stable).

So if you use Rust, you get these by simply calling [T]::sort(_unstable). Great performance out of the box :)

On my machine (Apple M2), using the benchmarks from the repository on Apple clang 17 and Rust 1.98 nightly:

    Sorting 50 million doubles:
    ipnsort             0.79s
    blqs                0.90s
    driftsort           1.13s   (stable)
    std::sort           1.22s
    std::stable_sort    4.64s   (stable)

    Sorting 50 million (i32, i32) structs:
    ipnsort             0.82s
    blqs                0.89s
    driftsort           1.07s   (stable)
    std::sort           3.09s
    std::stable_sort    3.15s   (stable)

And now for a cool party trick, let's repeat the 50 million doubles experiment again, but have the first 90% already sorted, last 10% random:

    driftsort           0.29s   (stable)
    ipnsort             0.81s
    std::sort           1.15s
    std::stable_sort    1.63s   (stable)
    blqs                1.89s

▲ mgaunard 2 hours ago | parent | prev | next [-]

Aren't there several bitonic sort network implementations that are vectorized, Intel's in particular?

Why not compare against that?

	▲	mswphd an hour ago \| parent \| next [-]
		Funny: you can cf "sorting network", and see they use them within their own design even.
	▲	jeffbee an hour ago \| parent \| prev [-]
		Great question. It would also be fair to ask how this behaves with non-random inputs. The benchmarks in the repo only use random values.

▲ davidkwast 2 hours ago | parent | prev [-]

It is so simple that I had to look very slowly to understand. Nicely done.

▲

NuclearPM an hour ago | parent [-]

If it wasn’t simple you could look fast and understand?

	▲	hyperhello 25 minutes ago \| parent [-]
		If it wasn't simple, there would be more lines of code to implement the same idea. As it is, he might have had to spend an hour understanding one line to understand that idea (1 line/hr slow), as opposed to spending an hour reading a hundred lines of code (100 line/hr fast) for the same result.