automata benchmarks

History · Versus Spot and Oink

PR #164 · f8caaa56

Release profile: one codegen unit and fat LTO

status done · queued 2026-11-11 16:19 · started 2026-11-11 16:19 · finished 2026-11-11 16:41

· · rustc 1.95.0 (59807616e 2026-04-14) (built from a source tarball) · valgrind-3.26.0 · pinned to cpu 1

Against merge base 38e9f0d4 — 30 regressions, 195 improvements, 41 unchanged, 0 new

benchmarkbaseheadchangeheap bytes
dpa::dpa::accepted_word::chain_400383 293391 265+2.08 %
dpa::dpa::prefix_partition::chain_163 339 0693 574 178+7.04 %
dpa::dpa::prefix_partition::chain_8861 644916 107+6.32 %
dpa::dpa::prefix_partition::scrambled_163 707 9093 999 698+7.87 %
dpa::dpa::prefix_partition::scrambled_81 022 8581 086 510+6.22 %
dpa::dpa::sccs::chain_1000500 888511 023+2.02 %
dpa::dpa::sccs::chain_40001 928 6151 971 630+2.23 %
nondeterministic::nondeterministic::nba_witness::nba_400014 689 96117 383 333+18.33 %
nondeterministic::nondeterministic::nca_witness::nca_400019 458 26121 904 941+12.57 %
nondeterministic::nondeterministic::npa_witness::empty_npa_10009 121 9529 427 737+3.35 %
nondeterministic::nondeterministic::npa_witness::empty_npa_400037 023 30338 265 192+3.35 %
nondeterministic::nondeterministic::npa_witness::npa_10002 479 5312 979 072+20.15 %
nondeterministic::nondeterministic::npa_witness::npa_400020 354 25523 816 129+17.01 %
nondeterministic::nondeterministic::nra_witness::nra_400020 639 56721 455 583+3.95 %
runs::runs::dfa_accepts_one_word::len_10000266 070276 039+3.75 %+0.00 %
runs::runs::dfa_accepts_one_word::len_1000002 650 7312 750 700+3.77 %+0.00 %
runs::runs::dpa_recurrent_states::long10 502 98813 767 740+31.08 %+0.00 %
runs::runs::dpa_recurrent_states::short572 037596 810+4.33 %+0.00 %
storage::storage::clone_linked::k2_10000370 824380 760+2.68 %+0.00 %
storage::storage::complete_dense::partial_5000155 628238 753+53.41 %+0.00 %
storage::storage::edges_from_all_states_linked::k2_200068 03370 033+2.94 %+0.00 %
storage::storage::predecessors_of_all_states_linked::k2_200068 03370 033+2.94 %+0.00 %
storage::storage::reachable_states_csr::k2_80001 101 1151 124 918+2.16 %+0.00 %
storage::storage::reachable_states_dense::k2_80001 133 6991 173 507+3.51 %+0.00 %
storage::storage::reachable_states_linked::k2_8000924 279980 094+6.04 %+0.00 %
ts::ts::clone::scrambled_10000371 163381 079+2.67 %+0.00 %
ts::ts::clone::scrambled_400001 481 4001 521 316+2.69 %+0.00 %
ts::ts::edges_from_all_states::scrambled_200072 66974 646+2.72 %+0.00 %
ts::ts::predecessors_of_all_states::scrambled_200072 66974 646+2.72 %+0.00 %
ts::ts::predecessors_of_all_states::scrambled_8000288 601296 578+2.76 %+0.00 %
dfa::dfa::accepts_many_words::scrambled_1000343 072319 438-6.89 %+0.00 %
dfa::dfa::complement::scrambled_1000366 068318 874-12.89 %+0.00 %
dfa::dfa::complement::scrambled_40001 435 8731 247 649-13.11 %+0.00 %
dfa::dfa::equivalent::deep_difference_10061 66752 831-14.33 %+0.00 %
dfa::dfa::equivalent::deep_difference_400212 158177 852-16.17 %+0.00 %
dfa::dfa::equivalent::minimized_10035 84931 312-12.66 %+0.00 %
dfa::dfa::equivalent::minimized_400120 587103 504-14.17 %+0.00 %
dfa::dfa::give_word::empty_10001 872 6131 795 234-4.13 %+0.00 %
dfa::dfa::give_word::empty_40006 930 8236 603 983-4.72 %+0.00 %
dfa::dfa::give_word::far_1000164 342157 743-4.02 %+0.00 %
dfa::dfa::give_word::far_4000946 982909 225-3.99 %+0.00 %
dfa::dfa::intersection::scrambled_1003 319 7092 716 048-18.18 %+0.00 %
dfa::dfa::intersection::scrambled_20013 224 87310 809 511-18.26 %+0.00 %
dfa::dfa::intersection_is_empty::empty_10059 26650 659-14.52 %+0.00 %
dfa::dfa::intersection_is_empty::empty_200109 26992 418-15.42 %+0.00 %
dfa::dfa::is_empty_language::empty_10001 872 6151 795 234-4.13 %+0.00 %
dfa::dfa::is_empty_language::empty_40006 930 8256 603 983-4.72 %+0.00 %
dfa::dfa::minimize::minimal_10003 450 9243 298 979-4.40 %+0.00 %
dfa::dfa::minimize::minimal_400013 472 60212 876 089-4.43 %+0.00 %
dfa::dfa::minimize::redundant_10002 292 8072 174 551-5.16 %+0.00 %
dfa::dfa::minimize::redundant_40008 869 1068 406 754-5.21 %+0.00 %
dfa::dfa::minimize::scrambled_10003 670 2563 502 256-4.58 %+0.00 %
dfa::dfa::minimize::scrambled_400014 250 46913 587 258-4.65 %+0.00 %
dfa::dfa::minimize_moore_with_edge_colors::scrambled_10003 669 2523 500 317-4.60 %+0.00 %
dfa::dfa::minimize_moore_with_edge_colors::scrambled_400014 239 07313 571 891-4.69 %+0.00 %
dfa::dfa::union::scrambled_1003 319 7092 716 048-18.18 %+0.00 %
dfa::dfa::union::scrambled_20013 224 87310 809 511-18.26 %+0.00 %
dpa::dpa::accepted_word_fixtures::ltl546 210495 442-9.29 %
dpa::dpa::accepted_word_fixtures::synthetic1 402 2961 255 420-10.47 %
dpa::dpa::accepted_word_fixtures_by_atoms::ltl1 734 6751 620 528-6.58 %
dpa::dpa::accepted_word_fixtures_by_atoms::synthetic2 873 2562 741 079-4.60 %
dpa::dpa::collect_dpa::scrambled_1000299 640258 437-13.75 %
dpa::dpa::collect_dpa::scrambled_40001 169 0311 004 782-14.05 %
dpa::dpa::complement::chain_10004 096 9403 806 713-7.08 %
dpa::dpa::complement::chain_400016 653 21115 498 940-6.93 %
dpa::dpa::complement::scrambled_10004 958 4944 640 280-6.42 %
dpa::dpa::complement::scrambled_400020 037 45818 790 501-6.22 %
dpa::dpa::complement_fixtures::ltl1 480 5031 318 752-10.93 %
dpa::dpa::complement_fixtures::many_aps13 919 76412 439 582-10.63 %
dpa::dpa::complement_fixtures::synthetic9 652 5839 051 767-6.22 %
dpa::dpa::complement_without_normalizing::scrambled_1000574 441542 888-5.49 %
dpa::dpa::complement_without_normalizing::scrambled_40002 259 8232 135 235-5.51 %
dpa::dpa::equivalent_fixtures::many_aps21 649 39018 698 034-13.63 %
dpa::dpa::hoa_parse::ltl5 509 1615 102 006-7.39 %
dpa::dpa::hoa_parse::many_aps88 889 28180 066 844-9.93 %
dpa::dpa::hoa_parse::synthetic25 096 68123 303 319-7.15 %
dpa::dpa::hoa_print::ltl19 039 65114 449 079-24.11 %
dpa::dpa::hoa_print::many_aps19 675 34517 708 492-10.00 %
dpa::dpa::hoa_print::synthetic27 397 17621 972 183-19.80 %
dpa::dpa::included_fixtures::many_aps18 597 82315 907 783-14.46 %
dpa::dpa::included_in::complement_100270 299260 739-3.54 %
dpa::dpa::included_in::complement_2588 07584 611-3.93 %
dpa::dpa::included_in::complement_50151 571146 080-3.62 %
dpa::dpa::included_in::normalized_100543 003524 060-3.49 %
dpa::dpa::included_in::normalized_25184 848177 925-3.75 %
dpa::dpa::included_in::normalized_50313 519302 723-3.44 %
dpa::dpa::language_equivalent::complement_100279 874268 661-4.01 %
dpa::dpa::language_equivalent::complement_2590 60086 600-4.42 %
dpa::dpa::language_equivalent::complement_50156 446149 885-4.19 %
dpa::dpa::language_equivalent::normalized_100993 356963 959-2.96 %
dpa::dpa::language_equivalent::normalized_25326 815315 935-3.33 %
dpa::dpa::language_equivalent::normalized_50581 323564 774-2.85 %
dpa::dpa::map_edge_colors_collect::scrambled_1000297 297263 002-11.54 %
dpa::dpa::map_edge_colors_collect::scrambled_40001 157 6921 021 347-11.78 %
dpa::dpa::normalized::chain_10003 824 3863 513 188-8.14 %
dpa::dpa::normalized::chain_400015 564 65714 326 415-7.96 %
dpa::dpa::normalized::scrambled_10004 685 7424 346 572-7.24 %
dpa::dpa::normalized::scrambled_400018 948 70617 617 793-7.02 %
dpa::dpa::normalized::scrambled_k4_100026 000 72525 249 999-2.89 %
dpa::dpa::normalized_fixtures::ltl1 415 8891 272 930-10.10 %
dpa::dpa::normalized_fixtures::many_aps13 659 71512 275 183-10.14 %
dpa::dpa::normalized_fixtures::synthetic9 337 5918 843 733-5.29 %
dpa::dpa::rejected_word::chain_100938 248885 242-5.65 %
dpa::dpa::rejected_word::chain_4003 643 9433 441 573-5.55 %
dpa::dpa::rejected_word::scrambled_100247 893235 103-5.16 %
dpa::dpa::rejected_word::scrambled_400935 362887 076-5.16 %
dpa::dpa::witness_colors::chain_1004 741 5404 471 330-5.70 %
dpa::dpa::witness_colors::chain_40046 520 65343 697 424-6.07 %
dpa::dpa::witness_colors::scrambled_1004 126 3723 895 188-5.60 %
dpa::dpa::witness_colors::scrambled_40031 846 70129 950 000-5.96 %
dpa::dpa::witness_inequivalence::complement_100279 873268 661-4.01 %
dpa::dpa::witness_inequivalence::complement_2590 59986 600-4.41 %
dpa::dpa::witness_inequivalence::complement_50156 445149 885-4.19 %
dpa::dpa::witness_not_subset_of::complement_100270 298260 739-3.54 %
dpa::dpa::witness_not_subset_of::complement_2588 07484 611-3.93 %
dpa::dpa::witness_not_subset_of::complement_50151 570146 080-3.62 %
dpa::dpa::witness_not_subset_of::normalized_100543 002524 060-3.49 %
dpa::dpa::witness_not_subset_of::normalized_25184 847177 925-3.74 %
dpa::dpa::witness_not_subset_of::normalized_50313 518302 723-3.44 %
dpa::dpa::witnesses_fixtures::ltl2 229 2151 970 349-11.61 %
dpa::dpa::witnesses_fixtures::synthetic19 359 35615 821 117-18.28 %
game::game::tangle_learning::few_priorities_10002 697 0482 598 081-3.67 %+0.00 %
game::game::tangle_learning::few_priorities_40008 120 6767 882 207-2.94 %+0.00 %
game::game::tangle_learning::many_priorities_10002 018 0281 963 252-2.71 %+0.00 %
game::game::tangle_learning::many_priorities_40006 752 8356 594 921-2.34 %+0.00 %
game::game::tangle_learning_min_odd::few_priorities_40008 017 7007 799 992-2.72 %+0.00 %
game::game::zielonka::ladder_10005 134 2814 708 253-8.30 %+10.07 %
game::game::zielonka::ladder_400019 816 37318 161 867-8.35 %+10.08 %
game::game::zielonka::many_priorities_10004 103 5183 821 963-6.86 %+9.97 %
game::game::zielonka::many_priorities_400012 909 83712 101 969-6.26 %+10.04 %
game::game::zielonka_min_odd::few_priorities_10002 139 0772 040 908-4.59 %+0.00 %
game::game::zielonka_min_odd::few_priorities_40006 302 0756 089 965-3.37 %+0.00 %
learning::learning::lstar_mealy::counting_161 816 8471 758 351-3.22 %+0.00 %
learning::learning::lstar_mealy::counting_8481 469450 759-6.38 %+0.00 %
learning::learning::sprout_parity::inf_ab_1001 270 7571 147 944-9.66 %+0.00 %
learning::learning::sprout_parity::inf_ab_4002 610 8202 354 606-9.81 %+0.00 %
nondeterministic::nondeterministic::fixture_accepts::ltl762 545731 487-4.07 %
nondeterministic::nondeterministic::nca_accepts::nca_400266 229 440254 927 534-4.25 %
nondeterministic::nondeterministic::npa_accepts::empty_npa_400493 167 601458 821 236-6.96 %
nondeterministic::nondeterministic::npa_accepts::npa_10030 411 62829 740 298-2.21 %
runs::runs::dfa_accepts_many_words::count_10004 303 2134 053 182-5.81 %+0.00 %
runs::runs::dfa_reached_state::count_10003 570 2113 442 180-3.59 %+0.00 %
runs::runs::dpa_accepts_lassos::long9 150 7458 225 405-10.11 %+0.00 %
runs::runs::dpa_accepts_lassos::short406 490376 801-7.30 %+0.00 %
runs::runs::dpa_recurrent_edge_colors::short1 189 7901 058 624-11.02 %+0.00 %
runs::runs::dpa_visited_sequences::short370 678350 418-5.47 %+0.00 %
runs::runs::fixture_accepts_lassos::ltl8 766 2717 833 947-10.64 %
scc::scc::scc_queries::small_cycles_1000906 676855 946-5.60 %+0.00 %
scc::scc::scc_queries::small_cycles_40003 548 9193 348 761-5.64 %+0.00 %
scc::scc::tarjan::back_edges_1000512 099493 252-3.68 %+0.00 %
scc::scc::tarjan::back_edges_40001 987 6271 914 660-3.67 %+0.00 %
scc::scc::tarjan::binary_tree_1000571 217551 319-3.48 %+0.00 %
scc::scc::tarjan::binary_tree_40002 290 4592 212 941-3.38 %+0.00 %
scc::scc::tarjan::fragmented_1000658 522626 713-4.83 %+0.00 %
scc::scc::tarjan::fragmented_40002 534 1082 413 515-4.76 %+0.00 %
scc::scc::tarjan::grid_1024596 080575 645-3.43 %+0.00 %
scc::scc::tarjan::grid_40962 378 4842 299 205-3.33 %+0.00 %
scc::scc::tarjan::path_10001 929 1191 735 137-10.06 %+0.00 %
scc::scc::tarjan::path_40007 632 9086 859 748-10.13 %+0.00 %
scc::scc::tarjan::ring_1000512 099493 252-3.68 %+0.00 %
scc::scc::tarjan::ring_40001 987 6271 914 660-3.67 %+0.00 %
scc::scc::tarjan::scrambled_1000579 056559 051-3.45 %+0.00 %
scc::scc::tarjan::scrambled_40002 316 4972 238 975-3.35 %+0.00 %
scc::scc::tarjan::small_cycles_1000905 658854 928-5.60 %+0.00 %
scc::scc::tarjan::small_cycles_40003 544 9013 344 743-5.65 %+0.00 %
scc::scc::tarjan_from::fragmented_1000242 530232 901-3.97 %+0.00 %
scc::scc::tarjan_from::fragmented_4000907 762872 519-3.88 %+0.00 %
scc::scc::tarjan_from::path_10001 921 1581 724 740-10.22 %+0.00 %
scc::scc::tarjan_from::path_40007 545 5846 763 890-10.36 %+0.00 %
scc::scc::tarjan_from::ring_1000503 645482 362-4.23 %+0.00 %
scc::scc::tarjan_from::scrambled_1000570 602548 161-3.93 %+0.00 %
storage::storage::add_edges_linked::k2_50001 402 6701 252 451-10.71 %+0.00 %
storage::storage::add_edges_linked::k8_50006 669 2846 144 063-7.88 %+0.00 %
storage::storage::edges_from_all_states_dense::k2_2000102 04392 047-9.80 %+0.00 %
storage::storage::edges_from_all_states_dense::k8_2000140 043128 047-8.57 %+0.00 %
storage::storage::minimize_csr::redundant_20004 633 7564 399 816-5.05 %+0.00 %
storage::storage::minimize_csr::redundant_800018 159 86117 235 334-5.09 %+0.00 %
storage::storage::minimize_dense::redundant_20004 676 9104 434 823-5.18 %+0.00 %
storage::storage::minimize_dense::redundant_800018 364 89517 408 185-5.21 %+0.00 %
storage::storage::minimize_linked::redundant_20004 505 0384 305 957-4.42 %+0.00 %
storage::storage::minimize_linked::redundant_800017 714 72116 930 017-4.43 %+0.00 %
storage::storage::overwrite_edges_linked::k2_50003 790 7753 410 553-10.03 %+0.00 %
storage::storage::predecessors_of_all_states_dense::k2_2000290 369232 309-20.00 %+0.00 %
storage::storage::product_successor_dense::n20073 08765 088-10.94 %+0.00 %
storage::storage::remove_state_dense::k2_100001 072 212924 162-13.81 %+0.00 %
storage::storage::remove_state_linked::k2_100001 094 012997 019-8.87 %+0.00 %
storage::storage::run_many_words_csr::count_1000551 036512 039-7.08 %+0.00 %
storage::storage::run_many_words_dense::count_1000558 044512 042-8.24 %+0.00 %
storage::storage::run_one_word_csr::len_1000002 600 0542 500 040-3.85 %+0.00 %
storage::storage::run_one_word_dense::len_1000002 800 0502 600 042-7.14 %+0.00 %
storage::storage::successor_all_pairs_dense::k2_2000162 237150 205-7.42 %+0.00 %
storage::storage::successor_all_pairs_dense::k8_2000814 297778 259-4.43 %+0.00 %
ts::ts::add_edges_in_order::k2_50001 402 6711 062 446-24.26 %+0.00 %
ts::ts::add_edges_in_order::k8_50006 669 2855 384 058-19.27 %+0.00 %
ts::ts::add_edges_in_reverse::k2_50001 402 6711 062 446-24.26 %+0.00 %
ts::ts::canonical_naming::scrambled_15003 144 0903 034 522-3.48 %+0.00 %
ts::ts::canonical_naming::scrambled_500972 576938 266-3.53 %+0.00 %
ts::ts::collect_dts::scrambled_100003 455 1282 934 925-15.06 %+0.00 %
ts::ts::collect_dts::scrambled_4000013 759 60711 679 372-15.12 %+0.00 %
ts::ts::determinize::nth_from_end_104 414 3204 305 680-2.46 %+0.00 %
ts::ts::determinize::nth_from_end_1219 628 00619 177 588-2.29 %+0.00 %
ts::ts::determinize::nth_from_end_81 007 268980 440-2.66 %+0.00 %
ts::ts::determinize_propositional::aps_6_n_64 333 8444 088 248-5.67 %+0.00 %
ts::ts::determinize_propositional::aps_7_n_64 525 3874 295 587-5.08 %+0.06 %
ts::ts::determinize_propositional::aps_8_n_626 425 54225 052 413-5.20 %+0.34 %
ts::ts::erase_state_colors_collect::scrambled_100002 377 1721 846 855-22.31 %+0.00 %
ts::ts::into_dfa::scrambled_100003 635 1663 054 983-15.96 %+0.00 %
ts::ts::map_edge_colors_collect::scrambled_100002 368 7841 928 468-18.59 %+0.00 %
ts::ts::map_edge_colors_collect::scrambled_400009 415 4097 655 047-18.70 %+0.00 %
ts::ts::matching_product_successor_index::n20075 66247 602-37.09 %+0.00 %
ts::ts::minimal_representative_of_all_states::scrambled_1002 102 8112 002 068-4.79 %+0.00 %
ts::ts::minimal_representative_of_all_states::scrambled_30016 917 26116 088 404-4.90 %+0.00 %
ts::ts::minimal_representatives::scrambled_20003 386 0403 248 796-4.05 %+0.00 %
ts::ts::minimal_representatives::scrambled_800014 908 24914 321 191-3.94 %+0.00 %
ts::ts::reachable_states::scrambled_2000290 091243 901-15.92 %+0.00 %
ts::ts::reachable_states::scrambled_80001 148 696964 480-16.04 %+0.00 %
ts::ts::remove_edges_from_matching::scrambled_10000566 234446 232-21.19 %+0.00 %
ts::ts::remove_edges_from_matching::scrambled_40000896 234746 232-16.74 %+0.00 %
ts::ts::remove_state::scrambled_100001 091 012997 019-8.62 %+0.00 %
ts::ts::remove_state::scrambled_400001 421 0121 357 019-4.50 %+0.00 %
ts::ts::scc_minimal_representatives::small_cycles_100219 042210 321-3.98 %+0.00 %
ts::ts::scc_minimal_representatives::small_cycles_4001 242 4751 192 086-4.06 %+0.00 %
ts::ts::subset_construction::nth_from_end_1010 228 2069 439 133-7.71 %+0.00 %
ts::ts::subset_construction::nth_from_end_1245 253 02542 061 900-7.05 %+0.00 %
ts::ts::subset_construction::nth_from_end_82 233 5062 040 011-8.66 %+0.00 %
dfa::dfa::equivalent::different_1009 0478 349-7.72 %+0.00 %
dfa::dfa::equivalent::different_4009 0888 390-7.68 %+0.00 %
dpa::dpa::accepted_word::chain_100113 482114 774+1.14 %
dpa::dpa::accepted_word::scrambled_100145 688145 660-0.02 %
dpa::dpa::accepted_word::scrambled_400496 798499 945+0.63 %
dpa::dpa::sccs::scrambled_1000567 845576 822+1.58 %
dpa::dpa::sccs::scrambled_40002 257 4852 295 945+1.70 %
game::game::tangle_learning::ladder_10001 179 3141 169 460-0.84 %+0.00 %
game::game::tangle_learning::ladder_40004 408 1344 381 816-0.60 %+0.00 %
game::game::tangle_learning_min_odd::few_priorities_10001 521 6151 500 213-1.41 %+0.00 %
game::game::zielonka::few_priorities_10001 126 1991 107 876-1.63 %+0.00 %
game::game::zielonka::few_priorities_40003 470 2543 498 897+0.83 %+0.00 %
nondeterministic::nondeterministic::nba_accepts::nba_400125 269 894122 996 323-1.81 %
nondeterministic::nondeterministic::nma_witness::nma_100025 744 46925 383 666-1.40 %
nondeterministic::nondeterministic::npa_accepts::npa_400125 279 542122 955 922-1.85 %
runs::runs::dfa_accepts_one_word::len_1003 4923 561+1.98 %+0.00 %
runs::runs::dpa_recurrent_edge_colors::long15 116 26615 221 636+0.70 %+0.00 %
runs::runs::dpa_visited_sequences::long8 738 2638 707 283-0.35 %+0.00 %
runs::runs::fixture_accepts_lassos::synthetic4 340 1894 309 057-0.72 %
storage::storage::add_edges_dense::k2_50001 356 4011 360 814+0.33 %+0.00 %
storage::storage::add_edges_dense::k8_50004 247 0594 281 430+0.81 %+0.00 %
storage::storage::clone_csr::k2_1000030 59030 473-0.38 %+0.00 %
storage::storage::clone_dense::k2_1000015 11315 042-0.47 %+0.00 %
storage::storage::complete_linked::partial_50001 210 8541 202 009-0.73 %+0.00 %
storage::storage::edges_from_all_states_csr::k2_200072 04772 045-0.00 %+0.00 %
storage::storage::edges_from_all_states_csr::k8_2000108 047108 045-0.00 %+0.00 %
storage::storage::edges_from_all_states_linked::k8_2000152 033154 033+1.32 %+0.00 %
storage::storage::overwrite_edges_dense::k2_50002 126 4312 140 845+0.68 %+0.00 %
storage::storage::predecessors_of_all_states_csr::k2_2000102 046102 062+0.02 %+0.00 %
storage::storage::product_successor_csr::n20064 09665 088+1.55 %+0.00 %
storage::storage::product_successor_linked::n20046 54746 540-0.02 %+0.00 %
storage::storage::run_many_words_linked::count_1000481 044481 040-0.00 %+0.00 %
storage::storage::run_one_word_linked::len_1000002 350 0392 350 039+0.00 %+0.00 %
storage::storage::successor_all_pairs_csr::k2_2000122 242122 208-0.03 %+0.00 %
storage::storage::successor_all_pairs_csr::k8_2000702 302702 262-0.01 %+0.00 %
storage::storage::successor_all_pairs_linked::k2_2000108 236110 202+1.82 %+0.00 %
storage::storage::successor_all_pairs_linked::k8_2000750 296752 256+0.26 %+0.00 %
ts::ts::builder_with_edges::k2_500081 365 96779 806 463-1.92 %+0.00 %
ts::ts::edges_from_all_states::scrambled_k8_2000156 601158 578+1.26 %+0.00 %
ts::ts::successor_index_all_pairs::scrambled_2000108 863110 814+1.79 %+0.00 %
ts::ts::successor_index_all_pairs::scrambled_k8_2000750 855752 800+0.26 %+0.00 %

