mattsu2020:sort_fix - Branch - uutils/coreutils

sort:Improve fast lexicographic path for sort default mode

#9272Closed

Comparing

mattsu2020:sort_fix

(

da74869

) with

main

(

6e99389

)

-34%

Improvements: 1

Regressions: 18

Untouched: 105

Skipped: 5

No successful run was found on main ( 1c50306) during the generation of this report, so 6e99389 was used instead as the comparison base. There might be some changes unrelated to this pull request in this report.

Benchmarks

Skipped (5)

Failed

sort_accented_data[500000]

src/uu/sort/benches/sort_bench.rs

Regression

-29%

362.5 ms508.9 ms

sort_german_locale

src/uu/sort/benches/sort_locale_bench.rs

Regression

-22%

39.1 ms50.2 ms

sort_reverse_mixed

src/uu/sort/benches/sort_locale_bench.rs

Regression

-21%

39.1 ms49.8 ms

sort_ascii_only[500000]

src/uu/sort/benches/sort_bench.rs

Regression

-24%

353.6 ms466.8 ms

sort_ascii_utf8_locale

src/uu/sort/benches/sort_locale_bench.rs

Regression

-29%

43.1 ms60.3 ms

sort_case_insensitive[500000]

src/uu/sort/benches/sort_bench.rs

Regression

-5%

278.5 ms292.9 ms

sort_unique_mixed

src/uu/sort/benches/sort_locale_bench.rs

Regression

-21%

39.3 ms49.4 ms

sort_ascii_c_locale

src/uu/sort/benches/sort_locale_bench.rs

Regression

-29%

21.5 ms30.2 ms

sort_long_line[160000]

src/uu/sort/benches/sort_bench.rs

Regression

-10%

1.6 ms1.8 ms

sort_case_sensitive[500000]

src/uu/sort/benches/sort_bench.rs

Regression

-34%

174.2 ms262.8 ms

sort_mixed_utf8_locale

src/uu/sort/benches/sort_locale_bench.rs

Regression

-19%

38.8 ms48.1 ms

sort_unique_locale[500000]

src/uu/sort/benches/sort_bench.rs

Regression

-25%

494 ms658.7 ms

sort_numeric

src/uu/sort/benches/sort_locale_bench.rs

Regression

-7%

23.2 ms24.8 ms

sort_reverse_locale[500000]

src/uu/sort/benches/sort_bench.rs

Regression

-29%

362 ms511.3 ms

sort_german_c_locale

src/uu/sort/benches/sort_locale_bench.rs

Regression

-23%

38.4 ms50 ms

sort_key_field[500000]

src/uu/sort/benches/sort_bench.rs

Regression

-4%

700.1 ms725.9 ms

sort_mixed_c_locale

src/uu/sort/benches/sort_locale_bench.rs

Regression

-23%

38.3 ms49.5 ms

sort_mixed_data[500000]

src/uu/sort/benches/sort_bench.rs

Regression

-30%

327.3 ms465.3 ms

Improved

factor_table

src/uu/factor/benches/factor_bench.rs

+6%

195.3 ms184.9 ms

Passed

rm_recursive_tree

src/uu/rm/benches/rm_bench.rs

13.6 ms13.6 ms

b64_decode_ignore_garbage_synthetic

src/uu/base64/benches/base64_bench.rs

149.8 µs149.8 µs

split_number_chunks

src/uu/split/benches/split_bench.rs

275.5 µs275.3 µs

du_all_wide_tree[(5000, 500)]

src/uu/du/benches/du_bench.rs

18.2 ms18.2 ms

hashsum_md5

src/uu/hashsum/benches/hashsum_bench.rs

32 ms32 ms

hashsum_sha1

src/uu/hashsum/benches/hashsum_bench.rs

72.5 ms72.5 ms

tsort_complex_dag[50000]

src/uu/tsort/benches/tsort_bench.rs

84.7 ms84.7 ms

ls_recursive_mixed_tree

src/uu/ls/benches/ls_bench.rs

1.4 ms1.4 ms

tsort_wide_dag[100000]

src/uu/tsort/benches/tsort_bench.rs

134.8 ms134.7 ms

cp_archive_balanced_tree[(5, 4, 10)]

src/uu/cp/benches/cp_bench.rs

77.7 ms77.7 ms

mv_multiple_to_dir

