naoNao89:feat/ls-locale-sorting-only - Branch - uutils/coreutils

ls: Implement locale-aware sorting

#8828

Comparing

naoNao89:feat/ls-locale-sorting-only

(

957061a

) with

main

(

cd27f69

)

-15%

Improvements: 3

Regressions: 5

Untouched: 98

New: 4

Skipped: 73

Benchmarks

Skipped (73)

Failed

ls_recursive_mixed_tree

src/uu/ls/benches/ls_bench.rs

Regression

-11%

1.4 ms1.5 ms

ls_recursive_long_all_deep_tree[(100, 4)]

src/uu/ls/benches/ls_bench.rs

Regression

-8%

3.2 ms3.4 ms

ls_recursive_balanced_tree[(6, 4, 15)]

src/uu/ls/benches/ls_bench.rs

Regression

-15%

56.1 ms66.1 ms

ls_recursive_deep_tree[(200, 2)]

src/uu/ls/benches/ls_bench.rs

Regression

-3%

2.1 ms2.2 ms

ls_recursive_long_all_balanced_tree[(6, 4, 15)]

src/uu/ls/benches/ls_bench.rs

Regression

-12%

136.8 ms156.3 ms

Improved

ls_recursive_long_all_mixed_tree

src/uu/ls/benches/ls_bench.rs

+25%

4 ms3.2 ms

ls_recursive_long_all_wide_tree[(15000, 1500)]

src/uu/ls/benches/ls_bench.rs

+10%

146.4 ms133 ms

ls_recursive_wide_tree[(10000, 1000)]

src/uu/ls/benches/ls_bench.rs

+9%

52.1 ms47.7 ms

New

ls_german_locale

src/uu/ls/benches/ls_bench.rs

N/A

N/A3.4 ms

ls_c_locale_explicit

src/uu/ls/benches/ls_bench.rs

N/A

N/A3.4 ms

ls_long_locale_comparison

src/uu/ls/benches/ls_bench.rs

N/A

N/A4 ms

ls_locale_sorting

src/uu/ls/benches/ls_bench.rs

N/A

N/A3.4 ms

Passed

du_balanced_tree[(5, 4, 10)]

src/uu/du/benches/du_bench.rs

+1%

9.2 ms9 ms

du_human_balanced_tree[(5, 4, 10)]

src/uu/du/benches/du_bench.rs

10.2 ms10.1 ms

sort_ascii_only[500000]

src/uu/sort/benches/sort_bench.rs

800 ms798 ms

sort_key_field[500000]

src/uu/sort/benches/sort_bench.rs

689.9 ms688.8 ms

cp_recursive_deep_tree[(120, 4)]

src/uu/cp/benches/cp_bench.rs

13.2 ms13.2 ms

mv_multiple_to_dir

src/uu/mv/benches/mv_bench.rs

13 ms12.9 ms

rm_single_file

src/uu/rm/benches/rm_bench.rs

100.4 ms100.4 ms

sort_mixed_utf8_locale

src/uu/sort/benches/sort_locale_bench.rs

94.1 ms94.1 ms

tsort_complex_dag[50000]

src/uu/tsort/benches/tsort_bench.rs

84 ms84 ms

sort_unique_mixed

src/uu/sort/benches/sort_locale_bench.rs

87.6 ms87.6 ms

cp_large_file[16]

src/uu/cp/benches/cp_bench.rs

293.6 µs293.6 µs

tsort_linear_chain[1000000]

src/uu/tsort/benches/tsort_bench.rs

1.5 s1.5 s

rm_force_files

src/uu/rm/benches/rm_bench.rs

2 ms2 ms

tsort_tree_dag[(10, 3)]

src/uu/tsort/benches/tsort_bench.rs

34.1 ms34.1 ms

split_numeric_suffix

src/uu/split/benches/split_bench.rs

6.1 ms6.1 ms

sort_numeric

src/uu/sort/benches/sort_locale_bench.rs

21.8 ms21.8 ms

sort_ascii_c_locale

src/uu/sort/benches/sort_locale_bench.rs

27.6 ms27.6 ms

split_lines

src/uu/split/benches/split_bench.rs

5.9 ms5.9 ms

sort_ascii_utf8_locale

src/uu/sort/benches/sort_locale_bench.rs

55.6 ms55.6 ms