Wall-clock times

Criterion means of a single run. They depend on the machine and are not compared; use the instruction counts above for that.

benchmarkbasehead
collect/clone/1000003.93 ms (3.84 ms … 4.03 ms)5.15 ms (5.09 ms … 5.22 ms)
collect/clone/100000044.28 ms (43.85 ms … 44.72 ms)36.15 ms (35.28 ms … 37.03 ms)
collect/collect_owned/1000007.23 ms (7.19 ms … 7.27 ms)6.93 ms (6.89 ms … 6.97 ms)
collect/collect_owned/100000081.41 ms (79.65 ms … 83.17 ms)79.61 ms (77.48 ms … 81.73 ms)
collect/collect_ref/1000005.21 ms (5.19 ms … 5.22 ms)4.27 ms (4.23 ms … 4.32 ms)
collect/collect_ref/100000089.22 ms (88.40 ms … 90.04 ms)75.20 ms (73.79 ms … 76.60 ms)
collect/map_edge_colors_collect_owned/1000008.02 ms (7.96 ms … 8.07 ms)6.75 ms (6.73 ms … 6.77 ms)
collect/map_edge_colors_collect_owned/100000089.84 ms (87.48 ms … 92.21 ms)72.52 ms (71.82 ms … 73.21 ms)
wallclock/dfa/accepts/word_100000927.76 µs (909.78 µs … 945.75 µs)907.55 µs (904.06 µs … 911.03 µs)
wallclock/dfa/minimize/redundant_40001.40 ms (1.39 ms … 1.42 ms)1.35 ms (1.34 ms … 1.35 ms)
wallclock/dpa/complement/scrambled_40003.59 ms (3.59 ms … 3.60 ms)3.17 ms (3.14 ms … 3.19 ms)
wallclock/dpa/normalized/scrambled_40003.43 ms (3.36 ms … 3.50 ms)3.19 ms (3.15 ms … 3.23 ms)
wallclock/hoa/parse/ltl944.29 µs (940.39 µs … 948.18 µs)879.64 µs (859.66 µs … 899.63 µs)
wallclock/nfa/determinize/nth_from_end_123.45 ms (3.43 ms … 3.48 ms)3.25 ms (3.22 ms … 3.28 ms)
wallclock/nfa/subset_construction/nth_from_end_128.96 ms (8.78 ms … 9.15 ms)7.24 ms (7.20 ms … 7.28 ms)
wallclock/scc/tarjan/scrambled_100002.21 ms (2.19 ms … 2.24 ms)2.38 ms (2.34 ms … 2.41 ms)