src/uu/mv/benches/mv_bench.rs

13.1 ms13.1 ms

factor_multiple_u64s[2]

src/uu/factor/benches/factor_bench.rs

178.2 ms178.2 ms

hashsum_sha256

src/uu/hashsum/benches/hashsum_bench.rs

173.6 ms173.6 ms

uniq_heavy_duplicates[10000]

src/uu/uniq/benches/uniq_bench.rs

1.9 ms1.9 ms

uniq_with_count[10000]

src/uu/uniq/benches/uniq_bench.rs

1.9 ms1.9 ms

rm_single_file

src/uu/rm/benches/rm_bench.rs

106.5 ms106.5 ms

split_numeric_suffix

src/uu/split/benches/split_bench.rs

5.9 ms5.9 ms

split_lines

src/uu/split/benches/split_bench.rs

5.7 ms5.7 ms

hashsum_sha512

src/uu/hashsum/benches/hashsum_bench.rs

110.8 ms110.8 ms

hashsum_md5_check

src/uu/hashsum/benches/hashsum_bench.rs

32 ms32 ms

cksum_default

src/uu/cksum/benches/cksum_bench.rs

17.7 ms17.7 ms

fold_custom_width[50000]

src/uu/fold/benches/fold_bench.rs

32.1 ms32.1 ms

cksum_crc

src/uu/cksum/benches/cksum_bench.rs

17.7 ms17.7 ms

cksum_raw_output

src/uu/cksum/benches/cksum_bench.rs

17.7 ms17.7 ms

cut_fields_custom_delim

src/uu/cut/benches/cut_bench.rs

40.7 ms40.7 ms

fold_many_lines[100000]

src/uu/fold/benches/fold_bench.rs

77.8 ms77.8 ms

cksum_sysv

src/uu/cksum/benches/cksum_bench.rs

48 ms48 ms

numfmt_padding[(10000, 50)]

src/uu/numfmt/benches/numfmt_bench.rs

47.7 ms47.7 ms

numfmt_from_si[10000]

src/uu/numfmt/benches/numfmt_bench.rs

33.3 ms33.3 ms

cksum_crc32b

src/uu/cksum/benches/cksum_bench.rs

14.1 ms14.1 ms

hashsum_sha256_check

src/uu/hashsum/benches/hashsum_bench.rs

173.6 ms173.6 ms

numfmt_round_modes[("up", 10000)]

src/uu/numfmt/benches/numfmt_bench.rs

34.7 ms34.7 ms

cut_fields_tab

src/uu/cut/benches/cut_bench.rs

34.1 ms34.1 ms

cut_bytes

src/uu/cut/benches/cut_bench.rs

8.5 ms8.5 ms

cksum_blake2b

src/uu/cksum/benches/cksum_bench.rs

192.9 ms192.9 ms

cksum_shake256

src/uu/cksum/benches/cksum_bench.rs

1.9 s1.9 s

cksum_sha512

src/uu/cksum/benches/cksum_bench.rs

1.1 s1.1 s

cksum_sha384

src/uu/cksum/benches/cksum_bench.rs

1.1 s1.1 s

cksum_sha224

src/uu/cksum/benches/cksum_bench.rs

1.7 s1.7 s

cksum_shake128

src/uu/cksum/benches/cksum_bench.rs

1.5 s1.5 s

cksum_sha256

src/uu/cksum/benches/cksum_bench.rs

1.7 s1.7 s

wc_words_synthetic[2000]

src/uu/wc/benches/wc_bench.rs

11.4 s11.4 s

cksum_sm3

src/uu/cksum/benches/cksum_bench.rs

1.6 s1.6 s

cksum_md5

src/uu/cksum/benches/cksum_bench.rs

317.8 ms317.8 ms

cksum_bsd

src/uu/cksum/benches/cksum_bench.rs

128.1 ms128.1 ms

cksum_sha3

src/uu/cksum/benches/cksum_bench.rs

1.8 s1.8 s

cksum_sha2

src/uu/cksum/benches/cksum_bench.rs

1.7 s1.7 s

unexpand_large_file[10]

src/uu/unexpand/benches/unexpand_bench.rs

549.3 ms549.3 ms

cksum_sha1

src/uu/cksum/benches/cksum_bench.rs

722.9 ms722.9 ms

unexpand_many_lines[100000]

src/uu/unexpand/benches/unexpand_bench.rs

