automata benchmarks

History · Versus Spot and Oink

main · fc170083

PropExpression: truth tables instead of BDDs for up to 6 atomic propositions (#159)

status done · queued 2026-11-09 22:56 · started 2026-11-09 23:07 · finished 2026-11-09 23:17

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

Results

benchmarkinstructionsest. cyclesL1 hitsLL hitsRAM hitsheap bytesallocations
dfa::dfa::accepts_many_words::scrambled_1000343 072435 476428 9411 2231200
dfa::dfa::complement::scrambled_1000366 068584 230566 3353 39726139 10419
dfa::dfa::complement::scrambled_40001 435 8732 309 0852 223 22516 99725556 89623
dfa::dfa::equivalent::deep_difference_10061 66797 66490 4794419916 19625
dfa::dfa::equivalent::deep_difference_400212 158336 646314 2011 85037765 36433
dfa::dfa::equivalent::different_1009 04715 37112 5717791 80412
dfa::dfa::equivalent::different_4009 08815 57212 52777761 80412
dfa::dfa::equivalent::minimized_10035 84954 44551 890105587 75617
dfa::dfa::equivalent::minimized_400120 587182 449176 6997236131 58023
dfa::dfa::give_word::empty_10001 872 6132 558 7332 531 0284 92588152 8643 738
dfa::dfa::give_word::empty_40006 930 8239 657 0819 554 28620 05572679 80815 828
dfa::dfa::give_word::far_1000164 342231 691227 0315475528 176394
dfa::dfa::give_word::far_4000946 9821 329 4981 307 3883 92571148 4642 233
dfa::dfa::intersection::scrambled_1003 719 7275 957 6185 779 01312 0683 379428 08842
dfa::dfa::intersection::scrambled_20014 824 89124 130 02222 990 72797 30918 6501 708 12049
dfa::dfa::intersection_is_empty::empty_10059 26694 07387 3733118715 70020
dfa::dfa::intersection_is_empty::empty_200109 269175 052161 72761429331 58023
dfa::dfa::is_empty_language::empty_10001 872 6152 558 7372 531 0324 92588152 8643 738
dfa::dfa::is_empty_language::empty_40006 930 8259 657 0519 554 29120 05571679 80815 828
dfa::dfa::minimize::minimal_10003 435 7345 203 5714 825 98139 7555 1091 135 4922 214
dfa::dfa::minimize::minimal_400013 412 36820 482 39118 822 711204 59918 1914 543 7248 254
dfa::dfa::minimize::redundant_10002 284 6413 452 6693 214 85925 9113 093760 7801 201
dfa::dfa::minimize::redundant_40008 836 89613 488 24712 428 632143 6669 7513 044 9004 241
dfa::dfa::minimize::scrambled_10003 647 9265 556 0415 121 11151 1115 1251 116 0522 217
dfa::dfa::minimize::scrambled_400014 161 22721 944 44919 835 394294 15218 2374 470 1408 261
dfa::dfa::minimize_moore_with_edge_colors::scrambled_10003 646 9365 548 7365 119 14650 0925 1181 116 0522 217
dfa::dfa::minimize_moore_with_edge_colors::scrambled_400014 149 84521 911 33119 806 826300 63417 1814 470 1408 261
dfa::dfa::union::scrambled_1003 719 7125 957 5665 778 97612 0793 377428 08842
dfa::dfa::union::scrambled_20014 824 87624 129 92222 990 71797 29118 6501 708 12049
dpa::dpa::accepted_word::chain_100114 049174 945162 75558340––
dpa::dpa::accepted_word::chain_400385 618585 000550 3152 975566––
dpa::dpa::accepted_word::scrambled_100144 593217 201204 56642355––
dpa::dpa::accepted_word::scrambled_400492 445730 867697 4672 816552––
dpa::dpa::collect_dpa::scrambled_1000301 647500 484481 2893 8045––
dpa::dpa::collect_dpa::scrambled_40001 177 0402 005 8911 882 25616 4041 189––
dpa::dpa::complement::chain_10004 125 5906 305 5825 801 84755 1846 509––
dpa::dpa::complement::chain_400016 768 09925 769 82823 528 178261 95526 625––
dpa::dpa::complement::scrambled_10004 987 7067 517 2056 970 30562 8866 642––
dpa::dpa::complement::scrambled_400020 155 46530 763 80028 097 905344 38226 971––
dpa::dpa::complement_fixtures::ltl1 483 8052 145 7042 099 5895 499532––
dpa::dpa::complement_fixtures::synthetic9 509 40513 639 38513 097 865104 041609––
dpa::dpa::complement_without_normalizing::scrambled_1000574 451837 070807 7905 18496––
dpa::dpa::complement_without_normalizing::scrambled_40002 259 8443 331 2953 176 56021 9801 281––
dpa::dpa::hoa_parse::ltl10 976 38615 882 19615 506 34153 8353 048––
dpa::dpa::hoa_parse::synthetic40 742 71159 298 44858 078 258173 94010 014––
dpa::dpa::hoa_print::ltl49 150 12367 253 60066 625 815121 686553––
dpa::dpa::hoa_print::synthetic143 134 123197 191 498194 268 853580 721544––
dpa::dpa::included_in::complement_100316 766496 750479 465895366––
dpa::dpa::included_in::complement_25100 026165 127149 04759451––
dpa::dpa::included_in::complement_50166 929267 810251 295188445––
dpa::dpa::included_in::normalized_100748 7151 161 6251 129 8552 357571––
dpa::dpa::included_in::normalized_25271 850423 820408 715200403––
dpa::dpa::included_in::normalized_50456 846707 266689 756653407––
dpa::dpa::language_equivalent::complement_100316 770496 756479 476894366––
dpa::dpa::language_equivalent::complement_25100 030165 139149 04968450––
dpa::dpa::language_equivalent::complement_50166 933267 836251 301192445––
dpa::dpa::language_equivalent::normalized_1001 538 4562 373 4252 317 6705 061870––
dpa::dpa::language_equivalent::normalized_25533 110824 382801 967493570––
dpa::dpa::language_equivalent::normalized_50944 7791 452 8421 423 3221 368648––
dpa::dpa::map_edge_colors_collect::scrambled_1000308 288508 245488 0603 89720––
dpa::dpa::map_edge_colors_collect::scrambled_40001 201 6812 034 4181 906 34317 1801 205––
dpa::dpa::normalized::chain_10003 853 0365 962 9685 472 29852 9566 454––
dpa::dpa::normalized::chain_400015 679 54524 408 04622 212 141253 21926 566––
dpa::dpa::normalized::scrambled_10004 714 9547 174 2346 640 44460 6356 589––
dpa::dpa::normalized::scrambled_400019 066 71329 402 26726 781 397335 78326 913––
dpa::dpa::normalized::scrambled_k4_100025 992 20437 137 05134 981 221380 1507 288––
dpa::dpa::normalized_fixtures::ltl1 417 0902 055 9942 013 8844 663537––
dpa::dpa::normalized_fixtures::synthetic9 194 17213 237 62512 716 300100 324563––
dpa::dpa::prefix_partition::chain_163 332 7005 061 1264 995 3711 4821 667––
dpa::dpa::prefix_partition::chain_8859 3241 317 0061 286 396214844––
dpa::dpa::prefix_partition::scrambled_163 729 9725 708 2225 619 8423 8021 982––
dpa::dpa::prefix_partition::scrambled_81 026 3941 569 8961 537 731441856––
dpa::dpa::rejected_word::chain_100930 1141 363 4461 320 1562 939817––
dpa::dpa::rejected_word::chain_4003 612 3735 436 6845 135 74448 0291 737––
dpa::dpa::rejected_word::scrambled_100245 586382 036348 011526897––
dpa::dpa::rejected_word::scrambled_400927 0601 430 0241 315 93410 2251 799––
dpa::dpa::sccs::chain_1000501 801791 320715 7956 8381 181––
dpa::dpa::sccs::chain_40001 932 5143 084 2812 758 23129 9025 044––
dpa::dpa::sccs::scrambled_1000568 758889 350813 1508 2191 003––
dpa::dpa::sccs::scrambled_40002 261 3843 611 7963 232 65146 2894 220––
dpa::dpa::witness_colors::chain_1004 650 7646 571 3756 447 9259 0032 241––
dpa::dpa::witness_colors::chain_40045 138 56263 568 98061 967 685194 05618 029––
dpa::dpa::witness_colors::scrambled_1004 042 2945 713 8755 617 7759 4061 402––
dpa::dpa::witness_colors::scrambled_40030 679 17343 157 96542 331 805146 2132 717––
dpa::dpa::witness_inequivalence::complement_100316 767496 719479 479886366––
dpa::dpa::witness_inequivalence::complement_25100 027165 126149 04666450––
dpa::dpa::witness_inequivalence::complement_50166 930267 807251 302186445––
dpa::dpa::witness_not_subset_of::complement_100316 765496 753479 463896366––
dpa::dpa::witness_not_subset_of::complement_25100 025165 088149 04858450––
dpa::dpa::witness_not_subset_of::complement_50166 928267 805251 295187445––
dpa::dpa::witness_not_subset_of::normalized_100748 7141 161 6321 129 8522 359571––
dpa::dpa::witness_not_subset_of::normalized_25271 849423 777408 717198402––
dpa::dpa::witness_not_subset_of::normalized_50456 845707 257689 757651407––
dpa::dpa::witnesses_fixtures::ltl2 218 7593 181 8933 115 5287 358845––
dpa::dpa::witnesses_fixtures::synthetic19 216 49629 118 91928 514 469114 779873––
game::game::tangle_learning::few_priorities_10002 681 1744 034 0063 684 53135 9244 853745 4001 292
game::game::tangle_learning::few_priorities_40008 074 12612 626 42011 018 890194 96718 0772 407 4163 266
game::game::tangle_learning::ladder_10001 178 8141 829 6121 626 13212 4444 036377 868118
game::game::tangle_learning::ladder_40004 406 5837 080 7766 015 791110 85314 5921 511 668225
game::game::tangle_learning::many_priorities_10002 009 4443 025 8582 742 66325 5454 442566 440848
game::game::tangle_learning::many_priorities_40006 730 56210 478 3529 098 317166 24015 6812 187 3441 620
game::game::tangle_learning_min_odd::few_priorities_10001 520 4012 316 1212 075 52626 3563 109525 072189
game::game::tangle_learning_min_odd::few_priorities_40007 998 15112 324 14710 820 237215 97012 1162 560 0641 933
game::game::zielonka::few_priorities_10001 126 2021 709 1951 520 52512 4643 610356 67695
game::game::zielonka::few_priorities_40003 470 2575 583 7434 684 11381 69514 0331 278 56484
game::game::zielonka::ladder_10005 134 2847 016 1796 609 65950 0984 458499 404182
game::game::zielonka::ladder_400019 816 37627 232 08725 422 837246 14716 5291 998 868212
game::game::zielonka::many_priorities_10004 103 4375 602 1455 264 31538 6984 124764 940339
game::game::zielonka::many_priorities_400012 909 79117 933 44416 554 599176 13814 2332 552 644288
game::game::zielonka_min_odd::few_priorities_10002 139 0593 023 2732 800 56823 7582 969512 012195
game::game::zielonka_min_odd::few_priorities_40006 302 0649 279 6238 309 198131 0439 0061 705 700158
learning::learning::lstar_mealy::counting_161 785 6372 434 2122 388 1177281 213154 5042 633
learning::learning::lstar_mealy::counting_8478 081679 789646 50922391940 472862
learning::learning::sprout_parity::inf_ab_1001 272 8121 856 4081 793 4832 2391 478200 4161 872
learning::learning::sprout_parity::inf_ab_4002 614 0683 794 5093 677 6149 3162 009405 0403 649
nondeterministic::nondeterministic::fixture_accepts::ltl786 6801 233 3901 169 3508 090674––
nondeterministic::nondeterministic::nba_accepts::nba_400125 268 484185 045 746174 141 0161 657 44474 786––
nondeterministic::nondeterministic::nba_witness::nba_400014 586 04421 412 59820 397 658138 4279 223––
nondeterministic::nondeterministic::nca_accepts::nca_400266 215 466395 064 980369 412 6154 559 28781 598––
nondeterministic::nondeterministic::nca_witness::nca_400019 590 60929 462 93927 306 869325 51415 100––
nondeterministic::nondeterministic::nma_witness::nma_100025 727 43037 903 66235 879 082371 4984 774––
nondeterministic::nondeterministic::npa_accepts::empty_npa_400492 867 078734 421 679686 766 9348 907 94289 001––
nondeterministic::nondeterministic::npa_accepts::npa_10030 410 45844 530 78642 655 071286 34812 685––
nondeterministic::nondeterministic::npa_accepts::npa_400125 278 162185 056 942174 150 6671 657 76774 784––
nondeterministic::nondeterministic::npa_witness::empty_npa_10009 115 02413 456 66012 720 745123 5093 382––
nondeterministic::nondeterministic::npa_witness::empty_npa_400036 996 51755 319 49551 353 295657 31419 418––
nondeterministic::nondeterministic::npa_witness::npa_10002 471 0533 673 9233 507 44820 7511 792––
nondeterministic::nondeterministic::npa_witness::npa_400020 162 80429 311 81628 099 431177 9099 224––
nondeterministic::nondeterministic::nra_witness::nra_400020 617 67931 391 26928 841 099337 19024 692––
runs::runs::dfa_accepts_many_words::count_10004 303 2135 381 9615 357 6464 7931000
runs::runs::dfa_accepts_one_word::len_1003 4924 7984 39838600
runs::runs::dfa_accepts_one_word::len_10000266 070329 527325 827698600
runs::runs::dfa_accepts_one_word::len_1000002 650 7313 276 8253 244 7106 3251400
runs::runs::dfa_reached_state::count_10003 570 2114 404 9584 380 6434 7931000
runs::runs::dpa_accepts_lassos::long9 150 74511 671 38511 646 5653 144260724 664500
runs::runs::dpa_accepts_lassos::short406 490540 876535 5863729826 236472
runs::runs::dpa_recurrent_edge_colors::long14 635 82618 270 10918 215 5046 455638922 1442 090
runs::runs::dpa_recurrent_edge_colors::short1 098 1071 482 4881 469 2531 590151168 6841 708
runs::runs::dpa_recurrent_states::long11 749 19315 694 62915 662 6943 944349788 104860
runs::runs::dpa_recurrent_states::short589 492792 388783 93378812981 996782
runs::runs::dpa_visited_sequences::long8 738 26312 087 72612 050 5815 0633382 190 780850
runs::runs::dpa_visited_sequences::short370 678511 671506 1616266829 986545
runs::runs::fixture_accepts_lassos::ltl9 165 94213 379 73213 349 1175 227128––
runs::runs::fixture_accepts_lassos::synthetic4 646 2826 836 3006 773 82511 585130––
scc::scc::scc_queries::small_cycles_1000906 6141 433 1251 272 0209 4223 257261 132559
scc::scc::scc_queries::small_cycles_40003 548 8435 657 9634 973 84350 91312 2731 045 3962 071
scc::scc::tarjan::back_edges_1000512 037837 644726 6995 4732 388170 27245
scc::scc::tarjan::back_edges_40001 987 5513 267 0552 821 29526 4538 957680 63253
scc::scc::tarjan::binary_tree_1000571 155892 378815 6134 0621 613105 76039
scc::scc::tarjan::binary_tree_40002 290 3833 582 1503 276 31521 1275 720419 51245
scc::scc::tarjan::fragmented_1000658 4671 046 449922 6449 6482 159146 084121
scc::scc::tarjan::fragmented_40002 534 0394 125 4283 544 56362 7917 626569 852167
scc::scc::tarjan::grid_1024596 018971 686847 6817 7282 439171 16045
scc::scc::tarjan::grid_40962 378 4084 000 9063 363 60163 6709 113684 18453
scc::scc::tarjan::path_10001 929 0573 028 1582 729 48823 1875 221455 2242 064
scc::scc::tarjan::path_40007 632 83212 001 28310 804 66398 32320 1431 821 5368 076
scc::scc::tarjan::ring_1000512 037841 284725 7896 3832 388170 27245
scc::scc::tarjan::ring_40001 987 5513 284 2992 816 98430 7648 957680 63253
scc::scc::tarjan::scrambled_1000578 994936 142823 9526 9542 212170 27245
scc::scc::tarjan::scrambled_40002 316 4213 790 8003 296 68041 8728 136680 63253
scc::scc::tarjan::small_cycles_1000905 5961 431 7741 270 7349 4303 254261 132559
scc::scc::tarjan::small_cycles_40003 544 8255 650 3504 969 43550 29312 2701 045 3962 071
scc::scc::tarjan_from::fragmented_1000242 363394 053344 6482 5241 05174 98564
scc::scc::tarjan_from::fragmented_4000907 5531 491 7711 296 37615 9233 308299 62578
scc::scc::tarjan_from::path_10001 920 9703 017 7372 721 88223 0375 162468 9932 091
scc::scc::tarjan_from::path_40007 545 35411 928 15210 697 327106 73219 9191 876 7538 109
scc::scc::tarjan_from::ring_1000503 457836 369717 7146 2522 497184 04172
scc::scc::tarjan_from::scrambled_1000570 414929 847816 2226 4782 321184 04172
storage::storage::add_edges_dense::k2_50001 356 4012 030 6561 985 3414 940589180 20037
storage::storage::add_edges_dense::k8_50004 247 0596 412 0746 225 38917 8352 786671 72840
storage::storage::add_edges_linked::k2_50001 402 6702 420 4772 258 38214 2262 5991 113 96026
storage::storage::add_edges_linked::k8_50006 669 28411 260 26110 330 81175 81515 7253 866 49628
storage::storage::clone_csr::k2_1000030 590183 48052 6254 1703 143230 0126
storage::storage::clone_dense::k2_1000015 11381 33425 8042 2511 265110 0084
storage::storage::clone_linked::k2_10000370 822901 735529 79512 4668 846680 0083
storage::storage::complete_dense::partial_5000155 627209 425202 330908731364
storage::storage::complete_linked::partial_50001 210 8541 718 7051 629 4556 9511 55765 67218
storage::storage::edges_from_all_states_csr::k2_200072 04777 21475 859222700
storage::storage::edges_from_all_states_csr::k8_2000108 047116 392111 0721 008800
storage::storage::edges_from_all_states_dense::k2_2000102 043119 287117 842233800
storage::storage::edges_from_all_states_dense::k8_2000140 043160 563155 0381 0351000
storage::storage::edges_from_all_states_linked::k2_200068 03386 72575 9252 132400
storage::storage::edges_from_all_states_linked::k8_2000152 033203 735166 6807 376500
storage::storage::minimize_csr::redundant_20004 617 5826 940 5056 457 91057 8865 5191 505 4202 212
storage::storage::minimize_csr::redundant_800018 095 64327 530 14525 281 710272 64325 2926 023 3008 250
storage::storage::minimize_dense::redundant_20004 660 7366 970 9406 512 97558 1404 7791 522 1562 221
storage::storage::minimize_dense::redundant_800018 300 67727 860 93125 561 001279 02925 8516 090 3408 261
storage::storage::minimize_linked::redundant_20004 488 8646 856 4536 304 65361 9276 9191 522 1562 221
storage::storage::minimize_linked::redundant_800017 650 50327 227 88324 777 018302 85326 7606 090 3408 261
storage::storage::overwrite_edges_dense::k2_50002 126 4333 232 7543 172 4247 915593180 20037
storage::storage::overwrite_edges_linked::k2_50003 790 7766 671 1605 952 01544 77214 1512 031 46427
storage::storage::predecessors_of_all_states_csr::k2_2000102 046121 042117 407678700
storage::storage::predecessors_of_all_states_dense::k2_2000290 369397 967388 2221 6204732 0083
storage::storage::predecessors_of_all_states_linked::k2_200068 03391 69574 6903 366500
storage::storage::product_successor_csr::n20064 09675 54575 16014900
storage::storage::product_successor_dense::n20073 08794 65494 104401000
storage::storage::product_successor_linked::n20046 54760 18757 012579800
storage::storage::reachable_states_csr::k2_80001 101 1151 630 0761 591 8467 4153317 36811
storage::storage::reachable_states_dense::k2_80001 133 6991 684 5391 639 2448 8283317 36811
storage::storage::reachable_states_linked::k2_8000924 2791 485 6351 386 52019 5224317 36811
storage::storage::remove_state_dense::k2_100001 072 2121 565 2441 390 28421 5101 926176 0001 003
storage::storage::remove_state_linked::k2_100001 094 0121 531 4451 492 7357 4204680 0003 000
storage::storage::run_many_words_csr::count_1000551 036653 977644 1621 907800
storage::storage::run_many_words_dense::count_1000558 044690 065680 1651 9101000
storage::storage::run_many_words_linked::count_1000481 044611 149601 1191 957700
storage::storage::run_one_word_csr::len_1000002 600 0543 025 4282 993 8236 272700
storage::storage::run_one_word_dense::len_1000002 800 0503 425 4913 393 8116 273900
storage::storage::run_one_word_linked::len_1000002 350 0392 975 4282 943 7736 296500
storage::storage::successor_all_pairs_csr::k2_2000122 242139 528138 103229881
storage::storage::successor_all_pairs_csr::k8_2000702 302802 770797 3751 0238321
storage::storage::successor_all_pairs_dense::k2_2000162 237193 579192 089235981
storage::storage::successor_all_pairs_dense::k8_2000814 297952 885947 3451 0459321
storage::storage::successor_all_pairs_linked::k2_2000108 236139 124128 1792 140781
storage::storage::successor_all_pairs_linked::k8_2000750 296946 170909 0007 3857321
ts::ts::add_edges_in_order::k2_50001 402 6712 420 3472 258 38714 2272 5951 113 96026
ts::ts::add_edges_in_order::k8_50006 669 28511 260 14710 330 81275 82015 7213 866 49628
ts::ts::add_edges_in_reverse::k2_50001 402 6712 419 5772 258 58714 0262 5961 113 96026
ts::ts::builder_with_edges::k2_500081 362 02198 214 62795 711 932451 8126 9611 739 53245
ts::ts::canonical_naming::scrambled_15003 167 6084 657 7354 467 72021 7982 315463 8085 846
ts::ts::canonical_naming::scrambled_500980 4221 418 5151 374 7053 176798134 3361 831
ts::ts::clone::scrambled_10000371 163902 473530 23812 4838 852680 0083
ts::ts::clone::scrambled_400001 481 4003 817 8822 116 80742 57542 5202 720 0083
ts::ts::collect_dts::scrambled_100003 465 1496 166 1505 606 84537 17110 6702 228 06427
ts::ts::collect_dts::scrambled_4000013 799 62824 683 23422 329 474135 29847 9228 912 73631
ts::ts::determinize::nth_from_end_104 485 5246 644 8696 283 32422 2037 158651 7206 013
ts::ts::determinize::nth_from_end_1219 876 08529 277 12927 766 72999 01029 0102 732 60026 423
ts::ts::determinize::nth_from_end_81 027 3331 524 9111 441 5563 0491 946156 5521 396
ts::ts::edges_from_all_states::scrambled_200072 66991 97980 7742 1571200
ts::ts::edges_from_all_states::scrambled_k8_2000156 601208 928171 4287 4021400
ts::ts::erase_state_colors_collect::scrambled_100003 007 1665 308 2474 748 86237 17310 6722 228 06427
ts::ts::into_dfa::scrambled_100003 565 1656 276 2655 716 87537 18110 6712 228 06427
ts::ts::map_edge_colors_collect::scrambled_100003 008 7685 438 2024 819 54738 45012 1832 490 19227
ts::ts::map_edge_colors_collect::scrambled_4000011 975 39121 772 19419 182 194140 32953 9539 961 29631
ts::ts::matching_product_successor_index::n20075 662111 066106 4666473900
ts::ts::minimal_representative_of_all_states::scrambled_1002 100 8142 967 8562 964 19112103347 5044 679
ts::ts::minimal_representative_of_all_states::scrambled_30016 911 26423 979 43123 966 5111 8421063 116 78438 196
ts::ts::minimal_representatives::scrambled_20003 384 0404 762 1304 715 2358 91067322 9447 709
ts::ts::minimal_representatives::scrambled_800014 900 24920 949 86520 734 91042 592571 464 89632 693
ts::ts::predecessors_of_all_states::scrambled_200072 66996 91579 5403 3911200
ts::ts::predecessors_of_all_states::scrambled_8000288 601389 362313 81215 0191300
ts::ts::reachable_states::scrambled_2000290 091460 935440 0053 605834 3369
ts::ts::reachable_states::scrambled_80001 148 6961 838 5401 739 09019 5195317 36811
ts::ts::remove_edges_from_matching::scrambled_10000566 234795 987771 6474 6583064 0002 000
ts::ts::remove_edges_from_matching::scrambled_40000896 2341 177 4871 126 27210 0333064 0002 000
ts::ts::remove_state::scrambled_100001 091 0121 528 4451 489 7357 4204680 0003 000
ts::ts::remove_state::scrambled_400001 421 0121 912 9091 843 61913 5364680 0003 000
ts::ts::scc_minimal_representatives::small_cycles_100219 944321 099305 5445943644 272309
ts::ts::scc_minimal_representatives::small_cycles_4001 246 3521 775 6451 725 2553 890884354 1481 325
ts::ts::subset_construction::nth_from_end_1010 216 38414 514 16714 019 01245 5097 6461 073 5209 919
ts::ts::subset_construction::nth_from_end_1245 206 09464 008 67361 763 083218 74132 9114 518 97643 857
ts::ts::subset_construction::nth_from_end_82 230 4653 186 9313 078 3816 2052 215257 1042 276
ts::ts::successor_index_all_pairs::scrambled_2000108 863140 297129 0222 1571481
ts::ts::successor_index_all_pairs::scrambled_k8_2000750 855947 282909 7427 40315321

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.

benchmarkhead
collect/clone/1000004.31 ms (4.28 ms … 4.35 ms)
collect/clone/100000043.09 ms (42.20 ms … 43.98 ms)
collect/collect_owned/1000008.00 ms (7.87 ms … 8.13 ms)
collect/collect_owned/100000086.70 ms (85.19 ms … 88.21 ms)
collect/collect_ref/1000005.12 ms (5.11 ms … 5.12 ms)
collect/collect_ref/100000089.54 ms (89.31 ms … 89.77 ms)
collect/map_edge_colors_collect_owned/1000007.56 ms (7.50 ms … 7.62 ms)
collect/map_edge_colors_collect_owned/100000089.63 ms (88.99 ms … 90.27 ms)
wallclock/dfa/accepts/word_100000919.80 µs (917.04 µs … 922.56 µs)
wallclock/dfa/minimize/redundant_40001.43 ms (1.43 ms … 1.43 ms)
wallclock/dpa/complement/scrambled_40003.54 ms (3.48 ms … 3.59 ms)
wallclock/dpa/normalized/scrambled_40003.29 ms (3.28 ms … 3.31 ms)
wallclock/hoa/parse/ltl1.74 ms (1.74 ms … 1.75 ms)
wallclock/nfa/determinize/nth_from_end_123.53 ms (3.51 ms … 3.55 ms)
wallclock/nfa/subset_construction/nth_from_end_128.08 ms (7.93 ms … 8.23 ms)
wallclock/scc/tarjan/scrambled_100002.23 ms (2.23 ms … 2.23 ms)

Versus Spot and Oink

dpa/equivalence

inputreferenceoursreferenceours / referencesize (ours / reference)same result
hard/l-dsa-3spot309.96 µs153.24 µs2.02×– / –yes
hard/l-nba-2spot131.92 µs34.72 µs3.80×– / –yes
hard/m-nba-3spot552.85 µs132.26 µs4.18×– / –yes
ltl/and-gf-3spot17.00 µs11.40 µs1.49×– / –yes
ltl/eh-patterns-0spot53.12 µs19.08 µs2.78×– / –yes
ltl/gf-equiv-3spot39.26 µs33.00 µs1.19×– / –yes
ltl/gf-implies-3spot19.20 µs18.24 µs1.05×– / –yes
ltl/gh-q-3spot109.18 µs27.50 µs3.97×– / –yes
ltl/gh-r-3spot52.62 µs67.48 µs0.78×– / –yes
ltl/go-theta-3spot21.62 µs20.28 µs1.07×– / –yes
ltl/lily-patterns-1spot26.20 µs14.96 µs1.75×– / –yes
ltl/ms-phi-r-1spot22.90 µs36.92 µs0.62×– / –yes
ltl/ms-phi-s-1spot23.08 µs38.64 µs0.60×– / –yes
ltl/rv-counter-3spot46.96 µs12.18 µs3.86×– / –yes
ltl/sb-patterns-0spot21.38 µs13.28 µs1.61×– / –yes
ltl/sejk-k-2spot32.96 µs56.76 µs0.58×– / –yes
ltl/tv-uu-3spot155.24 µs36.54 µs4.25×– / –yes
ltl/u-left-3spot17.80 µs8.12 µs2.19×– / –yes
random/n128-a2-p6-s1spot860.05 µs201.84 µs4.26×– / –yes
random/n16-a1-p3-s1spot36.04 µs14.56 µs2.48×– / –yes
random/n256-a2-p8-s1spot2.65 ms460.52 µs5.75×– / –yes
random/n64-a2-p4-s1spot374.50 µs95.74 µs3.91×– / –yes

dpa/inclusion

inputreferenceoursreferenceours / referencesize (ours / reference)same result
hard/l-dsa-3spot141.34 µs59.10 µs2.39×– / –yes
hard/l-nba-2spot63.48 µs21.16 µs3.00×– / –yes
hard/m-nba-3spot267.86 µs81.08 µs3.30×– / –yes
ltl/and-gf-3spot8.48 µs7.04 µs1.20×– / –yes
ltl/eh-patterns-0spot26.62 µs15.72 µs1.69×– / –yes
ltl/gf-equiv-3spot20.30 µs17.76 µs1.14×– / –yes
ltl/gf-implies-3spot9.84 µs10.02 µs0.98×– / –yes
ltl/gh-q-3spot53.96 µs26.24 µs2.06×– / –yes
ltl/gh-r-3spot26.02 µs32.76 µs0.79×– / –yes
ltl/go-theta-3spot10.80 µs14.52 µs0.74×– / –yes
ltl/lily-patterns-1spot13.74 µs11.96 µs1.15×– / –yes
ltl/ms-phi-r-1spot11.76 µs17.84 µs0.66×– / –yes
ltl/ms-phi-s-1spot11.92 µs23.38 µs0.51×– / –yes
ltl/rv-counter-3spot23.96 µs13.08 µs1.83×– / –yes
ltl/sb-patterns-0spot10.84 µs10.72 µs1.01×– / –yes
ltl/sejk-k-2spot16.56 µs27.18 µs0.61×– / –yes
ltl/tv-uu-3spot75.90 µs28.00 µs2.71×– / –yes
ltl/u-left-3spot8.64 µs7.66 µs1.13×– / –yes
random/n128-a2-p6-s1spot430.44 µs124.14 µs3.47×– / –yes
random/n16-a1-p3-s1spot17.32 µs8.98 µs1.93×– / –yes
random/n256-a2-p8-s1spot1.30 ms286.08 µs4.56×– / –yes
random/n64-a2-p4-s1spot180.86 µs59.00 µs3.07×– / –yes

game/solve

inputreferenceoursreferenceours / referencesize (ours / reference)same result
ladder_10000oink-ppp2.75 ms295.00 µs9.31×10000 / 10000yes
ladder_10000oink-zlk2.75 ms295.00 µs9.31×10000 / 10000yes
ladder_10000spot2.75 ms9.56 ms0.29×10000 / 10000yes
ladder_50000oink-ppp22.96 ms2.33 ms9.88×50000 / 50000yes
ladder_50000oink-zlk22.96 ms2.48 ms9.24×50000 / 50000yes
ladder_50000spot22.96 ms85.64 ms0.27×50000 / 50000yes
random_few_10000oink-ppp7.48 ms1.44 ms5.21×10000 / 10000yes
random_few_10000oink-zlk7.48 ms2.57 ms2.91×10000 / 10000yes
random_few_10000spot7.48 ms21.57 ms0.35×10000 / 10000yes
random_few_50000oink-ppp76.82 ms15.11 ms5.08×50000 / 50000yes
random_few_50000oink-zlk76.82 ms21.96 ms3.50×50000 / 50000yes
random_few_50000spot76.82 ms678.40 ms0.11×50000 / 50000yes
random_many_10000oink-ppp6.94 ms1.52 ms4.57×10000 / 10000yes
random_many_10000oink-zlk6.94 ms2.66 ms2.61×10000 / 10000yes
random_many_10000spot6.94 ms30.68 ms0.23×10000 / 10000yes
random_many_50000oink-ppp70.64 ms29.45 ms2.40×50000 / 50000yes
random_many_50000oink-zlk70.64 ms36.45 ms1.94×50000 / 50000yes
random_many_50000spot70.64 ms650.20 ms0.11×50000 / 50000yes

Log

== head fc170083dd94822bcaee1413e5c523824d8a20a8: building ["scc", "ts", "runs", "dfa", "dpa", "storage", "nondeterministic", "learning", "game"] ["wallclock"]
   Compiling automata v0.2.1 (/var/lib/automata-bench/work/src-head)
    Finished `bench` profile [optimized] target(s) in 1m 55s
  Executable benches/dfa.rs (/var/lib/automata-bench/work/target-head/release/deps/dfa-239ee49a27fc4838)
  Executable benches/dpa.rs (/var/lib/automata-bench/work/target-head/release/deps/dpa-ee8d1549550eb250)
  Executable benches/game.rs (/var/lib/automata-bench/work/target-head/release/deps/game-ae02ba3f0e2bb10f)
  Executable benches/learning.rs (/var/lib/automata-bench/work/target-head/release/deps/learning-b0862ee18af8325a)
  Executable benches/nondeterministic.rs (/var/lib/automata-bench/work/target-head/release/deps/nondeterministic-1f493dd18fd6ada5)
  Executable benches/runs.rs (/var/lib/automata-bench/work/target-head/release/deps/runs-94e3643e0035d2ac)
  Executable benches/scc.rs (/var/lib/automata-bench/work/target-head/release/deps/scc-960a9d86024978ff)
  Executable benches/storage.rs (/var/lib/automata-bench/work/target-head/release/deps/storage-3f2fde62ddd01f66)
  Executable benches/ts.rs (/var/lib/automata-bench/work/target-head/release/deps/ts-df55bed5e680b932)
  Executable benches/wallclock.rs (/var/lib/automata-bench/work/target-head/release/deps/wallclock-00d5b8c4e6931bbf)
== head: running scc
    Finished `bench` profile [optimized] target(s) in 0.23s
     Running benches/scc.rs (/var/lib/automata-bench/work/target-head/release/deps/scc-960a9d86024978ff)
gungraun_runner: Warn : The RUST_LOG environment variable to set the log level changed to GUNGRAUN_LOG
== head: running ts
    Finished `bench` profile [optimized] target(s) in 0.19s
     Running benches/ts.rs (/var/lib/automata-bench/work/target-head/release/deps/ts-df55bed5e680b932)
gungraun_runner: Warn : The RUST_LOG environment variable to set the log level changed to GUNGRAUN_LOG
== head: running runs
    Finished `bench` profile [optimized] target(s) in 0.23s
     Running benches/runs.rs (/var/lib/automata-bench/work/target-head/release/deps/runs-94e3643e0035d2ac)
gungraun_runner: Warn : The RUST_LOG environment variable to set the log level changed to GUNGRAUN_LOG
== head: running dfa
    Finished `bench` profile [optimized] target(s) in 0.20s
     Running benches/dfa.rs (/var/lib/automata-bench/work/target-head/release/deps/dfa-239ee49a27fc4838)
gungraun_runner: Warn : The RUST_LOG environment variable to set the log level changed to GUNGRAUN_LOG
== head: running dpa
    Finished `bench` profile [optimized] target(s) in 0.20s
     Running benches/dpa.rs (/var/lib/automata-bench/work/target-head/release/deps/dpa-ee8d1549550eb250)
gungraun_runner: Warn : The RUST_LOG environment variable to set the log level changed to GUNGRAUN_LOG
== head: running storage
    Finished `bench` profile [optimized] target(s) in 0.19s
     Running benches/storage.rs (/var/lib/automata-bench/work/target-head/release/deps/storage-3f2fde62ddd01f66)
gungraun_runner: Warn : The RUST_LOG environment variable to set the log level changed to GUNGRAUN_LOG
== head: running nondeterministic
    Finished `bench` profile [optimized] target(s) in 0.20s
     Running benches/nondeterministic.rs (/var/lib/automata-bench/work/target-head/release/deps/nondeterministic-1f493dd18fd6ada5)
gungraun_runner: Warn : The RUST_LOG environment variable to set the log level changed to GUNGRAUN_LOG
== head: running learning
    Finished `bench` profile [optimized] target(s) in 0.18s
     Running benches/learning.rs (/var/lib/automata-bench/work/target-head/release/deps/learning-b0862ee18af8325a)
gungraun_runner: Warn : The RUST_LOG environment variable to set the log level changed to GUNGRAUN_LOG
== head: running game
    Finished `bench` profile [optimized] target(s) in 0.18s
     Running benches/game.rs (/var/lib/automata-bench/work/target-head/release/deps/game-ae02ba3f0e2bb10f)
gungraun_runner: Warn : The RUST_LOG environment variable to set the log level changed to GUNGRAUN_LOG
== head: running wallclock (wall clock)
    Finished `bench` profile [optimized] target(s) in 0.20s
     Running benches/wallclock.rs (/var/lib/automata-bench/work/target-head/release/deps/wallclock-00d5b8c4e6931bbf)
Gnuplot not found, using plotters backend
Benchmarking wallclock/scc/tarjan/scrambled_10000
Benchmarking wallclock/scc/tarjan/scrambled_10000: Analyzing
Benchmarking wallclock/dpa/normalized/scrambled_4000
Benchmarking wallclock/dpa/normalized/scrambled_4000: Analyzing
Benchmarking wallclock/dpa/complement/scrambled_4000
Benchmarking wallclock/dpa/complement/scrambled_4000: Analyzing
Benchmarking wallclock/dfa/minimize/redundant_4000
Benchmarking wallclock/dfa/minimize/redundant_4000: Analyzing
Benchmarking wallclock/dfa/accepts/word_100000
Benchmarking wallclock/dfa/accepts/word_100000: Analyzing
Benchmarking wallclock/nfa/subset_construction/nth_from_end_12
Benchmarking wallclock/nfa/subset_construction/nth_from_end_12: Analyzing
Benchmarking wallclock/nfa/determinize/nth_from_end_12
Benchmarking wallclock/nfa/determinize/nth_from_end_12: Analyzing
Benchmarking wallclock/hoa/parse/ltl
Benchmarking wallclock/hoa/parse/ltl: Analyzing
Benchmarking collect/clone/100000
Benchmarking collect/clone/100000: Analyzing
Benchmarking collect/collect_owned/100000
Benchmarking collect/collect_owned/100000: Analyzing
Benchmarking collect/collect_ref/100000
Benchmarking collect/collect_ref/100000: Analyzing
Benchmarking collect/map_edge_colors_collect_owned/100000
Benchmarking collect/map_edge_colors_collect_owned/100000: Analyzing
Benchmarking collect/clone/1000000
Benchmarking collect/clone/1000000: Analyzing
Benchmarking collect/collect_owned/1000000
Benchmarking collect/collect_owned/1000000: Analyzing
Benchmarking collect/collect_ref/1000000
Benchmarking collect/collect_ref/1000000: Analyzing
Benchmarking collect/map_edge_colors_collect_owned/1000000
Benchmarking collect/map_edge_colors_collect_owned/1000000: Analyzing
== head: building the Python bindings
🍹 Building a mixed python/rust project
🔗 Found pyo3 bindings with abi3 support
🐍 Found CPython 3.13 at /nix/store/vilynzly1pyhawy04ljmrp7n9ffr24qy-python3-3.13.17/bin/python3
📡 Using build options features from pyproject.toml
   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 1m 50s
📦 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.310 ms / 0.153 ms
dpa/equivalence/hard/l-nba-2 vs spot: 0.132 ms / 0.035 ms
dpa/equivalence/hard/m-nba-3 vs spot: 0.553 ms / 0.132 ms
dpa/equivalence/ltl/and-gf-3 vs spot: 0.017 ms / 0.011 ms
dpa/equivalence/ltl/eh-patterns-0 vs spot: 0.053 ms / 0.019 ms
dpa/equivalence/ltl/gf-equiv-3 vs spot: 0.039 ms / 0.033 ms
dpa/equivalence/ltl/gf-implies-3 vs spot: 0.019 ms / 0.018 ms
dpa/equivalence/ltl/gh-q-3 vs spot: 0.109 ms / 0.028 ms
dpa/equivalence/ltl/gh-r-3 vs spot: 0.053 ms / 0.067 ms
dpa/equivalence/ltl/go-theta-3 vs spot: 0.022 ms / 0.020 ms
dpa/equivalence/ltl/lily-patterns-1 vs spot: 0.026 ms / 0.015 ms
dpa/equivalence/ltl/ms-phi-r-1 vs spot: 0.023 ms / 0.037 ms
dpa/equivalence/ltl/ms-phi-s-1 vs spot: 0.023 ms / 0.039 ms
dpa/equivalence/ltl/rv-counter-3 vs spot: 0.047 ms / 0.012 ms
dpa/equivalence/ltl/sb-patterns-0 vs spot: 0.021 ms / 0.013 ms
dpa/equivalence/ltl/sejk-k-2 vs spot: 0.033 ms / 0.057 ms
dpa/equivalence/ltl/tv-uu-3 vs spot: 0.155 ms / 0.037 ms
dpa/equivalence/ltl/u-left-3 vs spot: 0.018 ms / 0.008 ms
dpa/equivalence/random/n128-a2-p6-s1 vs spot: 0.860 ms / 0.202 ms
dpa/equivalence/random/n16-a1-p3-s1 vs spot: 0.036 ms / 0.015 ms
dpa/equivalence/random/n256-a2-p8-s1 vs spot: 2.650 ms / 0.461 ms
dpa/equivalence/random/n64-a2-p4-s1 vs spot: 0.375 ms / 0.096 ms
dpa/inclusion/hard/l-dsa-3 vs spot: 0.141 ms / 0.059 ms
dpa/inclusion/hard/l-nba-2 vs spot: 0.063 ms / 0.021 ms
dpa/inclusion/hard/m-nba-3 vs spot: 0.268 ms / 0.081 ms
dpa/inclusion/ltl/and-gf-3 vs spot: 0.008 ms / 0.007 ms
dpa/inclusion/ltl/eh-patterns-0 vs spot: 0.027 ms / 0.016 ms
dpa/inclusion/ltl/gf-equiv-3 vs spot: 0.020 ms / 0.018 ms
dpa/inclusion/ltl/gf-implies-3 vs spot: 0.010 ms / 0.010 ms
dpa/inclusion/ltl/gh-q-3 vs spot: 0.054 ms / 0.026 ms
dpa/inclusion/ltl/gh-r-3 vs spot: 0.026 ms / 0.033 ms
dpa/inclusion/ltl/go-theta-3 vs spot: 0.011 ms / 0.015 ms
dpa/inclusion/ltl/lily-patterns-1 vs spot: 0.014 ms / 0.012 ms
dpa/inclusion/ltl/ms-phi-r-1 vs spot: 0.012 ms / 0.018 ms
dpa/inclusion/ltl/ms-phi-s-1 vs spot: 0.012 ms / 0.023 ms
dpa/inclusion/ltl/rv-counter-3 vs spot: 0.024 ms / 0.013 ms
dpa/inclusion/ltl/sb-patterns-0 vs spot: 0.011 ms / 0.011 ms
dpa/inclusion/ltl/sejk-k-2 vs spot: 0.017 ms / 0.027 ms
dpa/inclusion/ltl/tv-uu-3 vs spot: 0.076 ms / 0.028 ms
dpa/inclusion/ltl/u-left-3 vs spot: 0.009 ms / 0.008 ms
dpa/inclusion/random/n128-a2-p6-s1 vs spot: 0.430 ms / 0.124 ms
dpa/inclusion/random/n16-a1-p3-s1 vs spot: 0.017 ms / 0.009 ms
dpa/inclusion/random/n256-a2-p8-s1 vs spot: 1.304 ms / 0.286 ms
dpa/inclusion/random/n64-a2-p4-s1 vs spot: 0.181 ms / 0.059 ms
game/solve/random_few_10000 vs spot: 7.481 ms / 21.571 ms
game/solve/random_few_10000 vs oink-zlk: 7.481 ms / 2.569 ms
game/solve/random_few_10000 vs oink-ppp: 7.481 ms / 1.435 ms
game/solve/random_few_50000 vs spot: 76.816 ms / 678.397 ms
game/solve/random_few_50000 vs oink-zlk: 76.816 ms / 21.962 ms
game/solve/random_few_50000 vs oink-ppp: 76.816 ms / 15.112 ms
game/solve/random_many_10000 vs spot: 6.936 ms / 30.680 ms
game/solve/random_many_10000 vs oink-zlk: 6.936 ms / 2.662 ms
game/solve/random_many_10000 vs oink-ppp: 6.936 ms / 1.518 ms
game/solve/random_many_50000 vs spot: 70.642 ms / 650.203 ms
game/solve/random_many_50000 vs oink-zlk: 70.642 ms / 36.452 ms
game/solve/random_many_50000 vs oink-ppp: 70.642 ms / 29.449 ms
game/solve/ladder_10000 vs spot: 2.747 ms / 9.562 ms
game/solve/ladder_10000 vs oink-zlk: 2.747 ms / 0.295 ms
game/solve/ladder_10000 vs oink-ppp: 2.747 ms / 0.295 ms
game/solve/ladder_50000 vs spot: 22.962 ms / 85.639 ms
game/solve/ladder_50000 vs oink-zlk: 22.962 ms / 2.484 ms
game/solve/ladder_50000 vs oink-ppp: 22.962 ms / 2.325 ms
== head: 253 benchmarks, 16 wall-clock measurements, 62 comparisons