sroar

package module
v0.0.16 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 28, 2026 License: Apache-2.0 Imports: 10 Imported by: 15

README

sroar: Serialized Roaring Bitmaps

sroar is a re-written version of Roaring Bitmaps in Go, with the aim to have equality between in-memory representation and on-disk representation. An sroar.Bitmap does not need to be marshalled or unmarshalled, as the underlying represetation is a byte slice. Therefore, it can be written to disk, brought to memory, or shipped over the network immediately. This is needed in Dgraph, where we need to deal with lots of bitmaps.

sroar only implements array and bitmap containers. It does NOT implement run containers, which is an optimization that RoaringBitmaps has. Despite that, it outperforms RoaringBitmaps as shown in the Benchmarks section.

The code borrows concepts and code from RoaringBitmaps.

Benchmarks

The benchmarks were run:

  • Using real data set as described in RoaringBitmaps.
  • Only on the 64-bit version of roaring bitmaps (roaring64).
  • Only on FastOr, which is the more expensive operation than And or equivalent.
  • On AMD Ryzen Threadripper 2950X 16-Core Processor.
  • Using Go benchmarks serially.

Based on the benchmarks, sroar is:

  • 6.5x faster (-85% p50) for benchmarks >1ms, uses
  • 15x (-93.5% p50) less memory for allocations >1MB.
  • 25x fewer allocations.

The benchmark command and the results are:

$ go test -bench BenchmarkRealDataFastOr --run=XXX --count=5 --benchmem

name CPU                                    old time/op    new time/op    delta
RealDataFastOr/census1881-32                 302ms ± 2%       2ms ± 3%   -99.29%  (p=0.008 n=5+5)
RealDataFastOr/wikileaks-noquotes-32        76.5ms ± 1%     0.9ms ± 1%   -98.83%  (p=0.008 n=5+5)
RealDataFastOr/wikileaks-noquotes_srt-32    34.8ms ± 5%     1.0ms ± 2%   -97.07%  (p=0.008 n=5+5)
RealDataFastOr/dimension_033-32             55.0ms ± 3%     2.7ms ± 0%   -95.16%  (p=0.016 n=5+4)
RealDataFastOr/census1881_srt-32            36.8ms ± 3%     2.9ms ± 1%   -92.13%  (p=0.008 n=5+5)
RealDataFastOr/dimension_003-32             50.4ms ± 1%    11.6ms ± 4%   -77.06%  (p=0.008 n=5+5)
RealDataFastOr/dimension_008-32             10.0ms ± 2%     3.7ms ± 2%   -62.69%  (p=0.008 n=5+5)
RealDataFastOr/weather_sept_85_srt-32       6.13ms ± 3%    2.72ms ± 2%   -55.66%  (p=0.008 n=5+5)
RealDataFastOr/census-income-32             1.70ms ± 3%    1.05ms ± 1%   -38.53%  (p=0.008 n=5+5)
RealDataFastOr/weather_sept_85-32           2.28ms ± 2%    4.07ms ± 2%   +78.52%  (p=0.008 n=5+5)

RealDataFastOr/uscensus2000-32               556µs ± 2%     791µs ± 1%   +42.17%  (p=0.008 n=5+5)
RealDataFastOr/census-income_srt-32          260µs ± 4%     986µs ± 2%  +279.09%  (p=0.008 n=5+5)

name MEM_BYTES                             old alloc/op   new alloc/op   delta
RealDataFastOr/census1881-32                 585MB ± 0%       1MB ± 0%   -99.75%  (p=0.008 n=5+5)
RealDataFastOr/wikileaks-noquotes-32        76.3MB ± 0%     0.6MB ± 0%   -99.24%  (p=0.008 n=5+5)
RealDataFastOr/wikileaks-noquotes_srt-32    22.8MB ± 0%     0.6MB ± 0%   -97.46%  (p=0.008 n=5+5)
RealDataFastOr/census1881_srt-32            15.3MB ± 0%     1.4MB ± 0%   -90.58%  (p=0.008 n=5+5)
RealDataFastOr/dimension_003-32             7.78MB ± 0%    1.44MB ± 0%   -81.49%  (p=0.008 n=5+5)
RealDataFastOr/dimension_033-32             1.10MB ± 0%    1.44MB ± 0%   +30.92%  (p=0.008 n=5+5)

