Benchmarks for Weighted Tree Automata

Table of Contents

1 What fits in 16GB RAM

Finding the number of states that copar can solve in 16GB RAM for a few different types of WTAs.

1.1 Powerset

1.1.1 GHC 8.6.4 with symbols 0,8 and zero-freq 0.7

./bench.py bisect ../../copar/bin/{random-wta,copar} --monoid powerset --symbols 0,8 --zero-frequency 0.7 --good 1400 --bad 1600 --start-states 1500
Trying 1500...
Trying 1450...
Trying 1475...
Trying 1487...
Trying 1481...
Trying 1478...
Trying 1479...
First bad state count: 1479

  1. File Size
    ls -sh bench/wta_powerset_0,8_0.7_1478*
    
    82M bench/wta_powerset_0,8_0.7_1478_0.coalgebra
    82M bench/wta_powerset_0,8_0.7_1478_1.coalgebra
    82M bench/wta_powerset_0,8_0.7_1478_2.coalgebra
    82M bench/wta_powerset_0,8_0.7_1478_3.coalgebra
    82M bench/wta_powerset_0,8_0.7_1478_4.coalgebra
    
    

1.1.2 GHC 8.4.4 with symbols 0,8 and zero-freq 0.7

./bench.py bisect ../../copar/bin/{random-wta,copar} --monoid powerset --symbols 0,8 --zero-frequency 0.7 --start-states 1000
Trying 1000...
Trying 2000...
Trying 1500...
Trying 1250...
Trying 1375...
Trying 1437...
Trying 1468...
Trying 1484...
Trying 1476...
Trying 1480...
Trying 1478...
Trying 1479...
First bad state count: 1479

  1. File Size
    ls -sh bench/wta_powerset_0,8_0.7_1478*
    
    82M bench/wta_powerset_0,8_0.7_1478_0.coalgebra
    82M bench/wta_powerset_0,8_0.7_1478_1.coalgebra
    82M bench/wta_powerset_0,8_0.7_1478_2.coalgebra
    82M bench/wta_powerset_0,8_0.7_1478_3.coalgebra
    82M bench/wta_powerset_0,8_0.7_1478_4.coalgebra
    
    
  2. Automaton size
    python bench.py run ../../copar/bin/copar --monoid powerset --symbols 0,8 --zero-frequency 0.7 --states 1478 --indiv --header
    
    i states edges initial-partition-size final-partition-size explicit-final-partition-size size1-skipped overall-duration parse-duration algorithm-duration initialize-duration refine-duration
    0 5243856 10484756 10 18 2 0 115.339077581 34.439478263 79.458232767 27.712258503 37.668249537
    1 5245405 10487854 10 18 2 0 114.001430765 34.477874858 78.07613373 27.764347556 37.074617863
    2 5243549 10484142 10 18 2 0 114.862812706 34.668409012 78.756016051 27.741448159 37.09480403
    3 5241660 10480364 10 18 2 0 114.228588077 34.362576104 78.424601434 27.648526393 37.043127108
    4 5243032 10483108 10 18 2 0 114.692551901 34.827430372 78.414037199 27.723198479 38.276163878

1.1.3 GHC 8.4.4 with symbols 1,0,4 and zero-freq 0.7

./bench.py bisect ../../copar/bin/{random-wta,copar} --monoid powerset --symbols 1,0,4 --zero-frequency 0.7
Trying 50...
Trying 100...
Trying 200...
Trying 150...
Trying 175...
Trying 162...
Trying 156...
Trying 153...
Trying 151...
Trying 152...
First bad state count: 152

  1. File Size
    ls -sh bench/wta_powerset_1,0,4_0.7_152*
    
    83M bench/wta_powerset_1,0,4_0.7_152_0.coalgebra
    83M bench/wta_powerset_1,0,4_0.7_152_1.coalgebra
    83M bench/wta_powerset_1,0,4_0.7_152_2.coalgebra
    83M bench/wta_powerset_1,0,4_0.7_152_3.coalgebra
    83M bench/wta_powerset_1,0,4_0.7_152_4.coalgebra
    
    
  2. Automaton Size
    python bench.py run ../../copar/bin/copar --monoid powerset --symbols 1,0,4 --zero-frequency 0.7 --states 151 --indiv --header
    
    i states edges initial-partition-size final-partition-size explicit-final-partition-size size1-skipped overall-duration parse-duration algorithm-duration initialize-duration refine-duration
    0 4131380 12393591 7 69 4 0 92.530296805 32.925871573 58.292789973 13.413784138 32.25285307
    1 4131667 12394466 7 69 4 0 104.072447103 32.6810851 70.054731043 22.601698388 34.657530397
    2 4130798 12391837 7 69 4 0 104.65358267 32.641475967 70.686110886 22.881971907 34.580390995
    3 4131273 12393268 7 69 4 0 104.436764929 33.010643372 70.097279338 22.722527765 34.948100296
    4 4131755 12394730 7 69 4 0 103.940596569 32.874641172 69.748179673 22.561661198 34.530464508

