Skip to content

Commit dd1ce26

Browse files
perf(buffer): portable fearless_simd kernels for bitmap rank-select (#10319)
Signed-off-by: Joe Isaacs <[email protected]>
1 parent cc018ee commit dd1ce26

2 files changed

Lines changed: 36 additions & 194 deletions

File tree

‎vortex-buffer/benches/vortex_bitbuffer.rs‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -333,3 +333,12 @@ fn set_indices_arrow_buffer(bencher: Bencher, length: usize) {
333333
}
334334
});
335335
}
336+
337+
/// Rank-select scan over a sparse deterministic bitmap, reaching the final chunk.
338+
#[divan::bench(args = [512, 65_536, 1_048_576])]
339+
fn select_last_vortex_buffer(bencher: Bencher, length: usize) {
340+
let buffer = BitBuffer::collect_bool(length, |i| i % 3 == 0);
341+
let nth = buffer.true_count() - 1;
342+
assert_eq!(buffer.select(nth), Some((length - 1) / 3 * 3));
343+
bencher.bench(|| divan::black_box(&buffer).select(divan::black_box(nth)));
344+
}

‎vortex-buffer/src/bit/select.rs‎

Lines changed: 27 additions & 194 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,15 @@
11
// SPDX-License-Identifier: Apache-2.0
22
// SPDX-FileCopyrightText: Copyright the Vortex contributors
33

4+
use fearless_simd::Level;
5+
use fearless_simd::Simd;
6+
use fearless_simd::dispatch;
7+
use fearless_simd::prelude::*;
8+
use fearless_simd::u8x64;
9+
use fearless_simd::u64x8;
10+
use fearless_simd_macros::simd;
11+
use vortex_error::VortexExpect;
12+
413
use super::count_ones::align_offset_len;
514
use crate::dispatch::CpuKernel;
615