uniq_heavy_duplicates[10000]

src/uu/uniq/benches/uniq_bench.rs

1.9 ms1.9 ms

cut_bytes

src/uu/cut/benches/cut_bench.rs

8.4 ms8.4 ms

uniq_with_count[10000]

src/uu/uniq/benches/uniq_bench.rs

1.8 ms1.8 ms

sort_random_strings

src/uu/sort/benches/sort_locale_bench.rs

56.8 ms56.8 ms

rm_multiple_files

src/uu/rm/benches/rm_bench.rs

2.2 ms2.2 ms

b64_decode_synthetic

src/uu/base64/benches/base64_bench.rs

145.7 µs145.7 µs

sort_german_locale

src/uu/sort/benches/sort_locale_bench.rs

94.5 ms94.5 ms

sort_reverse_mixed

src/uu/sort/benches/sort_locale_bench.rs

93.2 ms93.2 ms

cut_characters

src/uu/cut/benches/cut_bench.rs

7.5 ms7.5 ms

sort_german_c_locale

src/uu/sort/benches/sort_locale_bench.rs

94.5 ms94.5 ms

cut_fields_tab

src/uu/cut/benches/cut_bench.rs

33.9 ms33.9 ms

cut_fields_custom_delim

src/uu/cut/benches/cut_bench.rs

40.5 ms40.5 ms

rm_recursive_tree

src/uu/rm/benches/rm_bench.rs

14 ms14 ms

fold_custom_width[50000]

src/uu/fold/benches/fold_bench.rs

46.6 ms46.6 ms

numfmt_round_modes[("down", 10000)]

src/uu/numfmt/benches/numfmt_bench.rs

34.5 ms34.5 ms

hashsum_md5_check

src/uu/hashsum/benches/hashsum_bench.rs

32 ms32 ms

fold_many_lines[100000]

src/uu/fold/benches/fold_bench.rs

125.3 ms125.3 ms

numfmt_to_iec[10000]

src/uu/numfmt/benches/numfmt_bench.rs

34 ms34 ms

numfmt_from_si[10000]

src/uu/numfmt/benches/numfmt_bench.rs

33.1 ms33.1 ms

numfmt_to_si_precision[10000]

src/uu/numfmt/benches/numfmt_bench.rs

35.3 ms35.3 ms

numfmt_to_si[10000]

src/uu/numfmt/benches/numfmt_bench.rs

33.8 ms33.8 ms

numfmt_padding[(10000, 50)]

src/uu/numfmt/benches/numfmt_bench.rs

48.4 ms48.4 ms

wc_words_synthetic[2000]

src/uu/wc/benches/wc_bench.rs

10.3 s10.3 s

unexpand_large_file[10]

src/uu/unexpand/benches/unexpand_bench.rs

548 ms548 ms

hashsum_sha256_check

src/uu/hashsum/benches/hashsum_bench.rs

173.6 ms173.6 ms

expand_many_lines[100000]

src/uu/expand/benches/expand_bench.rs

100.9 ms100.9 ms

nl_large_file[10]

src/uu/nl/benches/nl_bench.rs

100.6 ms100.6 ms

unexpand_many_lines[100000]

src/uu/unexpand/benches/unexpand_bench.rs

261.4 ms261.4 ms

numfmt_round_modes[("up", 10000)]

src/uu/numfmt/benches/numfmt_bench.rs

32.7 ms32.7 ms

wc_bytes_lines_synthetic[2000]

src/uu/wc/benches/wc_bench.rs

120.2 ms120.2 ms

nl_many_lines[100000]

src/uu/nl/benches/nl_bench.rs

79.5 ms79.5 ms

wc_default_large_line_count[100000]

src/uu/wc/benches/wc_bench.rs

48.9 ms48.9 ms

numfmt_round_modes[("towards-zero", 10000)]

src/uu/numfmt/benches/numfmt_bench.rs

34.5 ms34.5 ms

sort_mixed_data[500000]

src/uu/sort/benches/sort_bench.rs

729.6 ms729.6 ms

wc_words_large_line_count[100000]

src/uu/wc/benches/wc_bench.rs

43.8 ms43.8 ms

hashsum_sha256

src/uu/hashsum/benches/hashsum_bench.rs

173.6 ms173.6 ms

