for alg in random lru fifo fifo2 car arc linux worst opt ;do echo $alg for s in 5 15 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 ;do printf "% 7.7d " $s; ~/projects/fslog/replacement -M$s -V2356223 \ -f 86839 -a $alg < fslog.trace done echo done Memory size Hits Misses Hit ratio (frames) random 0000005 4098312 19719823 17.206687 0000015 4580262 19237873 19.230145 0000032 5056031 18762104 21.227653 0000064 6034649 17783486 25.336362 0000128 7987212 15830923 33.534162 0000256 10663398 13154737 44.770080 0000512 13533498 10284637 56.820141 0001024 16862969 6955166 70.798864 0002048 19689851 4128284 82.667476 0004096 21049868 2768267 88.377482 0008192 21623202 2194933 90.784614 0016384 21900574 1917561 91.949156 0032768 22061236 1756899 92.623692 0065536 22193047 1625088 93.177098 0131072 22392670 1425465 94.015212 0262144 22701842 1116293 95.313264 0524288 22977381 840754 96.470110 1048576 23163434 654701 97.251250 2097152 23320548 497587 97.910890 4194304 23332195 485940 97.959790 lru 0000005 4454278 19363857 18.701204 0000015 4724158 19093977 19.834290 0000032 5113705 18704430 21.469796 0000064 5686223 18131912 23.873502 0000128 7884539 15933596 33.103091 0000256 11085532 12732603 46.542401 0000512 13998840 9819295 58.773871 0001024 17646467 6171668 74.088366 0002048 20964704 2853431 88.019923 0004096 21852423 1965712 91.746994 0008192 22050118 1768017 92.577013 0016384 22127292 1690843 92.901027 0032768 22169773 1648362 93.079383 0065536 22237414 1580721 93.363372 0131072 22344944 1473191 93.814835 0262144 22688962 1129173 95.259188 0524288 23191338 626797 97.368404 1048576 23279806 538329 97.739836 2097152 23331989 486146 97.958925 4194304 23332195 485940 97.959790 fifo 0000005 4368267 19449868 18.340088 0000015 4735021 19083114 19.879898 0000032 5137235 18680900 21.568586 0000064 6246911 17571224 26.227540 0000128 8253798 15564337 34.653418 0000256 10933497 12884638 45.904085 0000512 13500692 10317443 56.682406 0001024 16853481 6964654 70.759029 0002048 19949649 3868486 83.758233 0004096 21231481 2586654 89.139981 0008192 21721069 2097066 91.195507 0016384 21964127 1854008 92.215982 0032768 22081886 1736249 92.710391 0065536 22191802 1626333 93.171871 0131072 22321377 1496758 93.715889 0262144 22856458 961677 95.962417 0524288 23104404 713731 97.003414 1048576 23228539 589596 97.524592 2097152 23325186 492949 97.930363 4194304 23332195 485940 97.959790 fifo2 0000005 4396443 19421692 18.458385 0000015 4730761 19087374 19.862013 0000032 5120717 18697418 21.499236 0000064 5836762 17981373 24.505537 0000128 8078973 15739162 33.919419 0000256 11049157 12768978 46.389682 0000512 13754134 10064001 57.746478 0001024 17368718 6449417 72.922242 0002048 20762609 3055526 87.171431 0004096 21783348 2034787 91.456984 0008192 22032872 1785263 92.504606 0016384 22120816 1697319 92.873838 0032768 22165862 1652273 93.062962 0065536 22234479 1583656 93.351050 0131072 22342686 1475449 93.805355 0262144 22622156 1195979 94.978704 0524288 23189711 628424 97.361573 1048576 23275966 542169 97.723713 2097152 23326015 492120 97.933843 4194304 23332195 485940 97.959790 car 0000005 4290627 19527508 18.014118 0000015 4921775 18896360 20.663981 0000032 5497884 18320251 23.082764 0000064 6876491 16941644 28.870820 0000128 9140830 14677305 38.377606 0000256 12296205 11521930 51.625390 0000512 14441378 9376757 60.631859 0001024 17785194 6032941 74.670809 0002048 20624612 3193523 86.592053 0004096 21544527 2273608 90.454299 0008192 21809873 2008262 91.568349 0016384 21952614 1865521 92.167645 0032768 22037448 1780687 92.523819 0065536 22184952 1633183 93.143111 0131072 22469990 1348145 94.339838 0262144 22850968 967167 95.939367 0524288 22852446 965689 95.945573 1048576 22969923 848212 96.438798 2097152 23331702 486433 97.957720 4194304 23332195 485940 97.959790 arc 0000005 4296752 19521383 18.039834 0000015 4968151 18849984 20.858690 0000032 5600186 18217949 23.512278 0000064 6867332 16950803 28.832367 0000128 9098799 14719336 38.201140 0000256 12264090 11554045 51.490555 0000512 14437304 9380831 60.614754 0001024 17892878 5925257 75.122918 0002048 20776183 3041952 87.228421 0004096 21650944 2167191 90.901089 0008192 21902209 1915926 91.956020 0016384 22006210 1811925 92.392666 0032768 22087958 1730177 92.735884 0065536 22235273 1582862 93.354383 0131072 22536204 1281931 94.617836 0262144 22920075 898060 96.229512 0524288 22875921 942214 96.044132 1048576 22988035 830100 96.514840 2097152 23331702 486433 97.957720 4194304 23332195 485940 97.959790 linux 0000005 0 0 0.0 0000015 0 0 0.0 0000032 0 0 0.0 0000064 5080840 18737295 21.331813 0000128 6491162 17326973 27.253024 0000256 9683353 14134782 40.655379 0000512 13336960 10481175 55.994980 0001024 16048253 7769882 67.378294 0002048 20016278 3801857 84.037974 0004096 21564884 2253251 90.539767 0008192 21969898 1848237 92.240211 0016384 22103790 1714345 92.802354 0032768 22167291 1650844 93.068962 0065536 22228438 1589697 93.325686 0131072 22352932 1465203 93.848372 0262144 22628090 1190045 95.003618 0524288 23129590 688545 97.109157 1048576 23219534 598601 97.486785 2097152 23331965 486170 97.958824 4194304 23332195 485940 97.959790 worst 0000005 2951581 20866554 12.392158 0000015 2988565 20829570 12.547435 0000032 3073973 20744162 12.906019 0000064 3267323 20550812 13.717795 0000128 3543371 20274764 14.876778 0000256 3945290 19872845 16.564227 0000512 4757904 19060231 19.975972 0001024 6378330 17439805 26.779301 0002048 9102740 14715395 38.217686 0004096 11876030 11942105 49.861293 0008192 13975287 9842848 58.674984 0016384 15452412 8365723 64.876666 0032768 16504572 7313563 69.294141 0065536 17263002 6555133 72.478395 0131072 17849524 5968611 74.940897 0262144 18415079 5403056 77.315369 0524288 19183395 4634740 80.541130 1048576 20417092 3401043 85.720784 2097152 22953013 865122 96.367801 4194304 23332195 485940 97.959790 opt 0000005 5104348 18713787 21.430511 0000015 6396193 17421942 26.854298 0000032 7947630 15870505 33.367978 0000064 10138239 13679896 42.565209 0000128 13149754 10668381 55.208999 0000256 15587044 8231091 65.441916 0000512 18101323 5716812 75.998070 0001024 20756212 3061923 87.144573 0002048 22037304 1780831 92.523214 0004096 22198777 1619358 93.201155 0008192 22292317 1525818 93.593881 0016384 22408567 1409568 94.081955 0032768 22592906 1225229 94.855899 0065536 22803451 1014684 95.739868 0131072 23086507 731628 96.928273 0262144 23332195 485940 97.959790 0524288 23332195 485940 97.959790 1048576 23332195 485940 97.959790 2097152 23332195 485940 97.959790 4194304 23332195 485940 97.959790 for t in 0 1 2 3 4 5 6 7 8 9 10 11 15 20 ;do echo sfifo:$t for s in 5 15 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 ;do printf "% 7.7d " $s; ~/projects/fslog/replacement -M$s -V2356223 \ -f 86839 -a sfifo -t $t < fslog.trace done echo done sfifo:0 0000005 4368267 19449868 18.340088 0000015 4735021 19083114 19.879898 0000032 5137235 18680900 21.568586 0000064 6246911 17571224 26.227540 0000128 8253798 15564337 34.653418 0000256 10933497 12884638 45.904085 0000512 13500692 10317443 56.682406 0001024 16853481 6964654 70.759029 0002048 19949649 3868486 83.758233 0004096 21231481 2586654 89.139981 0008192 21721069 2097066 91.195507 0016384 21964127 1854008 92.215982 0032768 22081886 1736249 92.710391 0065536 22191802 1626333 93.171871 0131072 22321377 1496758 93.715889 0262144 22856458 961677 95.962417 0524288 23104404 713731 97.003414 1048576 23228539 589596 97.524592 2097152 23325186 492949 97.930363 4194304 23332195 485940 97.959790 sfifo:1 0000005 4368267 19449868 18.340088 0000015 4735021 19083114 19.879898 0000032 5137235 18680900 21.568586 0000064 6246911 17571224 26.227540 0000128 8254311 15563824 34.655572 0000256 10934332 12883803 45.907591 0000512 13501621 10316514 56.686306 0001024 16860171 6957964 70.787117 0002048 19973504 3844631 83.858388 0004096 21265319 2552816 89.282049 0008192 21768426 2049709 91.394335 0016384 22012075 1806060 92.417290 0032768 22122039 1696096 92.878972 0065536 22216554 1601581 93.275792 0131072 22335192 1482943 93.773891 0262144 22865425 952710 96.000065 0524288 23108591 709544 97.020993 1048576 23230398 587737 97.532397 2097152 23325710 492425 97.932563 4194304 23332195 485940 97.959790 sfifo:2 0000005 4368267 19449868 18.340088 0000015 4735021 19083114 19.879898 0000032 5137235 18680900 21.568586 0000064 5976043 17842092 25.090306 0000128 8252773 15565362 34.649115 0000256 10941277 12876858 45.936749 0000512 13503400 10314735 56.693776 0001024 16873505 6944630 70.843099 0002048 19998858 3819277 83.964836 0004096 21318030 2500105 89.503355 0008192 21814956 2003179 91.589690 0016384 22044779 1773356 92.554598 0032768 22136540 1681595 92.939854 0065536 22222262 1595873 93.299757 0131072 22337315 1480820 93.782805 0262144 22866168 951967 96.003184 0524288 23108891 709244 97.022252 1048576 23231044 587091 97.535109 2097152 23325717 492418 97.932592 4194304 23332195 485940 97.959790 sfifo:3 0000005 4368267 19449868 18.340088 0000015 4735021 19083114 19.879898 0000032 5137235 18680900 21.568586 0000064 5976043 17842092 25.090306 0000128 8251706 15566429 34.644635 0000256 10950390 12867745 45.975010 0000512 13506305 10311830 56.705972 0001024 16889272 6928863 70.909297 0002048 20028404 3789731 84.088884 0004096 21366517 2451618 89.706927 0008192 21847538 1970597 91.726485 0016384 22060841 1757294 92.622034 0032768 22142320 1675815 92.964122 0065536 22225577 1592558 93.313675 0131072 22339413 1478722 93.791613 0262144 22866353 951782 96.003961 0524288 23111312 706823 97.032417 1048576 23233414 584721 97.545060 2097152 23325741 492394 97.932693 4194304 23332195 485940 97.959790 sfifo:4 0000005 4368267 19449868 18.340088 0000015 4735021 19083114 19.879898 0000032 5132369 18685766 21.548156 0000064 5974132 17844003 25.082283 0000128 8244135 15574000 34.612849 0000256 10957620 12860515 46.005365 0000512 13511620 10306515 56.728287 0001024 16910712 6907423 70.999312 0002048 20064802 3753333 84.241701 0004096 21415111 2403024 89.910948 0008192 21874646 1943489 91.840297 0016384 22070961 1747174 92.664522 0032768 22145401 1672734 92.977057 0065536 22227568 1590567 93.322034 0131072 22340573 1477562 93.796483 0262144 22866711 951424 96.005464 0524288 23113482 704653 97.041527 1048576 23237131 581004 97.560665 2097152 23326015 492120 97.933843 4194304 23332195 485940 97.959790 sfifo:5 0000005 4368267 19449868 18.340088 0000015 4735021 19083114 19.879898 0000032 5132369 18685766 21.548156 0000064 5917189 17900946 24.843209 0000128 8247166 15570969 34.625574 0000256 10956488 12861647 46.000613 0000512 13518977 10299158 56.759175 0001024 16928928 6889207 71.075792 0002048 20094766 3723369 84.367504 0004096 21455520 2362615 90.080605 0008192 21897571 1920564 91.936548 0016384 22079330 1738805 92.699659 0032768 22148041 1670094 92.988141 0065536 22227873 1590262 93.323314 0131072 22340873 1477262 93.797743 0262144 22875985 942150 96.044401 0524288 23116281 701854 97.053279 1048576 23243043 575092 97.585487 2097152 23326015 492120 97.933843 4194304 23332195 485940 97.959790 sfifo:6 0000005 4368267 19449868 18.340088 0000015 4735021 19083114 19.879898 0000032 5132369 18685766 21.548156 0000064 5917189 17900946 24.843209 0000128 8248593 15569542 34.631565 0000256 10969185 12848950 46.053921 0000512 13526025 10292110 56.788766 0001024 16951642 6866493 71.171156 0002048 20131053 3687082 84.519854 0004096 21494024 2324111 90.242263 0008192 21915181 1902954 92.010483 0016384 22085471 1732664 92.725442 0032768 22151112 1667023 93.001035 0065536 22230058 1588077 93.332488 0131072 22341210 1476925 93.799158 0262144 22882971 935164 96.073731 0524288 23117963 700172 97.060341 1048576 23252561 565574 97.625448 2097152 23326015 492120 97.933843 4194304 23332195 485940 97.959790 sfifo:7 0000005 4368267 19449868 18.340088 0000015 4735129 19083006 19.880352 0000032 5128746 18689389 21.532945 0000064 5911353 17906782 24.818706 0000128 8256406 15561729 34.664368 0000256 10981015 12837120 46.103589 0000512 13534987 10283148 56.826393 0001024 16972111 6846024 71.257095 0002048 20171680 3646455 84.690426 0004096 21524079 2294056 90.368448 0008192 21928020 1890115 92.064387 0016384 22089602 1728533 92.742786 0032768 22153585 1664550 93.011418 0065536 22230491 1587644 93.334306 0131072 22341182 1476953 93.799040 0262144 22885727 932408 96.085302 0524288 23120192 697943 97.069699 1048576 23259412 558723 97.654212 2097152 23326015 492120 97.933843 4194304 23332195 485940 97.959790 sfifo:8 0000005 4368267 19449868 18.340088 0000015 4735129 19083006 19.880352 0000032 5128746 18689389 21.532945 0000064 5904801 17913334 24.791198 0000128 8254149 15563986 34.654892 0000256 11000999 12817136 46.187491 0000512 13544486 10273649 56.866274 0001024 16989655 6828480 71.330753 0002048 20203980 3614155 84.826037 0004096 21549503 2268632 90.475190 0008192 21940095 1878040 92.115084 0016384 22094925 1723210 92.765135 0032768 22155508 1662627 93.019491 0065536 22230628 1587507 93.334881 0131072 22341530 1476605 93.800501 0262144 22743899 1074236 95.489840 0524288 23122958 695177 97.081312 1048576 23261200 556935 97.661719 2097152 23326015 492120 97.933843 4194304 23332195 485940 97.959790 sfifo:9 0000005 4368267 19449868 18.340088 0000015 4735129 19083006 19.880352 0000032 5128746 18689389 21.532945 0000064 5904801 17913334 24.791198 0000128 8254779 15563356 34.657537 0000256 11009794 12808341 46.224417 0000512 13558491 10259644 56.925074 0001024 17013872 6804263 71.432427 0002048 20240908 3577227 84.981078 0004096 21576583 2241552 90.588885 0008192 21949879 1868256 92.156162 0016384 22098607 1719528 92.780593 0032768 22157241 1660894 93.026767 0065536 22230837 1587298 93.335759 0131072 22341776 1476359 93.801534 0262144 22745793 1072342 95.497792 0524288 23123764 694371 97.084696 1048576 23262042 556093 97.665254 2097152 23326015 492120 97.933843 4194304 23332195 485940 97.959790 sfifo:10 0000005 4368267 19449868 18.340088 0000015 4735129 19083006 19.880352 0000032 5128229 18689906 21.530775 0000064 5900111 17918024 24.771507 0000128 8259971 15558164 34.679336 0000256 11010715 12807420 46.228284 0000512 13569363 10248772 56.970720 0001024 17030850 6787285 71.503709 0002048 20267296 3550839 85.091868 0004096 21598495 2219640 90.680882 0008192 21958785 1859350 92.193553 0016384 22101920 1716215 92.794503 0032768 22159992 1658143 93.038317 0065536 22231439 1586696 93.338286 0131072 22341572 1476563 93.800678 0262144 22695516 1122619 95.286705 0524288 23125132 693003 97.090440 1048576 23270631 547504 97.701315 2097152 23326015 492120 97.933843 4194304 23332195 485940 97.959790 sfifo:11 0000005 4368267 19449868 18.340088 0000015 4735129 19083006 19.880352 0000032 5128229 18689906 21.530775 0000064 5895658 17922477 24.752811 0000128 8222497 15595638 34.522002 0000256 11013460 12804675 46.239808 0000512 13579125 10239010 57.011706 0001024 17049854 6768281 71.583497 0002048 20295517 3522618 85.210353 0004096 21613668 2204467 90.744586 0008192 21964493 1853642 92.217518 0016384 22103771 1714364 92.802274 0032768 22159068 1659067 93.034438 0065536 22232083 1586052 93.340990 0131072 22341806 1476329 93.801660 0262144 22701350 1116785 95.311199 0524288 23126876 691259 97.097762 1048576 23275214 542921 97.720556 2097152 23326015 492120 97.933843 4194304 23332195 485940 97.959790 sfifo:15 0000005 4368267 19449868 18.340088 0000015 4734969 19083166 19.879680 0000032 5127724 18690411 21.528655 0000064 5888863 17929272 24.724283 0000128 8294211 15523924 34.823092 0000256 11005156 12812979 46.204944 0000512 13613306 10204829 57.155214 0001024 17127177 6690958 71.908136 0002048 20416106 3402029 85.716644 0004096 21670588 2147547 90.983564 0008192 21985320 1832815 92.304960 0016384 22104377 1713758 92.804819 0032768 22159446 1658689 93.036025 0065536 22232722 1585413 93.343673 0131072 22342039 1476096 93.802638 0262144 22707610 1110525 95.337481 0524288 23141079 677056 97.157393 1048576 23276637 541498 97.726531 2097152 23326015 492120 97.933843 4194304 23332195 485940 97.959790 sfifo:20 0000005 4396961 19421174 18.460560 0000015 4734987 19083148 19.879755 0000032 5126484 18691651 21.523448 0000064 5881317 17936818 24.692601 0000128 7961974 15856161 33.428201 0000256 11005365 12812770 46.205822 0000512 13651756 10166379 57.316645 0001024 17188492 6629643 72.165566 0002048 20543409 3274726 86.251123 0004096 21716571 2101564 91.176622 0008192 22001236 1816899 92.371783 0016384 22110103 1708032 92.828859 0032768 22162580 1655555 93.049183 0065536 22234067 1584068 93.349320 0131072 22343170 1474965 93.807387 0262144 22664115 1154020 95.154868 0524288 23164769 653366 97.256855 1048576 23276936 541199 97.727786 2097152 23326015 492120 97.933843 4194304 23332195 485940 97.959790 ~/projects/fslog/replacement -M5 -V2356223 -f 86839 < fslog.trace kin=25 for kout in 10 20 30 40 50 ;do echo 2q: kin: $kin kout: $kout for s in 5 15 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 ;do printf "% 7.7d " $s; ~/projects/fslog/replacement -M$s -V2356223 \ -f 86839 -a 2q -k $kin -K $kout < fslog.trace done echo done 2q: kin: 25 kout: 10 0000005 4368267 19449868 18.340088 0000015 4735021 19083114 19.879898 0000032 4784727 19033408 20.088588 0000064 6603479 17214656 27.724585 0000128 8420880 15397255 35.354909 0000256 13425332 10392803 56.366009 0000512 15744090 8074045 66.101271 0001024 19366344 4451791 81.309238 0002048 21516482 2301653 90.336552 0004096 21800939 2017196 91.530840 0008192 21984917 1833218 92.303268 0016384 22110763 1707372 92.831630 0032768 22175520 1642615 93.103511 0065536 22244130 1574005 93.391569 0131072 22378895 1439240 93.957377 0262144 22752864 1065271 95.527479 0524288 23110076 708059 97.027227 1048576 23229651 588484 97.529261 2097152 23325186 492949 97.930363 4194304 23332195 485940 97.959790 2q: kin: 25 kout: 20 0000005 4368267 19449868 18.340088 0000015 4633252 19184883 19.452623 0000032 5215344 18602791 21.896525 0000064 6007615 17810520 25.222861 0000128 7517525 16300610 31.562190 0000256 13508873 10309262 56.716754 0000512 15553541 8264594 65.301255 0001024 19189061 4629074 80.564918 0002048 21491204 2326931 90.230423 0004096 21818995 1999140 91.606648 0008192 21981427 1836708 92.288615 0016384 22103281 1714854 92.800217 0032768 22175808 1642327 93.104720 0065536 22247877 1570258 93.407301 0131072 22437683 1380452 94.204198 0262144 22781140 1036995 95.646196 0524288 23107908 710227 97.018125 1048576 23230734 587401 97.533808 2097152 23325186 492949 97.930363 4194304 23332195 485940 97.959790 2q: kin: 25 kout: 30 0000005 4368267 19449868 18.340088 0000015 4733252 19084883 19.872471 0000032 5368508 18449627 22.539582 0000064 6114873 17703262 25.673181 0000128 7514707 16303428 31.550359 0000256 13420344 10397791 56.345066 0000512 15454512 8363623 64.885483 0001024 19047540 4770595 79.970745 0002048 21466332 2351803 90.125999 0004096 21827650 1990485 91.642985 0008192 21981629 1836506 92.289463 0016384 22101415 1716720 92.792383 0032768 22173742 1644393 93.096046 0065536 22248980 1569155 93.411932 0131072 22476971 1341164 94.369148 0262144 22787398 1030737 95.672470 0524288 23107671 710464 97.017130 1048576 23230738 587397 97.533825 2097152 23325186 492949 97.930363 4194304 23332195 485940 97.959790 2q: kin: 25 kout: 40 0000005 3864270 19953865 16.224066 0000015 4727589 19090546 19.848695 0000032 5562286 18255849 23.353155 0000064 6415199 17402936 26.934095 0000128 8084314 15733821 33.941843 0000256 13316138 10501997 55.907560 0000512 15390069 8428066 64.614921 0001024 18919398 4898737 79.432743 0002048 21442956 2375179 90.027855 0004096 21830577 1987558 91.655274 0008192 21990371 1827764 92.326167 0016384 22100406 1717729 92.788147 0032768 22165760 1652375 93.062534 0065536 22277950 1540185 93.533562 0131072 22503178 1314957 94.479177 0262144 22822182 995953 95.818510 0524288 23108698 709437 97.021442 1048576 23230738 587397 97.533825 2097152 23325186 492949 97.930363 4194304 23332195 485940 97.959790 2q: kin: 25 kout: 50 0000005 3864270 19953865 16.224066 0000015 4732383 19085752 19.868823 0000032 5480621 18337514 23.010286 0000064 6228543 17589592 26.150423 0000128 8417429 15400706 35.340420 0000256 13233622 10584513 55.561118 0000512 15333253 8484882 64.376380 0001024 18816376 5001759 79.000207 0002048 21426159 2391976 89.957333 0004096 21833041 1985094 91.665619 0008192 21991446 1826689 92.330680 0016384 22100371 1717764 92.788000 0032768 22156732 1661403 93.024630 0065536 22279098 1539037 93.538382 0131072 22507472 1310663 94.497206 0262144 22840959 977176 95.897345 0524288 23110862 707273 97.030527 1048576 23230738 587397 97.533825 2097152 23325186 492949 97.930363 4194304 23332195 485940 97.959790