@@ -10,12 +19,8 @@ use crate::dispatch::CpuKernel;
1019
/// The returned position is relative to the logical start (i.e., 0-indexed from `offset`).
1120
/// Returns `None` if `nth` is out of bounds.
1221
///
13-
/// Uses architecture-specific optimizations:
14-
/// - **aarch64**: NEON `vcnt`-based popcount for the 64-byte chunk scan.
15-
/// - **x86_64 + AVX-512 VPOPCNTDQ**: 64-byte chunk scan.
16-
/// - **x86_64 + AVX-512 VBMI2**: byte-lane compress for the final in-word select.
17-
/// - **x86_64 + BMI2**: `pdep` + `tzcnt` for the final in-word select.
18-
/// - **Scalar fallback**: 4× unrolled word scan with `count_ones`, byte-level narrowing.
22+
/// 64-byte chunks are scanned and selected with SIMD popcounts. The final in-word select uses
23+
/// `pdep` + `tzcnt` on x86_64 with BMI2, and a scalar fallback elsewhere.
1924
#[inline]
2025
pub fn bit_select(bytes: &[u8], offset: usize, len: usize, nth: usize) -> Option<usize> {
2126
let (head, middle, tail) = align_offset_len(bytes, offset, len);
@@ -83,140 +88,28 @@ pub fn bit_select(bytes: &[u8], offset: usize, len: usize, nth: usize) -> Option
8388
///
8489
/// If `chunk_index < chunks.len()`, the target bit is inside that chunk and `remaining`
8590
/// is the rank *within* that chunk. Otherwise all chunks were consumed.
86-
type ScanChunks = unsafe fn(&[[u8; 64]], usize, usize) -> (usize, usize, usize);
87-
8891
#[inline]
8992
fn scan_chunks(chunks: &[[u8; 64]], remaining: usize, pos: usize) -> (usize, usize, usize) {
90-
// Scans of a couple of chunks don't amortize the dispatch indirection: call the
91-
// per-architecture unconditional kernel directly so it stays inlinable (see the
92-
// size-gating note in the CpuKernel docs).
93-
if chunks.len() <= 2 {
94-
#[cfg(target_arch = "aarch64")]
95-
return scan_chunks_neon(chunks, remaining, pos);
96-
#[allow(unreachable_code)]
97-
{
98-
return scan_chunks_scalar(chunks, remaining, pos);
99-
}
100-
}
101-
102-
static KERNEL: CpuKernel<ScanChunks> = CpuKernel::new(|| {
103-
#[cfg(target_arch = "x86_64")]
104-
{
105-
if is_x86_feature_detected!("avx512f") && is_x86_feature_detected!("avx512vpopcntdq") {
106-
return scan_chunks_avx512_vpopcnt;
107-
}
108-
}
109-
#[cfg(target_arch = "aarch64")]
110-
return scan_chunks_neon;
111-
// The aarch64 arm above returns unconditionally (NEON needs no probe), making
112-
// this portable default unreachable there.
113-
#[allow(unreachable_code)]
114-
{
115-
scan_chunks_scalar
116-
}
117-
});
118-
// SAFETY: the selector only returns kernels that are safe or whose required CPU
119-
// features were probed before selection.
120-
unsafe { KERNEL.get()(chunks, remaining, pos) }
121-
}
122-
123-
#[cfg(target_arch = "aarch64")]
124-
#[allow(clippy::cast_possible_truncation)] // u64 → usize is lossless on aarch64 (64-bit)
125-
#[inline]
126-
fn scan_chunks_neon(
127-
chunks: &[[u8; 64]],
128-
mut remaining: usize,
129-
mut pos: usize,
130-
) -> (usize, usize, usize) {
131-
use std::arch::aarch64::vcntq_u8;
132-
use std::arch::aarch64::vgetq_lane_u64;
133-
use std::arch::aarch64::vld1q_u8;
134-
use std::arch::aarch64::vpaddlq_u8;
135-
use std::arch::aarch64::vpaddlq_u16;
136-
use std::arch::aarch64::vpaddlq_u32;
137-
138-
for (idx, chunk) in chunks.iter().enumerate() {
139-
let ptr = chunk.as_ptr();
140-
// SAFETY: chunk is exactly 64 bytes split across four 128-bit NEON loads.
141-
// NEON vld1q_u8 supports unaligned access.
142-
let total = unsafe {
143-
let pop_0 = vcntq_u8(vld1q_u8(ptr));
144-
let pop_1 = vcntq_u8(vld1q_u8(ptr.add(16)));
145-
let pop_2 = vcntq_u8(vld1q_u8(ptr.add(32)));
146-
let pop_3 = vcntq_u8(vld1q_u8(ptr.add(48)));
147-
let sums_0 = vpaddlq_u32(vpaddlq_u16(vpaddlq_u8(pop_0)));
148-
let sums_1 = vpaddlq_u32(vpaddlq_u16(vpaddlq_u8(pop_1)));
149-
let sums_2 = vpaddlq_u32(vpaddlq_u16(vpaddlq_u8(pop_2)));
150-
let sums_3 = vpaddlq_u32(vpaddlq_u16(vpaddlq_u8(pop_3)));
151-
152-
(vgetq_lane_u64::<0>(sums_0)
153-
+ vgetq_lane_u64::<1>(sums_0)
154-
+ vgetq_lane_u64::<0>(sums_1)
155-
+ vgetq_lane_u64::<1>(sums_1)
156-
+ vgetq_lane_u64::<0>(sums_2)
157-
+ vgetq_lane_u64::<1>(sums_2)
158-
+ vgetq_lane_u64::<0>(sums_3)
159-
+ vgetq_lane_u64::<1>(sums_3)) as usize
160-
};
161-
162-
if remaining < total {
163-
return (remaining, pos, idx);
164-
}
165-
166-
remaining -= total;
167-
pos += 512;
168-
}
169-
170-
(remaining, pos, chunks.len())
171-
}
172-
173-
#[cfg(target_arch = "x86_64")]
174-
#[target_feature(enable = "avx512f,avx512vpopcntdq")]
175-
unsafe fn scan_chunks_avx512_vpopcnt(
176-
chunks: &[[u8; 64]],
177-
mut remaining: usize,
178-
mut pos: usize,
179-
) -> (usize, usize, usize) {
180-
use std::arch::x86_64::_mm512_loadu_si512;
181-
use std::arch::x86_64::_mm512_popcnt_epi64;
182-
use std::arch::x86_64::_mm512_reduce_add_epi64;
183-
184-
use vortex_error::VortexExpect;
185-
186-
for (idx, chunk) in chunks.iter().enumerate() {
187-
// SAFETY: chunk is exactly 64 bytes. `_mm512_loadu_si512` supports unaligned access.
188-
let block = unsafe { _mm512_loadu_si512(chunk.as_ptr().cast()) };
189-
let counts = _mm512_popcnt_epi64(block);
190-
let total =
191-
usize::try_from(_mm512_reduce_add_epi64(counts)).vortex_expect("must fit in usize");
192-
193-
if remaining < total {
194-
return (remaining, pos, idx);
195-
}
196-
197-
remaining -= total;
198-
pos += 512;
199-
}
200-
201-
(remaining, pos, chunks.len())
93+
dispatch!(Level::new(), simd => scan_chunks_simd(simd, chunks, remaining, pos))
20294
}
20395

204-
#[inline]
205-
fn scan_chunks_scalar(
96+
#[simd]
97+
fn scan_chunks_simd<S: Simd>(
98+
simd: S,
20699
chunks: &[[u8; 64]],
207100
mut remaining: usize,
208101
mut pos: usize,
209102
) -> (usize, usize, usize) {
210103
for (idx, chunk) in chunks.iter().enumerate() {
211-
let total = count_ones_chunk(chunk);
104+
let words: u64x8<S> = u8x64::from_slice(simd, chunk).bitcast();
105+
let total = usize::try_from(words.count_ones().reduce_sum())
106+
.vortex_expect("chunk popcount fits in usize");
212107
if remaining < total {
213108
return (remaining, pos, idx);
214109
}
215-
216110
remaining -= total;
217111
pos += 512;
218112
}
219-
220113
(remaining, pos, chunks.len())
221114
}
222115

@@ -295,87 +188,27 @@ fn scan_words_scalar(
295188

296189
// ── In-chunk select ─────────────────────────────────────────────────────
297190

298-
type SelectInChunk = unsafe fn(&[u8; 64], usize) -> usize;
299-
300191
/// Position of the `nth` set bit inside a 64-byte chunk (0-indexed).
301192
#[inline]
302193
fn select_in_chunk(chunk: &[u8; 64], nth: usize) -> usize {
303-
static KERNEL: CpuKernel<SelectInChunk> = CpuKernel::new(|| {
304-
#[cfg(target_arch = "x86_64")]
305-
{
306-
if is_x86_feature_detected!("avx512f")
307-
&& is_x86_feature_detected!("avx512vpopcntdq")
308-
&& is_x86_feature_detected!("avx512vbmi2")
309-
{
310-
return select_in_chunk_vbmi2;
311-
}
312-
}
313-
select_in_chunk_scalar
314-
});
315-
// SAFETY: the selector only returns kernels that are safe or whose required CPU
316-
// features were probed before selection.
317-
unsafe { KERNEL.get()(chunk, nth) }
194+
dispatch!(Level::new(), simd => select_in_chunk_simd(simd, chunk, nth))
318195
}
319196

320-
#[cfg(target_arch = "x86_64")]
321-
#[target_feature(enable = "avx512f,avx512vpopcntdq,avx512vbmi2")]
322-
unsafe fn select_in_chunk_vbmi2(chunk: &[u8; 64], mut nth: usize) -> usize {
323-
use std::arch::x86_64::_mm512_loadu_si512;
324-
use std::arch::x86_64::_mm512_popcnt_epi64;
325-
use std::arch::x86_64::_mm512_storeu_epi64;
326-
327-
use vortex_error::VortexExpect;
328-
329-
let words = chunk.as_chunks::<8>().0;
330-
331-
// SAFETY: chunk is exactly 64 bytes. `_mm512_loadu_si512` supports unaligned access.
332-
let block = unsafe { _mm512_loadu_si512(chunk.as_ptr().cast()) };
333-
let counts = _mm512_popcnt_epi64(block);
334-
let mut lane_counts = [0_i64; 8];
335-
336-
// SAFETY: `lane_counts` has room for all eight i64 lanes.
337-
unsafe { _mm512_storeu_epi64(lane_counts.as_mut_ptr(), counts) };
338-
339-
for (idx, count) in lane_counts.into_iter().enumerate() {
340-
let count = usize::try_from(count).vortex_expect("must fit in usize");
341-
if nth < count {
342-
return idx * 64 + select_in_word(u64::from_le_bytes(words[idx]), nth);
343-
}
344-
nth -= count;
345-
}
346-
347-
unreachable!("select_in_chunk: nth exceeds popcount")
348-
}
349-
350-
#[inline]
351-
fn select_in_chunk_scalar(chunk: &[u8; 64], mut nth: usize) -> usize {
352-
let words = chunk.as_chunks::<8>().0;
353-
354-
for (idx, word) in words.iter().enumerate() {
355-
let word = u64::from_le_bytes(*word);
356-
let count = word.count_ones() as usize;
197+
#[simd]
198+
fn select_in_chunk_simd<S: Simd>(simd: S, chunk: &[u8; 64], mut nth: usize) -> usize {
199+
let words: [u64; 8] = std::array::from_fn(|i| u64::from_le_bytes(chunk.as_chunks::<8>().0[i]));
200+
let counts = u64x8::from_slice(simd, &words).count_ones().to_array();
201+
for (idx, count) in counts.into_iter().enumerate() {
202+
// Each lane is the popcount of a u64, hence at most 64.
203+
let count = usize::try_from(count).vortex_expect("u64 popcount fits in usize");
357204
if nth < count {
358-
return idx * 64 + select_in_word(word, nth);
205+
return idx * 64 + select_in_word(words[idx], nth);
359206
}
360207
nth -= count;
361208
}
362-
363209
unreachable!("select_in_chunk: nth exceeds popcount")
364210
}
365211

366-
#[inline]
367-
fn count_ones_chunk(chunk: &[u8; 64]) -> usize {
368-
let words = chunk.as_chunks::<8>().0;
369-
u64::from_le_bytes(words[0]).count_ones() as usize
370-
+ u64::from_le_bytes(words[1]).count_ones() as usize
371-
+ u64::from_le_bytes(words[2]).count_ones() as usize
372-
+ u64::from_le_bytes(words[3]).count_ones() as usize
373-
+ u64::from_le_bytes(words[4]).count_ones() as usize
374-
+ u64::from_le_bytes(words[5]).count_ones() as usize
375-
+ u64::from_le_bytes(words[6]).count_ones() as usize
376-
+ u64::from_le_bytes(words[7]).count_ones() as usize
377-
}
378-
379212
// ── In-word select ──────────────────────────────────────────────────────
380213

381214
type SelectInWord = unsafe fn(u64, usize) -> usize;

0 commit comments

Comments
 (0)