You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "fallintoplace (via GitHub)" <gi...@apache.org> on 2026/08/11 20:59:43 UTC

[PR] perf(arrow/array): compare binary values by valid runs [arrow-go]

fallintoplace opened a new pull request, #1174:
URL: https://github.com/apache/arrow-go/pull/1174

   ### Rationale for this change
   
   Binary and string equality currently compares every non-null value separately. This repeats offset lookups and small byte or string comparisons even when a long valid run is stored contiguously.
   
   ### What changes are included in this PR?
   
   - Walk contiguous valid runs for Binary, String, LargeBinary, and LargeString.
   - Compare each run payload in one operation.
   - Verify every value length so equal concatenated bytes with different boundaries still compare unequal.
   - Keep null payloads ignored.
   - Sample validity fragmentation and retain the scalar path for many tiny runs.
   - Add benchmarks and tests for offsets, null patterns, mismatches, and value boundaries.
   
   Apple M1 Pro results for 65,536 values of 32 bytes with `-cpu=1`:
   
   | Case | Before | After | Speedup |
   | --- | ---: | ---: | ---: |
   | Binary equal | 644 us | 360 us | 1.79x |
   | Binary 10% null | 582 us | 439 us | 1.33x |
   | Binary mismatch last | 648 us | 350 us | 1.85x |
   | Binary different length | 453 us | 262 us | 1.73x |
   | String equal | 633 us | 390 us | 1.62x |
   | String 10% null | 604 us | 496 us | 1.22x |
   | String mismatch last | 664 us | 406 us | 1.64x |
   | String different length | 426 us | 235 us | 1.81x |
   
   The alternating 50% null case selects the scalar path and remains neutral. All benchmark cases stay at zero allocations.
   
   ### Are these changes tested?
   
   Yes.
   
   - `go test ./arrow/...`
   - `go test -race ./arrow/array`
   - `go vet -composites=false ./arrow/array`
   - Cross-compiled array tests for linux/amd64 and linux/s390x.
   
   ### Are there any user-facing changes?
   
   No.


-- 
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] perf(arrow/array): compare binary values by valid runs [arrow-go]

Posted by "zeroshade (via GitHub)" <gi...@apache.org>.
zeroshade commented on code in PR #1174:
URL: https://github.com/apache/arrow-go/pull/1174#discussion_r3808088171


