{“payload”:{“allShortcutsEnabled”:false,”fileTree”:{“writeup/sort_safety”:{“items”:[{“name”:”assets”,”path”:”writeup/sort_safety/assets”,”contentType”:”directory”},{“name”:”text.md”,”path”:”writeup/sort_safety/text.md”,”contentType”:”file”}],”totalCount”:2},”writeup”:{“items”:[{“name”:”glidesort_perf_analysis”,”path”:”writeup/glidesort_perf_analysis”,”contentType”:”directory”},{“name”:”intel_avx512″,”path”:”writeup/intel_avx512″,”contentType”:”directory”},{“name”:”sort_safety”,”path”:”writeup/sort_safety”,”contentType”:”directory”}],”totalCount”:3},””:{“items”:[{“name”:”benches”,”path”:”benches”,”contentType”:”directory”},{“name”:”fuzz-afl”,”path”:”fuzz-afl”,”contentType”:”directory”},{“name”:”fuzz”,”path”:”fuzz”,”contentType”:”directory”},{“name”:”ipnsort”,”path”:”ipnsort”,”contentType”:”directory”},{“name”:”results”,”path”:”results”,”contentType”:”directory”},{“name”:”sort_test_tools”,”path”:”sort_test_tools”,”contentType”:”directory”},{“name”:”src”,”path”:”src”,”contentType”:”directory”},{“name”:”tests”,”path”:”tests”,”contentType”:”directory”},{“name”:”util”,”path”:”util”,”contentType”:”directory”},{“name”:”writeup”,”path”:”writeup”,”contentType”:”directory”},{“name”:”.editorconfig”,”path”:”.editorconfig”,”contentType”:”file”},{“name”:”.gitignore”,”path”:”.gitignore”,”contentType”:”file”},{“name”:”CODE_OF_CONDUCT.md”,”path”:”CODE_OF_CONDUCT.md”,”contentType”:”file”},{“name”:”Cargo.lock”,”path”:”Cargo.lock”,”contentType”:”file”},{“name”:”Cargo.toml”,”path”:”Cargo.toml”,”contentType”:”file”},{“name”:”LICENSE”,”path”:”LICENSE”,”contentType”:”file”},{“name”:”README.md”,”path”:”README.md”,”contentType”:”file”},{“name”:”build.rs”,”path”:”build.rs”,”contentType”:”file”},{“name”:”ideas.txt”,”path”:”ideas.txt”,”contentType”:”file”},{“name”:”notex.txt”,”path”:”notex.txt”,”contentType”:”file”}],”totalCount”:20}},”fileTreeProcessingTime”:8.799688,”foldersToFetch”:[],”reducedMotionEnabled”:null,”repo”:{“id”:526908111,”defaultBranch”:”main”,”name”:”sort-research-rs”,”ownerLogin”:”Voultapher”,”currentUserCanPush”:false,”isFork”:false,”isEmpty”:false,”createdAt”:”2022-08-20T11:33:31.000Z”,”ownerAvatar”:”https://avatars.githubusercontent.com/u/6864584?v=4″,”public”:true,”private”:false,”isOrgOwned”:false},”symbolsExpanded”:false,”treeExpanded”:true,”refInfo”:{“name”:”main”,”listCacheKey”:”v0:1694870203.0″,”canEdit”:false,”refType”:”branch”,”currentOid”:”bf90e294bd84c7cfe746f1bd718ff133bcb89389″},”path”:”writeup/sort_safety/text.md”,”currentUser”:null,”blob”:{“rawLines”:null,”stylingDirectives”:null,”csv”:null,”csvError”:null,”dependabotInfo”:{“showConfigurationBanner”:false,”configFilePath”:null,”networkDependabotPath”:”/Voultapher/sort-research-rs/network/updates”,”dismissConfigurationNoticePath”:”/settings/dismiss-notice/dependabot_configuration_notice”,”configurationNoticeDismissed”:null,”repoAlertsPath”:”/Voultapher/sort-research-rs/security/dependabot”,”repoSecurityAndAnalysisPath”:”/Voultapher/sort-research-rs/settings/security_analysis”,”repoOwnerIsOrg”:false,”currentUserCanAdminRepo”:false},”displayName”:”text.md”,”displayUrl”:”https://github.com/Voultapher/sort-research-rs/blob/main/writeup/sort_safety/text.md?raw=true”,”headerInfo”:{“blobSize”:”28.1 KB”,”deleteInfo”:{“deleteTooltip”:”You must be signed in to make or propose changes”},”editInfo”:{“editTooltip”:”You must be signed in to make or propose changes”},”ghDesktopPath”:”https://desktop.github.com”,”gitLfsPath”:null,”onBranch”:true,”shortPath”:”e409677″,”siteNavLoginPath”:”/login?return_to=https%3A%2F%2Fgithub.com%2FVoultapher%2Fsort-research-rs%2Fblob%2Fmain%2Fwriteup%2Fsort_safety%2Ftext.md”,”isCSV”:false,”isRichtext”:true,”toc”:[{“level”:1,”text”:”Safety vs Performance. A case study of C, C++ and Rust sort implementations.”,”anchor”:”safety-vs-performance-a-case-study-of-c-c-and-rust-sort-implementations”,”htmlText”:”Safety vs Performance. A case study of C, C++ and Rust sort implementations.”},{“level”:2,”text”:”Introduction”,”anchor”:”introduction”,”htmlText”:”Introduction”},{“level”:2,”text”:”Safe-to-use abstractions”,”anchor”:”safe-to-use-abstractions”,”htmlText”:”Safe-to-use abstractions”},{“level”:3,”text”:”Ord safety”,”anchor”:”ord-safety”,”htmlText”:”Ord safety”},{“level”:3,”text”:”Exception safety”,”anchor”:”exception-safety”,”htmlText”:”Exception safety”},{“level”:3,”text”:”Observation safety”,”anchor”:”observation-safety”,”htmlText”:”Observation safety”},{“level”:2,”text”:”Results”,”anchor”:”results”,”htmlText”:”Results”},{“level”:3,”text”:”Tested sort implementations”,”anchor”:”tested-sort-implementations”,”htmlText”:”Tested sort implementations”},{“level”:4,”text”:”Stable”,”anchor”:”stable”,”htmlText”:”Stable”},{“level”:4,”text”:”Unstable”,”anchor”:”unstable”,”htmlText”:”Unstable”},{“level”:3,”text”:”Property analysis”,”anchor”:”property-analysis”,”htmlText”:”Property analysis”},{“level”:3,”text”:”Observations”,”anchor”:”observations”,”htmlText”:”Observations”},{“level”:2,”text”:”Performance”,”anchor”:”performance”,”htmlText”:”Performance”},{“level”:3,”text”:”Benchmark setup”,”anchor”:”benchmark-setup”,”htmlText”:”Benchmark setup”},{“level”:3,”text”:”Results”,”anchor”:”results-1″,”htmlText”:”Results”},{“level”:4,”text”:”Stable”,”anchor”:”stable-1″,”htmlText”:”Stable”},{“level”:4,”text”:”Unstable”,”anchor”:”unstable-1″,”htmlText”:”Unstable”},{“level”:2,”text”:”libc++’s (libcxx) new std::sort”,”anchor”:”libcs-libcxx-new-stdsort”,”htmlText”:”libc++’s (libcxx) new std::sort”},{“level”:2,”text”:”Author’s conclusion and opinion”,”anchor”:”authors-conclusion-and-opinion”,”htmlText”:”Author’s conclusion and opinion”},{“level”:2,”text”:”Thanks”,”anchor”:”thanks”,”htmlText”:”Thanks”}],”lineInfo”:{“truncatedLoc”:”307″,”truncatedSloc”:”222″},”mode”:”file”},”image”:false,”isCodeownersFile”:null,”isPlain”:false,”isValidLegacyIssueTemplate”:false,”issueTemplateHelpUrl”:”https://docs.github.com/articles/about-issue-and-pull-request-templates”,”issueTemplate”:null,”discussionTemplate”:null,”language”:”Markdown”,”languageID”:222,”large”:false,”loggedIn”:false,”newDiscussionPath”:”/Voultapher/sort-research-rs/discussions/new”,”newIssuePath”:”/Voultapher/sort-research-rs/issues/new”,”planSupportInfo”:{“repoIsFork”:null,”repoOwnedByCurrentUser”:null,”requestFullPath”:”/Voultapher/sort-research-rs/blob/main/writeup/sort_safety/text.md”,”showFreeOrgGatedFeatureMessage”:null,”showPlanSupportBanner”:null,”upgradeDataAttributes”:null,”upgradePath”:null},”publishBannersInfo”:{“dismissActionNoticePath”:”/settings/dismiss-notice/publish_action_from_dockerfile”,”dismissStackNoticePath”:”/settings/dismiss-notice/publish_stack_from_file”,”releasePath”:”/Voultapher/sort-research-rs/releases/new?marketplace=true”,”showPublishActionBanner”:false,”showPublishStackBanner”:false},”rawBlobUrl”:”https://github.com/Voultapher/sort-research-rs/raw/main/writeup/sort_safety/text.md”,”renderImageOrRaw”:false,”richText”:”
Author: Lukas Bergdoll @Voultapher
nDate: 05-10-2023 (DD-MM-YYYY)
n
This is an analysis of sort implementations and their ability, or lack thereof, to avoid undefined behavior (UB) under various usage scenarios, and whether this affects their performance.
n
TL;DR: The combination of complex generic implementations striving for performance with arbitrary logic in user-defined comparison functions, makes generic high-performance sort implementations particularly difficult to implement in a way that avoids UB under every usage scenario. Even a sort implementation using only memory-safe abstractions is no guarantee of UB free adjacent logic. Overall no correlation between performance and safety could be found, nor whether safe or unsafe internal abstractions are used. However a strong correlation between being implemented for C or C++ users and a lack of safety presents itself.
n
n
Bias disclaimer. The author of this analysis is the author of ipnsort.
n
Introduction
n
Implementing a sort operation with the help of computers goes back to the early 1950s. The problem statement is deceptively simple. Take a list of elements and use a comparison function that implements a strict weak ordering to swap elements until it’s sorted. Now, 70 years later new and more resource-efficient ways to implement this operation are still being discovered. It’s an active field of study in science, BlockQuicksort 2016, ips4o 2017, pdqsort 2021, Multiway Powersort 2022, and many more. There are various directions science is exploring. Efficient sort implementations running single threaded on modern superscalar, out-of-order and speculative CPUs. Efficient implementations running on multiple such threads. Implementations running on massively parallel in-order GPUs. Exploration of better best-case, average-case and worst-case runtime. Exploiting existing patterns in the input data. Exploration of different characteristics, stable/unstable in-place/allocating and more. This analysis focuses on a lesser known and talked about aspect. How do implementations deal with a user-defined comparison function that implements arbitrary logic, may not implement a strict weak ordering, may leave the function without returning and can modify values as they are being compared.
n
The words sort implementation and sort algorithm, are explicitly not used interchangeably. Practically all modern implementations are hybrids, using multiple sort algorithms.
n
Safe-to-use abstractions
n
The Rust language has a concept of safe and unsafe interfaces. A safe interface is sound if the implementation avoids UB no matter how it is used, a property that composes. An implementation composed entirely of the usage of other safe interfaces is considered safe. However, in the presence of other adjacent unsafe code, further considerations arise. This puts the burden on the interface designers and implementers, instead of the users. The C++ standard has a similar concept, called wide and narrow contracts, and while conceptually it’s possible to design interfaces in C++ whose usage cannot lead to UB, common abstraction including standard library types like std::vector or algorithms like std::sort do not make such promises.
n
With the exception of rust_crumsort_rs_unstable, all Rust sort implementations considered in this analysis use unsafe abstractions in their implementations.
n
Ord safety
n
What happens if the user-defined type or comparison function does not implement a strict weak ordering? The C++ standard library sort interface makes it trivial to trigger this case:
n
C++:
n
sort(data.begin(), data.end(), [](const auto& a, const auto& b) {n return a <= b; // correct would be a < b.n});
n
The Rust standard library sort interface avoids this problem in many cases, by requiring the user-defined comparison function to return the Ordering type instead of a bool, but it is still possible:
n
Rust:
n
data.sort_by(|a, b| {n if a == b {n return Ordering::Less;n }nn a.cmp(b)n});
n
The question what happens if the comparison function does not implement a strict weak ordering can be answered by constructing experiments and measuring the outcomes for various implementations. The question what should happen is trickier to answer. Adjacent is the question what is and isn’t allowed to happen in order to avoid UB in every scenario.
n
Say the user wants to sort this input of integers:
nn
By mistake a comparison function is provided which does not implement the required strict weak ordering. What are possible outcomes?
n
A: [2, 3, 9, 3, 1, 6]nB: [3, 2, 1, 3, 9, 6] + exception/panicnC: