naoNao89:pr1-tsort-minimal-cycle - Branch - uutils/coreutils

tsort: fix minimal cycle reporting and precise back-edge removal (no refactors)

#8786Merged

Comparing

naoNao89:pr1-tsort-minimal-cycle

(

4d6fdea

) with

main

(

677fd95

)

+47%

Improvements: 1

Untouched: 124

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

Benchmarks

Improved

tsort_input_parsing_heavy[5000]

src/uu/tsort/benches/tsort_bench.rs

+47%

120.3 ms82 ms

Passed

du_max_depth_balanced_tree[(6, 4, 10)]

src/uu/du/benches/du_bench.rs

+1%

33.3 ms33 ms

sort_ascii_only[500000]

src/uu/sort/benches/sort_bench.rs

355.4 ms353.6 ms

cp_large_file[16]

src/uu/cp/benches/cp_bench.rs

343.7 µs342.4 µs

sort_reverse_locale[500000]

src/uu/sort/benches/sort_bench.rs

363.9 ms362.6 ms

du_deep_tree[(100, 3)]

src/uu/du/benches/du_bench.rs

1.2 ms1.2 ms

du_human_balanced_tree[(5, 4, 10)]

src/uu/du/benches/du_bench.rs

10.5 ms10.4 ms

du_all_balanced_tree[(4, 3, 10)]

src/uu/du/benches/du_bench.rs

1.6 ms1.6 ms

sort_numeric[500000]

src/uu/sort/benches/sort_bench.rs

1.2 s1.2 s

sort_long_line[160000]

src/uu/sort/benches/sort_bench.rs

1.6 ms1.6 ms

sort_german_c_locale

src/uu/sort/benches/sort_locale_bench.rs

38.4 ms38.4 ms

sort_german_locale

src/uu/sort/benches/sort_locale_bench.rs

39.1 ms39.1 ms

sort_unique_mixed

src/uu/sort/benches/sort_locale_bench.rs

39.3 ms39.3 ms

sort_key_field[500000]

src/uu/sort/benches/sort_bench.rs

700.1 ms699.9 ms

du_summarize_balanced_tree[(5, 4, 10)]

src/uu/du/benches/du_bench.rs

8.4 ms8.4 ms

du_wide_tree[(5000, 500)]

src/uu/du/benches/du_bench.rs

11.3 ms11.3 ms

ls_recursive_long_all_mixed_tree

src/uu/ls/benches/ls_bench.rs

2.8 ms2.8 ms

du_all_wide_tree[(5000, 500)]

src/uu/du/benches/du_bench.rs

18.2 ms18.2 ms

cp_preserve_metadata[(5, 4, 10)]

src/uu/cp/benches/cp_bench.rs

74.9 ms74.9 ms

split_numeric_suffix

src/uu/split/benches/split_bench.rs

5.9 ms5.9 ms

ls_recursive_deep_tree[(200, 2)]

src/uu/ls/benches/ls_bench.rs

2.2 ms2.2 ms

sort_numeric

src/uu/sort/benches/sort_locale_bench.rs

23.2 ms23.2 ms

cut_characters

src/uu/cut/benches/cut_bench.rs

7.5 ms7.5 ms

ls_recursive_long_all_deep_tree[(100, 4)]

src/uu/ls/benches/ls_bench.rs

3.2 ms3.2 ms

rm_single_file

src/uu/rm/benches/rm_bench.rs

106.5 ms106.5 ms

sort_mixed_c_locale

src/uu/sort/benches/sort_locale_bench.rs

38.3 ms38.3 ms

cut_bytes

src/uu/cut/benches/cut_bench.rs

8.5 ms8.5 ms

uniq_heavy_duplicates[10000]

src/uu/uniq/benches/uniq_bench.rs

1.9 ms1.9 ms

ls_recursive_long_all_wide_tree[(15000, 1500)]

src/uu/ls/benches/ls_bench.rs

142.4 ms142.4 ms

cut_fields_tab

src/uu/cut/benches/cut_bench.rs

34.1 ms34.1 ms

numfmt_padding[(10000, 50)]

src/uu/numfmt/benches/numfmt_bench.rs

47.8 ms47.8 ms

sort_dictionary_order[500000]

src/uu/sort/benches/sort_bench.rs

1.1 s1.1 s

numfmt_round_modes[("up", 10000)]

src/uu/numfmt/benches/numfmt_bench.rs

34.6 ms34.6 ms

seq_with_step

src/uu/seq/benches/seq_bench.rs

13.3 ms13.3 ms

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

src/uu/numfmt/benches/numfmt_bench.rs

34.7 ms34.7 ms

hashsum_md5_check

src/uu/hashsum/benches/hashsum_bench.rs

32 ms32 ms

numfmt_from_si[10000]

src/uu/numfmt/benches/numfmt_bench.rs

33.4 ms33.4 ms

wc_lines_extreme_line_lengths[(100000, 200)]

src/uu/wc/benches/wc_bench.rs

1.6 ms1.6 ms

numfmt_round_modes[("down", 10000)]

src/uu/numfmt/benches/numfmt_bench.rs