RealDataFastOr/dimension_008-32              537kB ± 0%      97kB ± 0%   -81.94%  (p=0.008 n=5+5)
RealDataFastOr/census-income-32              187kB ± 0%      70kB ± 0%   -62.86%  (p=0.008 n=5+5)
RealDataFastOr/census-income_srt-32         99.1kB ± 0%    69.6kB ± 0%   -29.81%  (p=0.008 n=5+5)
RealDataFastOr/weather_sept_85_srt-32        375kB ± 0%     292kB ± 0%   -21.95%  (p=0.008 n=5+5)
RealDataFastOr/uscensus2000-32               169kB ± 0%     231kB ± 0%   +36.97%  (p=0.008 n=5+5)
RealDataFastOr/weather_sept_85-32            169kB ± 0%     292kB ± 0%   +72.93%  (p=0.008 n=5+5)

name MEM_ALLOCS                           old allocs/op  new allocs/op  delta
RealDataFastOr/census1881_srt-32             29.7k ± 0%      0.0k ± 0%   -99.91%  (p=0.008 n=5+5)
RealDataFastOr/wikileaks-noquotes_srt-32     6.06k ± 0%     0.02k ± 0%   -99.74%  (p=0.008 n=5+5)
RealDataFastOr/dimension_003-32              4.57k ± 0%     0.03k ± 2%   -99.42%  (p=0.008 n=5+5)
RealDataFastOr/dimension_033-32              4.33k ± 0%     0.03k ± 0%   -99.38%  (p=0.000 n=5+4)
RealDataFastOr/uscensus2000-32               1.75k ± 0%     0.06k ± 0%   -96.85%  (p=0.008 n=5+5)
RealDataFastOr/dimension_008-32                704 ± 0%        23 ± 3%   -96.79%  (p=0.008 n=5+5)
RealDataFastOr/census-income-32                271 ± 0%         9 ± 0%   -96.68%  (p=0.008 n=5+5)
RealDataFastOr/weather_sept_85_srt-32          248 ± 0%        14 ± 0%   -94.35%  (p=0.008 n=5+5)
RealDataFastOr/weather_sept_85-32             81.0 ± 0%      14.0 ± 0%   -82.72%  (p=0.008 n=5+5)
RealDataFastOr/census-income_srt-32           40.0 ± 0%       9.0 ± 0%   -77.50%  (p=0.008 n=5+5)
RealDataFastOr/census1881-32                 54.5k ± 0%      0.0k ± 0%      ~     (p=0.079 n=4+5)
RealDataFastOr/wikileaks-noquotes-32         39.2k ± 0%      0.0k ± 0%      ~     (p=0.079 n=4+5)

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Accumulator added in v0.0.16 

type Accumulator struct {
	// contains filtered or unexported fields
}

Accumulator combines many bitmaps into one by depositing their elements into dense per-key staging containers instead of merging roaring structures pairwise. Merging N tiny bitmaps via Or/FastOr costs a structural container merge per source — for array containers that is an O(container size) memmove to insert even a single element, which makes N-way unions of near-singleton bitmaps quadratic in the source count. The accumulator makes every deposit O(1) by staging each touched 64K key range in one fixed-size dense block, then assembling the exact-size result once (Bitmap, BitmapToBuf or InitBitmapToBuf).

Total cost is O(total input elements + touched key ranges); staging memory is one 8KB block per touched key range (proportional to the spread of the result, not to the number of sources). In the sparse extreme — every element in its own range — that degrades to ~8KB per element, staging orders of magnitude more memory than the result it builds; FastOr or sort+FromSortedList are the better tools there. Reset caps only what is retained between unions, never the peak during one. Within one source, keys ascend, so its new ranges append cheaply; across sources, each new range that arrives out of order pays an O(existing ranges) insertion shift, so unions spanning many ranges fed from unsorted sources approach O(ranges²) in that term.

Usage: 

acc := NewAccumulator()
for _, bm := range sources {
	acc.Or(bm)
}
result := acc.Bitmap()

Or never retains its argument, so callers may release or reuse a source's memory as soon as Or returns. The zero Accumulator is ready to use; NewAccumulator is equivalent. An Accumulator is not safe for concurrent use.

