boolmark

Faster unique-value extraction for bounded-integer arrays, on CPU and GPU.

boolmark replaces sort-based unique() with direct boolean existence marking for the common case where your values are integers in a known, bounded range — category IDs, vocabulary tokens, pixel labels, user IDs mapped to a dense range, and similar.

pip install boolmark          # CPU only
pip install boolmark[gpu]     # + GPU support (CUDA 11.x)
# For CUDA 12.x: pip install boolmark cupy-cuda12x
# Check your CUDA version with: nvidia-smi

import numpy as np
from boolmark import unique

arr = np.array([3, 1, 3, 0, 2, 1])
unique(arr)
# array([0, 1, 2, 3])

from boolmark import unique_gpu

arr = np.random.randint(0, 50_000, size=100_000_000)
result = unique_gpu(arr)   # +8% to +30% faster than cp.unique() on T4

The idea, in one paragraph

np.unique() and cp.unique() solve this by sorting the whole array first, then scanning for adjacent duplicates — O(n log n) work. But if you only need to know which values are present, not their relative order against every other element, you don't need to sort at all. Use each integer value directly as an array index: flip a boolean flag at that position. After one pass, the flags tell you exactly what's present — O(n + k) work, and on GPU, zero atomic operations, because writing True to an already- True slot from multiple threads simultaneously is always safe (True OR True = True). Full explanation with a worked example: boolmark/core.py docstring, or REPORT.md §2.

Is this novel?

Partially, stated honestly. The mark-then-compact pattern itself is a classical parallel-algorithms technique (Blelloch 1990; Harris, Sengupta, Owens — GPU Gems 3, 2007). Bitmap indices in databases use the same idempotent-write property. This package does not claim to have invented a new data structure.

What's specific to this work: applying that classical pattern to displace sort-based unique() for bounded integers, and measuring that displacement rigorously — orthogonal test design (range size and duplication varied independently, not confounded), 30 trials per configuration, Welch's t-test for statistical significance, and honest reporting of where it does not help. Full methodology and raw data: REPORT.md.

Benchmark summary

When NOT to use this

• Floats, strings, unbounded integers → use np.unique() / cp.unique().
• Range k > 10,000,000 → memory cost of the boolean array gets large; use library implementations.
• Small n (<1M) with tiny k (~100) → GPU transfer overhead dominates; plain CPU np.unique() wins here.
• You need frequency counts, not just existence → this discards counts by design; use np.bincount().
• You're on Ampere/Hopper/Ada and need guaranteed numbers → not yet independently validated on those architectures.

API

boolmark.unique(arr, max_range=10_000_000) -> np.ndarray

boolmark.unique_gpu(arr, max_range=10_000_000, return_numpy=True) -> np.ndarray | cp.ndarray

boolmark.estimate_speedup_regime(n, k) -> str

All functions raise BooleanMarkError explicitly on unsuitable input (wrong dtype, empty array, oversized range) rather than silently guessing or returning a misleading result.

Contributing

The single most valuable contribution right now is benchmark data from a GPU architecture other than Tesla T4. Run benchmarks/run_benchmark.py on your hardware and open a PR with the output JSON.

Citation

@misc{boolmark2026,
  title  = {boolmark: Boolean-Marking Unique Extraction for Bounded-Integer Arrays},
  author = {Hanish Kumar},
  year   = {2026},
  url    = {https://github.com/Hanish9193/boolmark}
}

License

MIT