| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | AA | AB | AC | AD | AE | AF | AG | AH | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | average accross graphs | ||||||||||||||||||||||||||||||||||
2 | structure | BFS | Coloring | KCore | LDD | MIS | Map | Map_withRemote_0 | Map_withRemote_1 | Map_withRemote_16 | Map_withRemote_2 | Map_withRemote_32 | Map_withRemote_4 | Map_withRemote_64 | Map_withRemote_8 | PageRank | SSBetweennessCentrality | SimpleUnionCC | Spanner | WorkEfficientDensestSubgraph | average | ||||||||||||||
3 | run_csr_byte | 1.139 | 1.000 | 1.008 | 1.089 | 1.057 | 1.028 | 1.009 | 1.032 | 0.994 | 0.977 | 1.008 | 1.029 | 0.999 | 1.000 | 0.987 | 1.013 | 0.994 | 1.024 | 1.079 | 1.025 | ||||||||||||||
4 | run_csr | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | ||||||||||||||
5 | run_csr_shuffled | 1.023 | 0.989 | 0.979 | 1.024 | 0.955 | 0.967 | 0.985 | 1.020 | 0.992 | 0.977 | 0.987 | 0.989 | 0.981 | 1.003 | 0.986 | 1.010 | 0.852 | 1.118 | 1.033 | 0.993 | ||||||||||||||
6 | run_csr_compressed | 1.181 | 1.170 | 1.010 | 1.175 | 1.257 | 2.996 | 1.784 | 1.589 | 1.332 | 1.423 | 1.270 | 1.385 | 1.205 | 1.389 | 1.248 | 1.306 | 1.205 | 1.225 | 1.164 | 1.385 | ||||||||||||||
7 | run_vector_vector | 1.090 | 1.030 | 1.058 | 1.104 | 1.024 | 1.037 | 0.978 | 1.009 | 0.947 | 0.977 | 0.946 | 1.000 | 0.947 | 0.970 | 0.936 | 0.926 | 1.208 | 0.891 | 1.095 | 1.009 | ||||||||||||||
8 | run_dhb | 1.349 | 1.177 | 1.183 | 1.221 | 1.110 | 2.586 | 1.642 | 1.382 | 1.130 | 1.289 | 1.081 | 1.269 | 1.074 | 1.218 | 1.061 | 1.074 | 0.884 | 1.008 | 1.132 | 1.256 | ||||||||||||||
9 | run_sstgraph | 1.207 | 1.505 | 1.030 | 1.175 | 1.149 | 1.619 | 1.431 | 1.406 | 1.304 | 1.289 | 1.261 | 1.294 | 1.243 | 1.329 | 1.269 | 1.232 | 1.157 | 1.196 | 1.159 | 1.277 | ||||||||||||||
10 | run_vector_tinyset | 1.339 | 1.774 | 1.236 | 1.289 | 1.101 | 1.596 | 1.377 | 1.319 | 1.229 | 1.273 | 1.197 | 1.291 | 1.162 | 1.274 | 1.107 | 1.236 | 1.166 | 1.194 | 1.258 | 1.285 | ||||||||||||||
11 | run_absl_btree_set | 1.436 | 1.275 | 1.241 | 1.351 | 1.190 | 1.977 | 1.683 | 1.452 | 1.226 | 1.348 | 1.137 | 1.335 | 1.097 | 1.291 | 1.157 | 1.314 | 0.946 | 1.092 | 1.236 | 1.304 | ||||||||||||||
12 | run_absl_btree_set_inplace | 1.305 | 1.356 | 1.325 | 1.190 | 1.149 | 1.822 | 1.461 | 1.328 | 1.117 | 1.246 | 1.072 | 1.237 | 1.035 | 1.195 | 1.159 | 1.234 | 0.926 | 1.069 | 1.236 | 1.235 | ||||||||||||||
13 | run_absl_flat_hash_set | 1.667 | 1.424 | 1.237 | 1.588 | 1.277 | 2.842 | 2.069 | 1.795 | 1.308 | 1.574 | 1.221 | 1.522 | 1.170 | 1.426 | 1.300 | 1.498 | 1.195 | 1.377 | 1.300 | 1.515 | ||||||||||||||
14 | run_absl_flat_hash_set_inplace | 1.399 | 1.467 | 1.196 | 1.322 | 1.234 | 2.769 | 1.940 | 1.919 | 1.262 | 1.623 | 1.183 | 1.422 | 1.359 | 1.346 | 1.253 | 1.396 | 0.998 | 1.099 | 1.343 | 1.449 | ||||||||||||||
15 | run_terrace | 1.300 | 1.388 | 1.211 | 1.269 | 1.057 | 1.891 | 1.448 | 1.376 | 1.193 | 1.268 | 1.133 | 1.266 | 1.101 | 1.216 | 1.053 | 1.102 | 0.967 | 1.293 | 1.210 | 1.250 | ||||||||||||||
16 | run_vector_pma | 1.457 | 1.135 | 1.045 | 1.473 | 1.273 | 3.216 | 2.324 | 2.012 | 1.533 | 1.842 | 1.298 | 1.771 | 1.265 | 1.661 | 1.218 | 1.152 | 1.091 | 1.164 | 1.202 | 1.533 | ||||||||||||||
17 | run_vector_cpma | 1.501 | 1.219 | 1.107 | 1.512 | 1.387 | 3.906 | 2.714 | 2.298 | 1.546 | 2.033 | 1.389 | 1.937 | 1.246 | 1.782 | 1.341 | 1.355 | 1.191 | 1.271 | 1.260 | 1.684 | ||||||||||||||
18 | run_vector_spma | 1.519 | 1.146 | 1.042 | 1.476 | 1.277 | 3.226 | 2.314 | 2.025 | 1.486 | 1.845 | 1.326 | 1.814 | 1.218 | 1.724 | 1.246 | 1.156 | 1.099 | 1.167 | 1.190 | 1.542 | ||||||||||||||
19 | run_vector_scpma | 1.545 | 1.228 | 1.110 | 1.514 | 1.377 | 3.892 | 2.755 | 2.360 | 1.576 | 2.080 | 1.461 | 2.014 | 1.255 | 1.809 | 1.355 | 1.369 | 1.198 | 1.272 | 1.267 | 1.707 | ||||||||||||||
20 | run_single_pma | 1.273 | 0.985 | 1.004 | 1.165 | 1.123 | 2.070 | 1.543 | 1.296 | 1.137 | 1.267 | 1.099 | 1.182 | 1.061 | 1.168 | 1.155 | 1.183 | 1.015 | 1.116 | 1.079 | 1.206 | ||||||||||||||
21 | run_single_cpma | 1.344 | 1.354 | 1.011 | 1.154 | 1.337 | 2.841 | 2.031 | 1.390 | 1.188 | 1.279 | 1.142 | 1.257 | 1.114 | 1.228 | 1.678 | 1.487 | 1.077 | 1.228 | 1.195 | 1.386 | ||||||||||||||
22 | run_single_spma | 1.348 | 1.038 | 1.042 | 1.255 | 1.176 | 2.213 | 1.615 | 1.370 | 1.183 | 1.251 | 1.138 | 1.281 | 1.115 | 1.215 | 1.202 | 1.258 | 1.080 | 1.167 | 1.112 | 1.266 | ||||||||||||||
23 | run_single_scpma | 1.368 | 1.384 | 1.019 | 1.174 | 1.346 | 2.880 | 2.087 | 1.429 | 1.206 | 1.306 | 1.158 | 1.291 | 1.120 | 1.239 | 1.732 | 1.524 | 1.082 | 1.238 | 1.204 | 1.410 | ||||||||||||||
24 | run_vector_aspen | 1.306 | 1.588 | 1.255 | 1.338 | 1.112 | 1.677 | 1.323 | 1.252 | 1.138 | 1.209 | 1.034 | 1.202 | 1.009 | 1.169 | 1.074 | 1.075 | 0.882 | 1.049 | 1.190 | 1.204 | ||||||||||||||
25 | run_vector_aspen_inplace | 1.090 | 1.552 | 1.091 | 1.098 | 1.047 | 1.386 | 1.106 | 1.029 | 0.976 | 1.001 | 0.967 | 1.002 | 0.961 | 1.003 | 1.005 | 1.020 | 0.964 | 0.998 | 1.136 | 1.075 | ||||||||||||||
26 | run_std_set | 3.229 | 2.293 | 1.731 | 2.674 | 2.909 | 12.090 | 7.922 | 6.098 | 3.305 | 5.117 | 2.703 | 4.629 | 2.397 | 3.994 | 3.024 | 3.606 | 2.205 | 2.335 | 2.360 | 3.927 | ||||||||||||||
27 | run_std_set_inplace | 2.629 | 2.238 | 1.664 | 2.212 | 2.717 | 11.321 | 7.429 | 5.648 | 2.976 | 4.690 | 2.546 | 4.242 | 2.235 | 3.680 | 2.880 | 3.513 | 2.098 | 2.186 | 2.348 | 3.645 | ||||||||||||||
28 | run_std_unordered_set | 3.004 | 1.626 | 1.311 | 2.708 | 2.058 | 7.661 | 4.982 | 4.004 | 2.359 | 3.444 | 1.934 | 3.111 | 1.755 | 2.758 | 2.032 | 2.265 | 1.554 | 2.053 | 1.722 | 2.755 | ||||||||||||||
29 | run_std_unordered_set_inplace | 2.557 | 1.678 | 1.312 | 2.205 | 2.007 | 7.388 | 4.751 | 3.749 | 2.166 | 3.217 | 1.842 | 2.923 | 1.713 | 2.572 | 1.965 | 2.222 | 1.444 | 1.963 | 1.705 | 2.599 | ||||||||||||||
30 | run_vector_compressed_aspen | 1.411 | 1.857 | 1.149 | 1.377 | 1.457 | 2.572 | 1.837 | 1.681 | 1.431 | 1.559 | 1.372 | 1.532 | 1.330 | 1.482 | 1.589 | 1.618 | 1.153 | 1.274 | 1.444 | 1.533 | ||||||||||||||
31 | run_vector_compressed_aspen_inplace | 1.171 | 1.781 | 1.052 | 1.181 | 1.357 | 2.280 | 1.699 | 1.536 | 1.321 | 1.414 | 1.266 | 1.385 | 1.210 | 1.377 | 1.409 | 1.447 | 1.138 | 1.194 | 1.349 | 1.398 | ||||||||||||||
32 | run_vector_cpam | 1.214 | 1.363 | 1.102 | 1.180 | 1.134 | 1.477 | 1.424 | 1.375 | 1.175 | 1.270 | 1.146 | 1.287 | 1.123 | 1.270 | 1.135 | 1.155 | 1.040 | 1.101 | 1.193 | 1.219 | ||||||||||||||
33 | run_vector_cpam_inplace | 1.076 | 1.345 | 1.043 | 1.082 | 1.054 | 1.264 | 1.191 | 1.140 | 1.064 | 1.112 | 1.030 | 1.103 | 1.015 | 1.092 | 1.050 | 1.008 | 0.965 | 1.006 | 1.132 | 1.093 | ||||||||||||||
34 | run_vector_compressed_cpam | 1.385 | 1.473 | 1.016 | 1.309 | 1.381 | 2.913 | 2.162 | 1.933 | 1.522 | 1.732 | 1.453 | 1.658 | 1.320 | 1.596 | 1.417 | 1.480 | 1.192 | 1.285 | 1.287 | 1.553 | ||||||||||||||
35 | run_vector_compressed_cpam_inplace | 1.146 | 1.509 | 1.127 | 1.142 | 1.278 | 2.384 | 1.812 | 1.647 | 1.341 | 1.461 | 1.257 | 1.427 | 1.216 | 1.406 | 1.328 | 1.332 | 1.224 | 1.201 | 1.335 | 1.399 | ||||||||||||||
36 | |||||||||||||||||||||||||||||||||||
37 | |||||||||||||||||||||||||||||||||||
38 | |||||||||||||||||||||||||||||||||||
39 | |||||||||||||||||||||||||||||||||||
40 | average accross algorithms | ||||||||||||||||||||||||||||||||||
41 | structure | SD | LJ | CO | RM | road | TW | kron | PR | papers | FS | ER | |||||||||||||||||||||||
42 | run_csr_byte | #DIV/0! | 1.018 | 1.027 | 1.047 | 0.998 | 1.044 | 1.049 | 1.038 | 1.128 | 1.103 | 1.032 | 1.048 | ||||||||||||||||||||||
43 | run_csr | #DIV/0! | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 | ||||||||||||||||||||||
44 | run_csr_shuffled | #DIV/0! | 1.050 | 1.173 | 1.006 | 1.021 | 1.037 | 1.021 | 0.997 | 0.988 | 1.024 | 1.018 | 1.034 | ||||||||||||||||||||||
45 | run_csr_compressed | #DIV/0! | 1.225 | 1.285 | 1.308 | 1.143 | 1.203 | 1.226 | 1.302 | 1.256 | 1.243 | 1.219 | 1.241 | ||||||||||||||||||||||
46 | run_vector_vector | #DIV/0! | 1.038 | 1.039 | 1.085 | 1.163 | 1.080 | 1.176 | 1.059 | 1.070 | 1.112 | 1.012 | 1.083 | ||||||||||||||||||||||
47 | run_dhb | #DIV/0! | 1.253 | 1.265 | 1.197 | 1.035 | 1.419 | 1.189 | 1.067 | 1.087 | 1.082 | 1.115 | 1.171 | ||||||||||||||||||||||
48 | run_sstgraph | #DIV/0! | 1.270 | 1.256 | 1.300 | 1.102 | 1.438 | 1.359 | 1.279 | 1.200 | 1.212 | 1.190 | 1.261 | ||||||||||||||||||||||
49 | run_vector_tinyset | #DIV/0! | 1.220 | 1.338 | 1.222 | 1.153 | 1.866 | 1.893 | 1.130 | 1.128 | 1.169 | 1.181 | 1.330 | ||||||||||||||||||||||
50 | run_absl_btree_set | #DIV/0! | 1.253 | 1.321 | 1.285 | 1.132 | 1.476 | 1.420 | 1.142 | 1.214 | 1.180 | 1.388 | 1.281 | ||||||||||||||||||||||
51 | run_absl_btree_set_inplace | #DIV/0! | 1.182 | 1.302 | 1.198 | 1.082 | 1.470 | 1.575 | 1.157 | 1.090 | 1.179 | 1.258 | 1.249 | ||||||||||||||||||||||
52 | run_absl_flat_hash_set | #DIV/0! | 1.488 | 1.769 | 1.518 | 1.239 | 1.833 | 1.528 | 1.308 | 1.224 | 1.245 | 1.344 | 1.450 | ||||||||||||||||||||||
53 | run_absl_flat_hash_set_inplace | #DIV/0! | 1.287 | 1.418 | 1.291 | 1.054 | 1.740 | 1.480 | 1.305 | 1.205 | 1.215 | 1.279 | 1.327 | ||||||||||||||||||||||
54 | run_terrace | #DIV/0! | 1.138 | 1.402 | 1.111 | 1.090 | 1.657 | 1.554 | 1.130 | 1.100 | 1.157 | 1.043 | 1.238 | ||||||||||||||||||||||
55 | run_vector_pma | #DIV/0! | 1.433 | 1.258 | 1.285 | 1.702 | 1.264 | 1.194 | 1.131 | 1.245 | 1.181 | 1.110 | 1.280 | ||||||||||||||||||||||
56 | run_vector_cpma | #DIV/0! | 1.571 | 1.423 | 1.448 | 1.701 | 1.328 | 1.261 | 1.237 | 1.317 | 1.238 | 1.241 | 1.376 | ||||||||||||||||||||||
57 | run_vector_spma | #DIV/0! | 1.517 | 1.260 | 1.288 | 1.704 | 1.266 | 1.175 | 1.123 | 1.261 | 1.190 | 1.102 | 1.289 | ||||||||||||||||||||||
58 | run_vector_scpma | #DIV/0! | 1.556 | 1.462 | 1.420 | 1.695 | 1.349 | 1.258 | 1.248 | 1.313 | 1.241 | 1.241 | 1.378 | ||||||||||||||||||||||
59 | run_single_pma | #DIV/0! | 1.158 | 1.199 | 1.229 | 1.037 | 1.178 | 1.134 | 1.200 | 1.141 | 1.135 | 1.175 | 1.159 | ||||||||||||||||||||||
60 | run_single_cpma | #DIV/0! | 1.397 | 1.485 | 1.420 | 1.093 | 1.312 | 1.239 | 1.455 | 1.306 | 1.301 | 1.361 | 1.337 | ||||||||||||||||||||||
61 | run_single_spma | #DIV/0! | 1.167 | 1.227 | 1.258 | 1.050 | 1.180 | 1.167 | 1.251 | 1.164 | 1.144 | 1.210 | 1.182 | ||||||||||||||||||||||
62 | run_single_scpma | #DIV/0! | 1.414 | 1.533 | 1.497 | 1.107 | 1.321 | 1.266 | 1.481 | 1.308 | 1.288 | 1.386 | 1.360 | ||||||||||||||||||||||
63 | run_vector_aspen | #DIV/0! | 1.241 | 1.163 | 1.203 | 1.425 | 1.273 | 1.443 | 1.153 | 1.187 | 1.202 | 1.210 | 1.250 | ||||||||||||||||||||||
64 | run_vector_aspen_inplace | #DIV/0! | 1.107 | 1.126 | 1.126 | 1.109 | 1.184 | 1.239 | 1.171 | 1.158 | 1.191 | 1.146 | 1.156 | ||||||||||||||||||||||
65 | run_std_set | #DIV/0! | 2.713 | 3.487 | 3.305 | 1.474 | 3.235 | 2.545 | 3.702 | 2.295 | 2.210 | 3.212 | 2.818 | ||||||||||||||||||||||
66 | run_std_set_inplace | #DIV/0! | 2.434 | 3.324 | 3.054 | 1.067 | 3.098 | 2.536 | 3.683 | 1.928 | 2.068 | 2.970 | 2.616 | ||||||||||||||||||||||
67 | run_std_unordered_set | #DIV/0! | 2.176 | 3.129 | 2.547 | 1.658 | 2.372 | 1.685 | 2.311 | 1.779 | 1.894 | 2.062 | 2.161 | ||||||||||||||||||||||
68 | run_std_unordered_set_inplace | #DIV/0! | 1.923 | 2.806 | 2.255 | 1.468 | 2.253 | 1.677 | 2.331 | 1.692 | 1.836 | 2.021 | 2.026 | ||||||||||||||||||||||
69 | run_vector_compressed_aspen | #DIV/0! | 1.341 | 1.532 | 1.571 | 1.284 | 1.514 | 1.492 | 1.545 | 1.473 | 1.445 | 1.513 | 1.471 | ||||||||||||||||||||||
70 | run_vector_compressed_aspen_inplace | #DIV/0! | 1.262 | 1.444 | 1.419 | 1.094 | 1.401 | 1.471 | 1.542 | 1.313 | 1.379 | 1.380 | 1.370 | ||||||||||||||||||||||
71 | run_vector_cpam | #DIV/0! | 1.245 | 1.125 | 1.171 | 1.236 | 1.130 | 1.117 | 1.178 | 1.148 | 1.169 | 1.118 | 1.164 | ||||||||||||||||||||||
72 | run_vector_cpam_inplace | #DIV/0! | 1.120 | 1.094 | 1.100 | 1.094 | 1.125 | 1.171 | 1.186 | 1.078 | 1.198 | 1.066 | 1.123 | ||||||||||||||||||||||
73 | run_vector_compressed_cpam | #DIV/0! | 1.320 | 1.445 | 1.491 | 1.283 | 1.328 | 1.299 | 1.503 | 1.401 | 1.389 | 1.374 | 1.383 | ||||||||||||||||||||||
74 | run_vector_compressed_cpam_inplace | #DIV/0! | 1.216 | 1.328 | 1.339 | 1.100 | 1.322 | 1.479 | 1.508 | 1.249 | 1.373 | 1.300 | 1.321 | ||||||||||||||||||||||
75 | |||||||||||||||||||||||||||||||||||
76 | |||||||||||||||||||||||||||||||||||
77 | |||||||||||||||||||||||||||||||||||
78 | |||||||||||||||||||||||||||||||||||
79 | overall average | ||||||||||||||||||||||||||||||||||
80 | structure | normalized running time | benefit of inplace | benefit of colocated data | benefits of sharing data | cost of compression | |||||||||||||||||||||||||||||
81 | run_csr_byte | 1.048 | |||||||||||||||||||||||||||||||||
82 | run_csr | 1.000 | 1.083 | ||||||||||||||||||||||||||||||||
83 | run_csr_shuffled | 1.034 | |||||||||||||||||||||||||||||||||
84 | run_csr_compressed | 1.241 | 0.806 | ||||||||||||||||||||||||||||||||
85 | run_vector_vector | 1.083 | |||||||||||||||||||||||||||||||||
86 | run_dhb | 1.171 | |||||||||||||||||||||||||||||||||
87 | run_sstgraph | 1.261 | 1.055 | ||||||||||||||||||||||||||||||||
88 | run_vector_tinyset | 1.330 | |||||||||||||||||||||||||||||||||
89 | run_absl_btree_set | 1.281 | |||||||||||||||||||||||||||||||||
90 | run_absl_btree_set_inplace | 1.249 | 1.026 | ||||||||||||||||||||||||||||||||
91 | run_absl_flat_hash_set | 1.450 | |||||||||||||||||||||||||||||||||
92 | run_absl_flat_hash_set_inplace | 1.327 | 1.092 | ||||||||||||||||||||||||||||||||
93 | run_terrace | 1.238 | |||||||||||||||||||||||||||||||||
94 | run_vector_pma | 1.280 | |||||||||||||||||||||||||||||||||
95 | run_vector_cpma | 1.376 | 0.930 | ||||||||||||||||||||||||||||||||
96 | run_vector_spma | 1.289 | |||||||||||||||||||||||||||||||||
97 | run_vector_scpma | 1.378 | 0.935 | ||||||||||||||||||||||||||||||||
98 | run_single_pma | 1.159 | 1.105 | ||||||||||||||||||||||||||||||||
99 | run_single_cpma | 1.337 | 1.030 | 0.867 | |||||||||||||||||||||||||||||||
100 | run_single_spma | 1.182 | 1.090 |