Documentation
¶
Overview ¶
Package bitmap is ursus's validity-bitmap layer.
The offset problem ¶
Arrow arrays carry a row offset, and that offset applies to the validity bitmap as well as to the values buffer. Slicing an array is O(1) precisely because it only bumps the offset — which means a sliced column's validity bitmap starts at an arbitrary BIT, not at a byte boundary.
This is the single most error-prone thing about writing Arrow kernels. The natural-looking code
if buf[i/8]&(1<<(i%8)) != 0 { ... }
is correct for an unsliced array and silently wrong for a sliced one, and the wrongness is data-dependent, so it survives casual testing.
This package's answer is to make the offset unforgeable. A View owns its buffer and offset in unexported fields; there is no way to obtain the raw bytes without also being handed the bit offset (RawBits), and index arithmetic is done here, once, rather than at every call site. Kernels take Views, never []byte.
Two bitmaps, not one ¶
A Boolean column has TWO bitmaps: values and validity. They have identical layout and both are Views. Conflating them is defect D13(3) in the design review — `null > 5` must be null, which needs the comparison kernel to write the value bit and the dispatcher to write the validity bit separately.
Index ¶
- func AppendSetPositions(dst []int32, a, b View) []int32
- type Builder
- type View
- func (v View) Buffer() *memory.Buffer
- func (v View) CountSet() int
- func (v View) CountUnset() int
- func (v View) Get(i int) bool
- func (v View) IsAllSet() bool
- func (v View) IsByteAligned() bool
- func (v View) Len() int
- func (v View) PopCount() int
- func (v View) RawBits() (buf []byte, bitOffset int)
- func (v View) Slice(offset, length int) View
- func (v View) Words(yield func(w uint64, nbits int) bool)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func AppendSetPositions ¶ added in v0.4.0
AppendSetPositions appends to dst every position, relative to the views, where a is set and b is too. A b with no storage is all set. Both views must have the same length.
A word at a time: a run of unset bits costs one test, and a set bit one TrailingZeros. It is how a filter's mask becomes a selection.
Types ¶
type Builder ¶
type Builder struct {
// contains filtered or unexported fields
}
Builder accumulates bits and produces a View.
Why this exists rather than direct byte indexing ¶
A SIMD comparison kernel produces its result as a movemask: one bit per lane, packed into an integer. The number of lanes is a RUNTIME property — 8 float64 lanes on AVX-512, 4 on AVX2, 2 on SSE/Neon, and 1 at a time under software emulation. On the AVX-512 development machine 8 lanes happens to be exactly one bitmap byte, which makes the naive
out[i/8] = mask.ToBits()
look correct. At 128-bit width it writes 2 bits at a time and every write after the first straddles a byte boundary, silently corrupting the bitmap. That is defect D14b from the design review, and it is invisible on the machine that wrote the code.
AppendBits removes the whole class of bug: the caller says "here are n bits" and the Builder owns the packing. It is correct at every vector width, and it is what makes the GODEBUG=simd=128 and simd=0 CI legs meaningful rather than decorative.
func NewBuilder ¶
NewBuilder returns a Builder preallocated for capBits bits.
func (*Builder) AppendBits ¶
AppendBits adds the low n bits of word, LSB first — bit 0 of word becomes the next bit of the bitmap.
LSB-first is not a choice: it is Arrow's bitmap bit order, and it is also the order archsimd's Mask.ToBits() produces (lane 0 in bit 0), which is why a mask can be appended directly with no bit reversal.
func (*Builder) AppendMany ¶
AppendMany adds n copies of v. Used for null-padding and for the all-valid case.
func (*Builder) AppendView ¶
AppendView copies another view's bits. Offset-correct by construction.
func (*Builder) Finish ¶
Finish flushes any partial byte and returns the completed view. The Builder must not be used afterwards.
Trailing bits in the final byte are left zero, which matters: Arrow permits any value there, but leaving them zero makes bitmaps byte-comparable in tests and makes a stray read past the end behave as "null" rather than as garbage.
type View ¶
type View struct {
// contains filtered or unexported fields
}
View is a read-only window onto a bit buffer.
The zero View is valid and means "all bits set" — which for a validity bitmap is "no nulls". Arrow allows omitting the validity buffer entirely when null_count is zero, and representing that as the zero value keeps the common no-nulls path allocation-free and branch-predictable.
func And ¶
And returns a AND b, allocating only when both operands are materialised.
This is the operation behind null propagation for every total binary kernel: `valid_out = valid_a AND valid_b`. It is deliberately cheap in the common case where at least one side has no nulls.
func NewView ¶
NewView wraps buf as a bitmap of length bits starting at bit offset.
The caller must not mutate buf afterwards: Views are shared freely between batches and goroutines and are assumed immutable.
func (View) Buffer ¶
Buffer returns the view's storage as an Arrow buffer for handing to array.NewData, materialising the all-set form if necessary. Returns nil for an all-set view, which is what Arrow expects when null_count is zero.
func (View) CountUnset ¶
CountUnset returns the number of clear bits, i.e. the null count.
func (View) IsAllSet ¶
IsAllSet reports whether the view is the no-storage all-set form. It does NOT scan; a materialised bitmap that happens to be all ones returns false. Use it to take a fast path, never to decide correctness.
func (View) IsByteAligned ¶
IsByteAligned reports whether the view starts on a byte boundary.
No caller today. Kept because the offset arithmetic it encapsulates is easy to get wrong by hand, and because a View that is byte-aligned admits whole-byte copies that a shifted one does not.
func (View) PopCount ¶
PopCount returns the number of set bits, using Words so it is offset-correct. Prefer CountSet, which delegates to arrow's SIMD implementation; this exists as the reference the Words iterator is tested against.
func (View) RawBits ¶
RawBits exposes the backing buffer and this view's bit offset together, so a word-at-a-time kernel can use them without being able to forget the offset. Returns (nil, 0) for the all-set form.
func (View) Slice ¶
Slice returns bits [offset, offset+length) of v, composing the bit offsets. This is the only correct way to slice a bitmap and is O(1).
func (View) Words ¶
Words iterates the view as 64-bit little-endian words, LSB = lowest bit index, shifting to normalise away any bit offset. The final word is zero-padded above v.length bits; nbits reports how many bits of it are live.
This is the abstraction that makes offset handling a solved problem rather than a recurring bug: a kernel written against Words is correct for sliced and unsliced input alike, at every vector width.
Source Files