Versus Spot and Oink

dpa/equivalence

inputreferenceoursreferenceours / referencesize (ours / reference)same result
hard/l-dsa-3spot180.50 µs120.80 µs1.49×– / –yes
hard/l-nba-2spot55.82 µs36.96 µs1.51×– / –yes
hard/m-nba-3spot236.16 µs139.00 µs1.70×– / –yes
ltl/and-gf-3spot8.94 µs12.10 µs0.74×– / –yes
ltl/eh-patterns-0spot21.56 µs20.32 µs1.06×– / –yes
ltl/gf-equiv-3spot19.96 µs34.28 µs0.58×– / –yes
ltl/gf-implies-3spot10.76 µs20.04 µs0.54×– / –yes
ltl/gh-q-3spot49.92 µs29.52 µs1.69×– / –yes
ltl/gh-r-3spot20.64 µs68.36 µs0.30×– / –yes
ltl/go-theta-3spot10.96 µs21.50 µs0.51×– / –yes
ltl/lily-patterns-1spot12.00 µs16.14 µs0.74×– / –yes
ltl/ms-phi-r-1spot10.24 µs39.10 µs0.26×– / –yes
ltl/ms-phi-s-1spot10.20 µs40.54 µs0.25×– / –yes
ltl/rv-counter-3spot27.96 µs13.56 µs2.06×– / –yes
ltl/sb-patterns-0spot12.40 µs14.34 µs0.86×– / –yes
ltl/sejk-k-2spot13.32 µs57.70 µs0.23×– / –yes
ltl/tv-uu-3spot41.08 µs38.16 µs1.08×– / –yes
ltl/u-left-3spot10.36 µs8.92 µs1.16×– / –yes
many_aps/and-gf-12spot153.12 µs66.72 µs2.29×– / –yes
many_aps/gf-equiv-12spot129.90 µs90.78 µs1.43×– / –yes
many_aps/r-right-10spot64.94 µs26.12 µs2.49×– / –yes
many_aps/random-n16-a8-p4-s1spot260.18 µs132.14 µs1.97×– / –yes
many_aps/random-n24-a12-p4-s1spot1.27 ms449.30 µs2.82×– / –yes
many_aps/random-n32-a16-p4-s1spot3.88 ms1.20 ms3.24×– / –yes
random/n128-a2-p6-s1spot331.92 µs210.76 µs1.57×– / –yes
random/n16-a1-p3-s1spot21.50 µs15.76 µs1.36×– / –yes
random/n256-a2-p8-s1spot887.81 µs485.11 µs1.83×– / –yes
random/n64-a2-p4-s1spot143.08 µs100.30 µs1.43×– / –yes