262 ms262 ms

tsort_tree_dag[(10, 3)]

src/uu/tsort/benches/tsort_bench.rs

34.4 ms34.4 ms

seq_custom_separator

src/uu/seq/benches/seq_bench.rs

28.7 ms28.7 ms

seq_formatted

src/uu/seq/benches/seq_bench.rs

97.2 ms97.2 ms

expand_many_lines[100000]

src/uu/expand/benches/expand_bench.rs

149.9 ms149.9 ms

numfmt_round_modes[("down", 10000)]

src/uu/numfmt/benches/numfmt_bench.rs

34.7 ms34.7 ms

numfmt_to_si[10000]

src/uu/numfmt/benches/numfmt_bench.rs

34.2 ms34.2 ms

nl_many_lines[100000]

src/uu/nl/benches/nl_bench.rs

79.8 ms79.8 ms

numfmt_to_iec[10000]

src/uu/numfmt/benches/numfmt_bench.rs

34.2 ms34.2 ms

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

src/uu/numfmt/benches/numfmt_bench.rs

34.7 ms34.7 ms

nl_large_file[10]

src/uu/nl/benches/nl_bench.rs

100.9 ms100.9 ms

expand_custom_tabstops[50000]

src/uu/expand/benches/expand_bench.rs

37 ms37 ms

wc_default_large_line_count[100000]

src/uu/wc/benches/wc_bench.rs

50.4 ms50.4 ms

numfmt_to_si_precision[10000]

src/uu/numfmt/benches/numfmt_bench.rs

35.5 ms35.5 ms

seq_integers

src/uu/seq/benches/seq_bench.rs

26.1 ms26.1 ms

wc_words_large_line_count[100000]

src/uu/wc/benches/wc_bench.rs

47.9 ms47.9 ms

seq_with_step

src/uu/seq/benches/seq_bench.rs

13.3 ms13.3 ms

numfmt_large_numbers_si[10000]

src/uu/numfmt/benches/numfmt_bench.rs

32.9 ms32.9 ms

cksum_multiple_files

src/uu/cksum/benches/cksum_bench.rs

26.5 ms26.5 ms

cut_characters

src/uu/cut/benches/cut_bench.rs

7.5 ms7.5 ms

cp_recursive_deep_tree[(120, 4)]

src/uu/cp/benches/cp_bench.rs

13.6 ms13.6 ms

ls_recursive_wide_tree[(10000, 1000)]

src/uu/ls/benches/ls_bench.rs

52.6 ms52.6 ms

rm_multiple_files

src/uu/rm/benches/rm_bench.rs

2.3 ms2.3 ms

rm_force_files

src/uu/rm/benches/rm_bench.rs

2.1 ms2.1 ms

uniq_case_insensitive[10000]

src/uu/uniq/benches/uniq_bench.rs

1.7 ms1.7 ms

tsort_linear_chain[1000000]

src/uu/tsort/benches/tsort_bench.rs

1.5 s1.5 s

mv_directory

src/uu/mv/benches/mv_bench.rs

3.5 ms3.5 ms

ls_recursive_long_all_mixed_tree

src/uu/ls/benches/ls_bench.rs

2.8 ms2.8 ms

ls_recursive_long_all_wide_tree[(15000, 1500)]

src/uu/ls/benches/ls_bench.rs

142.3 ms142.3 ms

ls_recursive_balanced_tree[(6, 4, 15)]

src/uu/ls/benches/ls_bench.rs

55.5 ms55.5 ms

ls_recursive_long_all_deep_tree[(100, 4)]

src/uu/ls/benches/ls_bench.rs

3.2 ms3.2 ms

wc_bytes_lines_synthetic[2000]

src/uu/wc/benches/wc_bench.rs

120.2 ms120.2 ms

wc_lines_extreme_line_lengths[(100000, 200)]

src/uu/wc/benches/wc_bench.rs

1.6 ms1.6 ms

mv_single_file

src/uu/mv/benches/mv_bench.rs

129.6 ms129.6 ms

wc_lines_large_line_count[500000]

src/uu/wc/benches/wc_bench.rs

2.9 ms2.9 ms

wc_lines_variable_length[(50, 500)]

src/uu/wc/benches/wc_bench.rs

3.4 ms3.4 ms

mv_force_overwrite

src/uu/mv/benches/mv_bench.rs