func NewAccumulator added in v0.0.16 

func NewAccumulator() *Accumulator

func (*Accumulator) Bitmap added in v0.0.16 

func (acc *Accumulator) Bitmap() *Bitmap

Bitmap assembles and returns the union. The accumulator keeps its staging state afterwards; call Reset to reuse it for a new union.

func (*Accumulator) BitmapToBuf added in v0.0.16 

func (acc *Accumulator) BitmapToBuf(get func(sizeBytes int) []byte) *Bitmap

BitmapToBuf assembles the union into a buffer obtained from get — for callers that pool result memory — and returns a bitmap backed by it. get is called exactly once, with the exact required size in bytes, and must not itself use the accumulator (doing so panics). Returning a buffer smaller than the requested size panics — the caller was told exactly how much is needed. The buffer is adopted to its full capacity (rounded down to even), not just its length — a length-limited view of a larger backing array hands the whole backing array to the result. The returned bitmap holds a reference to the buffer, so the buffer must not be reused until the bitmap is released. Mutating the result stays within the buffer's capacity until it needs to grow, at which point it migrates to the heap.

func (*Accumulator) InitBitmapToBuf added in v0.0.16 

func (acc *Accumulator) InitBitmapToBuf(get func(sizeBytes int) (*Bitmap, []byte)) *Bitmap

InitBitmapToBuf is BitmapToBuf for callers that pool the result Bitmap struct together with its buffer: get returns both — typically from one pool entry — and the union is built into them, so a warm accumulator building into pooled memory allocates nothing. The struct must be non-nil; its previous fields are overwritten, never freed — it must not own anything the caller still needs. A buffer smaller than the requested size panics, as in BitmapToBuf.

func (*Accumulator) Or added in v0.0.16 

func (acc *Accumulator) Or(bm *Bitmap)

Or deposits all elements of bm into the accumulator. bm is only read, never retained: it may be released or reused as soon as Or returns.

func (*Accumulator) Reset added in v0.0.16 

func (acc *Accumulator) Reset()

Reset clears the accumulator for reuse. Up to maxRetainedBlocks staging blocks are cleared and kept as key-independent spares for the next union's ranges, whatever they are; everything else is released, so a pooled accumulator's memory and per-union cost stay bounded by the current union, not by every range it has ever served. Reset bounds retained memory only — the peak during a union is whatever its spread demands.

type Bitmap 

type Bitmap struct {
	// contains filtered or unexported fields
}

func And 

func And(a, b *Bitmap) *Bitmap

func AndNot added in v0.0.5 

func AndNot(a, b *Bitmap) *Bitmap

func AndOld added in v0.0.5 

func AndOld(a, b *Bitmap) *Bitmap

func CopresenceByMask added in v0.0.14 

func CopresenceByMask(bms []*Bitmap, mask uint64) *Bitmap

CopresenceByMask returns a new bitmap containing every value v in the union of bms whose masked value (v & mask) is present in bms[i].Masked(mask) for every i. Original (unmasked) values are preserved. Equivalent in result to the (much more expensive) fold: 

out := bms[0].Masked(mask)
for i := 1; i < len(bms); i++ {
    out = out.And(bms[i].Masked(mask))
}
// then map each masked value back to every original v in any bms[i]
// whose v & mask matches.

but processes all inputs in one pass — avoiding intermediate bitmap allocations and walking each input only once. None of the bms are modified.

Mask shape requirement: mask & 0xFFFF == 0xFFFF. Other mask shapes are not supported and will yield incorrect results.

Edge cases:

  • len(bms) == 0: empty result.
  • len(bms) == 1: result is a clone of bms[0] (single-input co-presence is trivially the input).
  • any input empty: empty result.

Algorithm: with mask_high = mask & 0xFFFFFFFFFFFF0000, group each input's containers by K & mask_high. Walk the masked-key entry slices of all N inputs in lockstep (multi-pointer max-key advance) to find groups present on every side. For each such group:

  1. compute pos_i = OR of positions across input i's containers in the group
  2. common_pos = AND_i (pos_i) — positions co-present in every side
  3. for each unique original key K appearing in any input's group, emit OR_i(bms[i][K]) AND common_pos at K (omitting empty results)

Step 2 short-circuits as soon as common_pos becomes empty.