dpa/inclusion

inputreferenceoursreferenceours / referencesize (ours / reference)same result
hard/l-dsa-3spot70.86 µs61.98 µs1.14×– / –yes
hard/l-nba-2spot35.10 µs24.30 µs1.44×– / –yes
hard/m-nba-3spot147.58 µs88.02 µs1.68×– / –yes
ltl/and-gf-3spot5.80 µs8.40 µs0.69×– / –yes
ltl/eh-patterns-0spot14.44 µs17.90 µs0.81×– / –yes
ltl/gf-equiv-3spot11.62 µs19.36 µs0.60×– / –yes
ltl/gf-implies-3spot6.16 µs11.72 µs0.53×– / –yes
ltl/gh-q-3spot33.18 µs28.88 µs1.15×– / –yes
ltl/gh-r-3spot12.36 µs35.10 µs0.35×– / –yes
ltl/go-theta-3spot6.92 µs16.36 µs0.42×– / –yes
ltl/lily-patterns-1spot8.20 µs13.86 µs0.59×– / –yes
ltl/ms-phi-r-1spot6.08 µs19.92 µs0.31×– / –yes
ltl/ms-phi-s-1spot6.04 µs25.22 µs0.24×– / –yes
ltl/rv-counter-3spot18.32 µs14.98 µs1.22×– / –yes
ltl/sb-patterns-0spot7.80 µs13.08 µs0.60×– / –yes
ltl/sejk-k-2spot7.88 µs28.72 µs0.27×– / –yes
ltl/tv-uu-3spot28.42 µs30.38 µs0.94×– / –yes
ltl/u-left-3spot6.68 µs8.68 µs0.77×– / –yes
many_aps/and-gf-12spot121.74 µs53.96 µs2.26×– / –yes
many_aps/gf-equiv-12spot72.90 µs51.48 µs1.42×– / –yes
many_aps/r-right-10spot46.72 µs24.48 µs1.91×– / –yes
many_aps/random-n16-a8-p4-s1spot212.76 µs98.36 µs2.16×– / –yes
many_aps/random-n24-a12-p4-s1spot1.10 ms390.96 µs2.80×– / –yes
many_aps/random-n32-a16-p4-s1spot3.77 ms1.08 ms3.47×– / –yes
random/n128-a2-p6-s1spot205.56 µs131.34 µs1.57×– / –yes
random/n16-a1-p3-s1spot13.58 µs10.64 µs1.28×– / –yes
random/n256-a2-p8-s1spot512.81 µs313.88 µs1.63×– / –yes
random/n64-a2-p4-s1spot84.70 µs64.54 µs1.31×– / –yes