##########
arrow/array/binary.go:
##########
@@ -418,17 +425,117 @@ func (a *LargeBinary) ValidateFull() error {
 }
 
 func arrayEqualLargeBinary(left, right *LargeBinary) bool {
-	for i := 0; i < left.Len(); i++ {
-		if left.IsNull(i) {
-			continue
+	if useScalarVariableWidthEquality(left) {
+		for i := range left.Len() {
+			if !left.IsNull(i) && !bytes.Equal(left.Value(i), right.Value(i)) {
+				return false
+			}
+		}
+		return true
+	}
+	return arrayEqualVariableWidth(
+		left.valueOffsets, right.valueOffsets,
+		left.valueBytes, right.valueBytes,
+		left.Offset(), right.Offset(), left.Len(),
+		left.NullN(), left.NullBitmapBytes(),
+		bytes.Equal,
+	)
+}
+
+type binaryOffset interface {
+	~int32 | ~int64
+}
+
+func useScalarVariableWidthEquality(values arrow.Array) bool {
+	if values.NullN() == 0 {
+		return false
+	}
+
+	// Very short validity runs cost more to set up than direct value comparisons.

Review Comment:
   The sampling heuristic introduces a substantial regression for short arrays with fragmented validity because it constructs and advances a run reader before ultimately selecting the original scalar loop.
   
   On Apple M4, alternating-null String arrays measured:
   
   | Length | Merge base | Current | Regression |
   |---:|---:|---:|---:|
   | 4 | ~27 ns | ~68 ns | 2.5× |
   | 8 | ~42 ns | ~100 ns | 2.4× |
   | 16 | ~74 ns | ~115 ns | 55% |
   | 32 | ~147 ns | ~187 ns | 27% |
   | 64 | ~282 ns | ~315 ns | 11% |
   
   The submitted benchmark only uses 65,536-element arrays, so it cannot expose this fixed-cost regression. Please add a cheap length cutoff before sampling and include short-array cases in the benchmark matrix. A performance change should not make these common small-array comparisons materially slower.



##########
arrow/array/binary.go:
##########
@@ -418,17 +425,117 @@ func (a *LargeBinary) ValidateFull() error {
 }
 
 func arrayEqualLargeBinary(left, right *LargeBinary) bool {
-	for i := 0; i < left.Len(); i++ {
-		if left.IsNull(i) {
-			continue
+	if useScalarVariableWidthEquality(left) {
+		for i := range left.Len() {
+			if !left.IsNull(i) && !bytes.Equal(left.Value(i), right.Value(i)) {
+				return false
+			}
+		}
+		return true
+	}
+	return arrayEqualVariableWidth(
+		left.valueOffsets, right.valueOffsets,
+		left.valueBytes, right.valueBytes,
+		left.Offset(), right.Offset(), left.Len(),
+		left.NullN(), left.NullBitmapBytes(),
+		bytes.Equal,
+	)
+}
+
+type binaryOffset interface {
+	~int32 | ~int64
+}
+
+func useScalarVariableWidthEquality(values arrow.Array) bool {
+	if values.NullN() == 0 {
+		return false
+	}
+
+	// Very short validity runs cost more to set up than direct value comparisons.
+	// Sample a few runs and retain the scalar path when they average under four values.
+	const (
+		sampleRuns          = 8
+		minAverageRunLength = 4
+	)
+	runs := bitutils.NewSetBitRunReader(

Review Comment:
   **Blocking:** `NullN() > 0` does not guarantee that a validity bitmap is present. Malformed IPC or C Data can supply a nonzero declared null count with an empty validity buffer.
   
   This unconditionally constructs a run reader over that empty slice. I reproduced equality on two eight-element Binary arrays with `nullCount=1` and an empty validity buffer:
   
   - merge base: returns normally
   - this PR: panics in `baseSetBitRunReader.loadPartial`
   
   An independent end-to-end IPC probe reproduced the same panic after changing only the serialized `null_count` while leaving the validity buffer absent.
   
   Please check `len(values.NullBitmapBytes())` before constructing the reader and retain the scalar fallback when it is empty. Add a regression test confirming equality does not panic on this malformed-input case.



-- 
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] perf(arrow/array): compare binary values by valid runs [arrow-go]

Posted by "zeroshade (via GitHub)" <gi...@apache.org>.
zeroshade commented on code in PR #1174:
URL: https://github.com/apache/arrow-go/pull/1174#discussion_r3896343961


##########
arrow/array/binary.go:
##########
@@ -432,17 +439,120 @@ func (a *LargeBinary) ValidateFull() error {
 }
 
 func arrayEqualLargeBinary(left, right *LargeBinary) bool {
-	for i := 0; i < left.Len(); i++ {
-		if left.IsNull(i) {
-			continue
+	if useScalarVariableWidthEquality(left) {
+		for i := range left.Len() {
+			if !left.IsNull(i) && !bytes.Equal(left.Value(i), right.Value(i)) {
+				return false
+			}
+		}
+		return true
+	}
+	return arrayEqualVariableWidth(
+		left.valueOffsets, right.valueOffsets,
+		left.valueBytes, right.valueBytes,
+		left.Offset(), right.Offset(), left.Len(),
+		left.NullN(), left.NullBitmapBytes(),
+		bytes.Equal,
+	)
+}
+
+type binaryOffset interface {
+	~int32 | ~int64
+}
+
+func useScalarVariableWidthEquality(values arrow.Array) bool {
+	if values.NullN() == 0 {
+		return false
+	}
+	if values.Len() <= 64 || len(values.NullBitmapBytes()) == 0 {
+		return true
+	}
+
+	// Very short validity runs cost more to set up than direct value comparisons.
+	// Sample a few runs and retain the scalar path when they average under four values.
+	const (
+		sampleRuns          = 8
+		minAverageRunLength = 4
+	)
+	runs := bitutils.NewSetBitRunReader(
+		values.NullBitmapBytes(), int64(values.Data().Offset()), int64(values.Len()),
+	)
+	validValues := int64(0)
+	for range sampleRuns {
+		run := runs.NextRun()
+		if run.Length == 0 {
+			return false
+		}
+		validValues += run.Length
+	}
+	return validValues < sampleRuns*minAverageRunLength
+}
+
+func arrayEqualVariableWidth[T binaryOffset, V ~[]byte | ~string](
+	leftOffsets, rightOffsets []T,
+	leftValues, rightValues V,
+	leftOffset, rightOffset, length, nulls int,
+	validity []byte,
+	equalValues func(V, V) bool,
+) bool {
+	if nulls == 0 {

Review Comment:
   The `nulls == 0` fast path compares every payload byte even when a validity bitmap contains nulls. With inconsistent `ArrayData`—a bitmap containing nulls but declared `null_count=0`—payload differences in null slots now make arrays unequal, unlike the prior scalar implementation. Please only use the whole-payload path when no validity bitmap exists, or otherwise process bitmap runs, and add a regression test.



-- 
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] perf(arrow/array): compare binary values by valid runs [arrow-go]

Posted by "zeroshade (via GitHub)" <gi...@apache.org>.
zeroshade merged PR #1174:
URL: https://github.com/apache/arrow-go/pull/1174


-- 
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