You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@parquet.apache.org by "iemejia (via GitHub)" <gi...@apache.org> on 2026/05/01 22:19:44 UTC
[PR] GH-3522: Optimize IntList.size() from O(slabs) to O(1) with running counter [parquet-java]
iemejia opened a new pull request, #3533:
URL: https://github.com/apache/parquet-java/pull/3533
## Summary
- Replace `IntList.size()` slab-iteration with a simple `totalSize` counter incremented on each `add()`
- Eliminates O(slabs) overhead from dictionary encoding hot paths where `size()` is called frequently
## Details
`IntList.size()` was iterating over all slabs to sum their lengths on every call. For delta encoding writers that check size thresholds frequently, this becomes O(slabs) per check. With a running counter it's O(1).
The improvement is primarily relevant for large row groups where the number of slabs grows.
All 576 parquet-column tests pass.
--
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: issues-unsubscribe@parquet.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org
Re: [PR] GH-3522: Optimize IntList.size() from O(slabs) to O(1) with running counter [parquet-java]
Posted by "Fokko (via GitHub)" <gi...@apache.org>.
Fokko commented on code in PR #3533:
URL: https://github.com/apache/parquet-java/pull/3533#discussion_r3197532011
##########
parquet-column/src/main/java/org/apache/parquet/column/values/dictionary/IntList.java:
##########
@@ -150,11 +152,6 @@ public IntIterator iterator() {
* @return the current size of the list
*/
public int size() {
- int size = currentSlabPos;
- for (int[] slab : slabs) {
- size += slab.length;
- }
Review Comment:
I don't think this change is correct. We're returning the slab length, and this one can grow as well (double until MAX_SLAB_SIZE)
--
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: issues-unsubscribe@parquet.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org
Re: [PR] GH-3522: Optimize IntList.size() from O(slabs) to O(1) with running counter [parquet-java]
Posted by "iemejia (via GitHub)" <gi...@apache.org>.
iemejia closed pull request #3533: GH-3522: Optimize IntList.size() from O(slabs) to O(1) with running counter
URL: https://github.com/apache/parquet-java/pull/3533
--
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: issues-unsubscribe@parquet.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org
Re: [PR] GH-3522: Optimize IntList.size() from O(slabs) to O(1) with running counter [parquet-java]
Posted by "iemejia (via GitHub)" <gi...@apache.org>.
iemejia commented on PR #3533:
URL: https://github.com/apache/parquet-java/pull/3533#issuecomment-4472735181
Closing in favor of #3566.
I initially submitted a series of small, focused PRs thinking they'd be easier to review. In practice the sheer number (~16 PRs, with more pending) made things harder to follow — even for me. I've regrouped the changes by encoding type / performance area so that each PR is self-contained with its own benchmarks and test coverage, which should make review and performance analysis much more straightforward.
Apologies for the churn. If you've been reviewing this PR, please continue the discussion on #3566 which supersedes it. Thank you.
--
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: issues-unsubscribe@parquet.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org
Re: [PR] GH-3522: Optimize IntList.size() from O(slabs) to O(1) with running counter [parquet-java]
Posted by "Fokko (via GitHub)" <gi...@apache.org>.
Fokko commented on code in PR #3533:
URL: https://github.com/apache/parquet-java/pull/3533#discussion_r3197516077
##########
parquet-column/src/main/java/org/apache/parquet/column/values/dictionary/IntList.java:
##########
Review Comment:
Should we also set `totalSize` to 0 here?
--
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: issues-unsubscribe@parquet.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org
Re: [PR] GH-3522: Optimize IntList.size() from O(slabs) to O(1) with running counter [parquet-java]
Posted by "Fokko (via GitHub)" <gi...@apache.org>.
Fokko commented on code in PR #3533:
URL: https://github.com/apache/parquet-java/pull/3533#discussion_r3197517836
##########
parquet-column/src/main/java/org/apache/parquet/column/values/dictionary/IntList.java:
##########
@@ -129,6 +130,7 @@ public void add(int i) {
currentSlab[currentSlabPos] = i;
++currentSlabPos;
+ ++totalSize;
Review Comment:
Looking at the code, totalSize will always be the same as currentSlabSize
--
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: issues-unsubscribe@parquet.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org