game/solve

inputreferenceoursreferenceours / referencesize (ours / reference)same result
ladder_10000oink-ppp2.65 ms324.00 µs8.18×10000 / 10000yes
ladder_10000oink-zlk2.65 ms310.50 µs8.53×10000 / 10000yes
ladder_10000spot2.65 ms9.60 ms0.28×10000 / 10000yes
ladder_50000oink-ppp18.84 ms2.13 ms8.83×50000 / 50000yes
ladder_50000oink-zlk18.84 ms2.25 ms8.37×50000 / 50000yes
ladder_50000spot18.84 ms71.48 ms0.26×50000 / 50000yes
random_few_10000oink-ppp6.91 ms1.40 ms4.95×10000 / 10000yes
random_few_10000oink-zlk6.91 ms2.82 ms2.45×10000 / 10000yes
random_few_10000spot6.91 ms20.42 ms0.34×10000 / 10000yes
random_few_50000oink-ppp80.49 ms18.43 ms4.37×50000 / 50000yes
random_few_50000oink-zlk80.49 ms20.47 ms3.93×50000 / 50000yes
random_few_50000spot80.49 ms692.71 ms0.12×50000 / 50000yes
random_many_10000oink-ppp7.20 ms1.56 ms4.61×10000 / 10000yes
random_many_10000oink-zlk7.20 ms2.90 ms2.48×10000 / 10000yes
random_many_10000spot7.20 ms30.12 ms0.24×10000 / 10000yes
random_many_50000oink-ppp78.05 ms38.73 ms2.01×50000 / 50000yes
random_many_50000oink-zlk78.05 ms45.33 ms1.72×50000 / 50000yes
random_many_50000spot78.05 ms722.66 ms0.11×50000 / 50000yes

