dtenedor opened a new pull request, #12277:
URL: https://github.com/apache/arrow-rs/pull/12277
# Which issue does this PR close?
None.
# Rationale for this change
The dictionary interner's hash table stores only each value's dictionary
index. That has two costs:
- Every lookup reads the value back from the dictionary to compare it. That
is a second dependent
cache miss after the table entry, and it makes `DictEncoder::put` 35% of
low-cardinality
dictionary writes.
- Every time the table grows, hashbrown re-hashes each value, reading it
back the same way.
High-cardinality columns build a dictionary until it outgrows the
dictionary page size limit, so
growth costs them 7-15% of write time.
# What changes are included in this PR?
- `Storage` gets an associated const, `INLINE_VALUES`, which defaults to
false. The column
dictionary encoder sets it for BOOLEAN, INT32, INT64, FLOAT and DOUBLE.
- For those types, each table entry holds the value's bytes, as a `u64`,
next to its index. Lookups
compare in the table, and growth hashes the entry itself.
- For every other storage, including the Arrow byte array dictionary, each
entry holds the value's
hash. Growth doesn't re-hash, and probes compare hashes before reading the
value.
Dictionaries are built in the same order, so output is byte-identical. Table
entries double in
size, from 8 to 16 bytes, and `estimated_memory_size` reflects that.
# Are these changes tested?
Covered by the existing dictionary and writer tests. Writer output was also
checked to be
byte-identical to main's.
`arrow_writer` bench, Intel Xeon Platinum 8559C, default x86-64 target,
median of 7 alternating
rounds:
| `arrow_writer` bench | main | PR | Speedup |
| :--- | ---: | ---: | ---: |
| `int64_dictionary_1pct_cardinality/default` | 7.656 ms | 6.594 ms | 1.16x |
| `primitive_dictionary_1pct_cardinality/default` | 7.414 ms | 6.366 ms |
1.16x |
| `float64_dictionary_1pct_cardinality/default` | 8.381 ms | 7.336 ms |
1.14x |
| `primitive_non_null/default` | 47.552 ms | 44.591 ms | 1.07x |
| `primitive_non_null/parquet_2` | 62.944 ms | 60.709 ms | 1.04x |
| `primitive/default` | 91.680 ms | 88.799 ms | 1.03x |
| `primitive_dictionary/default` | 14.972 ms | 14.405 ms | 1.04x |
| `int64_dictionary/default` | 11.933 ms | 11.710 ms | 1.02x |
Storing the full hash next to each key, for every type, helps growth but
leaves the dictionary read
on every hit. Keeping fixed-width values in the entry is what speeds up the
low-cardinality cases.
None of the measured inputs got slower. The cost is the table's memory: 8
more bytes per distinct
value.
# Are there any significant user-facing changes?
No. The new const is on the interner's `Storage` trait, which is
crate-private.
# AI usage disclosure
An AI coding agent (Claude Code) generated the code and this description,
and ran the benchmarks and
the output checks. This PR is a draft until the submitter has reviewed it.
This pull request and its description were written by Isaac.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]