sort_numeric[500000]

src/uu/sort/benches/sort_bench.rs

1.2 s1.2 s

seq_formatted

src/uu/seq/benches/seq_bench.rs

99.7 ms99.7 ms

sort_dictionary_order[500000]

src/uu/sort/benches/sort_bench.rs

1.1 s1.1 s

hashsum_sha512

src/uu/hashsum/benches/hashsum_bench.rs

111.7 ms111.7 ms

sort_case_sensitive[500000]

src/uu/sort/benches/sort_bench.rs

327.1 ms327.1 ms

sort_case_insensitive[500000]

src/uu/sort/benches/sort_bench.rs

417.1 ms417.1 ms

seq_integers

src/uu/seq/benches/seq_bench.rs

26.7 ms26.7 ms

hashsum_sha1

src/uu/hashsum/benches/hashsum_bench.rs

72.5 ms72.5 ms

seq_custom_separator

src/uu/seq/benches/seq_bench.rs

29.2 ms29.2 ms

expand_custom_tabstops[50000]

src/uu/expand/benches/expand_bench.rs

25.9 ms25.9 ms

sort_accented_data[500000]

src/uu/sort/benches/sort_bench.rs

819.3 ms819.3 ms

numfmt_large_numbers_si[10000]

src/uu/numfmt/benches/numfmt_bench.rs

34.5 ms34.5 ms

hashsum_md5

src/uu/hashsum/benches/hashsum_bench.rs

32 ms32 ms

sort_mixed_c_locale

src/uu/sort/benches/sort_locale_bench.rs

93.8 ms93.8 ms

wc_lines_variable_length[(50, 500)]

src/uu/wc/benches/wc_bench.rs

3.4 ms3.4 ms

uniq_case_insensitive[10000]

src/uu/uniq/benches/uniq_bench.rs

1.7 ms1.7 ms

seq_with_step

src/uu/seq/benches/seq_bench.rs

13.6 ms13.6 ms

b64_encode_synthetic

src/uu/base64/benches/base64_bench.rs

141.6 µs141.6 µs

wc_lines_large_line_count[500000]

src/uu/wc/benches/wc_bench.rs

2.9 ms2.9 ms

wc_lines_extreme_line_lengths[(100000, 200)]

src/uu/wc/benches/wc_bench.rs

1.6 ms1.6 ms

mv_directory

src/uu/mv/benches/mv_bench.rs

3.1 ms3.1 ms

wc_chars_large_line_count[100000]

src/uu/wc/benches/wc_bench.rs

990 µs990 µs

b64_decode_ignore_garbage_synthetic

src/uu/base64/benches/base64_bench.rs

145.2 µs145.2 µs

sort_unique_locale[500000]

src/uu/sort/benches/sort_bench.rs

1.1 s1.1 s

mv_single_file

src/uu/mv/benches/mv_bench.rs

120.5 ms120.5 ms

du_deep_tree[(100, 3)]

src/uu/du/benches/du_bench.rs

1.1 ms1.1 ms

wc_bytes_synthetic[500]

src/uu/wc/benches/wc_bench.rs

162.7 µs162.7 µs

tsort_wide_dag[100000]

src/uu/tsort/benches/tsort_bench.rs

135.5 ms135.5 ms

mv_force_overwrite

src/uu/mv/benches/mv_bench.rs

123.8 ms123.9 ms

cp_recursive_wide_tree[(6000, 800)]

src/uu/cp/benches/cp_bench.rs

187.8 ms187.9 ms

sort_long_line[160000]

src/uu/sort/benches/sort_bench.rs

2 ms2 ms

split_bytes

src/uu/split/benches/split_bench.rs

482.5 µs482.7 µs

cp_preserve_metadata[(5, 4, 10)]

src/uu/cp/benches/cp_bench.rs

73.9 ms73.9 ms

split_number_chunks

src/uu/split/benches/split_bench.rs

270.4 µs270.5 µs

cp_archive_balanced_tree[(5, 4, 10)]

src/uu/cp/benches/cp_bench.rs

76.7 ms76.8 ms

sort_reverse_locale[500000]

src/uu/sort/benches/sort_bench.rs

820.7 ms821.7 ms

du_max_depth_balanced_tree[(6, 4, 10)]

src/uu/du/benches/du_bench.rs