125.1 ms125.2 ms

b64_decode_synthetic

src/uu/base64/benches/base64_bench.rs

149.6 µs149.6 µs

ls_recursive_deep_tree[(200, 2)]

src/uu/ls/benches/ls_bench.rs

2.2 ms2.2 ms

wc_chars_large_line_count[100000]

src/uu/wc/benches/wc_bench.rs

994.9 µs995.1 µs

cksum_blake3

src/uu/cksum/benches/cksum_bench.rs

95.7 ms95.7 ms

ls_recursive_long_all_balanced_tree[(6, 4, 15)]

src/uu/ls/benches/ls_bench.rs

136 ms136 ms

cp_recursive_wide_tree[(6000, 800)]

src/uu/cp/benches/cp_bench.rs

189.3 ms189.4 ms

split_bytes

src/uu/split/benches/split_bench.rs

506.5 µs506.8 µs

cp_recursive_balanced_tree[(5, 4, 10)]

src/uu/cp/benches/cp_bench.rs

72.2 ms72.3 ms

wc_bytes_synthetic[500]

src/uu/wc/benches/wc_bench.rs

164.7 µs164.8 µs

tsort_input_parsing_heavy[5000]

src/uu/tsort/benches/tsort_bench.rs

82.4 ms82.4 ms

b64_encode_synthetic

src/uu/base64/benches/base64_bench.rs

146.4 µs146.5 µs

du_deep_tree[(100, 3)]

src/uu/du/benches/du_bench.rs

1.2 ms1.2 ms

cp_preserve_metadata[(5, 4, 10)]

src/uu/cp/benches/cp_bench.rs

74.9 ms75.1 ms

cp_large_file[16]

src/uu/cp/benches/cp_bench.rs

-1%

338.3 µs340.2 µs

du_wide_tree[(5000, 500)]

src/uu/du/benches/du_bench.rs

-1%

11.2 ms11.3 ms

sort_dictionary_order[500000]

src/uu/sort/benches/sort_bench.rs

-2%

1.1 s1.1 s

du_max_depth_balanced_tree[(6, 4, 10)]

src/uu/du/benches/du_bench.rs

-2%

32.5 ms33.1 ms

sort_numeric[500000]

src/uu/sort/benches/sort_bench.rs

-2%

1.2 s1.2 s

du_summarize_balanced_tree[(5, 4, 10)]

src/uu/du/benches/du_bench.rs

-2%

8.3 ms8.5 ms

Commits

Click on a commit to change the comparison range

Base

main

6e99389

-65.69%

fix format

0ee0e71

1 month ago

by mattsu2020

+65.7%

feat: add UTF-8 cache and token buffer to sorting chunks - Added token_buffer Vec<Field> to ChunkContents and RecycledChunk - Added utf8_cache Vec<Option<&'a str>> to LineData and RecycledChunk - Updated recycle, read, and parse_lines handling for new fields - Enables efficient tokenization and UTF-8 caching in sort operations

8b29782

1 month ago

by mattsu2020

-33.26%

refactor(sort): simplify merge_chunk_capacity calculation Use clamp() instead of chained max().min() for better readability. This replaces explicit bounds checking in merge_chunk_capacity() with the more idiomatic clamp method, achieving the same effect while reducing code verbosity.

0020eaf

1 month ago

by mattsu2020

-0.3%

feat: enhance external sort pipelining for better concurrency Implement dynamic pipeline depth to allow more overlapping between reading, sorting, and writing operations. The `pipeline_depth` setting now controls the number of in-flight chunks, with a minimum of 2, improving performance for large datasets by reducing I/O bottlenecks.

9911a1f

1 month ago

by mattsu2020

c415939

1 month ago

by mattsu2020

+33.56%

Merge branch 'sort_fix' of https://github.com/mattsu2020/coreutils into sort_fix

31a949f

1 month ago

by mattsu2020

-33.72%

feat(sort): add filtered lines caching and character filtering support Add a new `filtered_lines` field to `LineData` for caching processed line versions. Introduce `build_filtered_line` function to filter out non-printing or non-dictionary characters and handle case-ignore, enabling new sorting options. Update chunk recycling and parsing to manage the new field. Add buffer size normalization and pipeline depth tuning for improved memory efficiency in external sorting.

da74869

1 month ago

by mattsu2020

Home Terms Privacy Docs