1.1.4 GHC 8.4.4 with symbols 4,3,2 and zero-freq 0.7

./bench.py bisect ../../copar/bin/{random-wta,copar} --monoid powerset --symbols 4,3,2 --zero-frequency 0.7
Trying 50...
Trying 100...
Trying 200...
Trying 150...
Trying 175...
Trying 187...
Trying 193...
Trying 190...
Trying 191...
First bad state count: 191

  1. File Size
    ls -sh bench/wta_powerset_4,3,2_0.7_190*
    
    83M bench/wta_powerset_4,3,2_0.7_190_0.coalgebra
    83M bench/wta_powerset_4,3,2_0.7_190_1.coalgebra
    83M bench/wta_powerset_4,3,2_0.7_190_2.coalgebra
    83M bench/wta_powerset_4,3,2_0.7_190_3.coalgebra
    83M bench/wta_powerset_4,3,2_0.7_190_4.coalgebra
    
    
  2. Automaton Size
    python bench.py run ../../copar/bin/copar --monoid powerset --symbols 4,3,2 --zero-frequency 0.7 --states 190 --indiv --header
    
    i states edges initial-partition-size final-partition-size explicit-final-partition-size size1-skipped overall-duration parse-duration algorithm-duration initialize-duration refine-duration
    0 4150153 12416791 11 72964 190 7474719 141.894074912 32.94816078 104.894412823 19.27142335 73.292672481
    1 4149881 12415853 11 72964 190 7374059 143.936708293 32.959668876 106.847647981 19.335579933 74.389142529
    2 4147912 12410153 11 72964 190 7530637 143.039477927 32.922891848 106.049882108 19.238034371 73.786648681
    3 4149832 12415896 11 72964 190 7400820 141.899762867 32.763790399 105.08945468 19.081253852 73.103108932
    4 4147931 12410198 11 72964 190 7356721 142.277553489 33.004372363 105.135364747 19.217062907 72.82642293

1.1.5 GHC 8.4.4 with symbols 0,0,0,0,0,3 and zero-freq 0.7

./bench.py bisect ../../copar/bin/{random-wta,copar} --monoid powerset --symbols 0,0,0,0,0,3 --zero-frequency 0.7 --start-states 2
Trying 2...
Trying 4...
Trying 8...
Trying 16...
Trying 12...
Trying 10...
Trying 11...
First bad state count: 12

  1. File Size
    ls -sh bench/wta_powerset_0,0,0,0,0,3_0.7_11*
    
    47M bench/wta_powerset_0,0,0,0,0,3_0.7_11_0.coalgebra
    47M bench/wta_powerset_0,0,0,0,0,3_0.7_11_1.coalgebra
    47M bench/wta_powerset_0,0,0,0,0,3_0.7_11_2.coalgebra
    47M bench/wta_powerset_0,0,0,0,0,3_0.7_11_3.coalgebra
    47M bench/wta_powerset_0,0,0,0,0,3_0.7_11_4.coalgebra
    
    
  2. Automaton Size
    python bench.py run ../../copar/bin/copar --monoid powerset --symbols 0,0,0,0,0,3 --zero-frequency 0.7 --states 11 --indiv --header
    
    i states edges initial-partition-size final-partition-size explicit-final-partition-size size1-skipped overall-duration parse-duration algorithm-duration initialize-duration refine-duration
    0 1593503 9560952 5 98 2 0 44.433319213 19.470309466 24.352231629 11.34834025 10.606600771
    1 1594688 9568062 5 98 2 0 44.35660646 19.503070403 24.284648797 11.546398372 10.351405421
    2 1595746 9574410 5 98 2 0 44.979436845 19.622696684 24.756055326 11.448256352 10.958179969
    3 1594811 9568800 5 98 2 0 44.518512407 19.486959131 24.465812029 11.501689163 10.63837111
    4 1595187 9571056 5 98 2 0 44.449440224 19.537019031 24.300846734 11.389487771 10.5363747

