dtenedor opened a new pull request, #12282:
URL: https://github.com/apache/arrow-rs/pull/12282

   # Which issue does this PR close?
   
   None.
   
   # Rationale for this change
   
   When the `ArrowWriter` writes an Arrow dictionary array of strings or 
binary, it updates the page
   statistics by comparing every row's value with the running min and max: two 
`memcmp` calls per
   row. With the dictionary cache from #11982, interning is already one lookup 
per row, so these
   comparisons are now most of the cost. In 
`string_dictionary_low_cardinality_20`, a dictionary of 20
   values, `update_statistics` is 22-24% and `memcmp` 24-27% of the write.
   
   A batch of rows can only reference values from the dictionary, so its min 
and max are the min and
   max of the values it references, however many rows reference each one.
   
   # What changes are included in this PR?
   
   `update_dictionary_statistics` marks the keys the batch's rows use, then 
compares each referenced
   dictionary value once. It is used when the dictionary has no more values 
than the batch has rows:
   then some rows must repeat a value, and the pass over the dictionary's flags 
is no longer than the
   batch.
   
   The per-row computation is kept for:
   - larger dictionaries, where the rows of a batch are mostly distinct anyway
   - decimals: values that are numerically equal can have different bytes, and 
which one becomes the
     statistic depends on row order
   - geospatial statistics
   - a key outside the dictionary, which reads as an empty value
   
   The statistics, and so the file, are unchanged.
   
   # Are these changes tested?
   
   A new test writes dictionary arrays of 1 to 100,000 values, with null keys 
and null values, and
   checks that each writes the same file bytes as its values cast to `Utf8`. It 
passes before and after
   this change. Output was also checked to be byte-identical to main's for 288 
more dictionary array
   files:
   - `Int8`, `Int16` and `Int32` keys
   - `Utf8` and `Binary` values, with duplicate and empty values
   - 1 to 20,000 dictionary values
   - small batch and page sizes, and dictionary encoding turned off
   
   `arrow_writer` bench, Intel Xeon Platinum 8559C, default x86-64 target, 
median of 5 alternating
   rounds:
   
   | `arrow_writer` bench | main | PR | Speedup |
   | :--- | ---: | ---: | ---: |
   | `string_dictionary_low_cardinality_20/default` | 8.254 ms | 3.296 ms | 
2.50x |
   | `string_dictionary_low_cardinality_100/default` | 8.245 ms | 3.725 ms | 
2.21x |
   | `string_dictionary_low_cardinality_400/default` | 8.465 ms | 5.188 ms | 
1.63x |
   | the three above with `parquet_2` | | | 2.50x / 2.20x / 1.65x |
   | `string_dictionary_1pct_cardinality` (10K values, per-row path) | | | 
1.05-1.06x |
   | `string_dictionary` (per-row path) | | | 0.98-1.01x |
   | `string`, `string_non_null`, `short_string_non_null` (not dictionary 
arrays) | | | 0.98-1.01x |
   
   An earlier version used the shortcut for dictionaries up to 16 times the 
batch. It made
   `string_dictionary_1pct_cardinality` 0.61x, because its batches reference 
nearly 1,024 distinct
   values out of 10,000, and every batch scanned all 10,000 flags. Collecting 
keys as they are first
   seen instead brought that case to 0.87x, but lowered the low-cardinality 
gains, to 2.13x for 20
   values.
   Limiting the shortcut to dictionaries no larger than the batch avoids both.
   
   None of the measured inputs got slower. The 0.98x results are on paths this 
change doesn't affect.
   Not measured on aarch64.
   
   # Are there any significant user-facing changes?
   
   No.
   
   # AI usage disclosure
   
   An AI coding agent (Claude Code) generated the code, the test 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