mirror of
https://github.com/hanzoai/datastore.git
synced 2026-09-26 13:55:07 +00:00
Alexey MilovidovandClaude Opus 4.8
5a59ed8c49
Port the Rust standard library's current sort implementations to C++ and use them in `base/base/sort.h`: - ipnsort (by Lukas Bergdoll & Orson Peters) backs `::sort`, replacing `pdqsort`. It is pattern-defeating quicksort with a glidesort pivot, a sorting-network small-sort and a heapsort fallback, and detects already-sorted and reverse-sorted runs (handling them in O(n)). The port runs the full algorithm for trivially-copyable types and a move-based path otherwise. Its partition evaluates the comparator over a block in an ILP-friendly pre-pass before the serial rearrangement, which keeps throughput high for expensive (indirect / cache-missing) comparators - the dominant ClickHouse pattern. - driftsort (by Orson Peters & Lukas Bergdoll) backs a new `::stableSort`, replacing `std::stable_sort` call sites. It is a powersort merge tree over detected runs with a stable scratch quicksort, several times faster than `std::stable_sort`. It allocates up to n/2 extra memory. Both are vendored as header-only contribs (dual MIT / Apache-2.0), like `contrib/pdqsort`. They need raw pointers, so contiguous iterators are converted with `std::to_address`; non-contiguous iterators keep `pdqsort` / `std::stable_sort`. `trySort`, `nth_element` and `partial_sort` are unchanged. Validated against `std::sort` / `std::stable_sort` over thousands of randomized cases under AddressSanitizer (sizes, duplicate densities, patterns, and trivially-copyable, non-trivially-copyable and non-default-constructible element types) with zero mismatches; driftsort verified stable. Supersedes the blqsort approach in #106618: the CI performance comparison there showed blqsort regressing `ORDER BY toDecimal128(...) DESC` ~4.9x (a reverse-sorted worst case); ipnsort keeps the string-sort improvements without that regression. Related: https://github.com/ClickHouse/ClickHouse/pull/106618 Co-Authored-By: Claude Opus 4.8 (1M context) <[email protected]>
191 B
191 B
C++ port of ipnsort (unstable sort) by Lukas Bergdoll & Orson Peters. Upstream (Rust): https://github.com/Voultapher/sort-research-rs (ipnsort/). Dual-licensed MIT / Apache-2.0. See LICENSE.