1.2 Z,max

1.2.1 GHC 8.4.4 with symbols 0,8 and zero-freq 0.7

./bench.py bisect ../../copar/bin/{random-wta,copar} --monoid 'Z,max' --symbols 0,8 --zero-frequency 0.7
Trying 50...
Trying 100...
Trying 200...
Trying 400...
Trying 800...
Trying 1600...
Trying 1200...
Trying 1400...
Trying 1500...
Trying 1450...
Trying 1475...
Trying 1462...
Trying 1456...
Trying 1453...
Trying 1451...
First bad state count: 1451

1.2.2 File Size

ls -sh bench/wta_Z,max_0,8_0.7_1450*
182M bench/wta_Z,max_0,8_0.7_1450_0.coalgebra
182M bench/wta_Z,max_0,8_0.7_1450_1.coalgebra
182M bench/wta_Z,max_0,8_0.7_1450_2.coalgebra
182M bench/wta_Z,max_0,8_0.7_1450_3.coalgebra
182M bench/wta_Z,max_0,8_0.7_1450_4.coalgebra

1.2.3 Automaton Size

python bench.py run ../../copar/bin/copar --monoid 'Z,max' --symbols 0,8 --zero-frequency 0.7 --states 1450 --indiv --header
i states edges initial-partition-size final-partition-size explicit-final-partition-size size1-skipped overall-duration parse-duration algorithm-duration initialize-duration refine-duration
0 5047826 10092752 1458 13050 1450 9457197 127.724360284 43.258927035 81.171137974 26.874901612 40.422676395
1 5047514 10092128 1458 13050 1450 9456756 125.832804664 42.853972016 79.686342664 26.577174808 39.966384527
2 5049772 10096644 1458 13050 1450 9460968 126.336593045 42.68312591 80.349875424 26.745235991 40.031230363
3 5046916 10090932 1458 13050 1450 9455805 125.95962352 42.526542018 80.176310943 26.550162046 40.227319833
4 5049229 10095558 1458 13050 1450 9460347 126.718920083 42.559013501 80.863052096 26.756405734 40.145229524

1.2.4 GHC 8.4.4 with symbols 1,0,4 and zero-freq 0.7

./bench.py bisect ../../copar/bin/{random-wta,copar} --monoid 'Z,max' --symbols 1,0,4 --zero-frequency 0.7
Trying 50...
Trying 100...
Trying 200...
Trying 150...
Trying 175...
Trying 162...
Trying 156...
Trying 153...
Trying 151...
First bad state count: 151

ls -sh bench/wta_Z,max_1,0,4_0.7_150*
  1. File Size
    162M bench/wta_Z,max_1,0,4_0.7_150_0.coalgebra
    162M bench/wta_Z,max_1,0,4_0.7_150_1.coalgebra
    162M bench/wta_Z,max_1,0,4_0.7_150_2.coalgebra
    162M bench/wta_Z,max_1,0,4_0.7_150_3.coalgebra
    162M bench/wta_Z,max_1,0,4_0.7_150_4.coalgebra
    
    
  2. Automaton Size
    python bench.py run ../../copar/bin/copar --monoid 'Z,max' --symbols 1,0,4 --zero-frequency 0.7 --states 150 --indiv --header
    
    i states edges initial-partition-size final-partition-size explicit-final-partition-size size1-skipped overall-duration parse-duration algorithm-duration initialize-duration refine-duration
    0 4051480 12153896 155 90151 150 7087519 120.395749162 40.871788157 74.90886142 22.238988672 39.72932804
    1 4050707 12151583 155 90151 150 7087488 120.463605814 40.81720097 75.096220332 22.78192433 39.512466086
    2 4048842 12145992 155 90151 150 7083654 120.367574362 40.847872293 74.879748499 22.174812232 39.882652278
    3 4052208 12156090 155 90151 150 7090069 120.237306821 40.747046417 74.945644255 22.185753095 39.520022235
    4 4048823 12145929 155 90151 150 7084229 121.046334089 41.206127141 75.236966807 22.108849249 39.746848148

