History · Versus Spot and Oink
docs: drop obsolete entries from PERFORMANCE.md (#165)
status done · queued 2026-11-11 17:18 · started 2026-11-11 17:18 · finished 2026-11-11 17:38
· · 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 885 | 393 385 | 1 223 | 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 082 | 147 657 | 728 | 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 273 | 3 817 113 | 12 014 | 3 374 | 428 088 | 42 |
| dfa::dfa::intersection::scrambled_200 | 10 809 511 | 16 277 724 | 15 140 774 | 96 868 | 18 646 | 1 708 120 | 49 |
| dfa::dfa::intersection_is_empty::empty_100 | 50 659 | 79 041 | 72 531 | 35 | 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 318 | 4 604 643 | 39 732 | 5 029 | 1 135 492 | 2 214 |
| dfa::dfa::minimize::minimal_4000 | 12 876 089 | 19 609 314 | 17 952 604 | 204 572 | 18 110 | 4 543 724 | 8 254 |
| dfa::dfa::minimize::redundant_1000 | 2 174 551 | 3 263 168 | 3 028 278 | 25 887 | 3 013 | 760 780 | 1 201 |
| dfa::dfa::minimize::redundant_4000 | 8 406 754 | 12 753 344 | 11 696 774 | 143 617 | 9 671 | 3 044 900 | 4 241 |
| dfa::dfa::minimize::scrambled_1000 | 3 502 256 | 5 309 217 | 4 877 652 | 51 040 | 5 039 | 1 116 052 | 2 217 |
| dfa::dfa::minimize::scrambled_4000 | 13 587 258 | 20 978 230 | 18 872 885 | 294 026 | 18 149 | 4 470 140 | 8 261 |
| dfa::dfa::minimize_moore_with_edge_colors::scrambled_1000 | 3 500 317 | 5 293 004 | 4 866 639 | 50 098 | 5 025 | 1 116 052 | 2 217 |
| dfa::dfa::minimize_moore_with_edge_colors::scrambled_4000 | 13 571 891 | 20 909 140 | 18 808 240 | 300 578 | 17 086 | 4 470 140 | 8 261 |
| dfa::dfa::union::scrambled_100 | 2 716 048 | 3 995 273 | 3 817 113 | 12 014 | 3 374 | 428 088 | 42 |
| dfa::dfa::union::scrambled_200 | 10 809 511 | 16 277 720 | 15 140 775 | 96 867 | 18 646 | 1 708 120 | 49 |
| dpa::dpa::accepted_word::chain_100 | 114 774 | 174 778 | 162 978 | 50 | 330 | – | – |
| dpa::dpa::accepted_word::chain_400 | 391 265 | 589 357 | 555 062 | 2 967 | 556 | – | – |
| dpa::dpa::accepted_word::scrambled_100 | 145 660 | 218 233 | 206 028 | 40 | 343 | – | – |
| dpa::dpa::accepted_word::scrambled_400 | 499 945 | 740 793 | 707 773 | 2 817 | 541 | – | – |
| dpa::dpa::accepted_word_fixtures::ltl | 495 442 | 716 515 | 690 470 | 2 248 | 423 | – | – |
| dpa::dpa::accepted_word_fixtures::synthetic | 1 255 420 | 1 811 226 | 1 739 741 | 11 798 | 357 | – | – |
| dpa::dpa::accepted_word_fixtures_by_atoms::ltl | 1 620 528 | 2 381 547 | 2 324 047 | 7 671 | 547 | – | – |
| dpa::dpa::accepted_word_fixtures_by_atoms::synthetic | 2 741 079 | 4 051 521 | 3 966 981 | 13 128 | 540 | – | – |
| 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 444 | 5 221 069 | 55 163 | 6 416 | – | – |
| dpa::dpa::complement::chain_4000 | 15 498 940 | 23 452 276 | 21 213 691 | 262 014 | 26 529 | – | – |
| dpa::dpa::complement::scrambled_1000 | 4 640 280 | 6 873 586 | 6 331 486 | 62 514 | 6 558 | – | – |
| dpa::dpa::complement::scrambled_4000 | 18 790 501 | 28 240 194 | 25 579 294 | 344 027 | 26 879 | – | – |
| dpa::dpa::complement_fixtures::ltl | 1 318 752 | 1 878 320 | 1 840 340 | 4 810 | 398 | – | – |
| dpa::dpa::complement_fixtures::many_aps | 12 439 593 | 17 914 295 | 17 431 665 | 86 376 | 1 450 | – | – |
| dpa::dpa::complement_fixtures::synthetic | 9 051 767 | 12 765 566 | 12 268 556 | 96 441 | 423 | – | – |
| dpa::dpa::complement_without_normalizing::scrambled_1000 | 542 888 | 786 588 | 757 863 | 5 157 | 84 | – | – |
| dpa::dpa::complement_without_normalizing::scrambled_4000 | 2 135 235 | 3 133 799 | 2 979 554 | 21 966 | 1 269 | – | – |
| dpa::dpa::equivalent_fixtures::many_aps | 18 698 034 | 27 049 250 | 26 383 895 | 120 324 | 1 821 | – | – |
| dpa::dpa::hoa_parse::ltl | 5 102 006 | 7 693 373 | 7 405 213 | 35 617 | 3 145 | – | – |
| dpa::dpa::hoa_parse::many_aps | 80 066 835 | 132 200 341 | 115 009 426 | 290 122 | 449 723 | – | – |
| dpa::dpa::hoa_parse::synthetic | 23 303 319 | 35 262 960 | 33 885 730 | 175 325 | 14 303 | – | – |
| dpa::dpa::hoa_print::ltl | 14 449 248 | 31 516 462 | 19 332 332 | 7 343 | 347 069 | – | – |
| dpa::dpa::hoa_print::many_aps | 17 708 492 | 25 469 855 | 25 318 210 | 27 928 | 343 | – | – |
| dpa::dpa::hoa_print::synthetic | 21 972 183 | 42 634 433 | 30 233 398 | 37 557 | 348 950 | – | – |
| dpa::dpa::included_fixtures::many_aps | 15 907 783 | 23 119 513 | 22 585 733 | 94 401 | 1 765 | – | – |
| dpa::dpa::included_in::complement_100 | 260 739 | 388 049 | 371 329 | 845 | 357 | – | – |
| dpa::dpa::included_in::complement_25 | 84 611 | 131 494 | 119 159 | 80 | 341 | – | – |
| dpa::dpa::included_in::complement_50 | 146 080 | 219 879 | 206 694 | 313 | 332 | – | – |
| dpa::dpa::included_in::normalized_100 | 524 060 | 764 006 | 738 441 | 1 396 | 531 | – | – |
| dpa::dpa::included_in::normalized_25 | 177 925 | 261 399 | 249 524 | 156 | 317 | – | – |
| dpa::dpa::included_in::normalized_50 | 302 723 | 439 883 | 425 518 | 374 | 357 | – | – |
| dpa::dpa::language_equivalent::complement_100 | 268 661 | 397 813 | 380 478 | 870 | 371 | – | – |
| dpa::dpa::language_equivalent::complement_25 | 86 600 | 134 349 | 121 479 | 89 | 355 | – | – |
| dpa::dpa::language_equivalent::complement_50 | 149 885 | 224 791 | 211 036 | 329 | 346 | – | – |
| dpa::dpa::language_equivalent::normalized_100 | 963 959 | 1 387 341 | 1 353 446 | 2 215 | 652 | – | – |
| dpa::dpa::language_equivalent::normalized_25 | 315 935 | 456 707 | 442 182 | 238 | 381 | – | – |
| dpa::dpa::language_equivalent::normalized_50 | 564 774 | 808 108 | 791 073 | 502 | 415 | – | – |
| 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 008 | 4 851 578 | 52 924 | 6 366 | – | – |
| dpa::dpa::normalized::chain_4000 | 14 326 415 | 21 930 604 | 19 737 759 | 253 216 | 26 479 | – | – |
| dpa::dpa::normalized::scrambled_1000 | 4 346 572 | 6 490 823 | 5 961 713 | 60 266 | 6 508 | – | – |
| dpa::dpa::normalized::scrambled_4000 | 17 617 793 | 26 718 123 | 24 103 098 | 335 202 | 26 829 | – | – |
| dpa::dpa::normalized::scrambled_k4_1000 | 25 249 999 | 35 407 074 | 33 257 969 | 379 407 | 7 202 | – | – |
| dpa::dpa::normalized_fixtures::ltl | 1 272 930 | 1 821 401 | 1 786 341 | 4 646 | 338 | – | – |
| dpa::dpa::normalized_fixtures::many_aps | 12 275 183 | 17 721 630 | 17 254 670 | 83 592 | 1 400 | – | – |
| dpa::dpa::normalized_fixtures::synthetic | 8 843 733 | 12 507 295 | 12 040 140 | 90 743 | 384 | – | – |
| dpa::dpa::prefix_partition::chain_16 | 3 574 178 | 5 456 706 | 5 390 351 | 2 113 | 1 594 | – | – |
| dpa::dpa::prefix_partition::chain_8 | 916 107 | 1 409 057 | 1 379 877 | 432 | 772 | – | – |
| dpa::dpa::prefix_partition::scrambled_16 | 3 999 698 | 6 155 424 | 6 070 444 | 3 745 | 1 893 | – | – |
| dpa::dpa::prefix_partition::scrambled_8 | 1 086 510 | 1 669 613 | 1 639 248 | 599 | 782 | – | – |
| dpa::dpa::rejected_word::chain_100 | 885 231 | 1 282 025 | 1 241 395 | 2 834 | 756 | – | – |
| dpa::dpa::rejected_word::chain_400 | 3 441 584 | 5 130 488 | 4 832 083 | 47 977 | 1 672 | – | – |
| dpa::dpa::rejected_word::scrambled_100 | 235 103 | 360 768 | 329 643 | 506 | 817 | – | – |
| dpa::dpa::rejected_word::scrambled_400 | 887 076 | 1 355 310 | 1 244 360 | 10 234 | 1 708 | – | – |
| dpa::dpa::sccs::chain_1000 | 511 023 | 774 930 | 699 655 | 6 830 | 1 175 | – | – |
| dpa::dpa::sccs::chain_4000 | 1 971 630 | 3 022 719 | 2 696 939 | 29 890 | 5 038 | – | – |
| dpa::dpa::sccs::scrambled_1000 | 576 822 | 871 308 | 795 343 | 8 221 | 996 | – | – |
| dpa::dpa::sccs::scrambled_4000 | 2 295 945 | 3 543 743 | 3 164 888 | 46 273 | 4 214 | – | – |
| dpa::dpa::witness_colors::chain_100 | 4 471 330 | 6 366 048 | 6 245 888 | 9 010 | 2 146 | – | – |
| dpa::dpa::witness_colors::chain_400 | 43 697 424 | 62 813 212 | 61 212 837 | 194 579 | 17 928 | – | – |
| dpa::dpa::witness_colors::scrambled_100 | 3 895 188 | 5 531 851 | 5 442 571 | 8 735 | 1 303 | – | – |
| dpa::dpa::witness_colors::scrambled_400 | 29 949 989 | 42 974 134 | 42 154 394 | 145 685 | 2 609 | – | – |
| dpa::dpa::witness_inequivalence::complement_100 | 268 661 | 397 839 | 380 479 | 868 | 372 | – | – |
| dpa::dpa::witness_inequivalence::complement_25 | 86 600 | 134 391 | 121 476 | 91 | 356 | – | – |
| dpa::dpa::witness_inequivalence::complement_50 | 149 885 | 224 829 | 211 034 | 330 | 347 | – | – |
| dpa::dpa::witness_not_subset_of::complement_100 | 260 739 | 388 101 | 371 331 | 841 | 359 | – | – |
| dpa::dpa::witness_not_subset_of::complement_25 | 84 611 | 131 562 | 119 157 | 80 | 343 | – | – |
| dpa::dpa::witness_not_subset_of::complement_50 | 146 080 | 219 943 | 206 693 | 312 | 334 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_100 | 524 060 | 764 046 | 738 446 | 1 389 | 533 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_25 | 177 925 | 261 455 | 249 525 | 153 | 319 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_50 | 302 723 | 439 927 | 425 522 | 368 | 359 | – | – |
| dpa::dpa::witnesses_fixtures::ltl | 1 970 349 | 2 739 371 | 2 683 541 | 5 769 | 771 | – | – |
| dpa::dpa::witnesses_fixtures::synthetic | 15 821 117 | 22 785 101 | 22 257 961 | 99 968 | 780 | – | – |
| 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 758 268 | 2 387 224 | 2 349 084 | 376 | 1 036 | 154 504 | 2 633 |
| learning::learning::lstar_mealy::counting_8 | 450 608 | 631 355 | 604 975 | 75 | 743 | 40 472 | 862 |
| learning::learning::sprout_parity::inf_ab_100 | 1 147 944 | 1 643 132 | 1 584 542 | 1 932 | 1 398 | 200 416 | 1 872 |
| learning::learning::sprout_parity::inf_ab_400 | 2 354 594 | 3 354 863 | 3 243 683 | 8 789 | 1 921 | 405 040 | 3 649 |
| nondeterministic::nondeterministic::fixture_accepts::ltl | 731 487 | 1 133 732 | 1 084 307 | 6 245 | 520 | – | – |
| nondeterministic::nondeterministic::nba_accepts::nba_400 | 122 996 323 | 179 087 159 | 168 150 759 | 1 663 470 | 74 830 | – | – |
| nondeterministic::nondeterministic::nba_witness::nba_4000 | 17 383 333 | 26 028 564 | 25 014 714 | 138 524 | 9 178 | – | – |
| nondeterministic::nondeterministic::nca_accepts::nca_400 | 254 927 534 | 371 569 218 | 345 867 613 | 4 569 135 | 81 598 | – | – |
| nondeterministic::nondeterministic::nca_witness::nca_4000 | 21 904 941 | 33 241 987 | 31 087 887 | 325 673 | 15 021 | – | – |
| nondeterministic::nondeterministic::nma_witness::nma_1000 | 25 383 666 | 37 527 289 | 35 512 844 | 370 108 | 4 683 | – | – |
| nondeterministic::nondeterministic::npa_accepts::empty_npa_400 | 458 821 236 | 670 095 587 | 622 425 232 | 8 911 204 | 88 981 | – | – |
| nondeterministic::nondeterministic::npa_accepts::npa_100 | 29 740 298 | 42 889 069 | 41 005 489 | 287 781 | 12 705 | – | – |
| nondeterministic::nondeterministic::npa_accepts::npa_400 | 122 955 922 | 179 060 796 | 168 131 086 | 1 662 055 | 74 841 | – | – |
| nondeterministic::nondeterministic::npa_witness::empty_npa_1000 | 9 427 737 | 13 979 005 | 13 247 685 | 123 234 | 3 290 | – | – |
| nondeterministic::nondeterministic::npa_witness::empty_npa_4000 | 38 265 192 | 57 449 628 | 53 485 923 | 657 368 | 19 339 | – | – |
| nondeterministic::nondeterministic::npa_witness::npa_1000 | 2 979 072 | 4 478 245 | 4 313 255 | 20 783 | 1 745 | – | – |
| nondeterministic::nondeterministic::npa_witness::npa_4000 | 23 816 129 | 35 551 421 | 34 340 101 | 178 011 | 9 179 | – | – |
| nondeterministic::nondeterministic::nra_witness::nra_4000 | 21 455 583 | 32 709 993 | 30 163 398 | 337 203 | 24 588 | – | – |
| runs::runs::dfa_accepts_many_words::count_1000 | 4 053 182 | 5 005 902 | 4 981 602 | 4 790 | 10 | 0 | 0 |
| runs::runs::dfa_accepts_one_word::len_100 | 3 561 | 4 852 | 4 452 | 38 | 6 | 0 | 0 |
| runs::runs::dfa_accepts_one_word::len_10000 | 276 039 | 339 481 | 335 781 | 698 | 6 | 0 | 0 |
| runs::runs::dfa_accepts_one_word::len_100000 | 2 750 700 | 3 376 779 | 3 344 664 | 6 325 | 14 | 0 | 0 |
| runs::runs::dfa_reached_state::count_1000 | 3 442 180 | 4 272 831 | 4 248 601 | 4 790 | 8 | 0 | 0 |
| runs::runs::dpa_accepts_lassos::long | 8 225 405 | 10 785 654 | 10 761 099 | 3 133 | 254 | 724 664 | 500 |
| runs::runs::dpa_accepts_lassos::short | 376 801 | 502 316 | 497 086 | 402 | 92 | 26 236 | 472 |
| runs::runs::dpa_recurrent_edge_colors::long | 15 221 636 | 19 508 022 | 19 456 387 | 5 938 | 627 | 922 144 | 2 090 |
| runs::runs::dpa_recurrent_edge_colors::short | 1 058 624 | 1 435 398 | 1 424 308 | 1 238 | 140 | 168 684 | 1 708 |
| runs::runs::dpa_recurrent_states::long | 13 767 740 | 19 256 028 | 19 225 933 | 3 597 | 346 | 788 104 | 860 |
| runs::runs::dpa_recurrent_states::short | 596 810 | 814 493 | 807 323 | 552 | 126 | 81 996 | 782 |
| runs::runs::dpa_visited_sequences::long | 8 707 283 | 12 042 601 | 12 009 571 | 4 282 | 332 | 2 190 780 | 850 |
| runs::runs::dpa_visited_sequences::short | 350 418 | 483 868 | 479 183 | 503 | 62 | 29 986 | 545 |
| runs::runs::fixture_accepts_lassos::ltl | 7 833 947 | 11 053 586 | 11 022 406 | 5 550 | 98 | – | – |
| runs::runs::fixture_accepts_lassos::synthetic | 4 309 057 | 6 188 514 | 6 136 859 | 9 624 | 101 | – | – |
| 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 360 814 | 2 034 592 | 1 989 542 | 4 936 | 582 | 180 200 | 37 |
| storage::storage::add_edges_dense::k8_5000 | 4 281 430 | 6 445 912 | 6 259 532 | 17 830 | 2 778 | 671 728 | 40 |
| storage::storage::add_edges_linked::k2_5000 | 1 252 451 | 2 165 036 | 2 003 041 | 14 220 | 2 597 | 1 113 960 | 26 |
| storage::storage::add_edges_linked::k8_5000 | 6 144 063 | 10 329 598 | 9 400 508 | 75 757 | 15 723 | 3 866 496 | 28 |
| storage::storage::clone_csr::k2_10000 | 30 473 | 183 134 | 52 504 | 4 167 | 3 137 | 230 012 | 6 |
| storage::storage::clone_dense::k2_10000 | 15 042 | 81 080 | 25 730 | 2 250 | 1 260 | 110 008 | 4 |
| storage::storage::clone_linked::k2_10000 | 380 760 | 911 527 | 539 732 | 12 465 | 8 842 | 680 008 | 3 |
| storage::storage::complete_dense::partial_5000 | 238 753 | 355 489 | 348 674 | 901 | 66 | 136 | 4 |
| storage::storage::complete_linked::partial_5000 | 1 202 009 | 1 723 938 | 1 635 343 | 6 946 | 1 539 | 65 672 | 18 |
| storage::storage::edges_from_all_states_csr::k2_2000 | 72 045 | 77 204 | 75 854 | 221 | 7 | 0 | 0 |
| storage::storage::edges_from_all_states_csr::k8_2000 | 108 045 | 116 394 | 111 064 | 1 010 | 8 | 0 | 0 |
| storage::storage::edges_from_all_states_dense::k2_2000 | 92 047 | 101 291 | 99 846 | 233 | 8 | 0 | 0 |
| storage::storage::edges_from_all_states_dense::k8_2000 | 128 047 | 140 545 | 135 040 | 1 038 | 9 | 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 399 816 | 6 585 694 | 6 106 644 | 57 793 | 5 431 | 1 505 420 | 2 212 |
| storage::storage::minimize_csr::redundant_8000 | 17 235 334 | 26 136 155 | 23 891 730 | 272 478 | 25 201 | 6 023 300 | 8 250 |
| storage::storage::minimize_dense::redundant_2000 | 4 434 823 | 6 603 857 | 6 149 507 | 58 047 | 4 689 | 1 522 156 | 2 221 |
| storage::storage::minimize_dense::redundant_8000 | 17 408 185 | 26 418 737 | 24 122 742 | 278 893 | 25 758 | 6 090 340 | 8 261 |
| storage::storage::minimize_linked::redundant_2000 | 4 305 957 | 6 557 269 | 6 009 174 | 61 844 | 6 825 | 1 522 156 | 2 221 |
| storage::storage::minimize_linked::redundant_8000 | 16 930 017 | 26 057 460 | 23 610 780 | 302 695 | 26 663 | 6 090 340 | 8 261 |
| storage::storage::overwrite_edges_dense::k2_5000 | 2 140 845 | 3 246 643 | 3 186 628 | 7 908 | 585 | 180 200 | 37 |
| storage::storage::overwrite_edges_linked::k2_5000 | 3 410 553 | 6 005 589 | 5 286 679 | 44 753 | 14 147 | 2 031 464 | 27 |
| storage::storage::predecessors_of_all_states_csr::k2_2000 | 102 062 | 121 152 | 117 427 | 682 | 9 | 0 | 0 |
| storage::storage::predecessors_of_all_states_dense::k2_2000 | 232 309 | 311 675 | 302 160 | 1 616 | 41 | 32 008 | 3 |
| storage::storage::predecessors_of_all_states_linked::k2_2000 | 70 033 | 93 691 | 76 691 | 3 365 | 5 | 0 | 0 |
| storage::storage::product_successor_csr::n200 | 65 088 | 76 493 | 76 148 | 13 | 8 | 0 | 0 |
| storage::storage::product_successor_dense::n200 | 65 088 | 76 601 | 76 121 | 40 | 8 | 0 | 0 |
| storage::storage::product_successor_linked::n200 | 46 540 | 60 172 | 56 992 | 587 | 7 | 0 | 0 |
| storage::storage::reachable_states_csr::k2_8000 | 1 124 918 | 1 621 445 | 1 583 575 | 7 406 | 24 | 17 368 | 11 |
| storage::storage::reachable_states_dense::k2_8000 | 1 173 507 | 1 691 944 | 1 646 964 | 8 835 | 23 | 17 368 | 11 |
| storage::storage::reachable_states_linked::k2_8000 | 980 094 | 1 508 995 | 1 410 260 | 19 516 | 33 | 17 368 | 11 |
| storage::storage::remove_state_dense::k2_10000 | 924 162 | 1 347 834 | 1 173 244 | 21 513 | 1 915 | 176 000 | 1 003 |
| storage::storage::remove_state_linked::k2_10000 | 997 019 | 1 358 281 | 1 319 761 | 7 417 | 41 | 80 000 | 3 000 |
| storage::storage::run_many_words_csr::count_1000 | 512 039 | 601 912 | 592 162 | 1 908 | 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 500 040 | 2 925 299 | 2 893 799 | 6 272 | 4 | 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 394 | 2 943 774 | 6 296 | 4 | 0 | 0 |
| storage::storage::successor_all_pairs_csr::k2_2000 | 122 208 | 139 477 | 138 057 | 228 | 8 | 8 | 1 |
| storage::storage::successor_all_pairs_csr::k8_2000 | 702 262 | 802 721 | 797 321 | 1 024 | 8 | 32 | 1 |
| storage::storage::successor_all_pairs_dense::k2_2000 | 150 205 | 169 512 | 168 047 | 237 | 8 | 8 | 1 |
| storage::storage::successor_all_pairs_dense::k8_2000 | 778 259 | 880 816 | 875 296 | 1 048 | 8 | 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 800 781 | 95 801 970 | 93 298 580 | 451 776 | 6 986 | 1 739 532 | 45 |
| ts::ts::canonical_naming::scrambled_1500 | 3 034 522 | 4 445 109 | 4 255 469 | 21 856 | 2 296 | 463 808 | 5 846 |
| ts::ts::canonical_naming::scrambled_500 | 938 266 | 1 350 768 | 1 307 588 | 3 169 | 781 | 134 336 | 1 831 |
| ts::ts::clone::scrambled_10000 | 381 079 | 912 234 | 540 139 | 12 483 | 8 848 | 680 008 | 3 |
| ts::ts::clone::scrambled_40000 | 1 521 316 | 3 857 647 | 2 156 707 | 42 576 | 42 516 | 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 280 | 5 978 945 | 22 094 | 7 139 | 651 720 | 6 013 |
| ts::ts::determinize::nth_from_end_12 | 19 177 588 | 28 064 762 | 26 556 087 | 98 798 | 28 991 | 2 732 600 | 26 423 |
| ts::ts::determinize::nth_from_end_8 | 980 440 | 1 446 633 | 1 364 228 | 2 992 | 1 927 | 156 552 | 1 396 |
| ts::ts::determinize_propositional::aps_6_n_6 | 4 088 248 | 6 427 293 | 5 941 668 | 20 048 | 11 011 | 1 332 896 | 4 208 |
| ts::ts::determinize_propositional::aps_7_n_6 | 4 295 587 | 6 716 444 | 6 179 154 | 25 327 | 11 733 | 1 197 930 | 1 967 |
| ts::ts::determinize_propositional::aps_8_n_6 | 25 052 413 | 38 429 669 | 35 513 084 | 168 392 | 59 275 | 5 240 456 | 13 678 |
| ts::ts::edges_from_all_states::scrambled_2000 | 74 646 | 93 910 | 82 740 | 2 157 | 11 | 0 | 0 |
| ts::ts::edges_from_all_states::scrambled_k8_2000 | 158 578 | 210 791 | 173 396 | 7 402 | 11 | 0 | 0 |
| ts::ts::erase_state_colors_collect::scrambled_10000 | 1 846 855 | 3 177 699 | 2 618 444 | 37 175 | 10 668 | 2 228 064 | 27 |
| ts::ts::into_dfa::scrambled_10000 | 3 054 983 | 5 375 818 | 4 816 593 | 37 183 | 10 666 | 2 228 064 | 27 |
| ts::ts::map_edge_colors_collect::scrambled_10000 | 1 928 468 | 3 407 606 | 2 789 156 | 38 451 | 12 177 | 2 490 192 | 27 |
| ts::ts::map_edge_colors_collect::scrambled_40000 | 7 655 047 | 13 651 558 | 11 061 738 | 140 335 | 53 947 | 9 961 296 | 31 |
| ts::ts::matching_product_successor_index::n200 | 47 602 | 62 662 | 58 422 | 596 | 36 | 0 | 0 |
| ts::ts::minimal_representative_of_all_states::scrambled_100 | 2 002 068 | 2 856 224 | 2 852 764 | 13 | 97 | 347 504 | 4 679 |
| ts::ts::minimal_representative_of_all_states::scrambled_300 | 16 088 404 | 23 069 356 | 23 054 086 | 2 354 | 100 | 3 116 784 | 38 196 |
| ts::ts::minimal_representatives::scrambled_2000 | 3 248 796 | 4 585 498 | 4 538 728 | 8 920 | 62 | 322 944 | 7 709 |
| ts::ts::minimal_representatives::scrambled_8000 | 14 321 191 | 20 180 415 | 19 965 690 | 42 574 | 53 | 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 261 | 353 731 | 3 609 | 71 | 4 336 | 9 |
| ts::ts::reachable_states::scrambled_8000 | 964 480 | 1 493 828 | 1 394 778 | 19 523 | 41 | 17 368 | 11 |
| ts::ts::remove_edges_from_matching::scrambled_10000 | 446 232 | 589 776 | 565 656 | 4 656 | 24 | 64 000 | 2 000 |
| ts::ts::remove_edges_from_matching::scrambled_40000 | 746 232 | 941 276 | 890 281 | 10 031 | 24 | 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 345 | 289 560 | 45 | 416 | 44 272 | 309 |
| ts::ts::scc_minimal_representatives::small_cycles_400 | 1 192 086 | 1 679 643 | 1 629 923 | 3 889 | 865 | 354 148 | 1 325 |
| ts::ts::subset_construction::nth_from_end_10 | 9 439 133 | 13 173 465 | 12 681 495 | 45 278 | 7 588 | 1 073 520 | 9 919 |
| ts::ts::subset_construction::nth_from_end_12 | 42 061 900 | 58 466 831 | 56 225 971 | 218 194 | 32 854 | 4 518 976 | 43 857 |
| ts::ts::subset_construction::nth_from_end_8 | 2 040 011 | 2 862 542 | 2 756 752 | 6 052 | 2 158 | 257 104 | 2 276 |
| ts::ts::successor_index_all_pairs::scrambled_2000 | 110 814 | 142 198 | 130 953 | 2 158 | 13 | 8 | 1 |
| ts::ts::successor_index_all_pairs::scrambled_k8_2000 | 752 800 | 949 177 | 911 667 | 7 404 | 14 | 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 | 4.10 ms (3.99 ms … 4.21 ms) |
| collect/clone/1000000 | 40.33 ms (39.93 ms … 40.73 ms) |
| collect/collect_owned/100000 | 6.99 ms (6.92 ms … 7.06 ms) |
| collect/collect_owned/1000000 | 79.28 ms (77.83 ms … 80.72 ms) |
| collect/collect_ref/100000 | 4.30 ms (4.22 ms … 4.38 ms) |
| collect/collect_ref/1000000 | 77.79 ms (76.40 ms … 79.17 ms) |
| collect/map_edge_colors_collect_owned/100000 | 6.19 ms (6.07 ms … 6.31 ms) |
| collect/map_edge_colors_collect_owned/1000000 | 70.78 ms (69.81 ms … 71.75 ms) |
| wallclock/dfa/accepts/word_100000 | 927.11 µs (909.93 µs … 944.29 µs) |
| wallclock/dfa/minimize/redundant_4000 | 1.36 ms (1.35 ms … 1.37 ms) |
| wallclock/dpa/complement/scrambled_4000 | 3.30 ms (3.29 ms … 3.31 ms) |
| wallclock/dpa/normalized/scrambled_4000 | 3.03 ms (3.02 ms … 3.05 ms) |
| wallclock/hoa/parse/ltl | 852.65 µs (847.42 µs … 857.89 µs) |
| wallclock/nfa/determinize/nth_from_end_12 | 3.48 ms (3.42 ms … 3.54 ms) |
| wallclock/nfa/subset_construction/nth_from_end_12 | 8.23 ms (8.05 ms … 8.42 ms) |
| wallclock/scc/tarjan/scrambled_10000 | 2.12 ms (2.07 ms … 2.18 ms) |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| hard/l-dsa-3 | spot | 121.96 µs | 114.74 µs | 1.06× | – / – | yes |
| hard/l-nba-2 | spot | 55.74 µs | 36.38 µs | 1.53× | – / – | yes |
| hard/m-nba-3 | spot | 237.68 µs | 138.18 µs | 1.72× | – / – | yes |
| ltl/and-gf-3 | spot | 9.06 µs | 11.84 µs | 0.77× | – / – | yes |
| ltl/eh-patterns-0 | spot | 21.52 µs | 20.00 µs | 1.08× | – / – | yes |
| ltl/gf-equiv-3 | spot | 19.84 µs | 33.32 µs | 0.60× | – / – | yes |
| ltl/gf-implies-3 | spot | 10.48 µs | 19.12 µs | 0.55× | – / – | yes |
| ltl/gh-q-3 | spot | 50.06 µs | 29.24 µs | 1.71× | – / – | yes |
| ltl/gh-r-3 | spot | 20.80 µs | 67.54 µs | 0.31× | – / – | yes |
| ltl/go-theta-3 | spot | 10.92 µs | 21.14 µs | 0.52× | – / – | yes |
| ltl/lily-patterns-1 | spot | 11.98 µs | 15.78 µs | 0.76× | – / – | yes |
| ltl/ms-phi-r-1 | spot | 10.20 µs | 38.20 µs | 0.27× | – / – | yes |
| ltl/ms-phi-s-1 | spot | 10.32 µs | 39.74 µs | 0.26× | – / – | yes |
| ltl/rv-counter-3 | spot | 27.58 µs | 13.24 µs | 2.08× | – / – | yes |
| ltl/sb-patterns-0 | spot | 12.52 µs | 14.18 µs | 0.88× | – / – | yes |
| ltl/sejk-k-2 | spot | 13.40 µs | 57.36 µs | 0.23× | – / – | yes |
| ltl/tv-uu-3 | spot | 40.96 µs | 37.76 µs | 1.08× | – / – | yes |
| ltl/u-left-3 | spot | 10.44 µs | 8.56 µs | 1.22× | – / – | yes |
| many_aps/and-gf-12 | spot | 154.04 µs | 65.06 µs | 2.37× | – / – | yes |
| many_aps/gf-equiv-12 | spot | 130.24 µs | 90.52 µs | 1.44× | – / – | yes |
| many_aps/r-right-10 | spot | 64.54 µs | 25.76 µs | 2.51× | – / – | yes |
| many_aps/random-n16-a8-p4-s1 | spot | 258.82 µs | 130.84 µs | 1.98× | – / – | yes |
| many_aps/random-n24-a12-p4-s1 | spot | 1.20 ms | 449.32 µs | 2.67× | – / – | yes |
| many_aps/random-n32-a16-p4-s1 | spot | 3.91 ms | 1.19 ms | 3.29× | – / – | yes |
| random/n128-a2-p6-s1 | spot | 330.06 µs | 207.90 µs | 1.59× | – / – | yes |
| random/n16-a1-p3-s1 | spot | 21.40 µs | 15.74 µs | 1.36× | – / – | yes |
| random/n256-a2-p8-s1 | spot | 883.57 µs | 476.76 µs | 1.85× | – / – | yes |
| random/n64-a2-p4-s1 | spot | 141.74 µs | 101.78 µs | 1.39× | – / – | yes |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| hard/l-dsa-3 | spot | 72.30 µs | 61.26 µs | 1.18× | – / – | yes |
| hard/l-nba-2 | spot | 35.06 µs | 23.66 µs | 1.48× | – / – | yes |
| hard/m-nba-3 | spot | 147.06 µs | 87.64 µs | 1.68× | – / – | yes |
| ltl/and-gf-3 | spot | 5.76 µs | 8.16 µs | 0.71× | – / – | yes |
| ltl/eh-patterns-0 | spot | 14.44 µs | 17.66 µs | 0.82× | – / – | yes |
| ltl/gf-equiv-3 | spot | 11.28 µs | 18.78 µs | 0.60× | – / – | yes |
| ltl/gf-implies-3 | spot | 6.12 µs | 11.80 µs | 0.52× | – / – | yes |
| ltl/gh-q-3 | spot | 32.60 µs | 28.52 µs | 1.14× | – / – | yes |
| ltl/gh-r-3 | spot | 12.34 µs | 34.34 µs | 0.36× | – / – | yes |
| ltl/go-theta-3 | spot | 6.84 µs | 16.10 µs | 0.42× | – / – | yes |
| ltl/lily-patterns-1 | spot | 8.04 µs | 13.40 µs | 0.60× | – / – | yes |
| ltl/ms-phi-r-1 | spot | 6.08 µs | 19.00 µs | 0.32× | – / – | yes |
| ltl/ms-phi-s-1 | spot | 6.04 µs | 24.82 µs | 0.24× | – / – | yes |
| ltl/rv-counter-3 | spot | 17.90 µs | 14.70 µs | 1.22× | – / – | yes |
| ltl/sb-patterns-0 | spot | 7.68 µs | 12.26 µs | 0.63× | – / – | yes |
| ltl/sejk-k-2 | spot | 7.80 µs | 27.92 µs | 0.28× | – / – | yes |
| ltl/tv-uu-3 | spot | 28.36 µs | 30.42 µs | 0.93× | – / – | yes |
| ltl/u-left-3 | spot | 6.80 µs | 8.80 µs | 0.77× | – / – | yes |
| many_aps/and-gf-12 | spot | 124.22 µs | 54.24 µs | 2.29× | – / – | yes |
| many_aps/gf-equiv-12 | spot | 73.64 µs | 51.30 µs | 1.44× | – / – | yes |
| many_aps/r-right-10 | spot | 47.52 µs | 24.44 µs | 1.94× | – / – | yes |
| many_aps/random-n16-a8-p4-s1 | spot | 214.50 µs | 96.78 µs | 2.22× | – / – | yes |
| many_aps/random-n24-a12-p4-s1 | spot | 1.05 ms | 380.50 µs | 2.75× | – / – | yes |
| many_aps/random-n32-a16-p4-s1 | spot | 3.68 ms | 1.13 ms | 3.26× | – / – | yes |
| random/n128-a2-p6-s1 | spot | 196.90 µs | 125.32 µs | 1.57× | – / – | yes |
| random/n16-a1-p3-s1 | spot | 13.14 µs | 10.28 µs | 1.28× | – / – | yes |
| random/n256-a2-p8-s1 | spot | 508.26 µs | 305.30 µs | 1.66× | – / – | yes |
| random/n64-a2-p4-s1 | spot | 86.14 µs | 65.84 µs | 1.31× | – / – | yes |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| ladder_10000 | oink-ppp | 2.70 ms | 322.50 µs | 8.38× | 10000 / 10000 | yes |
| ladder_10000 | oink-zlk | 2.70 ms | 320.50 µs | 8.43× | 10000 / 10000 | yes |
| ladder_10000 | spot | 2.70 ms | 9.65 ms | 0.28× | 10000 / 10000 | yes |
| ladder_50000 | oink-ppp | 20.00 ms | 2.15 ms | 9.30× | 50000 / 50000 | yes |
| ladder_50000 | oink-zlk | 20.00 ms | 2.18 ms | 9.19× | 50000 / 50000 | yes |
| ladder_50000 | spot | 20.00 ms | 76.47 ms | 0.26× | 50000 / 50000 | yes |
| random_few_10000 | oink-ppp | 7.27 ms | 1.50 ms | 4.84× | 10000 / 10000 | yes |
| random_few_10000 | oink-zlk | 7.27 ms | 2.67 ms | 2.73× | 10000 / 10000 | yes |
| random_few_10000 | spot | 7.27 ms | 20.54 ms | 0.35× | 10000 / 10000 | yes |
| random_few_50000 | oink-ppp | 82.02 ms | 16.01 ms | 5.12× | 50000 / 50000 | yes |
| random_few_50000 | oink-zlk | 82.02 ms | 19.11 ms | 4.29× | 50000 / 50000 | yes |
| random_few_50000 | spot | 82.02 ms | 691.48 ms | 0.12× | 50000 / 50000 | yes |
| random_many_10000 | oink-ppp | 6.30 ms | 1.62 ms | 3.90× | 10000 / 10000 | yes |
| random_many_10000 | oink-zlk | 6.30 ms | 2.70 ms | 2.34× | 10000 / 10000 | yes |
| random_many_10000 | spot | 6.30 ms | 33.62 ms | 0.19× | 10000 / 10000 | yes |
| random_many_50000 | oink-ppp | 81.10 ms | 31.50 ms | 2.57× | 50000 / 50000 | yes |
| random_many_50000 | oink-zlk | 81.10 ms | 48.23 ms | 1.68× | 50000 / 50000 | yes |
| random_many_50000 | spot | 81.10 ms | 712.79 ms | 0.11× | 50000 / 50000 | yes |
== head 2b5473e7fce6730c7a92d0f24df9525438296779: 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 5m 37s
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.25s
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.18s
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.18s
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.21s
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.22s
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.23s
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.21s
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.20s
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.20s
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.23s
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 41s
📦 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.122 ms / 0.115 ms
dpa/equivalence/hard/l-nba-2 vs spot: 0.056 ms / 0.036 ms
dpa/equivalence/hard/m-nba-3 vs spot: 0.238 ms / 0.138 ms
dpa/equivalence/ltl/and-gf-3 vs spot: 0.009 ms / 0.012 ms
dpa/equivalence/ltl/eh-patterns-0 vs spot: 0.022 ms / 0.020 ms
dpa/equivalence/ltl/gf-equiv-3 vs spot: 0.020 ms / 0.033 ms
dpa/equivalence/ltl/gf-implies-3 vs spot: 0.010 ms / 0.019 ms
dpa/equivalence/ltl/gh-q-3 vs spot: 0.050 ms / 0.029 ms
dpa/equivalence/ltl/gh-r-3 vs spot: 0.021 ms / 0.068 ms
dpa/equivalence/ltl/go-theta-3 vs spot: 0.011 ms / 0.021 ms
dpa/equivalence/ltl/lily-patterns-1 vs spot: 0.012 ms / 0.016 ms
dpa/equivalence/ltl/ms-phi-r-1 vs spot: 0.010 ms / 0.038 ms
dpa/equivalence/ltl/ms-phi-s-1 vs spot: 0.010 ms / 0.040 ms
dpa/equivalence/ltl/rv-counter-3 vs spot: 0.028 ms / 0.013 ms
dpa/equivalence/ltl/sb-patterns-0 vs spot: 0.013 ms / 0.014 ms
dpa/equivalence/ltl/sejk-k-2 vs spot: 0.013 ms / 0.057 ms
dpa/equivalence/ltl/tv-uu-3 vs spot: 0.041 ms / 0.038 ms
dpa/equivalence/ltl/u-left-3 vs spot: 0.010 ms / 0.009 ms
dpa/equivalence/many_aps/and-gf-12 vs spot: 0.154 ms / 0.065 ms
dpa/equivalence/many_aps/gf-equiv-12 vs spot: 0.130 ms / 0.091 ms
dpa/equivalence/many_aps/r-right-10 vs spot: 0.065 ms / 0.026 ms
dpa/equivalence/many_aps/random-n16-a8-p4-s1 vs spot: 0.259 ms / 0.131 ms
dpa/equivalence/many_aps/random-n24-a12-p4-s1 vs spot: 1.200 ms / 0.449 ms
dpa/equivalence/many_aps/random-n32-a16-p4-s1 vs spot: 3.914 ms / 1.191 ms
dpa/equivalence/random/n128-a2-p6-s1 vs spot: 0.330 ms / 0.208 ms
dpa/equivalence/random/n16-a1-p3-s1 vs spot: 0.021 ms / 0.016 ms
dpa/equivalence/random/n256-a2-p8-s1 vs spot: 0.884 ms / 0.477 ms
dpa/equivalence/random/n64-a2-p4-s1 vs spot: 0.142 ms / 0.102 ms
dpa/inclusion/hard/l-dsa-3 vs spot: 0.072 ms / 0.061 ms
dpa/inclusion/hard/l-nba-2 vs spot: 0.035 ms / 0.024 ms
dpa/inclusion/hard/m-nba-3 vs spot: 0.147 ms / 0.088 ms
dpa/inclusion/ltl/and-gf-3 vs spot: 0.006 ms / 0.008 ms
dpa/inclusion/ltl/eh-patterns-0 vs spot: 0.014 ms / 0.018 ms
dpa/inclusion/ltl/gf-equiv-3 vs spot: 0.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.034 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.013 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.124 ms / 0.054 ms
dpa/inclusion/many_aps/gf-equiv-12 vs spot: 0.074 ms / 0.051 ms
dpa/inclusion/many_aps/r-right-10 vs spot: 0.048 ms / 0.024 ms
dpa/inclusion/many_aps/random-n16-a8-p4-s1 vs spot: 0.215 ms / 0.097 ms
dpa/inclusion/many_aps/random-n24-a12-p4-s1 vs spot: 1.047 ms / 0.381 ms
dpa/inclusion/many_aps/random-n32-a16-p4-s1 vs spot: 3.685 ms / 1.130 ms
dpa/inclusion/random/n128-a2-p6-s1 vs spot: 0.197 ms / 0.125 ms
dpa/inclusion/random/n16-a1-p3-s1 vs spot: 0.013 ms / 0.010 ms
dpa/inclusion/random/n256-a2-p8-s1 vs spot: 0.508 ms / 0.305 ms
dpa/inclusion/random/n64-a2-p4-s1 vs spot: 0.086 ms / 0.066 ms
game/solve/random_few_10000 vs spot: 7.270 ms / 20.535 ms
game/solve/random_few_10000 vs oink-zlk: 7.270 ms / 2.665 ms
game/solve/random_few_10000 vs oink-ppp: 7.270 ms / 1.503 ms
game/solve/random_few_50000 vs spot: 82.019 ms / 691.476 ms
game/solve/random_few_50000 vs oink-zlk: 82.019 ms / 19.112 ms
game/solve/random_few_50000 vs oink-ppp: 82.019 ms / 16.011 ms
game/solve/random_many_10000 vs spot: 6.298 ms / 33.620 ms
game/solve/random_many_10000 vs oink-zlk: 6.298 ms / 2.696 ms
game/solve/random_many_10000 vs oink-ppp: 6.298 ms / 1.616 ms
game/solve/random_many_50000 vs spot: 81.096 ms / 712.790 ms
game/solve/random_many_50000 vs oink-zlk: 81.096 ms / 48.230 ms
game/solve/random_many_50000 vs oink-ppp: 81.096 ms / 31.504 ms
game/solve/ladder_10000 vs spot: 2.702 ms / 9.647 ms
game/solve/ladder_10000 vs oink-zlk: 2.702 ms / 0.321 ms
game/solve/ladder_10000 vs oink-ppp: 2.702 ms / 0.323 ms
game/solve/ladder_50000 vs spot: 19.998 ms / 76.468 ms
game/solve/ladder_50000 vs oink-zlk: 19.998 ms / 2.176 ms
game/solve/ladder_50000 vs oink-ppp: 19.998 ms / 2.151 ms
== head: 266 benchmarks, 16 wall-clock measurements, 74 comparisons