History · Versus Spot and Oink
HOA: read parity edges without acceptance set (#151) (#167)
status done · queued 2026-11-11 19:29 · started 2026-11-11 19:29 · finished 2026-11-11 19:47
· · 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 | 319 438 | 399 881 | 393 386 | 1 222 | 11 | 0 | 0 |
| dfa::dfa::complement::scrambled_1000 | 318 874 | 512 713 | 495 033 | 3 375 | 23 | 139 104 | 19 |
| dfa::dfa::complement::scrambled_4000 | 1 247 649 | 2 024 598 | 1 938 853 | 16 995 | 22 | 556 896 | 23 |
| dfa::dfa::equivalent::deep_difference_100 | 52 831 | 82 619 | 75 499 | 45 | 197 | 16 196 | 25 |
| dfa::dfa::equivalent::deep_difference_400 | 177 852 | 277 913 | 255 568 | 1 851 | 374 | 65 364 | 33 |
| dfa::dfa::equivalent::different_100 | 8 349 | 14 148 | 11 488 | 7 | 75 | 1 804 | 12 |
| dfa::dfa::equivalent::different_400 | 8 390 | 14 353 | 11 443 | 78 | 72 | 1 804 | 12 |
| dfa::dfa::equivalent::minimized_100 | 31 312 | 46 508 | 44 273 | 104 | 49 | 7 756 | 17 |
| dfa::dfa::equivalent::minimized_400 | 103 504 | 153 074 | 147 659 | 726 | 51 | 31 580 | 23 |
| dfa::dfa::give_word::empty_1000 | 1 795 234 | 2 450 035 | 2 422 480 | 4 916 | 85 | 152 864 | 3 738 |
| dfa::dfa::give_word::empty_4000 | 6 603 983 | 9 194 133 | 9 091 428 | 20 065 | 68 | 679 808 | 15 828 |
| dfa::dfa::give_word::far_1000 | 157 743 | 223 352 | 218 827 | 548 | 51 | 28 176 | 394 |
| dfa::dfa::give_word::far_4000 | 909 225 | 1 280 347 | 1 258 337 | 3 933 | 67 | 148 464 | 2 233 |
| dfa::dfa::intersection::scrambled_100 | 2 716 048 | 3 995 295 | 3 817 115 | 12 011 | 3 375 | 428 088 | 42 |
| dfa::dfa::intersection::scrambled_200 | 10 809 511 | 16 277 754 | 15 140 774 | 96 867 | 18 647 | 1 708 120 | 49 |
| dfa::dfa::intersection_is_empty::empty_100 | 50 659 | 79 033 | 72 533 | 33 | 181 | 15 700 | 20 |
| dfa::dfa::intersection_is_empty::empty_200 | 92 418 | 145 704 | 132 529 | 619 | 288 | 31 580 | 23 |
| dfa::dfa::is_empty_language::empty_1000 | 1 795 234 | 2 450 069 | 2 422 479 | 4 916 | 86 | 152 864 | 3 738 |
| dfa::dfa::is_empty_language::empty_4000 | 6 603 983 | 9 194 167 | 9 091 427 | 20 065 | 69 | 679 808 | 15 828 |
| dfa::dfa::minimize::minimal_1000 | 3 298 979 | 4 979 390 | 4 604 640 | 39 733 | 5 031 | 1 135 492 | 2 214 |
| dfa::dfa::minimize::minimal_4000 | 12 876 089 | 19 609 366 | 17 952 606 | 204 568 | 18 112 | 4 543 724 | 8 254 |
| dfa::dfa::minimize::redundant_1000 | 2 174 551 | 3 263 224 | 3 028 279 | 25 884 | 3 015 | 760 780 | 1 201 |
| dfa::dfa::minimize::redundant_4000 | 8 406 754 | 12 753 392 | 11 696 777 | 143 612 | 9 673 | 3 044 900 | 4 241 |
| dfa::dfa::minimize::scrambled_1000 | 3 502 256 | 5 309 295 | 4 877 655 | 51 034 | 5 042 | 1 116 052 | 2 217 |
| dfa::dfa::minimize::scrambled_4000 | 13 587 258 | 20 978 316 | 18 872 886 | 294 022 | 18 152 | 4 470 140 | 8 261 |
| dfa::dfa::minimize_moore_with_edge_colors::scrambled_1000 | 3 500 317 | 5 293 070 | 4 866 645 | 50 089 | 5 028 | 1 116 052 | 2 217 |
| dfa::dfa::minimize_moore_with_edge_colors::scrambled_4000 | 13 571 891 | 20 909 246 | 18 808 236 | 300 579 | 17 089 | 4 470 140 | 8 261 |
| dfa::dfa::union::scrambled_100 | 2 716 048 | 3 995 295 | 3 817 115 | 12 011 | 3 375 | 428 088 | 42 |
| dfa::dfa::union::scrambled_200 | 10 809 511 | 16 277 754 | 15 140 774 | 96 867 | 18 647 | 1 708 120 | 49 |
| dpa::dpa::accepted_word::chain_100 | 114 774 | 174 736 | 162 981 | 48 | 329 | – | – |
| dpa::dpa::accepted_word::chain_400 | 391 265 | 589 315 | 555 065 | 2 965 | 555 | – | – |
| dpa::dpa::accepted_word::scrambled_100 | 145 660 | 218 263 | 206 028 | 39 | 344 | – | – |
| dpa::dpa::accepted_word::scrambled_400 | 499 945 | 740 789 | 707 774 | 2 816 | 541 | – | – |
| dpa::dpa::accepted_word_fixtures::ltl | 495 442 | 717 367 | 690 272 | 2 444 | 425 | – | – |
| dpa::dpa::accepted_word_fixtures::synthetic | 1 255 420 | 1 812 792 | 1 739 387 | 12 147 | 362 | – | – |
| dpa::dpa::accepted_word_fixtures_by_atoms::ltl | 1 620 528 | 2 382 789 | 2 323 729 | 7 990 | 546 | – | – |
| dpa::dpa::accepted_word_fixtures_by_atoms::synthetic | 2 741 079 | 4 051 671 | 3 966 936 | 13 174 | 539 | – | – |
| dpa::dpa::collect_dpa::scrambled_1000 | 258 437 | 421 129 | 402 024 | 3 800 | 3 | – | – |
| dpa::dpa::collect_dpa::scrambled_4000 | 1 004 782 | 1 689 474 | 1 565 929 | 16 393 | 1 188 | – | – |
| dpa::dpa::complement::chain_1000 | 3 806 713 | 5 721 624 | 5 221 069 | 55 157 | 6 422 | – | – |
| dpa::dpa::complement::chain_4000 | 15 498 940 | 23 452 464 | 21 213 689 | 262 010 | 26 535 | – | – |
| dpa::dpa::complement::scrambled_1000 | 4 640 280 | 6 873 638 | 6 331 503 | 62 493 | 6 562 | – | – |
| dpa::dpa::complement::scrambled_4000 | 18 790 501 | 28 240 496 | 25 579 271 | 344 043 | 26 886 | – | – |
| dpa::dpa::complement_fixtures::ltl | 1 318 752 | 1 877 476 | 1 840 506 | 4 650 | 392 | – | – |
| dpa::dpa::complement_fixtures::many_aps | 12 439 582 | 17 915 445 | 17 431 250 | 86 794 | 1 435 | – | – |
| dpa::dpa::complement_fixtures::synthetic | 9 051 778 | 12 768 424 | 12 267 864 | 97 144 | 424 | – | – |
| dpa::dpa::complement_without_normalizing::scrambled_1000 | 542 899 | 786 482 | 757 882 | 5 153 | 81 | – | – |
| dpa::dpa::complement_without_normalizing::scrambled_4000 | 2 135 246 | 3 133 689 | 2 979 574 | 21 961 | 1 266 | – | – |
| dpa::dpa::equivalent_fixtures::many_aps | 18 698 034 | 27 050 090 | 26 383 505 | 120 738 | 1 797 | – | – |
| dpa::dpa::hoa_parse::ltl | 5 180 332 | 7 808 013 | 7 519 903 | 35 754 | 3 124 | – | – |
| dpa::dpa::hoa_parse::many_aps | 80 468 714 | 132 800 512 | 115 595 187 | 293 060 | 449 715 | – | – |
| dpa::dpa::hoa_parse::synthetic | 23 750 490 | 35 938 771 | 34 536 016 | 180 577 | 14 282 | – | – |
| dpa::dpa::hoa_print::ltl | 14 450 353 | 31 507 113 | 19 336 733 | 4 446 | 347 090 | – | – |
| dpa::dpa::hoa_print::many_aps | 17 708 492 | 25 411 125 | 25 332 975 | 13 152 | 354 | – | – |
| dpa::dpa::hoa_print::synthetic | 21 972 183 | 42 584 781 | 30 245 826 | 25 127 | 348 952 | – | – |
| dpa::dpa::included_fixtures::many_aps | 15 907 783 | 23 120 683 | 22 585 403 | 94 736 | 1 760 | – | – |
| dpa::dpa::included_in::complement_100 | 260 739 | 388 107 | 371 322 | 851 | 358 | – | – |
| dpa::dpa::included_in::complement_25 | 84 611 | 131 576 | 119 146 | 92 | 342 | – | – |
| dpa::dpa::included_in::complement_50 | 146 080 | 219 989 | 206 674 | 332 | 333 | – | – |
| dpa::dpa::included_in::normalized_100 | 524 060 | 763 764 | 738 554 | 1 276 | 538 | – | – |
| dpa::dpa::included_in::normalized_25 | 177 925 | 261 373 | 249 568 | 107 | 322 | – | – |
| dpa::dpa::included_in::normalized_50 | 302 723 | 439 869 | 425 574 | 311 | 364 | – | – |
| dpa::dpa::language_equivalent::complement_100 | 268 661 | 397 843 | 380 478 | 869 | 372 | – | – |
| dpa::dpa::language_equivalent::complement_25 | 86 600 | 134 407 | 121 472 | 95 | 356 | – | – |
| dpa::dpa::language_equivalent::complement_50 | 149 885 | 224 881 | 211 021 | 343 | 347 | – | – |
| dpa::dpa::language_equivalent::normalized_100 | 963 959 | 1 387 511 | 1 353 471 | 2 181 | 661 | – | – |
| dpa::dpa::language_equivalent::normalized_25 | 315 935 | 456 429 | 442 274 | 143 | 384 | – | – |
| dpa::dpa::language_equivalent::normalized_50 | 564 774 | 808 298 | 791 093 | 473 | 424 | – | – |
| dpa::dpa::map_edge_colors_collect::scrambled_1000 | 263 002 | 419 699 | 399 659 | 3 875 | 19 | – | – |
| dpa::dpa::map_edge_colors_collect::scrambled_4000 | 1 021 347 | 1 681 854 | 1 553 859 | 17 171 | 1 204 | – | – |
| dpa::dpa::normalized::chain_1000 | 3 513 188 | 5 339 222 | 4 851 577 | 52 918 | 6 373 | – | – |
| dpa::dpa::normalized::chain_4000 | 14 326 415 | 21 930 822 | 19 737 757 | 253 211 | 26 486 | – | – |
| dpa::dpa::normalized::scrambled_1000 | 4 346 572 | 6 490 921 | 5 961 726 | 60 248 | 6 513 | – | – |
| dpa::dpa::normalized::scrambled_4000 | 17 617 793 | 26 718 459 | 24 103 074 | 335 218 | 26 837 | – | – |
| dpa::dpa::normalized::scrambled_k4_1000 | 25 249 999 | 35 407 372 | 33 257 947 | 379 422 | 7 209 | – | – |
| dpa::dpa::normalized_fixtures::ltl | 1 272 930 | 1 820 337 | 1 786 562 | 4 431 | 332 | – | – |
| dpa::dpa::normalized_fixtures::many_aps | 12 275 183 | 17 722 940 | 17 254 290 | 83 979 | 1 393 | – | – |
| dpa::dpa::normalized_fixtures::synthetic | 8 843 733 | 12 509 865 | 12 039 505 | 91 377 | 385 | – | – |
| dpa::dpa::prefix_partition::chain_16 | 3 574 178 | 5 459 472 | 5 389 682 | 2 779 | 1 597 | – | – |
| dpa::dpa::prefix_partition::chain_8 | 916 107 | 1 410 217 | 1 379 602 | 705 | 774 | – | – |
| dpa::dpa::prefix_partition::scrambled_16 | 3 999 698 | 6 158 346 | 6 069 751 | 4 433 | 1 898 | – | – |
| dpa::dpa::prefix_partition::scrambled_8 | 1 086 510 | 1 671 137 | 1 638 897 | 946 | 786 | – | – |
| dpa::dpa::rejected_word::chain_100 | 885 231 | 1 282 131 | 1 241 421 | 2 801 | 763 | – | – |
| dpa::dpa::rejected_word::chain_400 | 3 442 123 | 5 131 196 | 4 832 701 | 47 939 | 1 680 | – | – |
| dpa::dpa::rejected_word::scrambled_100 | 235 103 | 360 904 | 329 639 | 506 | 821 | – | – |
| dpa::dpa::rejected_word::scrambled_400 | 887 076 | 1 355 518 | 1 244 353 | 10 235 | 1 714 | – | – |
| dpa::dpa::sccs::chain_1000 | 511 023 | 774 938 | 699 653 | 6 832 | 1 175 | – | – |
| dpa::dpa::sccs::chain_4000 | 1 971 630 | 3 022 723 | 2 696 938 | 29 891 | 5 038 | – | – |
| dpa::dpa::sccs::scrambled_1000 | 576 822 | 871 380 | 795 340 | 8 222 | 998 | – | – |
| dpa::dpa::sccs::scrambled_4000 | 2 295 945 | 3 543 815 | 3 164 885 | 46 274 | 4 216 | – | – |
| dpa::dpa::witness_colors::chain_100 | 4 471 330 | 6 365 802 | 6 245 957 | 8 940 | 2 147 | – | – |
| dpa::dpa::witness_colors::chain_400 | 43 697 424 | 62 812 938 | 61 212 943 | 194 468 | 17 933 | – | – |
| dpa::dpa::witness_colors::scrambled_100 | 3 895 199 | 5 532 039 | 5 442 539 | 8 779 | 1 303 | – | – |
| dpa::dpa::witness_colors::scrambled_400 | 29 949 989 | 42 973 994 | 42 154 459 | 145 616 | 2 613 | – | – |
| dpa::dpa::witness_inequivalence::complement_100 | 268 661 | 397 853 | 380 483 | 863 | 373 | – | – |
| dpa::dpa::witness_inequivalence::complement_25 | 86 600 | 134 421 | 121 476 | 90 | 357 | – | – |
| dpa::dpa::witness_inequivalence::complement_50 | 149 885 | 224 895 | 211 025 | 338 | 348 | – | – |
| dpa::dpa::witness_not_subset_of::complement_100 | 260 739 | 388 163 | 371 323 | 848 | 360 | – | – |
| dpa::dpa::witness_not_subset_of::complement_25 | 84 611 | 131 628 | 119 148 | 88 | 344 | – | – |
| dpa::dpa::witness_not_subset_of::complement_50 | 146 080 | 220 041 | 206 676 | 328 | 335 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_100 | 524 060 | 763 820 | 738 555 | 1 273 | 540 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_25 | 177 925 | 261 433 | 249 568 | 105 | 324 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_50 | 302 723 | 439 921 | 425 576 | 307 | 366 | – | – |
| dpa::dpa::witnesses_fixtures::ltl | 1 970 349 | 2 740 021 | 2 683 296 | 6 025 | 760 | – | – |
| dpa::dpa::witnesses_fixtures::synthetic | 15 821 117 | 22 786 957 | 22 257 512 | 100 415 | 782 | – | – |
| game::game::tangle_learning::few_priorities_1000 | 2 598 081 | 3 917 533 | 3 570 783 | 35 967 | 4 769 | 745 400 | 1 292 |
| game::game::tangle_learning::few_priorities_4000 | 7 882 207 | 12 361 123 | 10 759 633 | 194 361 | 17 991 | 2 407 416 | 3 266 |
| game::game::tangle_learning::ladder_1000 | 1 169 460 | 1 811 071 | 1 611 131 | 12 275 | 3 959 | 377 868 | 118 |
| game::game::tangle_learning::ladder_4000 | 4 381 816 | 7 035 996 | 5 976 831 | 110 249 | 14 512 | 1 511 668 | 225 |
| game::game::tangle_learning::many_priorities_1000 | 1 963 252 | 2 956 172 | 2 676 227 | 25 518 | 4 353 | 566 440 | 848 |
| game::game::tangle_learning::many_priorities_4000 | 6 594 921 | 10 279 493 | 8 905 703 | 165 656 | 15 586 | 2 187 344 | 1 620 |
| game::game::tangle_learning_min_odd::few_priorities_1000 | 1 500 213 | 2 281 477 | 2 044 147 | 26 270 | 3 028 | 525 072 | 189 |
| game::game::tangle_learning_min_odd::few_priorities_4000 | 7 799 992 | 12 020 318 | 10 520 538 | 215 732 | 12 032 | 2 560 064 | 1 933 |
| game::game::zielonka::few_priorities_1000 | 1 107 876 | 1 656 056 | 1 469 421 | 12 421 | 3 558 | 356 676 | 95 |
| game::game::zielonka::few_priorities_4000 | 3 498 897 | 5 565 197 | 4 670 222 | 81 121 | 13 982 | 1 278 564 | 84 |
| game::game::zielonka::ladder_1000 | 4 708 253 | 6 180 832 | 5 779 897 | 49 821 | 4 338 | 549 716 | 211 |
| game::game::zielonka::ladder_4000 | 18 161 867 | 23 979 390 | 22 178 395 | 245 350 | 16 407 | 2 200 404 | 247 |
| game::game::zielonka::many_priorities_1000 | 3 821 963 | 5 020 038 | 4 685 583 | 38 373 | 4 074 | 841 196 | 367 |
| game::game::zielonka::many_priorities_4000 | 12 101 969 | 16 234 075 | 14 860 860 | 175 383 | 14 180 | 2 808 868 | 310 |
| game::game::zielonka_min_odd::few_priorities_1000 | 2 040 908 | 2 803 965 | 2 583 830 | 23 552 | 2 925 | 512 012 | 195 |
| game::game::zielonka_min_odd::few_priorities_4000 | 6 089 965 | 8 778 711 | 7 810 441 | 130 927 | 8 961 | 1 705 700 | 158 |
| learning::learning::lstar_mealy::counting_16 | 1 751 762 | 2 376 855 | 2 339 535 | 436 | 1 004 | 154 184 | 2 615 |
| learning::learning::lstar_mealy::counting_8 | 446 460 | 624 621 | 598 881 | 136 | 716 | 40 280 | 852 |
| learning::learning::sprout_parity::inf_ab_100 | 1 146 508 | 1 639 597 | 1 582 442 | 1 974 | 1 351 | 200 320 | 1 868 |
| learning::learning::sprout_parity::inf_ab_400 | 2 353 106 | 3 351 340 | 3 241 495 | 8 858 | 1 873 | 404 944 | 3 645 |
| nondeterministic::nondeterministic::fixture_accepts::ltl | 731 487 | 1 132 614 | 1 084 594 | 5 957 | 521 | – | – |
| nondeterministic::nondeterministic::nba_accepts::nba_400 | 122 996 323 | 179 087 273 | 168 150 723 | 1 663 507 | 74 829 | – | – |
| nondeterministic::nondeterministic::nba_witness::nba_4000 | 17 383 333 | 26 028 582 | 25 014 717 | 138 520 | 9 179 | – | – |
| nondeterministic::nondeterministic::nca_accepts::nca_400 | 254 927 534 | 371 569 756 | 345 867 471 | 4 569 278 | 81 597 | – | – |
| nondeterministic::nondeterministic::nca_witness::nca_4000 | 21 904 941 | 33 242 097 | 31 087 867 | 325 692 | 15 022 | – | – |
| nondeterministic::nondeterministic::nma_witness::nma_1000 | 25 383 666 | 37 527 531 | 35 512 776 | 370 177 | 4 682 | – | – |
| nondeterministic::nondeterministic::npa_accepts::empty_npa_400 | 458 821 236 | 670 094 773 | 622 425 428 | 8 911 009 | 88 980 | – | – |
| nondeterministic::nondeterministic::npa_accepts::npa_100 | 29 740 298 | 42 888 667 | 41 005 582 | 287 689 | 12 704 | – | – |
| nondeterministic::nondeterministic::npa_accepts::npa_400 | 122 955 922 | 179 060 414 | 168 131 174 | 1 661 968 | 74 840 | – | – |
| nondeterministic::nondeterministic::npa_witness::empty_npa_1000 | 9 427 737 | 13 979 095 | 13 247 670 | 123 248 | 3 291 | – | – |
| nondeterministic::nondeterministic::npa_witness::empty_npa_4000 | 38 265 192 | 57 449 786 | 53 485 891 | 657 399 | 19 340 | – | – |
| nondeterministic::nondeterministic::npa_witness::npa_1000 | 2 979 072 | 4 478 275 | 4 313 255 | 20 782 | 1 746 | – | – |
| nondeterministic::nondeterministic::npa_witness::npa_4000 | 23 816 129 | 35 551 463 | 34 340 098 | 178 013 | 9 180 | – | – |
| nondeterministic::nondeterministic::nra_witness::nra_4000 | 21 455 583 | 32 710 089 | 30 163 374 | 337 227 | 24 588 | – | – |
| runs::runs::dfa_accepts_many_words::count_1000 | 4 053 182 | 5 005 868 | 4 981 603 | 4 790 | 9 | 0 | 0 |
| runs::runs::dfa_accepts_one_word::len_100 | 3 561 | 4 886 | 4 451 | 38 | 7 | 0 | 0 |
| runs::runs::dfa_accepts_one_word::len_10000 | 276 039 | 339 515 | 335 780 | 698 | 7 | 0 | 0 |
| runs::runs::dfa_accepts_one_word::len_100000 | 2 750 700 | 3 376 813 | 3 344 663 | 6 325 | 15 | 0 | 0 |
| runs::runs::dfa_reached_state::count_1000 | 3 442 180 | 4 272 865 | 4 248 600 | 4 790 | 9 | 0 | 0 |
| runs::runs::dpa_accepts_lassos::long | 8 225 405 | 10 785 678 | 10 761 108 | 3 122 | 256 | 724 664 | 500 |
| runs::runs::dpa_accepts_lassos::short | 376 801 | 502 418 | 497 083 | 402 | 95 | 26 236 | 472 |
| runs::runs::dpa_recurrent_edge_colors::long | 15 221 636 | 19 507 710 | 19 456 480 | 5 843 | 629 | 922 144 | 2 090 |
| runs::runs::dpa_recurrent_edge_colors::short | 1 058 624 | 1 435 548 | 1 424 293 | 1 250 | 143 | 168 684 | 1 708 |
| runs::runs::dpa_recurrent_states::long | 13 767 740 | 19 256 422 | 19 225 872 | 3 653 | 351 | 788 104 | 860 |
| runs::runs::dpa_recurrent_states::short | 596 810 | 814 701 | 807 316 | 553 | 132 | 81 996 | 782 |
| runs::runs::dpa_visited_sequences::long | 8 707 283 | 12 042 555 | 12 009 575 | 4 279 | 331 | 2 190 780 | 850 |
| runs::runs::dpa_visited_sequences::short | 350 418 | 483 834 | 479 184 | 503 | 61 | 29 986 | 545 |
| runs::runs::fixture_accepts_lassos::ltl | 7 833 947 | 11 053 548 | 11 022 408 | 5 549 | 97 | – | – |
| runs::runs::fixture_accepts_lassos::synthetic | 4 309 057 | 6 188 492 | 6 136 857 | 9 627 | 100 | – | – |
| scc::scc::scc_queries::small_cycles_1000 | 855 946 | 1 334 674 | 1 174 024 | 9 436 | 3 242 | 261 132 | 559 |
| scc::scc::scc_queries::small_cycles_4000 | 3 348 761 | 5 268 920 | 4 585 400 | 50 891 | 12 259 | 1 045 396 | 2 071 |
| scc::scc::tarjan::back_edges_1000 | 493 252 | 795 135 | 684 570 | 5 467 | 2 378 | 170 272 | 45 |
| scc::scc::tarjan::back_edges_4000 | 1 914 660 | 3 101 390 | 2 656 010 | 26 447 | 8 947 | 680 632 | 53 |
| scc::scc::tarjan::binary_tree_1000 | 551 319 | 848 324 | 771 934 | 4 078 | 1 600 | 105 760 | 39 |
| scc::scc::tarjan::binary_tree_4000 | 2 212 941 | 3 410 014 | 3 104 544 | 21 138 | 5 708 | 419 512 | 45 |
| scc::scc::tarjan::fragmented_1000 | 626 713 | 981 364 | 858 184 | 9 656 | 2 140 | 146 084 | 121 |
| scc::scc::tarjan::fragmented_4000 | 2 413 515 | 3 877 549 | 3 297 114 | 62 845 | 7 606 | 569 852 | 167 |
| scc::scc::tarjan::grid_1024 | 575 645 | 926 563 | 802 903 | 7 743 | 2 427 | 171 160 | 45 |
| scc::scc::tarjan::grid_4096 | 2 299 205 | 3 824 759 | 3 187 829 | 63 672 | 9 102 | 684 184 | 53 |
| scc::scc::tarjan::path_1000 | 1 735 137 | 2 678 460 | 2 380 255 | 23 206 | 5 205 | 455 224 | 2 064 |
| scc::scc::tarjan::path_4000 | 6 859 748 | 10 607 265 | 9 411 220 | 98 320 | 20 127 | 1 821 536 | 8 076 |
| scc::scc::tarjan::ring_1000 | 493 252 | 798 771 | 683 661 | 6 376 | 2 378 | 170 272 | 45 |
| scc::scc::tarjan::ring_4000 | 1 914 660 | 3 118 638 | 2 651 698 | 30 759 | 8 947 | 680 632 | 53 |
| scc::scc::tarjan::scrambled_1000 | 559 051 | 892 093 | 780 128 | 6 986 | 2 201 | 170 272 | 45 |
| scc::scc::tarjan::scrambled_4000 | 2 238 975 | 3 618 654 | 3 124 914 | 41 873 | 8 125 | 680 632 | 53 |
| scc::scc::tarjan::small_cycles_1000 | 854 928 | 1 333 299 | 1 172 739 | 9 446 | 3 238 | 261 132 | 559 |
| scc::scc::tarjan::small_cycles_4000 | 3 344 743 | 5 261 129 | 4 581 024 | 50 243 | 12 254 | 1 045 396 | 2 071 |
| scc::scc::tarjan_from::fragmented_1000 | 232 901 | 373 990 | 324 880 | 2 549 | 1 039 | 74 985 | 64 |
| scc::scc::tarjan_from::fragmented_4000 | 872 519 | 1 416 622 | 1 221 482 | 15 956 | 3 296 | 299 625 | 78 |
| scc::scc::tarjan_from::path_1000 | 1 724 740 | 2 664 485 | 2 369 140 | 23 061 | 5 144 | 468 993 | 2 091 |
| scc::scc::tarjan_from::path_4000 | 6 763 890 | 10 521 572 | 9 291 232 | 106 761 | 19 901 | 1 876 753 | 8 109 |
| scc::scc::tarjan_from::ring_1000 | 482 362 | 790 400 | 672 060 | 6 266 | 2 486 | 184 041 | 72 |
| scc::scc::tarjan_from::scrambled_1000 | 548 161 | 882 310 | 768 880 | 6 523 | 2 309 | 184 041 | 72 |
| storage::storage::add_edges_dense::k2_5000 | 1 390 812 | 2 084 726 | 2 039 536 | 4 936 | 586 | 180 200 | 37 |
| storage::storage::add_edges_dense::k8_5000 | 4 311 427 | 6 496 049 | 6 309 524 | 17 831 | 2 782 | 671 728 | 40 |
| storage::storage::add_edges_linked::k2_5000 | 1 252 451 | 2 165 062 | 2 003 042 | 14 218 | 2 598 | 1 113 960 | 26 |
| storage::storage::add_edges_linked::k8_5000 | 6 144 063 | 10 329 624 | 9 400 509 | 75 755 | 15 724 | 3 866 496 | 28 |
| storage::storage::clone_csr::k2_10000 | 22 537 | 76 085 | 42 575 | 6 618 | 12 | 210 012 | 4 |
| storage::storage::clone_dense::k2_10000 | 15 042 | 81 072 | 25 732 | 2 248 | 1 260 | 110 008 | 4 |
| storage::storage::clone_linked::k2_10000 | 380 760 | 911 493 | 539 733 | 12 465 | 8 841 | 680 008 | 3 |
| storage::storage::complete_dense::partial_5000 | 230 702 | 348 722 | 343 457 | 885 | 24 | 56 | 1 |
| storage::storage::complete_linked::partial_5000 | 1 183 129 | 1 690 433 | 1 602 968 | 6 944 | 1 507 | 65 592 | 15 |
| storage::storage::edges_from_all_states_csr::k2_2000 | 34 038 | 38 328 | 38 043 | 29 | 4 | 0 | 0 |
| storage::storage::edges_from_all_states_csr::k8_2000 | 34 038 | 38 628 | 37 968 | 104 | 4 | 0 | 0 |
| storage::storage::edges_from_all_states_dense::k2_2000 | 92 047 | 101 257 | 99 847 | 233 | 7 | 0 | 0 |
| storage::storage::edges_from_all_states_dense::k8_2000 | 128 047 | 140 511 | 135 041 | 1 038 | 8 | 0 | 0 |
| storage::storage::edges_from_all_states_linked::k2_2000 | 70 033 | 88 755 | 77 925 | 2 131 | 5 | 0 | 0 |
| storage::storage::edges_from_all_states_linked::k8_2000 | 154 033 | 205 731 | 168 681 | 7 375 | 5 | 0 | 0 |
| storage::storage::minimize_csr::redundant_2000 | 4 240 645 | 6 376 529 | 5 902 609 | 60 603 | 4 883 | 1 505 420 | 2 212 |
| storage::storage::minimize_csr::redundant_8000 | 16 584 073 | 25 284 397 | 23 034 757 | 275 488 | 24 920 | 6 023 300 | 8 250 |
| storage::storage::minimize_dense::redundant_2000 | 4 434 823 | 6 603 981 | 6 149 506 | 58 044 | 4 693 | 1 522 156 | 2 221 |
| storage::storage::minimize_dense::redundant_8000 | 17 408 185 | 26 418 899 | 24 122 739 | 278 891 | 25 763 | 6 090 340 | 8 261 |
| storage::storage::minimize_linked::redundant_2000 | 4 305 957 | 6 557 531 | 6 009 161 | 61 850 | 6 832 | 1 522 156 | 2 221 |
| storage::storage::minimize_linked::redundant_8000 | 16 930 017 | 26 057 752 | 23 610 767 | 302 700 | 26 671 | 6 090 340 | 8 261 |
| storage::storage::overwrite_edges_dense::k2_5000 | 2 170 843 | 3 296 781 | 3 236 621 | 7 909 | 589 | 180 200 | 37 |
| storage::storage::overwrite_edges_linked::k2_5000 | 3 410 553 | 6 005 649 | 5 286 679 | 44 751 | 14 149 | 2 031 464 | 27 |
| storage::storage::predecessors_of_all_states_csr::k2_2000 | 251 025 | 342 244 | 316 539 | 4 959 | 26 | 48 008 | 3 |
| storage::storage::predecessors_of_all_states_dense::k2_2000 | 232 309 | 311 709 | 302 159 | 1 616 | 42 | 32 008 | 3 |
| storage::storage::predecessors_of_all_states_linked::k2_2000 | 70 033 | 93 657 | 76 692 | 3 365 | 4 | 0 | 0 |
| storage::storage::product_successor_csr::n200 | 48 082 | 58 507 | 58 107 | 38 | 6 | 0 | 0 |
| storage::storage::product_successor_dense::n200 | 65 088 | 76 567 | 76 122 | 40 | 7 | 0 | 0 |
| storage::storage::product_successor_linked::n200 | 46 540 | 60 130 | 56 995 | 585 | 6 | 0 | 0 |
| storage::storage::reachable_states_csr::k2_8000 | 988 709 | 1 471 287 | 1 410 827 | 11 896 | 28 | 17 368 | 11 |
| storage::storage::reachable_states_dense::k2_8000 | 1 173 507 | 1 692 012 | 1 646 962 | 8 835 | 25 | 17 368 | 11 |
| storage::storage::reachable_states_linked::k2_8000 | 980 094 | 1 509 063 | 1 410 258 | 19 516 | 35 | 17 368 | 11 |
| storage::storage::remove_state_dense::k2_10000 | 924 162 | 1 347 826 | 1 173 246 | 21 511 | 1 915 | 176 000 | 1 003 |
| storage::storage::remove_state_linked::k2_10000 | 997 019 | 1 358 213 | 1 319 763 | 7 417 | 39 | 80 000 | 3 000 |
| storage::storage::run_many_words_csr::count_1000 | 504 041 | 624 024 | 614 144 | 1 934 | 6 | 0 | 0 |
| storage::storage::run_many_words_dense::count_1000 | 512 042 | 601 929 | 592 164 | 1 911 | 6 | 0 | 0 |
| storage::storage::run_many_words_linked::count_1000 | 481 040 | 611 107 | 601 112 | 1 957 | 6 | 0 | 0 |
| storage::storage::run_one_word_csr::len_100000 | 2 450 042 | 3 025 395 | 2 993 795 | 6 285 | 5 | 0 | 0 |
| storage::storage::run_one_word_dense::len_100000 | 2 600 042 | 3 025 345 | 2 993 800 | 6 274 | 5 | 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 | 96 205 | 117 081 | 113 641 | 646 | 6 | 8 | 1 |
| storage::storage::successor_all_pairs_csr::k8_2000 | 510 259 | 627 149 | 616 199 | 2 148 | 6 | 32 | 1 |
| storage::storage::successor_all_pairs_dense::k2_2000 | 150 205 | 169 478 | 168 048 | 237 | 7 | 8 | 1 |
| storage::storage::successor_all_pairs_dense::k8_2000 | 778 259 | 880 782 | 875 297 | 1 048 | 7 | 32 | 1 |
| storage::storage::successor_all_pairs_linked::k2_2000 | 110 202 | 141 070 | 130 135 | 2 138 | 7 | 8 | 1 |
| storage::storage::successor_all_pairs_linked::k8_2000 | 752 256 | 948 110 | 910 950 | 7 383 | 7 | 32 | 1 |
| ts::ts::add_edges_in_order::k2_5000 | 1 062 446 | 1 774 972 | 1 613 037 | 14 215 | 2 596 | 1 113 960 | 26 |
| ts::ts::add_edges_in_order::k8_5000 | 5 384 058 | 8 769 462 | 7 840 522 | 75 734 | 15 722 | 3 866 496 | 28 |
| ts::ts::add_edges_in_reverse::k2_5000 | 1 062 446 | 1 774 180 | 1 613 235 | 14 017 | 2 596 | 1 113 960 | 26 |
| ts::ts::builder_with_edges::k2_5000 | 79 938 740 | 95 907 151 | 93 436 991 | 450 485 | 6 221 | 1 739 532 | 45 |
| ts::ts::canonical_naming::scrambled_1500 | 3 034 522 | 4 445 169 | 4 255 454 | 21 871 | 2 296 | 463 808 | 5 846 |
| ts::ts::canonical_naming::scrambled_500 | 938 266 | 1 350 758 | 1 307 583 | 3 175 | 780 | 134 336 | 1 831 |
| ts::ts::clone::scrambled_10000 | 381 079 | 912 268 | 540 138 | 12 483 | 8 849 | 680 008 | 3 |
| ts::ts::clone::scrambled_40000 | 1 521 316 | 3 857 681 | 2 156 706 | 42 576 | 42 517 | 2 720 008 | 3 |
| ts::ts::collect_dts::scrambled_10000 | 2 934 925 | 5 185 584 | 4 626 499 | 37 169 | 10 664 | 2 228 064 | 27 |
| ts::ts::collect_dts::scrambled_40000 | 11 679 372 | 20 762 632 | 18 409 072 | 135 300 | 47 916 | 8 912 736 | 31 |
| ts::ts::determinize::nth_from_end_10 | 4 305 680 | 6 339 242 | 5 978 947 | 22 093 | 7 138 | 651 720 | 6 013 |
| ts::ts::determinize::nth_from_end_12 | 19 177 588 | 28 064 700 | 26 556 095 | 98 791 | 28 990 | 2 732 600 | 26 423 |
| ts::ts::determinize::nth_from_end_8 | 980 440 | 1 446 599 | 1 364 229 | 2 992 | 1 926 | 156 552 | 1 396 |
| ts::ts::determinize_propositional::aps_6_n_6 | 4 088 248 | 6 427 459 | 5 941 679 | 20 030 | 11 018 | 1 332 896 | 4 208 |
| ts::ts::determinize_propositional::aps_7_n_6 | 4 295 587 | 6 716 468 | 6 179 163 | 25 316 | 11 735 | 1 197 930 | 1 967 |
| ts::ts::determinize_propositional::aps_8_n_6 | 25 052 413 | 38 429 955 | 35 513 095 | 168 370 | 59 286 | 5 240 456 | 13 678 |
| ts::ts::edges_from_all_states::scrambled_2000 | 74 646 | 93 978 | 82 738 | 2 157 | 13 | 0 | 0 |
| ts::ts::edges_from_all_states::scrambled_k8_2000 | 158 578 | 210 859 | 173 394 | 7 402 | 13 | 0 | 0 |
| ts::ts::erase_state_colors_collect::scrambled_10000 | 1 846 855 | 3 177 597 | 2 618 447 | 37 175 | 10 665 | 2 228 064 | 27 |
| ts::ts::into_dfa::scrambled_10000 | 3 054 983 | 5 375 920 | 4 816 590 | 37 183 | 10 669 | 2 228 064 | 27 |
| ts::ts::map_edge_colors_collect::scrambled_10000 | 1 928 468 | 3 407 504 | 2 789 159 | 38 451 | 12 174 | 2 490 192 | 27 |
| ts::ts::map_edge_colors_collect::scrambled_40000 | 7 655 047 | 13 651 456 | 11 061 741 | 140 335 | 53 944 | 9 961 296 | 31 |
| ts::ts::matching_product_successor_index::n200 | 47 602 | 62 598 | 58 423 | 597 | 34 | 0 | 0 |
| ts::ts::minimal_representative_of_all_states::scrambled_100 | 2 002 068 | 2 856 122 | 2 852 767 | 13 | 94 | 347 504 | 4 679 |
| ts::ts::minimal_representative_of_all_states::scrambled_300 | 16 088 404 | 23 069 254 | 23 054 089 | 2 354 | 97 | 3 116 784 | 38 196 |
| ts::ts::minimal_representatives::scrambled_2000 | 3 248 796 | 4 585 532 | 4 538 727 | 8 920 | 63 | 322 944 | 7 709 |
| ts::ts::minimal_representatives::scrambled_8000 | 14 321 191 | 20 180 453 | 19 965 688 | 42 575 | 54 | 1 464 896 | 32 693 |
| ts::ts::predecessors_of_all_states::scrambled_2000 | 74 646 | 98 850 | 81 505 | 3 392 | 11 | 0 | 0 |
| ts::ts::predecessors_of_all_states::scrambled_8000 | 296 578 | 397 297 | 321 777 | 15 020 | 12 | 0 | 0 |
| ts::ts::reachable_states::scrambled_2000 | 243 901 | 374 295 | 353 730 | 3 609 | 72 | 4 336 | 9 |
| ts::ts::reachable_states::scrambled_8000 | 964 480 | 1 493 862 | 1 394 777 | 19 523 | 42 | 17 368 | 11 |
| ts::ts::remove_edges_from_matching::scrambled_10000 | 446 232 | 589 810 | 565 655 | 4 656 | 25 | 64 000 | 2 000 |
| ts::ts::remove_edges_from_matching::scrambled_40000 | 746 232 | 941 310 | 890 280 | 10 031 | 25 | 64 000 | 2 000 |
| ts::ts::remove_state::scrambled_10000 | 997 019 | 1 358 319 | 1 319 759 | 7 418 | 42 | 80 000 | 3 000 |
| ts::ts::remove_state::scrambled_40000 | 1 357 019 | 1 772 783 | 1 703 643 | 13 534 | 42 | 80 000 | 3 000 |
| ts::ts::scc_minimal_representatives::small_cycles_100 | 210 321 | 304 069 | 289 569 | 44 | 408 | 44 272 | 309 |
| ts::ts::scc_minimal_representatives::small_cycles_400 | 1 192 086 | 1 679 371 | 1 629 931 | 3 889 | 857 | 354 148 | 1 325 |
| ts::ts::subset_construction::nth_from_end_10 | 9 439 133 | 13 173 435 | 12 681 495 | 45 279 | 7 587 | 1 073 520 | 9 919 |
| ts::ts::subset_construction::nth_from_end_12 | 42 061 900 | 58 466 837 | 56 225 962 | 218 204 | 32 853 | 4 518 976 | 43 857 |
| ts::ts::subset_construction::nth_from_end_8 | 2 040 011 | 2 862 504 | 2 756 754 | 6 051 | 2 157 | 257 104 | 2 276 |
| ts::ts::successor_index_all_pairs::scrambled_2000 | 110 814 | 142 232 | 130 952 | 2 158 | 14 | 8 | 1 |
| ts::ts::successor_index_all_pairs::scrambled_k8_2000 | 752 800 | 949 211 | 911 666 | 7 404 | 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.66 ms (3.63 ms … 3.70 ms) |
| collect/clone/1000000 | 37.76 ms (36.73 ms … 38.79 ms) |
| collect/collect_owned/100000 | 6.43 ms (6.43 ms … 6.43 ms) |
| collect/collect_owned/1000000 | 74.59 ms (73.17 ms … 76.00 ms) |
| collect/collect_ref/100000 | 4.10 ms (3.99 ms … 4.22 ms) |
| collect/collect_ref/1000000 | 80.30 ms (78.53 ms … 82.07 ms) |
| collect/map_edge_colors_collect_owned/100000 | 7.01 ms (6.97 ms … 7.05 ms) |
| collect/map_edge_colors_collect_owned/1000000 | 71.56 ms (70.21 ms … 72.91 ms) |
| wallclock/dfa/accepts/word_100000 | 828.28 µs (827.51 µs … 829.05 µs) |
| wallclock/dfa/minimize/redundant_4000 | 1.32 ms (1.30 ms … 1.34 ms) |
| wallclock/dpa/complement/scrambled_4000 | 3.36 ms (3.34 ms … 3.39 ms) |
| wallclock/dpa/normalized/scrambled_4000 | 3.08 ms (3.05 ms … 3.11 ms) |
| wallclock/hoa/parse/ltl | 776.52 µs (775.95 µs … 777.10 µs) |
| wallclock/nfa/determinize/nth_from_end_12 | 3.01 ms (2.97 ms … 3.05 ms) |
| wallclock/nfa/subset_construction/nth_from_end_12 | 6.45 ms (6.32 ms … 6.59 ms) |
| wallclock/scc/tarjan/scrambled_10000 | 1.93 ms (1.88 ms … 1.98 ms) |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| hard/l-dsa-3 | spot | 122.58 µs | 117.70 µs | 1.04× | – / – | yes |
| hard/l-nba-2 | spot | 56.20 µs | 37.44 µs | 1.50× | – / – | yes |
| hard/m-nba-3 | spot | 238.82 µs | 140.78 µs | 1.70× | – / – | yes |
| ltl/and-gf-3 | spot | 9.16 µs | 12.98 µs | 0.71× | – / – | yes |
| ltl/eh-patterns-0 | spot | 21.78 µs | 20.94 µs | 1.04× | – / – | yes |
| ltl/gf-equiv-3 | spot | 20.04 µs | 34.12 µs | 0.59× | – / – | yes |
| ltl/gf-implies-3 | spot | 10.68 µs | 19.90 µs | 0.54× | – / – | yes |
| ltl/gh-q-3 | spot | 50.76 µs | 30.14 µs | 1.68× | – / – | yes |
| ltl/gh-r-3 | spot | 20.76 µs | 68.50 µs | 0.30× | – / – | yes |
| ltl/go-theta-3 | spot | 11.20 µs | 22.00 µs | 0.51× | – / – | yes |
| ltl/lily-patterns-1 | spot | 12.34 µs | 16.58 µs | 0.74× | – / – | yes |
| ltl/ms-phi-r-1 | spot | 10.22 µs | 38.62 µs | 0.26× | – / – | yes |
| ltl/ms-phi-s-1 | spot | 10.48 µs | 41.02 µs | 0.26× | – / – | yes |
| ltl/rv-counter-3 | spot | 28.78 µs | 14.28 µs | 2.02× | – / – | yes |
| ltl/sb-patterns-0 | spot | 12.46 µs | 14.68 µs | 0.85× | – / – | yes |
| ltl/sejk-k-2 | spot | 13.48 µs | 58.24 µs | 0.23× | – / – | yes |
| ltl/tv-uu-3 | spot | 41.32 µs | 39.36 µs | 1.05× | – / – | yes |
| ltl/u-left-3 | spot | 10.56 µs | 9.36 µs | 1.13× | – / – | yes |
| many_aps/and-gf-12 | spot | 168.96 µs | 76.56 µs | 2.21× | – / – | yes |
| many_aps/gf-equiv-12 | spot | 131.12 µs | 91.96 µs | 1.43× | – / – | yes |
| many_aps/r-right-10 | spot | 66.88 µs | 26.88 µs | 2.49× | – / – | yes |
| many_aps/random-n16-a8-p4-s1 | spot | 269.88 µs | 136.08 µs | 1.98× | – / – | yes |
| many_aps/random-n24-a12-p4-s1 | spot | 1.18 ms | 448.70 µs | 2.62× | – / – | yes |
| many_aps/random-n32-a16-p4-s1 | spot | 3.86 ms | 1.23 ms | 3.13× | – / – | yes |
| random/n128-a2-p6-s1 | spot | 338.82 µs | 215.86 µs | 1.57× | – / – | yes |
| random/n16-a1-p3-s1 | spot | 22.88 µs | 16.76 µs | 1.37× | – / – | yes |
| random/n256-a2-p8-s1 | spot | 891.45 µs | 489.03 µs | 1.82× | – / – | yes |
| random/n64-a2-p4-s1 | spot | 141.46 µs | 101.86 µs | 1.39× | – / – | yes |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| hard/l-dsa-3 | spot | 71.66 µs | 62.14 µs | 1.15× | – / – | yes |
| hard/l-nba-2 | spot | 35.82 µs | 24.40 µs | 1.47× | – / – | yes |
| hard/m-nba-3 | spot | 148.08 µs | 91.18 µs | 1.62× | – / – | yes |
| ltl/and-gf-3 | spot | 5.90 µs | 8.66 µs | 0.68× | – / – | yes |
| ltl/eh-patterns-0 | spot | 14.28 µs | 17.90 µs | 0.80× | – / – | yes |
| ltl/gf-equiv-3 | spot | 11.42 µs | 19.08 µs | 0.60× | – / – | yes |
| ltl/gf-implies-3 | spot | 6.32 µs | 11.58 µs | 0.55× | – / – | yes |
| ltl/gh-q-3 | spot | 33.12 µs | 29.06 µs | 1.14× | – / – | yes |
| ltl/gh-r-3 | spot | 12.32 µs | 34.86 µs | 0.35× | – / – | yes |
| ltl/go-theta-3 | spot | 6.86 µs | 16.04 µs | 0.43× | – / – | yes |
| ltl/lily-patterns-1 | spot | 8.04 µs | 13.98 µs | 0.58× | – / – | yes |
| ltl/ms-phi-r-1 | spot | 6.04 µs | 19.24 µs | 0.31× | – / – | yes |
| ltl/ms-phi-s-1 | spot | 6.12 µs | 25.32 µs | 0.24× | – / – | yes |
| ltl/rv-counter-3 | spot | 18.08 µs | 14.52 µs | 1.25× | – / – | yes |
| ltl/sb-patterns-0 | spot | 7.64 µs | 12.12 µs | 0.63× | – / – | yes |
| ltl/sejk-k-2 | spot | 7.84 µs | 28.00 µs | 0.28× | – / – | yes |
| ltl/tv-uu-3 | spot | 28.46 µs | 30.08 µs | 0.95× | – / – | yes |
| ltl/u-left-3 | spot | 6.72 µs | 8.68 µs | 0.77× | – / – | yes |
| many_aps/and-gf-12 | spot | 125.80 µs | 54.50 µs | 2.31× | – / – | yes |
| many_aps/gf-equiv-12 | spot | 74.80 µs | 53.08 µs | 1.41× | – / – | yes |
| many_aps/r-right-10 | spot | 49.00 µs | 25.78 µs | 1.90× | – / – | yes |
| many_aps/random-n16-a8-p4-s1 | spot | 223.70 µs | 100.84 µs | 2.22× | – / – | yes |
| many_aps/random-n24-a12-p4-s1 | spot | 1.12 ms | 396.64 µs | 2.83× | – / – | yes |
| many_aps/random-n32-a16-p4-s1 | spot | 3.80 ms | 1.12 ms | 3.39× | – / – | yes |
| random/n128-a2-p6-s1 | spot | 198.46 µs | 128.34 µs | 1.55× | – / – | yes |
| random/n16-a1-p3-s1 | spot | 13.46 µs | 10.80 µs | 1.25× | – / – | yes |
| random/n256-a2-p8-s1 | spot | 512.25 µs | 317.64 µs | 1.61× | – / – | yes |
| random/n64-a2-p4-s1 | spot | 87.22 µs | 65.72 µs | 1.33× | – / – | yes |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| ladder_10000 | oink-ppp | 2.75 ms | 328.00 µs | 8.39× | 10000 / 10000 | yes |
| ladder_10000 | oink-zlk | 2.75 ms | 335.00 µs | 8.21× | 10000 / 10000 | yes |
| ladder_10000 | spot | 2.75 ms | 10.17 ms | 0.27× | 10000 / 10000 | yes |
| ladder_50000 | oink-ppp | 18.93 ms | 2.12 ms | 8.92× | 50000 / 50000 | yes |
| ladder_50000 | oink-zlk | 18.93 ms | 2.47 ms | 7.66× | 50000 / 50000 | yes |
| ladder_50000 | spot | 18.93 ms | 77.59 ms | 0.24× | 50000 / 50000 | yes |
| random_few_10000 | oink-ppp | 6.98 ms | 1.46 ms | 4.80× | 10000 / 10000 | yes |
| random_few_10000 | oink-zlk | 6.98 ms | 2.76 ms | 2.53× | 10000 / 10000 | yes |
| random_few_10000 | spot | 6.98 ms | 21.11 ms | 0.33× | 10000 / 10000 | yes |
| random_few_50000 | oink-ppp | 77.03 ms | 16.00 ms | 4.81× | 50000 / 50000 | yes |
| random_few_50000 | oink-zlk | 77.03 ms | 20.71 ms | 3.72× | 50000 / 50000 | yes |
| random_few_50000 | spot | 77.03 ms | 679.94 ms | 0.11× | 50000 / 50000 | yes |
| random_many_10000 | oink-ppp | 6.31 ms | 1.64 ms | 3.84× | 10000 / 10000 | yes |
| random_many_10000 | oink-zlk | 6.31 ms | 3.04 ms | 2.07× | 10000 / 10000 | yes |
| random_many_10000 | spot | 6.31 ms | 29.88 ms | 0.21× | 10000 / 10000 | yes |
| random_many_50000 | oink-ppp | 82.90 ms | 35.20 ms | 2.35× | 50000 / 50000 | yes |
| random_many_50000 | oink-zlk | 82.90 ms | 51.28 ms | 1.62× | 50000 / 50000 | yes |
| random_many_50000 | spot | 82.90 ms | 779.68 ms | 0.11× | 50000 / 50000 | yes |
== head c432f0685d5caae9cbf90860f1c1bfc53ac51ae5: 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 4m 14s
Executable benches/dfa.rs (/var/lib/automata-bench/work/target-head/release/deps/dfa-c46c79a89c1c2941)
Executable benches/dpa.rs (/var/lib/automata-bench/work/target-head/release/deps/dpa-0b05141996aaf468)
Executable benches/game.rs (/var/lib/automata-bench/work/target-head/release/deps/game-fc166083591c2309)
Executable benches/learning.rs (/var/lib/automata-bench/work/target-head/release/deps/learning-72c8d077fb858ea9)
Executable benches/nondeterministic.rs (/var/lib/automata-bench/work/target-head/release/deps/nondeterministic-e95514e1aa52b38c)
Executable benches/runs.rs (/var/lib/automata-bench/work/target-head/release/deps/runs-3b37aa113a4e75ae)
Executable benches/scc.rs (/var/lib/automata-bench/work/target-head/release/deps/scc-b88e81c5af8ec1fc)
Executable benches/storage.rs (/var/lib/automata-bench/work/target-head/release/deps/storage-fffb4b0cac4d81af)
Executable benches/ts.rs (/var/lib/automata-bench/work/target-head/release/deps/ts-bb6ee25ff0b06f0f)
Executable benches/wallclock.rs (/var/lib/automata-bench/work/target-head/release/deps/wallclock-3b599e26071f9e69)
== head: running scc
Finished `bench` profile [optimized] target(s) in 0.63s
Running benches/scc.rs (/var/lib/automata-bench/work/target-head/release/deps/scc-b88e81c5af8ec1fc)
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.21s
Running benches/ts.rs (/var/lib/automata-bench/work/target-head/release/deps/ts-bb6ee25ff0b06f0f)
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.26s
Running benches/runs.rs (/var/lib/automata-bench/work/target-head/release/deps/runs-3b37aa113a4e75ae)
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.22s
Running benches/dfa.rs (/var/lib/automata-bench/work/target-head/release/deps/dfa-c46c79a89c1c2941)
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.18s
Running benches/dpa.rs (/var/lib/automata-bench/work/target-head/release/deps/dpa-0b05141996aaf468)
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.20s
Running benches/storage.rs (/var/lib/automata-bench/work/target-head/release/deps/storage-fffb4b0cac4d81af)
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.18s
Running benches/nondeterministic.rs (/var/lib/automata-bench/work/target-head/release/deps/nondeterministic-e95514e1aa52b38c)
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.19s
Running benches/learning.rs (/var/lib/automata-bench/work/target-head/release/deps/learning-72c8d077fb858ea9)
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.19s
Running benches/game.rs (/var/lib/automata-bench/work/target-head/release/deps/game-fc166083591c2309)
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.19s
Running benches/wallclock.rs (/var/lib/automata-bench/work/target-head/release/deps/wallclock-3b599e26071f9e69)
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 7m 33s
📦 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.123 ms / 0.118 ms
dpa/equivalence/hard/l-nba-2 vs spot: 0.056 ms / 0.037 ms
dpa/equivalence/hard/m-nba-3 vs spot: 0.239 ms / 0.141 ms
dpa/equivalence/ltl/and-gf-3 vs spot: 0.009 ms / 0.013 ms
dpa/equivalence/ltl/eh-patterns-0 vs spot: 0.022 ms / 0.021 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.051 ms / 0.030 ms
dpa/equivalence/ltl/gh-r-3 vs spot: 0.021 ms / 0.069 ms
dpa/equivalence/ltl/go-theta-3 vs spot: 0.011 ms / 0.022 ms
dpa/equivalence/ltl/lily-patterns-1 vs spot: 0.012 ms / 0.017 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.029 ms / 0.014 ms
dpa/equivalence/ltl/sb-patterns-0 vs spot: 0.012 ms / 0.015 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.039 ms
dpa/equivalence/ltl/u-left-3 vs spot: 0.011 ms / 0.009 ms
dpa/equivalence/many_aps/and-gf-12 vs spot: 0.169 ms / 0.077 ms
dpa/equivalence/many_aps/gf-equiv-12 vs spot: 0.131 ms / 0.092 ms
dpa/equivalence/many_aps/r-right-10 vs spot: 0.067 ms / 0.027 ms
dpa/equivalence/many_aps/random-n16-a8-p4-s1 vs spot: 0.270 ms / 0.136 ms
dpa/equivalence/many_aps/random-n24-a12-p4-s1 vs spot: 1.176 ms / 0.449 ms
dpa/equivalence/many_aps/random-n32-a16-p4-s1 vs spot: 3.860 ms / 1.232 ms
dpa/equivalence/random/n128-a2-p6-s1 vs spot: 0.339 ms / 0.216 ms
dpa/equivalence/random/n16-a1-p3-s1 vs spot: 0.023 ms / 0.017 ms
dpa/equivalence/random/n256-a2-p8-s1 vs spot: 0.891 ms / 0.489 ms
dpa/equivalence/random/n64-a2-p4-s1 vs spot: 0.141 ms / 0.102 ms
dpa/inclusion/hard/l-dsa-3 vs spot: 0.072 ms / 0.062 ms
dpa/inclusion/hard/l-nba-2 vs spot: 0.036 ms / 0.024 ms
dpa/inclusion/hard/m-nba-3 vs spot: 0.148 ms / 0.091 ms
dpa/inclusion/ltl/and-gf-3 vs spot: 0.006 ms / 0.009 ms
dpa/inclusion/ltl/eh-patterns-0 vs spot: 0.014 ms / 0.018 ms
dpa/inclusion/ltl/gf-equiv-3 vs spot: 0.011 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.019 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.012 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.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.126 ms / 0.055 ms
dpa/inclusion/many_aps/gf-equiv-12 vs spot: 0.075 ms / 0.053 ms
dpa/inclusion/many_aps/r-right-10 vs spot: 0.049 ms / 0.026 ms
dpa/inclusion/many_aps/random-n16-a8-p4-s1 vs spot: 0.224 ms / 0.101 ms
dpa/inclusion/many_aps/random-n24-a12-p4-s1 vs spot: 1.121 ms / 0.397 ms
dpa/inclusion/many_aps/random-n32-a16-p4-s1 vs spot: 3.803 ms / 1.123 ms
dpa/inclusion/random/n128-a2-p6-s1 vs spot: 0.198 ms / 0.128 ms
dpa/inclusion/random/n16-a1-p3-s1 vs spot: 0.013 ms / 0.011 ms
dpa/inclusion/random/n256-a2-p8-s1 vs spot: 0.512 ms / 0.318 ms
dpa/inclusion/random/n64-a2-p4-s1 vs spot: 0.087 ms / 0.066 ms
game/solve/random_few_10000 vs spot: 6.982 ms / 21.110 ms
game/solve/random_few_10000 vs oink-zlk: 6.982 ms / 2.756 ms
game/solve/random_few_10000 vs oink-ppp: 6.982 ms / 1.456 ms
game/solve/random_few_50000 vs spot: 77.026 ms / 679.939 ms
game/solve/random_few_50000 vs oink-zlk: 77.026 ms / 20.713 ms
game/solve/random_few_50000 vs oink-ppp: 77.026 ms / 16.001 ms
game/solve/random_many_10000 vs spot: 6.311 ms / 29.880 ms
game/solve/random_many_10000 vs oink-zlk: 6.311 ms / 3.042 ms
game/solve/random_many_10000 vs oink-ppp: 6.311 ms / 1.643 ms
game/solve/random_many_50000 vs spot: 82.897 ms / 779.680 ms
game/solve/random_many_50000 vs oink-zlk: 82.897 ms / 51.280 ms
game/solve/random_many_50000 vs oink-ppp: 82.897 ms / 35.202 ms
game/solve/ladder_10000 vs spot: 2.751 ms / 10.168 ms
game/solve/ladder_10000 vs oink-zlk: 2.751 ms / 0.335 ms
game/solve/ladder_10000 vs oink-ppp: 2.751 ms / 0.328 ms
game/solve/ladder_50000 vs spot: 18.927 ms / 77.590 ms
game/solve/ladder_50000 vs oink-zlk: 18.927 ms / 2.472 ms
game/solve/ladder_50000 vs oink-ppp: 18.927 ms / 2.122 ms
== head: 266 benchmarks, 16 wall-clock measurements, 74 comparisons