Log

   Compiling num-integer v0.1.47
   Compiling polycool v0.4.0
   Compiling memoffset v0.9.1
   Compiling matrixmultiply v0.3.11
   Compiling arrayref v0.3.9
   Compiling roxmltree v0.20.0
   Compiling sptr v0.3.2
   Compiling parking_lot v0.12.5
   Compiling hugealloc v0.1.1
   Compiling tiny-skia-path v0.12.0
   Compiling oxidd-derive v0.13.0
   Compiling kurbo v0.13.1
   Compiling fontconfig-parser v0.5.8
   Compiling rustpython-parser-core v0.4.0
   Compiling num-bigint v0.4.8
   Compiling rustpython-parser v0.4.0
   Compiling miniz_oxide v0.8.9
   Compiling pyo3 v0.27.2
   Compiling fdeflate v0.3.7
   Compiling phf v0.11.3
   Compiling memmap2 v0.9.12
   Compiling getrandom v0.4.3
   Compiling rawpointer v0.2.1
   Compiling foldhash v0.1.5
   Compiling rustix v1.1.6
   Compiling fixedbitset v0.5.7
   Compiling zmij v1.0.23
   Compiling tinyvec v1.13.3
   Compiling hashbrown v0.15.5
   Compiling rustpython-ast v0.4.0
   Compiling fontdb v0.24.0
   Compiling svgtypes v0.16.2
   Compiling itertools v0.11.0
   Compiling png v0.18.1
   Compiling rayon v1.12.0
   Compiling oxidd-dump v0.8.0
   Compiling pyo3-macros v0.27.2
   Compiling unic-emoji-char v0.9.0
   Compiling unic-ucd-ident v0.9.0
   Compiling roxmltree v0.21.2
   Compiling tracing-attributes v0.1.31
   Compiling derive-where v1.7.0
   Compiling simplecss v0.2.2
   Compiling skrifa v0.44.0
   Compiling harfrust v0.12.0
   Compiling itertools v0.15.0
   Compiling num-complex v0.4.6
   Compiling linear-hashtbl v0.1.4
   Compiling numpy v0.27.1
   Compiling tracing-core v0.1.36
   Compiling is-docker v0.2.0
   Compiling color_quant v1.1.0
   Compiling base64 v0.23.1
   Compiling serde v1.0.229
   Compiling winnow v1.0.5
   Compiling quick-error v2.0.1
   Compiling serde_json v1.0.154
   Compiling thiserror v2.0.21
   Compiling pico-args v0.5.0
   Compiling xmlwriter v0.1.0
   Compiling unicode-segmentation v1.13.3
   Compiling unicode-script v0.5.9
   Compiling byteorder-lite v0.1.0
   Compiling unindent v0.2.4
   Compiling data-url v0.3.2
   Compiling weezl v0.1.12
   Compiling linux-raw-sys v0.12.1
   Compiling rustc-hash v1.1.0
   Compiling indoc v2.0.8
   Compiling unicode-vo v0.1.0
   Compiling imagesize v0.15.0
   Compiling lalrpop-util v0.20.2
   Compiling hashbrown v0.17.1
   Compiling unicode-bidi v0.3.18
   Compiling yansi v1.0.1
   Compiling pin-project-lite v0.2.17
   Compiling rustc-hash v2.1.3
   Compiling zune-core v0.5.3
   Compiling ariadne v0.6.0
   Compiling zune-jpeg v0.5.15
   Compiling indexmap v2.14.2
   Compiling tracing v0.1.44
   Compiling usvg v0.49.0
   Compiling chumsky v0.13.0
   Compiling oxidd-manager-index v0.13.1
   Compiling gif v0.14.2
   Compiling image-webp v0.2.4
   Compiling toml_parser v1.1.5+spec-1.1.0
   Compiling is-wsl v0.4.0
   Compiling ndarray v0.17.2
   Compiling tiny-skia v0.12.0
   Compiling oxidd-rules-bdd v0.13.0
   Compiling oxidd-cache v0.13.0
   Compiling toml_datetime v1.1.3+spec-1.1.0
   Compiling serde_spanned v1.1.3
   Compiling rgb v0.8.53
   Compiling thiserror-impl v2.0.21
   Compiling serde_derive v1.0.229
   Compiling itoa v1.0.18
   Compiling iana-time-zone v0.1.65
   Compiling num-conv v0.2.2
   Compiling toml_writer v1.2.0+spec-1.1.0
   Compiling powerfmt v0.2.1
   Compiling deranged v0.5.9
   Compiling fastrand v2.5.0
   Compiling time-core v0.1.9
   Compiling tempfile v3.27.0
   Compiling toml v1.2.1+spec-1.1.0
   Compiling resvg v0.49.0
   Compiling time v0.3.55
   Compiling chrono v0.4.45
   Compiling hoars v0.5.0
   Compiling oxidd v0.13.0
   Compiling open v5.4.5
   Compiling pyo3-stub-gen-derive v0.23.2
   Compiling ordered-float v5.4.0
   Compiling inventory v0.3.25
   Compiling maplit v1.0.2
   Compiling layout-rs v0.1.3
   Compiling pyo3-stub-gen v0.23.2
   Compiling automata v0.2.1 (/var/lib/automata-bench/work/src-head)
   Compiling automata-py v0.1.0 (/var/lib/automata-bench/work/src-head/python)
    Finished `release` profile [optimized] target(s) in 10m 06s
