GNUTest sort-float fails

[drinkcat]

./util/run-gnu-test.sh tests/sort/sort-float

--- exp	2025-05-29 19:17:40.585712112 +0200
+++ out	2025-05-29 19:17:40.587272316 +0200
@@ -3,9 +3,9 @@
 -3.4028235e+38
 -1.1754944e-38
 -2.2250738585072014e-308
--3.3621031431120935063e-4932
-0
 3.3621031431120935063e-4932
+0
+-3.3621031431120935063e-4932
 2.2250738585072014e-308
 1.1754944e-38
 3.4028235e+38

Simple repro:

$ cat > digits <<END
0
-3.3621031431120935063e-4932
3.3621031431120935063e-4932
END
$ env sort -sg digits 
-3.3621031431120935063e-4932
0
3.3621031431120935063e-4932
$ cargo run -p uu_sort -- -sg digits
0
-3.3621031431120935063e-4932
3.3621031431120935063e-4932

I've been looking at a bunch of number issues, I can look at this too.

[drinkcat]

https://www.gnu.org/software/coreutils/manual/coreutils.html#sort-invocation:

‘-g’
‘--general-numeric-sort’
‘--sort=general-numeric’
Sort numerically, converting a prefix of each line to a long double-precision floating point number. See Floating point numbers. Do not report overflow, underflow, or conversion errors.

It's our usual problem... We use f64 which is actualy single-precision. And f128 is not stable in Rust. I think we should move to ExtendedBigDecimal and do better than what GNU coreutils does.

Another interesting tidbit:

You can use this option to sort hexadecimal numbers prefixed with ‘0x’ or ‘0X’, where those numbers are not fixed width, or of varying case.

Sounds like another reason to use our generic parsing methods. (hexadecimal exponents appear to be supported as well)

[drinkcat]

I know somebody is going to ask about performance, so here's the baseline:

seq 100 -0.000258 0 | sort -R > tmp/floatdata
hyperfine -L sort sort,target/release/sort "{sort} -g tmp/floatdata"
Benchmark 1: sort -g tmp/floatdata
  Time (mean ± σ):     320.6 ms ±   6.5 ms    [User: 1001.8 ms, System: 10.0 ms]
  Range (min … max):   311.8 ms … 331.0 ms    10 runs
 
Benchmark 2: target/release/sort -g tmp/floatdata
  Time (mean ± σ):      77.4 ms ±  12.3 ms    [User: 353.7 ms, System: 25.2 ms]
  Range (min … max):    54.7 ms … 102.0 ms    49 runs
 
Summary
  target/release/sort -g tmp/floatdata ran
    4.14 ± 0.66 times faster than sort -g tmp/floatdata

And we do produce the same output:

$ target/release/sort -g tmp/floatdata | sha256sum
87ccc444843407197d10da4a04f7d7cda8d350ec6f2f56f6472e2ea3c695400b  -
$ sort -g tmp/floatdata | sha256sum
87ccc444843407197d10da4a04f7d7cda8d350ec6f2f56f6472e2ea3c695400b  -

[drinkcat]

Something's here: https://github.com/drinkcat/coreutils/tree/sort-float, but this comes at a significant performance cost (I made no attempt to optimize the parsing function, even pushing back against review comments IIRC... thinking this is something that wouldn't matter -- e.g. parsing performance doesn't matter for seq and printf)

A slowdown is to be expected, but maybe we can do better than 2x (we're still ~2x bettter than GNU though)

hyperfine -L sort sort,./sort-main,target/release/sort "{sort} -g tmp/floatdata"
Benchmark 1: sort -g tmp/floatdata
  Time (mean ± σ):     312.9 ms ±   5.3 ms    [User: 992.2 ms, System: 7.2 ms]
  Range (min … max):   306.9 ms … 326.7 ms    10 runs
 
Benchmark 2: ./sort-main -g tmp/floatdata
  Time (mean ± σ):      81.0 ms ±  13.4 ms    [User: 376.0 ms, System: 22.8 ms]
  Range (min … max):    60.5 ms … 104.3 ms    30 runs
 
Benchmark 3: target/release/sort -g tmp/floatdata
  Time (mean ± σ):     168.3 ms ±  18.7 ms    [User: 579.5 ms, System: 30.7 ms]
  Range (min … max):   147.5 ms … 213.3 ms    18 runs
 
Summary
  ./sort-main -g tmp/floatdata ran
    2.08 ± 0.41 times faster than target/release/sort -g tmp/floatdata
    3.86 ± 0.64 times faster than sort -g tmp/floatdata

[sylvestre]

i have been told that LANG can change the performance, you run both benchmark with LANG=C, right ?

[sylvestre]

I know somebody is going to ask about performance

You read my mind ;)

[drinkcat]

i have been told that LANG can change the performance, you run both benchmark with LANG=C, right ?

I didn't. Seems to be within the margin of error though, if there are any differences.

[drinkcat]

cargo build -r -p uu_sort && LANG= LC_ALL= hyperfine -L sort sort,./sort-main,./sort-baseline,target/release/sort "{sort} -g tmp/floatdata"
Benchmark 1: sort -g tmp/floatdata
  Time (mean ± σ):     320.1 ms ±  11.2 ms    [User: 1007.3 ms, System: 10.5 ms]
  Range (min … max):   306.5 ms … 339.8 ms    10 runs
 
Benchmark 2: ./sort-main -g tmp/floatdata
  Time (mean ± σ):      76.4 ms ±   8.9 ms    [User: 348.1 ms, System: 22.1 ms]
  Range (min … max):    59.6 ms …  92.1 ms    45 runs
 
Benchmark 3: ./sort-baseline -g tmp/floatdata
  Time (mean ± σ):     164.4 ms ±  12.8 ms    [User: 559.4 ms, System: 27.9 ms]
  Range (min … max):   143.5 ms … 194.2 ms    18 runs
 
Benchmark 4: target/release/sort -g tmp/floatdata
  Time (mean ± σ):     142.1 ms ±  15.3 ms    [User: 575.7 ms, System: 30.7 ms]
  Range (min … max):   108.6 ms … 165.3 ms    18 runs
 
Summary
  ./sort-main -g tmp/floatdata ran
    1.86 ± 0.29 times faster than target/release/sort -g tmp/floatdata
    2.15 ± 0.30 times faster than ./sort-baseline -g tmp/floatdata
    4.19 ± 0.51 times faster than sort -g tmp/floatdata

Some optimizations get us from 115% slower to 86% slower, but now I'm running out of low-hanging fruits...

[drinkcat]

Not 100% related to this, I think we can gain quite a bit of performance by doing the number parsing in parallel (similar to how the sorting is done in parallel). Would need to teach myself rayon.

edit: Would need to figure out how to parallelize chunk.rs::parse_lines