func CopresenceByMaskToBuf added in v0.0.14 

func CopresenceByMaskToBuf(bms []*Bitmap, mask uint64, buf []byte) *Bitmap

CopresenceByMaskToBuf is like CopresenceByMask but uses the provided byte slice as the underlying buffer for the result bitmap, avoiding the result's heap allocation when the buffer is large enough. If the buffer is too small the bitmap grows internally (and allocates), so correctness is unaffected — only the allocation-elision is.

Sizing guidance: a safe upper bound is the sum of input byte sizes (sum_i bms[i].LenInBytes()). The result's keys area is bounded by the sum of input keys areas, and each result container is bounded by the sum of its contributing inputs' containers (the per-key OR can't exceed it; the subsequent AND with commonPos can only shrink). In practice results are often much smaller — callers that know their workload's typical density can pass a smaller buffer and accept occasional growth.

Same mask shape requirement as CopresenceByMask: mask & 0xFFFF == 0xFFFF.

func FastAnd 

func FastAnd(bitmaps ...*Bitmap) *Bitmap

func FastOr 

func FastOr(bitmaps ...*Bitmap) *Bitmap

FastOr would merge given Bitmaps into one Bitmap. This is faster than doing an OR over the bitmaps iteratively.

func FastParOr 

func FastParOr(numGo int, bitmaps ...*Bitmap) *Bitmap

FastParOr would group up bitmaps and call FastOr on them concurrently. It would then merge the groups into final Bitmap. This approach is simpler and faster than operating at a container level, because we can't operate on array containers belonging to the same Bitmap concurrently because array containers can expand, leaving no clear boundaries.

If FastParOr is called with numGo=1, it just calls FastOr.

Experiments with numGo=4 shows that FastParOr would be 2x the speed of FastOr, but 4x the memory usage, even under 50% CPU usage. So, use wisely.

func FromBuffer 

func FromBuffer(data []byte) *Bitmap

FromBuffer returns a pointer to bitmap corresponding to the given buffer. This bitmap shouldn't be modified because it might corrupt the given buffer.

func FromBufferUnlimited added in v0.0.10 

func FromBufferUnlimited(buf []byte) *Bitmap

FromBufferUnlimited returns a pointer to bitmap corresponding to the given buffer. Entire buffer capacity is utlized for future bitmap modifications and expansions.

func FromBufferWithCopy 

func FromBufferWithCopy(src []byte) *Bitmap

FromBufferWithCopy creates a copy of the given buffer and returns a bitmap based on the copied buffer. This bitmap is safe for both read and write operations.

func FromSortedList 

func FromSortedList(vals []uint64) *Bitmap

func InitFromBufferUnlimited added in v0.0.16 

func InitFromBufferUnlimited(dst *Bitmap, buf []byte) *Bitmap

InitFromBufferUnlimited re-points dst at buf — the in-place equivalent of FromBufferUnlimited. dst's previous content is discarded, never freed. A buf too small for even the empty bitmap (under 8 bytes) falls back to a heap allocation. Returns dst.

func MaskedAnd added in v0.0.14 

func MaskedAnd(a, b *Bitmap, mask uint64) *Bitmap

MaskedAnd returns a new bitmap containing the AND of a and b, with mask applied to all keys. Keys that become equal after masking have their containers merged via OR. This is equivalent to Masked(And(a, b), mask) but allocates only one bitmap instead of two. Neither a nor b is modified. The lowest 16 bits of keys are always zeroed.

func MaskedAndToBuf added in v0.0.14 

func MaskedAndToBuf(a, b *Bitmap, mask uint64, buf []byte) *Bitmap

MaskedAndToBuf is like MaskedAnd but uses the provided byte slice as the underlying buffer for the result bitmap, avoiding heap allocation when the buffer is large enough. The lowest 16 bits of keys are always zeroed.

func NewBitmap 

func NewBitmap() *Bitmap

func NewBitmapToBuf added in v0.0.14 

func NewBitmapToBuf(buf []byte) *Bitmap

NewBitmapToBuf creates a new bitmap using the provided byte slice as the underlying data buffer. If the buffer is too small to hold the initial bitmap structure, a heap-allocated bitmap is returned instead. The _ptr field is set to keep a GC reference to buf, since the bitmap operates on an unsafe []uint16 view of the same memory.

func NewBitmapWith 

func NewBitmapWith(numKeys int) *Bitmap

func Or 

func Or(a, b *Bitmap) *Bitmap

func OrOld added in v0.0.5 

func OrOld(a, b *Bitmap) *Bitmap

func Prefill added in v0.0.9 

func Prefill(maxX uint64) *Bitmap

Prefill creates bitmap prefilled with elements [0-maxX]

func (*Bitmap) And 

func (ra *Bitmap) And(bm *Bitmap) *Bitmap

And performs in-place AND of ra and bm (ra &= bm). ra drives the two-pointer walk: ra containers with no matching bm key must be zeroed out, so every ra container must be visited.

func (*Bitmap) AndConc added in v0.0.9 

func (ra *Bitmap) AndConc(bm *Bitmap, maxConcurrency int) *Bitmap

AndConc performs And merge concurrently (ra &= bm). ra drives the walk: every ra container must be visited to zero out those with no matching bm key. Concurrency is calculated based on number of internal containers in ra, so that each goroutine handles at least [minContainersPerRoutine] containers. maxConcurrency limits concurrency calculated internally. If maxConcurrency <= 0, then calculated concurrency is not limited.

E.g.: dst bitmap has 100 containers. Internal concurrency = 100/24 = 4. For: - maxConcurrency = 2, there will be 2 goroutines executed - maxConcurrency = 6, there will be 4 goroutines executed

func (*Bitmap) AndMasked added in v0.0.14 

func (ra *Bitmap) AndMasked(b *Bitmap, mask uint64) *Bitmap

AndMasked is equivalent to ra.And(b.Masked(mask)) but avoids allocating an intermediate masked bitmap. b is not modified.

For each key k in ra, AndMasked finds all keys k' in b where k'&mask == k, ORs their containers together, then ANDs the result into ra's container at k. If no key in b maps to k under the mask, ra's container at k is zeroed out. The lowest 16 bits of the mask are always ignored.

func (*Bitmap) AndMaskedConc added in v0.0.14 

func (ra *Bitmap) AndMaskedConc(b *Bitmap, mask uint64, maxConcurrency int) *Bitmap

AndMaskedConc is like AndMasked but processes ra's containers concurrently. Concurrency is calculated based on number of internal containers in ra, so that each goroutine handles at least [minContainersPerRoutine] containers. maxConcurrency limits concurrency calculated internally. If maxConcurrency <= 0, then calculated concurrency is not limited.

func (*Bitmap) AndNot 

func (ra *Bitmap) AndNot(bm *Bitmap) *Bitmap

AndNot performs in-place AND-NOT of ra and bm (ra &^= bm). Neither bitmap has unmatched containers requiring mandatory action: unmatched ra containers are kept, unmatched bm containers are irrelevant. The smaller bitmap drives for a minor sequential optimisation.

func (*Bitmap) AndNotConc added in v0.0.9 

func (ra *Bitmap) AndNotConc(bm *Bitmap, maxConcurrency int) *Bitmap

AndNotConc performs AndNot merge concurrently (ra &^= bm). Neither bitmap has unmatched containers requiring mandatory action, so the smaller bitmap drives to minimise goroutine count. Concurrency is calculated based on number of internal containers in the smaller bitmap, so that each goroutine handles at least [minContainersPerRoutine] containers. maxConcurrency limits concurrency calculated internally. If maxConcurrency <= 0, then calculated concurrency is not limited.

E.g.: smaller bitmap has 100 containers. Internal concurrency = 100/24 = 4. For: - maxConcurrency = 2, there will be 2 goroutines executed - maxConcurrency = 6, there will be 4 goroutines executed

func (*Bitmap) AndNotOld added in v0.0.5 

func (ra *Bitmap) AndNotOld(bm *Bitmap)

func (*Bitmap) AndOld added in v0.0.5 

func (ra *Bitmap) AndOld(bm *Bitmap)

func (*Bitmap) Cleanup 

func (ra *Bitmap) Cleanup()

func (*Bitmap) Clone 

func (ra *Bitmap) Clone() *Bitmap

func (*Bitmap) CloneToBuf added in v0.0.9 

func (ra *Bitmap) CloneToBuf(buf []byte) *Bitmap

func (*Bitmap) Contains 

func (ra *Bitmap) Contains(x uint64) bool

func (*Bitmap) ConvertToBitmapContainers added in v0.0.3 

func (ra *Bitmap) ConvertToBitmapContainers()

func (*Bitmap) Debug 

func (ra *Bitmap) Debug(x uint64) string

func (*Bitmap) FillUp added in v0.0.9 

func (ra *Bitmap) FillUp(maxX uint64)

FillUp fill bitmap with elements (maximum-maxX], where maximum means last element. If bitmap is empty then [0-maxX] elements are added (reusing underlying data slice if big enough to fit all elements). If last element is >= than given maxX nothing is done.

func (*Bitmap) GetCardinality 

func (ra *Bitmap) GetCardinality() int

func (*Bitmap) InitCloneToBuf added in v0.0.16 

func (src *Bitmap) InitCloneToBuf(dst *Bitmap, buf []byte) *Bitmap

InitCloneToBuf re-initializes dst over buf with a clone of src — the in-place equivalent of CloneToBuf. dst's previous content is discarded, never freed. A nil or zero-value src yields an empty bitmap over buf; a buf too small for the clone panics, too small for even the empty bitmap falls back to a heap allocation. Returns dst.

func (*Bitmap) Intersects added in v0.0.14 

func (ra *Bitmap) Intersects(bm *Bitmap) bool

Intersects reports whether ra and bm share at least one element. Equivalent to !ra.Clone().And(bm).IsEmpty() but short-circuits at the first common element without allocating a result bitmap.

func (*Bitmap) IntersectsMasked added in v0.0.14 

func (ra *Bitmap) IntersectsMasked(bm *Bitmap, mask uint64) bool

IntersectsMasked reports whether ra and bm share at least one element after applying mask to bm's keys. Equivalent to !ra.Clone().And(bm.Masked(mask)).IsEmpty() but short-circuits at the first common element without allocating. Containers in ra whose key has a non-zero dimension (low 16 bits != 0) are not checked — same behaviour as AndMasked.

func (*Bitmap) IsEmpty 

func (ra *Bitmap) IsEmpty() bool

func (*Bitmap) LenInBytes added in v0.0.9 

func (ra *Bitmap) LenInBytes() int

func (*Bitmap) ManyIterator 

func (r *Bitmap) ManyIterator() *ManyItr

TODO: See if this is needed, we should remove this

func (*Bitmap) Masked added in v0.0.14 

func (ra *Bitmap) Masked(mask uint64) *Bitmap

Masked applies the given mask to every key and returns a new bitmap. Keys that collapse to the same masked value have their containers merged via container-level OR operations.

func (*Bitmap) MaskedToBuf added in v0.0.14 

func (ra *Bitmap) MaskedToBuf(mask uint64, buf []byte) *Bitmap

MaskedToBuf is like Masked but uses the provided byte slice as the underlying buffer for the result bitmap, avoiding heap allocation when the buffer is large enough.

func (*Bitmap) Maximum 

func (ra *Bitmap) Maximum() uint64

func (*Bitmap) Minimum 

func (ra *Bitmap) Minimum() uint64

func (*Bitmap) NewContainsCursor added in v0.0.15 

func (ra *Bitmap) NewContainsCursor() *ContainsCursor

NewContainsCursor returns a cursor bound to ra. A nil ra (or nil cursor) reports false, matching Bitmap.Contains.

func (*Bitmap) NewIterator 

func (bm *Bitmap) NewIterator() *Iterator

func (*Bitmap) NewRangeIterators 

func (bm *Bitmap) NewRangeIterators(numRanges int) []*Iterator

func (*Bitmap) NumContainers added in v0.0.14 

func (ra *Bitmap) NumContainers() int

func (*Bitmap) Or 

func (ra *Bitmap) Or(bm *Bitmap) *Bitmap

Or performs in-place OR of ra and bm (ra |= bm). bm drives the two-pointer walk: bm containers with no matching ra key must be added to ra, so every bm container must be visited. Ra containers with no matching bm key are left unchanged — no visit required.

func (*Bitmap) OrConc added in v0.0.9 

func (ra *Bitmap) OrConc(bm *Bitmap, maxConcurrency int) *Bitmap

OrConc performs Or merge concurrently (ra |= bm). bm drives the walk: every bm container must be visited to add those with no matching ra key. Concurrency is calculated based on number of internal containers in bm, so that each goroutine handles at least [minContainersPerRoutine] containers. maxConcurrency limits concurrency calculated internally. If maxConcurrency <= 0, then calculated concurrency is not limited.

E.g.: src bitmap has 100 containers. Internal concurrency = 100/24 = 4. For: - maxConcurrency = 2, there will be 2 goroutines executed - maxConcurrency = 6, there will be 4 goroutines executed

func (*Bitmap) OrOld added in v0.0.5 

func (dst *Bitmap) OrOld(src *Bitmap)

TODO: Check if we want to use lazyMode

func (*Bitmap) Rank 

func (ra *Bitmap) Rank(x uint64) int

func (*Bitmap) Remove 

func (ra *Bitmap) Remove(x uint64) bool

func (*Bitmap) RemoveRange 

func (ra *Bitmap) RemoveRange(lo, hi uint64)

Remove range removes [lo, hi) from the bitmap.

func (*Bitmap) Reset 

func (ra *Bitmap) Reset()

func (*Bitmap) Select 

func (ra *Bitmap) Select(x uint64) (uint64, error)

Select returns the element at the xth index. (0-indexed)

func (*Bitmap) Set 

func (ra *Bitmap) Set(x uint64) bool

func (*Bitmap) SetMany 

func (ra *Bitmap) SetMany(vals []uint64)

TODO: Potentially this can be optimized.

func (*Bitmap) Split 

func (bm *Bitmap) Split(externalSize func(start, end uint64) uint64, maxSz uint64) []*Bitmap

Split splits the bitmap based on maxSz and the externalSize function. It splits the bitmap such that size of each split bitmap + external size corresponding to its elements approximately equal to maxSz (it can be greater than maxSz sometimes). The splits are returned in sorted order. externalSize is a function that should return the external size corresponding to elements in range [start, end]. External size is used to calculate the split boundaries.

func (*Bitmap) String 

func (ra *Bitmap) String() string

func (*Bitmap) ToArray 

func (ra *Bitmap) ToArray() []uint64

func (*Bitmap) ToBuffer 

func (ra *Bitmap) ToBuffer() []byte

func (*Bitmap) ToBufferWithCopy 

func (ra *Bitmap) ToBufferWithCopy() []byte

func (*Bitmap) ZeroOut added in v0.0.13 

func (ra *Bitmap) ZeroOut()

type ContainsCursor added in v0.0.15 

type ContainsCursor struct {
	// contains filtered or unexported fields
}

ContainsCursor accelerates repeated Contains on a fixed Bitmap when successive probes have locality: it returns the identical result to Bitmap.Contains for any x in any order, and is cheapest when probes repeat the previous container or advance past it (same-container repeats skip the key search; forward moves gallop from the cached position at both the container and the array-value level; backward moves fall back to the plain search).

Not safe for concurrent use; the bound Bitmap must not be mutated while the cursor is live.

func (*ContainsCursor) Contains added in v0.0.15 

func (cur *ContainsCursor) Contains(x uint64) bool

Contains reports whether x is set, for any x in any order (cheapest when x repeats the previous container or advances past it).

func (*ContainsCursor) NextGeq added in v0.0.15 

func (cur *ContainsCursor) NextGeq(x uint64) (uint64, bool)

NextGeq returns the smallest set value >= x and whether one exists. It shares the cursor's cache and leaves the cursor positioned on the returned value, so interleaving Contains and NextGeq with non-decreasing arguments keeps both on their fast paths. This is the successor primitive for leapfrog intersection: instead of probing candidates one by one, a caller can jump directly to the bitmap's next admissible value.

func (*ContainsCursor) Reset added in v0.0.15 

func (cur *ContainsCursor) Reset(ra *Bitmap)

Reset re-binds the cursor to ra and clears its cache, letting callers embed a ContainsCursor by value and prime it without a heap allocation.

type Iterator 

type Iterator struct {
	// contains filtered or unexported fields
}

func (*Iterator) Next 

func (it *Iterator) Next() uint64

type ManyItr 

type ManyItr struct {
	// contains filtered or unexported fields
}

func (*ManyItr) NextMany 

func (itr *ManyItr) NextMany(buf []uint64) int

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.