📦 Built wheel for abi3 Python ≥ 3.11 to /var/lib/automata-bench/work/versus-head/wheels/automatars-0.1.0-cp311-abi3-manylinux_2_34_aarch64.whl
== head: running benches/versus/compare.py (Spot, Oink)
dpa/equivalence/hard/l-dsa-3 vs spot: 0.181 ms / 0.121 ms
dpa/equivalence/hard/l-nba-2 vs spot: 0.056 ms / 0.037 ms
dpa/equivalence/hard/m-nba-3 vs spot: 0.236 ms / 0.139 ms
dpa/equivalence/ltl/and-gf-3 vs spot: 0.009 ms / 0.012 ms
dpa/equivalence/ltl/eh-patterns-0 vs spot: 0.022 ms / 0.020 ms
dpa/equivalence/ltl/gf-equiv-3 vs spot: 0.020 ms / 0.034 ms
dpa/equivalence/ltl/gf-implies-3 vs spot: 0.011 ms / 0.020 ms
dpa/equivalence/ltl/gh-q-3 vs spot: 0.050 ms / 0.030 ms
dpa/equivalence/ltl/gh-r-3 vs spot: 0.021 ms / 0.068 ms
dpa/equivalence/ltl/go-theta-3 vs spot: 0.011 ms / 0.021 ms
dpa/equivalence/ltl/lily-patterns-1 vs spot: 0.012 ms / 0.016 ms
dpa/equivalence/ltl/ms-phi-r-1 vs spot: 0.010 ms / 0.039 ms
dpa/equivalence/ltl/ms-phi-s-1 vs spot: 0.010 ms / 0.041 ms
dpa/equivalence/ltl/rv-counter-3 vs spot: 0.028 ms / 0.014 ms
dpa/equivalence/ltl/sb-patterns-0 vs spot: 0.012 ms / 0.014 ms
dpa/equivalence/ltl/sejk-k-2 vs spot: 0.013 ms / 0.058 ms
dpa/equivalence/ltl/tv-uu-3 vs spot: 0.041 ms / 0.038 ms
dpa/equivalence/ltl/u-left-3 vs spot: 0.010 ms / 0.009 ms
dpa/equivalence/many_aps/and-gf-12 vs spot: 0.153 ms / 0.067 ms
dpa/equivalence/many_aps/gf-equiv-12 vs spot: 0.130 ms / 0.091 ms
dpa/equivalence/many_aps/r-right-10 vs spot: 0.065 ms / 0.026 ms
dpa/equivalence/many_aps/random-n16-a8-p4-s1 vs spot: 0.260 ms / 0.132 ms
dpa/equivalence/many_aps/random-n24-a12-p4-s1 vs spot: 1.269 ms / 0.449 ms
dpa/equivalence/many_aps/random-n32-a16-p4-s1 vs spot: 3.875 ms / 1.197 ms
dpa/equivalence/random/n128-a2-p6-s1 vs spot: 0.332 ms / 0.211 ms
dpa/equivalence/random/n16-a1-p3-s1 vs spot: 0.022 ms / 0.016 ms
dpa/equivalence/random/n256-a2-p8-s1 vs spot: 0.888 ms / 0.485 ms
dpa/equivalence/random/n64-a2-p4-s1 vs spot: 0.143 ms / 0.100 ms
dpa/inclusion/hard/l-dsa-3 vs spot: 0.071 ms / 0.062 ms
dpa/inclusion/hard/l-nba-2 vs spot: 0.035 ms / 0.024 ms
dpa/inclusion/hard/m-nba-3 vs spot: 0.148 ms / 0.088 ms
dpa/inclusion/ltl/and-gf-3 vs spot: 0.006 ms / 0.008 ms
dpa/inclusion/ltl/eh-patterns-0 vs spot: 0.014 ms / 0.018 ms
dpa/inclusion/ltl/gf-equiv-3 vs spot: 0.012 ms / 0.019 ms
dpa/inclusion/ltl/gf-implies-3 vs spot: 0.006 ms / 0.012 ms
dpa/inclusion/ltl/gh-q-3 vs spot: 0.033 ms / 0.029 ms
dpa/inclusion/ltl/gh-r-3 vs spot: 0.012 ms / 0.035 ms
dpa/inclusion/ltl/go-theta-3 vs spot: 0.007 ms / 0.016 ms
dpa/inclusion/ltl/lily-patterns-1 vs spot: 0.008 ms / 0.014 ms
dpa/inclusion/ltl/ms-phi-r-1 vs spot: 0.006 ms / 0.020 ms
dpa/inclusion/ltl/ms-phi-s-1 vs spot: 0.006 ms / 0.025 ms
dpa/inclusion/ltl/rv-counter-3 vs spot: 0.018 ms / 0.015 ms
dpa/inclusion/ltl/sb-patterns-0 vs spot: 0.008 ms / 0.013 ms
dpa/inclusion/ltl/sejk-k-2 vs spot: 0.008 ms / 0.029 ms
dpa/inclusion/ltl/tv-uu-3 vs spot: 0.028 ms / 0.030 ms
dpa/inclusion/ltl/u-left-3 vs spot: 0.007 ms / 0.009 ms
dpa/inclusion/many_aps/and-gf-12 vs spot: 0.122 ms / 0.054 ms
dpa/inclusion/many_aps/gf-equiv-12 vs spot: 0.073 ms / 0.051 ms
dpa/inclusion/many_aps/r-right-10 vs spot: 0.047 ms / 0.024 ms
dpa/inclusion/many_aps/random-n16-a8-p4-s1 vs spot: 0.213 ms / 0.098 ms
dpa/inclusion/many_aps/random-n24-a12-p4-s1 vs spot: 1.096 ms / 0.391 ms
dpa/inclusion/many_aps/random-n32-a16-p4-s1 vs spot: 3.767 ms / 1.085 ms
dpa/inclusion/random/n128-a2-p6-s1 vs spot: 0.206 ms / 0.131 ms
dpa/inclusion/random/n16-a1-p3-s1 vs spot: 0.014 ms / 0.011 ms
dpa/inclusion/random/n256-a2-p8-s1 vs spot: 0.513 ms / 0.314 ms
dpa/inclusion/random/n64-a2-p4-s1 vs spot: 0.085 ms / 0.065 ms
game/solve/random_few_10000 vs spot: 6.908 ms / 20.415 ms
game/solve/random_few_10000 vs oink-zlk: 6.908 ms / 2.816 ms
game/solve/random_few_10000 vs oink-ppp: 6.908 ms / 1.396 ms
game/solve/random_few_50000 vs spot: 80.487 ms / 692.710 ms
game/solve/random_few_50000 vs oink-zlk: 80.487 ms / 20.473 ms
game/solve/random_few_50000 vs oink-ppp: 80.487 ms / 18.426 ms
game/solve/random_many_10000 vs spot: 7.197 ms / 30.121 ms
game/solve/random_many_10000 vs oink-zlk: 7.197 ms / 2.899 ms
game/solve/random_many_10000 vs oink-ppp: 7.197 ms / 1.561 ms
game/solve/random_many_50000 vs spot: 78.047 ms / 722.660 ms
game/solve/random_many_50000 vs oink-zlk: 78.047 ms / 45.328 ms
game/solve/random_many_50000 vs oink-ppp: 78.047 ms / 38.734 ms
game/solve/ladder_10000 vs spot: 2.650 ms / 9.602 ms
game/solve/ladder_10000 vs oink-zlk: 2.650 ms / 0.310 ms
game/solve/ladder_10000 vs oink-ppp: 2.650 ms / 0.324 ms
game/solve/ladder_50000 vs spot: 18.842 ms / 71.478 ms
game/solve/ladder_50000 vs oink-zlk: 18.842 ms / 2.252 ms
game/solve/ladder_50000 vs oink-ppp: 18.842 ms / 2.134 ms
== head: 266 benchmarks, 16 wall-clock measurements, 74 comparisons