History · Versus Spot and Oink
CsrTs: real compressed sparse rows, nondeterministic, any alphabet (#166)
status done · queued 2026-11-11 18:41 · started 2026-11-11 18:41 · finished 2026-11-11 18:59
· · rustc 1.95.0 (59807616e 2026-04-14) (built from a source tarball) · valgrind-3.26.0 · pinned to cpu 1
| benchmark | instructions | est. cycles | L1 hits | LL hits | RAM hits | heap bytes | allocations |
|---|---|---|---|---|---|---|---|
| dfa::dfa::accepts_many_words::scrambled_1000 | 319 438 | 399 881 | 393 386 | 1 222 | 11 | 0 | 0 |
| dfa::dfa::complement::scrambled_1000 | 318 874 | 512 713 | 495 033 | 3 375 | 23 | 139 104 | 19 |
| dfa::dfa::complement::scrambled_4000 | 1 247 649 | 2 024 598 | 1 938 853 | 16 995 | 22 | 556 896 | 23 |
| dfa::dfa::equivalent::deep_difference_100 | 52 831 | 82 619 | 75 499 | 45 | 197 | 16 196 | 25 |
| dfa::dfa::equivalent::deep_difference_400 | 177 852 | 277 913 | 255 568 | 1 851 | 374 | 65 364 | 33 |
| dfa::dfa::equivalent::different_100 | 8 349 | 14 148 | 11 488 | 7 | 75 | 1 804 | 12 |
| dfa::dfa::equivalent::different_400 | 8 390 | 14 353 | 11 443 | 78 | 72 | 1 804 | 12 |
| dfa::dfa::equivalent::minimized_100 | 31 312 | 46 508 | 44 273 | 104 | 49 | 7 756 | 17 |
| dfa::dfa::equivalent::minimized_400 | 103 504 | 153 074 | 147 659 | 726 | 51 | 31 580 | 23 |
| dfa::dfa::give_word::empty_1000 | 1 795 234 | 2 450 035 | 2 422 480 | 4 916 | 85 | 152 864 | 3 738 |
| dfa::dfa::give_word::empty_4000 | 6 603 983 | 9 194 133 | 9 091 428 | 20 065 | 68 | 679 808 | 15 828 |
| dfa::dfa::give_word::far_1000 | 157 743 | 223 352 | 218 827 | 548 | 51 | 28 176 | 394 |
| dfa::dfa::give_word::far_4000 | 909 225 | 1 280 347 | 1 258 337 | 3 933 | 67 | 148 464 | 2 233 |
| dfa::dfa::intersection::scrambled_100 | 2 716 048 | 3 995 295 | 3 817 115 | 12 011 | 3 375 | 428 088 | 42 |
| dfa::dfa::intersection::scrambled_200 | 10 809 511 | 16 277 754 | 15 140 774 | 96 867 | 18 647 | 1 708 120 | 49 |
| dfa::dfa::intersection_is_empty::empty_100 | 50 659 | 79 033 | 72 533 | 33 | 181 | 15 700 | 20 |
| dfa::dfa::intersection_is_empty::empty_200 | 92 418 | 145 704 | 132 529 | 619 | 288 | 31 580 | 23 |
| dfa::dfa::is_empty_language::empty_1000 | 1 795 234 | 2 450 069 | 2 422 479 | 4 916 | 86 | 152 864 | 3 738 |
| dfa::dfa::is_empty_language::empty_4000 | 6 603 983 | 9 194 167 | 9 091 427 | 20 065 | 69 | 679 808 | 15 828 |
| dfa::dfa::minimize::minimal_1000 | 3 298 979 | 4 979 390 | 4 604 640 | 39 733 | 5 031 | 1 135 492 | 2 214 |
| dfa::dfa::minimize::minimal_4000 | 12 876 089 | 19 609 366 | 17 952 606 | 204 568 | 18 112 | 4 543 724 | 8 254 |
| dfa::dfa::minimize::redundant_1000 | 2 174 551 | 3 263 224 | 3 028 279 | 25 884 | 3 015 | 760 780 | 1 201 |
| dfa::dfa::minimize::redundant_4000 | 8 406 754 | 12 753 392 | 11 696 777 | 143 612 | 9 673 | 3 044 900 | 4 241 |
| dfa::dfa::minimize::scrambled_1000 | 3 502 256 | 5 309 295 | 4 877 655 | 51 034 | 5 042 | 1 116 052 | 2 217 |
| dfa::dfa::minimize::scrambled_4000 | 13 587 258 | 20 978 316 | 18 872 886 | 294 022 | 18 152 | 4 470 140 | 8 261 |
| dfa::dfa::minimize_moore_with_edge_colors::scrambled_1000 | 3 500 317 | 5 293 070 | 4 866 645 | 50 089 | 5 028 | 1 116 052 | 2 217 |
| dfa::dfa::minimize_moore_with_edge_colors::scrambled_4000 | 13 571 891 | 20 909 246 | 18 808 236 | 300 579 | 17 089 | 4 470 140 | 8 261 |
| dfa::dfa::union::scrambled_100 | 2 716 048 | 3 995 295 | 3 817 115 | 12 011 | 3 375 | 428 088 | 42 |
| dfa::dfa::union::scrambled_200 | 10 809 511 | 16 277 754 | 15 140 774 | 96 867 | 18 647 | 1 708 120 | 49 |
| dpa::dpa::accepted_word::chain_100 | 114 774 | 174 706 | 162 981 | 49 | 328 | – | – |
| dpa::dpa::accepted_word::chain_400 | 391 265 | 589 285 | 555 065 | 2 966 | 554 | – | – |
| dpa::dpa::accepted_word::scrambled_100 | 145 660 | 218 267 | 206 027 | 40 | 344 | – | – |
| dpa::dpa::accepted_word::scrambled_400 | 499 945 | 740 793 | 707 773 | 2 817 | 541 | – | – |
| dpa::dpa::accepted_word_fixtures::ltl | 495 442 | 716 693 | 690 418 | 2 301 | 422 | – | – |
| dpa::dpa::accepted_word_fixtures::synthetic | 1 255 420 | 1 812 010 | 1 739 545 | 11 994 | 357 | – | – |
| dpa::dpa::accepted_word_fixtures_by_atoms::ltl | 1 620 528 | 2 381 539 | 2 324 034 | 7 686 | 545 | – | – |
| dpa::dpa::accepted_word_fixtures_by_atoms::synthetic | 2 741 079 | 4 051 447 | 3 966 992 | 13 118 | 539 | – | – |
| dpa::dpa::collect_dpa::scrambled_1000 | 258 437 | 421 129 | 402 024 | 3 800 | 3 | – | – |
| dpa::dpa::collect_dpa::scrambled_4000 | 1 004 782 | 1 689 474 | 1 565 929 | 16 393 | 1 188 | – | – |
| dpa::dpa::complement::chain_1000 | 3 806 713 | 5 721 376 | 5 221 071 | 55 163 | 6 414 | – | – |
| dpa::dpa::complement::chain_4000 | 15 498 940 | 23 452 204 | 21 213 694 | 262 013 | 26 527 | – | – |
| dpa::dpa::complement::scrambled_1000 | 4 640 280 | 6 874 146 | 6 331 346 | 62 654 | 6 558 | – | – |
| dpa::dpa::complement::scrambled_4000 | 18 790 501 | 28 240 818 | 25 579 138 | 344 183 | 26 879 | – | – |
| dpa::dpa::complement_fixtures::ltl | 1 318 763 | 1 878 760 | 1 840 245 | 4 917 | 398 | – | – |
| dpa::dpa::complement_fixtures::many_aps | 12 439 582 | 17 914 573 | 17 431 468 | 86 576 | 1 435 | – | – |
| dpa::dpa::complement_fixtures::synthetic | 9 051 767 | 12 766 908 | 12 268 228 | 96 768 | 424 | – | – |
| dpa::dpa::complement_without_normalizing::scrambled_1000 | 542 899 | 786 566 | 757 876 | 5 157 | 83 | – | – |
| dpa::dpa::complement_without_normalizing::scrambled_4000 | 2 135 235 | 3 133 769 | 2 979 554 | 21 967 | 1 268 | – | – |
| dpa::dpa::equivalent_fixtures::many_aps | 18 698 034 | 27 049 368 | 26 383 813 | 120 413 | 1 814 | – | – |
| dpa::dpa::hoa_parse::ltl | 5 102 006 | 7 691 057 | 7 405 672 | 35 174 | 3 129 | – | – |
| dpa::dpa::hoa_parse::many_aps | 80 066 844 | 132 197 944 | 115 010 044 | 289 526 | 449 722 | – | – |
| dpa::dpa::hoa_parse::synthetic | 23 303 319 | 35 261 720 | 33 885 920 | 175 151 | 14 287 | – | – |
| dpa::dpa::hoa_print::ltl | 14 450 352 | 31 507 498 | 19 336 568 | 4 619 | 347 081 | – | – |
| dpa::dpa::hoa_print::many_aps | 17 708 492 | 25 446 101 | 25 324 141 | 21 998 | 342 | – | – |
| dpa::dpa::hoa_print::synthetic | 21 972 183 | 42 573 141 | 30 248 796 | 22 149 | 348 960 | – | – |
| dpa::dpa::included_fixtures::many_aps | 15 907 783 | 23 120 487 | 22 585 437 | 94 704 | 1 758 | – | – |
| dpa::dpa::included_in::complement_100 | 260 739 | 388 057 | 371 327 | 847 | 357 | – | – |
| dpa::dpa::included_in::complement_25 | 84 611 | 131 538 | 119 148 | 91 | 341 | – | – |
| dpa::dpa::included_in::complement_50 | 146 080 | 219 891 | 206 691 | 316 | 332 | – | – |
| dpa::dpa::included_in::normalized_100 | 524 060 | 764 122 | 738 412 | 1 425 | 531 | – | – |
| dpa::dpa::included_in::normalized_25 | 177 925 | 261 499 | 249 499 | 181 | 317 | – | – |
| dpa::dpa::included_in::normalized_50 | 302 723 | 440 103 | 425 463 | 429 | 357 | – | – |
| dpa::dpa::language_equivalent::complement_100 | 268 661 | 397 785 | 380 485 | 863 | 371 | – | – |
| dpa::dpa::language_equivalent::complement_25 | 86 600 | 134 357 | 121 477 | 91 | 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 429 | 1 353 424 | 2 237 | 652 | – | – |
| dpa::dpa::language_equivalent::normalized_25 | 315 935 | 456 811 | 442 156 | 264 | 381 | – | – |
| dpa::dpa::language_equivalent::normalized_50 | 564 774 | 808 312 | 791 022 | 553 | 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 338 940 | 4 851 580 | 52 924 | 6 364 | – | – |
| dpa::dpa::normalized::chain_4000 | 14 326 415 | 21 930 536 | 19 737 761 | 253 216 | 26 477 | – | – |
| dpa::dpa::normalized::scrambled_1000 | 4 346 572 | 6 491 383 | 5 961 573 | 60 406 | 6 508 | – | – |
| dpa::dpa::normalized::scrambled_4000 | 17 617 793 | 26 718 747 | 24 102 942 | 335 358 | 26 829 | – | – |
| dpa::dpa::normalized::scrambled_k4_1000 | 25 249 999 | 35 408 762 | 33 257 547 | 379 829 | 7 202 | – | – |
| dpa::dpa::normalized_fixtures::ltl | 1 272 930 | 1 821 551 | 1 786 296 | 4 692 | 337 | – | – |
| dpa::dpa::normalized_fixtures::many_aps | 12 275 183 | 17 722 044 | 17 254 454 | 83 823 | 1 385 | – | – |
| dpa::dpa::normalized_fixtures::synthetic | 8 843 733 | 12 508 695 | 12 039 790 | 91 093 | 384 | – | – |
| dpa::dpa::prefix_partition::chain_16 | 3 574 178 | 5 457 398 | 5 390 178 | 2 286 | 1 594 | – | – |
| dpa::dpa::prefix_partition::chain_8 | 916 107 | 1 409 361 | 1 379 801 | 508 | 772 | – | – |
| dpa::dpa::prefix_partition::scrambled_16 | 3 999 698 | 6 155 542 | 6 070 422 | 3 766 | 1 894 | – | – |
| dpa::dpa::prefix_partition::scrambled_8 | 1 086 510 | 1 669 881 | 1 639 181 | 666 | 782 | – | – |
| dpa::dpa::rejected_word::chain_100 | 885 231 | 1 281 987 | 1 241 397 | 2 833 | 755 | – | – |
| dpa::dpa::rejected_word::chain_400 | 3 441 573 | 5 130 458 | 4 832 068 | 47 981 | 1 671 | – | – |
| dpa::dpa::rejected_word::scrambled_100 | 235 103 | 360 734 | 329 644 | 506 | 816 | – | – |
| dpa::dpa::rejected_word::scrambled_400 | 887 076 | 1 355 284 | 1 244 359 | 10 236 | 1 707 | – | – |
| dpa::dpa::sccs::chain_1000 | 511 023 | 774 862 | 699 657 | 6 830 | 1 173 | – | – |
| dpa::dpa::sccs::chain_4000 | 1 971 630 | 3 022 655 | 2 696 940 | 29 891 | 5 036 | – | – |
| dpa::dpa::sccs::scrambled_1000 | 576 822 | 871 308 | 795 343 | 8 221 | 996 | – | – |
| dpa::dpa::sccs::scrambled_4000 | 2 295 945 | 3 543 747 | 3 164 887 | 46 274 | 4 214 | – | – |
| dpa::dpa::witness_colors::chain_100 | 4 471 341 | 6 365 988 | 6 245 903 | 9 009 | 2 144 | – | – |
| dpa::dpa::witness_colors::chain_400 | 43 697 424 | 62 813 104 | 61 212 849 | 194 569 | 17 926 | – | – |
| dpa::dpa::witness_colors::scrambled_100 | 3 895 188 | 5 531 955 | 5 442 545 | 8 761 | 1 303 | – | – |
| dpa::dpa::witness_colors::scrambled_400 | 29 949 989 | 42 974 338 | 42 154 343 | 145 736 | 2 609 | – | – |
| dpa::dpa::witness_inequivalence::complement_100 | 268 661 | 397 823 | 380 483 | 864 | 372 | – | – |
| dpa::dpa::witness_inequivalence::complement_25 | 86 600 | 134 395 | 121 475 | 92 | 356 | – | – |
| dpa::dpa::witness_inequivalence::complement_50 | 149 885 | 224 821 | 211 036 | 328 | 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 590 | 119 150 | 87 | 343 | – | – |
| dpa::dpa::witness_not_subset_of::complement_50 | 146 080 | 219 955 | 206 690 | 315 | 334 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_100 | 524 060 | 764 174 | 738 414 | 1 421 | 533 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_25 | 177 925 | 261 563 | 249 498 | 180 | 319 | – | – |
| dpa::dpa::witness_not_subset_of::normalized_50 | 302 723 | 440 143 | 425 468 | 422 | 359 | – | – |
| dpa::dpa::witnesses_fixtures::ltl | 1 970 349 | 2 739 907 | 2 683 407 | 5 903 | 771 | – | – |
| dpa::dpa::witnesses_fixtures::synthetic | 15 821 117 | 22 786 083 | 22 257 723 | 100 205 | 781 | – | – |
| 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 753 165 | 2 378 436 | 2 341 356 | 437 | 997 | 154 184 | 2 615 |
| learning::learning::lstar_mealy::counting_8 | 446 458 | 624 608 | 598 868 | 136 | 716 | 40 280 | 852 |
| learning::learning::sprout_parity::inf_ab_100 | 1 146 477 | 1 639 558 | 1 582 403 | 1 974 | 1 351 | 200 320 | 1 868 |
| learning::learning::sprout_parity::inf_ab_400 | 2 353 128 | 3 351 364 | 3 241 519 | 8 858 | 1 873 | 404 944 | 3 645 |
| nondeterministic::nondeterministic::fixture_accepts::ltl | 731 487 | 1 132 488 | 1 084 618 | 5 934 | 520 | – | – |
| nondeterministic::nondeterministic::nba_accepts::nba_400 | 122 996 323 | 179 087 545 | 168 150 685 | 1 663 541 | 74 833 | – | – |
| nondeterministic::nondeterministic::nba_witness::nba_4000 | 17 383 333 | 26 028 582 | 25 014 717 | 138 520 | 9 179 | – | – |
| nondeterministic::nondeterministic::nca_accepts::nca_400 | 254 927 534 | 371 570 174 | 345 867 389 | 4 569 357 | 81 600 | – | – |
| nondeterministic::nondeterministic::nca_witness::nca_4000 | 21 904 941 | 33 241 977 | 31 087 897 | 325 662 | 15 022 | – | – |
| nondeterministic::nondeterministic::nma_witness::nma_1000 | 25 383 666 | 37 526 707 | 35 512 952 | 370 005 | 4 678 | – | – |
| nondeterministic::nondeterministic::npa_accepts::empty_npa_400 | 458 821 236 | 670 096 369 | 622 425 029 | 8 911 408 | 88 980 | – | – |
| nondeterministic::nondeterministic::npa_accepts::npa_100 | 29 740 298 | 42 889 015 | 41 005 525 | 287 742 | 12 708 | – | – |
| nondeterministic::nondeterministic::npa_accepts::npa_400 | 122 955 922 | 179 060 750 | 168 131 120 | 1 662 018 | 74 844 | – | – |
| nondeterministic::nondeterministic::npa_witness::empty_npa_1000 | 9 427 737 | 13 978 641 | 13 247 746 | 123 177 | 3 286 | – | – |
| nondeterministic::nondeterministic::npa_witness::empty_npa_4000 | 38 265 192 | 57 449 426 | 53 485 951 | 657 343 | 19 336 | – | – |
| nondeterministic::nondeterministic::npa_witness::npa_1000 | 2 979 072 | 4 478 089 | 4 313 264 | 20 778 | 1 741 | – | – |
| nondeterministic::nondeterministic::npa_witness::npa_4000 | 23 816 129 | 35 551 281 | 34 340 106 | 178 010 | 9 175 | – | – |
| nondeterministic::nondeterministic::nra_witness::nra_4000 | 21 455 583 | 32 709 833 | 30 163 393 | 337 214 | 24 582 | – | – |
| 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 644 | 10 761 109 | 3 122 | 255 | 724 664 | 500 |
| runs::runs::dpa_accepts_lassos::short | 376 801 | 502 346 | 497 086 | 401 | 93 | 26 236 | 472 |
| runs::runs::dpa_recurrent_edge_colors::long | 15 221 636 | 19 508 096 | 19 456 376 | 5 948 | 628 | 922 144 | 2 090 |
| runs::runs::dpa_recurrent_edge_colors::short | 1 058 624 | 1 435 448 | 1 424 303 | 1 242 | 141 | 168 684 | 1 708 |
| runs::runs::dpa_recurrent_states::long | 13 767 740 | 19 256 810 | 19 225 745 | 3 784 | 347 | 788 104 | 860 |
| runs::runs::dpa_recurrent_states::short | 596 810 | 814 523 | 807 323 | 551 | 127 | 81 996 | 782 |
| runs::runs::dpa_visited_sequences::long | 8 707 283 | 12 043 619 | 12 009 309 | 4 545 | 331 | 2 190 780 | 850 |
| runs::runs::dpa_visited_sequences::short | 350 418 | 483 834 | 479 184 | 503 | 61 | 29 986 | 545 |
| runs::runs::fixture_accepts_lassos::ltl | 7 833 947 | 11 053 582 | 11 022 407 | 5 549 | 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 390 812 | 2 084 726 | 2 039 536 | 4 936 | 586 | 180 200 | 37 |
| storage::storage::add_edges_dense::k8_5000 | 4 311 427 | 6 496 049 | 6 309 524 | 17 831 | 2 782 | 671 728 | 40 |
| storage::storage::add_edges_linked::k2_5000 | 1 252 451 | 2 165 062 | 2 003 042 | 14 218 | 2 598 | 1 113 960 | 26 |
| storage::storage::add_edges_linked::k8_5000 | 6 144 063 | 10 329 624 | 9 400 509 | 75 755 | 15 724 | 3 866 496 | 28 |
| storage::storage::clone_csr::k2_10000 | 22 537 | 76 085 | 42 575 | 6 618 | 12 | 210 012 | 4 |
| storage::storage::clone_dense::k2_10000 | 15 042 | 81 072 | 25 732 | 2 248 | 1 260 | 110 008 | 4 |
| storage::storage::clone_linked::k2_10000 | 380 760 | 911 493 | 539 733 | 12 465 | 8 841 | 680 008 | 3 |
| storage::storage::complete_dense::partial_5000 | 230 702 | 348 722 | 343 457 | 885 | 24 | 56 | 1 |
| storage::storage::complete_linked::partial_5000 | 1 183 129 | 1 690 433 | 1 602 968 | 6 944 | 1 507 | 65 592 | 15 |
| storage::storage::edges_from_all_states_csr::k2_2000 | 34 038 | 38 328 | 38 043 | 29 | 4 | 0 | 0 |
| storage::storage::edges_from_all_states_csr::k8_2000 | 34 038 | 38 628 | 37 968 | 104 | 4 | 0 | 0 |
| storage::storage::edges_from_all_states_dense::k2_2000 | 92 047 | 101 257 | 99 847 | 233 | 7 | 0 | 0 |
| storage::storage::edges_from_all_states_dense::k8_2000 | 128 047 | 140 511 | 135 041 | 1 038 | 8 | 0 | 0 |
| storage::storage::edges_from_all_states_linked::k2_2000 | 70 033 | 88 755 | 77 925 | 2 131 | 5 | 0 | 0 |
| storage::storage::edges_from_all_states_linked::k8_2000 | 154 033 | 205 731 | 168 681 | 7 375 | 5 | 0 | 0 |
| storage::storage::minimize_csr::redundant_2000 | 4 240 645 | 6 376 529 | 5 902 609 | 60 603 | 4 883 | 1 505 420 | 2 212 |
| storage::storage::minimize_csr::redundant_8000 | 16 584 073 | 25 284 397 | 23 034 757 | 275 488 | 24 920 | 6 023 300 | 8 250 |
| storage::storage::minimize_dense::redundant_2000 | 4 434 823 | 6 603 981 | 6 149 506 | 58 044 | 4 693 | 1 522 156 | 2 221 |
| storage::storage::minimize_dense::redundant_8000 | 17 408 185 | 26 418 899 | 24 122 739 | 278 891 | 25 763 | 6 090 340 | 8 261 |
| storage::storage::minimize_linked::redundant_2000 | 4 305 957 | 6 557 531 | 6 009 161 | 61 850 | 6 832 | 1 522 156 | 2 221 |
| storage::storage::minimize_linked::redundant_8000 | 16 930 017 | 26 057 752 | 23 610 767 | 302 700 | 26 671 | 6 090 340 | 8 261 |
| storage::storage::overwrite_edges_dense::k2_5000 | 2 170 843 | 3 296 781 | 3 236 621 | 7 909 | 589 | 180 200 | 37 |
| storage::storage::overwrite_edges_linked::k2_5000 | 3 410 553 | 6 005 649 | 5 286 679 | 44 751 | 14 149 | 2 031 464 | 27 |
| storage::storage::predecessors_of_all_states_csr::k2_2000 | 251 025 | 342 244 | 316 539 | 4 959 | 26 | 48 008 | 3 |
| storage::storage::predecessors_of_all_states_dense::k2_2000 | 232 309 | 311 709 | 302 159 | 1 616 | 42 | 32 008 | 3 |
| storage::storage::predecessors_of_all_states_linked::k2_2000 | 70 033 | 93 657 | 76 692 | 3 365 | 4 | 0 | 0 |
| storage::storage::product_successor_csr::n200 | 48 082 | 58 507 | 58 107 | 38 | 6 | 0 | 0 |
| storage::storage::product_successor_dense::n200 | 65 088 | 76 567 | 76 122 | 40 | 7 | 0 | 0 |
| storage::storage::product_successor_linked::n200 | 46 540 | 60 130 | 56 995 | 585 | 6 | 0 | 0 |
| storage::storage::reachable_states_csr::k2_8000 | 988 709 | 1 471 287 | 1 410 827 | 11 896 | 28 | 17 368 | 11 |
| storage::storage::reachable_states_dense::k2_8000 | 1 173 507 | 1 692 012 | 1 646 962 | 8 835 | 25 | 17 368 | 11 |
| storage::storage::reachable_states_linked::k2_8000 | 980 094 | 1 509 063 | 1 410 258 | 19 516 | 35 | 17 368 | 11 |
| storage::storage::remove_state_dense::k2_10000 | 924 162 | 1 347 826 | 1 173 246 | 21 511 | 1 915 | 176 000 | 1 003 |
| storage::storage::remove_state_linked::k2_10000 | 997 019 | 1 358 213 | 1 319 763 | 7 417 | 39 | 80 000 | 3 000 |
| storage::storage::run_many_words_csr::count_1000 | 504 041 | 624 024 | 614 144 | 1 934 | 6 | 0 | 0 |
| storage::storage::run_many_words_dense::count_1000 | 512 042 | 601 929 | 592 164 | 1 911 | 6 | 0 | 0 |
| storage::storage::run_many_words_linked::count_1000 | 481 040 | 611 107 | 601 112 | 1 957 | 6 | 0 | 0 |
| storage::storage::run_one_word_csr::len_100000 | 2 450 042 | 3 025 395 | 2 993 795 | 6 285 | 5 | 0 | 0 |
| storage::storage::run_one_word_dense::len_100000 | 2 600 042 | 3 025 345 | 2 993 800 | 6 274 | 5 | 0 | 0 |
| storage::storage::run_one_word_linked::len_100000 | 2 350 039 | 2 975 428 | 2 943 773 | 6 296 | 5 | 0 | 0 |
| storage::storage::successor_all_pairs_csr::k2_2000 | 96 205 | 117 081 | 113 641 | 646 | 6 | 8 | 1 |
| storage::storage::successor_all_pairs_csr::k8_2000 | 510 259 | 627 149 | 616 199 | 2 148 | 6 | 32 | 1 |
| storage::storage::successor_all_pairs_dense::k2_2000 | 150 205 | 169 478 | 168 048 | 237 | 7 | 8 | 1 |
| storage::storage::successor_all_pairs_dense::k8_2000 | 778 259 | 880 782 | 875 297 | 1 048 | 7 | 32 | 1 |
| storage::storage::successor_all_pairs_linked::k2_2000 | 110 202 | 141 070 | 130 135 | 2 138 | 7 | 8 | 1 |
| storage::storage::successor_all_pairs_linked::k8_2000 | 752 256 | 948 110 | 910 950 | 7 383 | 7 | 32 | 1 |
| ts::ts::add_edges_in_order::k2_5000 | 1 062 446 | 1 774 972 | 1 613 037 | 14 215 | 2 596 | 1 113 960 | 26 |
| ts::ts::add_edges_in_order::k8_5000 | 5 384 058 | 8 769 462 | 7 840 522 | 75 734 | 15 722 | 3 866 496 | 28 |
| ts::ts::add_edges_in_reverse::k2_5000 | 1 062 446 | 1 774 180 | 1 613 235 | 14 017 | 2 596 | 1 113 960 | 26 |
| ts::ts::builder_with_edges::k2_5000 | 79 938 182 | 95 907 047 | 93 436 287 | 450 577 | 6 225 | 1 739 532 | 45 |
| ts::ts::canonical_naming::scrambled_1500 | 3 034 522 | 4 445 169 | 4 255 454 | 21 871 | 2 296 | 463 808 | 5 846 |
| ts::ts::canonical_naming::scrambled_500 | 938 266 | 1 350 758 | 1 307 583 | 3 175 | 780 | 134 336 | 1 831 |
| ts::ts::clone::scrambled_10000 | 381 079 | 912 268 | 540 138 | 12 483 | 8 849 | 680 008 | 3 |
| ts::ts::clone::scrambled_40000 | 1 521 316 | 3 857 681 | 2 156 706 | 42 576 | 42 517 | 2 720 008 | 3 |
| ts::ts::collect_dts::scrambled_10000 | 2 934 925 | 5 185 584 | 4 626 499 | 37 169 | 10 664 | 2 228 064 | 27 |
| ts::ts::collect_dts::scrambled_40000 | 11 679 372 | 20 762 632 | 18 409 072 | 135 300 | 47 916 | 8 912 736 | 31 |
| ts::ts::determinize::nth_from_end_10 | 4 305 680 | 6 339 242 | 5 978 947 | 22 093 | 7 138 | 651 720 | 6 013 |
| ts::ts::determinize::nth_from_end_12 | 19 177 588 | 28 064 700 | 26 556 095 | 98 791 | 28 990 | 2 732 600 | 26 423 |
| ts::ts::determinize::nth_from_end_8 | 980 440 | 1 446 599 | 1 364 229 | 2 992 | 1 926 | 156 552 | 1 396 |
| ts::ts::determinize_propositional::aps_6_n_6 | 4 088 248 | 6 427 459 | 5 941 679 | 20 030 | 11 018 | 1 332 896 | 4 208 |
| ts::ts::determinize_propositional::aps_7_n_6 | 4 295 587 | 6 716 410 | 6 179 155 | 25 327 | 11 732 | 1 197 930 | 1 967 |
| ts::ts::determinize_propositional::aps_8_n_6 | 25 052 413 | 38 429 955 | 35 513 095 | 168 370 | 59 286 | 5 240 456 | 13 678 |
| ts::ts::edges_from_all_states::scrambled_2000 | 74 646 | 93 978 | 82 738 | 2 157 | 13 | 0 | 0 |
| ts::ts::edges_from_all_states::scrambled_k8_2000 | 158 578 | 210 859 | 173 394 | 7 402 | 13 | 0 | 0 |
| ts::ts::erase_state_colors_collect::scrambled_10000 | 1 846 855 | 3 177 597 | 2 618 447 | 37 175 | 10 665 | 2 228 064 | 27 |
| ts::ts::into_dfa::scrambled_10000 | 3 054 983 | 5 375 920 | 4 816 590 | 37 183 | 10 669 | 2 228 064 | 27 |
| ts::ts::map_edge_colors_collect::scrambled_10000 | 1 928 468 | 3 407 504 | 2 789 159 | 38 451 | 12 174 | 2 490 192 | 27 |
| ts::ts::map_edge_colors_collect::scrambled_40000 | 7 655 047 | 13 651 456 | 11 061 741 | 140 335 | 53 944 | 9 961 296 | 31 |
| ts::ts::matching_product_successor_index::n200 | 47 602 | 62 598 | 58 423 | 597 | 34 | 0 | 0 |
| ts::ts::minimal_representative_of_all_states::scrambled_100 | 2 002 068 | 2 856 122 | 2 852 767 | 13 | 94 | 347 504 | 4 679 |
| ts::ts::minimal_representative_of_all_states::scrambled_300 | 16 088 404 | 23 069 254 | 23 054 089 | 2 354 | 97 | 3 116 784 | 38 196 |
| ts::ts::minimal_representatives::scrambled_2000 | 3 248 796 | 4 585 532 | 4 538 727 | 8 920 | 63 | 322 944 | 7 709 |
| ts::ts::minimal_representatives::scrambled_8000 | 14 321 191 | 20 180 453 | 19 965 688 | 42 575 | 54 | 1 464 896 | 32 693 |
| ts::ts::predecessors_of_all_states::scrambled_2000 | 74 646 | 98 850 | 81 505 | 3 392 | 11 | 0 | 0 |
| ts::ts::predecessors_of_all_states::scrambled_8000 | 296 578 | 397 297 | 321 777 | 15 020 | 12 | 0 | 0 |
| ts::ts::reachable_states::scrambled_2000 | 243 901 | 374 295 | 353 730 | 3 609 | 72 | 4 336 | 9 |
| ts::ts::reachable_states::scrambled_8000 | 964 480 | 1 493 862 | 1 394 777 | 19 523 | 42 | 17 368 | 11 |
| ts::ts::remove_edges_from_matching::scrambled_10000 | 446 232 | 589 810 | 565 655 | 4 656 | 25 | 64 000 | 2 000 |
| ts::ts::remove_edges_from_matching::scrambled_40000 | 746 232 | 941 310 | 890 280 | 10 031 | 25 | 64 000 | 2 000 |
| ts::ts::remove_state::scrambled_10000 | 997 019 | 1 358 319 | 1 319 759 | 7 418 | 42 | 80 000 | 3 000 |
| ts::ts::remove_state::scrambled_40000 | 1 357 019 | 1 772 783 | 1 703 643 | 13 534 | 42 | 80 000 | 3 000 |
| ts::ts::scc_minimal_representatives::small_cycles_100 | 210 321 | 304 069 | 289 569 | 44 | 408 | 44 272 | 309 |
| ts::ts::scc_minimal_representatives::small_cycles_400 | 1 192 086 | 1 679 371 | 1 629 931 | 3 889 | 857 | 354 148 | 1 325 |
| ts::ts::subset_construction::nth_from_end_10 | 9 439 133 | 13 173 435 | 12 681 495 | 45 279 | 7 587 | 1 073 520 | 9 919 |
| ts::ts::subset_construction::nth_from_end_12 | 42 061 900 | 58 466 837 | 56 225 962 | 218 204 | 32 853 | 4 518 976 | 43 857 |
| ts::ts::subset_construction::nth_from_end_8 | 2 040 011 | 2 862 504 | 2 756 754 | 6 051 | 2 157 | 257 104 | 2 276 |
| ts::ts::successor_index_all_pairs::scrambled_2000 | 110 814 | 142 232 | 130 952 | 2 158 | 14 | 8 | 1 |
| ts::ts::successor_index_all_pairs::scrambled_k8_2000 | 752 800 | 949 211 | 911 666 | 7 404 | 15 | 32 | 1 |
Criterion means of a single run. They depend on the machine and are not compared; use the instruction counts above for that.
| benchmark | head |
|---|---|
| collect/clone/100000 | 4.41 ms (4.34 ms … 4.48 ms) |
| collect/clone/1000000 | 39.45 ms (39.07 ms … 39.83 ms) |
| collect/collect_owned/100000 | 8.25 ms (8.18 ms … 8.33 ms) |
| collect/collect_owned/1000000 | 78.18 ms (77.10 ms … 79.25 ms) |
| collect/collect_ref/100000 | 4.25 ms (4.16 ms … 4.35 ms) |
| collect/collect_ref/1000000 | 75.26 ms (74.42 ms … 76.11 ms) |
| collect/map_edge_colors_collect_owned/100000 | 6.46 ms (6.32 ms … 6.61 ms) |
| collect/map_edge_colors_collect_owned/1000000 | 72.09 ms (71.47 ms … 72.71 ms) |
| wallclock/dfa/accepts/word_100000 | 925.17 µs (900.65 µs … 949.70 µs) |
| wallclock/dfa/minimize/redundant_4000 | 1.36 ms (1.36 ms … 1.36 ms) |
| wallclock/dpa/complement/scrambled_4000 | 3.39 ms (3.35 ms … 3.44 ms) |
| wallclock/dpa/normalized/scrambled_4000 | 3.09 ms (3.08 ms … 3.09 ms) |
| wallclock/hoa/parse/ltl | 885.70 µs (868.96 µs … 902.45 µs) |
| wallclock/nfa/determinize/nth_from_end_12 | 3.42 ms (3.40 ms … 3.44 ms) |
| wallclock/nfa/subset_construction/nth_from_end_12 | 8.49 ms (8.38 ms … 8.61 ms) |
| wallclock/scc/tarjan/scrambled_10000 | 2.20 ms (2.17 ms … 2.22 ms) |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| hard/l-dsa-3 | spot | 125.00 µs | 119.82 µs | 1.04× | – / – | yes |
| hard/l-nba-2 | spot | 55.80 µs | 36.54 µs | 1.53× | – / – | yes |
| hard/m-nba-3 | spot | 236.72 µs | 135.28 µs | 1.75× | – / – | yes |
| ltl/and-gf-3 | spot | 9.12 µs | 12.36 µs | 0.74× | – / – | yes |
| ltl/eh-patterns-0 | spot | 21.84 µs | 20.08 µs | 1.09× | – / – | yes |
| ltl/gf-equiv-3 | spot | 20.42 µs | 34.22 µs | 0.60× | – / – | yes |
| ltl/gf-implies-3 | spot | 10.68 µs | 19.56 µs | 0.55× | – / – | yes |
| ltl/gh-q-3 | spot | 50.84 µs | 28.70 µs | 1.77× | – / – | yes |
| ltl/gh-r-3 | spot | 21.20 µs | 69.42 µs | 0.31× | – / – | yes |
| ltl/go-theta-3 | spot | 11.20 µs | 21.44 µs | 0.52× | – / – | yes |
| ltl/lily-patterns-1 | spot | 12.10 µs | 16.12 µs | 0.75× | – / – | yes |
| ltl/ms-phi-r-1 | spot | 10.48 µs | 39.02 µs | 0.27× | – / – | yes |
| ltl/ms-phi-s-1 | spot | 10.40 µs | 40.66 µs | 0.26× | – / – | yes |
| ltl/rv-counter-3 | spot | 27.80 µs | 13.04 µs | 2.13× | – / – | yes |
| ltl/sb-patterns-0 | spot | 12.70 µs | 14.12 µs | 0.90× | – / – | yes |
| ltl/sejk-k-2 | spot | 13.60 µs | 59.24 µs | 0.23× | – / – | yes |
| ltl/tv-uu-3 | spot | 41.30 µs | 37.56 µs | 1.10× | – / – | yes |
| ltl/u-left-3 | spot | 10.64 µs | 8.92 µs | 1.19× | – / – | yes |
| many_aps/and-gf-12 | spot | 160.20 µs | 65.08 µs | 2.46× | – / – | yes |
| many_aps/gf-equiv-12 | spot | 130.48 µs | 92.36 µs | 1.41× | – / – | yes |
| many_aps/r-right-10 | spot | 65.08 µs | 25.36 µs | 2.57× | – / – | yes |
| many_aps/random-n16-a8-p4-s1 | spot | 262.48 µs | 129.02 µs | 2.03× | – / – | yes |
| many_aps/random-n24-a12-p4-s1 | spot | 1.34 ms | 461.30 µs | 2.91× | – / – | yes |
| many_aps/random-n32-a16-p4-s1 | spot | 3.75 ms | 1.17 ms | 3.21× | – / – | yes |
| random/n128-a2-p6-s1 | spot | 330.50 µs | 205.96 µs | 1.60× | – / – | yes |
| random/n16-a1-p3-s1 | spot | 21.54 µs | 15.74 µs | 1.37× | – / – | yes |
| random/n256-a2-p8-s1 | spot | 892.41 µs | 469.72 µs | 1.90× | – / – | yes |
| random/n64-a2-p4-s1 | spot | 141.88 µs | 97.86 µs | 1.45× | – / – | yes |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| hard/l-dsa-3 | spot | 71.28 µs | 61.08 µs | 1.17× | – / – | yes |
| hard/l-nba-2 | spot | 34.84 µs | 22.76 µs | 1.53× | – / – | yes |
| hard/m-nba-3 | spot | 148.20 µs | 81.78 µs | 1.81× | – / – | yes |
| ltl/and-gf-3 | spot | 5.80 µs | 8.12 µs | 0.71× | – / – | yes |
| ltl/eh-patterns-0 | spot | 14.42 µs | 17.96 µs | 0.80× | – / – | yes |
| ltl/gf-equiv-3 | spot | 11.58 µs | 18.96 µs | 0.61× | – / – | yes |
| ltl/gf-implies-3 | spot | 6.24 µs | 11.48 µs | 0.54× | – / – | yes |
| ltl/gh-q-3 | spot | 33.02 µs | 27.68 µs | 1.19× | – / – | yes |
| ltl/gh-r-3 | spot | 12.44 µs | 35.28 µs | 0.35× | – / – | yes |
| ltl/go-theta-3 | spot | 6.94 µs | 15.96 µs | 0.43× | – / – | yes |
| ltl/lily-patterns-1 | spot | 8.12 µs | 13.90 µs | 0.58× | – / – | yes |
| ltl/ms-phi-r-1 | spot | 6.12 µs | 19.36 µs | 0.32× | – / – | yes |
| ltl/ms-phi-s-1 | spot | 6.08 µs | 25.36 µs | 0.24× | – / – | yes |
| ltl/rv-counter-3 | spot | 17.92 µs | 14.22 µs | 1.26× | – / – | yes |
| ltl/sb-patterns-0 | spot | 7.72 µs | 12.08 µs | 0.64× | – / – | yes |
| ltl/sejk-k-2 | spot | 7.86 µs | 28.50 µs | 0.28× | – / – | yes |
| ltl/tv-uu-3 | spot | 28.34 µs | 28.78 µs | 0.98× | – / – | yes |
| ltl/u-left-3 | spot | 6.76 µs | 8.72 µs | 0.78× | – / – | yes |
| many_aps/and-gf-12 | spot | 122.86 µs | 51.82 µs | 2.37× | – / – | yes |
| many_aps/gf-equiv-12 | spot | 74.28 µs | 51.26 µs | 1.45× | – / – | yes |
| many_aps/r-right-10 | spot | 46.76 µs | 23.44 µs | 1.99× | – / – | yes |
| many_aps/random-n16-a8-p4-s1 | spot | 213.88 µs | 95.08 µs | 2.25× | – / – | yes |
| many_aps/random-n24-a12-p4-s1 | spot | 1.01 ms | 377.18 µs | 2.69× | – / – | yes |
| many_aps/random-n32-a16-p4-s1 | spot | 3.39 ms | 1.06 ms | 3.20× | – / – | yes |
| random/n128-a2-p6-s1 | spot | 201.46 µs | 123.84 µs | 1.63× | – / – | yes |
| random/n16-a1-p3-s1 | spot | 13.12 µs | 10.28 µs | 1.28× | – / – | yes |
| random/n256-a2-p8-s1 | spot | 508.26 µs | 293.02 µs | 1.73× | – / – | yes |
| random/n64-a2-p4-s1 | spot | 85.62 µs | 62.36 µs | 1.37× | – / – | yes |
| input | reference | ours | reference | ours / reference | size (ours / reference) | same result |
|---|---|---|---|---|---|---|
| ladder_10000 | oink-ppp | 2.53 ms | 303.00 µs | 8.36× | 10000 / 10000 | yes |
| ladder_10000 | oink-zlk | 2.53 ms | 307.00 µs | 8.25× | 10000 / 10000 | yes |
| ladder_10000 | spot | 2.53 ms | 9.54 ms | 0.27× | 10000 / 10000 | yes |
| ladder_50000 | oink-ppp | 19.49 ms | 2.09 ms | 9.33× | 50000 / 50000 | yes |
| ladder_50000 | oink-zlk | 19.49 ms | 2.12 ms | 9.21× | 50000 / 50000 | yes |
| ladder_50000 | spot | 19.49 ms | 72.52 ms | 0.27× | 50000 / 50000 | yes |
| random_few_10000 | oink-ppp | 6.74 ms | 1.39 ms | 4.84× | 10000 / 10000 | yes |
| random_few_10000 | oink-zlk | 6.74 ms | 2.66 ms | 2.53× | 10000 / 10000 | yes |
| random_few_10000 | spot | 6.74 ms | 20.43 ms | 0.33× | 10000 / 10000 | yes |
| random_few_50000 | oink-ppp | 72.46 ms | 15.43 ms | 4.70× | 50000 / 50000 | yes |
| random_few_50000 | oink-zlk | 72.46 ms | 18.40 ms | 3.94× | 50000 / 50000 | yes |
| random_few_50000 | spot | 72.46 ms | 651.40 ms | 0.11× | 50000 / 50000 | yes |
| random_many_10000 | oink-ppp | 6.48 ms | 1.54 ms | 4.20× | 10000 / 10000 | yes |
| random_many_10000 | oink-zlk | 6.48 ms | 2.60 ms | 2.49× | 10000 / 10000 | yes |
| random_many_10000 | spot | 6.48 ms | 29.96 ms | 0.22× | 10000 / 10000 | yes |
| random_many_50000 | oink-ppp | 65.65 ms | 26.19 ms | 2.51× | 50000 / 50000 | yes |
| random_many_50000 | oink-zlk | 65.65 ms | 37.03 ms | 1.77× | 50000 / 50000 | yes |
| random_many_50000 | spot | 65.65 ms | 643.46 ms | 0.10× | 50000 / 50000 | yes |
== head 91ab2741d67d80a15ea1c1cabf1ec70b87abaf59: building ["scc", "ts", "runs", "dfa", "dpa", "storage", "nondeterministic", "learning", "game"] ["wallclock"]
Compiling automata v0.2.1 (/var/lib/automata-bench/work/src-head)
Finished `bench` profile [optimized] target(s) in 4m 07s
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.21s
Running benches/scc.rs (/var/lib/automata-bench/work/target-head/release/deps/scc-b88e81c5af8ec1fc)
gungraun_runner: Warn : The RUST_LOG environment variable to set the log level changed to GUNGRAUN_LOG
== head: running ts
Finished `bench` profile [optimized] target(s) in 0.21s
Running benches/ts.rs (/var/lib/automata-bench/work/target-head/release/deps/ts-bb6ee25ff0b06f0f)
gungraun_runner: Warn : The RUST_LOG environment variable to set the log level changed to GUNGRAUN_LOG
== head: running runs
Finished `bench` profile [optimized] target(s) in 0.22s
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.18s
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.19s
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.19s
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.19s
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.21s
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.21s
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.22s
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 25s
📦 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.125 ms / 0.120 ms
dpa/equivalence/hard/l-nba-2 vs spot: 0.056 ms / 0.037 ms
dpa/equivalence/hard/m-nba-3 vs spot: 0.237 ms / 0.135 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.034 ms
dpa/equivalence/ltl/gf-implies-3 vs spot: 0.011 ms / 0.020 ms
dpa/equivalence/ltl/gh-q-3 vs spot: 0.051 ms / 0.029 ms
dpa/equivalence/ltl/gh-r-3 vs spot: 0.021 ms / 0.069 ms
dpa/equivalence/ltl/go-theta-3 vs spot: 0.011 ms / 0.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.039 ms
dpa/equivalence/ltl/ms-phi-s-1 vs spot: 0.010 ms / 0.041 ms
dpa/equivalence/ltl/rv-counter-3 vs spot: 0.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.014 ms / 0.059 ms
dpa/equivalence/ltl/tv-uu-3 vs spot: 0.041 ms / 0.038 ms
dpa/equivalence/ltl/u-left-3 vs spot: 0.011 ms / 0.009 ms
dpa/equivalence/many_aps/and-gf-12 vs spot: 0.160 ms / 0.065 ms
dpa/equivalence/many_aps/gf-equiv-12 vs spot: 0.130 ms / 0.092 ms
dpa/equivalence/many_aps/r-right-10 vs spot: 0.065 ms / 0.025 ms
dpa/equivalence/many_aps/random-n16-a8-p4-s1 vs spot: 0.262 ms / 0.129 ms
dpa/equivalence/many_aps/random-n24-a12-p4-s1 vs spot: 1.342 ms / 0.461 ms
dpa/equivalence/many_aps/random-n32-a16-p4-s1 vs spot: 3.747 ms / 1.169 ms
dpa/equivalence/random/n128-a2-p6-s1 vs spot: 0.331 ms / 0.206 ms
dpa/equivalence/random/n16-a1-p3-s1 vs spot: 0.022 ms / 0.016 ms
dpa/equivalence/random/n256-a2-p8-s1 vs spot: 0.892 ms / 0.470 ms
dpa/equivalence/random/n64-a2-p4-s1 vs spot: 0.142 ms / 0.098 ms
dpa/inclusion/hard/l-dsa-3 vs spot: 0.071 ms / 0.061 ms
dpa/inclusion/hard/l-nba-2 vs spot: 0.035 ms / 0.023 ms
dpa/inclusion/hard/m-nba-3 vs spot: 0.148 ms / 0.082 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.012 ms / 0.019 ms
dpa/inclusion/ltl/gf-implies-3 vs spot: 0.006 ms / 0.011 ms
dpa/inclusion/ltl/gh-q-3 vs spot: 0.033 ms / 0.028 ms
dpa/inclusion/ltl/gh-r-3 vs spot: 0.012 ms / 0.035 ms
dpa/inclusion/ltl/go-theta-3 vs spot: 0.007 ms / 0.016 ms
dpa/inclusion/ltl/lily-patterns-1 vs spot: 0.008 ms / 0.014 ms
dpa/inclusion/ltl/ms-phi-r-1 vs spot: 0.006 ms / 0.019 ms
dpa/inclusion/ltl/ms-phi-s-1 vs spot: 0.006 ms / 0.025 ms
dpa/inclusion/ltl/rv-counter-3 vs spot: 0.018 ms / 0.014 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.029 ms
dpa/inclusion/ltl/tv-uu-3 vs spot: 0.028 ms / 0.029 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.123 ms / 0.052 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.047 ms / 0.023 ms
dpa/inclusion/many_aps/random-n16-a8-p4-s1 vs spot: 0.214 ms / 0.095 ms
dpa/inclusion/many_aps/random-n24-a12-p4-s1 vs spot: 1.013 ms / 0.377 ms
dpa/inclusion/many_aps/random-n32-a16-p4-s1 vs spot: 3.394 ms / 1.062 ms
dpa/inclusion/random/n128-a2-p6-s1 vs spot: 0.201 ms / 0.124 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.293 ms
dpa/inclusion/random/n64-a2-p4-s1 vs spot: 0.086 ms / 0.062 ms
game/solve/random_few_10000 vs spot: 6.740 ms / 20.428 ms
game/solve/random_few_10000 vs oink-zlk: 6.740 ms / 2.664 ms
game/solve/random_few_10000 vs oink-ppp: 6.740 ms / 1.393 ms
game/solve/random_few_50000 vs spot: 72.462 ms / 651.401 ms
game/solve/random_few_50000 vs oink-zlk: 72.462 ms / 18.399 ms
game/solve/random_few_50000 vs oink-ppp: 72.462 ms / 15.428 ms
game/solve/random_many_10000 vs spot: 6.479 ms / 29.964 ms
game/solve/random_many_10000 vs oink-zlk: 6.479 ms / 2.604 ms
game/solve/random_many_10000 vs oink-ppp: 6.479 ms / 1.542 ms
game/solve/random_many_50000 vs spot: 65.653 ms / 643.459 ms
game/solve/random_many_50000 vs oink-zlk: 65.653 ms / 37.026 ms
game/solve/random_many_50000 vs oink-ppp: 65.653 ms / 26.191 ms
game/solve/ladder_10000 vs spot: 2.532 ms / 9.542 ms
game/solve/ladder_10000 vs oink-zlk: 2.532 ms / 0.307 ms
game/solve/ladder_10000 vs oink-ppp: 2.532 ms / 0.303 ms
game/solve/ladder_50000 vs spot: 19.486 ms / 72.521 ms
game/solve/ladder_50000 vs oink-zlk: 19.486 ms / 2.116 ms
game/solve/ladder_50000 vs oink-ppp: 19.486 ms / 2.087 ms
== head: 266 benchmarks, 16 wall-clock measurements, 74 comparisons