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]

Reply via email to