Skip to contentSkip to conversation

lib: add statsort(), a distribution/bucket sort

PATCH In review Peter Taraba 2 participants 3 messages Aug 4 – Aug 5 Library code

lore
Share & tools
lore
#0 lore raw

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
new file mode 100644
index 000000000000..877f83cd2cfa
@@ -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
maintainer
#1 lore raw
Quoted 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.

#2 lore raw

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