1.2.5 GHC 8.4.4 with symbols 4,3,2 and zero-freq 0.7

./bench.py bisect ../../copar/bin/{random-wta,copar} --monoid 'Z,max' --symbols 4,3,2 --zero-frequency 0.7 --start-states 100
Trying 100...
Trying 200...
Trying 150...
Trying 175...
Trying 187...
Trying 193...
Trying 190...
Trying 188...
Trying 189...
First bad state count: 189

  1. File Size
    ls -sh bench/wta_Z,max_4,3,2_0.7_188*
    
    162M bench/wta_Z,max_4,3,2_0.7_188_0.coalgebra
    162M bench/wta_Z,max_4,3,2_0.7_188_1.coalgebra
    162M bench/wta_Z,max_4,3,2_0.7_188_2.coalgebra
    162M bench/wta_Z,max_4,3,2_0.7_188_3.coalgebra
    162M bench/wta_Z,max_4,3,2_0.7_188_4.coalgebra
    
    
  2. Automaton Size
    python bench.py run ../../copar/bin/copar --monoid 'Z,max' --symbols 4,3,2 --zero-frequency 0.7 --states 188 --indiv --header
    
    i states edges initial-partition-size final-partition-size explicit-final-partition-size size1-skipped overall-duration parse-duration algorithm-duration initialize-duration refine-duration
    0 4020872 12029832 197 71444 188 6045852 115.942447016 40.75075879 71.271681594 18.625916768 39.91853539
    1 4017121 12018620 197 71444 188 6040501 113.960683621 40.210261362 69.908854506 18.715510494 39.429755908
    2 4017092 12018743 197 71444 188 6040038 114.417975118 40.056454421 70.449543532 18.443439893 39.714702929
    3 4013171 12006729 197 71444 188 6034912 104.421419394 40.426583126 60.116296609 10.279226244 37.258447268
    4 4018149 12021895 197 71444 188 6042204 104.595285757 40.484957759 60.29935373 10.313693438 37.315322541

1.2.6 GHC 8.4.4 with symbols 0,0,0,0,0,3 and zero-freq 0.7

./bench.py bisect ../../copar/bin/{random-wta,copar} --monoid 'Z,max' --symbols 0,0,0,0,0,3 --zero-frequency 0.7 --start-states 6
Trying 6...
Trying 12...
Trying 9...
Trying 10...
Trying 11...
First bad state count: 12

  1. File Size
    ls -sh bench/wta_Z,max_0,0,0,0,0,3_0.7_11*
    
    79M bench/wta_Z,max_0,0,0,0,0,3_0.7_11_0.coalgebra
    79M bench/wta_Z,max_0,0,0,0,0,3_0.7_11_1.coalgebra
    79M bench/wta_Z,max_0,0,0,0,0,3_0.7_11_2.coalgebra
    79M bench/wta_Z,max_0,0,0,0,0,3_0.7_11_3.coalgebra
    79M bench/wta_Z,max_0,0,0,0,0,3_0.7_11_4.coalgebra
    
    
  2. Automaton Size
    python bench.py run ../../copar/bin/copar --monoid 'Z,max' --symbols 0,0,0,0,0,3 --zero-frequency 0.7 --states 11 --indiv --header
    
    i states edges initial-partition-size final-partition-size explicit-final-partition-size size1-skipped overall-duration parse-duration algorithm-duration initialize-duration refine-duration
    0 1595450 9572634 14 473731 11 2679440 59.567674089 22.815217966 34.656233896 10.712862563 21.527223791
    1 1596274 9577578 14 473599 11 2680789 59.667949978 22.964709813 34.595654672 10.671440318 21.504327033
    2 1593533 9561132 14 473725 11 2676188 59.60896951 22.965296594 34.468009878 10.694780509 21.357284246
    3 1593597 9561516 14 473516 11 2675256 59.618517937 22.900218752 34.517770264 10.699678956 21.404437124
    4 1595682 9574026 14 473759 11 2679419 59.829033166 22.84743033 34.719394797 10.690592405 21.632768706

