GH-34569: [C++] Diffing of Run-End Encoded arrays by felipecrv · Pull Request #35003 · apache/arrow

felipecrv · 2023-04-10T14:12:25Z

What changes are included in this PR?

Ability to diff run-end encoded arrays without expanding them first. This is useful for debugging and understanding of unit test failures.

Many successive random accesses to REE arrays by logical indices incur many successive binary searches on the run-ends array to find the physical index of the values array, so this PR implements a few interesting optimizations -- the most complicated one is encapsulated in a new utility available via ree_util.h as there are many potential uses for it other than diffing.

+-------------+---------------------------+----------------------------------------------------+
|             |                                  Optimizations                                 |
+-------------+---------------------------+-----------------------+----------------------------+
| # bsearches | Null checks on Comparator | RunLengthOfEqualsFrom | Cached FindPhysicalIndex() |
+-------------+---------------------------+----------------------+-----------------------------+
|    3798     |                           |                      |                             |
+-------------+---------------------------+----------------------+-----------------------------+
|    1914     |           X               |                      |                             |
+-------------+---------------------------+----------------------+-----------------------------+
|     180     |           X               |        X             |                             |
+-------------+---------------------------+----------------------+-----------------------------+
|     153     |           X               |                      |           X                 |
+-------------+---------------------------+----------------------+-----------------------------+
|      75     |           X               |        X             |           X                 |
+-------------+---------------------------+----------------------+-----------------------------+

Are these changes tested?

Yes. By existing and newly added REE-specific tests.

Are there any user-facing changes?

No.

Closes: [C++] Diffing of Run-End Encoded arrays #34569

github-actions · 2023-04-10T14:12:51Z

Closes: [C++] Diffing of Run-End Encoded arrays #34569

…mparator This will allow different comparator to initialize and keep *mutable state* between the calls to Equals. This can also be done with mutable lambdas, but I believe this way is much readable and safer even though it's a bit verbose.

...to count number of binary searches.

This approximately halves the number of binary searches performed during diffing to resolve physical index on REE arrays. The number goes from 3798 to 1914 (~= 1899 = 3798/2).

…of equal values

… buffers

…EE arrays This makes the number of binary searches to find physical indices go from 1914 to 180 during the execution of diff tests on REEs. I took care of not including the newly added test in this accounting.

When new queries for the physical index of a logical index come in, binary search is performed again but the first candidate checked is the result of the previous search (cached physical index) instead of the midpoint of the run-ends array. If that test fails, FindPhysicalIndex() is called with one of the partitions defined by the cached index. If the queried logical indices follow an increasing or decreasing pattern, this first test is much more effective in (1) finding the answer right away (close logical indices belong to the same runs) or (2) discarding many more candidates than probing the midpoint would. The most adversarial case -- alternating between 0 and length-1 queries -- only adds one extra binary search probe when compared to always starting binary search from the midpoint without any of these optimizations. This optimization further reduces the number of binary searches performed during arrow-diff-test from 180 to 75. Which is a log2(n) speed-up (180/log2(180) ~= 79.81). Without the RunLengthOfEqualsFrom optimization, this optimization alone reduces the number of binary searches from 1914 to 153. +-------------+---------------------------+----------------------------------------------------+ | | Optimizations | +-------------+---------------------------+-----------------------+----------------------------+ | # bsearches | Null checks on Comparator | RunLengthOfEqualsFrom | Cached FindPhysicalIndex() | +-------------+---------------------------+----------------------+-----------------------------+ | 3798 | | | | +-------------+---------------------------+----------------------+-----------------------------+ | 1914 | X | | | +-------------+---------------------------+----------------------+-----------------------------+ | 180 | X | X | | +-------------+---------------------------+----------------------+-----------------------------+ | 153 | X | | X | +-------------+---------------------------+----------------------+-----------------------------+ | 75 | X | X | X | +-------------+---------------------------+----------------------+-----------------------------+

bkietz

This approach looks good to me, just a few style nits

…n diff.cc

bkietz

LGTM

conbench-apache-arrow · 2023-10-27T18:54:34Z

After merging your PR, Conbench analyzed the 5 benchmarking runs that have been run so far on merge-commit fcbcb7d.

There was 1 benchmark result indicating a performance regression:

Commit Run on ursa-i9-9960x at 2023-10-27 01:21:47Z
- tpch (R) with engine=arrow, format=native, language=R, memory_map=False, query_id=TPCH-20, scale_factor=1

The full Conbench report has more details.

