-
Notifications
You must be signed in to change notification settings - Fork 1
Numerical results (tables)
Jean-Francois Baffier edited this page May 24, 2017
·
7 revisions
Those two tables store the numerical results of two sets of experiments evaluating the compressed stack structure. Both uses the TestRun example. The first scenario, Push Only, is favorable to the compression as it pushes all the data into the stack. It illustrates the potential of compression of the Compressed Stacks.
On the contrary, the second scenario, Christmas Tree, is unfavorable to the compression and illustrates the worst gain of memory and loss of speed a user can expect.
| Size | 2^i | Classique | 10 | 50 | 100 | 500 | sqrt | 4root | 8root | log | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| time | mem | time | mem | time | mem | time | mem | time | mem | time | mem | time | mem | time | mem | time | mem | ||
| 1024 | 10 | 0 | 31310 | 0 | 13471 | 0 | 15719 | 0 | 23211 | 0 | 83217 | 0 | 22626 | 0 | 11790 | 0 | 10814 | 0 | 11065 |
| 2048 | 11 | 0 | 55885 | 0 | 13471 | 0 | 25031 | 0 | 23691 | 0 | 83443 | 0 | 18151 | 0 | 11465 | 0 | 11174 | 0 | 11456 |
| 4096 | 12 | 0 | 105038 | 0 | 13471 | 1 | 27986 | 0 | 24624 | 0 | 83200 | 0 | 39271 | 0 | 15041 | 0 | 12041 | 0 | 15036 |
| 8192 | 13 | 0 | 203343 | 0 | 15590 | 0 | 27987 | 0 | 42940 | 1 | 83757 | 0 | 29516 | 0 | 15915 | 0 | 12042 | 0 | 15109 |
| 16384 | 14 | 0 | 399951 | 0 | 15680 | 0 | 27987 | 0 | 48820 | 0 | 84403 | 0 | 39897 | 1 | 16835 | 0 | 12666 | 0 | 15707 |
| 32768 | 15 | 0 | 793167 | 1 | 15754 | 0 | 27987 | 0 | 48820 | 0 | 86393 | 0 | 51540 | 0 | 15950 | 0 | 12250 | 0 | 16131 |
| 65536 | 16 | 1 | 1579600 | 0 | 17940 | 0 | 34756 | 1 | 48821 | 0 | 88914 | 0 | 73074 | 0 | 22924 | 1 | 12992 | 0 | 16225 |
| 131072 | 17 | 0 | 3152464 | 1 | 17961 | 0 | 36169 | 1 | 48821 | 0 | 168570 | 0 | 96930 | 0 | 24985 | 1 | 12971 | 1 | 18980 |
| 262144 | 18 | 0 | 6298192 | 1 | 18009 | 1 | 35737 | 0 | 49589 | 1 | 204213 | 1 | 138706 | 1 | 26729 | 1 | 15904 | 1 | 19761 |
| 524288 | 19 | 1 | 12589649 | 1 | 19933 | 2 | 36146 | 1 | 62355 | 1 | 204214 | 0 | 186375 | 1 | 24573 | 2 | 16145 | 2 | 19837 |
| 1048576 | 20 | 2 | 25172561 | 4 | 20509 | 2 | 36146 | 2 | 65019 | 2 | 204214 | 2 | 269900 | 3 | 39002 | 4 | 17025 | 3 | 20618 |
| 2097152 | 21 | 3 | 50338385 | 7 | 20530 | 5 | 36842 | 4 | 65019 | 4 | 204214 | 4 | 367052 | 6 | 43170 | 8 | 17025 | 7 | 20949 |
| 4194304 | 22 | 7 | 100670033 | 15 | 20530 | 11 | 45362 | 9 | 65019 | 8 | 204214 | 7 | 535812 | 12 | 46634 | 16 | 17956 | 12 | 21090 |
| 8388608 | 23 | 13 | 201333330 | 28 | 22574 | 20 | 46107 | 16 | 64975 | 15 | 204215 | 16 | 722944 | 16 | 42275 | 28 | 17339 | 22 | 21857 |
| 16777216 | 24 | 22 | 402659921 | 52 | 22523 | 37 | 46131 | 30 | 65932 | 27 | 206039 | 30 | 1058877 | 40 | 71187 | 62 | 18978 | 52 | 31294 |
| 33554432 | 25 | 49 | 805313106 | 103 | 22574 | 74 | 46854 | 61 | 65956 | 53 | 209759 | 51 | 1448904 | 77 | 79115 | 119 | 23874 | 100 | 32102 |
| 67108864 | 26 | 95 | 1610619475 | 242 | 24612 | 142 | 46900 | 150 | 84149 | 127 | 265269 | 97 | 2119426 | 147 | 86733 | 277 | 24732 | 204 | 32103 |
| 134217728 | 27 | 203 | 3221232211 | 502 | 25238 | 319 | 47668 | 304 | 86309 | 272 | 276957 | 194 | 2886903 | 244 | 77880 | 494 | 25628 | 449 | 33052 |
| 268435456 | 28 | 453 | 6442457683 | 885 | 25236 | 670 | 56668 | 639 | 86261 | 507 | 276955 | 410 | 4206559 | 615 | 137000 | 986 | 26540 | 778 | 33478 |
| 536870912 | 29 | 816 | 12884908628 | 2074 | 27013 | 1382 | 56717 | 1199 | 86289 | 1029 | 276958 | 822 | 5574982 | 1011 | 119774 | 1975 | 27541 | 1563 | 34176 |
| 1073741824 | 30 | 1250 | 25769942944 | 5590 | 40765 | 2854 | 56703 | 3360 | 82302 | 1558 | 277002 | 1265 | 5820112 | 1956 | 145321 | 4835 | 31264 | 4303 | 55822 |
| Size | 2^i | Classique | 10 | 50 | 100 | 500 | sqrt | 4root | 8root | log | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| time | mem | time | mem | time | mem | time | mem | time | mem | time | mem | time | mem | time | mem | time | mem | ||
| 1024 | 10 | 0 | 9788 | 0 | 14580 | 1 | 17184 | 0 | 26665 | 0 | 60401 | 0 | 14104 | 0 | 14279 | 0 | 14815 | 0 | 12075 |
| 2048 | 11 | 0 | 12860 | 0 | 15052 | 0 | 17272 | 0 | 26665 | 0 | 60401 | 0 | 21756 | 0 | 13207 | 0 | 15011 | 0 | 13179 |
| 4096 | 12 | 0 | 19004 | 0 | 18116 | 0 | 23628 | 0 | 27265 | 0 | 94705 | 0 | 19984 | 0 | 16579 | 0 | 18603 | 0 | 16579 |
| 8192 | 13 | 0 | 19004 | 0 | 17828 | 0 | 24012 | 0 | 27265 | 0 | 94705 | 0 | 34908 | 0 | 18031 | 0 | 17683 | 0 | 18031 |
| 16384 | 14 | 0 | 31293 | 0 | 19345 | 0 | 24013 | 0 | 37582 | 0 | 94786 | 0 | 31938 | 0 | 19545 | 1 | 18428 | 0 | 18552 |
| 32768 | 15 | 0 | 55869 | 0 | 23173 | 0 | 30841 | 0 | 51426 | 0 | 95258 | 0 | 41778 | 0 | 23561 | 0 | 23372 | 0 | 23173 |
| 65536 | 16 | 0 | 55869 | 1 | 24189 | 1 | 30841 | 1 | 51426 | 0 | 95258 | 0 | 56290 | 1 | 23117 | 1 | 21312 | 1 | 26261 |
| 131072 | 17 | 1 | 105022 | 1 | 25306 | 1 | 35742 | 1 | 51427 | 0 | 96291 | 1 | 74403 | 1 | 27418 | 1 | 22349 | 1 | 26262 |
| 262144 | 18 | 0 | 203326 | 2 | 25306 | 0 | 37110 | 1 | 52355 | 0 | 145151 | 0 | 99107 | 1 | 30754 | 2 | 26329 | 1 | 24834 |
| 524288 | 19 | 0 | 203326 | 3 | 25306 | 1 | 37110 | 1 | 52355 | 1 | 146127 | 1 | 138955 | 1 | 35818 | 5 | 29961 | 2 | 31962 |
| 1048576 | 20 | 0 | 399935 | 5 | 27327 | 3 | 49551 | 3 | 62832 | 2 | 146128 | 1 | 188429 | 3 | 35103 | 9 | 29962 | 5 | 31963 |
| 2097152 | 21 | 2 | 793151 | 13 | 32815 | 5 | 49551 | 5 | 63872 | 5 | 208172 | 4 | 259157 | 7 | 46051 | 16 | 30122 | 11 | 34851 |
| 4194304 | 22 | 3 | 793151 | 29 | 32815 | 11 | 49551 | 12 | 63872 | 8 | 208172 | 5 | 366501 | 12 | 50755 | 38 | 35682 | 25 | 41683 |
| 8388608 | 23 | 7 | 1579583 | 67 | 38635 | 22 | 55379 | 24 | 85280 | 16 | 208172 | 11 | 504341 | 23 | 59107 | 55 | 31582 | 49 | 41683 |
| 16777216 | 24 | 14 | 3152448 | 145 | 41456 | 60 | 71680 | 50 | 87033 | 34 | 209909 | 21 | 701726 | 45 | 58336 | 128 | 41887 | 77 | 42788 |
| 33554432 | 25 | 27 | 3152448 | 290 | 41456 | 121 | 73256 | 101 | 87033 | 69 | 209909 | 47 | 998534 | 120 | 79188 | 258 | 43515 | 200 | 46200 |
| 67108864 | 26 | 53 | 6298176 | 591 | 41456 | 241 | 73256 | 206 | 88185 | 138 | 209909 | 89 | 1383782 | 239 | 90772 | 721 | 46467 | 358 | 46096 |
| 134217728 | 27 | 105 | 12589633 | 1510 | 50301 | 560 | 73257 | 464 | 96854 | 309 | 258730 | 183 | 1944408 | 442 | 102446 | 1501 | 50301 | 866 | 55621 |
| 268435456 | 28 | 212 | 12589633 | 2990 | 50301 | 1137 | 74489 | 934 | 98566 | 643 | 258730 | 323 | 2754704 | 712 | 104698 | 3378 | 56901 | 2333 | 62141 |
| 536870912 | 29 | 479 | 25172545 | 6123 | 51693 | 2310 | 79397 | 2061 | 98566 | 1510 | 258730 | 881 | 3853128 | 2149 | 135446 | 4869 | 56517 | 4245 | 63149 |
| 1073741824 | 30 | 1195 | 50338370 | 16051 | 54782 | 6279 | 101318 | 4801 | 127131 | 2948 | 349859 | 1407 | 5392905 | 3344 | 146675 | 11465 | 64342 | 8023 | 63150 |