1.3 Word,or

1.3.1 GHC 8.4.4 with symbols 0,8 and zero-freq 0.7

./bench.py bisect ../../copar/bin/{random-wta,copar} --monoid 'Word,or' --symbols 0,8 --zero-frequency 0.7 --start-states 1000
Trying 1000...
Trying 2000...
Trying 1500...
Trying 1250...
Trying 1375...
Trying 1437...
Trying 1406...
Trying 1421...
Trying 1413...
Trying 1409...
Trying 1407...
Trying 1408...
First bad state count: 1409

  1. File Size
    ls -sh bench/wta_Word,or_0,8_0.7_1408*
    
    164M bench/wta_Word,or_0,8_0.7_1408_0.coalgebra
    164M bench/wta_Word,or_0,8_0.7_1408_1.coalgebra
    165M bench/wta_Word,or_0,8_0.7_1408_2.coalgebra
    165M bench/wta_Word,or_0,8_0.7_1408_3.coalgebra
    165M bench/wta_Word,or_0,8_0.7_1408_4.coalgebra
    
    
  2. Automaton Size
    python bench.py run ../../copar/bin/copar --monoid 'Word,or' --symbols 0,8 --zero-frequency 0.7 --states 1408 --indiv --header
    
    i states edges initial-partition-size final-partition-size explicit-final-partition-size size1-skipped overall-duration parse-duration algorithm-duration initialize-duration refine-duration
    0 4757493 9512170 1416 12672 1408 8913294 122.529064018 49.673619826 69.872621378 24.487186873 37.636595831
    1 4757305 9511794 1416 12672 1408 8912679 121.871882143 49.468009438 69.396700752 24.548033181 37.526833514
    2 4760364 9517912 1416 12672 1408 8918643 122.195401637 49.367139075 69.859922188 24.551202679 37.745627532
    3 4760232 9517648 1416 12672 1408 8918564 121.744240716 49.628682967 69.111452032 24.573090085 37.819264634
    4 4759753 9516690 1416 12672 1408 8917624 118.671354206 49.213411686 66.440058464 25.139216435 33.058420248

1.3.2 GHC 8.4.4 with symbols 1,0,4 and zero-freq 0.7

./bench.py bisect ../../copar/bin/{random-wta,copar} --monoid 'Word,or' --symbols 1,0,4 --zero-frequency 0.7 --start-states 120
Trying 120...
Trying 240...
Trying 180...
Trying 150...
Trying 135...
Trying 142...
Trying 146...
Trying 148...
Trying 149...
First bad state count: 149

  1. File Size
    ls -sh bench/wta_Word,or_1,0,4_0.7_148*
    
    151M bench/wta_Word,or_1,0,4_0.7_148_0.coalgebra
    151M bench/wta_Word,or_1,0,4_0.7_148_1.coalgebra
    151M bench/wta_Word,or_1,0,4_0.7_148_2.coalgebra
    151M bench/wta_Word,or_1,0,4_0.7_148_3.coalgebra
    151M bench/wta_Word,or_1,0,4_0.7_148_4.coalgebra
    
    
  2. Automaton Size
    python bench.py run ../../copar/bin/copar --monoid 'Word,or' --symbols 1,0,4 --zero-frequency 0.7 --states 148 --indiv --header
    
    i states edges initial-partition-size final-partition-size explicit-final-partition-size size1-skipped overall-duration parse-duration algorithm-duration initialize-duration refine-duration
    0 3889583 11668189 153 87765 148 6805177 117.573809962 44.159477335 69.176479615 20.97881901 36.97313268
    1 3891836 11675004 153 87765 148 6809318 118.060187599 44.059742822 69.709799716 20.986764025 37.089169403
    2 3889498 11667962 153 87765 148 6805428 117.680086041 43.801892931 69.639925802 20.888711457 36.894495934
    3 3890675 11671481 153 87765 148 6807190 118.213230214 44.026034118 69.934017821 20.807216331 36.920223682
    4 3889335 11667465 153 87765 148 6804884 118.020940476 44.097067581 69.813347698 20.923033139 36.907214948

