Metadata-Version: 2.4
Name: boolmark
Version: 0.1.0
Summary: Faster unique-value extraction for bounded-integer arrays (CPU + GPU)
Project-URL: Homepage, https://github.com/Hanish9193/boolmark
Project-URL: Repository, https://github.com/Hanish9193/boolmark
Project-URL: Report, https://github.com/Hanish9193/boolmark/blob/main/REPORT.md
Project-URL: Issues, https://github.com/Hanish9193/boolmark/issues
Author-email: Hanish Kumar <hanish.kumar9193@gmail.com>
License-Expression: MIT
License-File: LICENSE
Keywords: cuda,cupy,gpu,parallel-algorithms,sorting,unique
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Requires-Python: >=3.9
Requires-Dist: numpy>=1.21
Provides-Extra: dev
Requires-Dist: pytest-cov; extra == 'dev'
Requires-Dist: pytest>=7.0; extra == 'dev'
Provides-Extra: gpu
Requires-Dist: cupy-cuda11x>=11.0.0; extra == 'gpu'
Description-Content-Type: text/markdown

# 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.

```bash
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
```

```python
import numpy as np
from boolmark import unique

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

```python
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`](boolmark/core.py) docstring, or
[REPORT.md](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](REPORT.md).

## Benchmark summary

| | Result |
|---|---|
| Test matrix | 16 configs, k × duplication ratio independently varied |
| Significance | 16/16 statistically significant wins (p<0.0001, 30 trials each) |
| Speedup vs CuPy/Thrust | +8.2% to +29.5% (mean +20.5%) |
| GPU-resident speedup | 2.51× (data already on GPU, transfer eliminated) |
| Hardware validated | NVIDIA Tesla T4 (Turing). *(2nd architecture pending — see Contributing)* |
| Correctness | 100% match vs `np.unique()` across all trials, zero mismatches |

## 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

```python
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`](benchmarks/run_benchmark.py) on your
hardware and open a PR with the output JSON.

## Citation

```bibtex
@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
