History · Versus Spot and Oink
Atoms for propositional alphabets: faster determinization (#157) (#162)
status done · queued 2026-11-11 13:37 · started 2026-11-11 13:37 · finished 2026-11-11 13:48
· · rustc 1.95.0 (59807616e 2026-04-14) (built from a source tarball) · valgrind-3.26.0 · pinned to cpu 1
| benchmark | instructions | est. cycles | L1 hits | LL hits | RAM hits | heap bytes | allocations |
|---|---|---|---|---|---|---|---|
| dfa::dfa::accepts_many_words::scrambled_1000 | 343 072 | 435 464 | 428 944 | 1 220 | 12 | 0 | 0 |
| dfa::dfa::complement::scrambled_1000 | 366 068 | 584 238 | 566 333 | 3 399 | 26 | 139 104 | 19 |
| dfa::dfa::complement::scrambled_4000 | 1 435 873 | 2 309 093 | 2 223 223 | 16 999 | 25 | 556 896 | 23 |
| dfa::dfa::equivalent::deep_difference_100 | 61 667 | 97 786 | 90 471 | 49 | 202 | 16 196 | 25 |
| dfa::dfa::equivalent::deep_difference_400 | 212 158 | 336 680 | 314 200 | 1 850 | 378 | 65 364 | 33 |
| dfa::dfa::equivalent::different_100 | 9 047 | 15 443 | 12 568 | 8 | 81 | 1 804 | 12 |
| dfa::dfa::equivalent::different_400 | 9 088 | 15 644 | 12 524 | 78 | 78 | 1 804 | 12 |
| dfa::dfa::equivalent::minimized_100 | 35 849 | 54 513 | 51 888 | 105 | 60 | 7 756 | 17 |
| dfa::dfa::equivalent::minimized_400 | 120 587 | 182 487 | 176 697 | 724 | 62 | 31 580 | 23 |
| dfa::dfa::give_word::empty_1000 | 1 872 613 | 2 558 605 | 2 531 030 | 4 927 | 84 | 152 864 | 3 738 |
| dfa::dfa::give_word::empty_4000 | 6 930 823 | 9 656 961 | 9 554 286 | 20 059 | 68 | 679 808 | 15 828 |
| dfa::dfa::give_word::far_1000 | 164 342 | 231 589 | 227 034 | 547 | 52 | 28 176 | 394 |
| dfa::dfa::give_word::far_4000 | 946 982 | 1 329 396 | 1 307 391 | 3 925 | 68 | 148 464 | 2 233 |
| dfa::dfa::intersection::scrambled_100 | 3 319 709 | 5 217 401 | 5 038 986 | 12 065 | 3 374 | 428 088 | 42 |
| dfa::dfa::intersection::scrambled_200 | 13 224 873 | 21 169 191 | 20 030 861 | 97 144 | 18 646 | 1 708 120 | 49 |
| dfa::dfa::intersection_is_empty::empty_100 | 59 266 | 94 001 | 87 376 | 30 | 185 | 15 700 | 20 |
| dfa::dfa::intersection_is_empty::empty_200 | 109 269 | 175 048 | 161 728 | 613 | 293 | 31 580 | 23 |
| dfa::dfa::is_empty_language::empty_1000 | 1 872 615 | 2 558 677 | 2 531 032 | 4 927 | 86 | 152 864 | 3 738 |
| dfa::dfa::is_empty_language::empty_4000 | 6 930 825 | 9 656 965 | 9 554 290 | 20 059 | 68 | 679 808 | 15 828 |
| dfa::dfa::minimize::minimal_1000 | 3 450 924 | 5 260 262 | 4 882 207 | 39 771 | 5 120 | 1 135 492 | 2 214 |
| dfa::dfa::minimize::minimal_4000 | 13 472 602 | 20 707 238 | 19 046 968 | 204 647 | 18 201 | 4 543 724 | 8 254 |
| dfa::dfa::minimize::redundant_1000 | 2 292 807 | 3 485 427 | 3 247 032 | 25 937 | 3 106 | 760 780 | 1 201 |
| dfa::dfa::minimize::redundant_4000 | 8 869 106 | 13 616 893 | 12 556 903 | 143 657 | 9 763 | 3 044 900 | 4 241 |
| dfa::dfa::minimize::scrambled_1000 | 3 670 256 | 5 623 871 | 5 188 596 | 51 110 | 5 135 | 1 116 052 | 2 217 |
| dfa::dfa::minimize::scrambled_4000 | 14 250 469 | 22 214 474 | 20 104 804 | 294 198 | 18 248 | 4 470 140 | 8 261 |
| dfa::dfa::minimize_moore_with_edge_colors::scrambled_1000 | 3 669 252 | 5 616 688 | 5 186 583 | 50 111 | 5 130 | 1 116 052 | 2 217 |
| dfa::dfa::minimize_moore_with_edge_colors::scrambled_4000 | 14 239 073 | 22 181 428 | 20 076 193 | 300 696 | 17 193 | 4 470 140 | 8 261 |
| dfa::dfa::union::scrambled_100 | 3 319 709 | 5 217 405 | 5 038 985 | 12 066 | 3 374 | 428 088 | 42 |
| dfa::dfa::union::scrambled_200 | 13 224 873 | 21 169 157 | 20 030 862 | 97 144 | 18 645 | 1 708 120 | 49 |
| dpa::dpa::accepted_word::chain_100 | 113 482 | 174 665 | 162 010 | 53 | 354 | – | – |
| dpa::dpa::accepted_word::chain_400 | 383 293 | 582 364 | 547 234 | 2 966 | 580 | – | – |
| dpa::dpa::accepted_word::scrambled_100 | 145 688 | 219 606 | 206 481 | 42 | 369 | – | – |
| dpa::dpa::accepted_word::scrambled_400 | 496 798 | 738 926 | 705 026 | 2 818 | 566 | – | – |
| dpa::dpa::accepted_word_fixtures::ltl | 546 210 | 807 833 | 778 218 | 2 717 | 458 | – | – |
| dpa::dpa::accepted_word_fixtures::synthetic | 1 402 296 | 2 089 662 | 2 013 632 | 12 441 | 395 | – | – |
| dpa::dpa::accepted_word_fixtures_by_atoms::ltl | 1 734 675 | 2 593 631 | 2 518 226 | 10 496 | 655 | – | – |
| dpa::dpa::accepted_word_fixtures_by_atoms::synthetic | 2 873 256 | 4 313 744 | 4 220 069 | 14 220 | 645 | – | – |
| dpa::dpa::collect_dpa::scrambled_1000 | 299 640 | 481 513 | 462 283 | 3 804 | 6 | – | – |
| dpa::dpa::collect_dpa::scrambled_4000 | 1 169 031 | 1 929 918 | 1 806 248 | 16 404 | 1 190 | – | – |
| dpa::dpa::complement::chain_1000 | 4 096 940 | 6 248 524 | 5 745 044 | 55 154 | 6 506 | – | – |
| dpa::dpa::complement::chain_4000 | 16 653 211 | 25 541 848 | 23 300 378 | 261 940 | 26 622 | – | – |
| dpa::dpa::complement::scrambled_1000 | 4 958 494 | 7 462 311 | 6 915 741 | 62 834 | 6 640 | – | – |
| dpa::dpa::complement::scrambled_4000 | 20 037 458 | 30 543 214 | 27 877 684 | 344 309 | 26 971 | – | – |
| dpa::dpa::complement_fixtures::ltl | 1 480 503 | 2 153 299 | 2 109 074 | 5 555 | 470 | – | – |
| dpa::dpa::complement_fixtures::many_aps | 13 919 764 | 20 572 840 | 20 081 700 | 87 203 | 1 575 | – | – |
| dpa::dpa::complement_fixtures::synthetic | 9 652 583 | 13 851 255 | 13 340 565 | 98 659 | 497 | – | – |
| dpa::dpa::complement_without_normalizing::scrambled_1000 | 574 441 | 820 766 | 791 771 | 5 176 | 89 | – | – |
| dpa::dpa::complement_without_normalizing::scrambled_4000 | 2 259 823 | 3 267 011 | 3 112 521 | 21 980 | 1 274 | – | – |
| dpa::dpa::equivalent_fixtures::many_aps | 21 649 390 | 32 289 803 | 31 617 648 | 121 642 | 1 827 | – | – |
| dpa::dpa::hoa_parse::ltl | 5 509 161 | 8 394 704 | 8 055 619 | 43 184 | 3 519 | – | – |
| dpa::dpa::hoa_parse::many_aps | 88 889 281 | 144 103 380 | 126 816 815 | 303 428 | 450 555 | – | – |
| dpa::dpa::hoa_parse::synthetic | 25 096 681 | 38 185 153 | 36 756 203 | 183 065 | 14 675 | – | – |
| dpa::dpa::hoa_print::ltl | 19 039 651 | 36 379 123 | 24 186 758 | 7 485 | 347 284 | – | – |
| dpa::dpa::hoa_print::many_aps | 19 675 345 | 28 413 981 | 28 332 281 | 13 386 | 422 | – | – |
| dpa::dpa::hoa_print::synthetic | 27 397 176 | 48 704 419 | 36 382 239 | 20 330 | 349 158 | – | – |
| dpa::dpa::included_fixtures::many_aps | 18 597 823 | 27 918 988 | 27 376 573 | 95 624 | 1 837 | – | – |
| dpa::dpa::included_in::complement_100 | 270 299 | 410 428 | 391 668 | 861 | 413 | – | – |
| dpa::dpa::included_in::complement_25 | 88 075 | 140 043 | 125 703 | 96 | 396 | – | – |
| dpa::dpa::included_in::complement_50 | 151 571 | 232 902 | 217 782 | 308 | 388 | – | – |
| dpa::dpa::included_in::normalized_100 | 543 003 | 803 274 | 776 594 | 1 360 | 568 | – | – |
| dpa::dpa::included_in::normalized_25 | 184 848 | 275 786 | 262 531 | 103 | 364 | – | – |
| dpa::dpa::included_in::normalized_50 | 313 519 | 462 832 | 446 897 | 352 | 405 | – | – |
| dpa::dpa::language_equivalent::complement_100 | 279 874 | 422 356 | 403 611 | 865 | 412 | – | – |
| dpa::dpa::language_equivalent::complement_25 | 90 600 | 143 209 | 128 954 | 93 | 394 | – | – |
| dpa::dpa::language_equivalent::complement_50 | 156 446 | 238 990 | 223 950 | 313 | 385 | – | – |
| dpa::dpa::language_equivalent::normalized_100 | 993 356 | 1 447 206 | 1 412 261 | 2 285 | 672 | – | – |
| dpa::dpa::language_equivalent::normalized_25 | 326 815 | 477 816 | 462 811 | 124 | 411 | – | – |
| dpa::dpa::language_equivalent::normalized_50 | 581 323 | 841 604 | 824 179 | 461 | 432 | – | – |
| dpa::dpa::map_edge_colors_collect::scrambled_1000 | 297 297 | 476 256 | 456 071 | 3 897 | 20 | – | – |
| dpa::dpa::map_edge_colors_collect::scrambled_4000 | 1 157 692 | 1 906 447 | 1 778 352 | 17 184 | 1 205 | – | – |
| dpa::dpa::normalized::chain_1000 | 3 824 386 | 5 906 056 | 5 415 496 | 52 920 | 6 456 | – | – |
| dpa::dpa::normalized::chain_4000 | 15 564 657 | 24 180 160 | 21 984 355 | 253 185 | 26 568 | – | – |
| dpa::dpa::normalized::scrambled_1000 | 4 685 742 | 7 119 672 | 6 585 827 | 60 632 | 6 591 | – | – |
| dpa::dpa::normalized::scrambled_4000 | 18 948 706 | 29 181 685 | 26 561 205 | 335 677 | 26 917 | – | – |
| dpa::dpa::normalized::scrambled_k4_1000 | 26 000 725 | 37 157 841 | 35 003 006 | 379 937 | 7 290 | – | – |
| dpa::dpa::normalized_fixtures::ltl | 1 415 889 | 2 067 134 | 2 028 184 | 4 885 | 415 | – | – |
| dpa::dpa::normalized_fixtures::many_aps | 13 659 715 | 20 248 781 | 19 772 546 | 84 537 | 1 530 | – | – |
| dpa::dpa::normalized_fixtures::synthetic | 9 337 591 | 13 443 500 | 12 961 680 | 93 130 | 462 | – | – |
| dpa::dpa::prefix_partition::chain_16 | 3 339 069 | 5 086 305 | 5 008 540 | 3 828 | 1 675 | – | – |
| dpa::dpa::prefix_partition::chain_8 | 861 644 | 1 327 089 | 1 290 174 | 1 461 | 846 | – | – |
| dpa::dpa::prefix_partition::scrambled_16 | 3 707 909 | 5 679 645 | 5 579 395 | 6 190 | 1 980 | – | – |
| dpa::dpa::prefix_partition::scrambled_8 | 1 022 858 | 1 569 648 | 1 529 983 | 1 913 | 860 | – | – |
| dpa::dpa::rejected_word::chain_100 | 938 248 | 1 376 676 | 1 332 746 | 3 018 | 824 | – | – |
| dpa::dpa::rejected_word::chain_400 | 3 643 943 | 5 486 568 | 5 184 983 | 48 102 | 1 745 | – | – |
| dpa::dpa::rejected_word::scrambled_100 | 247 893 | 385 958 | 351 708 | 522 | 904 | – | – |
| dpa::dpa::rejected_word::scrambled_400 | 935 362 | 1 443 236 | 1 329 341 | 10 221 | 1 794 | – | – |
| dpa::dpa::sccs::chain_1000 | 500 888 | 788 721 | 712 921 | 6 837 | 1 189 | – | – |
| dpa::dpa::sccs::chain_4000 | 1 928 615 | 3 072 698 | 2 746 378 | 29 900 | 5 052 | – | – |
| dpa::dpa::sccs::scrambled_1000 | 567 845 | 886 821 | 810 266 | 8 227 | 1 012 | – | – |
| dpa::dpa::sccs::scrambled_4000 | 2 257 485 | 3 600 279 | 3 220 804 | 46 278 | 4 231 | – | – |
| dpa::dpa::witness_colors::chain_100 | 4 741 540 | 6 720 535 | 6 596 740 | 9 128 | 2 233 | – | – |
| dpa::dpa::witness_colors::chain_400 | 46 520 653 | 65 842 744 | 64 242 184 | 193 958 | 18 022 | – | – |
| dpa::dpa::witness_colors::scrambled_100 | 4 126 372 | 5 852 986 | 5 757 381 | 9 405 | 1 388 | – | – |
| dpa::dpa::witness_colors::scrambled_400 | 31 846 701 | 45 099 685 | 44 276 665 | 145 683 | 2 703 | – | – |
| dpa::dpa::witness_inequivalence::complement_100 | 279 873 | 422 291 | 403 611 | 866 | 410 | – | – |
| dpa::dpa::witness_inequivalence::complement_25 | 90 599 | 143 204 | 128 954 | 92 | 394 | – | – |
| dpa::dpa::witness_inequivalence::complement_50 | 156 445 | 238 959 | 223 949 | 314 | 384 | – | – |
| dpa::dpa::witness_not_subset_of::complement_100 | 270 298 | 410 431 | 391 666 | 862 | 413 | – | – |
| dpa::dpa::witness_not_subset_of::complement_25 | 88 074 | 140 076 | 125 701 | 96 | 397 | – | – |
| dpa::dpa::witness_not_subset_of::complement_50 | 151 570 | 232 879 | 217 779 | 311 | 387 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_100 | 543 002 | 803 231 | 776 596 | 1 358 | 567 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_25 | 184 847 | 275 793 | 262 528 | 105 | 364 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_50 | 313 518 | 462 809 | 446 894 | 355 | 404 | – | – |
| dpa::dpa::witnesses_fixtures::ltl | 2 229 215 | 3 231 744 | 3 163 249 | 7 840 | 837 | – | – |
| dpa::dpa::witnesses_fixtures::synthetic | 19 359 356 | 29 661 018 | 29 124 838 | 101 230 | 858 | – | – |
| game::game::tangle_learning::few_priorities_1000 | 2 697 048 | 4 062 930 | 3 713 175 | 35 910 | 4 863 | 745 400 | 1 292 |
| game::game::tangle_learning::few_priorities_4000 | 8 120 676 | 12 712 286 | 11 104 496 | 194 956 | 18 086 | 2 407 416 | 3 266 |
| game::game::tangle_learning::ladder_1000 | 1 179 314 | 1 831 726 | 1 627 971 | 12 443 | 4 044 | 377 868 | 118 |
| game::game::tangle_learning::ladder_4000 | 4 408 134 | 7 087 236 | 6 022 281 | 110 826 | 14 595 | 1 511 668 | 225 |
| game::game::tangle_learning::many_priorities_1000 | 2 018 028 | 3 042 090 | 2 758 585 | 25 523 | 4 454 | 566 440 | 848 |
| game::game::tangle_learning::many_priorities_4000 | 6 752 835 | 10 526 430 | 9 145 870 | 166 289 | 15 689 | 2 187 344 | 1 620 |
| game::game::tangle_learning_min_odd::few_priorities_1000 | 1 521 615 | 2 322 134 | 2 081 284 | 26 351 | 3 117 | 525 072 | 189 |
| game::game::tangle_learning_min_odd::few_priorities_4000 | 8 017 700 | 12 367 400 | 10 863 250 | 215 955 | 12 125 | 2 560 064 | 1 933 |
| game::game::zielonka::few_priorities_1000 | 1 126 199 | 1 709 021 | 1 520 536 | 12 455 | 3 606 | 356 676 | 95 |
| game::game::zielonka::few_priorities_4000 | 3 470 254 | 5 583 687 | 4 684 117 | 81 690 | 14 032 | 1 278 564 | 84 |
| game::game::zielonka::ladder_1000 | 5 134 281 | 7 016 077 | 6 609 667 | 50 090 | 4 456 | 499 404 | 182 |
| game::game::zielonka::ladder_4000 | 19 816 373 | 27 231 951 | 25 422 846 | 246 139 | 16 526 | 1 998 868 | 212 |
| game::game::zielonka::many_priorities_1000 | 4 103 518 | 5 602 303 | 5 264 438 | 38 691 | 4 126 | 764 940 | 339 |
| game::game::zielonka::many_priorities_4000 | 12 909 837 | 17 933 476 | 16 554 676 | 176 129 | 14 233 | 2 552 644 | 288 |
| game::game::zielonka_min_odd::few_priorities_1000 | 2 139 077 | 3 023 373 | 2 800 593 | 23 759 | 2 971 | 512 012 | 195 |
| game::game::zielonka_min_odd::few_priorities_4000 | 6 302 075 | 9 279 687 | 8 309 227 | 131 029 | 9 009 | 1 705 700 | 158 |
| learning::learning::lstar_mealy::counting_16 | 1 816 847 | 2 478 309 | 2 432 244 | 757 | 1 208 | 154 504 | 2 633 |
| learning::learning::lstar_mealy::counting_8 | 481 469 | 684 456 | 650 971 | 222 | 925 | 40 472 | 862 |
| learning::learning::sprout_parity::inf_ab_100 | 1 270 757 | 1 850 240 | 1 786 935 | 2 224 | 1 491 | 200 416 | 1 872 |
| learning::learning::sprout_parity::inf_ab_400 | 2 610 820 | 3 782 713 | 3 665 588 | 9 271 | 2 022 | 405 040 | 3 649 |
| nondeterministic::nondeterministic::fixture_accepts::ltl | 762 545 | 1 185 102 | 1 120 562 | 8 449 | 637 | – | – |
| nondeterministic::nondeterministic::nba_accepts::nba_400 | 125 269 894 | 185 047 774 | 174 142 949 | 1 657 470 | 74 785 | – | – |
| nondeterministic::nondeterministic::nba_witness::nba_4000 | 14 689 961 | 21 476 746 | 20 461 706 | 138 412 | 9 228 | – | – |
| nondeterministic::nondeterministic::nca_accepts::nca_400 | 266 229 440 | 395 082 740 | 369 431 005 | 4 559 084 | 81 609 | – | – |
| nondeterministic::nondeterministic::nca_witness::nca_4000 | 19 458 261 | 29 273 295 | 27 117 250 | 325 488 | 15 103 | – | – |
| nondeterministic::nondeterministic::nma_witness::nma_1000 | 25 744 469 | 37 890 678 | 35 867 768 | 371 150 | 4 776 | – | – |
| nondeterministic::nondeterministic::npa_accepts::empty_npa_400 | 493 167 601 | 734 838 886 | 687 188 026 | 8 907 144 | 89 004 | – | – |
| nondeterministic::nondeterministic::npa_accepts::npa_100 | 30 411 628 | 44 532 162 | 42 656 897 | 286 244 | 12 687 | – | – |
| nondeterministic::nondeterministic::npa_accepts::npa_400 | 125 279 542 | 185 057 918 | 174 152 953 | 1 657 505 | 74 784 | – | – |
| nondeterministic::nondeterministic::npa_witness::empty_npa_1000 | 9 121 952 | 13 459 237 | 12 723 917 | 123 432 | 3 376 | – | – |
| nondeterministic::nondeterministic::npa_witness::empty_npa_4000 | 37 023 303 | 55 330 026 | 51 364 426 | 657 236 | 19 412 | – | – |
| nondeterministic::nondeterministic::npa_witness::npa_1000 | 2 479 531 | 3 680 179 | 3 513 794 | 20 740 | 1 791 | – | – |
| nondeterministic::nondeterministic::npa_witness::npa_4000 | 20 354 255 | 29 430 896 | 28 218 496 | 177 898 | 9 226 | – | – |
| nondeterministic::nondeterministic::nra_witness::nra_4000 | 20 639 567 | 31 400 771 | 28 850 876 | 337 114 | 24 695 | – | – |
| runs::runs::dfa_accepts_many_words::count_1000 | 4 303 213 | 5 381 979 | 5 357 649 | 4 789 | 11 | 0 | 0 |
| runs::runs::dfa_accepts_one_word::len_100 | 3 492 | 4 866 | 4 396 | 38 | 8 | 0 | 0 |
| runs::runs::dfa_accepts_one_word::len_10000 | 266 070 | 329 557 | 325 827 | 697 | 7 | 0 | 0 |
| runs::runs::dfa_accepts_one_word::len_100000 | 2 650 731 | 3 276 889 | 3 244 709 | 6 324 | 16 | 0 | 0 |
| runs::runs::dfa_reached_state::count_1000 | 3 570 211 | 4 404 908 | 4 380 648 | 4 789 | 9 | 0 | 0 |
| runs::runs::dpa_accepts_lassos::long | 9 150 745 | 11 671 083 | 11 646 633 | 3 077 | 259 | 724 664 | 500 |
| runs::runs::dpa_accepts_lassos::short | 406 490 | 540 866 | 535 596 | 361 | 99 | 26 236 | 472 |
| runs::runs::dpa_recurrent_edge_colors::long | 15 116 266 | 19 231 177 | 19 179 462 | 5 835 | 644 | 922 144 | 2 090 |
| runs::runs::dpa_recurrent_edge_colors::short | 1 189 790 | 1 666 323 | 1 655 008 | 1 157 | 158 | 168 684 | 1 708 |
| runs::runs::dpa_recurrent_states::long | 10 502 988 | 13 660 284 | 13 630 404 | 3 519 | 351 | 788 104 | 860 |
| runs::runs::dpa_recurrent_states::short | 572 037 | 764 556 | 757 266 | 534 | 132 | 81 996 | 782 |
| runs::runs::dpa_visited_sequences::long | 8 738 263 | 12 085 908 | 12 050 998 | 4 651 | 333 | 2 190 780 | 850 |
| runs::runs::dpa_visited_sequences::short | 370 678 | 510 989 | 506 294 | 498 | 63 | 29 986 | 545 |
| runs::runs::fixture_accepts_lassos::ltl | 8 766 271 | 12 652 156 | 12 620 176 | 5 542 | 122 | – | – |
| runs::runs::fixture_accepts_lassos::synthetic | 4 340 189 | 6 192 993 | 6 139 153 | 9 907 | 123 | – | – |
| scc::scc::scc_queries::small_cycles_1000 | 906 676 | 1 433 544 | 1 272 094 | 9 428 | 3 266 | 261 132 | 559 |
| scc::scc::scc_queries::small_cycles_4000 | 3 548 919 | 5 658 394 | 4 973 939 | 50 917 | 12 282 | 1 045 396 | 2 071 |
| scc::scc::tarjan::back_edges_1000 | 512 099 | 838 107 | 726 777 | 5 473 | 2 399 | 170 272 | 45 |
| scc::scc::tarjan::back_edges_4000 | 1 987 627 | 3 267 534 | 2 821 394 | 26 452 | 8 968 | 680 632 | 53 |
| scc::scc::tarjan::binary_tree_1000 | 571 217 | 892 769 | 815 694 | 4 061 | 1 622 | 105 760 | 39 |
| scc::scc::tarjan::binary_tree_4000 | 2 290 459 | 3 582 573 | 3 276 413 | 21 129 | 5 729 | 419 512 | 45 |
| scc::scc::tarjan::fragmented_1000 | 658 522 | 1 046 852 | 922 717 | 9 644 | 2 169 | 146 084 | 121 |
| scc::scc::tarjan::fragmented_4000 | 2 534 108 | 4 125 859 | 3 544 654 | 62 789 | 7 636 | 569 852 | 167 |
| scc::scc::tarjan::grid_1024 | 596 080 | 972 081 | 847 761 | 7 728 | 2 448 | 171 160 | 45 |
| scc::scc::tarjan::grid_4096 | 2 378 484 | 4 001 351 | 3 363 701 | 63 669 | 9 123 | 684 184 | 53 |
| scc::scc::tarjan::path_1000 | 1 929 119 | 3 028 523 | 2 729 568 | 23 188 | 5 229 | 455 224 | 2 064 |
| scc::scc::tarjan::path_4000 | 7 632 908 | 12 001 664 | 10 804 764 | 98 323 | 20 151 | 1 821 536 | 8 076 |
| scc::scc::tarjan::ring_1000 | 512 099 | 841 747 | 725 867 | 6 383 | 2 399 | 170 272 | 45 |
| scc::scc::tarjan::ring_4000 | 1 987 627 | 3 284 782 | 2 817 082 | 30 764 | 8 968 | 680 632 | 53 |
| scc::scc::tarjan::scrambled_1000 | 579 056 | 936 579 | 824 029 | 6 956 | 2 222 | 170 272 | 45 |
| scc::scc::tarjan::scrambled_4000 | 2 316 497 | 3 791 249 | 3 296 779 | 41 872 | 8 146 | 680 632 | 53 |
| scc::scc::tarjan::small_cycles_1000 | 905 658 | 1 432 219 | 1 270 809 | 9 434 | 3 264 | 261 132 | 559 |
| scc::scc::tarjan::small_cycles_4000 | 3 544 901 | 5 650 785 | 4 969 530 | 50 298 | 12 279 | 1 045 396 | 2 071 |
| scc::scc::tarjan_from::fragmented_1000 | 242 530 | 394 598 | 344 878 | 2 524 | 1 060 | 74 985 | 64 |
| scc::scc::tarjan_from::fragmented_4000 | 907 762 | 1 492 342 | 1 296 667 | 15 923 | 3 316 | 299 625 | 78 |
| scc::scc::tarjan_from::path_1000 | 1 921 158 | 3 018 244 | 2 722 144 | 23 037 | 5 169 | 468 993 | 2 091 |
| scc::scc::tarjan_from::path_4000 | 7 545 584 | 11 928 681 | 10 697 651 | 106 731 | 19 925 | 1 876 753 | 8 109 |
| scc::scc::tarjan_from::ring_1000 | 503 645 | 836 974 | 717 974 | 6 251 | 2 507 | 184 041 | 72 |
| scc::scc::tarjan_from::scrambled_1000 | 570 602 | 930 380 | 816 485 | 6 476 | 2 329 | 184 041 | 72 |
| storage::storage::add_edges_dense::k2_5000 | 1 356 401 | 2 030 490 | 1 985 345 | 4 941 | 584 | 180 200 | 37 |
| storage::storage::add_edges_dense::k8_5000 | 4 247 059 | 6 411 874 | 6 225 394 | 17 836 | 2 780 | 671 728 | 40 |
| storage::storage::add_edges_linked::k2_5000 | 1 402 670 | 2 420 469 | 2 258 384 | 14 224 | 2 599 | 1 113 960 | 26 |
| storage::storage::add_edges_linked::k8_5000 | 6 669 284 | 11 260 273 | 10 330 808 | 75 818 | 15 725 | 3 866 496 | 28 |
| storage::storage::clone_csr::k2_10000 | 30 590 | 183 480 | 52 625 | 4 170 | 3 143 | 230 012 | 6 |
| storage::storage::clone_dense::k2_10000 | 15 113 | 81 342 | 25 802 | 2 253 | 1 265 | 110 008 | 4 |
| storage::storage::clone_linked::k2_10000 | 370 824 | 901 703 | 529 798 | 12 466 | 8 845 | 680 008 | 3 |
| storage::storage::complete_dense::partial_5000 | 155 628 | 209 494 | 202 329 | 908 | 75 | 136 | 4 |
| storage::storage::complete_linked::partial_5000 | 1 210 854 | 1 718 845 | 1 629 450 | 6 952 | 1 561 | 65 672 | 18 |
| storage::storage::edges_from_all_states_csr::k2_2000 | 72 047 | 77 214 | 75 859 | 222 | 7 | 0 | 0 |
| storage::storage::edges_from_all_states_csr::k8_2000 | 108 047 | 116 392 | 111 072 | 1 008 | 8 | 0 | 0 |
| storage::storage::edges_from_all_states_dense::k2_2000 | 102 043 | 119 287 | 117 842 | 233 | 8 | 0 | 0 |
| storage::storage::edges_from_all_states_dense::k8_2000 | 140 043 | 160 529 | 155 039 | 1 035 | 9 | 0 | 0 |
| storage::storage::edges_from_all_states_linked::k2_2000 | 68 033 | 86 725 | 75 925 | 2 132 | 4 | 0 | 0 |
| storage::storage::edges_from_all_states_linked::k8_2000 | 152 033 | 203 701 | 166 681 | 7 376 | 4 | 0 | 0 |
| storage::storage::minimize_csr::redundant_2000 | 4 633 756 | 7 005 056 | 6 522 111 | 57 893 | 5 528 | 1 505 420 | 2 212 |
| storage::storage::minimize_csr::redundant_8000 | 18 159 861 | 27 786 740 | 25 537 970 | 272 654 | 25 300 | 6 023 300 | 8 250 |
| storage::storage::minimize_dense::redundant_2000 | 4 676 910 | 7 035 651 | 6 577 166 | 58 153 | 4 792 | 1 522 156 | 2 221 |
| storage::storage::minimize_dense::redundant_8000 | 18 364 895 | 28 117 702 | 25 817 247 | 279 050 | 25 863 | 6 090 340 | 8 261 |
| storage::storage::minimize_linked::redundant_2000 | 4 505 038 | 6 920 768 | 6 368 868 | 61 926 | 6 922 | 1 522 156 | 2 221 |
| storage::storage::minimize_linked::redundant_8000 | 17 714 721 | 27 484 314 | 25 033 274 | 302 874 | 26 762 | 6 090 340 | 8 261 |
| storage::storage::overwrite_edges_dense::k2_5000 | 2 126 431 | 3 232 518 | 3 172 428 | 7 916 | 586 | 180 200 | 37 |
| storage::storage::overwrite_edges_linked::k2_5000 | 3 790 775 | 6 671 113 | 5 952 018 | 44 769 | 14 150 | 2 031 464 | 27 |
| storage::storage::predecessors_of_all_states_csr::k2_2000 | 102 046 | 121 042 | 117 407 | 678 | 7 | 0 | 0 |
| storage::storage::predecessors_of_all_states_dense::k2_2000 | 290 369 | 397 907 | 388 222 | 1 622 | 45 | 32 008 | 3 |
| storage::storage::predecessors_of_all_states_linked::k2_2000 | 68 033 | 91 729 | 74 689 | 3 366 | 6 | 0 | 0 |
| storage::storage::product_successor_csr::n200 | 64 096 | 75 545 | 75 160 | 14 | 9 | 0 | 0 |
| storage::storage::product_successor_dense::n200 | 73 087 | 94 620 | 94 105 | 40 | 9 | 0 | 0 |
| storage::storage::product_successor_linked::n200 | 46 547 | 60 175 | 57 015 | 576 | 8 | 0 | 0 |
| storage::storage::reachable_states_csr::k2_8000 | 1 101 115 | 1 630 118 | 1 591 843 | 7 417 | 34 | 17 368 | 11 |
| storage::storage::reachable_states_dense::k2_8000 | 1 133 699 | 1 684 505 | 1 639 245 | 8 828 | 32 | 17 368 | 11 |
| storage::storage::reachable_states_linked::k2_8000 | 924 279 | 1 485 595 | 1 386 515 | 19 529 | 41 | 17 368 | 11 |
| storage::storage::remove_state_dense::k2_10000 | 1 072 212 | 1 565 086 | 1 390 286 | 21 513 | 1 921 | 176 000 | 1 003 |
| storage::storage::remove_state_linked::k2_10000 | 1 094 012 | 1 531 479 | 1 492 734 | 7 420 | 47 | 80 000 | 3 000 |
| storage::storage::run_many_words_csr::count_1000 | 551 036 | 653 943 | 644 163 | 1 907 | 7 | 0 | 0 |
| storage::storage::run_many_words_dense::count_1000 | 558 044 | 690 031 | 680 166 | 1 910 | 9 | 0 | 0 |
| storage::storage::run_many_words_linked::count_1000 | 481 044 | 611 149 | 601 119 | 1 957 | 7 | 0 | 0 |
| storage::storage::run_one_word_csr::len_100000 | 2 600 054 | 3 025 428 | 2 993 823 | 6 272 | 7 | 0 | 0 |
| storage::storage::run_one_word_dense::len_100000 | 2 800 050 | 3 425 457 | 3 393 812 | 6 273 | 8 | 0 | 0 |
| storage::storage::run_one_word_linked::len_100000 | 2 350 039 | 2 975 428 | 2 943 773 | 6 296 | 5 | 0 | 0 |
| storage::storage::successor_all_pairs_csr::k2_2000 | 122 242 | 139 664 | 138 099 | 229 | 12 | 8 | 1 |
| storage::storage::successor_all_pairs_csr::k8_2000 | 702 302 | 802 872 | 797 372 | 1 023 | 11 | 32 | 1 |
| storage::storage::successor_all_pairs_dense::k2_2000 | 162 237 | 193 545 | 192 090 | 235 | 8 | 8 | 1 |
| storage::storage::successor_all_pairs_dense::k8_2000 | 814 297 | 952 851 | 947 346 | 1 045 | 8 | 32 | 1 |
| storage::storage::successor_all_pairs_linked::k2_2000 | 108 236 | 139 158 | 128 178 | 2 140 | 8 | 8 | 1 |
| storage::storage::successor_all_pairs_linked::k8_2000 | 750 296 | 946 204 | 908 999 | 7 385 | 8 | 32 | 1 |
| ts::ts::add_edges_in_order::k2_5000 | 1 402 671 | 2 420 339 | 2 258 389 | 14 225 | 2 595 | 1 113 960 | 26 |
| ts::ts::add_edges_in_order::k8_5000 | 6 669 285 | 11 260 127 | 10 330 817 | 75 815 | 15 721 | 3 866 496 | 28 |
| ts::ts::add_edges_in_reverse::k2_5000 | 1 402 671 | 2 419 539 | 2 258 589 | 14 025 | 2 595 | 1 113 960 | 26 |
| ts::ts::builder_with_edges::k2_5000 | 81 365 967 | 98 218 377 | 95 716 412 | 451 610 | 6 969 | 1 739 532 | 45 |
| ts::ts::canonical_naming::scrambled_1500 | 3 144 090 | 4 592 087 | 4 402 177 | 21 798 | 2 312 | 463 808 | 5 846 |
| ts::ts::canonical_naming::scrambled_500 | 972 576 | 1 396 523 | 1 352 838 | 3 172 | 795 | 134 336 | 1 831 |
| ts::ts::clone::scrambled_10000 | 371 163 | 902 511 | 530 236 | 12 484 | 8 853 | 680 008 | 3 |
| ts::ts::clone::scrambled_40000 | 1 481 400 | 3 817 882 | 2 116 807 | 42 575 | 42 520 | 2 720 008 | 3 |
| ts::ts::collect_dts::scrambled_10000 | 3 455 128 | 6 155 959 | 5 596 814 | 37 167 | 10 666 | 2 228 064 | 27 |
| ts::ts::collect_dts::scrambled_40000 | 13 759 607 | 24 643 035 | 22 289 445 | 135 292 | 47 918 | 8 912 736 | 31 |
| ts::ts::determinize::nth_from_end_10 | 4 414 320 | 6 505 401 | 6 144 541 | 22 129 | 7 149 | 651 720 | 6 013 |
| ts::ts::determinize::nth_from_end_12 | 19 628 006 | 28 773 781 | 27 264 531 | 98 836 | 29 002 | 2 732 600 | 26 423 |
| ts::ts::determinize::nth_from_end_8 | 1 007 268 | 1 486 487 | 1 403 617 | 3 015 | 1 937 | 156 552 | 1 396 |
| ts::ts::determinize_propositional::aps_6_n_6 | 4 333 844 | 6 819 430 | 6 334 370 | 19 550 | 11 066 | 1 332 896 | 4 208 |
| ts::ts::determinize_propositional::aps_7_n_6 | 4 525 387 | 7 097 834 | 6 557 729 | 25 351 | 11 810 | 1 197 162 | 1 965 |
| ts::ts::determinize_propositional::aps_8_n_6 | 26 425 542 | 40 592 597 | 37 675 092 | 167 848 | 59 379 | 5 222 792 | 13 670 |
| ts::ts::edges_from_all_states::scrambled_2000 | 72 669 | 91 975 | 80 775 | 2 156 | 12 | 0 | 0 |
| ts::ts::edges_from_all_states::scrambled_k8_2000 | 156 601 | 208 856 | 171 431 | 7 401 | 12 | 0 | 0 |
| ts::ts::erase_state_colors_collect::scrambled_10000 | 2 377 172 | 4 108 251 | 3 548 881 | 37 163 | 10 673 | 2 228 064 | 27 |
| ts::ts::into_dfa::scrambled_10000 | 3 635 166 | 6 416 219 | 5 856 879 | 37 178 | 10 670 | 2 228 064 | 27 |
| ts::ts::map_edge_colors_collect::scrambled_10000 | 2 368 784 | 4 158 051 | 3 539 571 | 38 450 | 12 178 | 2 490 192 | 27 |
| ts::ts::map_edge_colors_collect::scrambled_40000 | 9 415 409 | 16 652 015 | 14 062 220 | 140 330 | 53 947 | 9 961 296 | 31 |
| ts::ts::matching_product_successor_index::n200 | 75 662 | 111 078 | 106 463 | 650 | 39 | 0 | 0 |
| ts::ts::minimal_representative_of_all_states::scrambled_100 | 2 102 811 | 2 971 313 | 2 967 683 | 12 | 102 | 347 504 | 4 679 |
| ts::ts::minimal_representative_of_all_states::scrambled_300 | 16 917 261 | 23 990 168 | 23 976 933 | 1 912 | 105 | 3 116 784 | 38 196 |
| ts::ts::minimal_representatives::scrambled_2000 | 3 386 040 | 4 763 976 | 4 717 251 | 8 897 | 64 | 322 944 | 7 709 |
| ts::ts::minimal_representatives::scrambled_8000 | 14 908 249 | 20 957 741 | 20 742 926 | 42 578 | 55 | 1 464 896 | 32 693 |
| ts::ts::predecessors_of_all_states::scrambled_2000 | 72 669 | 96 915 | 79 540 | 3 391 | 12 | 0 | 0 |
| ts::ts::predecessors_of_all_states::scrambled_8000 | 288 601 | 389 328 | 313 813 | 15 019 | 12 | 0 | 0 |
| ts::ts::reachable_states::scrambled_2000 | 290 091 | 460 911 | 439 996 | 3 616 | 81 | 4 336 | 9 |
| ts::ts::reachable_states::scrambled_8000 | 1 148 696 | 1 838 492 | 1 739 087 | 19 524 | 51 | 17 368 | 11 |
| ts::ts::remove_edges_from_matching::scrambled_10000 | 566 234 | 795 995 | 771 645 | 4 660 | 30 | 64 000 | 2 000 |
| ts::ts::remove_edges_from_matching::scrambled_40000 | 896 234 | 1 177 495 | 1 126 270 | 10 035 | 30 | 64 000 | 2 000 |
| ts::ts::remove_state::scrambled_10000 | 1 091 012 | 1 528 415 | 1 489 735 | 7 421 | 45 | 80 000 | 3 000 |
| ts::ts::remove_state::scrambled_40000 | 1 421 012 | 1 912 879 | 1 843 619 | 13 537 | 45 | 80 000 | 3 000 |
| ts::ts::scc_minimal_representatives::small_cycles_100 | 219 042 | 318 864 | 303 249 | 57 | 438 | 44 272 | 309 |
| ts::ts::scc_minimal_representatives::small_cycles_400 | 1 242 475 | 1 766 000 | 1 715 580 | 3 882 | 886 | 354 148 | 1 325 |
| ts::ts::subset_construction::nth_from_end_10 | 10 228 206 | 14 537 462 | 14 042 037 | 45 563 | 7 646 | 1 073 520 | 9 919 |
| ts::ts::subset_construction::nth_from_end_12 | 45 253 025 | 64 100 574 | 61 854 764 | 218 778 | 32 912 | 4 518 976 | 43 857 |
| ts::ts::subset_construction::nth_from_end_8 | 2 233 506 | 3 193 168 | 3 084 223 | 6 284 | 2 215 | 257 104 | 2 276 |
| ts::ts::successor_index_all_pairs::scrambled_2000 | 108 863 | 140 327 | 129 022 | 2 156 | 15 | 8 | 1 |
| ts::ts::successor_index_all_pairs::scrambled_k8_2000 | 750 855 | 947 312 | 909 742 | 7 402 | 16 | 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.93 ms (3.84 ms … 4.03 ms) |
| collect/clone/1000000 | 44.28 ms (43.85 ms … 44.72 ms) |
| collect/collect_owned/100000 | 7.23 ms (7.19 ms … 7.27 ms) |
| collect/collect_owned/1000000 | 81.41 ms (79.65 ms … 83.17 ms) |
| collect/collect_ref/100000 | 5.21 ms (5.19 ms … 5.22 ms) |
| collect/collect_ref/1000000 | 89.22 ms (88.40 ms … 90.04 ms) |
| collect/map_edge_colors_collect_owned/100000 | 8.02 ms (7.96 ms … 8.07 ms) |
| collect/map_edge_colors_collect_owned/1000000 | 89.84 ms (87.48 ms … 92.21 ms) |
| wallclock/dfa/accepts/word_100000 | 927.76 µs (909.78 µs … 945.75 µs) |
| wallclock/dfa/minimize/redundant_4000 | 1.40 ms (1.39 ms … 1.42 ms) |
| wallclock/dpa/complement/scrambled_4000 | 3.59 ms (3.59 ms … 3.60 ms) |
| wallclock/dpa/normalized/scrambled_4000 | 3.43 ms (3.36 ms … 3.50 ms) |
| wallclock/hoa/parse/ltl | 944.29 µs (940.39 µs … 948.18 µs) |
| wallclock/nfa/determinize/nth_from_end_12 | 3.45 ms (3.43 ms … 3.48 ms) |
| wallclock/nfa/subset_construction/nth_from_end_12 | 8.96 ms (8.78 ms … 9.15 ms) |
| wallclock/scc/tarjan/scrambled_10000 | 2.21 ms (2.19 ms … 2.24 ms) |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| hard/l-dsa-3 | spot | 140.18 µs | 113.74 µs | 1.23× | – / – | yes |
| hard/l-nba-2 | spot | 64.66 µs | 35.76 µs | 1.81× | – / – | yes |
| hard/m-nba-3 | spot | 275.62 µs | 138.58 µs | 1.99× | – / – | yes |
| ltl/and-gf-3 | spot | 10.38 µs | 11.94 µs | 0.87× | – / – | yes |
| ltl/eh-patterns-0 | spot | 26.76 µs | 19.84 µs | 1.35× | – / – | yes |
| ltl/gf-equiv-3 | spot | 24.48 µs | 33.44 µs | 0.73× | – / – | yes |
| ltl/gf-implies-3 | spot | 12.82 µs | 19.08 µs | 0.67× | – / – | yes |
| ltl/gh-q-3 | spot | 58.74 µs | 28.46 µs | 2.06× | – / – | yes |
| ltl/gh-r-3 | spot | 25.72 µs | 69.20 µs | 0.37× | – / – | yes |
| ltl/go-theta-3 | spot | 12.58 µs | 20.70 µs | 0.61× | – / – | yes |
| ltl/lily-patterns-1 | spot | 13.68 µs | 15.76 µs | 0.87× | – / – | yes |
| ltl/ms-phi-r-1 | spot | 12.14 µs | 37.60 µs | 0.32× | – / – | yes |
| ltl/ms-phi-s-1 | spot | 12.18 µs | 39.14 µs | 0.31× | – / – | yes |
| ltl/rv-counter-3 | spot | 30.40 µs | 13.48 µs | 2.26× | – / – | yes |
| ltl/sb-patterns-0 | spot | 14.52 µs | 14.10 µs | 1.03× | – / – | yes |
| ltl/sejk-k-2 | spot | 15.98 µs | 57.56 µs | 0.28× | – / – | yes |
| ltl/tv-uu-3 | spot | 46.68 µs | 38.64 µs | 1.21× | – / – | yes |
| ltl/u-left-3 | spot | 11.76 µs | 8.34 µs | 1.41× | – / – | yes |
| many_aps/and-gf-12 | spot | 180.02 µs | 66.32 µs | 2.71× | – / – | yes |
| many_aps/gf-equiv-12 | spot | 151.04 µs | 96.12 µs | 1.57× | – / – | yes |
| many_aps/r-right-10 | spot | 75.56 µs | 25.50 µs | 2.96× | – / – | yes |
| many_aps/random-n16-a8-p4-s1 | spot | 306.68 µs | 128.56 µs | 2.39× | – / – | yes |
| many_aps/random-n24-a12-p4-s1 | spot | 1.49 ms | 448.40 µs | 3.33× | – / – | yes |
| many_aps/random-n32-a16-p4-s1 | spot | 4.54 ms | 1.23 ms | 3.68× | – / – | yes |
| random/n128-a2-p6-s1 | spot | 357.96 µs | 207.52 µs | 1.72× | – / – | yes |
| random/n16-a1-p3-s1 | spot | 24.08 µs | 16.10 µs | 1.50× | – / – | yes |
| random/n256-a2-p8-s1 | spot | 967.89 µs | 474.99 µs | 2.04× | – / – | yes |
| random/n64-a2-p4-s1 | spot | 152.10 µs | 100.38 µs | 1.52× | – / – | yes |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| hard/l-dsa-3 | spot | 76.24 µs | 59.84 µs | 1.27× | – / – | yes |
| hard/l-nba-2 | spot | 38.60 µs | 22.74 µs | 1.70× | – / – | yes |
| hard/m-nba-3 | spot | 163.12 µs | 84.98 µs | 1.92× | – / – | yes |
| ltl/and-gf-3 | spot | 6.78 µs | 8.10 µs | 0.84× | – / – | yes |
| ltl/eh-patterns-0 | spot | 17.58 µs | 17.76 µs | 0.99× | – / – | yes |
| ltl/gf-equiv-3 | spot | 14.04 µs | 19.22 µs | 0.73× | – / – | yes |
| ltl/gf-implies-3 | spot | 7.38 µs | 12.04 µs | 0.61× | – / – | yes |
| ltl/gh-q-3 | spot | 37.52 µs | 27.64 µs | 1.36× | – / – | yes |
| ltl/gh-r-3 | spot | 14.50 µs | 34.58 µs | 0.42× | – / – | yes |
| ltl/go-theta-3 | spot | 8.36 µs | 16.16 µs | 0.52× | – / – | yes |
| ltl/lily-patterns-1 | spot | 9.48 µs | 13.48 µs | 0.70× | – / – | yes |
| ltl/ms-phi-r-1 | spot | 7.36 µs | 18.78 µs | 0.39× | – / – | yes |
| ltl/ms-phi-s-1 | spot | 7.24 µs | 24.74 µs | 0.29× | – / – | yes |
| ltl/rv-counter-3 | spot | 19.36 µs | 14.00 µs | 1.38× | – / – | yes |
| ltl/sb-patterns-0 | spot | 9.00 µs | 11.84 µs | 0.76× | – / – | yes |
| ltl/sejk-k-2 | spot | 9.44 µs | 27.68 µs | 0.34× | – / – | yes |
| ltl/tv-uu-3 | spot | 31.48 µs | 28.88 µs | 1.09× | – / – | yes |
| ltl/u-left-3 | spot | 8.00 µs | 9.26 µs | 0.86× | – / – | yes |
| many_aps/and-gf-12 | spot | 142.92 µs | 52.74 µs | 2.71× | – / – | yes |
| many_aps/gf-equiv-12 | spot | 82.04 µs | 50.30 µs | 1.63× | – / – | yes |
| many_aps/r-right-10 | spot | 52.90 µs | 23.16 µs | 2.28× | – / – | yes |
| many_aps/random-n16-a8-p4-s1 | spot | 257.92 µs | 104.62 µs | 2.47× | – / – | yes |
| many_aps/random-n24-a12-p4-s1 | spot | 1.31 ms | 403.14 µs | 3.26× | – / – | yes |
| many_aps/random-n32-a16-p4-s1 | spot | 4.14 ms | 1.13 ms | 3.66× | – / – | yes |
| random/n128-a2-p6-s1 | spot | 213.28 µs | 124.96 µs | 1.71× | – / – | yes |
| random/n16-a1-p3-s1 | spot | 14.68 µs | 9.92 µs | 1.48× | – / – | yes |
| random/n256-a2-p8-s1 | spot | 550.03 µs | 295.64 µs | 1.86× | – / – | yes |
| random/n64-a2-p4-s1 | spot | 90.20 µs | 60.04 µs | 1.50× | – / – | yes |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| ladder_10000 | oink-ppp | 2.61 ms | 310.00 µs | 8.41× | 10000 / 10000 | yes |
| ladder_10000 | oink-zlk | 2.61 ms | 307.00 µs | 8.49× | 10000 / 10000 | yes |
| ladder_10000 | spot | 2.61 ms | 9.47 ms | 0.28× | 10000 / 10000 | yes |
| ladder_50000 | oink-ppp | 20.44 ms | 2.21 ms | 9.23× | 50000 / 50000 | yes |
| ladder_50000 | oink-zlk | 20.44 ms | 1.98 ms | 10.31× | 50000 / 50000 | yes |
| ladder_50000 | spot | 20.44 ms | 71.23 ms | 0.29× | 50000 / 50000 | yes |
| random_few_10000 | oink-ppp | 7.79 ms | 1.47 ms | 5.31× | 10000 / 10000 | yes |
| random_few_10000 | oink-zlk | 7.79 ms | 2.74 ms | 2.84× | 10000 / 10000 | yes |
| random_few_10000 | spot | 7.79 ms | 21.49 ms | 0.36× | 10000 / 10000 | yes |
| random_few_50000 | oink-ppp | 80.47 ms | 17.62 ms | 4.57× | 50000 / 50000 | yes |
| random_few_50000 | oink-zlk | 80.47 ms | 20.55 ms | 3.92× | 50000 / 50000 | yes |
| random_few_50000 | spot | 80.47 ms | 684.01 ms | 0.12× | 50000 / 50000 | yes |
| random_many_10000 | oink-ppp | 7.03 ms | 1.59 ms | 4.41× | 10000 / 10000 | yes |
| random_many_10000 | oink-zlk | 7.03 ms | 2.81 ms | 2.50× | 10000 / 10000 | yes |
| random_many_10000 | spot | 7.03 ms | 31.17 ms | 0.23× | 10000 / 10000 | yes |
| random_many_50000 | oink-ppp | 81.71 ms | 26.64 ms | 3.07× | 50000 / 50000 | yes |
| random_many_50000 | oink-zlk | 81.71 ms | 35.94 ms | 2.27× | 50000 / 50000 | yes |
| random_many_50000 | spot | 81.71 ms | 667.50 ms | 0.12× | 50000 / 50000 | yes |
== head 38e9f0d4ee9208f4d9f2210d954d92f1b9eaa42c: building ["scc", "ts", "runs", "dfa", "dpa", "storage", "nondeterministic", "learning", "game"] ["wallclock"]
Compiling automata v0.2.1 (/var/lib/automata-bench/work/src-head)
Finished `bench` profile [optimized] target(s) in 2m 09s
Executable benches/dfa.rs (/var/lib/automata-bench/work/target-head/release/deps/dfa-a84ba41f760e70ed)
Executable benches/dpa.rs (/var/lib/automata-bench/work/target-head/release/deps/dpa-23bb829f074058ad)
Executable benches/game.rs (/var/lib/automata-bench/work/target-head/release/deps/game-14422f732ec85029)
Executable benches/learning.rs (/var/lib/automata-bench/work/target-head/release/deps/learning-ee53c00379271c59)
Executable benches/nondeterministic.rs (/var/lib/automata-bench/work/target-head/release/deps/nondeterministic-f164d05108dbce73)
Executable benches/runs.rs (/var/lib/automata-bench/work/target-head/release/deps/runs-85a152aa046a29b4)
Executable benches/scc.rs (/var/lib/automata-bench/work/target-head/release/deps/scc-1b22c641fd9d2d89)
Executable benches/storage.rs (/var/lib/automata-bench/work/target-head/release/deps/storage-f95e3d4a8c506941)
Executable benches/ts.rs (/var/lib/automata-bench/work/target-head/release/deps/ts-4948f6cc6a43d201)
Executable benches/wallclock.rs (/var/lib/automata-bench/work/target-head/release/deps/wallclock-93fb383f608d3bab)
== head: running scc
Finished `bench` profile [optimized] target(s) in 0.26s
Running benches/scc.rs (/var/lib/automata-bench/work/target-head/release/deps/scc-1b22c641fd9d2d89)
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.24s
Running benches/ts.rs (/var/lib/automata-bench/work/target-head/release/deps/ts-4948f6cc6a43d201)
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.19s
Running benches/runs.rs (/var/lib/automata-bench/work/target-head/release/deps/runs-85a152aa046a29b4)
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-a84ba41f760e70ed)
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.21s
Running benches/dpa.rs (/var/lib/automata-bench/work/target-head/release/deps/dpa-23bb829f074058ad)
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-f95e3d4a8c506941)
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.22s
Running benches/nondeterministic.rs (/var/lib/automata-bench/work/target-head/release/deps/nondeterministic-f164d05108dbce73)
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-ee53c00379271c59)
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-14422f732ec85029)
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.22s
Running benches/wallclock.rs (/var/lib/automata-bench/work/target-head/release/deps/wallclock-93fb383f608d3bab)
Gnuplot not found, using plotters backend
Benchmarking wallclock/scc/tarjan/scrambled_10000
Benchmarking wallclock/scc/tarjan/scrambled_10000: Analyzing
Benchmarking wallclock/dpa/normalized/scrambled_4000
Benchmarking wallclock/dpa/normalized/scrambled_4000: Analyzing
Benchmarking wallclock/dpa/complement/scrambled_4000
Benchmarking wallclock/dpa/complement/scrambled_4000: Analyzing
Benchmarking wallclock/dfa/minimize/redundant_4000
Benchmarking wallclock/dfa/minimize/redundant_4000: Analyzing
Benchmarking wallclock/dfa/accepts/word_100000
Benchmarking wallclock/dfa/accepts/word_100000: Analyzing
Benchmarking wallclock/nfa/subset_construction/nth_from_end_12
Benchmarking wallclock/nfa/subset_construction/nth_from_end_12: Analyzing
Benchmarking wallclock/nfa/determinize/nth_from_end_12
Benchmarking wallclock/nfa/determinize/nth_from_end_12: Analyzing
Benchmarking wallclock/hoa/parse/ltl
Benchmarking wallclock/hoa/parse/ltl: Analyzing
Benchmarking collect/clone/100000
Benchmarking collect/clone/100000: Analyzing
Benchmarking collect/collect_owned/100000
Benchmarking collect/collect_owned/100000: Analyzing
Benchmarking collect/collect_ref/100000
Benchmarking collect/collect_ref/100000: Analyzing
Benchmarking collect/map_edge_colors_collect_owned/100000
Benchmarking collect/map_edge_colors_collect_owned/100000: Analyzing
Benchmarking collect/clone/1000000
Benchmarking collect/clone/1000000: Analyzing
Benchmarking collect/collect_owned/1000000
Benchmarking collect/collect_owned/1000000: Analyzing
Benchmarking collect/collect_ref/1000000
Benchmarking collect/collect_ref/1000000: Analyzing
Benchmarking collect/map_edge_colors_collect_owned/1000000
Benchmarking collect/map_edge_colors_collect_owned/1000000: Analyzing
== head: building the Python bindings
🍹 Building a mixed python/rust project
🔗 Found pyo3 bindings with abi3 support
🐍 Found CPython 3.13 at /nix/store/vilynzly1pyhawy04ljmrp7n9ffr24qy-python3-3.13.17/bin/python3
📡 Using build options features from pyproject.toml
Compiling automata v0.2.1 (/var/lib/automata-bench/work/src-head)
Compiling automata-py v0.1.0 (/var/lib/automata-bench/work/src-head/python)
Finished `release` profile [optimized] target(s) in 1m 55s
📦 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.140 ms / 0.114 ms
dpa/equivalence/hard/l-nba-2 vs spot: 0.065 ms / 0.036 ms
dpa/equivalence/hard/m-nba-3 vs spot: 0.276 ms / 0.139 ms
dpa/equivalence/ltl/and-gf-3 vs spot: 0.010 ms / 0.012 ms
dpa/equivalence/ltl/eh-patterns-0 vs spot: 0.027 ms / 0.020 ms
dpa/equivalence/ltl/gf-equiv-3 vs spot: 0.024 ms / 0.033 ms
dpa/equivalence/ltl/gf-implies-3 vs spot: 0.013 ms / 0.019 ms
dpa/equivalence/ltl/gh-q-3 vs spot: 0.059 ms / 0.028 ms
dpa/equivalence/ltl/gh-r-3 vs spot: 0.026 ms / 0.069 ms
dpa/equivalence/ltl/go-theta-3 vs spot: 0.013 ms / 0.021 ms
dpa/equivalence/ltl/lily-patterns-1 vs spot: 0.014 ms / 0.016 ms
dpa/equivalence/ltl/ms-phi-r-1 vs spot: 0.012 ms / 0.038 ms
dpa/equivalence/ltl/ms-phi-s-1 vs spot: 0.012 ms / 0.039 ms
dpa/equivalence/ltl/rv-counter-3 vs spot: 0.030 ms / 0.013 ms
dpa/equivalence/ltl/sb-patterns-0 vs spot: 0.015 ms / 0.014 ms
dpa/equivalence/ltl/sejk-k-2 vs spot: 0.016 ms / 0.058 ms
dpa/equivalence/ltl/tv-uu-3 vs spot: 0.047 ms / 0.039 ms
dpa/equivalence/ltl/u-left-3 vs spot: 0.012 ms / 0.008 ms
dpa/equivalence/many_aps/and-gf-12 vs spot: 0.180 ms / 0.066 ms
dpa/equivalence/many_aps/gf-equiv-12 vs spot: 0.151 ms / 0.096 ms
dpa/equivalence/many_aps/r-right-10 vs spot: 0.076 ms / 0.025 ms
dpa/equivalence/many_aps/random-n16-a8-p4-s1 vs spot: 0.307 ms / 0.129 ms
dpa/equivalence/many_aps/random-n24-a12-p4-s1 vs spot: 1.494 ms / 0.448 ms
dpa/equivalence/many_aps/random-n32-a16-p4-s1 vs spot: 4.540 ms / 1.234 ms
dpa/equivalence/random/n128-a2-p6-s1 vs spot: 0.358 ms / 0.208 ms
dpa/equivalence/random/n16-a1-p3-s1 vs spot: 0.024 ms / 0.016 ms
dpa/equivalence/random/n256-a2-p8-s1 vs spot: 0.968 ms / 0.475 ms
dpa/equivalence/random/n64-a2-p4-s1 vs spot: 0.152 ms / 0.100 ms
dpa/inclusion/hard/l-dsa-3 vs spot: 0.076 ms / 0.060 ms
dpa/inclusion/hard/l-nba-2 vs spot: 0.039 ms / 0.023 ms
dpa/inclusion/hard/m-nba-3 vs spot: 0.163 ms / 0.085 ms
dpa/inclusion/ltl/and-gf-3 vs spot: 0.007 ms / 0.008 ms
dpa/inclusion/ltl/eh-patterns-0 vs spot: 0.018 ms / 0.018 ms
dpa/inclusion/ltl/gf-equiv-3 vs spot: 0.014 ms / 0.019 ms
dpa/inclusion/ltl/gf-implies-3 vs spot: 0.007 ms / 0.012 ms
dpa/inclusion/ltl/gh-q-3 vs spot: 0.038 ms / 0.028 ms
dpa/inclusion/ltl/gh-r-3 vs spot: 0.015 ms / 0.035 ms
dpa/inclusion/ltl/go-theta-3 vs spot: 0.008 ms / 0.016 ms
dpa/inclusion/ltl/lily-patterns-1 vs spot: 0.009 ms / 0.013 ms
dpa/inclusion/ltl/ms-phi-r-1 vs spot: 0.007 ms / 0.019 ms
dpa/inclusion/ltl/ms-phi-s-1 vs spot: 0.007 ms / 0.025 ms
dpa/inclusion/ltl/rv-counter-3 vs spot: 0.019 ms / 0.014 ms
dpa/inclusion/ltl/sb-patterns-0 vs spot: 0.009 ms / 0.012 ms
dpa/inclusion/ltl/sejk-k-2 vs spot: 0.009 ms / 0.028 ms
dpa/inclusion/ltl/tv-uu-3 vs spot: 0.031 ms / 0.029 ms
dpa/inclusion/ltl/u-left-3 vs spot: 0.008 ms / 0.009 ms
dpa/inclusion/many_aps/and-gf-12 vs spot: 0.143 ms / 0.053 ms
dpa/inclusion/many_aps/gf-equiv-12 vs spot: 0.082 ms / 0.050 ms
dpa/inclusion/many_aps/r-right-10 vs spot: 0.053 ms / 0.023 ms
dpa/inclusion/many_aps/random-n16-a8-p4-s1 vs spot: 0.258 ms / 0.105 ms
dpa/inclusion/many_aps/random-n24-a12-p4-s1 vs spot: 1.314 ms / 0.403 ms
dpa/inclusion/many_aps/random-n32-a16-p4-s1 vs spot: 4.144 ms / 1.133 ms
dpa/inclusion/random/n128-a2-p6-s1 vs spot: 0.213 ms / 0.125 ms
dpa/inclusion/random/n16-a1-p3-s1 vs spot: 0.015 ms / 0.010 ms
dpa/inclusion/random/n256-a2-p8-s1 vs spot: 0.550 ms / 0.296 ms
dpa/inclusion/random/n64-a2-p4-s1 vs spot: 0.090 ms / 0.060 ms
game/solve/random_few_10000 vs spot: 7.791 ms / 21.490 ms
game/solve/random_few_10000 vs oink-zlk: 7.791 ms / 2.744 ms
game/solve/random_few_10000 vs oink-ppp: 7.791 ms / 1.467 ms
game/solve/random_few_50000 vs spot: 80.470 ms / 684.008 ms
game/solve/random_few_50000 vs oink-zlk: 80.470 ms / 20.552 ms
game/solve/random_few_50000 vs oink-ppp: 80.470 ms / 17.620 ms
game/solve/random_many_10000 vs spot: 7.027 ms / 31.170 ms
game/solve/random_many_10000 vs oink-zlk: 7.027 ms / 2.808 ms
game/solve/random_many_10000 vs oink-ppp: 7.027 ms / 1.592 ms
game/solve/random_many_50000 vs spot: 81.713 ms / 667.496 ms
game/solve/random_many_50000 vs oink-zlk: 81.713 ms / 35.941 ms
game/solve/random_many_50000 vs oink-ppp: 81.713 ms / 26.636 ms
game/solve/ladder_10000 vs spot: 2.608 ms / 9.470 ms
game/solve/ladder_10000 vs oink-zlk: 2.608 ms / 0.307 ms
game/solve/ladder_10000 vs oink-ppp: 2.608 ms / 0.310 ms
game/solve/ladder_50000 vs spot: 20.438 ms / 71.234 ms
game/solve/ladder_50000 vs oink-zlk: 20.438 ms / 1.982 ms
game/solve/ladder_50000 vs oink-ppp: 20.438 ms / 2.215 ms
== head: 266 benchmarks, 16 wall-clock measurements, 74 comparisons