History · Versus Spot and Oink
Benchmarks: fixtures with many atomic propositions (#156, PR A) (#160)
status done · queued 2026-11-09 23:53 · started 2026-11-09 23:53 · finished 2026-11-10 00:04
· · rustc 1.95.0 (59807616e 2026-04-14) (built from a source tarball) · valgrind-3.26.0 · pinned to cpu 1
| benchmark | instructions | est. cycles | L1 hits | LL hits | RAM hits | heap bytes | allocations |
|---|---|---|---|---|---|---|---|
| dfa::dfa::accepts_many_words::scrambled_1000 | 343 072 | 435 476 | 428 941 | 1 223 | 12 | 0 | 0 |
| dfa::dfa::complement::scrambled_1000 | 366 068 | 584 230 | 566 335 | 3 397 | 26 | 139 104 | 19 |
| dfa::dfa::complement::scrambled_4000 | 1 435 873 | 2 309 085 | 2 223 225 | 16 997 | 25 | 556 896 | 23 |
| dfa::dfa::equivalent::deep_difference_100 | 61 667 | 97 664 | 90 479 | 44 | 199 | 16 196 | 25 |
| dfa::dfa::equivalent::deep_difference_400 | 212 158 | 336 646 | 314 201 | 1 850 | 377 | 65 364 | 33 |
| dfa::dfa::equivalent::different_100 | 9 047 | 15 371 | 12 571 | 7 | 79 | 1 804 | 12 |
| dfa::dfa::equivalent::different_400 | 9 088 | 15 572 | 12 527 | 77 | 76 | 1 804 | 12 |
| dfa::dfa::equivalent::minimized_100 | 35 849 | 54 445 | 51 890 | 105 | 58 | 7 756 | 17 |
| dfa::dfa::equivalent::minimized_400 | 120 587 | 182 449 | 176 699 | 723 | 61 | 31 580 | 23 |
| dfa::dfa::give_word::empty_1000 | 1 872 613 | 2 558 733 | 2 531 028 | 4 925 | 88 | 152 864 | 3 738 |
| dfa::dfa::give_word::empty_4000 | 6 930 823 | 9 657 081 | 9 554 286 | 20 055 | 72 | 679 808 | 15 828 |
| dfa::dfa::give_word::far_1000 | 164 342 | 231 691 | 227 031 | 547 | 55 | 28 176 | 394 |
| dfa::dfa::give_word::far_4000 | 946 982 | 1 329 498 | 1 307 388 | 3 925 | 71 | 148 464 | 2 233 |
| dfa::dfa::intersection::scrambled_100 | 3 719 727 | 5 957 618 | 5 779 013 | 12 068 | 3 379 | 428 088 | 42 |
| dfa::dfa::intersection::scrambled_200 | 14 824 891 | 24 130 022 | 22 990 727 | 97 309 | 18 650 | 1 708 120 | 49 |
| dfa::dfa::intersection_is_empty::empty_100 | 59 266 | 94 073 | 87 373 | 31 | 187 | 15 700 | 20 |
| dfa::dfa::intersection_is_empty::empty_200 | 109 269 | 175 052 | 161 727 | 614 | 293 | 31 580 | 23 |
| dfa::dfa::is_empty_language::empty_1000 | 1 872 615 | 2 558 737 | 2 531 032 | 4 925 | 88 | 152 864 | 3 738 |
| dfa::dfa::is_empty_language::empty_4000 | 6 930 825 | 9 657 051 | 9 554 291 | 20 055 | 71 | 679 808 | 15 828 |
| dfa::dfa::minimize::minimal_1000 | 3 435 734 | 5 203 571 | 4 825 981 | 39 755 | 5 109 | 1 135 492 | 2 214 |
| dfa::dfa::minimize::minimal_4000 | 13 412 368 | 20 482 391 | 18 822 711 | 204 599 | 18 191 | 4 543 724 | 8 254 |
| dfa::dfa::minimize::redundant_1000 | 2 284 641 | 3 452 669 | 3 214 859 | 25 911 | 3 093 | 760 780 | 1 201 |
| dfa::dfa::minimize::redundant_4000 | 8 836 896 | 13 488 247 | 12 428 632 | 143 666 | 9 751 | 3 044 900 | 4 241 |
| dfa::dfa::minimize::scrambled_1000 | 3 647 926 | 5 556 041 | 5 121 111 | 51 111 | 5 125 | 1 116 052 | 2 217 |
| dfa::dfa::minimize::scrambled_4000 | 14 161 227 | 21 944 449 | 19 835 394 | 294 152 | 18 237 | 4 470 140 | 8 261 |
| dfa::dfa::minimize_moore_with_edge_colors::scrambled_1000 | 3 646 936 | 5 548 736 | 5 119 146 | 50 092 | 5 118 | 1 116 052 | 2 217 |
| dfa::dfa::minimize_moore_with_edge_colors::scrambled_4000 | 14 149 845 | 21 911 331 | 19 806 826 | 300 634 | 17 181 | 4 470 140 | 8 261 |
| dfa::dfa::union::scrambled_100 | 3 719 712 | 5 957 566 | 5 778 976 | 12 079 | 3 377 | 428 088 | 42 |
| dfa::dfa::union::scrambled_200 | 14 824 876 | 24 129 922 | 22 990 717 | 97 291 | 18 650 | 1 708 120 | 49 |
| dpa::dpa::accepted_word::chain_100 | 112 530 | 172 038 | 159 793 | 62 | 341 | – | – |
| dpa::dpa::accepted_word::chain_400 | 379 899 | 573 673 | 538 958 | 2 974 | 567 | – | – |
| dpa::dpa::accepted_word::scrambled_100 | 144 738 | 217 060 | 204 265 | 46 | 359 | – | – |
| dpa::dpa::accepted_word::scrambled_400 | 493 406 | 730 290 | 696 750 | 2 823 | 555 | – | – |
| dpa::dpa::collect_dpa::scrambled_1000 | 301 647 | 500 484 | 481 289 | 3 804 | 5 | – | – |
| dpa::dpa::collect_dpa::scrambled_4000 | 1 177 040 | 2 005 925 | 1 882 255 | 16 404 | 1 190 | – | – |
| dpa::dpa::complement::chain_1000 | 4 108 584 | 6 261 259 | 5 757 844 | 55 190 | 6 499 | – | – |
| dpa::dpa::complement::chain_4000 | 16 700 093 | 25 593 463 | 23 352 178 | 261 959 | 26 614 | – | – |
| dpa::dpa::complement::scrambled_1000 | 4 971 453 | 7 468 012 | 6 921 107 | 62 887 | 6 642 | – | – |
| dpa::dpa::complement::scrambled_4000 | 20 090 469 | 30 567 039 | 27 901 194 | 344 365 | 26 972 | – | – |
| dpa::dpa::complement_fixtures::ltl | 1 500 432 | 2 171 176 | 2 115 541 | 6 528 | 657 | – | – |
| dpa::dpa::complement_fixtures::many_aps | 128 792 342 | 173 017 509 | 172 361 199 | 127 146 | 588 | – | – |
| dpa::dpa::complement_fixtures::synthetic | 9 444 899 | 13 499 056 | 12 952 021 | 105 102 | 615 | – | – |
| dpa::dpa::complement_without_normalizing::scrambled_1000 | 574 449 | 836 894 | 807 794 | 5 183 | 91 | – | – |
| dpa::dpa::complement_without_normalizing::scrambled_4000 | 2 259 853 | 3 331 131 | 3 176 576 | 21 979 | 1 276 | – | – |
| dpa::dpa::equivalent_fixtures::many_aps | 94 848 718 | 126 854 456 | 126 243 651 | 119 214 | 421 | – | – |
| dpa::dpa::hoa_parse::ltl | 10 979 634 | 15 945 613 | 15 496 793 | 68 428 | 3 048 | – | – |
| dpa::dpa::hoa_parse::many_aps | 270 019 542 | 368 922 221 | 367 397 221 | 191 558 | 16 206 | – | – |
| dpa::dpa::hoa_parse::synthetic | 40 738 329 | 59 603 682 | 57 993 437 | 251 867 | 10 026 | – | – |
| dpa::dpa::hoa_print::ltl | 49 107 216 | 67 193 972 | 66 562 417 | 122 489 | 546 | – | – |
| dpa::dpa::hoa_print::many_aps | 753 714 860 | 1 018 965 253 | 1 017 570 603 | 275 122 | 544 | – | – |
| dpa::dpa::hoa_print::synthetic | 143 208 859 | 197 422 360 | 194 336 435 | 613 454 | 533 | – | – |
| dpa::dpa::included_fixtures::many_aps | 92 011 612 | 122 808 738 | 122 339 943 | 90 777 | 426 | – | – |
| dpa::dpa::included_in::complement_100 | 269 290 | 408 186 | 389 346 | 856 | 416 | – | – |
| dpa::dpa::included_in::complement_25 | 87 716 | 139 297 | 124 952 | 90 | 397 | – | – |
| dpa::dpa::included_in::complement_50 | 150 987 | 231 660 | 216 495 | 303 | 390 | – | – |
| dpa::dpa::included_in::normalized_100 | 541 195 | 797 974 | 769 904 | 1 617 | 571 | – | – |
| dpa::dpa::included_in::normalized_25 | 184 110 | 274 382 | 259 927 | 322 | 367 | – | – |
| dpa::dpa::included_in::normalized_50 | 312 439 | 459 812 | 442 892 | 521 | 409 | – | – |
| dpa::dpa::language_equivalent::complement_100 | 278 865 | 420 208 | 401 288 | 858 | 418 | – | – |
| dpa::dpa::language_equivalent::complement_25 | 90 241 | 142 689 | 128 184 | 101 | 400 | – | – |
| dpa::dpa::language_equivalent::complement_50 | 155 862 | 237 938 | 222 653 | 313 | 392 | – | – |
| dpa::dpa::language_equivalent::normalized_100 | 989 905 | 1 436 210 | 1 399 255 | 2 638 | 679 | – | – |
| dpa::dpa::language_equivalent::normalized_25 | 325 469 | 474 570 | 458 005 | 422 | 413 | – | – |
| dpa::dpa::language_equivalent::normalized_50 | 579 273 | 835 436 | 816 396 | 728 | 440 | – | – |
| dpa::dpa::map_edge_colors_collect::scrambled_1000 | 307 253 | 507 028 | 486 993 | 3 888 | 17 | – | – |
| dpa::dpa::map_edge_colors_collect::scrambled_4000 | 1 197 646 | 2 030 249 | 1 902 264 | 17 183 | 1 202 | – | – |
| dpa::dpa::normalized::chain_1000 | 3 836 030 | 5 918 731 | 5 428 296 | 52 958 | 6 447 | – | – |
| dpa::dpa::normalized::chain_4000 | 15 611 539 | 24 231 771 | 22 036 141 | 253 220 | 26 558 | – | – |
| dpa::dpa::normalized::scrambled_1000 | 4 698 701 | 7 125 107 | 6 591 237 | 60 644 | 6 590 | – | – |
| dpa::dpa::normalized::scrambled_4000 | 19 001 717 | 29 205 542 | 26 584 692 | 335 758 | 26 916 | – | – |
| dpa::dpa::normalized::scrambled_k4_1000 | 25 720 479 | 36 579 268 | 34 425 133 | 379 790 | 7 291 | – | – |
| dpa::dpa::normalized_fixtures::ltl | 1 409 455 | 2 044 262 | 1 998 172 | 5 340 | 554 | – | – |
| dpa::dpa::normalized_fixtures::many_aps | 129 810 449 | 174 473 178 | 173 829 593 | 125 875 | 406 | – | – |
| dpa::dpa::normalized_fixtures::synthetic | 9 128 777 | 13 095 797 | 12 571 462 | 100 877 | 570 | – | – |
| dpa::dpa::prefix_partition::chain_16 | 3 310 414 | 5 029 274 | 4 961 039 | 1 978 | 1 667 | – | – |
| dpa::dpa::prefix_partition::chain_8 | 853 868 | 1 309 452 | 1 277 922 | 412 | 842 | – | – |
| dpa::dpa::prefix_partition::scrambled_16 | 3 700 115 | 5 664 996 | 5 575 456 | 4 069 | 1 977 | – | – |
| dpa::dpa::prefix_partition::scrambled_8 | 1 019 221 | 1 559 922 | 1 527 042 | 570 | 858 | – | – |
| dpa::dpa::rejected_word::chain_100 | 937 946 | 1 371 684 | 1 328 379 | 2 963 | 814 | – | – |
| dpa::dpa::rejected_word::chain_400 | 3 643 601 | 5 469 766 | 5 168 516 | 48 098 | 1 736 | – | – |
| dpa::dpa::rejected_word::scrambled_100 | 247 652 | 384 336 | 350 301 | 528 | 897 | – | – |
| dpa::dpa::rejected_word::scrambled_400 | 934 686 | 1 437 870 | 1 324 060 | 10 232 | 1 790 | – | – |
| dpa::dpa::sccs::chain_1000 | 487 826 | 762 432 | 686 827 | 6 847 | 1 182 | – | – |
| dpa::dpa::sccs::chain_4000 | 1 876 539 | 2 968 389 | 2 642 264 | 29 910 | 5 045 | – | – |
| dpa::dpa::sccs::scrambled_1000 | 554 783 | 860 514 | 784 169 | 8 241 | 1 004 | – | – |
| dpa::dpa::sccs::scrambled_4000 | 2 205 409 | 3 495 960 | 3 116 685 | 46 294 | 4 223 | – | – |
| dpa::dpa::witness_colors::chain_100 | 4 743 878 | 6 717 395 | 6 594 760 | 8 903 | 2 232 | – | – |
| dpa::dpa::witness_colors::chain_400 | 46 530 825 | 65 834 988 | 64 234 348 | 193 981 | 18 021 | – | – |
| dpa::dpa::witness_colors::scrambled_100 | 4 128 722 | 5 851 268 | 5 756 118 | 9 321 | 1 387 | – | – |
| dpa::dpa::witness_colors::scrambled_400 | 31 854 846 | 45 091 478 | 44 267 468 | 145 888 | 2 702 | – | – |
| dpa::dpa::witness_inequivalence::complement_100 | 278 864 | 420 219 | 401 284 | 861 | 418 | – | – |
| dpa::dpa::witness_inequivalence::complement_25 | 90 240 | 142 672 | 128 187 | 97 | 400 | – | – |
| dpa::dpa::witness_inequivalence::complement_50 | 155 861 | 237 941 | 222 651 | 314 | 392 | – | – |
| dpa::dpa::witness_not_subset_of::complement_100 | 269 289 | 408 113 | 389 348 | 855 | 414 | – | – |
| dpa::dpa::witness_not_subset_of::complement_25 | 87 715 | 139 262 | 124 952 | 90 | 396 | – | – |
| dpa::dpa::witness_not_subset_of::complement_50 | 150 986 | 231 633 | 216 493 | 305 | 389 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_100 | 541 194 | 797 935 | 769 905 | 1 616 | 570 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_25 | 184 109 | 274 339 | 259 929 | 320 | 366 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_50 | 312 438 | 459 815 | 442 890 | 522 | 409 | – | – |
| dpa::dpa::witnesses_fixtures::ltl | 2 245 906 | 3 223 686 | 3 156 716 | 7 500 | 842 | – | – |
| dpa::dpa::witnesses_fixtures::synthetic | 19 746 177 | 30 076 839 | 29 470 064 | 115 216 | 877 | – | – |
| game::game::tangle_learning::few_priorities_1000 | 2 681 174 | 4 034 006 | 3 684 531 | 35 924 | 4 853 | 745 400 | 1 292 |
| game::game::tangle_learning::few_priorities_4000 | 8 074 126 | 12 626 420 | 11 018 890 | 194 967 | 18 077 | 2 407 416 | 3 266 |
| game::game::tangle_learning::ladder_1000 | 1 178 814 | 1 829 612 | 1 626 132 | 12 444 | 4 036 | 377 868 | 118 |
| game::game::tangle_learning::ladder_4000 | 4 406 583 | 7 080 776 | 6 015 791 | 110 853 | 14 592 | 1 511 668 | 225 |
| game::game::tangle_learning::many_priorities_1000 | 2 009 444 | 3 025 858 | 2 742 663 | 25 545 | 4 442 | 566 440 | 848 |
| game::game::tangle_learning::many_priorities_4000 | 6 730 562 | 10 478 352 | 9 098 317 | 166 240 | 15 681 | 2 187 344 | 1 620 |
| game::game::tangle_learning_min_odd::few_priorities_1000 | 1 520 401 | 2 316 121 | 2 075 526 | 26 356 | 3 109 | 525 072 | 189 |
| game::game::tangle_learning_min_odd::few_priorities_4000 | 7 998 151 | 12 324 147 | 10 820 237 | 215 970 | 12 116 | 2 560 064 | 1 933 |
| game::game::zielonka::few_priorities_1000 | 1 126 202 | 1 709 195 | 1 520 525 | 12 464 | 3 610 | 356 676 | 95 |
| game::game::zielonka::few_priorities_4000 | 3 470 257 | 5 583 743 | 4 684 113 | 81 695 | 14 033 | 1 278 564 | 84 |
| game::game::zielonka::ladder_1000 | 5 134 284 | 7 016 179 | 6 609 659 | 50 098 | 4 458 | 499 404 | 182 |
| game::game::zielonka::ladder_4000 | 19 816 376 | 27 232 087 | 25 422 837 | 246 147 | 16 529 | 1 998 868 | 212 |
| game::game::zielonka::many_priorities_1000 | 4 103 437 | 5 602 145 | 5 264 315 | 38 698 | 4 124 | 764 940 | 339 |
| game::game::zielonka::many_priorities_4000 | 12 909 791 | 17 933 444 | 16 554 599 | 176 138 | 14 233 | 2 552 644 | 288 |
| game::game::zielonka_min_odd::few_priorities_1000 | 2 139 059 | 3 023 273 | 2 800 568 | 23 758 | 2 969 | 512 012 | 195 |
| game::game::zielonka_min_odd::few_priorities_4000 | 6 302 064 | 9 279 623 | 8 309 198 | 131 043 | 9 006 | 1 705 700 | 158 |
| learning::learning::lstar_mealy::counting_16 | 1 787 091 | 2 435 591 | 2 389 896 | 711 | 1 204 | 154 504 | 2 633 |
| learning::learning::lstar_mealy::counting_8 | 478 063 | 679 813 | 646 498 | 223 | 920 | 40 472 | 862 |
| learning::learning::sprout_parity::inf_ab_100 | 1 272 775 | 1 856 353 | 1 793 428 | 2 239 | 1 478 | 200 416 | 1 872 |
| learning::learning::sprout_parity::inf_ab_400 | 2 614 105 | 3 794 564 | 3 677 669 | 9 316 | 2 009 | 405 040 | 3 649 |
| nondeterministic::nondeterministic::fixture_accepts::ltl | 822 089 | 1 281 766 | 1 217 831 | 8 363 | 632 | – | – |
| nondeterministic::nondeterministic::nba_accepts::nba_400 | 125 268 484 | 185 045 746 | 174 141 016 | 1 657 444 | 74 786 | – | – |
| nondeterministic::nondeterministic::nba_witness::nba_4000 | 14 586 044 | 21 412 598 | 20 397 658 | 138 427 | 9 223 | – | – |
| nondeterministic::nondeterministic::nca_accepts::nca_400 | 266 215 466 | 395 064 980 | 369 412 615 | 4 559 287 | 81 598 | – | – |
| nondeterministic::nondeterministic::nca_witness::nca_4000 | 19 590 609 | 29 462 939 | 27 306 869 | 325 514 | 15 100 | – | – |
| nondeterministic::nondeterministic::nma_witness::nma_1000 | 25 727 430 | 37 903 662 | 35 879 082 | 371 498 | 4 774 | – | – |
| nondeterministic::nondeterministic::npa_accepts::empty_npa_400 | 492 867 078 | 734 421 679 | 686 766 934 | 8 907 942 | 89 001 | – | – |
| nondeterministic::nondeterministic::npa_accepts::npa_100 | 30 410 458 | 44 530 786 | 42 655 071 | 286 348 | 12 685 | – | – |
| nondeterministic::nondeterministic::npa_accepts::npa_400 | 125 278 162 | 185 056 942 | 174 150 667 | 1 657 767 | 74 784 | – | – |
| nondeterministic::nondeterministic::npa_witness::empty_npa_1000 | 9 115 024 | 13 456 660 | 12 720 745 | 123 509 | 3 382 | – | – |
| nondeterministic::nondeterministic::npa_witness::empty_npa_4000 | 36 996 517 | 55 319 495 | 51 353 295 | 657 314 | 19 418 | – | – |
| nondeterministic::nondeterministic::npa_witness::npa_1000 | 2 471 053 | 3 673 923 | 3 507 448 | 20 751 | 1 792 | – | – |
| nondeterministic::nondeterministic::npa_witness::npa_4000 | 20 162 804 | 29 311 816 | 28 099 431 | 177 909 | 9 224 | – | – |
| nondeterministic::nondeterministic::nra_witness::nra_4000 | 20 617 679 | 31 391 269 | 28 841 099 | 337 190 | 24 692 | – | – |
| runs::runs::dfa_accepts_many_words::count_1000 | 4 303 213 | 5 381 961 | 5 357 646 | 4 793 | 10 | 0 | 0 |
| runs::runs::dfa_accepts_one_word::len_100 | 3 492 | 4 798 | 4 398 | 38 | 6 | 0 | 0 |
| runs::runs::dfa_accepts_one_word::len_10000 | 266 070 | 329 527 | 325 827 | 698 | 6 | 0 | 0 |
| runs::runs::dfa_accepts_one_word::len_100000 | 2 650 731 | 3 276 825 | 3 244 710 | 6 325 | 14 | 0 | 0 |
| runs::runs::dfa_reached_state::count_1000 | 3 570 211 | 4 404 958 | 4 380 643 | 4 793 | 10 | 0 | 0 |
| runs::runs::dpa_accepts_lassos::long | 9 150 745 | 11 671 385 | 11 646 565 | 3 144 | 260 | 724 664 | 500 |
| runs::runs::dpa_accepts_lassos::short | 406 490 | 540 876 | 535 586 | 372 | 98 | 26 236 | 472 |
| runs::runs::dpa_recurrent_edge_colors::long | 14 635 826 | 18 270 109 | 18 215 504 | 6 455 | 638 | 922 144 | 2 090 |
| runs::runs::dpa_recurrent_edge_colors::short | 1 098 107 | 1 482 488 | 1 469 253 | 1 590 | 151 | 168 684 | 1 708 |
| runs::runs::dpa_recurrent_states::long | 11 749 193 | 15 694 629 | 15 662 694 | 3 944 | 349 | 788 104 | 860 |
| runs::runs::dpa_recurrent_states::short | 589 492 | 792 388 | 783 933 | 788 | 129 | 81 996 | 782 |
| runs::runs::dpa_visited_sequences::long | 8 738 263 | 12 087 726 | 12 050 581 | 5 063 | 338 | 2 190 780 | 850 |
| runs::runs::dpa_visited_sequences::short | 370 678 | 511 671 | 506 161 | 626 | 68 | 29 986 | 545 |
| runs::runs::fixture_accepts_lassos::ltl | 9 167 918 | 13 375 750 | 13 349 280 | 4 426 | 124 | – | – |
| runs::runs::fixture_accepts_lassos::synthetic | 4 648 858 | 6 847 540 | 6 775 700 | 13 458 | 130 | – | – |
| scc::scc::scc_queries::small_cycles_1000 | 906 614 | 1 433 125 | 1 272 020 | 9 422 | 3 257 | 261 132 | 559 |
| scc::scc::scc_queries::small_cycles_4000 | 3 548 843 | 5 657 963 | 4 973 843 | 50 913 | 12 273 | 1 045 396 | 2 071 |
| scc::scc::tarjan::back_edges_1000 | 512 037 | 837 644 | 726 699 | 5 473 | 2 388 | 170 272 | 45 |
| scc::scc::tarjan::back_edges_4000 | 1 987 551 | 3 267 055 | 2 821 295 | 26 453 | 8 957 | 680 632 | 53 |
| scc::scc::tarjan::binary_tree_1000 | 571 155 | 892 378 | 815 613 | 4 062 | 1 613 | 105 760 | 39 |
| scc::scc::tarjan::binary_tree_4000 | 2 290 383 | 3 582 150 | 3 276 315 | 21 127 | 5 720 | 419 512 | 45 |
| scc::scc::tarjan::fragmented_1000 | 658 467 | 1 046 449 | 922 644 | 9 648 | 2 159 | 146 084 | 121 |
| scc::scc::tarjan::fragmented_4000 | 2 534 039 | 4 125 428 | 3 544 563 | 62 791 | 7 626 | 569 852 | 167 |
| scc::scc::tarjan::grid_1024 | 596 018 | 971 686 | 847 681 | 7 728 | 2 439 | 171 160 | 45 |
| scc::scc::tarjan::grid_4096 | 2 378 408 | 4 000 906 | 3 363 601 | 63 670 | 9 113 | 684 184 | 53 |
| scc::scc::tarjan::path_1000 | 1 929 057 | 3 028 158 | 2 729 488 | 23 187 | 5 221 | 455 224 | 2 064 |
| scc::scc::tarjan::path_4000 | 7 632 832 | 12 001 283 | 10 804 663 | 98 323 | 20 143 | 1 821 536 | 8 076 |
| scc::scc::tarjan::ring_1000 | 512 037 | 841 284 | 725 789 | 6 383 | 2 388 | 170 272 | 45 |
| scc::scc::tarjan::ring_4000 | 1 987 551 | 3 284 299 | 2 816 984 | 30 764 | 8 957 | 680 632 | 53 |
| scc::scc::tarjan::scrambled_1000 | 578 994 | 936 142 | 823 952 | 6 954 | 2 212 | 170 272 | 45 |
| scc::scc::tarjan::scrambled_4000 | 2 316 421 | 3 790 800 | 3 296 680 | 41 872 | 8 136 | 680 632 | 53 |
| scc::scc::tarjan::small_cycles_1000 | 905 596 | 1 431 774 | 1 270 734 | 9 430 | 3 254 | 261 132 | 559 |
| scc::scc::tarjan::small_cycles_4000 | 3 544 825 | 5 650 350 | 4 969 435 | 50 293 | 12 270 | 1 045 396 | 2 071 |
| scc::scc::tarjan_from::fragmented_1000 | 242 363 | 394 053 | 344 648 | 2 524 | 1 051 | 74 985 | 64 |
| scc::scc::tarjan_from::fragmented_4000 | 907 553 | 1 491 771 | 1 296 376 | 15 923 | 3 308 | 299 625 | 78 |
| scc::scc::tarjan_from::path_1000 | 1 920 970 | 3 017 737 | 2 721 882 | 23 037 | 5 162 | 468 993 | 2 091 |
| scc::scc::tarjan_from::path_4000 | 7 545 354 | 11 928 152 | 10 697 327 | 106 732 | 19 919 | 1 876 753 | 8 109 |
| scc::scc::tarjan_from::ring_1000 | 503 457 | 836 369 | 717 714 | 6 252 | 2 497 | 184 041 | 72 |
| scc::scc::tarjan_from::scrambled_1000 | 570 414 | 929 847 | 816 222 | 6 478 | 2 321 | 184 041 | 72 |
| storage::storage::add_edges_dense::k2_5000 | 1 356 401 | 2 030 656 | 1 985 341 | 4 940 | 589 | 180 200 | 37 |
| storage::storage::add_edges_dense::k8_5000 | 4 247 059 | 6 412 074 | 6 225 389 | 17 835 | 2 786 | 671 728 | 40 |
| storage::storage::add_edges_linked::k2_5000 | 1 402 670 | 2 420 477 | 2 258 382 | 14 226 | 2 599 | 1 113 960 | 26 |
| storage::storage::add_edges_linked::k8_5000 | 6 669 284 | 11 260 261 | 10 330 811 | 75 815 | 15 725 | 3 866 496 | 28 |
| storage::storage::clone_csr::k2_10000 | 30 590 | 183 480 | 52 625 | 4 170 | 3 143 | 230 012 | 6 |
| storage::storage::clone_dense::k2_10000 | 15 113 | 81 334 | 25 804 | 2 251 | 1 265 | 110 008 | 4 |
| storage::storage::clone_linked::k2_10000 | 370 822 | 901 735 | 529 795 | 12 466 | 8 846 | 680 008 | 3 |
| storage::storage::complete_dense::partial_5000 | 155 627 | 209 425 | 202 330 | 908 | 73 | 136 | 4 |
| storage::storage::complete_linked::partial_5000 | 1 210 854 | 1 718 705 | 1 629 455 | 6 951 | 1 557 | 65 672 | 18 |
| storage::storage::edges_from_all_states_csr::k2_2000 | 72 047 | 77 214 | 75 859 | 222 | 7 | 0 | 0 |
| storage::storage::edges_from_all_states_csr::k8_2000 | 108 047 | 116 392 | 111 072 | 1 008 | 8 | 0 | 0 |
| storage::storage::edges_from_all_states_dense::k2_2000 | 102 043 | 119 287 | 117 842 | 233 | 8 | 0 | 0 |
| storage::storage::edges_from_all_states_dense::k8_2000 | 140 043 | 160 563 | 155 038 | 1 035 | 10 | 0 | 0 |
| storage::storage::edges_from_all_states_linked::k2_2000 | 68 033 | 86 725 | 75 925 | 2 132 | 4 | 0 | 0 |
| storage::storage::edges_from_all_states_linked::k8_2000 | 152 033 | 203 735 | 166 680 | 7 376 | 5 | 0 | 0 |
| storage::storage::minimize_csr::redundant_2000 | 4 617 582 | 6 940 505 | 6 457 910 | 57 886 | 5 519 | 1 505 420 | 2 212 |
| storage::storage::minimize_csr::redundant_8000 | 18 095 643 | 27 530 145 | 25 281 710 | 272 643 | 25 292 | 6 023 300 | 8 250 |
| storage::storage::minimize_dense::redundant_2000 | 4 660 736 | 6 970 940 | 6 512 975 | 58 140 | 4 779 | 1 522 156 | 2 221 |
| storage::storage::minimize_dense::redundant_8000 | 18 300 677 | 27 860 931 | 25 561 001 | 279 029 | 25 851 | 6 090 340 | 8 261 |
| storage::storage::minimize_linked::redundant_2000 | 4 488 864 | 6 856 453 | 6 304 653 | 61 927 | 6 919 | 1 522 156 | 2 221 |
| storage::storage::minimize_linked::redundant_8000 | 17 650 503 | 27 227 883 | 24 777 018 | 302 853 | 26 760 | 6 090 340 | 8 261 |
| storage::storage::overwrite_edges_dense::k2_5000 | 2 126 433 | 3 232 754 | 3 172 424 | 7 915 | 593 | 180 200 | 37 |
| storage::storage::overwrite_edges_linked::k2_5000 | 3 790 776 | 6 671 160 | 5 952 015 | 44 772 | 14 151 | 2 031 464 | 27 |
| storage::storage::predecessors_of_all_states_csr::k2_2000 | 102 046 | 121 042 | 117 407 | 678 | 7 | 0 | 0 |
| storage::storage::predecessors_of_all_states_dense::k2_2000 | 290 369 | 397 967 | 388 222 | 1 620 | 47 | 32 008 | 3 |
| storage::storage::predecessors_of_all_states_linked::k2_2000 | 68 033 | 91 695 | 74 690 | 3 366 | 5 | 0 | 0 |
| storage::storage::product_successor_csr::n200 | 64 096 | 75 545 | 75 160 | 14 | 9 | 0 | 0 |
| storage::storage::product_successor_dense::n200 | 73 087 | 94 654 | 94 104 | 40 | 10 | 0 | 0 |
| storage::storage::product_successor_linked::n200 | 46 547 | 60 187 | 57 012 | 579 | 8 | 0 | 0 |
| storage::storage::reachable_states_csr::k2_8000 | 1 101 115 | 1 630 076 | 1 591 846 | 7 415 | 33 | 17 368 | 11 |
| storage::storage::reachable_states_dense::k2_8000 | 1 133 699 | 1 684 539 | 1 639 244 | 8 828 | 33 | 17 368 | 11 |
| storage::storage::reachable_states_linked::k2_8000 | 924 279 | 1 485 635 | 1 386 520 | 19 522 | 43 | 17 368 | 11 |
| storage::storage::remove_state_dense::k2_10000 | 1 072 212 | 1 565 244 | 1 390 284 | 21 510 | 1 926 | 176 000 | 1 003 |
| storage::storage::remove_state_linked::k2_10000 | 1 094 012 | 1 531 445 | 1 492 735 | 7 420 | 46 | 80 000 | 3 000 |
| storage::storage::run_many_words_csr::count_1000 | 551 036 | 653 977 | 644 162 | 1 907 | 8 | 0 | 0 |
| storage::storage::run_many_words_dense::count_1000 | 558 044 | 690 065 | 680 165 | 1 910 | 10 | 0 | 0 |
| storage::storage::run_many_words_linked::count_1000 | 481 044 | 611 149 | 601 119 | 1 957 | 7 | 0 | 0 |
| storage::storage::run_one_word_csr::len_100000 | 2 600 054 | 3 025 428 | 2 993 823 | 6 272 | 7 | 0 | 0 |
| storage::storage::run_one_word_dense::len_100000 | 2 800 050 | 3 425 491 | 3 393 811 | 6 273 | 9 | 0 | 0 |
| storage::storage::run_one_word_linked::len_100000 | 2 350 039 | 2 975 428 | 2 943 773 | 6 296 | 5 | 0 | 0 |
| storage::storage::successor_all_pairs_csr::k2_2000 | 122 242 | 139 528 | 138 103 | 229 | 8 | 8 | 1 |
| storage::storage::successor_all_pairs_csr::k8_2000 | 702 302 | 802 770 | 797 375 | 1 023 | 8 | 32 | 1 |
| storage::storage::successor_all_pairs_dense::k2_2000 | 162 237 | 193 579 | 192 089 | 235 | 9 | 8 | 1 |
| storage::storage::successor_all_pairs_dense::k8_2000 | 814 297 | 952 885 | 947 345 | 1 045 | 9 | 32 | 1 |
| storage::storage::successor_all_pairs_linked::k2_2000 | 108 236 | 139 124 | 128 179 | 2 140 | 7 | 8 | 1 |
| storage::storage::successor_all_pairs_linked::k8_2000 | 750 296 | 946 170 | 909 000 | 7 385 | 7 | 32 | 1 |
| ts::ts::add_edges_in_order::k2_5000 | 1 402 671 | 2 420 347 | 2 258 387 | 14 227 | 2 595 | 1 113 960 | 26 |
| ts::ts::add_edges_in_order::k8_5000 | 6 669 285 | 11 260 147 | 10 330 812 | 75 820 | 15 721 | 3 866 496 | 28 |
| ts::ts::add_edges_in_reverse::k2_5000 | 1 402 671 | 2 419 577 | 2 258 587 | 14 026 | 2 596 | 1 113 960 | 26 |
| ts::ts::builder_with_edges::k2_5000 | 81 367 023 | 98 219 387 | 95 717 447 | 451 696 | 6 956 | 1 739 532 | 45 |
| ts::ts::canonical_naming::scrambled_1500 | 3 167 608 | 4 657 735 | 4 467 720 | 21 798 | 2 315 | 463 808 | 5 846 |
| ts::ts::canonical_naming::scrambled_500 | 980 422 | 1 418 515 | 1 374 705 | 3 176 | 798 | 134 336 | 1 831 |
| ts::ts::clone::scrambled_10000 | 371 163 | 902 473 | 530 238 | 12 483 | 8 852 | 680 008 | 3 |
| ts::ts::clone::scrambled_40000 | 1 481 400 | 3 817 882 | 2 116 807 | 42 575 | 42 520 | 2 720 008 | 3 |
| ts::ts::collect_dts::scrambled_10000 | 3 465 149 | 6 166 150 | 5 606 845 | 37 171 | 10 670 | 2 228 064 | 27 |
| ts::ts::collect_dts::scrambled_40000 | 13 799 628 | 24 683 234 | 22 329 474 | 135 298 | 47 922 | 8 912 736 | 31 |
| ts::ts::determinize::nth_from_end_10 | 4 485 524 | 6 644 869 | 6 283 324 | 22 203 | 7 158 | 651 720 | 6 013 |
| ts::ts::determinize::nth_from_end_12 | 19 876 085 | 29 277 129 | 27 766 729 | 99 010 | 29 010 | 2 732 600 | 26 423 |
| ts::ts::determinize::nth_from_end_8 | 1 027 333 | 1 524 911 | 1 441 556 | 3 049 | 1 946 | 156 552 | 1 396 |
| ts::ts::edges_from_all_states::scrambled_2000 | 72 669 | 91 979 | 80 774 | 2 157 | 12 | 0 | 0 |
| ts::ts::edges_from_all_states::scrambled_k8_2000 | 156 601 | 208 928 | 171 428 | 7 402 | 14 | 0 | 0 |
| ts::ts::erase_state_colors_collect::scrambled_10000 | 3 007 166 | 5 308 247 | 4 748 862 | 37 173 | 10 672 | 2 228 064 | 27 |
| ts::ts::into_dfa::scrambled_10000 | 3 565 165 | 6 276 265 | 5 716 875 | 37 181 | 10 671 | 2 228 064 | 27 |
| ts::ts::map_edge_colors_collect::scrambled_10000 | 3 008 768 | 5 438 202 | 4 819 547 | 38 450 | 12 183 | 2 490 192 | 27 |
| ts::ts::map_edge_colors_collect::scrambled_40000 | 11 975 391 | 21 772 194 | 19 182 194 | 140 329 | 53 953 | 9 961 296 | 31 |
| ts::ts::matching_product_successor_index::n200 | 75 662 | 111 066 | 106 466 | 647 | 39 | 0 | 0 |
| ts::ts::minimal_representative_of_all_states::scrambled_100 | 2 100 814 | 2 967 856 | 2 964 191 | 12 | 103 | 347 504 | 4 679 |
| ts::ts::minimal_representative_of_all_states::scrambled_300 | 16 911 264 | 23 979 431 | 23 966 511 | 1 842 | 106 | 3 116 784 | 38 196 |
| ts::ts::minimal_representatives::scrambled_2000 | 3 384 040 | 4 762 130 | 4 715 235 | 8 910 | 67 | 322 944 | 7 709 |
| ts::ts::minimal_representatives::scrambled_8000 | 14 900 249 | 20 949 865 | 20 734 910 | 42 592 | 57 | 1 464 896 | 32 693 |
| ts::ts::predecessors_of_all_states::scrambled_2000 | 72 669 | 96 915 | 79 540 | 3 391 | 12 | 0 | 0 |
| ts::ts::predecessors_of_all_states::scrambled_8000 | 288 601 | 389 362 | 313 812 | 15 019 | 13 | 0 | 0 |
| ts::ts::reachable_states::scrambled_2000 | 290 091 | 460 935 | 440 005 | 3 605 | 83 | 4 336 | 9 |
| ts::ts::reachable_states::scrambled_8000 | 1 148 696 | 1 838 540 | 1 739 090 | 19 519 | 53 | 17 368 | 11 |
| ts::ts::remove_edges_from_matching::scrambled_10000 | 566 234 | 795 987 | 771 647 | 4 658 | 30 | 64 000 | 2 000 |
| ts::ts::remove_edges_from_matching::scrambled_40000 | 896 234 | 1 177 487 | 1 126 272 | 10 033 | 30 | 64 000 | 2 000 |
| ts::ts::remove_state::scrambled_10000 | 1 091 012 | 1 528 445 | 1 489 735 | 7 420 | 46 | 80 000 | 3 000 |
| ts::ts::remove_state::scrambled_40000 | 1 421 012 | 1 912 909 | 1 843 619 | 13 536 | 46 | 80 000 | 3 000 |
| ts::ts::scc_minimal_representatives::small_cycles_100 | 219 944 | 321 099 | 305 544 | 59 | 436 | 44 272 | 309 |
| ts::ts::scc_minimal_representatives::small_cycles_400 | 1 246 352 | 1 775 645 | 1 725 255 | 3 890 | 884 | 354 148 | 1 325 |
| ts::ts::subset_construction::nth_from_end_10 | 10 216 384 | 14 514 167 | 14 019 012 | 45 509 | 7 646 | 1 073 520 | 9 919 |
| ts::ts::subset_construction::nth_from_end_12 | 45 206 094 | 64 008 673 | 61 763 083 | 218 741 | 32 911 | 4 518 976 | 43 857 |
| ts::ts::subset_construction::nth_from_end_8 | 2 230 465 | 3 186 931 | 3 078 381 | 6 205 | 2 215 | 257 104 | 2 276 |
| ts::ts::successor_index_all_pairs::scrambled_2000 | 108 863 | 140 297 | 129 022 | 2 157 | 14 | 8 | 1 |
| ts::ts::successor_index_all_pairs::scrambled_k8_2000 | 750 855 | 947 282 | 909 742 | 7 403 | 15 | 32 | 1 |
Criterion means of a single run. They depend on the machine and are not compared; use the instruction counts above for that.
| benchmark | head |
|---|---|
| collect/clone/100000 | 3.97 ms (3.95 ms … 3.99 ms) |
| collect/clone/1000000 | 40.52 ms (39.91 ms … 41.14 ms) |
| collect/collect_owned/100000 | 7.46 ms (7.43 ms … 7.49 ms) |
| collect/collect_owned/1000000 | 90.62 ms (88.64 ms … 92.59 ms) |
| collect/collect_ref/100000 | 5.44 ms (5.41 ms … 5.48 ms) |
| collect/collect_ref/1000000 | 90.63 ms (88.75 ms … 92.51 ms) |
| collect/map_edge_colors_collect_owned/100000 | 7.37 ms (7.36 ms … 7.37 ms) |
| collect/map_edge_colors_collect_owned/1000000 | 84.39 ms (83.67 ms … 85.11 ms) |
| wallclock/dfa/accepts/word_100000 | 937.29 µs (937.18 µs … 937.40 µs) |
| wallclock/dfa/minimize/redundant_4000 | 1.41 ms (1.41 ms … 1.41 ms) |
| wallclock/dpa/complement/scrambled_4000 | 3.60 ms (3.58 ms … 3.63 ms) |
| wallclock/dpa/normalized/scrambled_4000 | 3.41 ms (3.41 ms … 3.42 ms) |
| wallclock/hoa/parse/ltl | 1.75 ms (1.74 ms … 1.76 ms) |
| wallclock/nfa/determinize/nth_from_end_12 | 3.43 ms (3.39 ms … 3.46 ms) |
| wallclock/nfa/subset_construction/nth_from_end_12 | 8.85 ms (8.75 ms … 8.95 ms) |
| wallclock/scc/tarjan/scrambled_10000 | 2.58 ms (2.53 ms … 2.64 ms) |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| hard/l-dsa-3 | spot | 132.08 µs | 114.12 µs | 1.16× | – / – | yes |
| hard/l-nba-2 | spot | 58.08 µs | 34.52 µs | 1.68× | – / – | yes |
| hard/m-nba-3 | spot | 256.82 µs | 132.98 µs | 1.93× | – / – | yes |
| ltl/and-gf-3 | spot | 9.92 µs | 11.32 µs | 0.88× | – / – | yes |
| ltl/eh-patterns-0 | spot | 22.88 µs | 19.22 µs | 1.19× | – / – | yes |
| ltl/gf-equiv-3 | spot | 21.44 µs | 33.12 µs | 0.65× | – / – | yes |
| ltl/gf-implies-3 | spot | 11.04 µs | 18.34 µs | 0.60× | – / – | yes |
| ltl/gh-q-3 | spot | 51.56 µs | 27.28 µs | 1.89× | – / – | yes |
| ltl/gh-r-3 | spot | 23.80 µs | 67.10 µs | 0.35× | – / – | yes |
| ltl/go-theta-3 | spot | 12.16 µs | 20.12 µs | 0.60× | – / – | yes |
| ltl/lily-patterns-1 | spot | 12.72 µs | 14.96 µs | 0.85× | – / – | yes |
| ltl/ms-phi-r-1 | spot | 11.44 µs | 36.76 µs | 0.31× | – / – | yes |
| ltl/ms-phi-s-1 | spot | 11.36 µs | 37.80 µs | 0.30× | – / – | yes |
| ltl/rv-counter-3 | spot | 28.10 µs | 12.00 µs | 2.34× | – / – | yes |
| ltl/sb-patterns-0 | spot | 13.52 µs | 13.16 µs | 1.03× | – / – | yes |
| ltl/sejk-k-2 | spot | 15.08 µs | 55.36 µs | 0.27× | – / – | yes |
| ltl/tv-uu-3 | spot | 41.50 µs | 36.18 µs | 1.15× | – / – | yes |
| ltl/u-left-3 | spot | 10.98 µs | 7.84 µs | 1.40× | – / – | yes |
| many_aps/and-gf-12 | spot | 565.63 µs | 61.68 µs | 9.17× | – / – | yes |
| many_aps/gf-equiv-12 | spot | 134.32 µs | 89.58 µs | 1.50× | – / – | yes |
| many_aps/r-right-10 | spot | 145.96 µs | 25.40 µs | 5.75× | – / – | yes |
| many_aps/random-n16-a8-p4-s1 | spot | 694.21 µs | 128.78 µs | 5.39× | – / – | yes |
| many_aps/random-n24-a12-p4-s1 | spot | 2.95 ms | 426.93 µs | 6.92× | – / – | yes |
| many_aps/random-n32-a16-p4-s1 | spot | 7.08 ms | 1.23 ms | 5.76× | – / – | yes |
| random/n128-a2-p6-s1 | spot | 344.92 µs | 203.00 µs | 1.70× | – / – | yes |
| random/n16-a1-p3-s1 | spot | 22.56 µs | 15.42 µs | 1.46× | – / – | yes |
| random/n256-a2-p8-s1 | spot | 946.25 µs | 465.19 µs | 2.03× | – / – | yes |
| random/n64-a2-p4-s1 | spot | 148.64 µs | 95.96 µs | 1.55× | – / – | yes |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| hard/l-dsa-3 | spot | 70.24 µs | 59.26 µs | 1.19× | – / – | yes |
| hard/l-nba-2 | spot | 34.80 µs | 21.64 µs | 1.61× | – / – | yes |
| hard/m-nba-3 | spot | 145.72 µs | 80.16 µs | 1.82× | – / – | yes |
| ltl/and-gf-3 | spot | 5.92 µs | 7.44 µs | 0.80× | – / – | yes |
| ltl/eh-patterns-0 | spot | 14.94 µs | 16.60 µs | 0.90× | – / – | yes |
| ltl/gf-equiv-3 | spot | 12.28 µs | 17.76 µs | 0.69× | – / – | yes |
| ltl/gf-implies-3 | spot | 6.38 µs | 10.62 µs | 0.60× | – / – | yes |
| ltl/gh-q-3 | spot | 33.08 µs | 28.88 µs | 1.15× | – / – | yes |
| ltl/gh-r-3 | spot | 13.68 µs | 33.80 µs | 0.40× | – / – | yes |
| ltl/go-theta-3 | spot | 7.32 µs | 14.98 µs | 0.49× | – / – | yes |
| ltl/lily-patterns-1 | spot | 8.20 µs | 12.68 µs | 0.65× | – / – | yes |
| ltl/ms-phi-r-1 | spot | 6.64 µs | 18.10 µs | 0.37× | – / – | yes |
| ltl/ms-phi-s-1 | spot | 6.52 µs | 24.28 µs | 0.27× | – / – | yes |
| ltl/rv-counter-3 | spot | 18.06 µs | 13.68 µs | 1.32× | – / – | yes |
| ltl/sb-patterns-0 | spot | 8.12 µs | 11.06 µs | 0.73× | – / – | yes |
| ltl/sejk-k-2 | spot | 8.48 µs | 27.64 µs | 0.31× | – / – | yes |
| ltl/tv-uu-3 | spot | 27.70 µs | 27.88 µs | 0.99× | – / – | yes |
| ltl/u-left-3 | spot | 6.92 µs | 8.00 µs | 0.86× | – / – | yes |
| many_aps/and-gf-12 | spot | 545.99 µs | 51.04 µs | 10.70× | – / – | yes |
| many_aps/gf-equiv-12 | spot | 85.60 µs | 51.30 µs | 1.67× | – / – | yes |
| many_aps/r-right-10 | spot | 129.84 µs | 23.12 µs | 5.62× | – / – | yes |
| many_aps/random-n16-a8-p4-s1 | spot | 649.69 µs | 97.52 µs | 6.66× | – / – | yes |
| many_aps/random-n24-a12-p4-s1 | spot | 2.86 ms | 381.20 µs | 7.50× | – / – | yes |
| many_aps/random-n32-a16-p4-s1 | spot | 6.90 ms | 1.07 ms | 6.48× | – / – | yes |
| random/n128-a2-p6-s1 | spot | 202.08 µs | 121.10 µs | 1.67× | – / – | yes |
| random/n16-a1-p3-s1 | spot | 13.16 µs | 9.44 µs | 1.39× | – / – | yes |
| random/n256-a2-p8-s1 | spot | 516.85 µs | 288.66 µs | 1.79× | – / – | yes |
| random/n64-a2-p4-s1 | spot | 85.80 µs | 61.20 µs | 1.40× | – / – | yes |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| ladder_10000 | oink-ppp | 2.79 ms | 307.00 µs | 9.08× | 10000 / 10000 | yes |
| ladder_10000 | oink-zlk | 2.79 ms | 306.00 µs | 9.11× | 10000 / 10000 | yes |
| ladder_10000 | spot | 2.79 ms | 9.64 ms | 0.29× | 10000 / 10000 | yes |
| ladder_50000 | oink-ppp | 21.45 ms | 2.13 ms | 10.07× | 50000 / 50000 | yes |
| ladder_50000 | oink-zlk | 21.45 ms | 2.21 ms | 9.68× | 50000 / 50000 | yes |
| ladder_50000 | spot | 21.45 ms | 70.52 ms | 0.30× | 50000 / 50000 | yes |
| random_few_10000 | oink-ppp | 7.83 ms | 1.48 ms | 5.30× | 10000 / 10000 | yes |
| random_few_10000 | oink-zlk | 7.83 ms | 2.76 ms | 2.83× | 10000 / 10000 | yes |
| random_few_10000 | spot | 7.83 ms | 21.32 ms | 0.37× | 10000 / 10000 | yes |
| random_few_50000 | oink-ppp | 81.24 ms | 16.97 ms | 4.79× | 50000 / 50000 | yes |
| random_few_50000 | oink-zlk | 81.24 ms | 20.84 ms | 3.90× | 50000 / 50000 | yes |
| random_few_50000 | spot | 81.24 ms | 712.15 ms | 0.11× | 50000 / 50000 | yes |
| random_many_10000 | oink-ppp | 7.26 ms | 1.60 ms | 4.52× | 10000 / 10000 | yes |
| random_many_10000 | oink-zlk | 7.26 ms | 2.87 ms | 2.53× | 10000 / 10000 | yes |
| random_many_10000 | spot | 7.26 ms | 30.41 ms | 0.24× | 10000 / 10000 | yes |
| random_many_50000 | oink-ppp | 84.93 ms | 34.31 ms | 2.48× | 50000 / 50000 | yes |
| random_many_50000 | oink-zlk | 84.93 ms | 46.33 ms | 1.83× | 50000 / 50000 | yes |
| random_many_50000 | spot | 84.93 ms | 729.73 ms | 0.12× | 50000 / 50000 | yes |
== head 1bf383b20a4b798c37edf559a20e4bdb9ded5c24: 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 2m 00s
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.22s
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.18s
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.21s
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.21s
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.19s
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.22s
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.24s
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.21s
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.21s
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.21s
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.132 ms / 0.114 ms
dpa/equivalence/hard/l-nba-2 vs spot: 0.058 ms / 0.035 ms
dpa/equivalence/hard/m-nba-3 vs spot: 0.257 ms / 0.133 ms
dpa/equivalence/ltl/and-gf-3 vs spot: 0.010 ms / 0.011 ms
dpa/equivalence/ltl/eh-patterns-0 vs spot: 0.023 ms / 0.019 ms
dpa/equivalence/ltl/gf-equiv-3 vs spot: 0.021 ms / 0.033 ms
dpa/equivalence/ltl/gf-implies-3 vs spot: 0.011 ms / 0.018 ms
dpa/equivalence/ltl/gh-q-3 vs spot: 0.052 ms / 0.027 ms
dpa/equivalence/ltl/gh-r-3 vs spot: 0.024 ms / 0.067 ms
dpa/equivalence/ltl/go-theta-3 vs spot: 0.012 ms / 0.020 ms
dpa/equivalence/ltl/lily-patterns-1 vs spot: 0.013 ms / 0.015 ms
dpa/equivalence/ltl/ms-phi-r-1 vs spot: 0.011 ms / 0.037 ms
dpa/equivalence/ltl/ms-phi-s-1 vs spot: 0.011 ms / 0.038 ms
dpa/equivalence/ltl/rv-counter-3 vs spot: 0.028 ms / 0.012 ms
dpa/equivalence/ltl/sb-patterns-0 vs spot: 0.014 ms / 0.013 ms
dpa/equivalence/ltl/sejk-k-2 vs spot: 0.015 ms / 0.055 ms
dpa/equivalence/ltl/tv-uu-3 vs spot: 0.042 ms / 0.036 ms
dpa/equivalence/ltl/u-left-3 vs spot: 0.011 ms / 0.008 ms
dpa/equivalence/many_aps/and-gf-12 vs spot: 0.566 ms / 0.062 ms
dpa/equivalence/many_aps/gf-equiv-12 vs spot: 0.134 ms / 0.090 ms
dpa/equivalence/many_aps/r-right-10 vs spot: 0.146 ms / 0.025 ms
dpa/equivalence/many_aps/random-n16-a8-p4-s1 vs spot: 0.694 ms / 0.129 ms
dpa/equivalence/many_aps/random-n24-a12-p4-s1 vs spot: 2.953 ms / 0.427 ms
dpa/equivalence/many_aps/random-n32-a16-p4-s1 vs spot: 7.078 ms / 1.228 ms
dpa/equivalence/random/n128-a2-p6-s1 vs spot: 0.345 ms / 0.203 ms
dpa/equivalence/random/n16-a1-p3-s1 vs spot: 0.023 ms / 0.015 ms
dpa/equivalence/random/n256-a2-p8-s1 vs spot: 0.946 ms / 0.465 ms
dpa/equivalence/random/n64-a2-p4-s1 vs spot: 0.149 ms / 0.096 ms
dpa/inclusion/hard/l-dsa-3 vs spot: 0.070 ms / 0.059 ms
dpa/inclusion/hard/l-nba-2 vs spot: 0.035 ms / 0.022 ms
dpa/inclusion/hard/m-nba-3 vs spot: 0.146 ms / 0.080 ms
dpa/inclusion/ltl/and-gf-3 vs spot: 0.006 ms / 0.007 ms
dpa/inclusion/ltl/eh-patterns-0 vs spot: 0.015 ms / 0.017 ms
dpa/inclusion/ltl/gf-equiv-3 vs spot: 0.012 ms / 0.018 ms
dpa/inclusion/ltl/gf-implies-3 vs spot: 0.006 ms / 0.011 ms
dpa/inclusion/ltl/gh-q-3 vs spot: 0.033 ms / 0.029 ms
dpa/inclusion/ltl/gh-r-3 vs spot: 0.014 ms / 0.034 ms
dpa/inclusion/ltl/go-theta-3 vs spot: 0.007 ms / 0.015 ms
dpa/inclusion/ltl/lily-patterns-1 vs spot: 0.008 ms / 0.013 ms
dpa/inclusion/ltl/ms-phi-r-1 vs spot: 0.007 ms / 0.018 ms
dpa/inclusion/ltl/ms-phi-s-1 vs spot: 0.007 ms / 0.024 ms
dpa/inclusion/ltl/rv-counter-3 vs spot: 0.018 ms / 0.014 ms
dpa/inclusion/ltl/sb-patterns-0 vs spot: 0.008 ms / 0.011 ms
dpa/inclusion/ltl/sejk-k-2 vs spot: 0.008 ms / 0.028 ms
dpa/inclusion/ltl/tv-uu-3 vs spot: 0.028 ms / 0.028 ms
dpa/inclusion/ltl/u-left-3 vs spot: 0.007 ms / 0.008 ms
dpa/inclusion/many_aps/and-gf-12 vs spot: 0.546 ms / 0.051 ms
dpa/inclusion/many_aps/gf-equiv-12 vs spot: 0.086 ms / 0.051 ms
dpa/inclusion/many_aps/r-right-10 vs spot: 0.130 ms / 0.023 ms
dpa/inclusion/many_aps/random-n16-a8-p4-s1 vs spot: 0.650 ms / 0.098 ms
dpa/inclusion/many_aps/random-n24-a12-p4-s1 vs spot: 2.858 ms / 0.381 ms
dpa/inclusion/many_aps/random-n32-a16-p4-s1 vs spot: 6.901 ms / 1.065 ms
dpa/inclusion/random/n128-a2-p6-s1 vs spot: 0.202 ms / 0.121 ms
dpa/inclusion/random/n16-a1-p3-s1 vs spot: 0.013 ms / 0.009 ms
dpa/inclusion/random/n256-a2-p8-s1 vs spot: 0.517 ms / 0.289 ms
dpa/inclusion/random/n64-a2-p4-s1 vs spot: 0.086 ms / 0.061 ms
game/solve/random_few_10000 vs spot: 7.827 ms / 21.323 ms
game/solve/random_few_10000 vs oink-zlk: 7.827 ms / 2.764 ms
game/solve/random_few_10000 vs oink-ppp: 7.827 ms / 1.478 ms
game/solve/random_few_50000 vs spot: 81.239 ms / 712.146 ms
game/solve/random_few_50000 vs oink-zlk: 81.239 ms / 20.835 ms
game/solve/random_few_50000 vs oink-ppp: 81.239 ms / 16.969 ms
game/solve/random_many_10000 vs spot: 7.256 ms / 30.414 ms
game/solve/random_many_10000 vs oink-zlk: 7.256 ms / 2.873 ms
game/solve/random_many_10000 vs oink-ppp: 7.256 ms / 1.604 ms
game/solve/random_many_50000 vs spot: 84.932 ms / 729.727 ms
game/solve/random_many_50000 vs oink-zlk: 84.932 ms / 46.334 ms
game/solve/random_many_50000 vs oink-ppp: 84.932 ms / 34.306 ms
game/solve/ladder_10000 vs spot: 2.788 ms / 9.637 ms
game/solve/ladder_10000 vs oink-zlk: 2.788 ms / 0.306 ms
game/solve/ladder_10000 vs oink-ppp: 2.788 ms / 0.307 ms
game/solve/ladder_50000 vs spot: 21.447 ms / 70.517 ms
game/solve/ladder_50000 vs oink-zlk: 21.447 ms / 2.215 ms
game/solve/ladder_50000 vs oink-ppp: 21.447 ms / 2.130 ms
== head: 259 benchmarks, 16 wall-clock measurements, 74 comparisons