ScratchQuickSort: a faster version of QuickSort

07/26/2023, 8:20 PM — 8:30 PM UTC
32-141

Abstract:

ScratchQuickSort is a novel variation on QuickSort that is typically faster, always stable, and now Julia's default sorting algorithm for generic data.

Description:

By leveraging a scratch space, ScratchQuickSort utilizes a faster partitioning strategy which emits simpler cpu instructions than QuickSort. Specifically the order of comparisons and memory reads is independent of the results of those comparisons allowing better ILP and faster iteration. Due to Julia's integrated sorting pipeline, the scratch space used by ScratchQuickSort is reused throughout the sorting pipeline and is rarely a performance bottleneck.

Nevertheless, ScratchQuickSort is not always faster than ScratchQuickSort and this talk will briefly explain how to avoid those limitations when they do occur

Should time allow, this talk may also describe how ScratchQuickSort is robust to invalid user orderings that cause ScratchQuickSort to segfault and how it ensures stability with negligible performance overhead.

ScratchQuickSort was first published (as far as I can tell) when it was introduced to the Julia programming language in https://github.com/JuliaLang/julia/pull/45222

Platinum sponsors

JuliaHub

Gold sponsors

ASML

Silver sponsors

Pumas AIQuEra Computing Inc.Relational AIJeffrey Sarnoff

Bronze sponsors

Jolin.ioBeacon Biosignals

Academic partners

NAWA

Local partners

Postmates

Fiscal Sponsor

NumFOCUS