1.3.3 GHC 8.4.4 with symbols 1,0,4 and zero-freq 0.7

./bench.py bisect ../../copar/bin/{random-wta,copar} --monoid 'Word,or' --symbols 4,3,2 --zero-frequency 0.7
Trying 50...
Trying 100...
Trying 200...
Trying 150...
Trying 175...
Trying 187...
Trying 181...
Trying 184...
Trying 185...
Trying 186...
First bad state count: 187

  1. File Size
    ls -sh bench/wta_Word,or_4,3,2_0.7_186*
    
    152M bench/wta_Word,or_4,3,2_0.7_186_0.coalgebra
    152M bench/wta_Word,or_4,3,2_0.7_186_1.coalgebra
    152M bench/wta_Word,or_4,3,2_0.7_186_2.coalgebra
    152M bench/wta_Word,or_4,3,2_0.7_186_3.coalgebra
    152M bench/wta_Word,or_4,3,2_0.7_186_4.coalgebra
    
    
  2. Automaton Size
    python bench.py run ../../copar/bin/copar --monoid 'Word,or' --symbols 4,3,2 --zero-frequency 0.7 --states 186 --indiv --header
    
    i states edges initial-partition-size final-partition-size explicit-final-partition-size size1-skipped overall-duration parse-duration algorithm-duration initialize-duration refine-duration
    0 3890269 11638838 195 69940 186 5848699 114.733470175 43.499787726 67.5948969 17.660572753 37.835620352
    1 3893818 11649123 195 69940 186 5854005 114.756947419 43.702682275 67.505722972 17.675712966 37.818639736
    2 3893265 11647592 195 69940 186 5854134 115.418354168 43.606980048 68.133828807 17.837028275 37.992011256
    3 3892206 11644421 195 69940 186 5852423 113.998060941 43.769845642 66.618120946 17.720427448 37.714434677
    4 3892036 11643814 195 69940 186 5851296 115.965290499 44.138476758 68.234040288 17.763408679 38.356640369

1.3.4 GHC 8.4.4 with symbols 0,0,0,0,0,3 and zero-freq 0.7

./bench.py bisect ../../copar/bin/{random-wta,copar} --monoid 'Word,or' --symbols 0,0,0,0,0,3 --zero-frequency 0.7 --start-states 6                                                                            
Trying 6...                          
Trying 12...
Trying 9...
Trying 10...
Trying 11...
First bad state count: 12

  1. File Size
    ls -sh bench/wta_Word,or_0,0,0,0,0,3_0.7_11*
    
    77M bench/wta_Word,or_0,0,0,0,0,3_0.7_11_0.coalgebra
    77M bench/wta_Word,or_0,0,0,0,0,3_0.7_11_1.coalgebra
    77M bench/wta_Word,or_0,0,0,0,0,3_0.7_11_2.coalgebra
    77M bench/wta_Word,or_0,0,0,0,0,3_0.7_11_3.coalgebra
    77M bench/wta_Word,or_0,0,0,0,0,3_0.7_11_4.coalgebra
    
    
  2. Automaton Size
    python bench.py run ../../copar/bin/copar --monoid 'Word,or' --symbols 0,0,0,0,0,3 --zero-frequency 0.7 --states 11 --indiv --header
    
    i states edges initial-partition-size final-partition-size explicit-final-partition-size size1-skipped overall-duration parse-duration algorithm-duration initialize-duration refine-duration
    0 1594413 9566412 14 473587 11 2676959 61.53939505 24.79942316 34.477272309 10.822832613 21.313535924
    1 1596360 9578094 14 473404 11 2681034 61.147599248 24.824030133 34.101896988 10.793184 20.989457877
    2 1595591 9573480 14 473700 11 2679546 61.459443653 24.801616514 34.389540062 10.893824596 21.133849133
    3 1593825 9562884 14 473580 11 2676789 61.147557505 24.98879381 33.942496577 10.818043846 20.839884809
    4 1596528 9579102 14 473600 11 2681048 61.864094058 24.884111862 34.762990208 10.893522867 21.485077775

Author: Hans-Peter Deifel

Created: 2019-03-27 Mi 10:50

Validate