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