34.6 ms34.6 ms

ls_recursive_wide_tree[(10000, 1000)]

src/uu/ls/benches/ls_bench.rs

53 ms53 ms

numfmt_large_numbers_si[10000]

src/uu/numfmt/benches/numfmt_bench.rs

32.9 ms32.9 ms

seq_integers

src/uu/seq/benches/seq_bench.rs

26.1 ms26.1 ms

cksum_default

src/uu/cksum/benches/cksum_bench.rs

17.7 ms17.7 ms

seq_custom_separator

src/uu/seq/benches/seq_bench.rs

28.7 ms28.7 ms

sort_mixed_data[500000]

src/uu/sort/benches/sort_bench.rs

327.3 ms327.3 ms

expand_custom_tabstops[50000]

src/uu/expand/benches/expand_bench.rs

36.6 ms36.6 ms

seq_formatted

src/uu/seq/benches/seq_bench.rs

97.2 ms97.2 ms

cut_fields_custom_delim

src/uu/cut/benches/cut_bench.rs

40.7 ms40.7 ms

expand_many_lines[100000]

src/uu/expand/benches/expand_bench.rs

148.1 ms148.1 ms

unexpand_many_lines[100000]

src/uu/unexpand/benches/unexpand_bench.rs

262 ms262 ms

sort_case_insensitive[500000]

src/uu/sort/benches/sort_bench.rs

278.6 ms278.6 ms

unexpand_large_file[10]

src/uu/unexpand/benches/unexpand_bench.rs

549.3 ms549.3 ms

hashsum_sha256_check

src/uu/hashsum/benches/hashsum_bench.rs

173.6 ms173.6 ms

cksum_sha384

src/uu/cksum/benches/cksum_bench.rs

1.1 s1.1 s

cksum_sha512

src/uu/cksum/benches/cksum_bench.rs

1.1 s1.1 s

cksum_sha2

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_shake128

src/uu/cksum/benches/cksum_bench.rs

1.5 s1.5 s

cksum_shake256

src/uu/cksum/benches/cksum_bench.rs

1.9 s1.9 s

cksum_sha224

src/uu/cksum/benches/cksum_bench.rs

1.7 s1.7 s

cksum_sha3

src/uu/cksum/benches/cksum_bench.rs

1.8 s1.8 s

cksum_sm3

src/uu/cksum/benches/cksum_bench.rs

1.6 s1.6 s

cksum_sha256

src/uu/cksum/benches/cksum_bench.rs

1.7 s1.7 s

cksum_blake2b

src/uu/cksum/benches/cksum_bench.rs

192.9 ms192.9 ms

cksum_md5

src/uu/cksum/benches/cksum_bench.rs

317.8 ms317.8 ms

cksum_sysv

src/uu/cksum/benches/cksum_bench.rs

48 ms48 ms

cksum_sha1

src/uu/cksum/benches/cksum_bench.rs

722.9 ms722.9 ms

wc_bytes_lines_synthetic[2000]

src/uu/wc/benches/wc_bench.rs

120.2 ms120.2 ms

cksum_blake3

src/uu/cksum/benches/cksum_bench.rs

95.7 ms95.7 ms

cksum_bsd

src/uu/cksum/benches/cksum_bench.rs

128.1 ms128.1 ms

numfmt_to_si_precision[10000]

src/uu/numfmt/benches/numfmt_bench.rs

35.5 ms35.5 ms

sort_accented_data[500000]

src/uu/sort/benches/sort_bench.rs

362.4 ms362.4 ms

cksum_raw_output

src/uu/cksum/benches/cksum_bench.rs

17.8 ms17.8 ms

cksum_crc32b

src/uu/cksum/benches/cksum_bench.rs

14.1 ms14.1 ms

nl_large_file[10]

src/uu/nl/benches/nl_bench.rs

100.9 ms100.9 ms

nl_many_lines[100000]

src/uu/nl/benches/nl_bench.rs

79.8 ms79.8 ms

cksum_crc

src/uu/cksum/benches/cksum_bench.rs

17.8 ms17.8 ms

wc_default_large_line_count[100000]

src/uu/wc/benches/wc_bench.rs

50.4 ms50.4 ms

fold_many_lines[100000]

src/uu/fold/benches/fold_bench.rs

116.2 ms116.2 ms

wc_words_large_line_count[100000]

src/uu/wc/benches/wc_bench.rs

47.9 ms47.9 ms

cksum_multiple_files

src/uu/cksum/benches/cksum_bench.rs

26.6 ms26.6 ms

ls_recursive_balanced_tree[(6, 4, 15)]

src/uu/ls/benches/ls_bench.rs

56.4 ms56.4 ms

wc_lines_variable_length[(50, 500)]

src/uu/wc/benches/wc_bench.rs

3.4 ms3.4 ms

numfmt_to_iec[10000]

src/uu/numfmt/benches/numfmt_bench.rs

34.2 ms34.2 ms

wc_lines_large_line_count[500000]

src/uu/wc/benches/wc_bench.rs

2.9 ms2.9 ms

numfmt_to_si[10000]

src/uu/numfmt/benches/numfmt_bench.rs