32.3 ms32.4 ms

tsort_input_parsing_heavy[50000]

src/uu/tsort/benches/tsort_bench.rs

12.8 s12.8 s

cp_recursive_balanced_tree[(5, 4, 10)]

src/uu/cp/benches/cp_bench.rs

71.3 ms71.4 ms

du_all_wide_tree[(5000, 500)]

src/uu/du/benches/du_bench.rs

18.1 ms18.1 ms

du_wide_tree[(5000, 500)]

src/uu/du/benches/du_bench.rs

11.3 ms11.3 ms

du_summarize_balanced_tree[(5, 4, 10)]

src/uu/du/benches/du_bench.rs

8.4 ms8.4 ms

du_all_balanced_tree[(4, 3, 10)]

src/uu/du/benches/du_bench.rs

-1%

1.6 ms1.6 ms

Commits

Click on a commit to change the comparison range

Base

main

cd27f69

-14.95%

fix: use is_ascii_uppercase() for clippy compliance

9f59362

18 hours ago

by naoNao89

-0.09%

perf(ls): reduce small-dir sorting overhead and stabilize group-directories-first ordering Use an adaptive strategy for Sort::Name: in-place comparator for small directories; cache bytes + index-permute for larger sets. Replace a second unstable sort for --group-directories-first with a stable partition via index permutation to preserve prior order.

1c55819

16 hours ago

by naoNao89

-0.34%

perf(ls): lower adaptive sort threshold from 64 to 24 entries Reduces CodSpeed regression in recursive workloads with medium-sized directories. Benchmark ls_recursive_balanced_tree has 19 entries per directory (4 subdirs + 15 files). With threshold=64, these use in-place sort, calling os_str_as_bytes_lossy() ~160 times per directory. Over 5,461 directories, this is ~874k conversions. Lowering threshold to 24 triggers byte caching for these directories, reducing conversions to 19 per directory (~104k total). Expected improvement: ~8.4x fewer conversions = ~15% speedup. Threshold remains above typical small directories (1-10 files) to avoid allocation overhead where in-place sort is faster.

d1b775f

5 hours ago

by naoNao89

+0.74%

fix(ls): correct threshold logic - use 16 to enable caching for 19-entry dirs Previous threshold=24 still used in-place sort for 19-entry directories because the condition is 'n <= threshold'. The balanced tree benchmark has 19 entries per directory (4 subdirs + 15 files), so threshold must be <19 to trigger caching. With threshold=16: - Directories with ≤16 entries: in-place sort (fast for very small dirs) - Directories with >16 entries: byte caching (fast for recursive workloads) - Balanced tree (19 entries): now uses caching ✓ This should eliminate the 15% CodSpeed regression in ls_recursive_balanced_tree.

b270e76

5 hours ago

by naoNao89

+0.14%

perf(ls): hybrid caching strategy - always cache in recursive mode Fixes recursive performance regression by detecting recursive mode and always using byte caching for those workloads. This is critical because recursive mode sorts thousands of small directories. Strategy: - Recursive mode OR large dirs (>8 entries): Use byte caching - Non-recursive small dirs (≤8 entries): Use in-place sort Recursive workloads like ls_recursive_balanced_tree sort ~5,461 directories with 19 entries each. Always caching in recursive mode eliminates repeated os_str_as_bytes_lossy() overhead. Expected results: - Recursive balanced/mixed/deep: Regression eliminated - Non-recursive: Minimal overhead - Wide trees: Continue improving (already using cache)

3aca88e

3 hours ago

by naoNao89

-0.62%

perf(ls): optimize locale sort with in-place algorithm Replace hybrid caching strategy with simpler in-place sort. Comprehensive benchmark comparison of 6 algorithms shows: - Algorithm 4 (in-place) is 9% faster in recursive workloads - Critical 19-entry dirs: 174.55µs vs 191.91µs (current) - Simpler code with less allocation overhead - No permutation complexity Benchmark methodology: - Tested sizes: 10, 19, 50, 100, 200 entries - Patterns: sequential, reverse, random - Recursive simulation: 100 dirs × 19 entries each - Tool: Criterion.rs with 5s measurement time Expected CodSpeed impact: -9% improvement in ls_recursive_balanced_tree

957061a

2 hours ago

by naoNao89

Home Terms Privacy Docs