Drafted by Claude Code on Connor's behalf, and not yet edited by him.
encodings/sequence/src/compute/compare.rs:59 finds the single index where const appears in an arithmetic sequence, then builds the result with a per-row predicate:
let buffer = BitBuffer::from_iter((0..lhs.len()).map(|idx| idx == set_idx));
The kernel already knows the answer is "all false except set_idx", so this spends O(len) closure calls and branches to set one bit, where a zeroed buffer plus one store is O(len / 64).
BitBuffer::from_iter also goes bit at a time, though it does pre-allocate new_unset(len) and write only the true bits, so it's not as bad as it looks for a single set bit. Note that vortex-buffer's own docs point at BitBuffer::collect_bool as the preferred entry point for every predicate.
This call site is not benchmarked. For scale, the bit-at-a-time path measured 6.6x to 7.9x slower than BitBuffer::from(vec) (which routes to the multiversioned byte-to-bit packer) for an owned Vec<bool> of 64Ki to 1Mi elements, in a different kernel.
Two options:
- Build it directly:
BitBufferMut::new_unset(lhs.len()), then set(set_idx), then freeze().
- Swap to
BitBuffer::collect_bool(lhs.len(), |idx| idx == set_idx). Smaller diff, but still O(len) closure calls.
(1) says what the kernel means and is the cheaper of the two. Either way it's worth a quick benchmark, since the magnitude here is a guess.
Open question: should BitBuffer::from_iter delegate to the packer when the iterator reports an exact size hint? That would fix the class at the source, though how many real call sites there are is unclear...
Drafted by Claude Code on Connor's behalf, and not yet edited by him.
encodings/sequence/src/compute/compare.rs:59finds the single index whereconstappears in an arithmetic sequence, then builds the result with a per-row predicate:The kernel already knows the answer is "all false except
set_idx", so this spendsO(len)closure calls and branches to set one bit, where a zeroed buffer plus one store isO(len / 64).BitBuffer::from_iteralso goes bit at a time, though it does pre-allocatenew_unset(len)and write only thetruebits, so it's not as bad as it looks for a single set bit. Note thatvortex-buffer's own docs point atBitBuffer::collect_boolas the preferred entry point for every predicate.This call site is not benchmarked. For scale, the bit-at-a-time path measured 6.6x to 7.9x slower than
BitBuffer::from(vec)(which routes to the multiversioned byte-to-bit packer) for an ownedVec<bool>of 64Ki to 1Mi elements, in a different kernel.Two options:
BitBufferMut::new_unset(lhs.len()), thenset(set_idx), thenfreeze().BitBuffer::collect_bool(lhs.len(), |idx| idx == set_idx). Smaller diff, but stillO(len)closure calls.(1) says what the kernel means and is the cheaper of the two. Either way it's worth a quick benchmark, since the magnitude here is a guess.
Open question: should
BitBuffer::from_iterdelegate to the packer when the iterator reports an exact size hint? That would fix the class at the source, though how many real call sites there are is unclear...