This is an automated email from the ASF dual-hosted git repository.
zeroshade pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-go.git
The following commit(s) were added to refs/heads/main by this push:
new 871b2197 perf(compute): vectorize mixed 64-bit filters (#1311)
871b2197 is described below
commit 871b21973ef1a52baba41daa16f2bbfa67f21197
Author: Minh Vu <[email protected]>
AuthorDate: Wed Sep 23 20:19:55 2026 +0200
perf(compute): vectorize mixed 64-bit filters (#1311)
## What changed
- Add AVX2 and ARM64 NEON paths for null-free 64-bit fixed-width filters.
- Compact two groups of four uint64 values from each filter byte with
table-driven permutations and exact-size stores.
- Keep the existing path for nulls, unsupported CPUs, short or unaligned
inputs, dense masks, and noasm builds.
- Add exhaustive mask tests, guard tests, and int64/float64 benchmarks.
## Benchmark
Apple M1 Pro, macOS arm64, Go 1.26.3. Median of five runs. The baseline
uses GODEBUG=cpu.all=off.
| Case | Baseline | NEON | Speedup |
| --- | ---: | ---: | ---: |
| int64, 1M, alternating | 3.97 ms | 0.45 ms | 8.7x |
| int64, 1M, random50 | 2.86 ms | 1.61 ms | 1.8x |
| float64, 1M, alternating | 4.07 ms | 0.47 ms | 8.6x |
| float64, 1M, random50 | 2.92 ms | 1.65 ms | 1.8x |
The mixed-mask cases also go from 33 to 32 allocations per operation. The
output allocation is still the main B/op cost.
## Tests
- Full go test suite with Parquet test data
- go test ./arrow/compute/...
- go test -tags noasm ./arrow/compute/...
- go test -race ./arrow/compute/internal/kernels ./arrow/compute
- amd64 cross-build of the kernel package
---
arrow/compute/internal/kernels/Makefile | 10 +-
.../compute/internal/kernels/_lib/filter_uint64.cc | 78 ++++++++++
.../kernels/_lib/filter_uint64_avx2_amd64.s | 82 +++++++++++
.../internal/kernels/filter_uint64_arch_test.go | 125 ++++++++++++++++
.../internal/kernels/filter_uint64_avx2_amd64.go | 92 ++++++++++++
.../internal/kernels/filter_uint64_avx2_amd64.s | 79 ++++++++++
.../kernels/filter_uint64_avx2_amd64_test.go | 46 ++++++
.../internal/kernels/filter_uint64_avx2_noasm.go | 23 +++
.../internal/kernels/filter_uint64_neon_arm64.go | 92 ++++++++++++
.../internal/kernels/filter_uint64_neon_arm64.s | 160 +++++++++++++++++++++
.../kernels/filter_uint64_neon_arm64_test.go | 46 ++++++
.../internal/kernels/filter_uint64_neon_noasm.go | 23 +++
arrow/compute/internal/kernels/vector_selection.go | 8 ++
arrow/compute/vector_selection_bench_test.go | 66 ++++++++-
14 files changed, 928 insertions(+), 2 deletions(-)
diff --git a/arrow/compute/internal/kernels/Makefile
b/arrow/compute/internal/kernels/Makefile
index 91a12e62..a1a8b419 100644
--- a/arrow/compute/internal/kernels/Makefile
+++ b/arrow/compute/internal/kernels/Makefile
@@ -41,7 +41,8 @@ ALL_SOURCES := $(shell find . -path ./_lib -prune -o -name
'*.go' -name '*.s' -n
INTEL_SOURCES := \
cast_numeric_avx2_amd64.s cast_numeric_sse4_amd64.s
constant_factor_avx2_amd64.s \
constant_factor_sse4_amd64.s base_arithmetic_avx2_amd64.s
base_arithmetic_sse4_amd64.s \
- scalar_comparison_avx2_amd64.s scalar_comparison_sse4_amd64.s
filter_uint32_avx2_amd64.s
+ scalar_comparison_avx2_amd64.s scalar_comparison_sse4_amd64.s \
+ filter_uint32_avx2_amd64.s filter_uint64_avx2_amd64.s
#
# ARROW-15336: DO NOT add the assembly target for Arm64 (ARM_SOURCES) until
c2goasm added the Arm64 support.
@@ -75,6 +76,9 @@ _lib/scalar_comparison_sse4_amd64.s: _lib/scalar_comparison.cc
_lib/filter_uint32_avx2_amd64.s: _lib/filter_uint32.cc
$(CXX) -std=c++17 -S $(C_FLAGS) $(ASM_FLAGS_AVX2) $^ -o $@ ;
$(PERL_FIXUP_ROTATE) $@
+_lib/filter_uint64_avx2_amd64.s: _lib/filter_uint64.cc
+ $(CXX) -std=c++17 -S $(C_FLAGS) $(ASM_FLAGS_AVX2) -mno-stackrealign
-fomit-frame-pointer $^ -o $@ ; $(PERL_FIXUP_ROTATE) $@
+
_lib/base_arithmetic_neon.s: _lib/base_arithmetic.cc
$(CXX) -std=c++17 -S $(C_FLAGS_NEON) $^ -o $@ ; $(PERL_FIXUP_ROTATE) $@
@@ -114,6 +118,10 @@ scalar_comparison_sse4_amd64.s:
_lib/scalar_comparison_sse4_amd64.s
filter_uint32_avx2_amd64.s: _lib/filter_uint32_avx2_amd64.s
$(C2GOASM) -a -f $^ $@
+filter_uint64_avx2_amd64.s: _lib/filter_uint64_avx2_amd64.s
+ $(C2GOASM) -a -f $^ $@
+ perl -i -pe 's{^//\s*\+build\b.*}{//go:build go1.18 && amd64 && !noasm
&& !appengine}' $@
+
clean:
rm -f $(INTEL_SOURCES)
rm -f $(addprefix _lib/,$(INTEL_SOURCES))
diff --git a/arrow/compute/internal/kernels/_lib/filter_uint64.cc
b/arrow/compute/internal/kernels/_lib/filter_uint64.cc
new file mode 100644
index 00000000..f00fed30
--- /dev/null
+++ b/arrow/compute/internal/kernels/_lib/filter_uint64.cc
@@ -0,0 +1,78 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include <arch.h>
+#include <immintrin.h>
+#include <stdint.h>
+
+extern "C" void FULL_NAME(filter_uint64)(const uint64_t* values,
+ const uint8_t* filter,
+ uint64_t* output,
+ const uint8_t* tables,
+ const int64_t length) {
+ const uint8_t* permutation_tables = tables;
+ const uint64_t* store_masks = reinterpret_cast<const uint64_t*>(tables +
512);
+ const uint8_t* popcount = tables + 672;
+ int64_t output_length = 0;
+ const int64_t num_bytes = length / 8;
+
+ for (int64_t i = 0; i < num_bytes; ++i) {
+ const uint8_t mask = filter[i];
+ const uint64_t* input = values + i * 8;
+
+ if (mask == 0) {
+ continue;
+ }
+
+ if (mask == 0xff) {
+ const __m256i low = _mm256_loadu_si256(reinterpret_cast<const
__m256i*>(input));
+ const __m256i high = _mm256_loadu_si256(reinterpret_cast<const
__m256i*>(input + 4));
+ _mm256_storeu_si256(reinterpret_cast<__m256i*>(output +
output_length), low);
+ _mm256_storeu_si256(reinterpret_cast<__m256i*>(output +
output_length + 4), high);
+ output_length += 8;
+ continue;
+ }
+
+ const uint8_t low_mask = mask & 0xf;
+ const uint8_t high_mask = mask >> 4;
+ const int low_count = popcount[low_mask];
+ const int high_count = popcount[high_mask];
+
+ if (low_count != 0) {
+ const __m256i input_values =
_mm256_loadu_si256(reinterpret_cast<const __m256i*>(input));
+ const __m256i permutation = _mm256_loadu_si256(
+ reinterpret_cast<const __m256i*>(permutation_tables + low_mask
* 32));
+ const __m256i compacted =
_mm256_permutevar8x32_epi32(input_values, permutation);
+ const __m256i store_mask = _mm256_loadu_si256(
+ reinterpret_cast<const __m256i*>(store_masks + low_count * 4));
+ _mm256_maskstore_epi32(reinterpret_cast<int*>(output +
output_length),
+ store_mask, compacted);
+ output_length += low_count;
+ }
+
+ if (high_count != 0) {
+ const __m256i input_values =
_mm256_loadu_si256(reinterpret_cast<const __m256i*>(input + 4));
+ const __m256i permutation = _mm256_loadu_si256(
+ reinterpret_cast<const __m256i*>(permutation_tables +
high_mask * 32));
+ const __m256i compacted =
_mm256_permutevar8x32_epi32(input_values, permutation);
+ const __m256i store_mask = _mm256_loadu_si256(
+ reinterpret_cast<const __m256i*>(store_masks + high_count *
4));
+ _mm256_maskstore_epi32(reinterpret_cast<int*>(output +
output_length),
+ store_mask, compacted);
+ output_length += high_count;
+ }
+ }
+}
diff --git a/arrow/compute/internal/kernels/_lib/filter_uint64_avx2_amd64.s
b/arrow/compute/internal/kernels/_lib/filter_uint64_avx2_amd64.s
new file mode 100644
index 00000000..bdca2b4a
--- /dev/null
+++ b/arrow/compute/internal/kernels/_lib/filter_uint64_avx2_amd64.s
@@ -0,0 +1,82 @@
+ .intel_syntax noprefix
+ .file "filter_uint64.cc"
+ .text
+ .globl filter_uint64_avx2 # -- Begin function
filter_uint64_avx2
+ .p2align 4
+ .type filter_uint64_avx2,@function
+filter_uint64_avx2: # @filter_uint64_avx2
+# %bb.0:
+ lea rax, [r8 + 7]
+ test r8, r8
+ cmovns rax, r8
+ cmp r8, 8
+ jl .LBB0_11
+# %bb.1:
+ push r14
+ push rbx
+ sar rax, 3
+ add rdi, 32
+ xor r8d, r8d
+ xor r9d, r9d
+ jmp .LBB0_2
+ .p2align 4
+.LBB0_4: # in Loop: Header=BB0_2 Depth=1
+ vmovdqu ymm0, ymmword ptr [rdi - 32]
+ vmovdqu ymm1, ymmword ptr [rdi]
+ vmovdqu ymmword ptr [rdx + 8*r8], ymm0
+ vmovdqu ymmword ptr [rdx + 8*r8 + 32], ymm1
+ add r8, 8
+.LBB0_9: # in Loop: Header=BB0_2 Depth=1
+ inc r9
+ add rdi, 64
+ cmp rax, r9
+ je .LBB0_10
+.LBB0_2: # =>This Inner Loop Header: Depth=1
+ movzx r10d, byte ptr [rsi + r9]
+ test r10d, r10d
+ je .LBB0_9
+# %bb.3: # in Loop: Header=BB0_2 Depth=1
+ cmp r10d, 255
+ je .LBB0_4
+# %bb.5: # in Loop: Header=BB0_2 Depth=1
+ mov r14d, r10d
+ and r14d, 15
+ shr r10d, 4
+ movzx ebx, byte ptr [rcx + r14 + 672]
+ movzx r11d, byte ptr [rcx + r10 + 672]
+ test rbx, rbx
+ je .LBB0_7
+# %bb.6: # in Loop: Header=BB0_2 Depth=1
+ shl r14d, 5
+ vmovdqu ymm0, ymmword ptr [rcx + r14]
+ vpermd ymm0, ymm0, ymmword ptr [rdi - 32]
+ mov r14d, ebx
+ shl r14d, 5
+ vmovdqu ymm1, ymmword ptr [rcx + r14 + 512]
+ vpmaskmovd ymmword ptr [rdx + 8*r8], ymm1, ymm0
+ add r8, rbx
+.LBB0_7: # in Loop: Header=BB0_2 Depth=1
+ test r11, r11
+ je .LBB0_9
+# %bb.8: # in Loop: Header=BB0_2 Depth=1
+ shl r10d, 5
+ vmovdqu ymm0, ymmword ptr [rcx + r10]
+ vpermd ymm0, ymm0, ymmword ptr [rdi]
+ mov r10d, r11d
+ shl r10d, 5
+ vmovdqu ymm1, ymmword ptr [rcx + r10 + 512]
+ vpmaskmovd ymmword ptr [rdx + 8*r8], ymm1, ymm0
+ add r8, r11
+ jmp .LBB0_9
+.LBB0_10:
+ pop rbx
+ pop r14
+.LBB0_11:
+ vzeroupper
+ ret
+.Lfunc_end0:
+ .size filter_uint64_avx2, .Lfunc_end0-filter_uint64_avx2
+ # -- End function
+ .ident "Apple clang version 21.0.0 (clang-2100.1.1.101)"
+ .section ".note.GNU-stack","",@progbits
+ .addrsig
diff --git a/arrow/compute/internal/kernels/filter_uint64_arch_test.go
b/arrow/compute/internal/kernels/filter_uint64_arch_test.go
new file mode 100644
index 00000000..8eb42d0e
--- /dev/null
+++ b/arrow/compute/internal/kernels/filter_uint64_arch_test.go
@@ -0,0 +1,125 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//go:build go1.18 && (amd64 || arm64) && !noasm && !appengine
+
+package kernels
+
+import "testing"
+
+type filterUint64Func func(values []uint64, output []uint64, filter []byte,
filterOffset, length int64) bool
+
+func testFilterUint64AllMasks(t *testing.T, filter filterUint64Func) {
+ t.Helper()
+
+ const (
+ filterBytes = 256
+ length = filterBytes * 8
+ )
+ values := make([]uint64, length)
+ filterData := make([]byte, filterBytes)
+ for i := range values {
+ values[i] = uint64(i*17 + 3)
+ }
+ for i := range filterData {
+ filterData[i] = byte(i)
+ }
+
+ expected := make([]uint64, 0, length)
+ for i, mask := range filterData {
+ for lane := 0; lane < 8; lane++ {
+ if mask&(1<<uint(lane)) != 0 {
+ expected = append(expected, values[i*8+lane])
+ }
+ }
+ }
+
+ backing := make([]uint64, len(expected)+1)
+ backing[len(expected)] = 0xdeadbeef
+ if !filter(values, backing[:len(expected)], filterData, 0, length) {
+ t.Fatal("filterUint64 did not select the mixed-mask path")
+ }
+ for i, want := range expected {
+ if got := backing[i]; got != want {
+ t.Fatalf("output[%d] = %d, want %d", i, got, want)
+ }
+ }
+ if got := backing[len(expected)]; got != 0xdeadbeef {
+ t.Fatalf("sentinel = %#x, want %#x", got, uint64(0xdeadbeef))
+ }
+}
+
+func testFilterUint64AlignedOffset(t *testing.T, filter filterUint64Func) {
+ t.Helper()
+
+ const (
+ offset = 8
+ length = 64
+ )
+ values := make([]uint64, length)
+ for i := range values {
+ values[i] = uint64(i)
+ }
+ filterData := make([]byte, offset/8+length/8)
+ for i := range filterData[offset/8:] {
+ filterData[offset/8+i] = 0x55
+ }
+
+ output := make([]uint64, length/2)
+ if !filter(values, output, filterData, offset, length) {
+ t.Fatal("filterUint64 did not select the aligned-offset path")
+ }
+ for i, got := range output {
+ want := uint64(2 * i)
+ if got != want {
+ t.Fatalf("output[%d] = %d, want %d", i, got, want)
+ }
+ }
+}
+
+func testFilterUint64Guards(t *testing.T, filter filterUint64Func) {
+ t.Helper()
+
+ values := make([]uint64, 128)
+ mixed := make([]byte, 16)
+ for i := range mixed {
+ mixed[i] = 0x55
+ }
+ output := make([]uint64, 64)
+
+ tests := []struct {
+ name string
+ filter []byte
+ offset int64
+ length int64
+ want bool
+ }{
+ {name: "short", filter: mixed, length: 56},
+ {name: "non-multiple-of-eight", filter: mixed, length: 71},
+ {name: "unaligned-filter-offset", filter: mixed, offset: 3,
length: 64},
+ {name: "all-false", filter: make([]byte, 8), length: 64},
+ {name: "all-true", filter: []byte{0xff, 0xff, 0xff, 0xff, 0xff,
0xff, 0xff, 0xff}, length: 64},
+ {name: "too-few-mixed-bytes", filter: []byte{0x55, 0x55, 0x55,
0x00, 0x00, 0x00, 0x00, 0x00}, length: 64},
+ {name: "out-of-bounds-filter", filter: mixed[:4], length: 64},
+ }
+ for _, tt := range tests {
+ t.Run(tt.name, func(t *testing.T) {
+ if got := filter(values, output, tt.filter, tt.offset,
tt.length); got != tt.want {
+ t.Fatalf("filterUint64() = %t, want %t", got,
tt.want)
+ }
+ })
+ }
+}
diff --git a/arrow/compute/internal/kernels/filter_uint64_avx2_amd64.go
b/arrow/compute/internal/kernels/filter_uint64_avx2_amd64.go
new file mode 100644
index 00000000..a1733bb6
--- /dev/null
+++ b/arrow/compute/internal/kernels/filter_uint64_avx2_amd64.go
@@ -0,0 +1,92 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//go:build go1.18 && amd64 && !noasm && !appengine
+
+package kernels
+
+import (
+ "encoding/binary"
+ "math/bits"
+ "unsafe"
+
+ "golang.org/x/sys/cpu"
+)
+
+var filterUint64Tables = makeFilterUint64Tables()
+
+func makeFilterUint64Tables() (tables [688]byte) {
+ for mask := 0; mask < 16; mask++ {
+ pos := 0
+ for lane := 0; lane < 4; lane++ {
+ if mask&(1<<uint(lane)) == 0 {
+ continue
+ }
+ binary.LittleEndian.PutUint32(tables[mask*32+pos*8:],
uint32(lane*2))
+ binary.LittleEndian.PutUint32(tables[mask*32+pos*8+4:],
uint32(lane*2+1))
+ pos++
+ }
+ }
+
+ for count := 1; count <= 4; count++ {
+ for lane := 0; lane < count*2; lane++ {
+
binary.LittleEndian.PutUint32(tables[512+count*32+lane*4:], ^uint32(0))
+ }
+ }
+ for mask := 0; mask < 16; mask++ {
+ tables[672+mask] = byte(bits.OnesCount8(uint8(mask)))
+ }
+ return tables
+}
+
+//go:noescape
+func _filter_uint64_avx2(values, filter, output, tables unsafe.Pointer, length
int64)
+
+func filterUint64Avx2(values []uint64, output []uint64, filterData []byte,
filterOffset, length int64) bool {
+ if !cpu.X86.HasAVX2 || length < 64 || length%8 != 0 || filterOffset%8
!= 0 {
+ return false
+ }
+
+ numBytes := length / 8
+ filterByteOffset := filterOffset / 8
+ if filterByteOffset < 0 || filterByteOffset+numBytes >
int64(len(filterData)) {
+ return false
+ }
+
+ mixedBytes := 0
+ const sampleBytes = 64
+ for i := int64(0); i < numBytes && i < sampleBytes; i++ {
+ mask := filterData[filterByteOffset+i]
+ if mask != 0 && mask != 0xff {
+ mixedBytes++
+ if mixedBytes == 4 {
+ break
+ }
+ }
+ }
+ if mixedBytes < 4 || len(output) == 0 {
+ return false
+ }
+
+ _filter_uint64_avx2(
+ unsafe.Pointer(&values[0]),
+ unsafe.Pointer(&filterData[filterByteOffset]),
+ unsafe.Pointer(&output[0]),
+ unsafe.Pointer(&filterUint64Tables[0]),
+ length,
+ )
+ return true
+}
diff --git a/arrow/compute/internal/kernels/filter_uint64_avx2_amd64.s
b/arrow/compute/internal/kernels/filter_uint64_avx2_amd64.s
new file mode 100644
index 00000000..c1b87d32
--- /dev/null
+++ b/arrow/compute/internal/kernels/filter_uint64_avx2_amd64.s
@@ -0,0 +1,79 @@
+//go:build go1.18 && amd64 && !noasm && !appengine
+// AUTO-GENERATED BY C2GOASM -- DO NOT EDIT
+
+TEXT ·_filter_uint64_avx2(SB), $0-40
+
+ MOVQ values+0(FP), DI
+ MOVQ filter+8(FP), SI
+ MOVQ output+16(FP), DX
+ MOVQ tables+24(FP), CX
+ MOVQ length+32(FP), R8
+
+ LONG $0x07408d49 // lea rax, [r8 + 7]
+ WORD $0x854d; BYTE $0xc0 // test r8, r8
+ LONG $0xc0490f49 // cmovns rax, r8
+ LONG $0x08f88349 // cmp r8, 8
+ JL LBB0_11
+ WORD $0x5641 // push r14
+ BYTE $0x53 // push rbx
+ LONG $0x03f8c148 // sar rax, 3
+ LONG $0x20c78348 // add rdi, 32
+ WORD $0x3145; BYTE $0xc0 // xor r8d, r8d
+ WORD $0x3145; BYTE $0xc9 // xor r9d, r9d
+ JMP LBB0_2
+
+LBB0_4:
+ LONG $0x476ffec5; BYTE $0xe0 // vmovdqu ymm0, yword
[rdi - 32]
+ LONG $0x0f6ffec5 // vmovdqu ymm1, yword
[rdi]
+ LONG $0x7f7ea1c4; WORD $0xc204 // vmovdqu yword [rdx +
8*r8], ymm0
+ LONG $0x7f7ea1c4; WORD $0xc24c; BYTE $0x20 // vmovdqu yword [rdx +
8*r8 + 32], ymm1
+ LONG $0x08c08349 // add r8, 8
+
+LBB0_9:
+ WORD $0xff49; BYTE $0xc1 // inc r9
+ LONG $0x40c78348 // add rdi, 64
+ WORD $0x394c; BYTE $0xc8 // cmp rax, r9
+ JE LBB0_10
+
+LBB0_2:
+ LONG $0x14b60f46; BYTE $0x0e // movzx r10d, byte [rsi
+ r9]
+ WORD $0x8545; BYTE $0xd2 // test r10d, r10d
+ JE LBB0_9
+ LONG $0xfffa8141; WORD $0x0000; BYTE $0x00 // cmp r10d, 255
+ JE LBB0_4
+ WORD $0x8945; BYTE $0xd6 // mov r14d, r10d
+ LONG $0x0fe68341 // and r14d, 15
+ LONG $0x04eac141 // shr r10d, 4
+ QUAD $0x0002a0319cb60f42; BYTE $0x00 // movzx ebx, byte [rcx +
r14 + 672]
+ QUAD $0x0002a0119cb60f46; BYTE $0x00 // movzx r11d, byte [rcx
+ r10 + 672]
+ WORD $0x8548; BYTE $0xdb // test rbx, rbx
+ JE LBB0_7
+ LONG $0x05e6c141 // shl r14d, 5
+ LONG $0x6f7ea1c4; WORD $0x3104 // vmovdqu ymm0, yword
[rcx + r14]
+ LONG $0x367de2c4; WORD $0xe047 // vpermd ymm0, ymm0,
yword [rdi - 32]
+ WORD $0x8941; BYTE $0xde // mov r14d, ebx
+ LONG $0x05e6c141 // shl r14d, 5
+ QUAD $0x0200318c6f7ea1c4; WORD $0x0000 // vmovdqu ymm1, yword
[rcx + r14 + 512]
+ LONG $0x8e75a2c4; WORD $0xc204 // vpmaskmovd yword [rdx
+ 8*r8], ymm1, ymm0
+ WORD $0x0149; BYTE $0xd8 // add r8, rbx
+
+LBB0_7:
+ WORD $0x854d; BYTE $0xdb // test r11, r11
+ JE LBB0_9
+ LONG $0x05e2c141 // shl r10d, 5
+ LONG $0x6f7ea1c4; WORD $0x1104 // vmovdqu ymm0, yword [rcx +
r10]
+ LONG $0x367de2c4; BYTE $0x07 // vpermd ymm0, ymm0, yword
[rdi]
+ WORD $0x8945; BYTE $0xda // mov r10d, r11d
+ LONG $0x05e2c141 // shl r10d, 5
+ QUAD $0x0200118c6f7ea1c4; WORD $0x0000 // vmovdqu ymm1, yword [rcx +
r10 + 512]
+ LONG $0x8e75a2c4; WORD $0xc204 // vpmaskmovd yword [rdx +
8*r8], ymm1, ymm0
+ WORD $0x014d; BYTE $0xd8 // add r8, r11
+ JMP LBB0_9
+
+LBB0_10:
+ BYTE $0x5b // pop rbx
+ WORD $0x5e41 // pop r14
+
+LBB0_11:
+ VZEROUPPER
+ RET
diff --git a/arrow/compute/internal/kernels/filter_uint64_avx2_amd64_test.go
b/arrow/compute/internal/kernels/filter_uint64_avx2_amd64_test.go
new file mode 100644
index 00000000..7ba53948
--- /dev/null
+++ b/arrow/compute/internal/kernels/filter_uint64_avx2_amd64_test.go
@@ -0,0 +1,46 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//go:build go1.18 && amd64 && !noasm && !appengine
+
+package kernels
+
+import (
+ "testing"
+
+ "golang.org/x/sys/cpu"
+)
+
+func TestFilterUint64Avx2AllMasks(t *testing.T) {
+ if !cpu.X86.HasAVX2 {
+ t.Skip("AVX2 is not available")
+ }
+ testFilterUint64AllMasks(t, filterUint64Avx2)
+}
+
+func TestFilterUint64Avx2AlignedOffset(t *testing.T) {
+ if !cpu.X86.HasAVX2 {
+ t.Skip("AVX2 is not available")
+ }
+ testFilterUint64AlignedOffset(t, filterUint64Avx2)
+}
+
+func TestFilterUint64Avx2Guards(t *testing.T) {
+ if !cpu.X86.HasAVX2 {
+ t.Skip("AVX2 is not available")
+ }
+ testFilterUint64Guards(t, filterUint64Avx2)
+}
diff --git a/arrow/compute/internal/kernels/filter_uint64_avx2_noasm.go
b/arrow/compute/internal/kernels/filter_uint64_avx2_noasm.go
new file mode 100644
index 00000000..842c185a
--- /dev/null
+++ b/arrow/compute/internal/kernels/filter_uint64_avx2_noasm.go
@@ -0,0 +1,23 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//go:build go1.18 && (noasm || !amd64 || appengine)
+
+package kernels
+
+func filterUint64Avx2([]uint64, []uint64, []byte, int64, int64) bool {
+ return false
+}
diff --git a/arrow/compute/internal/kernels/filter_uint64_neon_arm64.go
b/arrow/compute/internal/kernels/filter_uint64_neon_arm64.go
new file mode 100644
index 00000000..08766040
--- /dev/null
+++ b/arrow/compute/internal/kernels/filter_uint64_neon_arm64.go
@@ -0,0 +1,92 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//go:build go1.18 && arm64 && !noasm && !appengine
+
+package kernels
+
+import (
+ "math/bits"
+ "unsafe"
+
+ "golang.org/x/sys/cpu"
+)
+
+var filterUint64NeonTables = makeFilterUint64NeonTables()
+
+func makeFilterUint64NeonTables() (tables [528]byte) {
+ for mask := 0; mask < 16; mask++ {
+ for i := 0; i < 32; i++ {
+ tables[mask*32+i] = 0x80
+ }
+
+ pos := 0
+ for lane := 0; lane < 4; lane++ {
+ if mask&(1<<uint(lane)) == 0 {
+ continue
+ }
+ vectorOffset := mask*32 + (pos/2)*16 + (pos%2)*8
+ for byteInLane := 0; byteInLane < 8; byteInLane++ {
+ tables[vectorOffset+byteInLane] = byte(lane*8 +
byteInLane)
+ }
+ pos++
+ }
+ }
+
+ for mask := 0; mask < 16; mask++ {
+ tables[512+mask] = byte(bits.OnesCount8(uint8(mask)))
+ }
+ return tables
+}
+
+//go:noescape
+func _filter_uint64_neon(values, filter, output, tables unsafe.Pointer, length
int64)
+
+func filterUint64Neon(values []uint64, output []uint64, filterData []byte,
filterOffset, length int64) bool {
+ if !cpu.ARM64.HasASIMD || length < 64 || length%8 != 0 ||
filterOffset%8 != 0 {
+ return false
+ }
+
+ numBytes := length / 8
+ filterByteOffset := filterOffset / 8
+ if filterByteOffset < 0 || filterByteOffset+numBytes >
int64(len(filterData)) {
+ return false
+ }
+
+ mixedBytes := 0
+ const sampleBytes = 64
+ for i := int64(0); i < numBytes && i < sampleBytes; i++ {
+ mask := filterData[filterByteOffset+i]
+ if mask != 0 && mask != 0xff {
+ mixedBytes++
+ if mixedBytes == 4 {
+ break
+ }
+ }
+ }
+ if mixedBytes < 4 || len(output) == 0 {
+ return false
+ }
+
+ _filter_uint64_neon(
+ unsafe.Pointer(&values[0]),
+ unsafe.Pointer(&filterData[filterByteOffset]),
+ unsafe.Pointer(&output[0]),
+ unsafe.Pointer(&filterUint64NeonTables[0]),
+ length,
+ )
+ return true
+}
diff --git a/arrow/compute/internal/kernels/filter_uint64_neon_arm64.s
b/arrow/compute/internal/kernels/filter_uint64_neon_arm64.s
new file mode 100644
index 00000000..0f51e128
--- /dev/null
+++ b/arrow/compute/internal/kernels/filter_uint64_neon_arm64.s
@@ -0,0 +1,160 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//go:build go1.18 && arm64 && !noasm && !appengine
+
+#include "textflag.h"
+
+// Each filter byte selects up to four uint64 values from each of two
+// four-value halves. The table-driven VTBL compacts one half into two
+// vectors. The stores write exactly the selected number of bytes.
+
+// func _filter_uint64_neon(values, filter, output, tables unsafe.Pointer,
length int64)
+TEXT ·_filter_uint64_neon(SB), NOSPLIT|NOFRAME, $0-40
+ MOVD values+0(FP), R0
+ MOVD filter+8(FP), R1
+ MOVD output+16(FP), R2
+ MOVD tables+24(FP), R3
+ MOVD length+32(FP), R4
+
+ LSR $3, R4, R4
+
+filter_loop:
+ MOVBU (R1), R5
+ ADD $1, R1
+ CBZ R5, filter_next
+ CMPW $255, R5
+ BEQ filter_all
+
+ ANDW $15, R5, R6
+ ADD $512, R3, R8
+ MOVBU (R8)(R6<<0), R9
+ CBZ R9, filter_high
+
+ VLD1 (R0), [V0.D2]
+ ADD $16, R0, R8
+ VLD1 (R8), [V1.D2]
+
+ LSL $5, R6, R10
+ ADD R3, R10, R10
+ VLD1 (R10), [V2.B16]
+ VTBL V2.B16, [V0.B16, V1.B16], V4.B16
+ ADD $16, R10, R10
+ VLD1 (R10), [V2.B16]
+ VTBL V2.B16, [V0.B16, V1.B16], V5.B16
+
+ CMPW $1, R9
+ BEQ filter_low_store1
+ CMPW $2, R9
+ BEQ filter_low_store2
+ CMPW $3, R9
+ BEQ filter_low_store3
+ VST1 [V4.D2], (R2)
+ ADD $16, R2
+ VST1 [V5.D2], (R2)
+ ADD $16, R2
+ B filter_high
+
+filter_low_store1:
+ VMOV V4.D[0], R8
+ MOVD R8, (R2)
+ ADD $8, R2
+ B filter_high
+
+filter_low_store2:
+ VST1 [V4.D2], (R2)
+ ADD $16, R2
+ B filter_high
+
+filter_low_store3:
+ VST1 [V4.D2], (R2)
+ ADD $16, R2
+ VMOV V5.D[0], R8
+ MOVD R8, (R2)
+ ADD $8, R2
+
+filter_high:
+ LSR $4, R5, R6
+ ADD $512, R3, R8
+ MOVBU (R8)(R6<<0), R9
+ CBZ R9, filter_next
+
+ ADD $32, R0, R8
+ VLD1 (R8), [V0.D2]
+ ADD $48, R0, R8
+ VLD1 (R8), [V1.D2]
+
+ LSL $5, R6, R10
+ ADD R3, R10, R10
+ VLD1 (R10), [V2.B16]
+ VTBL V2.B16, [V0.B16, V1.B16], V4.B16
+ ADD $16, R10, R10
+ VLD1 (R10), [V2.B16]
+ VTBL V2.B16, [V0.B16, V1.B16], V5.B16
+
+ CMPW $1, R9
+ BEQ filter_high_store1
+ CMPW $2, R9
+ BEQ filter_high_store2
+ CMPW $3, R9
+ BEQ filter_high_store3
+ VST1 [V4.D2], (R2)
+ ADD $16, R2
+ VST1 [V5.D2], (R2)
+ ADD $16, R2
+ B filter_next
+
+filter_high_store1:
+ VMOV V4.D[0], R8
+ MOVD R8, (R2)
+ ADD $8, R2
+ B filter_next
+
+filter_high_store2:
+ VST1 [V4.D2], (R2)
+ ADD $16, R2
+ B filter_next
+
+filter_high_store3:
+ VST1 [V4.D2], (R2)
+ ADD $16, R2
+ VMOV V5.D[0], R8
+ MOVD R8, (R2)
+ ADD $8, R2
+ B filter_next
+
+filter_all:
+ VLD1 (R0), [V0.D2]
+ ADD $16, R0, R8
+ VLD1 (R8), [V1.D2]
+ ADD $32, R0, R8
+ VLD1 (R8), [V2.D2]
+ ADD $48, R0, R8
+ VLD1 (R8), [V3.D2]
+ VST1 [V0.D2], (R2)
+ ADD $16, R2
+ VST1 [V1.D2], (R2)
+ ADD $16, R2
+ VST1 [V2.D2], (R2)
+ ADD $16, R2
+ VST1 [V3.D2], (R2)
+ ADD $16, R2
+
+filter_next:
+ ADD $64, R0
+ SUBS $1, R4, R4
+ BNE filter_loop
+ RET
diff --git a/arrow/compute/internal/kernels/filter_uint64_neon_arm64_test.go
b/arrow/compute/internal/kernels/filter_uint64_neon_arm64_test.go
new file mode 100644
index 00000000..2eae877c
--- /dev/null
+++ b/arrow/compute/internal/kernels/filter_uint64_neon_arm64_test.go
@@ -0,0 +1,46 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//go:build go1.18 && arm64 && !noasm && !appengine
+
+package kernels
+
+import (
+ "testing"
+
+ "golang.org/x/sys/cpu"
+)
+
+func TestFilterUint64NeonAllMasks(t *testing.T) {
+ if !cpu.ARM64.HasASIMD {
+ t.Skip("ARM64 SIMD is not available")
+ }
+ testFilterUint64AllMasks(t, filterUint64Neon)
+}
+
+func TestFilterUint64NeonAlignedOffset(t *testing.T) {
+ if !cpu.ARM64.HasASIMD {
+ t.Skip("ARM64 SIMD is not available")
+ }
+ testFilterUint64AlignedOffset(t, filterUint64Neon)
+}
+
+func TestFilterUint64NeonGuards(t *testing.T) {
+ if !cpu.ARM64.HasASIMD {
+ t.Skip("ARM64 SIMD is not available")
+ }
+ testFilterUint64Guards(t, filterUint64Neon)
+}
diff --git a/arrow/compute/internal/kernels/filter_uint64_neon_noasm.go
b/arrow/compute/internal/kernels/filter_uint64_neon_noasm.go
new file mode 100644
index 00000000..1459d23e
--- /dev/null
+++ b/arrow/compute/internal/kernels/filter_uint64_neon_noasm.go
@@ -0,0 +1,23 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//go:build go1.18 && (noasm || !arm64 || appengine)
+
+package kernels
+
+func filterUint64Neon([]uint64, []uint64, []byte, int64, int64) bool {
+ return false
+}
diff --git a/arrow/compute/internal/kernels/vector_selection.go
b/arrow/compute/internal/kernels/vector_selection.go
index 32a6f4b7..8ea29377 100644
--- a/arrow/compute/internal/kernels/vector_selection.go
+++ b/arrow/compute/internal/kernels/vector_selection.go
@@ -495,6 +495,14 @@ func PrimitiveFilter(ctx *exec.KernelCtx, batch
*exec.ExecSpan, out *exec.ExecRe
return nil
}
}
+ if bitWidth == 64 && values.Nulls == 0 && filter.Nulls == 0 {
+ valuesData := exec.GetSpanValues[uint64](values, 1)
+ outData := exec.GetSpanValues[uint64](out, 1)
+ if filterUint64Avx2(valuesData, outData, filter.Buffers[1].Buf,
filter.Offset, values.Len) ||
+ filterUint64Neon(valuesData, outData,
filter.Buffers[1].Buf, filter.Offset, values.Len) {
+ return nil
+ }
+ }
var wr writeFiltered
switch bitWidth {
diff --git a/arrow/compute/vector_selection_bench_test.go
b/arrow/compute/vector_selection_bench_test.go
index 4a14f6ad..8bef0201 100644
--- a/arrow/compute/vector_selection_bench_test.go
+++ b/arrow/compute/vector_selection_bench_test.go
@@ -39,8 +39,28 @@ func BenchmarkFilterFloat32MixedMasks(b *testing.B) {
benchmarkFilter32MixedMasks(b, makeFilterFloat32BenchmarkInput)
}
+func BenchmarkFilterInt64MixedMasks(b *testing.B) {
+ benchmarkFilter64MixedMasks(b, makeFilterInt64BenchmarkInput)
+}
+
+func BenchmarkFilterFloat64MixedMasks(b *testing.B) {
+ benchmarkFilter64MixedMasks(b, makeFilterFloat64BenchmarkInput)
+}
+
func benchmarkFilter32MixedMasks(b *testing.B,
makeInput func(*testing.B, int, func(int) bool) (arrow.Array,
arrow.Array),
+) {
+ benchmarkFilterMixedMasks(b, makeInput, 4)
+}
+
+func benchmarkFilter64MixedMasks(b *testing.B,
+ makeInput func(*testing.B, int, func(int) bool) (arrow.Array,
arrow.Array),
+) {
+ benchmarkFilterMixedMasks(b, makeInput, 8)
+}
+
+func benchmarkFilterMixedMasks(b *testing.B,
+ makeInput func(*testing.B, int, func(int) bool) (arrow.Array,
arrow.Array), valueBytes int,
) {
patterns := []struct {
name string
@@ -65,7 +85,7 @@ func benchmarkFilter32MixedMasks(b *testing.B,
defer filter.Release()
b.ReportAllocs()
- b.SetBytes(int64(size * 4))
+ b.SetBytes(int64(size * valueBytes))
b.ResetTimer()
for i := 0; i < b.N; i++ {
result, err :=
compute.FilterArray(context.Background(), values, filter,
*compute.DefaultFilterOptions())
@@ -166,6 +186,50 @@ func makeFilterFloat32BenchmarkInput(b *testing.B, size
int, selected func(int)
return values, filter
}
+func makeFilterInt64BenchmarkInput(b *testing.B, size int, selected func(int)
bool) (arrow.Array, arrow.Array) {
+ b.Helper()
+ mem := memory.DefaultAllocator
+
+ valuesBuilder := array.NewInt64Builder(mem)
+ valuesBuilder.Reserve(size)
+ for i := 0; i < size; i++ {
+ valuesBuilder.Append(int64(i))
+ }
+ values := valuesBuilder.NewInt64Array()
+ valuesBuilder.Release()
+
+ filterBuilder := array.NewBooleanBuilder(mem)
+ filterBuilder.Reserve(size)
+ for i := 0; i < size; i++ {
+ filterBuilder.Append(selected(i))
+ }
+ filter := filterBuilder.NewBooleanArray()
+ filterBuilder.Release()
+ return values, filter
+}
+
+func makeFilterFloat64BenchmarkInput(b *testing.B, size int, selected
func(int) bool) (arrow.Array, arrow.Array) {
+ b.Helper()
+ mem := memory.DefaultAllocator
+
+ valuesBuilder := array.NewFloat64Builder(mem)
+ valuesBuilder.Reserve(size)
+ for i := 0; i < size; i++ {
+ valuesBuilder.Append(float64(i))
+ }
+ values := valuesBuilder.NewFloat64Array()
+ valuesBuilder.Release()
+
+ filterBuilder := array.NewBooleanBuilder(mem)
+ filterBuilder.Reserve(size)
+ for i := 0; i < size; i++ {
+ filterBuilder.Append(selected(i))
+ }
+ filter := filterBuilder.NewBooleanArray()
+ filterBuilder.Release()
+ return values, filter
+}
+
func filterBenchmarkRandom(i, selectedPercent int) bool {
x := uint32(i)*747796405 + 2891336453
x = ((x >> ((x >> 28) + 4)) ^ x) * 277803737
