You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "adamreeve (via GitHub)" <gi...@apache.org> on 2025/01/08 03:46:08 UTC
[PR] [Parquet] Fix slow dictionary encoding of NaN float values [arrow-rs]
adamreeve opened a new pull request, #6953:
URL: https://github.com/apache/arrow-rs/pull/6953
# Which issue does this PR close?
Closes #6952
# Rationale for this change
This treats NaNs as equal to other NaNs of the same type for the purpose of dictionary encoding them when writing f32 or f64 Parquet physical values.
# What changes are included in this PR?
* Introduces a new `Intern` trait to define equality behaviour for interning, replacing the use of `PartialEq`.
* Adds a benchmark for writing floating point values with NaNs to Parquet.
# Are there any user-facing changes?
* Users should see improved performance when writing floating point data with many NaNs to Parquet
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Parquet] Fix slow dictionary encoding of NaN float values [arrow-rs]
Posted by "adamreeve (via GitHub)" <gi...@apache.org>.
adamreeve commented on PR #6953:
URL: https://github.com/apache/arrow-rs/pull/6953#issuecomment-2576679001
Benchmark results from the new benchmarks before changing the interning behaviour:
```
write_batch primitive/4096 values float with NaNs
time: [5.6968 ms 5.7060 ms 5.7141 ms]
thrpt: [9.6186 MiB/s 9.6324 MiB/s 9.6479 MiB/s]
Found 8 outliers among 100 measurements (8.00%)
3 (3.00%) low severe
4 (4.00%) low mild
1 (1.00%) high mild
write_batch primitive/4096 values float with no NaNs
time: [383.44 µs 383.65 µs 383.85 µs]
thrpt: [143.18 MiB/s 143.26 MiB/s 143.34 MiB/s]
Found 1 outliers among 100 measurements (1.00%)
1 (1.00%) high mild
```
This shows that writing with 50% NaN values is much slower than with no NaNs.
After the change, performance with NaNs is very similar to without NaNs:
```
write_batch primitive/4096 values float with NaNs
time: [406.40 µs 406.63 µs 406.88 µs]
thrpt: [135.08 MiB/s 135.16 MiB/s 135.24 MiB/s]
change:
time: [-92.875% -92.861% -92.845%] (p = 0.00 < 0.05)
thrpt: [+1297.6% +1300.7% +1303.5%]
Performance has improved.
Found 3 outliers among 100 measurements (3.00%)
1 (1.00%) high mild
2 (2.00%) high severe
write_batch primitive/4096 values float with no NaNs
time: [382.52 µs 384.16 µs 385.50 µs]
thrpt: [142.58 MiB/s 143.07 MiB/s 143.68 MiB/s]
change:
time: [+0.1803% +0.3520% +0.5192%] (p = 0.00 < 0.05)
thrpt: [-0.5165% -0.3507% -0.1799%]
Change within noise threshold.
Found 3 outliers among 100 measurements (3.00%)
3 (3.00%) low severe
```
(I removed the `4096 values float with no NaNs` benchmark from this PR after running these benchmarks as I don't think there's a lot of value in keeping it)
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Parquet] Improve speed of dictionary encoding NaN float values [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6953:
URL: https://github.com/apache/arrow-rs/pull/6953#issuecomment-2583852964
FYI @etseidl
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Parquet] Fix slow dictionary encoding of NaN float values [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6953:
URL: https://github.com/apache/arrow-rs/pull/6953#issuecomment-2578805209
> > Thank you @adamreeve -- is there any chance you could break out the benchmark into its own PR so it is easier to compare the before/after performance of this change?
>
> Sure, I've made #6955 to just add the benchmark and test, I'll make this PR a draft and rebase it once that is merged.
THanks! I have merged #6955 -- I'll run the benchmarks when this one is rebased
THanks again @adamreeve
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Parquet] Improve speed of dictionary encoding NaN float values [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold commented on PR #6953:
URL: https://github.com/apache/arrow-rs/pull/6953#issuecomment-2590154743
> I feel like there must be semantic difference between comparing Nans using .eq and comparing the bit patterns
We generally use floating point total ordering, as described [here](https://docs.rs/arrow-ord/latest/arrow_ord/cmp/fn.gt.html). This is equivalent to byte-ordering when it comes to NaNs. As such IMO this is a bug fix.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Parquet] Fix slow dictionary encoding of NaN float values [arrow-rs]
Posted by "adamreeve (via GitHub)" <gi...@apache.org>.
adamreeve commented on code in PR #6953:
URL: https://github.com/apache/arrow-rs/pull/6953#discussion_r1906448875
##########
parquet/src/util/interner.rs:
##########
@@ -66,7 +70,7 @@ impl<S: Storage> Interner<S> {
.dedup
.entry(
hash,
- |index| value == self.storage.get(*index),
+ |index| value.eq(self.storage.get(*index)),
Review Comment:
Hmm, after opening this PR I realised a simpler approach would be to just compare the values by their byte representation here:
```rust
|index| value.as_bytes() == self.storage.get(*index).as_bytes()
```
I will check what effect that has on performance.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Parquet] Improve speed of dictionary encoding NaN float values [arrow-rs]
Posted by "adamreeve (via GitHub)" <gi...@apache.org>.
adamreeve commented on PR #6953:
URL: https://github.com/apache/arrow-rs/pull/6953#issuecomment-2586516918
> I think technically speaking this could be a behavior change as previously different Nan representations would be collapsed into a single dictionary entry, but now they will use different entries.
I don't think this is true as the `NaN == NaN` test being false would have caused all NaN values to get separate entries in the dictionary, so behaviour shouldn't have changed. But it does differ from C++ Arrow which does collapse all NaNs to a single entry.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Parquet] Improve speed of dictionary encoding NaN float values [arrow-rs]
Posted by "tustvold (via GitHub)" <gi...@apache.org>.
tustvold merged PR #6953:
URL: https://github.com/apache/arrow-rs/pull/6953
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Parquet] Fix slow dictionary encoding of NaN float values [arrow-rs]
Posted by "adamreeve (via GitHub)" <gi...@apache.org>.
adamreeve commented on PR #6953:
URL: https://github.com/apache/arrow-rs/pull/6953#issuecomment-2578662372
> Thank you @adamreeve -- is there any chance you could break out the benchmark into its own PR so it is easier to compare the before/after performance of this change?
Sure, I've made #6955 to just add the benchmark and test, I'll make this PR a draft and rebase it once that is merged.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Parquet] Fix slow dictionary encoding of NaN float values [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6953:
URL: https://github.com/apache/arrow-rs/pull/6953#issuecomment-2583809609
Running benchmarks now
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Parquet] Improve speed of dictionary encoding NaN float values [arrow-rs]
Posted by "bkirwi (via GitHub)" <gi...@apache.org>.
bkirwi commented on PR #6953:
URL: https://github.com/apache/arrow-rs/pull/6953#issuecomment-2941133915
In particular, this also fixes behaviour for negative and positive zero in floating point. Since these _do_ compare equal but have different bit representations, IIUC the old code would combine them into a single dictionary entry... but _only if they happened to hash to the same bucket. Since the hash function is randomly initialized, this was very rare, but I have observed it. (Normally the bits will hash to different buckets and they'll have separate entries in the dictionary.)
Comparing the bit representation solves this issue as well, since those are not bitwise identical and thus will reliably end up with different dict entries.
Mentioning here in case anyone else is searching for this issue. Thanks for the fix!
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Parquet] Fix slow dictionary encoding of NaN float values [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6953:
URL: https://github.com/apache/arrow-rs/pull/6953#issuecomment-2577749607
Thank you @adamreeve -- is there any chance you could break out the benchmark into its own PR so it is easier to compare the before/after performance of this change?
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Parquet] Fix slow dictionary encoding of NaN float values [arrow-rs]
Posted by "adamreeve (via GitHub)" <gi...@apache.org>.
adamreeve commented on PR #6953:
URL: https://github.com/apache/arrow-rs/pull/6953#issuecomment-2578887593
OK I've rebased this now and switched to comparing byte representations for all types rather than needing a new trait, which is a simpler solution and is consistent with how values are hashed. The performance was very similar between the two approaches on my machine.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [Parquet] Improve speed of dictionary encoding NaN float values [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6953:
URL: https://github.com/apache/arrow-rs/pull/6953#issuecomment-2590103438
> > I think technically speaking this could be a behavior change as previously different Nan representations would be collapsed into a single dictionary entry, but now they will use different entries.
>
> I don't think this is true as the `NaN == NaN` test being false would have caused all NaN values to get separate entries in the dictionary, so behaviour shouldn't have changed. But it does differ from C++ Arrow which does collapse all NaNs to a single entry.
I feel like there must be semantic difference between comparing Nans using .eq and comparing the bit patterns 🤔
However, I suppose at this point it is just an intellectual execise 🤷
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org