lib: add statsort(), a distribution/bucket sort
PATCH 1/1 lib: add statsort(), a distribution/bucket sort
Adds statsort(), a bucket/distribution sort for arrays keyed by a signed 64-bit value. Recursively distributes elements into sqrt(n) buckets based on linear interpolation of the key over the current range, narrowing the range at each level. Falls back to sort_r() (lib/sort.c) for small ranges, skewed/degenerate key distributions, and allocation failure, so worst-case behavior is never worse than sort_r() plus O(n) bucketing overhead.
Benchmarked against sort() and glibc qsort() on uniform and Gaussian-distributed long arrays:
❯ ./run.sh
Compiling...
Running...
Running edge-case checks...
Edge cases OK.
== n = 10000 distribution = uniform ==
statsort_longs best of 5: 0.0004 s ( 37.04 ns/elem) sort (kernel) best of 5: 0.0008 s ( 78.48 ns/elem) qsort (libc) best of 5: 0.0007 s ( 74.27 ns/elem)
== n = 10000 distribution = gaussian ==
statsort_longs best of 5: 0.0004 s ( 39.69 ns/elem) sort (kernel) best of 5: 0.0008 s ( 77.78 ns/elem) qsort (libc) best of 5: 0.0007 s ( 74.42 ns/elem)
== n = 10000 distribution = duplicates ==
statsort_longs best of 5: 0.0008 s ( 78.19 ns/elem) sort (kernel) best of 5: 0.0007 s ( 74.88 ns/elem) qsort (libc) best of 5: 0.0005 s ( 47.52 ns/elem)
== n = 10000 distribution = small_range ==
statsort_longs best of 5: 0.0006 s ( 55.06 ns/elem) sort (kernel) best of 5: 0.0008 s ( 77.46 ns/elem) qsort (libc) best of 5: 0.0006 s ( 61.69 ns/elem)
== n = 10000 distribution = sorted ==
statsort_longs best of 5: 0.0002 s ( 24.67 ns/elem) sort (kernel) best of 5: 0.0007 s ( 73.20 ns/elem) qsort (libc) best of 5: 0.0002 s ( 17.29 ns/elem)
== n = 10000 distribution = reversed ==
statsort_longs best of 5: 0.0004 s ( 39.31 ns/elem) sort (kernel) best of 5: 0.0007 s ( 73.46 ns/elem) qsort (libc) best of 5: 0.0002 s ( 22.86 ns/elem)
== n = 10000 distribution = constant ==
statsort_longs best of 5: 0.0000 s ( 1.38 ns/elem) sort (kernel) best of 5: 0.0006 s ( 62.94 ns/elem) qsort (libc) best of 5: 0.0002 s ( 17.30 ns/elem)
== n = 100000 distribution = uniform ==
statsort_longs best of 5: 0.0042 s ( 41.62 ns/elem) sort (kernel) best of 5: 0.0112 s ( 111.84 ns/elem) qsort (libc) best of 5: 0.0093 s ( 93.15 ns/elem)
== n = 100000 distribution = gaussian ==
statsort_longs best of 5: 0.0042 s ( 41.71 ns/elem) sort (kernel) best of 5: 0.0114 s ( 113.96 ns/elem) qsort (libc) best of 5: 0.0094 s ( 93.86 ns/elem)
== n = 100000 distribution = duplicates ==
statsort_longs best of 5: 0.0106 s ( 105.76 ns/elem) sort (kernel) best of 5: 0.0097 s ( 96.88 ns/elem) qsort (libc) best of 5: 0.0055 s ( 54.64 ns/elem)
== n = 100000 distribution = small_range ==
statsort_longs best of 5: 0.0080 s ( 80.38 ns/elem) sort (kernel) best of 5: 0.0101 s ( 100.98 ns/elem) qsort (libc) best of 5: 0.0070 s ( 70.33 ns/elem)
== n = 100000 distribution = sorted ==
statsort_longs best of 5: 0.0033 s ( 33.44 ns/elem) sort (kernel) best of 5: 0.0095 s ( 94.56 ns/elem) qsort (libc) best of 5: 0.0020 s ( 20.41 ns/elem)
== n = 100000 distribution = reversed ==
statsort_longs best of 5: 0.0040 s ( 39.83 ns/elem) sort (kernel) best of 5: 0.0094 s ( 93.55 ns/elem) qsort (libc) best of 5: 0.0027 s ( 27.24 ns/elem)
== n = 100000 distribution = constant ==
statsort_longs best of 5: 0.0001 s ( 1.39 ns/elem) sort (kernel) best of 5: 0.0084 s ( 84.11 ns/elem) qsort (libc) best of 5: 0.0020 s ( 20.42 ns/elem)
== n = 100000000 distribution = uniform ==
statsort_longs best of 1: 9.0722 s ( 90.72 ns/elem) sort (kernel) best of 1: 171.2293 s (1712.29 ns/elem) qsort (libc) best of 1: 18.4959 s ( 184.96 ns/elem)
== n = 100000000 distribution = gaussian ==
statsort_longs best of 1: 8.6535 s ( 86.54 ns/elem) sort (kernel) best of 1: 170.0339 s (1700.34 ns/elem) qsort (libc) best of 1: 17.1339 s ( 171.34 ns/elem)
== n = 100000000 distribution = duplicates ==
statsort_longs best of 1: 23.0730 s ( 230.73 ns/elem) sort (kernel) best of 1: 17.0882 s ( 170.88 ns/elem) qsort (libc) best of 1: 9.6171 s ( 96.17 ns/elem)
== n = 100000000 distribution = small_range ==
statsort_longs best of 1: 19.4232 s ( 194.23 ns/elem) sort (kernel) best of 1: 31.0023 s ( 310.02 ns/elem) qsort (libc) best of 1: 11.5071 s ( 115.07 ns/elem)
== n = 100000000 distribution = sorted ==
statsort_longs best of 1: 3.9397 s ( 39.40 ns/elem) sort (kernel) best of 1: 16.4800 s ( 164.80 ns/elem) qsort (libc) best of 1: 3.7129 s ( 37.13 ns/elem)
== n = 100000000 distribution = reversed ==
statsort_longs best of 1: 5.9803 s ( 59.80 ns/elem) sort (kernel) best of 1: 19.3678 s ( 193.68 ns/elem) qsort (libc) best of 1: 5.7287 s ( 57.29 ns/elem)
== n = 100000000 distribution = constant ==
statsort_longs best of 1: 0.1562 s ( 1.56 ns/elem) sort (kernel) best of 1: 22.3140 s ( 223.14 ns/elem) qsort (libc) best of 1: 3.7718 s ( 37.72 ns/elem)
--- include/linux/statsort.h | 22 +++ lib/statsort.c | 326 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 348 insertions(+) create mode 100644 include/linux/statsort.h create mode 100644 lib/statsort.c
include/linux/statsort.h new file +22 -0
@@ -0,0 +1,22 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_STATSORT_H +#define _LINUX_STATSORT_H + +#include <linux/types.h> + +/** +* typedef statsort_key_func_t - sort-key extraction callback +* @elem: pointer to the element to extract a key from +* @priv: opaque pointer, passed through from statsort()'s @priv +* +* Return: a signed 64-bit key such that, for any two elements a and +* b, (key(a) < key(b)) matches the order statsort() should produce. +*/ +typedef s64 (*statsort_key_func_t )(const void *elem,const void *priv); + +void statsort (void *base,size_t num,size_t size, +statsort_key_func_t key_func,const void *priv); + +void statsort_longs (long *base,size_t num); + +#endif /* _LINUX_STATSORT_H */
lib/statsort.c new file +326 -0
326 lines not on this page · raw message
Signature · 1 line
2.55.0
Andrew Morton
maintainerQuoted 2 lines · On Tue, 4 Aug 2026 16:34:49 -0700 Peter Taraba…
Adds
statsort(), a bucket/distribution sort for arrays keyed by a signed 64-bit value.
um why? Is there some intended user of this? If so, please share all the details.
because it's much faster than current alternatives and linux kernel will need it in future. don't forget the unknown is much larger than known.
FYI - this alg is even faster than C++ Boost library:
https://github.com/drpt78stu2/fspclib