Repository navigation
Commit b9e6252
committed
fix: grow the value buffer on a power of two ladder
`ArrowBytesMap::new` starts its value buffer empty and
`ArrowBytesMap::with_capacity` starts it at `INITIAL_BUFFER_CAPACITY`.
`Vec` then doubles from wherever its first allocation landed, so the two
sit on different ladders and can hold the same values at capacities
differing by up to 2x, in either direction depending on the value
lengths. Measured on 500,000 distinct 28 byte values, the lazily grown
map reported 52,494,344 bytes against 45,154,312 for a pre-allocated
one, 16% more for identical contents.
That matters because the ungrouped `COUNT(DISTINCT <string>)`
accumulator is the caller that had a use for the warm up: it builds one
map and grows it to hold every distinct value in the input. Rounding
every buffer growth up to a power of two puts both constructors on one
ladder, so a lazily allocated map is never larger than a pre-allocated
one holding the same values. Growth stays geometric, so appending is
still amortized constant time. `ArrowBytesViewMap` has no such buffer
and is unaffected.
Two new tests cover the ungrouped path, which had none:
`ungrouped_utf8_accumulator_is_never_worse_than_a_pre_allocated_set` and
its `Utf8View` counterpart drive an accumulator to 0 through 500,000
distinct values and assert it is strictly cheaper than a pre-allocated
set at per group cardinalities and exactly equal at ungrouped ones. The
`Utf8` one fails without this change, at 1,000 distinct values, with the
lazy set reporting 110,408 bytes against 96,072. Two map level tests pin
the ladder itself.1 parent 37d3ac2 commit b9e6252
2 files changed
Lines changed: 223 additions & 2 deletions
File tree
- datafusion
- functions-aggregate-common/src/aggregate/count_distinct
- physical-expr-common/src
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
43 | 43 | | |
44 | 44 | | |
45 | 45 | | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
46 | 54 | | |
47 | 55 | | |
48 | 56 | | |
| |||
157 | 165 | | |
158 | 166 | | |
159 | 167 | | |
| 168 | + | |
| 169 | + | |
| 170 | + | |
| 171 | + | |
| 172 | + | |
| 173 | + | |
| 174 | + | |
| 175 | + | |
| 176 | + | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
| 180 | + | |
| 181 | + | |
| 182 | + | |
| 183 | + | |
| 184 | + | |
| 185 | + | |
| 186 | + | |
| 187 | + | |
| 188 | + | |
| 189 | + | |
| 190 | + | |
| 191 | + | |
| 192 | + | |
| 193 | + | |
| 194 | + | |
| 195 | + | |
| 196 | + | |
| 197 | + | |
| 198 | + | |
| 199 | + | |
| 200 | + | |
| 201 | + | |
| 202 | + | |
| 203 | + | |
| 204 | + | |
| 205 | + | |
| 206 | + | |
| 207 | + | |
| 208 | + | |
| 209 | + | |
| 210 | + | |
| 211 | + | |
| 212 | + | |
| 213 | + | |
| 214 | + | |
| 215 | + | |
| 216 | + | |
| 217 | + | |
| 218 | + | |
| 219 | + | |
| 220 | + | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
| 225 | + | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
| 229 | + | |
| 230 | + | |
| 231 | + | |
| 232 | + | |
| 233 | + | |
| 234 | + | |
| 235 | + | |
| 236 | + | |
| 237 | + | |
| 238 | + | |
| 239 | + | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
| 247 | + | |
| 248 | + | |
| 249 | + | |
| 250 | + | |
| 251 | + | |
| 252 | + | |
| 253 | + | |
| 254 | + | |
| 255 | + | |
| 256 | + | |
| 257 | + | |
| 258 | + | |
| 259 | + | |
| 260 | + | |
| 261 | + | |
| 262 | + | |
| 263 | + | |
| 264 | + | |
| 265 | + | |
| 266 | + | |
| 267 | + | |
| 268 | + | |
| 269 | + | |
| 270 | + | |
| 271 | + | |
| 272 | + | |
| 273 | + | |
| 274 | + | |
| 275 | + | |
| 276 | + | |
| 277 | + | |
| 278 | + | |
| 279 | + | |
| 280 | + | |
| 281 | + | |
| 282 | + | |
| 283 | + | |
| 284 | + | |
| 285 | + | |
| 286 | + | |
| 287 | + | |
| 288 | + | |
| 289 | + | |
| 290 | + | |
| 291 | + | |
| 292 | + | |
| 293 | + | |
| 294 | + | |
| 295 | + | |
| 296 | + | |
| 297 | + | |
| 298 | + | |
| 299 | + | |
| 300 | + | |
| 301 | + | |
| 302 | + | |
| 303 | + | |
| 304 | + | |
| 305 | + | |
| 306 | + | |
| 307 | + | |
| 308 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
259 | 259 | | |
260 | 260 | | |
261 | 261 | | |
| 262 | + | |
| 263 | + | |
| 264 | + | |
| 265 | + | |
| 266 | + | |
| 267 | + | |
| 268 | + | |
| 269 | + | |
| 270 | + | |
| 271 | + | |
| 272 | + | |
| 273 | + | |
| 274 | + | |
| 275 | + | |
| 276 | + | |
| 277 | + | |
| 278 | + | |
| 279 | + | |
| 280 | + | |
| 281 | + | |
| 282 | + | |
| 283 | + | |
262 | 284 | | |
263 | 285 | | |
264 | 286 | | |
| |||
471 | 493 | | |
472 | 494 | | |
473 | 495 | | |
474 | | - | |
| 496 | + | |
475 | 497 | | |
476 | 498 | | |
477 | 499 | | |
| |||
509 | 531 | | |
510 | 532 | | |
511 | 533 | | |
512 | | - | |
| 534 | + | |
513 | 535 | | |
514 | 536 | | |
515 | 537 | | |
| |||
826 | 848 | | |
827 | 849 | | |
828 | 850 | | |
| 851 | + | |
| 852 | + | |
| 853 | + | |
| 854 | + | |
| 855 | + | |
| 856 | + | |
| 857 | + | |
| 858 | + | |
| 859 | + | |
| 860 | + | |
| 861 | + | |
| 862 | + | |
| 863 | + | |
| 864 | + | |
| 865 | + | |
| 866 | + | |
| 867 | + | |
| 868 | + | |
| 869 | + | |
| 870 | + | |
| 871 | + | |
| 872 | + | |
| 873 | + | |
| 874 | + | |
| 875 | + | |
| 876 | + | |
| 877 | + | |
| 878 | + | |
| 879 | + | |
| 880 | + | |
| 881 | + | |
| 882 | + | |
| 883 | + | |
| 884 | + | |
| 885 | + | |
| 886 | + | |
| 887 | + | |
| 888 | + | |
| 889 | + | |
| 890 | + | |
| 891 | + | |
| 892 | + | |
| 893 | + | |
| 894 | + | |
| 895 | + | |
| 896 | + | |
| 897 | + | |
| 898 | + | |
| 899 | + | |
| 900 | + | |
829 | 901 | | |
830 | 902 | | |
831 | 903 | | |
| |||
0 commit comments