GH-26648: [C++] Optimize union equality comparison

[mcshawn10]

Rationale for this change

#26648 proposes an optimization in checking sparse array equality by detecting contiguous runs, this PR implements that change

What changes are included in this PR?

previously, sparse array comparison was checked one by one, in this change, contiguous runs are detected and compared by checking equality of current and previous child_ids

Are these changes tested?

already covered by existing unit tests

Are there any user-facing changes?

no

• GitHub Issue: [C++] Optimize union equality comparison #26648

[github-actions]

⚠️ GitHub issue #26648 has been automatically assigned in GitHub to PR creator.

[mapleFU]

Thanks! By the way is there any benchmark result for this pr?

[mcshawn10]

Thanks! By the way is there any benchmark result for this pr?

still figuring that part out! 😅

[mcshawn10]

overall.json

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Non-regressions: (6)
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
                              benchmark          baseline          contender  change %                                                                                                                                                                                                   counters
    ArrayRangeEqualsSparseUnion/65536/0 47.119M items/sec 105.533M items/sec   123.973      {'family_index': 0, 'per_family_instance_index': 5, 'run_name': 'ArrayRangeEqualsSparseUnion/65536/0', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 506, 'null_percent': 0.0}
  ArrayRangeEqualsSparseUnion/65536/100 29.924M items/sec  57.186M items/sec    91.101    {'family_index': 0, 'per_family_instance_index': 1, 'run_name': 'ArrayRangeEqualsSparseUnion/65536/100', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 326, 'null_percent': 1.0}
ArrayRangeEqualsSparseUnion/65536/10000 30.820M items/sec  57.887M items/sec    87.826 {'family_index': 0, 'per_family_instance_index': 0, 'run_name': 'ArrayRangeEqualsSparseUnion/65536/10000', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 325, 'null_percent': 0.01}
   ArrayRangeEqualsSparseUnion/65536/10 30.616M items/sec  56.025M items/sec    82.990    {'family_index': 0, 'per_family_instance_index': 2, 'run_name': 'ArrayRangeEqualsSparseUnion/65536/10', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 331, 'null_percent': 10.0}
    ArrayRangeEqualsSparseUnion/65536/1 46.987M items/sec  82.663M items/sec    75.926    {'family_index': 0, 'per_family_instance_index': 4, 'run_name': 'ArrayRangeEqualsSparseUnion/65536/1', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 488, 'null_percent': 100.0}
    ArrayRangeEqualsSparseUnion/65536/2 31.326M items/sec  54.119M items/sec    72.760     {'family_index': 0, 'per_family_instance_index': 3, 'run_name': 'ArrayRangeEqualsSparseUnion/65536/2', 'repetitions': 1, 'repetition_index': 0, 'threads': 1, 'iterations': 340, 'null_percent': 50.0}

[pitrou]

Thanks a lot for your PR @mcshawn10 . This looks mostly good, here are two minor suggestions.

[pitrou]

We should probably only do this final comparison if result_ is still true.

[pitrou]

Can break just as above.

[mcshawn10]

thank you for the feedback! just implemented the suggestions

[pitrou]

It turns out that we didn't have any proper tests for sparse union comparison, so I added one.

[conbench-apache-arrow]

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

There were 8 benchmark results with an error:

• Commit Run on arm64-t4g-2xlarge-linux at 2025-02-04 19:22:05Z
  • tpch (R) with engine=arrow, format=native, language=R, memory_map=False, query_id=TPCH-03, scale_factor=1
  • tpch (R) with engine=arrow, format=parquet, language=R, memory_map=False, query_id=TPCH-03, scale_factor=1
• and 6 more (see the report linked below)

There were no benchmark performance regressions. 🎉

The full Conbench report has more details. It also includes information about 1 possible false positive for unstable benchmarks that are known to sometimes produce them.