### What changes are included in this PR? Ability to diff run-end encoded arrays without expanding them first. This is useful for debugging and understanding of unit test failures. Many successive random accesses to REE arrays by logical indices incur many successive binary searches on the run-ends array to find the physical index of the values array, so this PR implements a few interesting optimizations -- the most complicated one is encapsulated in a new utility available via `ree_util.h` as there are many potential uses for it other than diffing. +-------------+---------------------------+----------------------------------------------------+ | | Optimizations | +-------------+---------------------------+-----------------------+----------------------------+ | # bsearches | Null checks on Comparator | RunLengthOfEqualsFrom | Cached FindPhysicalIndex() | +-------------+---------------------------+----------------------+-----------------------------+ | 3798 | | | | +-------------+---------------------------+----------------------+-----------------------------+ | 1914 | X | | | +-------------+---------------------------+----------------------+-----------------------------+ | 180 | X | X | | +-------------+---------------------------+----------------------+-----------------------------+ | 153 | X | | X | +-------------+---------------------------+----------------------+-----------------------------+ | 75 | X | X | X | +-------------+---------------------------+----------------------+-----------------------------+ ### Are these changes tested? Yes. By existing and newly added REE-specific tests. ### Are there any user-facing changes? No. * Closes: apache#34569 Authored-by: Felipe Oliveira Carvalho <[email protected]> Signed-off-by: Benjamin Kietzman <[email protected]>

github-actions Bot added Component: C++ awaiting review labels Apr 10, 2023

felipecrv force-pushed the diff_ree branch from 9c66b7b to 734b06e Compare October 22, 2023 01:09

felipecrv added 2 commits October 23, 2023 21:36

Implement diffing of Run-End Encoded arrays

9f83f96

felipecrv force-pushed the diff_ree branch from 734b06e to 2405ba0 Compare October 24, 2023 02:59

felipecrv marked this pull request as ready for review October 24, 2023 03:06

felipecrv requested review from bkietz and mapleFU October 24, 2023 03:06

felipecrv added 8 commits October 24, 2023 00:15

diff.cc: Add TODO note about null comparisons and instrumentation

0c40f4a

...to count number of binary searches.

diff.cc: Remove the unsafe creation of value comparators

cdbe50e

diff.cc: Move validity comparison to the comparator

54b4c54

This approximately halves the number of binary searches performed during diffing to resolve physical index on REE arrays. The number goes from 3798 to 1914 (~= 1899 = 3798/2).

diff.cc: Delegate to the ValueComparator the ability to extend a run …

f8fdf60

…of equal values

diff.cc: Prepare REEValueComparator for direct access to the run-ends…

2c93b3f

… buffers

diff.cc: Write a custom implementation of RunLengthOfEqualsFrom for R…

a9db49f

…EE arrays This makes the number of binary searches to find physical indices go from 1914 to 180 during the execution of diff tests on REEs. I took care of not including the newly added test in this accounting.

ree_util: Introduce the PhysicalIndexFinder class and use it in diff.cc

1151b38

felipecrv force-pushed the diff_ree branch from 2405ba0 to 1151b38 Compare October 24, 2023 03:15

fixup! diff.cc: Remove the unsafe creation of value comparators

00c31ec

bkietz requested changes Oct 24, 2023

View reviewed changes

github-actions Bot added awaiting changes and removed awaiting review labels Oct 24, 2023

felipecrv added 3 commits October 24, 2023 19:02

fixup! ree_util: Introduce the PhysicalIndexFinder class and use it i…

a5a7514

…n diff.cc

Simplify the ValueComparatorFactory class

0ee60bb

Remove the rather confusing ValidityIfEquals function

4894b19

felipecrv requested a review from bkietz October 24, 2023 22:03

github-actions Bot added awaiting change review and removed awaiting changes labels Oct 24, 2023

github-actions Bot added the awaiting changes label Oct 25, 2023

Initialize everything on Diff()

9e43e44

github-actions Bot added awaiting change review and removed awaiting changes labels Oct 26, 2023

Use clever branchless code to increment physical run indices

4c1eb37

github-actions Bot added awaiting change review and removed awaiting changes labels Oct 26, 2023

bkietz approved these changes Oct 26, 2023

View reviewed changes

bkietz merged commit fcbcb7d into apache:main Oct 26, 2023

bkietz removed the awaiting change review label Oct 26, 2023

github-actions Bot added the awaiting merge label Oct 26, 2023

felipecrv deleted the diff_ree branch October 26, 2023 21:42

Navigation Menu

Repository navigation

GH-34569: [C++] Diffing of Run-End Encoded arrays - #35003

GH-34569: [C++] Diffing of Run-End Encoded arrays#35003
bkietz merged 16 commits into
apache:mainfrom
felipecrv:diff_ree

felipecrv commented Apr 10, 2023 •

edited

Loading

Uh oh!

github-actions Bot commented Apr 10, 2023

Uh oh!

bkietz left a comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

bkietz left a comment

Uh oh!

conbench-apache-arrow Bot commented Oct 27, 2023

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Conversation

felipecrv commented Apr 10, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

What changes are included in this PR?

Are these changes tested?

Are there any user-facing changes?

Uh oh!

github-actions Bot commented Apr 10, 2023

Uh oh!

bkietz left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

bkietz left a comment

Choose a reason for hiding this comment

Uh oh!

conbench-apache-arrow Bot commented Oct 27, 2023

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

felipecrv commented Apr 10, 2023 •

edited

Loading