apache / apache/arrow-rs

AVX512 optimized filter kernels for primitive types

Open
#1,949 3 comments 3 reactions 0 assignees View on GitHub
enhancement
Dominant language
Rust
Stars
3.6k
Forks
1.3k
Avg merge
2d 18h
Merged PRs (30d)
169

Description

**Is your feature request related to a problem or challenge? Please describe what you are trying to do.**

In #1829 we removed AVX512 optimizations for AND/OR kernels since the autovectorized code was just as good, but there are some AVX512 instructions that could have a big benefit and which the compiler would not be able to use automatically. One of those extensions is the [`compressstore` instruction](https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#text=compressstore&ig_expand=1426) which basically implements most of the filter kernel in a single instruction.

[I recently experimented with those](https://github.com/apache/arrow-rs/compare/main...jhorstmann:arrow-rs:experiment-avx512-filter-kernel) and found that, while our current filters are extremely good for extreme selectivities thanks to all the optimizations that @tustvold did, for selectivities between 5% and 99% the AVX512 version would be faster. For a random selectivity of 50% nearly 10x faster.

**Describe the solution you'd like**

There are a few open questions how to best integrate these functions into the filter kernels. They don't fit that well into the existing strategies, since they would be specific to primitive arrays, and there might be different selectivity cutoffs for falling back to one of the existing strategies.

We would also need to decide whether to statically dispatch to these kernels, based on `target-cpu` or `target-feature`, or use runtime feature detection.

The 8 and 16 bit versions of these instructions are also only available since the `icelake` generation, making testing a bit more difficult.

**Describe alternatives you've considered**

There is a [discussion on the portable-simd about portable alternatives to these instructions](https://github.com/rust-lang/portable-simd/issues/240) but that would require quite some work in llvm, since there are not portable llvm intrinsics yet, only the x86/avx512 implementations.

**Additional context**

Benchmark results for filtering i32 running on a zen5 machine:

```
filter i32 (kept 1/2) time: [26.685 µs 26.766 µs 26.854 µs]

filter i32 high selectivity (kept 1023/1024)
time: [14.614 µs 14.641 µs 14.669 µs]

filter i32 low selectivity (kept 1/1024)
time: [3.8293 µs 3.8593 µs 3.8939 µs]

filter i32 avx512 (kept 1/2)
time: [3.7767 µs 3.7820 µs 3.7880 µs]

filter i32 avx512 high selectivity (kept 1023/1024)
time: [3.7905 µs 3.8362 µs 3.9007 µs]

filter i32 avx512 low selectivity (kept 1/1024)
time: [3.9136 µs 3.9250 µs 3.9392 µs]
```

Contributor guide

Open the contributing guide

Research direction

Start by reading the existing filter kernels and the changes in #1829, then compare them with the linked AVX512 experiment. Investigate the benchmark results and the open questions around selectivity cutoffs, primitive-array integration, dispatch, and hardware support; done means an agreed design and validated AVX512 filter implementation.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Needs clarification
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.