34.2 ms34.2 ms

fold_custom_width[50000]

src/uu/fold/benches/fold_bench.rs

43.4 ms43.4 ms

rm_recursive_tree

src/uu/rm/benches/rm_bench.rs

13.6 ms13.6 ms

mv_single_file

src/uu/mv/benches/mv_bench.rs

129.6 ms129.6 ms

mv_directory

src/uu/mv/benches/mv_bench.rs

3.5 ms3.5 ms

uniq_case_insensitive[10000]

src/uu/uniq/benches/uniq_bench.rs

1.7 ms1.7 ms

mv_force_overwrite

src/uu/mv/benches/mv_bench.rs

125.1 ms125.1 ms

split_number_chunks

src/uu/split/benches/split_bench.rs

275.6 µs275.7 µs

rm_force_files

src/uu/rm/benches/rm_bench.rs

2.1 ms2.1 ms

split_lines

src/uu/split/benches/split_bench.rs

5.7 ms5.7 ms

sort_reverse_mixed

src/uu/sort/benches/sort_locale_bench.rs

39.1 ms39.1 ms

uniq_with_count[10000]

src/uu/uniq/benches/uniq_bench.rs

1.9 ms1.9 ms

sort_ascii_utf8_locale

src/uu/sort/benches/sort_locale_bench.rs

43 ms43.1 ms

rm_multiple_files

src/uu/rm/benches/rm_bench.rs

2.3 ms2.3 ms

hashsum_sha256

src/uu/hashsum/benches/hashsum_bench.rs

173.6 ms173.6 ms

ls_recursive_mixed_tree

src/uu/ls/benches/ls_bench.rs

1.4 ms1.4 ms

sort_case_sensitive[500000]

src/uu/sort/benches/sort_bench.rs

174.2 ms174.2 ms

sort_unique_locale[500000]

src/uu/sort/benches/sort_bench.rs

494 ms494 ms

hashsum_sha1

src/uu/hashsum/benches/hashsum_bench.rs

72.5 ms72.5 ms

sort_ascii_c_locale

src/uu/sort/benches/sort_locale_bench.rs

21.5 ms21.5 ms

ls_recursive_long_all_balanced_tree[(6, 4, 15)]

src/uu/ls/benches/ls_bench.rs

136.3 ms136.3 ms

wc_chars_large_line_count[100000]

src/uu/wc/benches/wc_bench.rs

994.5 µs994.6 µs

hashsum_sha512

src/uu/hashsum/benches/hashsum_bench.rs

110.8 ms110.8 ms

cp_recursive_deep_tree[(120, 4)]

src/uu/cp/benches/cp_bench.rs

13.6 ms13.6 ms

hashsum_md5

src/uu/hashsum/benches/hashsum_bench.rs

32 ms32 ms

mv_multiple_to_dir

src/uu/mv/benches/mv_bench.rs

13.1 ms13.1 ms

cp_recursive_wide_tree[(6000, 800)]

src/uu/cp/benches/cp_bench.rs

189.1 ms189.2 ms

b64_decode_synthetic

src/uu/base64/benches/base64_bench.rs

149.2 µs149.3 µs

cp_archive_balanced_tree[(5, 4, 10)]

src/uu/cp/benches/cp_bench.rs

77.8 ms77.9 ms

b64_encode_synthetic

src/uu/base64/benches/base64_bench.rs

146 µs146.1 µs

b64_decode_ignore_garbage_synthetic

src/uu/base64/benches/base64_bench.rs

149.8 µs149.9 µs

sort_mixed_utf8_locale

src/uu/sort/benches/sort_locale_bench.rs

38.8 ms38.8 ms

wc_bytes_synthetic[500]

src/uu/wc/benches/wc_bench.rs

164.2 µs164.2 µs

split_bytes

src/uu/split/benches/split_bench.rs

505.4 µs505.6 µs

cp_recursive_balanced_tree[(5, 4, 10)]

src/uu/cp/benches/cp_bench.rs

72.2 ms72.3 ms

tsort_wide_dag[100000]

src/uu/tsort/benches/tsort_bench.rs

134.6 ms134.7 ms

tsort_linear_chain[1000000]

src/uu/tsort/benches/tsort_bench.rs

1.5 s1.5 s

tsort_tree_dag[(10, 3)]

src/uu/tsort/benches/tsort_bench.rs

34.4 ms34.4 ms

tsort_complex_dag[50000]

src/uu/tsort/benches/tsort_bench.rs

84.6 ms84.7 ms

du_balanced_tree[(5, 4, 10)]

src/uu/du/benches/du_bench.rs

-1%

9.2 ms9.3 ms

Commits

Click on a commit to change the comparison range

Base

main

677fd95

+46.74%

fix(tsort): correct minimal cycle reporting and precise back-edge removal with iterative DFS - Implement iterative DFS to prevent stack overflows (from PR #8737) - Fix minimal cycle reporting to show only actual cycle nodes - Remove redundant back-edge from last cycle node to first - Update test expectations for corrected cycle handling

4d6fdea

2 months ago

by naoNao89

Home Terms Privacy Docs