Post a Comment On: cbloom rants

Wrapping up the series with lots of numbers. Previous parts : cbloom rants 12-17-11 - LZ Optimal Parse with A Star Part 4
cbloom rants 12-17-11 - LZ Optimal Parse with A Star Part 3
cbloom rants 12-17-11 - LZ Optimal Parse with A Star Part 2
cbloom rants 10-24-11 - LZ Optimal Parse with A Star Part 1
I'm delirious with fever right now so I might write something inane, but I'm so bored of lying in bed so I'm trying to wrap this up. Anyhoo.. So first of all we have to talk a bit about what we're comparing the A Star parse to. "Normal" is a complex forward lazy parse using heuristics to guide parsing, as described in Part 1. "Fast" is like Normal but uses simpler heuristics and simpler match finder. "Chain" is more interesting. Chain is a complex "lazy"-type parser which considers N decisions ahead (eg. Chain 4 considers 4 decisions ahead). It works thusly : Chain Parse : first do a full parse of the file using some other parser; this provides with a baseline cost to end from each point. Now do a forward parse. At each position, consider all match and literal options. For each option, step ahead by that option and consider all the options at the next position. Add up the cost of each coding step. After N steps (for chain N) add on the cost to end from the first baseline parse. Go back to the original position and finalize the choice with the lowest cost. Basically it's a full graph walk for N steps, then use an estimate of the cost to the end from the final nodes of that sub-graph. To make Chain parsing viable you have to reduce the number of match options to a maximum of 8 or so. Still Chain N has a complexity of 8^N , so it becomes slow very quickly as N grows. Chain forward parse is significantly better than LZSS style backwards optimal parse for these LZ coders that have important adaptive state. The baseline parse I use for Chain actually is a backwards LZSS optimal parse, so you can see how it does by looking at the "Chain 0" results. First overall results. Chain 6 is the most amount of steps I can run in reasonable time, and AStar 2048 means the quantum length for dividing up the file for AStar was 2048. raw Fast Normal Chain 6 AStar 2048 lzt00 16914 5179 5016 4923 4920 lzt01 200000 198313 198321 198312 198312 lzt02 755121 181109 177792 173220 173315 lzt03 3471552 1746443 1713023 1698949 1690655 lzt04 48649 13088 12412 10407 10249 lzt05 927796 368346 367598 355804 354230 lzt06 563160 352827 351051 344721 343173 lzt07 500000 226533 215996 209133 208566 lzt08 355400 250503 249987 230541 230220 lzt09 786488 302927 287479 268544 265525 lzt10 154624 11508 10958 10307 10291 lzt11 58524 20553 19628 19139 19087 lzt12 164423 29001 26488 23966 23622 lzt13 1041576 935484 931415 924510 922745 lzt14 102400 47690 47298 46417 46350 lzt15 34664 10832 10688 10269 10260 lzt16 21504 10110 10055 9952 9927 lzt17 53161 19526 18514 17971 17970 lzt18 102400 64280 63251 59772 59635 lzt19 768771 322951 288872 269132 269162 lzt20 1179702 888881 872315 856369 855588 lzt21 679936 91677 88011 83529 83184 lzt22 400000 287715 284378 279674 279459 lzt23 1048576 807253 804048 798369 798334 lzt24 3471552 1418076 1411387 1399197 1388105 lzt25 1029744 113085 107882 97320 100175 lzt26 262144 212445 210836 207701 207552 lzt27 857241 237253 235137 222023 220837 lzt28 1591760 332660 308940 260547 252808 lzt29 3953035 1193914 1180823 1147160 1135603 lzt30 100000 100001 100001 100001 100001 10800163 10609600 10337879 10289860 Now number of Chain steps for the chain parser : (that's O0 - O6) U N O0 O1 O2 O3 O4 O5 O6 lzt00 16914 5016 5024 4922 4922 4922 4922 4923 4923 lzt01 200000 198321 198321 198312 198312 198312 198312 198312 198312 lzt02 755121 177792 177877 175905 174835 174073 173759 173509 173220 lzt03 3471552 1713023 1712337 1704417 1703873 1702651 1701635 1700282 1698949 lzt04 48649 12412 11315 10516 10481 10457 10427 10416 10407 lzt05 927796 367598 368729 365743 364332 360630 356403 355968 355804 lzt06 563160 351051 350995 346856 345500 344778 344739 344702 344721 lzt07 500000 215996 215644 211336 209481 209259 209244 209138 209133 lzt08 355400 249987 249372 239375 237320 231554 231435 233324 230541 lzt09 786488 287479 284875 280683 275679 270721 269754 269107 268544 lzt10 154624 10958 10792 10367 10335 10330 10311 10301 10307 lzt11 58524 19628 19604 19247 19175 19225 19162 19159 19139 lzt12 164423 26488 25644 24217 24177 24094 24108 24011 23966 lzt13 1041576 931415 931415 929713 927841 926162 924515 924513 924510 lzt14 102400 47298 47300 46518 46483 46461 46437 46429 46417 lzt15 34664 10688 10656 10317 10301 10275 10278 10267 10269 lzt16 21504 10055 10053 9960 9966 9959 9952 9948 9952 lzt17 53161 18514 18549 17971 17970 17974 17971 17973 17971 lzt18 102400 63251 63248 59863 59850 59799 59790 59764 59772 lzt19 768771 288872 281959 277661 273316 269157 269141 269133 269132 lzt20 1179702 872315 872022 868088 865376 863236 859727 856408 856369 lzt21 679936 88011 88068 84848 83851 83733 83674 83599 83529 lzt22 400000 284378 284297 281902 279711 279685 279689 279696 279674 lzt23 1048576 804048 804064 802742 801324 799891 798367 798368 798369 lzt24 3471552 1411387 1410226 1404736 1403314 1402345 1401064 1400193 1399197 lzt25 1029744 107882 107414 99839 100154 99710 98552 98132 97320 lzt26 262144 210836 210855 207775 207763 207738 207725 207706 207701 lzt27 857241 235137 236568 233524 228073 223123 222884 222540 222023 lzt28 1591760 308940 295072 286018 276905 273520 269611 264726 260547 lzt29 3953035 1180823 1183407 1180733 1177854 1170944 1162310 1152482 1147160 lzt30 100000 100001 100001 100001 100001 100001 100001 100001 100001 10609600 10585703 10494105 10448475 10404719 10375899 10355030 10337879 Some notes : up to 6 (the most I can run) more chain steps is better - for the sum, but not for all files. In some cases, more steps is worse, which should never really happen, but it's an issue of approximate optimal parsers I'll discuss later. (*) On most files, going past 4 chain steps helps very little, but on some files it seems to monotonically keep improving. For example lzt29 stands out. Those files are ones that get helped the most by AStar. Now the effect on quantum size on AStar. In all cases I only output codes from the first 3/4 of each quantum. raw 256 512 1024 2048 4096 8192 16384 lzt00 16914 4923 4923 4920 4920 4920 4921 4921 lzt01 200000 198312 198312 198312 198312 198312 198314 198314 lzt02 755121 175242 173355 173368 173315 173331 173454 173479 lzt03 3471552 1699795 1691530 1690878 1690655 1690594 1690603 1690617 lzt04 48649 10243 10245 10234 10249 10248 10241 10241 lzt05 927796 357166 354629 354235 354230 354233 354242 354257 lzt06 563160 346663 343202 343139 343173 343194 343263 343238 lzt07 500000 209934 208669 208584 208566 208556 208553 208562 lzt08 355400 228389 229447 229975 230220 230300 230374 230408 lzt09 786488 266571 265564 265487 265525 265559 265542 265527 lzt10 154624 10701 10468 10330 10291 10273 10273 10272 lzt11 58524 19139 19123 19096 19087 19085 19084 19084 lzt12 164423 23712 23654 23616 23622 23628 23630 23627 lzt13 1041576 923258 922853 922747 922745 922753 922751 922753 lzt14 102400 46397 46364 46351 46350 46350 46348 46350 lzt15 34664 10376 10272 10260 10260 10251 10258 10254 lzt16 21504 9944 9931 9926 9927 9927 9927 9927 lzt17 53161 17937 17970 17968 17970 17969 17969 17969 lzt18 102400 59703 59613 59632 59635 59637 59640 59640 lzt19 768771 269213 269151 269128 269162 269193 269218 269229 lzt20 1179702 855992 855580 855478 855588 855671 855685 855707 lzt21 679936 83882 83291 83215 83184 83172 83171 83169 lzt22 400000 279803 279368 279414 279459 279605 279630 279647 lzt23 1048576 798325 798319 798321 798334 798354 798357 798358 lzt24 3471552 1393742 1388636 1388031 1388105 1388317 1388628 1388671 lzt25 1029744 97910 101246 101302 100175 100484 100272 100149 lzt26 262144 207779 207563 207541 207552 207559 207577 207576 lzt27 857241 222229 220832 220770 220837 220773 220756 220757 lzt28 1591760 256404 253257 252933 252808 252737 252735 252699 lzt29 3953035 1136193 1135442 1135543 1135603 1135710 1135689 1135713 lzt30 100000 100001 100001 100001 100001 100001 100001 100001 10319878 10292810 10290735 10289860 10290696 10291106 10291116 The best sum is at 2048, but 1024 is a lot faster and almost the same. Again, as the previous note at (*), we should really see just improvement with larger quantum sizes, but past 2048 we start seeing it go backwards in some cases. Lastly a look at where the AStar parse is spending its time. This is for a 1024 quantum. The x axis here is the log2 of the number of nodes visited to parse a quantum. So, log2=20 means a million nodes were needed to parse that quantum. So for speed purposes a cell one to the right is twice as bad. The values in the cells are the percentage of quanta in the file that needed that number of nodes. (note : log2=20 means one million nodes were visited to output 768 bytes worth of codes, so it's quite a lot) log2 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 lzt00 0 0 0 18.18 59.09 18.18 4.55 lzt01 3.75 0.75 41.2 34.08 13.86 5.62 0.75 lzt02 1.81 1.36 25.37 34.09 13.59 13.02 8.15 1.93 0.23 0.23 lzt03 1.46 1.18 17.51 18.46 14.16 13.17 6.95 4.81 3.66 4.81 9.54 2.79 0.96 0.11 0.03 lzt04 1.67 0 0 1.67 0 21.67 5 18.33 3.33 10 16.67 16.67 5 lzt05 0.59 0.25 4.41 10.77 9.92 18.32 13.23 10.09 9.67 6.02 12.47 3.22 0.51 0.08 0.08 lzt06 0.8 0.93 6.81 23.77 14.69 16.96 21.09 11.48 2.67 0.8 lzt07 0.46 0.46 8.66 7.88 6.8 15.3 17 14.53 5.56 9.58 8.19 4.79 0.31 0.31 lzt08 0 0 0 0 0 0 1.68 1.68 1.47 27.67 53.88 11.95 1.68 lzt09 0.29 0.48 0.76 0.86 0.95 3.9 28.07 47.76 16.18 0.38 lzt10 0 0.56 10.17 12.99 9.04 9.04 10.17 41.24 4.52 0.56 1.13 lzt11 0 0 7.89 10.53 14.47 17.11 6.58 9.21 21.05 10.53 2.63 lzt12 0 0 0 0 0 4.27 28.91 59.24 7.58 lzt13 0 0 0.07 0.14 0.57 1.72 3.36 5.72 39.24 42.03 7.08 0.07 lzt14 0 0.83 0 2.5 8.33 34.17 42.5 5 2.5 1.67 0.83 0 0.83 lzt15 0 2.27 4.55 15.91 13.64 15.91 13.64 6.82 11.36 11.36 4.55 lzt16 0 0 3.57 0 14.29 42.86 32.14 3.57 lzt17 1.39 1.39 2.78 1.39 4.17 75 13.89 lzt18 0 0 0 0 0 0.72 0 2.17 2.9 11.59 56.52 23.19 2.9 lzt19 0 0 1.26 2.81 0.39 7.56 87.11 0.87 lzt20 0 0.13 2.08 2.02 4.29 67.07 24.29 0.06 lzt21 0.2 0.78 6.07 6.07 5.28 19.77 35.62 22.9 1.96 0.2 0.2 lzt22 0 0.56 2.98 5.59 26.82 62.94 1.12 lzt23 0 0 0 0 0 0.07 1.35 2.63 0.92 70.88 23.15 0.14 0.36 0.5 lzt24 0.44 0.61 4.14 37.41 7.62 12.68 12.72 8.52 6.11 5.19 3.11 0.94 0.31 0.04 lzt25 0.22 0.43 1.52 1.74 2.68 6.44 15.69 27.19 30.22 13.09 0.72 lzt26 0 0 0 1.15 3.15 2.58 77.65 14.61 0.57 lzt27 0.61 0.1 7.55 6.53 1.22 4.39 5 4.08 7.76 44.8 16.43 1.43 lzt28 0.25 0.1 3.71 0.94 0.74 6.77 15.56 10.08 10.97 14.82 18.68 11.41 4.05 1.24 0.1 lzt29 0.3 0.73 1.61 22.37 5.28 6.16 26.34 2.97 0.48 0.85 19.63 12.47 0.73 lzt30 3.7 0.74 47.41 34.07 12.59 0.74 Well there's no easy answer, the character of the files are all very different. In many cases the A Star parse is reasonably fast (comparable to Chain 3 or something). But in some cases it's quite slow, eg. lzt04, lzt08, lzt28. Okay, I think that's all the data. We have one point to discuss : (*) = in all these type of endeavors, we see these anomolies where as we give the optimizer more space to make decisions, it gets better for a while, then starts getting worse. I saw the same thing, but more extreme, with video coding. Basically what causes this is that you aren't optimizing for your real final goal. If you were optimizing for the total output size, then giving it more freedom should never hurt. But you aren't. With Chain N or with A Star in both cases you are optimizing just some local portion, and it turns out that if you let it make really aggressive decisions trying to optimize the local bit, that can hurt overall. A similar issue happens with an Huffman optimal parse, becuase you are using the huffman code lengths from the previous parse to do the current parse. That's fine as long as your parse is reasonably similar, but if you let the optimal parser really go nuts, it can start to get pretty far off those statistics, which makes it wrong, so that more optimizing actually gives worse results. With video coding the main issue I had was that the optimization was generally local (eg. just on one macro block at a time or some such), but it of course affects the future as a source for motion compensation (and in other ways), and it turns out if you do really aggressive optimization on the local decisions, that can wind up hurting overall. A similar thing can happen in image and video coding if you let optimization proceed very aggressively, because you have to use some simple analytic criterion (such as RMSE - though even if you use a fancier metric the same problems arise). The issue is that the coder can wind up finding strange states that are a good trade-off for RMSE, but wind up looking just horrible visually. Obviously the correct solution is to optimize with the true final goal in mind. But that's not always possible, either computationally, or because the final goal is subjective. Generally the solution is to moderate the optimization in some way. You have some heuristic idea of what kind of solutions will provide good globally optimal solutions. (for example, in image/video coding, you might require that the bit rate allocation not create too big of a difference between adjacent blocks). So you sort of want to guide your optimization to start around where you suspect the answer to be, and then you tune it so that you don't allow it to be too aggressive in making whatever decision it thinks is locally optimal.