Skip to content

README.md

Latest commit

 

History

History
2237 lines (1753 loc) · 133 KB

README.md

File metadata and controls

2237 lines (1753 loc) · 133 KB
Raw

Bit - High-Performance C Bitsets

License

Bit is a fixed-capacity, uncompressed bitset library for C. It provides individual bitsets, packed collections of bitsets, set operations, population counts, and OpenMP-enabled container operations. The public interface is based on David Hanson's Bit_T design and extended with packed Bit_DB_T containers. While I strive to ensure the README.md is "in sync" with the codebase, this does not always happen. You should therefore treat the public declarations in include/bit.h as the ultimate source of truth if something does work according to what REAMDE.md claims (and alert me to fix it!).

Contents

Project Background and Features

Bit began as a retype and extension of David Hanson's Bit_T interface from Chapter 13 of C Interfaces and Implementations (Addison-Wesley, ISBN 0-201-49841-3). This is a great book, written before the era of vector extensions and GPUs and adopts the literate programming approach to educate while delivering good quality code. The bitset is formally a vector of bits, and less formally a contiguously stored buffer of bytes, with each bit in each byte directly addressable, modifiable and ultimately useful for compute work in microcontrollers or high performance massive databases using Boolean algebra. Hanson published his book just before multi-threading frameworks like pthreads and OpenMP were introduced (the specifications were published in 1997, shortly after Hanson's book was released in 1996) but before multicore processors (those would not become widely available for another decade), and half a decade before DirectX8 opened up GPUs for general purpose compute purposes. Other compute innovations that postdate this book include the introduction of vectorized operations (Single Instruction, Multiple Data aka SIMD) and the formalization of the cache level hierarchies to narrow the memory-CPU gap. The Bit_T thus became the starting point of an exploration on how we can take classic books and algorithms implemented in C and polish them up for the modern era. This repository is about this personal journey (assisted in the latter stages by generative AI).

The project keeps the original emphasis on a small C interface while extending it with setop count operations that are accelerated by vector extensions, packed bitset containers of bitsets (for the mathematically oriented, these are arrays of bitsets/bitvectors) eying applications in analytical vector databases. When developing Bit I deliberately started with Hanson's small interface because it is easy to reason about, then kept extending and experimenting with the C preprocessor as a form of meta-programming to allow seamless and portable execution in CPUs and GPUs. The result is still a small bitset library at heart, but it now has two useful levels of abstraction: an individual Bit_T and a packed Bit_DB_T for bulk, production work.

The production work I had in mind involves dense, fixed-capacity bitsets and workloads where bitwise set operations, population counts (counting the bits equal to one in a byte) predictable memory access patterns for performance in both CPU and GPUs. Specific implementation features that facilitate these use cases are:

  • Population counting: Counting the number of one's in a container is the basis of similarity measures (such as the Hamming distance).1 There are numerous ways to do this calculation, some of which are better geared to specific forms of hardware than others. A scalar population count is part of my CPU and nearly all GPUs, but hardware instructions are limited to Arm or AVX512 capable CPUs. If one were to execute massive database searches that are based e.g. on Hamming distances, memory access patterns may favor implementations that are based on SIMD extensions as compilers may not always be able to auto-vectorize. Bit attempts to squeeze the maximum of performance in a portable manner by 1) bundling libpopcnt that can use CPU-specific population-count implementations (hardware instructions such as VPOPCNTDQ in AVX512 platforms or algorithms such as the Harley-Seal) when enabled 2) vectorized population ops (such as bitwise AND/XOR/OR) with counts (setops) through the SIMDe vectorized loads, stores and portable intrinsics for counts in vectors and 3) a portable Wilkes-Wheeler-Gill (WWG) / sideways-addition path. Key applications of bitsets in the era of data intensive applications require performant, high throughput population counting and the performance portability of this operation has heavily weighted on the design of this library.
  • Fused Set operations with counts: Union, intersection, symmetric difference, and set difference are available for individual bitsets and packed containers. The library also provides fused setop count operations in which the bitwise Boolean algebra is followed by a population count without forming the full intermediate result of the bitwise operation before counting the bits. The fused setop/count operations (or fused logical cardinality operations if you want to be more formal) are accelerated to various degrees by the underlying pop count implementation for a given hardware architecture, so having multiple ways to skin the popcount cat provides an easy way to optimize Bit for your own hardware using the build system.
  • External storage: Bitsets and containers can borrow caller-owned buffers when their storage is allocated with the size and padding required by the public API. This functionality exists to easily interface Bit with other languages (e.g. Perl) without un-necessary copying memory across language interfaces.
  • Packed containers: Bit_DB_T stores equally sized bitsets in contiguous storage for all-pairs count operations on CPU or, where configured, GPU offload. Packing effectively transforms the bitsets into the equivalent of Boolean matrices of bits. This has an important theoretical implication, i.e. fused setop_count operations can be viewed as Boolean analogues of conventional matrix multiplication and thus one could port ideas from high Performance BLAS libraries to speed up things quite a bit. Packed storage has important performance implications for the processor: a) Zero Pointer Chasing keeps the prefetcher happy b) Cache friendly implementation through tiling and c) Natural SIMD implementations: vector lanes can massively accelerate both the setop and the cardinality computation (especially if the processor has a vector instruction for the popcount) at the register level.
  • Multithreaded portable performance through OpenMP: On the CPU side, one can implement a cache hierarchy friendly multi level (3 to 6) tiled Boolean algebra analog of a GEneral Matrix Matrix (GEMM) across many threads/cores. On the GPU side one can sequentially adapt these multi-level tiled algorithms for the same purpose. Because Bit uses flat, dense matrices, one can map the entire container to a GPU device using a single OpenMP #pragma omp target directive and exploring different parallelization strategies and work-sharing constructs. One interesting finding is that different compilers (e.g. gcc and the LLVM based ones) use different models to map OpenMP compiler directives to the underlying 2 dimensional compute fabric of GPUs, so that one has to utilize slightly different OpenMP implementations to maximize performance for a given compiler in a given compute architecture
  • Vendor agnostic OpenMP offload: NVIDIA, AMD, and experimental integrated Intel paths are opt-in: you do not need to use them if you are not going to deploy in the GPU. The default configuration of the build system is to not build these offloads, but retain the GPU-facing API in the library; if the latter is built without offload support, then the internal macro implementations ensure that the GPU API uses the CPU code path. Thus we will not break consuming code that uses the GPU API if the library is built without offloading capabilities.

Comparison to Other Libraries

Bit is not a compressed CRoaring or dynamically growing bitmap library, so given the simplicity of the static bitset data structures, one can find numerous similar implementations in software repositories. Daniel Lemire's cbitset and the bitset_t dense bitvector interface in CRoaring are the closest libraries to Bit (though neither provides Bit's packed-container multithreading or GPU offload; CRoaring's Roaring containers do use SIMD, while cbitset relies on popcount builtins and compiler auto-vectorization). These are not the only libraries that one can find in the C / C++ ecosystem that provide similar functionality. The following table contrasts features of Bit versus other alternatives that one may adopt for their own project:

Library Internal Structure Dynamic Growth Fused Logic + Count Bit Matrices / Containers Explicit SIMD GPU / Hardware Multithreading
Bit [1] Uncompressed dense array No (Fixed at init; borrowed caller buffers via Bit_load / BitDB_load) Yes (Bit_{union,inter,diff,minus}_count; BitDB_*_count_{cpu,gpu}) Yes (Native contiguous Bit_DB_T; all-pairs $N \times M$ counts) Yes (libpopcnt and SIMDe paths; WWG fallback) Yes (OpenMP target; NVIDIA/AMD, experimental Intel) Yes (Host OpenMP on container counts)
CRoaring [2] Compressed Roaring (array / bitset / run); 32- and 64-bit Yes (roaring_bitmap_add(); dense bitset_set / bitset_resize / bitset_grow) Yes (roaring_bitmap_{and,or,xor,andnot}_cardinality; dense count equivalents) Partial (or_many, xor_many; no equal-stride packed row matrix) Yes (AVX2, AVX-512, NEON; runtime dispatch on x86) No No (ops are single-threaded; COW allows concurrent reads)
BitMagic [3] Compressed hierarchical blocks + GAP/RLE; rank-select as an accelerator Yes (set(), set_bit(), resize()) Yes (count_and, count_or, count_xor, count_sub) Yes (bm::aggregator<>, sparse_vector, rsc_sparse_vector, bit-transposed containers) Yes (SSE2/SSE4.2, AVX2, NEON, Wasm SIMD; AVX-512 experimental) No Partial (task pool and parallel planners; aggregator is not auto-parallel and is not shareable across threads)
cbitset [4] Uncompressed dense array Yes (bitset_resize(), bitset_grow(); bitset_set auto-grows) Yes (bitset_intersection_count, bitset_union_count, bitset_difference_count, bitset_symmetric_difference_count) No No (popcount builtins / auto-vectorization; no wide-SIMD API) No No
goldsborough/bitset [5] Uncompressed vector-backed Yes (bitset_push(), bitset_grow(), bitset_reserve(), bitset_setup(); there is no bitset_resize()) No (bitset_and / bitset_or / bitset_xor write a destination) No No No No
EWAHBoolArray [6] Compressed EWAH (enhanced WAH RLE); also uncompressed BoolArray Yes (set(), addWord(), append(), padWithZeroes(); updates are append-oriented) Yes (logicalandcount, logicalorcount, logicalxorcount, logicalandnotcount) Partial (fast_logicalor for N-way union; no packed matrix) No (scalar POPCNT / builtins) No No
boost::dynamic_bitset [7] Uncompressed vector of blocks Yes (resize(), push_back(), push_front(), append()) No ((a & b).count() materializes; intersects tests existence only) No No No (Boost.Compute has a separate device dynamic_bitset) No
std::bitset [8] Uncompressed fixed array No (compile-time <size_t N>) No ((a & b).count() copies then counts) No (static arrays of bitsets only) No No No
sul::dynamic_bitset [9] Uncompressed C++17/20 header-only Yes (resize(), push_back(), append()) No (intersects only; no fused set-op cardinality) No Partial (optional libpopcnt for count() only) No No
SDSL-lite [10] Uncompressed bit_vector (int_vector<1>) plus compressed/succinct (rrr_vector, sd_vector, …) Partial (bit_vector / int_vector resize; compressed forms are generally rebuilt) No (rank/select support, not pairwise fused cardinality) No (succinct indexes, not dense all-pairs rows) Partial (low-level popcount/SSE in support code) No No
FastBit [11] WAH-compressed bitmap indexes over columnar data No as a general resizable bitset (indexes are built from columns) Partial (compressed AND/OR/XOR/MINUS; in-domain count(mask)) Partial (many bitmaps as bit-sliced / binned indexes) No (compressed-word algorithms) No No (query-level parallelism, not a bitset thread API)
SIMD-Bitset [12] Uncompressed aligned char* Partial (Resize(int) reallocates; not a production grow API) Partial (CountAnd; AND/OR materialize) No Yes (AVX/AVX2; experimental, leaky ownership) No No
libalgebra [13] Raw word arrays (does not expose a bitset container) No Yes (STORM_intersect_count, STORM_union_count, STORM_diff_count) No (useful as a kernel backend only) Yes (SSE4.2, AVX2, AVX-512, NEON) No No
opentl/bitset [14] New C++ GitLab project (~6 commits at this snapshot) Not established (too small/new to treat as a production comparator) Not established No Not established No No

These libraries fall roughly in four categories that suggest their use niche:

  1. General-Purpose Utilities (std::bitset, boost::dynamic_bitset, goldsborough/bitset, sul::dynamic_bitset) Designed for everyday software engineering. They provide safe, easy-to-use APIs for tracking state flags and application logic. They allow dynamic memory allocation (except std::bitset), but lack fused cardinality operations and native matrix containers. Running batch queries across thousands of bitsets requires manual loops and intermediate memory allocations. sul::dynamic_bitset is a modern header-only stand-in for Boost that can optionally use libpopcnt.

  2. Compression, Indexes, and Succinct Structures (CRoaring, BitMagic, EWAHBoolArray, FastBit, SDSL-lite) Engineered to handle massive amounts of sparse or compressible data. Both CRoaring and BitMagic recognize the memory bottleneck of intermediate allocations and implement fused logical counters. BitMagic explicitly provides robust container abstractions for succinct bit-transposed data (e.g., bm::sparse_vector). Crucially, it features bm::aggregator<>, a cache-friendly, SIMD-optimized engine designed for fast N-way AND/OR/SUB batch operations across groups of bit-vectors. However, these features are explicitly oriented toward compressed, inverted-index style workloads (like column-store databases and text search). Because these succinct matrices are composed of compressed trees or run-length encoded streams, traversing them requires complex branching logic, making adaptation to multi-core GPU accelerator threads challenging. CRoaring can still be extremely fast on dense data (it falls back to dense bitset containers), but its overall architecture and strength remain in the sparse/compressed regime. EWAH is the classic word-aligned RLE bitmap (Git-style workloads). FastBit is a WAH bitmap index over scientific/columnar data, not a general bitset ADT. SDSL-lite is a succinct rank/select toolkit (bit_vector, rrr_vector, sd_vector, wavelet trees, FM-indexes), not a dense Boolean GEMM engine.

  3. The HPC Compute Engine: Bit deliberately trades memory compression and dynamic resizing for maximum computational throughput, explicit parallelism, and strong hardware affinity. HPC workloads such as bioinformatics, similarity search against static document collections, and Boolean matrix algebra rarely operate on isolated pairs of bit vectors. Instead, they process hundreds of thousands of vectors at once. Bit treats its containers (Bit_DB_T) as contiguous 2-D dense matrices of packed bitsets, enabling efficient bulk and all-pairs operations. While libraries such as BitMagic excel at N-way aggregations over sparse, compressed indexes using CPU SIMD, Bit is purpose-built for dense, fixed-capacity packed batches. By enforcing fixed sizes and storing matrices in contiguous memory, a single OpenMP offload directive can map the data directly onto NVIDIA, AMD GPUs and integrated Intel GPUs. Streaming multiprocessors can then compute batch similarities with no pointer chasing and minimal branch divergence—delivering throughput that compressed, pointer-heavy formats cannot efficiently achieve on accelerator hardware.if you have massive, dense bitsets and need to throw everything modern silicon has at them (SIMD, Multithreading, and GPU compute), Bit fills a high-performance computing void. The comparison against the IndexBinaryFlat, a highly optimized algorithm from FAISS for high performance similarity search in binary vectors using population counts of Hamming distance matrices illustrates how the well individual components of Bit combine to achieve performance that comes close to state of the art libraries. While FAISS optimizes a search problem, Bit optimizes the broader dense Boolean linear-algebra / similarity-computation problem.

  4. Kernel backends and experimental code (libalgebra, SIMD-Bitset, opentl/bitset) libalgebra does not expose a bitset class directly; it is a header-only SIMD kernel for popcount, positional popcount, and fused intersect/union/diff cardinality over raw word arrays and tensors. SIMD-Bitset is instructional AVX code with incomplete ownership. opentl/bitset is too new for direct comparison: analysis of its code suggest it provides functionality similar to the original Bit_T library by David Hanson.

Design, Bit Counting, and OpenMP

This section provides further background about the design choice of Bit's implementation, some useful trivia and performance notes about population counting and justification about the containerized operations and the use of OpenMP.

The use of macros in Bit

Internally the library relies on a considerable amount of macro code to reduce repetition. Within these macros internal _Pragma helpers are used to express CPU worksharing, vector length and processor adaptible SIMD reduction, coordinate the data travel to and from the GPU, without maintaining several nearly identical kernels. This is one of the places where the C preprocessor is earning its keep and I am forever indebted to the Hanson book that showed me I should embrace the macro style. While the public C API does not expose these macros, it does provide a macro interface to the high level functions that can be used to direct code to the CPU or the GPU. I have found these macros to substantially cut on the amount of boilerplate I had to use to develop the functionality of the library and I encourage their use.

Population Count algorithms

The codebase originally used the name Wilkes-Wheeler-Gill (WWG) for a portable sideways-addition population-count technique. Historical literature also calls the technique Gillies-Miller sideways addition.2 This algorithm offered a portable fallback when a specific target or compiler path did not use a native popcount instruction. The algorithm is a very performant one and until Bit release 1.0 was the default algorithm when one did not want to include the libpopcnt library. The present release offers as an alternative to libpopcnt an implementation based on SIMDe's simde_mm512_popcnt_epi64, simde_mm256_popcnt_epi64 or simde_mm_popcnt_epi64 , with the choice made at compile time based on compiler flags for the architecture used. Internally SIMDe is using different algorithms to accomodate different vector architectures (including hardware acceleration if available e.g. in Neon and AVX512 processors). If the vector architecture cannot be resolved via the compiler flags, then the Bit does not use vectorized loads and stores and defaults to the WWG algorith. This choice of algorithms was motivated by the history of the library: WWG was the first popcount I used, followed by the quick adoption of libpopcnt and more recently of SIMDe based portable intrinsics. There is emerging evidence, e.g. see my companion repository bench_popcount , that one must consider additional choices that vary by compiler, architecture and possibly surrounding code context. Turning on LTO will also affect performance and considering that one can obtain differences in performance of an order of magnitude or more, it is worth to have more than one options on the table.

It is worth reflecting on my personal path in exploring population count implementations. This stemmed from the nature of the applications I am using Bit for: in these applications a performant population count can make a huge difference in how the entire application (mostly vector database searches) performs. David Hanson's original implementation of the population count relied on a scalar lookup of the upper and lower nibbles of each byte in the bitvector. Scalar hardware population counts would not appear in processor instructions until the late 1990s and early 2000s (for those into conspiracy theories, look up the relevant stories about NSA's request/insistence to include this instruction in processor ISAs), so Hanson used a very standard approach for the time. This vectorized approach still forms the basis of performant AVX2 vectorized popcount operations and is included in:

  • sse-popcount, including the Harley-Seal population-count work associated with Lemire, Kurz, and Mula.
  • SIMDe for AVX2 paths

For those who want to explore the fascinating history of the population count in the CPU (going all the way to Alan Turing) here are some links:

The last paper provides an interesting evaluation of popcounts in both CPU and GPU and provides an independent evaluation that the Harley-Seal which is used by [libpopcnt](https://github.com/kimwalisch/libpopcnt is slightly better than the vectorized look up method in AVX2 systems. The same paper showed that bit tweaking tricks don't really offer a substantial performance gain in the GPU. I was not aware of this paper when I selected WWG as the default GPU code path unless USE_BUILTIN_POPCOUNT=1 is selected at build time. There is a useful compiler lesson hiding here: during development I found that Clang's (and gcc's) NVIDIA target, the hand-written WWG expression and __builtin_popcountll produced byte-identical device PTX containing popc.b64. Both compilers recognized the classic SWAR pattern and canonicalized it to the hardware operation. Since USE_BUILTIN_POPCOUNT need not change performance, I left it as the default choice for the compiler to mess with.

Why Containers, OpenMP and Macros?

The non-containerized bitset operations are straightforward to parallelize at the application level using OpenMP. Therefore one may ask what is the benefit of providing packed containers?
By explicitly defining the storage layout, these containers facilitate optimal scheduling for batched all-pairs operations. Techniques including CPU memory tiling, OpenMP thread scheduling, and dense GPU layouts are employed to ensure that data locality and parallel work distribution are tightly coupled to the hardware, bypassing the inefficiencies of generic loop nests. This distinction is intentional. An application with an array of independent Bit_T objects can write an OpenMP loop to process one large collection of Bit_T against another directly and very cleanly:

#include "bit.h"
#include <assert.h>
#include <stdlib.h>

int main(void) {
  const int query_count = 2;
  const int reference_count = 3;
  Bit_T queries[2];
  Bit_T references[3];
  int *counts = calloc((size_t)query_count * reference_count, sizeof(*counts));
  assert(counts != NULL);

  for (int i = 0; i < query_count; ++i) {
    queries[i] = Bit_new(128);
    Bit_bset(queries[i], 10 + i);
  }
  for (int j = 0; j < reference_count; ++j) {
    references[j] = Bit_new(128);
    Bit_bset(references[j], 10 + j);
  }

#pragma omp parallel for collapse(2)
  for (int i = 0; i < query_count; ++i) {
    for (int j = 0; j < reference_count; ++j) {
      counts[i * reference_count + j] =
          Bit_inter_count(queries[i], references[j]);
    }
  }

  for (int i = 0; i < query_count; ++i) Bit_free(&queries[i]);
  for (int j = 0; j < reference_count; ++j) Bit_free(&references[j]);
  free(counts);
  return 0;
}

Bit_DB_T exists for the cases where one would the library to own that bulk organization. Its contiguous storage lets the implementation tile the two outer container dimensions and block the inner bit-vector reduction achieving high performance. The CPU_TILE, BITVECTOR_TILE, outer-row/column shape, unroll, and scratch-buffer settings that will be discussed in the benchmarking and tuning sections are "knobs" that affect cache use, register pressure, and memory traffic. These should be thought as tuning controls for a specific CPU architecture rather than universal constants, even though the default choices mostly work sufficiently well. A user should not need to worry about those after perhaps an initial tuning to the specific machine they want their code to run at.

Branches and their Status

This repository includes three specific branches with their branch-specific tooling. Historically these branches emerged from the need to test different OpenMP implementations for GPUs, the integrated Intel GPU branch (which to this day requires further work and is considered highly experimental, not fit for production work until features of OpenMP 5.0 are fully integrated in the implementation). The following table lists the three branches, but for all intents and purposes the main is what you need.

Branch Purpose Notes
main Baseline library, SIMD, CPU tuning, NUMA experiments, and shared benchmark work Owns the CPU sweep/tuning scripts and the main-to-branch synchronization helpers. The FAISS benchmark suite is cross-branch shared (see below).
gpuOpt GPU/offload kernel and comparative benchmark work Owns Makefile_bench.mak, the openmp_bit_nocpu GPU-only kernel testbed, native CUDA/HIP benchmarks, GPU sweep/plot tooling and results, and the gpuOpt-to-branch synchronization helpers. The FAISS benchmark suite is cross-branch shared (see below).
inteliGPU Intel oneAPI CPU build and offload validation Build with CC=icx GPU=INTEL. Its scripts/ directory retains the shared bug-report helper and the shared FAISS benchmark suite.

Script Inventory by Branch

The repository contains a number of scripts that may be used to report bugs when building the library, synchronize common code paths between two branches, profile and fine tune the library for a specific architecture via benchmarking and summarize the results visually and with markdown tables. Finally, there are scripts that compare the performance of an example application built with Bit, a poor person's analogue of the IndexBinaryFlat functionality from FAISS. The profiling/tuning/benchmark scripts follow the same design philosophy: a JSON configuration file that provides the grid over which one sweeps performance metrics, a Perl script that parses the configuration script, executes artefacts build with Bit, parses and logs their output, and a R script that does the visualization.

Script or group main gpuOpt inteliGPU Purpose
generate_bug_report.sh Yes Yes Yes Backend for make bug_report; collects build configuration, diagnostics, preprocessed source, and an optional backtrace.
cpu_param_sweep.pl + benchmark_config_cpu.json Yes No No JSON-driven broad CPU build/runtime sweep.
cpu_profiling_analytics.R Yes No No Intended analysis and plotting companion for broad CPU sweep CSV files; see the compatibility note below.
sweep_cpu_tuning.pl Yes No No Focused CPU kernel timing and perf stat profiling; writes its own CSV and Markdown reports.
run_numa_sweeps.sh Yes No No Runs four dual-socket scenarios through sweep_cpu_tuning.pl.
gpu_param_sweep.pl + plot_performance.R No Yes No Compatible GPU sweep and plotting pair for benchmark_GPU_params/.
Tracked benchmark_GPU_params/ results No Yes No Historical GPU sweep CSV/log results kept with their producer and plotter.
faiss_compare.pl + benchmark_config_faiss.json Yes Yes Yes Small JSON-driven FAISS-vs-Bit comparison sweep; harvests per-iteration timings into benchmark_FAISS/. Shared across branches.
faiss_compare_visualize.R Yes Yes Yes R report for the FAISS comparison; boxplots of per-iteration times and a summarized CSV in benchmark_FAISS/. Shared across branches.
faiss_cpu_benchmark.py Yes Yes Yes Native FAISS IndexBinaryFlat CPU baseline; one of the two sweep FAISS arms. Shared across branches.
faiss_gpu_benchmark.py Yes Yes Yes Native FAISS GPU comparison (no CPU baseline); the other sweep FAISS arm. Shared across branches.
faiss_cpu_gpu_benchmark.py No Yes No Fixed-workload FAISS binary-index comparison with a measured CPU baseline and each detected CUDA GPU. NOT used by the sweep; gpuOpt-only.
push_main_to_gpuOpt.sh, push_main_to_inteliGPU.sh Yes No No Copy curated paths from main to the named destination branch.
push_gpuOpt_to_main.sh, push_gpuOpt_to_inteliGPU.sh No Yes No Mirror the same selective-copy workflow with gpuOpt as the source branch.

The FAISS programs require Python, NumPy, and a FAISS build with GPU support. They print fixed-workload timing summaries and do not feed either R script.

Build and Test

Building and testing requires a Linux environment (though I have only tested Debian flavors such as Ubuntu 22.04, 24.04, WSL Ubuntu flavors and Armbian). As long as the tooling noted below is available, the library (at least the non GPU versions) should build without issues.

Requirements

  • A C compiler supported by the current Makefile: clang, gcc, amdclang, or icx. Versions that have been tested are:
GCC AMDClang Clang ICX
12.4.0 18.0.0 18.1.8 2026.1.1

The major compatibility requirement is the use of a compiler that supports an OpenMP version that is at least 201511 or newer (I have tested OpenMP versions up to 202011)

  • GNU Make.
  • OpenMP support for the selected compiler (this may require installing the relevant libraries).
  • CUDA and an OpenMP offload-capable LLVM toolchain for NVIDIA offload.
  • ROCm and a compatible LLVM/ROCm stack for AMD offload.
  • Intel oneAPI icx for the Intel integrated GPU OpenMP offload (icx is a valid and very performant choice if the library is built without offload capabilities).
  • nvcc for the experimental CUDA benchmark and hipcc for the experimental HIP benchmarks in the gpuOpt branch.

To get you started, just clone and build the default CPU configuration without specifying any target:

git clone https://github.com/chrisarg/Bit.git
cd Bit

make

The test target builds build/test_bit but does not execute it. Build and run it explicitly:

make test 
./build/test_bit

This will execute a number of tests to ensure that the library builds and computes correctly. make disclean or make clean wipes out the slate clean.

Compiler and GPU Target Matrix

The standard Makefile builds the library and ordinary benchmarks on main and the specialized branches. The following table summarizes the various targets that one can build using a range of compilers and GPU offload configuration flags. The rightmost column below is gpuOpt-only: its GPU-only and native targets require make -f Makefile_bench.mak. Those targets are useful in ongoing work to optimize the OpenMP implementations against native CUDA and HIP builds. The CUDA/HIP targets are all AI assisted1 and they are mess of slopware due to the AI's hallucinating and me failing to control them through rigorous prompting.

Compiler (CC=) GPU target (GPU=) Standard targets Standard OpenMP/offload checks gpuOpt benchmark targets
gcc or clang NONE library, test, bench, bench_omp, bug_report test_offload builds but detects host fallback; bench_omp is CPU-only none
gcc or clang NVIDIA library, test, bench, bench_omp, bug_report test_offload, bench_omp openmp_bit_nocpu, cuda_gpu_bench, gpu_bench_csv
gcc or clang AMD library, test, bench, bench_omp, bug_report test_offload, bench_omp openmp_bit_nocpu, hip_gpu_bench, gpu_bench_csv
amdclang AMD library, test, bench, bench_omp, bug_report test_offload, bench_omp openmp_bit_nocpu, hip_gpu_bench, gpu_bench_csv
icx INTEL library, test, bench, bench_omp, bug_report test_offload , bench_omp
icx NONE library, test, bench, bench_omp, bug_report test_offload , bench_omp

Important things to remember:

  • The Makefile rejects CC=amdclang with a GPU target other than AMD, CC=icx with a GPU target other than INTEL (or NONE). Combinations such as GPU=NONE,NVIDIA will also be rejected
  • Native CUDA and HIP benchmarks deliberately compile their device source with nvcc and hipcc, respectively, rather than the value passed through CC but still use GPU=NVIDIA or GPU=AMD as build guards. To use these targets you will need to have a functional CUDA/HIP installation and you may want to specify the location in the Makefile_bench.mak makefile if things do not work.
  • On gpuOpt, openmp_bit_nocpu is blocked when GPU=NONE. Its Makefile guard tests whether a non-NONE target was selected; validate the experimental Intel path with test_offload on the target machine.

Build Configuration

These are Make variables, not runtime environment variables and are listed alphabetically:

Variable Default Effect
APPLY_LTO 1 Enables LTO for supported compilers; set to 0 to disable it.
CC clang Selects the compiler, one of GCC , CLANG, AMDCLANG, ICX (case insensitive).
CLANG_RUNTIME_RPATH 1 Embeds the selected Clang OpenMP runtime path; set to 0 only when deliberately testing another runtime.
GPU NONE CPU fallback, or NVIDIA, AMD, and experimental INTEL offload.
GPU_ARCH Auto-detected when possible NVIDIA sm_/compute_ and AMD gfx architecture list.
LIBPOPCNT 1 Enables bundled libpopcnt integration; set LIBPOPCNT=0 to disable it.
OPENMP_GPU_IMPL Compiler specific Selects the backend for GPU accelerated containerized setop counts.
SIMD_DIAGNOSTICS 0 Enables SIMD configuration diagnostics.
USE_BUILTIN_POPCOUNT 0 Enables GPU Hardware accelerated popcounts; the default is the WWG algorithm, but both gcc and the LLVM compilers recognize the pattern and replace the function with the hardware version.

There are additional optimization flags for CPU and GPU that are detailed in the benchmark sections. Those are intended for extreme adaptation to a given environment; for the most part you can forget about them as I strived to find reasonable defaults that work in the average case. However you should feel free to experiment with those, and the sweeping scripts will give you a tool to do so semi-automatically

Important GPU Note:1 The major GPU optimization is the use of the algorithm for performing the setop_count operations. The two GPU algorithms packaged with the algorithm in the main branch are controlled via the OPENMP_GPU_IMPL flag. These two choices do not have tuning parameters, but others in the experimental gpuOpt branch do. As noted below if you do not specify OPENMP_GPU_IMPL, an appropriate value is selected for you based on the compiler you use to build the library.

Offload Builds

The primary GPU selection is GPU= and the values that are currently supported are NONE (no offload) AMD, NVIDIA or INTEL (those are case insensitive). When building for a particular architecture, one needs optionally to specify the architecture using the GPU_ARCH configuration flag. As a reminder, NVIDIA architectures use sm_ or compute_ prefixes; AMD architectures use gfx prefixes. The current Makefile has no equivalent GPU_ARCH selector for Intel targets (perhaps I can get an Arc Battlemage for Christmas?). There is some support for automatic detection of the architecture in use through tools such as nvidia-smi, but this will likely fail if you have more than one architectures in your system, so it is best to specify manually.

Examples of building the library with offload support:

# NVIDIA OpenMP offload. Omit GPU_ARCH only when nvidia-smi can detect a target.
make CC=clang GPU=NVIDIA GPU_ARCH=sm_70

# AMD OpenMP offload.
make CC=clang GPU=AMD GPU_ARCH=gfx90a

# Experimental Intel OpenMP offload.
make CC=icx GPU=INTEL

When building for an offload target, the OPENMP_GPU_IMPL is a compile-time choice. The active main values are:

  • TEAM_PARALLEL_SIMD
  • TRANSPOSED_TEAM_PARALLEL_SIMD

If you do not specify the parameter, the build system will use TEAM_PARALLEL_SIMD for the gcc and TRANSPOSED_TEAM_PARALLEL_SIMD LLVM compilers since these are the paths that lead to optimal code generation for each compiler after benchmarking. For the mast part you can forget about this choice unless you are into extreme benchmarking. If you are curious to see how these work, run the benchmarks built and run the bench_omp target with both choices for both clang and gcc.

GPU Troubleshooting and Validation

During development of the library, I found that it is too easy for novices like me to build artefacts that do not offload. The hard lesson learned: GPU offload is opt-in, and OpenMP can fall back to the host when an image, plugin, driver, or device is unavailable Therefore I included the target test_offload that can validate offloat configurations. Setting OMP_TARGET_OFFLOAD=MANDATORY prevents an accidental host fallback from being.

build/test_offload <problem_size> [device_id] [benchmark_iterations]

The test first verifies integer, float, and double target calculations against host results. When benchmark_iterations is positive, it also reports memory-bound, compute-heavy, and device-resident benchmark modes. The device-resident mode transfers its working data once and is useful for separating steady-state device computation from host/device transfer overhead.

Use OMP_TARGET_OFFLOAD=MANDATORY for validation so an unintended host fallback fails visibly:

# Correctness checks only.
OMP_TARGET_OFFLOAD=MANDATORY ./build/test_offload 100000 0

# Correctness checks plus 100 benchmark iterations.
OMP_TARGET_OFFLOAD=MANDATORY ./build/test_offload 100000 0 100

The executable prints the detected target-device count, default device, and whether each probed target region ran on the host or a device. If no devices are reported or a target region runs on the initial device, rebuild for the intended architecture, verify the selected runtime plugin, and rerun with diagnostics.

You can build and run the offload diagnostic with all supported compilers as:

make test_offload CC=clang GPU=NVIDIA GPU_ARCH=sm_70
OMP_TARGET_OFFLOAD=MANDATORY ./build/test_offload 100000 0

make test_offload CC=clang GPU=AMD GPU_ARCH=gfx90a
OMP_TARGET_OFFLOAD=MANDATORY ./build/test_offload 100000 0

make test_offload CC=icx GPU=INTEL
OMP_TARGET_OFFLOAD=MANDATORY ./build/test_offload 100000 0

Runtime Diagnostics

During system updates one can break the GPU offload and we would like to have a run time option to check what is happening under the hood. The current Makefile exports quiet Clang runtime defaults:

  • LIBOMPTARGET_INFO=0
  • LIBOMPTARGET_DEBUG=0

Override them while diagnosing device discovery, image loading, or launch behavior:

LIBOMPTARGET_INFO=16 LIBOMPTARGET_DEBUG=1 \
  make test_offload CC=clang GPU=AMD GPU_ARCH=gfx90a

OMP_TARGET_OFFLOAD=MANDATORY LIBOMPTARGET_INFO=16 \
  ./build/test_offload 100000 0

If you are using GCC to compile, use GOMP_DEBUG=1 instead.

NVIDIA Offload Notes

NVIDIA builds accept sm_<target> or compute_<target> values. The Makefile can derive sm_ values from nvidia-smi when GPU_ARCH is not supplied, but an explicit target specification is nearly always the better choice (e.g. since the underlying compiler support and the driver support for architectures may not be identical):

make test_offload CC=clang GPU=NVIDIA GPU_ARCH=sm_70
OMP_TARGET_OFFLOAD=MANDATORY ./build/test_offload 100000 0

# Build multiple NVIDIA images when the installed toolchain supports them.
make test_offload CC=clang GPU=NVIDIA GPU_ARCH=sm_70,sm_80

On a multi-GPU host, restrict visible devices before running the test. The selected physical device normally becomes OpenMP logical device 0:

CUDA_VISIBLE_DEVICES=0 OMP_TARGET_OFFLOAD=MANDATORY \
  ./build/test_offload 1000000 0 1

CUDA_VISIBLE_DEVICES=1 OMP_TARGET_OFFLOAD=MANDATORY \
  ./build/test_offload 1000000 0 1

Some LLVM/libomptarget and driver combinations behave more reliably with one visible NVIDIA device at a time. If a multi-device run reports zero target devices or fails during initialization, narrow CUDA_VISIBLE_DEVICES, keep the program device ID at 0, and rerun the mandatory-offload check.

AMD Offload Notes

AMD targets use the gfx<target> spelling. The Makefile can query rocm-smi when GPU_ARCH is omitted; inspect the system directly before pinning a target manually:

rocminfo | grep -Eo 'gfx[0-9a-f]+' | sort -u
rocm-smi --showproductname

make clean
make test_offload CC=clang GPU=AMD GPU_ARCH=gfx90a
OMP_TARGET_OFFLOAD=MANDATORY ./build/test_offload 4096 0

If several AMD devices are visible or the OpenMP runtime selects the wrong one, restrict visibility and rerun the same mandatory-offload test:

ROCR_VISIBLE_DEVICES=0 OMP_TARGET_OFFLOAD=MANDATORY \
  ./build/test_offload 4096 0

# Alternative ROCr visibility variable used by some installations.
HSA_VISIBLE_DEVICES=0 OMP_TARGET_OFFLOAD=MANDATORY \
  ./build/test_offload 4096 0

If the runtime cannot load an AMD target image, first make GPU_ARCH match the actual gfx target and the installed LLVM/ROCm stack. The Makefile exposes ROCM_PATH and ROCM_DEVICE_LIB_PATH for non-default installations; inspect those paths before changing system libraries.

Legacy AMD Architecture Workaround

This historical recipe was used for a Radeon Pro W5500 (gfx1012) with LLVM 18. This was the card I bought for <120 dollars on eBAY to check the AMD paths during the GPU price bloodbath in 2026. While the card is not supported via ROCM, code that compiles for the nearby gfx1010 target can be used to offload Bit with this card.

Similar workarounds are possible with other AMD cards, but I feel that you should treat the following note as as a record of one working environment that will allow you to repurpose a cheap GPU for real work, rather than a general solution. If you decide to try this with another card, please verify verify your own setup with OMP_TARGET_OFFLOAD=MANDATORY and drop me a note.

# Historical example: compile a nearby supported target, then present that
# target to the runtime for this shell only.
make test_offload CC=clang GPU=AMD GPU_ARCH=gfx1010
export HSA_OVERRIDE_GFX_VERSION=10.1.0
OMP_TARGET_OFFLOAD=MANDATORY ./build/test_offload 4096 0

Some LLVM 18 installations also looked for a matching libomptarget-amdgpu-*.bc filename for the physical target. System-wide aliases change the compiler installation, so inspect the active toolchain first and make that change only with an administrator and a rollback plan:

find "$ROCM_DEVICE_LIB_PATH" -maxdepth 1 -name 'libomptarget-amdgpu-*.bc' -print

In any case, prefer a ROCm/LLVM release that supports the actual target. If an alias is used, record it and retest after compiler, runtime, or driver updates.

Compiler Bug Reports

make bug_report creates a timestamped directory under bug_reports/ with the build log, configuration, preprocessed source, and, for a failing build, an attempted backtrace. The target defaults to BUG_TARGET=bench_omp.

make bug_report CC=clang GPU=NVIDIA GPU_ARCH=sm_70 BUG_TARGET=bench_omp

Review build.log, config.txt, backtrace.txt, and src-bit.preprocessed.i in the generated report directory.

The report script records the selected compiler, target list, effective flags, and the failing build output. It also adds compiler-specific reproduction artifacts:

  • GCC: gcc-v.txt, gcc-repro-command.txt, and gcc-save-temps.log.
  • Clang: compiler crash reproducers when Clang emits them under the configured report directory.

If the target build fails and gdb is available, the script reruns the target under batch gdb and writes a full backtrace to backtrace.txt. When the build succeeds, that file explicitly records that no failing process was available. Temporary preprocessing and intermediate compiler artifacts in build/ are removed after collection.

Using the Library

Usage is straightforward and follow's Hanson's clean separation of interfaces and implementations. Just include bit.h (the API) and link against build/libbit.so or build/libbit.a after building the library to your application and things should work. The documentation of the API below is deliberately kept at a minimum: the header file should be consulted for the precise order of arguments and their types with the examples included below showing the implementation of common use cases.

Public API Reference

Bit_T and Bit_DB_T are Abstract Data Types (ADT) and one works with them through their public interface. A C structure typedef SETOP_COUNT_OPTS is used to control the CPU and GPU OpenMP environment. I exposed the implementation of this structure to assist with the development of interfacing code when offloading to the GPU and when multi-threading in the CPU.

Public type Purpose
Bit_T One fixed-capacity mutable bitset.
Bit_DB_T A packed collection of equally sized bitsets.
SETOP_COUNT_OPTS CPU thread count plus GPU device-residency controls for all-pairs container counts.

Individual Bitset API

Family Functions Contract
Lifecycle and storage Bit_new, Bit_load, Bit_free, Bit_extract, Bit_buffer_size Create library-owned storage, borrow caller storage, release the wrapper, or copy bytes out.
Properties Bit_length, Bit_count Return fixed capacity or population count.
Single-bit mutation Bit_bset, Bit_bclear, Bit_get, Bit_put Access one indexed bit; Bit_put returns its previous value.
Bulk/range mutation Bit_aset, Bit_aclear, Bit_set, Bit_clear, Bit_not Apply an index array or an inclusive [lo, hi] range.
Callback traversal Bit_map Visit indexes from left to right with the current bit value and caller closure.
Comparisons Bit_eq, Bit_leq, Bit_lt Compare equal-length bitsets.
Allocating set operations Bit_union, Bit_inter, Bit_diff, Bit_minus Return a newly allocated result that must be passed to Bit_free.
Count-only set operations Bit_union_count, Bit_inter_count, Bit_diff_count, Bit_minus_count Return the result population count without constructing a bitset.

Set-operation names follow the implementation and tests and require one left and one right operand:

Operation Expression Example for $A={1,3,5}$ and $B={3,5,7}$
union $A \mathbin{\mathrm{OR}} B$ ${1,3,5,7}$
inter $A \mathbin{\mathrm{AND}} B$ ${3,5}$
diff $A \mathbin{\mathrm{XOR}} B$ ${1,7}$
minus $A \mathbin{\mathrm{AND\mbox{-}NOT}} B$ ${1}$

For these individual-bitset set operations, one NULL operand is interpreted as the empty set. Thus Bit_union(set, NULL) and Bit_minus(set, NULL) return a copy of set, while Bit_inter(set, NULL) returns an empty bitset. Passing both operands as NULL is invalid. This convention follows those adopted by Hanson in his book, and frankly correspond to how these operations work in Boolean algebra.

Packed Container API

The packed container API consists of library functions and a smaller set of macros. The macros are very helpful for meta-programming with the C preprocessor and for extending the API of the library itself.

Family Functions Contract
Lifecycle and storage BitDB_new, BitDB_load, BitDB_free Create or borrow storage for a fixed number of equal-length bitsets.
Properties and counts BitDB_length, BitDB_nelem, BitDB_count_at, BitDB_count Query shape or population counts; BitDB_count allocates an array the caller frees.
Element access BitDB_get_from, BitDB_put_at Copy one element out as a new Bit_T, or copy one equal-length Bit_T into the container.
Buffer access BitDB_extract_from, BitDB_replace_at Copy one element to or from a caller-provided buffer.
Clearing BitDB_clear_at, BitDB_clear Clear one element or the complete packed container.
Allocating all-pairs counts BitDB_{inter,union,diff,minus}_count_{cpu,gpu} Allocate and return an int matrix; the caller uses free.
Caller-owned all-pairs counts BitDB_{inter,union,diff,minus}_count_store_{cpu,gpu} Write into a caller-provided int matrix.
Target convenience macros BitDB_{inter,union,diff,minus}_count(..., cpu|gpu) Select the corresponding direct CPU or GPU function in C source.
Target convenience macros BitDB_{inter,union,diff,minus}_count_store(..., cpu|gpu) Select the corresponding direct CPU or GPU function in C source.
Build diagnostics print_Bit_configuration Print the compiled tile, buffer, popcount, and OpenMP configuration.

Container binary operations require two non-NULL containers (also denoted as right and left in the documentation) whose bitsets have the same length. If the left and right containers hold $N$ and $M$ bitsets, the result contains $N \times M$ integers in row-major order. diff and minus retain the XOR and left AND-NOT meanings shown above.

The header also defines target-selecting _count _count_store macros using the same order of arguments as the direct functions, except the last:

BitDB_inter_count(left, right, results, options, cpu);
BitDB_inter_count_store(left, right, results, options, cpu);

The final token may be cpu or gpu. Direct _store_cpu and _store_gpu functions remain useful for foreign-function interfaces and callers that cannot use C preprocessor macros.

Ownership and Validation of Bitsets and their containers

Bit was written with the explicit intention to facilitate flexible storage ownership: there are functions in the API that own bitsets and containers, and others that use externally allocated buffers for the countainers.

Value Owner and release rule
Bit_new / BitDB_new result Library owns storage. Bit_free / BitDB_free releases it, sets the handle to NULL, and returns NULL.
Bit_load / BitDB_load result Caller owns storage. The matching free routine destroys the wrapper, sets the handle to NULL, and returns the borrowed pointer for the caller to free or reuse.
BitDB_get_from or an allocating Bit_* operation Caller owns the new Bit_T and releases it with Bit_free.
BitDB_count or non-store container count Caller owns the returned int * and releases it with free.
_store_ container count Caller allocates and retains the result buffer.

Bitsets and containers owned by the library are zero initialized by default. The implementation uses assert for most pointer, index, length, allocation, and equal-shape checks. Defining NDEBUG during compilations removes those checks. However the library cannot recover from segfault from an an undersized external buffer or invalid index with or without NDEBUG. Since the library cannot determine the allocation size behind a raw pointer, so callers must size borrowed and extraction buffers correctly as we illustrate in the examples below.

A note about memory allignment, allocation and library operations

This is a technical note that should not affect normal users, and is probably an overkill for many modern processors. Internally Bit does enforce strict alignment of the memory buffers it owns, but makes no assumptions about borrowed storage (though it will do a runtime check to optimize the execution path of logical operations and counts for such buffers). The rules are the following:

  • Bit_T Allocation: When allocating a single bitset via Bit_new, the library uses the standard C calloc function. Because it relies on calloc, it receives the default memory alignment provided by the host system's standard library (typically 8 or 16 bytes), without enforcing any custom strict alignment.
  • Bit_DB_T Allocation: When allocating a packed database of bitsets via BitDB_new, the library explicitly enforces stricter alignment using a custom internal allocator. The required alignment depends on the system architecture that the library is build for: 32 bytes for 32-bit architectures and 64 bytes for 64-bit architectures. This allows us to use aligned load/stores which may be faster in some older processors. In any case maintaining the aligned code path is no match for the C preprocessor which provides a unified internal API.
  • Borrowed External Storage: When you load an externally allocated buffer using Bit_load or BitDB_load, the library interacts with the borrowed storage in the following ways:
    • Minimum Padding Requirements: The library explicitly expects the external buffer size to be padded to the next multiple of 8 bytes (the size of a uint64_t) to prevent out-of-bounds access during scalar operations.
    • Dynamic Alignment Dispatch: The library does not strictly force the borrowed storage to match its ideal internal 32-byte or 64-byte alignment. Instead, it checks the external pointer's alignment at runtime during vectorized database set operations.
    • Vectorization Fallback: If the external buffer meets the optimal alignment checks (64-byte alignment on 64-bit systems, or 8-byte alignment on 32-bit systems), the CPU executes fast aligned SIMD loads. If the external buffer is unaligned, the library safely falls back to unaligned SIMD instructions to execute the operations.

At some point, I should probably take down the machinery because everyone is telling me that unaligned loads carry no penalty in our time.

Using Individual Bitsets

This is a straightforward example showing the creation of two bitsets with sufficient storage for 128 bits, setting individual bits, doing a bitwise and for an overlap and computing the cardinality of the result.

#include "bit.h"
#include <stdio.h>

int main(void) {
  Bit_T left = Bit_new(128);
  Bit_T right = Bit_new(128);
  Bit_bset(left, 3);
  Bit_bset(left, 64);
  Bit_bset(right, 64);
  Bit_bset(right, 100);

  Bit_T overlap = Bit_inter(left, right);
  printf("intersection count: %d\n", Bit_count(overlap));

  Bit_free(&overlap);
  Bit_free(&right);
  Bit_free(&left);
  return 0;
}

The distinction between diff and minus is easier to see with actual bits. For $A={1,3,5}$ and $B={3,5,7}$, symmetric difference keeps 1 and 7, whereas left set difference keeps only 1:

#include "bit.h"
#include <assert.h>

int main(void) {
  Bit_T left = Bit_new(128);
  Bit_T right = Bit_new(128);
  int left_bits[] = {1, 3, 5};
  int right_bits[] = {3, 5, 7};
  Bit_aset(left, left_bits, 3);
  Bit_aset(right, right_bits, 3);

  Bit_T symmetric = Bit_diff(left, right);
  Bit_T remainder = Bit_minus(left, right);
  assert(Bit_count(symmetric) == 2);
  assert(Bit_get(symmetric, 1) && Bit_get(symmetric, 7));
  assert(Bit_count(remainder) == 1 && Bit_get(remainder, 1));

  Bit_free(&remainder);
  Bit_free(&symmetric);
  Bit_free(&right);
  Bit_free(&left);
  return 0;
}

The corresponding Bit_*_count functions compute the same population counts without forming the intermediate bitset.

Using External Storage

Bit_load and BitDB_load borrow caller-owned storage. The caller must allocate enough padded storage and later free the pointer returned by the matching free routine. The function Bit_buffer_size returns the minimum number of bytes needed to store a bitset of a requested size/capacity (in this case 130). For performance the storage used to store a bitset is the closest to the requested size integer multiple of 64.

#include "bit.h"
#include <stdlib.h>

int main(void) {
  const int length = 130;
  const int bytes = Bit_buffer_size(length);
  void *storage = calloc(1, (size_t)bytes);
  if (storage == NULL) {
    return 1;
  }

  Bit_T borrowed = Bit_load(length, storage);
  Bit_bset(borrowed, 129);

  /* Bit_free returns storage for externally loaded bitsets. */
  free(Bit_free(&borrowed));
  return 0;
}

For a bitset allocated with Bit_new, Bit_free(&bitset) frees its internal storage and returns NULL. BitDB_free follows the same ownership rule for packed containers. Bit_extract copies a bitset into caller-provided storage and returns the number of bytes written.

Borrowed container storage is the per-bitset buffer size multiplied by the number of elements. BitDB_free returns that original pointer rather than freeing it behind the caller's back. The size of the needed external buffer can similarly be obtained by multiplying the number of bitsets in the container (variable count in the snippet below) and the size in bytes needed to store a library of a given number of bits (this is the value returned by Bit_buffer_size):

#include "bit.h"
#include <stdlib.h>

int main(void) {
  const int length = 130;
  const int count = 4;
  const size_t bytes = (size_t)Bit_buffer_size(length) * count;
  void *storage = calloc(1, bytes);
  if (storage == NULL) {
    return 1;
  }

  Bit_DB_T borrowed = BitDB_load(length, count, storage);
  Bit_T seed = Bit_new(length);
  Bit_bset(seed, 129);
  BitDB_put_at(borrowed, 0, seed);

  Bit_free(&seed);
  storage = BitDB_free(&borrowed);
  free(storage);
  return 0;
}

How to Play with Containers

The ADT Bit_DB_T stores equally sized bitsets in a packed container. You can create such a container with BitDB_new(length, count) and fill it with individual bitsets BitDB_put_at. The example below creates a container with 2 elements of capacity of 128 bits, then allocates a bitset of the same capacity (seed), sets the 9th bit and puts it at the first index of the container. Then we extract the bitset at the first index of the container and verify that the bit at the 9th position is set.

#include "bit.h"
#include <assert.h>
#include <stdlib.h>

int main(void) {
  const int length = 128;
  Bit_DB_T database = BitDB_new(length, 2);
  Bit_T seed = Bit_new(length);
  Bit_bset(seed, 9);
  BitDB_put_at(database, 0, seed);

  Bit_T copy = BitDB_get_from(database, 0);
  assert(Bit_get(copy, 9) == 1);

  void *buffer = calloc(1, (size_t)Bit_buffer_size(length));
  if (buffer == NULL) {
    Bit_free(&copy);
    Bit_free(&seed);
    BitDB_free(&database);
    return 1;
  }
  BitDB_extract_from(database, 0, buffer);
  BitDB_clear_at(database, 0);
  assert(BitDB_count_at(database, 0) == 0);
  BitDB_replace_at(database, 1, buffer);
  assert(BitDB_count_at(database, 1) == 1);

  free(buffer);
  Bit_free(&copy);
  Bit_free(&seed);
  BitDB_free(&database);
  return 0;
}

In this example we initialize two containers, fill them with individual bitsets and then perform a population count in the CPU. The assignment SETOP_COUNT_OPTS options = {.num_cpu_threads = 2}; is used to control the number of OpenMP threads we will task for this job.

#include "bit.h"
#include <stdio.h>
#include <stdlib.h>

int main(void) {
  Bit_T seed = Bit_new(128);
  Bit_bset(seed, 10);
  Bit_bset(seed, 65);

  Bit_DB_T queries = BitDB_new(128, 2);
  Bit_DB_T references = BitDB_new(128, 3);
  for (int index = 0; index < BitDB_nelem(queries); ++index) {
    BitDB_put_at(queries, index, seed);
  }
  for (int index = 0; index < BitDB_nelem(references); ++index) {
    BitDB_put_at(references, index, seed);
  }

  SETOP_COUNT_OPTS options = {.num_cpu_threads = 2};
  int *counts = BitDB_inter_count_cpu(queries, references, options);
  if (counts != NULL) {
    printf("first intersection count: %d\n", counts[0]);
  }

  free(counts);
  BitDB_free(&references);
  BitDB_free(&queries);
  Bit_free(&seed);
  return 0;
}

Counting the cardinality of containers is an important data intensive application of Bit. The function BitDB_count(container) returns a newly allocated array containing one population count per stored bitset for the container of interest. The non-store container count functions (BitDB_inter_count_cpu, BitDB_union_count_gpu, and so on) also return a newly allocated result array. In both cases, the caller is responsible to free the returned array of counts, i.e. the library will not manage the storage for you.

The result array for a binary container operation has BitDB_nelem(left) * BitDB_nelem(right) elements in row-major order:

result[left_index * BitDB_nelem(right) + right_index]

Use _store_ variants when the caller has previously allocated the research buffer :

size_t result_count = (size_t)BitDB_nelem(queries) * BitDB_nelem(references);
int *results = malloc(result_count * sizeof(*results));
if (results != NULL) {
  BitDB_inter_count_store_cpu(queries, references, results, options);
  free(results);
}

These _store_ variants were created to interface with external libraries and dynamically typed languages (e.g. Perl) that use their own custom allocators. The typical C user should probably never have to use them within C.

The macros BitDB_inter_count, BitDB_union_count, BitDB_diff_count, and BitDB_minus_count select a cpu or gpu function at compile time. Use the function forms when linking against a shared library from code that cannot see the macros. However I strongly encourage you to use the macro interface when coding in C.

Controlling the OpenMP environment in CPU and GPU

The SETOP_COUNT_OPTS that provides control options for CPU execution and advanced GPU data-residency decisions for containerized operations. This is structure in C that is declared in the header of the Bit library as:

typedef struct {
  int num_cpu_threads;      
  int device_id;            
  bool upd_1st_operand;     
  bool upd_2nd_operand;     
  bool release_1st_operand; 
  bool release_2nd_operand; 
  bool defer_counts_transfer; 
  bool release_counts;        
  enum {
    TRANSPOSED_TEAM_PARALLEL_SIMD = 0, // transpose + team parallel + SIMD
    SHARED_TILE_ILP = 1, // Shared tile + Instruction level parallelism
  } algorithm; // reserved; current library dispatch does not read this field
} SETOP_COUNT_OPTS;

The meaning of the fields is explained in the table below:

Field Current behavior
num_cpu_threads A positive value selects the CPU OpenMP thread count; a nonpositive value uses the OpenMP runtime maximum.
device_id Selects the OpenMP target device for GPU calls; ignored by CPU calls.
upd_1st_operand, upd_2nd_operand Refresh an operand that is already present on the selected device. An absent operand is mapped on first use regardless of the update flag.
release_1st_operand, release_2nd_operand Decreases the reference counter of the corresponding device mapping after the operation. Leave false only when a later call deliberately reuses that mapping. Setting true will not cause the de-allocation of the buffers if their reference counters is not zero.
defer_counts_transfer Defers the transfer of the counts from the GPU to the host e.g. when further processing should be done.
release_counts Decrements the reference counter of the device mapping for counts if true; may lead to de-allocation of the mapping on the device if this was the last reference to this buffer for the entire program.
algorithm Present in the public structure, but not read by the current library dispatch. It will become runtime kernel selector (at some point in the future).

Using SETOP_COUNT_OPTS for device resident repetitive tasks

If one conceptualizes the right sided container as a fixed, reference database of bits, a repeated query (left side container) workflow can keep an unchanged reference container mapped, refresh each modified query container, and release both operand mappings on the final call. That optimization also creates a responsibility: if host data changes while its update flag is false, the device is allowed to keep using the older mapped contents.

The main justification of allowing device resident bitset is that remory allocations and de-allocations in the CPU are very costly, so it pays handsomely in terms of performance if one did not have to move things around unless absolutely necessary. Consider for example the scenario in which one has 3 containers, each of size N that must be matched against a single container of size M. The device has enough memory to fit a single container of size N, another one of size N, and the results of size N * M. In this case,

SETOP_COUNT_OPTS opts_1to2 = {
    .device_id = -1,
    .upd_1st_operand = true,
    .upd_2nd_operand = false,
    .release_1st_operand = false,
    .release_2nd_operand = false,
    .release_counts = false
};

instructs the mapper to update the first operand in the GPU when iterating over the first two containers of size N. To process the final container, one can use

SETOP_COUNT_OPTS opts_3 = {
    .device_id = -1,
    .upd_1st_operand = true,
    .upd_2nd_operand = false,
    .release_1st_operand = true,
    .release_2nd_operand = true,
    .release_counts = true
};

which will update the first operand in the GPU and release all the buffers on the device upon exit. Since OpenMP manages device memory regions using reference counting, releasing of the regions amounts to decreasing the reference counters for each of the regions. Regions that are no longer referenced will be automatically de-allocated.

Benchmarks and Experiments

Standard Benchmarks

Build the CPU benchmark suite:

make bench_omp GPU=NONE

For GPU=NONE, this creates:

  • build/openmp_bit_nogpu
  • build/openmp_bit_container
  • build/cpu_param_sweep

build/cpu_param_sweep is the four-argument C benchmark used by the broad CPU parameter workflow. It is distinct from scripts/cpu_param_sweep.pl, the JSON-driven Perl coordinator described in Automation Scripts.

make bench additionally builds build/benchmark.

The OpenMP benchmark command lines are defined by their source files:

build/openmp_bit <size> <number-of-bitsets> <number-of-reference-bitsets> <max-threads> [gpu-id]
build/openmp_bit_nogpu <size> <number-of-bitsets> <number-of-reference-bitsets> <max-threads>
build/openmp_bit_container <bits> <left-bitsets> <right-bitsets> <threads> <repetitions>

With a non-NONE GPU target, make bench_omp also builds build/openmp_bit. The fourth argument of openmp_bit_nogpu is a maximum CPU thread count.

Benchmark Scope and Interpretation

The OpenMP benchmark is a practical all-pairs intersection-count comparison: it searches query bitsets against a reference collection and reports the largest observed intersection count. The mixed benchmark establishes serial baselines, sweeps OpenMP thread counts for the ordinary bitset representation, and repeats the workload with packed Bit_DB_T containers. With a configured offload target, it also exercises container operations through the GPU path.

openmp_bit_nogpu keeps the serial, OpenMP, and packed-container CPU portions while excluding GPU execution. Use it when characterizing CPU tiles, OpenMP scheduling, affinity, and memory locality without an offload runtime in the measurement.

The speedup values use the run's first serial measurement as their baseline. They are useful for comparing configurations on the same machine and workload; bitset shape, topology, compiler, OpenMP runtime, memory placement, and GPU strategy all change the result when that context changes.

Experimental gpuOpt Benchmark Layer

Makefile_bench.mak is an experimental extension for GPU-only OpenMP kernels and native CUDA/HIP benchmarks. It exists only on gpuOpt and is not the public library build interface. Switch branches before using any command in this section:

git switch gpuOpt

# GPU-only OpenMP benchmark.
make -f Makefile_bench.mak openmp_bit_nocpu \
  CC=clang GPU=NVIDIA GPU_ARCH=sm_70

# Native benchmark backends.
make -f Makefile_bench.mak cuda_gpu_bench GPU=NVIDIA GPU_ARCH=sm_70
make -f Makefile_bench.mak hip_gpu_bench GPU=AMD GPU_ARCH=gfx90a

# Run the selected native backend and write CSV/log output.
make -f Makefile_bench.mak gpu_bench_csv GPU=NVIDIA GPU_ARCH=sm_70

The GPU-only executable accepts:

build/openmp_bit_nocpu <size> <number-of-bitsets> <number-of-reference-bitsets> <gpu-iterations> [gpu-id]

Its fourth argument is GPU iterations, not a CPU thread count.

OPENMP_GPU_IMPL is also a compile-time choice for the experimental GPU benchmark, not a public runtime option. The active gpuOpt values are:

  • TEAM_PARALLEL_SIMD
  • TRANSPOSED_TEAM_PARALLEL_SIMD
  • SHARED_TILE_ILP
  • TRANSPOSED_TILED_GEMM

The experimental SHARED_TILE_ILP and TRANSPOSED_TILED_GEMM variants are available ONLY to the openmp_bit_nocpu testbed. The FAISS GPU comparator (openmp_bit_gpu_FAISS_comp) always uses the library's built-in kernel (TEAM_PARALLEL_SIMD or TRANSPOSED_TEAM_PARALLEL_SIMD, selected by OPENMP_GPU_IMPL at library build time).

For example:

make -f Makefile_bench.mak openmp_bit_nocpu \
  CC=clang GPU=NVIDIA GPU_ARCH=sm_70 \
  OPENMP_GPU_IMPL=TRANSPOSED_TILED_GEMM

These kernels and native CUDA/HIP paths are experimental. Build for the target compiler and architecture, confirm agreement with the CPU reference, and then measure the workload you care about.

FAISS C comparators

Two thin, public-API-only C benchmarks mirror the Python FAISS scripts and are built by the MAIN Makefile (not Makefile_bench.mak). Both consume only the public bit.h interface and link libbit (which now also carries the private top-k selection object); there is no GPU_COMPILE_TOPK flag -- top-k placement is fixed at build time: host for the CPU executable, device for the GPU executable.

C executable Python counterpart top-k runs on
openmp_bit_cpu_FAISS_comp scripts/faiss_cpu_benchmark.py host
openmp_bit_gpu_FAISS_comp scripts/faiss_gpu_benchmark.py device

Build them (the GPU target requires GPU != NONE):

make CC=clang GPU=NVIDIA GPU_ARCH=sm_70 \
  openmp_bit_cpu_FAISS_comp openmp_bit_gpu_FAISS_comp

Usage:

build/openmp_bit_cpu_FAISS_comp <size> <num-bitsets> <num-ref-bitsets> <top-k> <iterations> [threads] [--no-verify]
build/openmp_bit_gpu_FAISS_comp <size> <num-bitsets> <num-ref-bitsets> <top-k> <gpu-iterations> [gpu-id] [--no-verify]

Timing scope and the --no-verify flag

The reported per-iteration end-to-end time (... OpenMP Filter Total and the SEARCH SUMMARY E2E Avg Time (ns)) is a single wall-clock span around the whole search call -- the count operation plus the top-k selection plus result handling -- matching the Python scripts' time.perf_counter_ns() bracket around index.search(). The scalar best-score reduction over the returned top-k scores is computed outside that span (untimed), exactly as the Python scripts compute distances.min() after their timed call. The comparators also print the two component spans separately (GPU/CPU Algorithm Timing = count call only; Filter Timings = top-k only) for diagnosis, but the sweep harvests the end-to-end Filter Total line.

Both comparators compute an independent CPU all-pairs reference and cross-check the device/library results against it (the agreements/disagreements lines). That reference uses a host OpenMP parallel for and intentionally saturates all cores during the setup phase. Pass --no-verify to skip the reference computation and the cross-check: the benchmark then presents like the Python FAISS GPU script, with the host mostly idle and no independent reference. The flag is opt-in; the default behavior (verify on) and the sweep (scripts/faiss_compare.pl) are unchanged.

FAISS comparison sweep

scripts/faiss_compare.pl runs a small (non-exhaustive) Cartesian comparison of four builds : native FAISS CPU, native FAISS GPU, and the two Bit OpenMP comparators. The sweep is parameterized by the schema scripts/benchmark_config_faiss.json. It harvests PER-ITERATION end-to-end timings (each cell runs a fixed number of iterations; this is 100 by default, but can be changed into the JSON configuration file) into a long-format CSV. The default run grid sweeps bitset size x top_k x database size (num_refs in {10000, 100000, 1000000}). The OpenMP builds are independent of any FAISS installation; only the two native FAISS builds need the FAISS conda environment (resolved automatically via conda run -n faiss_env when the base python cannot import FAISS).

Reproducible up-front build

Before the grid runs, faiss_compare.pl performs a single make -B that pins libbit and the comparators to a known configuration, so each result set is reproducible and self-describing. This is driven by the build block of scripts/benchmark_config_faiss.json:

  • gpu is required. Set it to "NONE" for a CPU-only comparison, or to a target such as "NVIDIA", "AMD", or "INTEL" to also build the GPU comparator. The value is passed verbatim to make GPU=....
  • gpu_arch is optional; leave it blank to let the Makefile auto-detect the architecture (nvidia-smi / rocmsmi).
  • The remaining keys (cc, cpu_tile, bitvector_tile, buffer_size, outer_row_num, outer_col_num, outer_vec_blk, libpopcnt, apply_lto, use_builtin_popcount) map to the host-build Make variables. Blank or empty values are omitted so the Makefile defaults take over; set a value to pin it (e.g. "libpopcnt": "1").

Only the comparators relevant to the target are built: openmp_bit_cpu_FAISS_comp always, plus openmp_bit_gpu_FAISS_comp when gpu != "NONE". When gpu == "NONE", the GPU builds (bit_gpu, faiss_gpu) are dropped from the run even if stale binaries exist. The build aborts the whole comparison on failure, printing the tail of the build output.

The effective configuration actually passed to make (only the non-omitted variables) is recorded in benchmark_FAISS/build_config.txt alongside the results, so the exact build behind any CSV can be reproduced.

For a GPU comparison, set gpu (and optionally pin the popcount path and compiler); everything left blank uses the Makefile defaults:

"build": {
  "gpu": "NVIDIA",
  "gpu_arch": "",
  "libpopcnt": "1",
  "cc": "clang"
}

This runs make -B openmp_bit_cpu_FAISS_comp openmp_bit_gpu_FAISS_comp GPU=NVIDIA LIBPOPCNT=1 CC=clang (GPU architecture auto-detected) and enables the bit_gpu and faiss_gpu builds. A failed build (for example, an unsupported cc) stops the sweep before any benchmark runs.

# Run from ANY directory -- the script auto-detects the repo root, builds the
# comparators itself (make -B), and writes results under <repo-root>/benchmark_FAISS/.
# Full grid: bitset sizes 1024..65536 x top_k 64..2048 x num_refs
# 10000..1000000, 100 iterations each.
perl scripts/faiss_compare.pl --config scripts/benchmark_config_faiss.json

# Quick smoke run / dry run.
perl scripts/faiss_compare.pl --bitset_bits 1024 --top_k 64 --num_refs 10000,100000 --dry_run

The script is working-directory agnostic: it locates the repository root from its own path, chdirs there, builds the comparators with make -C <root> -B ..., and runs each target. Results are always written to <repo-root>/benchmark_FAISS/ (alongside benchmark_CPU_params/ and benchmark_GPU_params/), regardless of the directory you invoke it from. GPU visibility for the GPU builds is derived from build.gpu (NVIDIA->CUDA_VISIBLE_DEVICES, AMD->ROCR_VISIBLE_DEVICES, INTEL->none); set system_env.gpu_visible_env in the JSON (e.g. "CUDA_VISIBLE_DEVICES=1") to override. The host comparator (bit_cpu) runs with no GPU-visibility prefix.

Outputs (all under <repo-root>/benchmark_FAISS/):

  • faiss_compare_results.csv -- long-format per-iteration timings.
  • faiss_compare_summary.csv -- per-cell mean/median/sd (written by the R step).
  • faiss_compare_report.pdf -- boxplots of the per-iteration distributions.

Regenerate the report with:

Rscript scripts/faiss_compare_visualize.R

FAISS vs Bit: per-iteration time distribution

FAISS vs Bit: per-iteration throughput distribution

Median per-iteration time vs bitset size

The openmp_bit_nocpu strategy selector and the experimental Makefile_bench.mak targets belong to gpuOpt. The FAISS comparators (openmp_bit_cpu_FAISS_comp, openmp_bit_gpu_FAISS_comp) are part of the cross-branch shared FAISS suite and are built by the standard Makefile on all branches (see FAISS C comparators).

Interpreting openmp_bit_nocpu Output

The GPU-only benchmark is a safe place to experiment with container kernels without changing the standard library path. It creates random query and reference bitsets, computes a CPU reference result, performs a warm-up run, and then reports several timing views:

  • GPU Algorithm Timing: kernel-focused time for the intersection-count operation.
  • GPU Algorithm + PCIe Timings: end-to-end device-path time, including staging and transfer work measured by the benchmark.
  • GPU Transpose Timings: layout preparation time for strategies that need a transposed representation.
  • CPU Overhead Timings: host-side setup, dispatch, and synchronization work around device execution.
  • Per-Iteration Data Movement Breakdown: query upload and result download volume; the resident reference database is reported separately and excluded from the repeated-transfer payload.
  • Agreement/Disagreement Counts: comparison with the CPU reference. Treat any disagreement warning as a correctness failure to investigate before interpreting throughput.
  • Estimated Throughput: both kernel-focused and total-operation rates, with the latter representing the user-visible combination of staging, transfers, and computation.

Use GPU Algorithm Timing to compare kernel and layout choices. Use the total-operation view when transfers are part of the workload, and check the movement breakdown when a large result matrix makes download time dominant.

OpenMP Strategy Notes

The strategy selector changes compile-time layout and parallelization choices. TEAM_PARALLEL_SIMD is the baseline team/parallel/SIMD approach; TRANSPOSED_TEAM_PARALLEL_SIMD prepares a column-oriented reference layout; SHARED_TILE_ILP combines shared tiles with instruction-level parallelism; and TRANSPOSED_TILED_GEMM is a further experimental tiled formulation.

These names describe implementation choices, not a ranking. Earlier GCC 12/13 and Clang experiments produced different correctness and performance outcomes for the same transposed and shared-tile structures. For each candidate, keep the compiler, architecture, and command with the result; check CPU agreement first, then compare timings. The GPU-only layer keeps that exploration separate from the library's public execution path.

Automation Scripts

Artifact Output Locations (working-directory behavior)

All benchmark producers anchor their output to the repository root, not the directory you invoke them from. You can run any of them from any working directory and the artifacts always land in the same place:

Producer Artifacts land in Mechanism
scripts/faiss_compare.pl <repo-root>/benchmark_FAISS/ Detects the repo root from the script's own path and chdirs into it.
scripts/faiss_compare_visualize.R reads/writes <repo-root>/benchmark_FAISS/ Resolves the root via this.path::this.dir().
scripts/cpu_param_sweep.pl <repo-root>/benchmark_CPU_params/ (or <repo-root>/<out_dir> if --out_dir is overridden) Detects the repo root from the script's own path and chdirs into it; a relative --config is resolved against the original working directory first.
scripts/cpu_profiling_analytics.R reads <repo-root>/benchmark_CPU_params/ Searches a short list of candidate locations, preferring the repo root.
scripts/sweep_cpu_tuning.pl <repo-root>/tuning-results/ Requires CWD = repo root (aborts otherwise).
scripts/run_numa_sweeps.sh <repo-root>/tuning-results/ (one run tag per experiment) + tuning-results/numa-compare-<timestamp>.md Resolves the root from BASH_SOURCE and cds into it; four experiments plus a cross-experiment table.

The relative out_dir in benchmark_config_cpu.json (default benchmark_CPU_params) and the benchmark_FAISS output directory are therefore always interpreted relative to the repository root. To redirect a run elsewhere, pass an absolute --out_dir to cpu_param_sweep.pl.

CPU Sweep Workflow (main)

The main CPU tools are complementary stages of investigation, not interchangeable benchmark front ends:

Stage Tool and benchmark Configuration Measurements and artifacts
Broad discovery scripts/cpu_param_sweep.pl -> build/cpu_param_sweep JSON matrices and command-line overrides External wall-clock timings for ordinary-bitset and packed-container paths, plus host telemetry, CSV, and raw logs under benchmark_CPU_params/.
Profiling for focused tuning scripts/sweep_cpu_tuning.pl -> build/openmp_bit_container Environment-variable matrix Repeated packed-container timings, CPU affinity, and perf stat profiles under tuning-results/.
Dual-socket analysis scripts/run_numa_sweeps.sh -> sweep_cpu_tuning.pl Four comparable topology/memory-policy cases Socket-local baselines plus first-touch and interleaved dual-socket results in the focused tuner's artifact layout.

Use the broad sweep to find candidates across compiler, kernel, workload, and placement choices. Use the focused profiler when you need further insights before locking the configuration for a specific architecture, then use the NUMA runner when the question is memory placement on a dual-socket host and how this affects performance (one worker per physical core by default -- see Why SMT is off by default). The stages can be used independently when that is the only question being investigated.

These scripts and their configuration live on main. The benchmark sources and Makefile targets may also exist on another branch without the coordinating scripts being present there.

1. Broad Parameter Discovery: cpu_param_sweep.pl

scripts/cpu_param_sweep.pl is the JSON-driven coordinator; it is distinct from build/cpu_param_sweep, the C benchmark executable that it rebuilds and invokes. It requires --config and uses scripts/benchmark_config_cpu.json for build matrices, runtime matrices, telemetry, commands, and output parsing.

The script is working-directory agnostic: it locates the repository root from its own path and chdirs there, so it can be invoked from any directory and always builds/runs against <repo-root> and writes under <repo-root>/benchmark_CPU_params/. Both of these invocations are equivalent:

git switch main

# From the repository root.
perl scripts/cpu_param_sweep.pl --config scripts/benchmark_config_cpu.json

# Or from the scripts/ directory (a relative --config is resolved against the
# directory you invoke it from).
cd scripts
perl ./cpu_param_sweep.pl --config ./benchmark_config_cpu.json
Configuration Model

The framework is schema-driven: the JSON file is the source of truth for the build matrix, run matrix, system environment, telemetry, and output parser. The Perl engine dynamically enumerates the build/run matrix, gathers telemetry, interpolates commands, and runs each configured instance. It is generic within the three supported blocks, build_matrix, run_matrix, and system_env; the current configuration still supplies the benchmark-specific build_cmd, run_cmd, and parser contract.

  1. benchmark_config_cpu.json defines compiler and Make-variable combinations, workload sizes, threads, NUMA policies, command templates, output locations, telemetry extractors, and CSV columns.
  2. cpu_param_sweep.pl reads that configuration at runtime, creates its Cartesian build/run space, adds command-line bindings for configuration keys, and executes each workload using the configured taskset, numactl, and scheduling settings.

The current configuration requires Perl 5.36, numactl, taskset, and the selected compiler/toolchain. The active runner imports Algorithm::Loops, IPC::Run, Log::Log4perl, and JSON::PP; ensure the required modules are available before starting a sweep.

perl -MAlgorithm::Loops -MIPC::Run -MLog::Log4perl -MJSON::PP -e 1

It writes CSV and raw logs beneath benchmark_CPU_params/ by default.

Command-Line Overrides

The runner creates options from every key in build_matrix, run_matrix, and system_env. A value passed on the command line overrides the corresponding JSON value; comma-separated matrix values become a smaller sweep.

cd scripts

# Override the configured output directory and thread-count matrix.
perl ./cpu_param_sweep.pl \
  --config ./benchmark_config_cpu.json \
  --out_dir ../custom_results \
  --threads 1,2,4,8,16,20

The JSON uses underscore-style option names, such as out_dir, because those are the configuration keys consumed by GetOptions.

Affinity and Thread Scaling

taskset (a system_env scalar) and threads (a run_matrix list) accept machine-portable sentinel values so a single configuration works across hosts with different core counts. The resolved logical-core count is the value reported by nproc (which honors cgroup/affinity limits on shared nodes), falling back to counting processor entries in /proc/cpuinfo.

taskset controls the CPU mask passed to taskset -c:

Value Behavior
explicit cpulist (0-9, 0,2,4, 0-15:2) Passed verbatim to taskset -c.
auto Expands to 0-(N-1), pinning to all N usable logical CPUs.

threads controls the OpenMP thread-count sweep:

Value Behavior
explicit list ([1, 2, 4, 8]) Swept as-is.
["auto"] Expands to 1..N (every logical core).
list containing "maxcores" The sentinel is dropped and numeric entries are capped at <= N, preserving order and removing duplicates. On an 8-core machine, [1, 2, 3, 4, "maxcores", 16, 18] becomes [1, 2, 3, 4], and [1, 2, 3, 4, 8, 16, 18, 72, "maxcores"] becomes [1, 2, 3, 4, 8].

If every requested thread count exceeds the available cores (an impossible scenario on the current machine), the runner logs a warning and falls back to sweeping 1..N rather than aborting.

Both sentinels are also available as command-line overrides:

perl ./cpu_param_sweep.pl --config ./benchmark_config_cpu.json \
  --taskset auto --threads auto

perl ./cpu_param_sweep.pl --config ./benchmark_config_cpu.json \
  --threads 1,2,4,maxcores

The resolved core count is recorded per run in the Logical_CPUs CSV column (emitted by the cpu_count telemetry entry) and is used by cpu_profiling_analytics.R to facet and annotate the optimization-frontier, register-pressure, and cache-saturation plots.

The focused tuner honors the same auto keyword through its CORES and THREADS environment variables (e.g. CORES=auto THREADS=auto ./scripts/sweep_cpu_tuning.pl). Note the scope differs deliberately: the tuner's auto expands via nproc --all (the full logical-CPU complement, SMT siblings included, ignoring any affinity already in force) because it profiles whole-machine behavior, whereas cpu_param_sweep.pl's auto uses the cgroup/affinity-aware nproc. run_numa_sweeps.sh is unaffected: it derives per-socket physical-core lists from the discovered topology instead (see Why SMT is off by default).

Repetition Ranges and Reproducible Randomization

Repetition-style matrix keys such as rep_id can be written as a single object instead of an explicit list. The object expands before grid generation:

Value Behavior
{ "repeat": 10 } Expands to 1..10 (run each configuration ten times).
{ "range": "3-6" } Expands to 3,4,5,6.
explicit list ([1, 2, 3]) or scalar Used as-is (backward compatible).

rep_id is not interpolated into any command; it only multiplies executions and labels CSV rows for repetition aggregation.

Both the build grid and the run grid are shuffled so execution order is decorrelated from time (thermal/turbo drift and background load), which makes the measured timings more statistically reliable. Set seed in system_env (or pass --seed N) to make the shuffled order reproducible across invocations; omit it for a fresh random order each run. The active seed is logged at startup.

"system_env": { "seed": 12345, ... }
perl ./cpu_param_sweep.pl --config ./benchmark_config_cpu.json --seed 12345

The FAISS benchmark suite is excluded from this scheme; its seeds are hardwired in the comparator source.

Telemetry and CSV Parsing

Telemetry is described in JSON rather than embedded as benchmark-specific Perl logic. The current configuration reads CPU and operating-system files and runs a compiler-version command. Its extractors include CPU model, SIMD tier, and hardware population-count capability:

"telemetry": {
  "hardware": {
    "file": "/proc/cpuinfo",
    "extractors": {
      "Processor": "model name\\s*:\\s*(.+)",
      "SIMD": "(?:flags|Features|isa).*?\\b(avx512f|avx2(?!.*\\bavx512f\\b)|avx(?!.*\\bavx2\\b|.*\\bavx512f\\b)|sse4_2(?!.*\\bavx)|sve2|sve(?!.*\\bsve2\\b)|asimd(?!.*\\bsve)|rv64[a-z]*v[a-z]*)\\b",
      "vpopcountHW": "(?:flags|Features|isa).*?\\b(avx512_vpopcntdq|avx512_bitalg|zvbb|asimd)\\b"
    }
  },
  "os": {
    "file": "/etc/os-release",
    "extractors": {
      "Operating_System": "PRETTY_NAME=\\\"([^\\\"]+)\\\""
    }
  },
  "toolchain": {
    "cmd": "{cc} --version | head -n 1",
    "extractors": {
      "Compiler_Version": "(.*)"
    }
  }
}

Likewise, output_parser captures the benchmark's standard output using named regular-expression groups and writes selected values into CSV columns. Its map normalizes the optional container label before output:

"output_parser": {
  "regex": "(?i)Total\\s+time\\s+for\\s+(?<Benchmark_Type>Container\\s+-\\s+)?Multi-threaded\\s+-\\s+OpenMP:\\s+(?<Timing_ns>\\d+)\\s+ns.*?Number\\s+of\\s+threads:\\s+(?<Threads>\\d+)",
  "columns": ["Benchmark_Type", "Threads", "Timing_ns"],
  "map": {
    "Benchmark_Type": {
      "Container - ": "Containerized",
      "Container -": "Containerized",
      "__UNDEF__": "Non-Containerized"
    }
  }
}

The regex and command templates are part of the selected configuration's contract. Update them together when changing benchmark output or command-line behavior.

2. Focused Kernel Profiling & Tuning: sweep_cpu_tuning.pl

After the broad parameter sweep identifies candidates, the focused tools on main answer two different questions: sweep_cpu_tuning.pl collects repeated timing and performance-counter evidence for a selected packed-container configuration, while run_numa_sweeps.sh compares that workflow under four dual-socket memory-placement cases. They currently remain on main:

  • scripts/sweep_cpu_tuning.pl
  • scripts/run_numa_sweeps.sh

Switch to main before using either workflow. sweep_cpu_tuning.pl must run from the repository root because it verifies that Makefile is present there.

git switch main
make bench_omp GPU=NONE CC=clang

ELEVATE=always CORES=0-9 REPS=5 PERF_REPS=3 \
  perl ./scripts/sweep_cpu_tuning.pl
Focused Container-Kernel Sweep

sweep_cpu_tuning.pl is used to generate insights before CPU tuning of the containerized intersection-count kernel for a given architecture. It really is a "live-cell imaging" of the library in action as it streams data across memory hierarchies. For each configuration it performs a clean rebuild, runs build/openmp_bit_container with an explicit CPU affinity, and collects perf stat profiles. It is intended to compare CPU tiles, K blocks, outer-product microkernel shapes, unrolling, and the independent libpopcnt scratch-buffer path without timing unrelated benchmark work.

Use it after cpu_param_sweep.pl narrows the candidate space or whenever cache, execution, vectorization, TLB, NUMA, power, or scheduling evidence is needed. Unlike build/cpu_param_sweep, this benchmark measures only the packed Bit_DB_T intersection-count path; it does not compare ordinary-bitset and container timings in the same process.

The default sweep evaluates the direct SIMD path (LIBPOPCNT_MODES=0). Include both modes explicitly when comparing it with the libpopcnt path:

git switch main
LIBPOPCNT_MODES=0,1 ELEVATE=always \
  perl ./scripts/sweep_cpu_tuning.pl
Configuration File and Reproducible Order

In addition to environment variables, sweep_cpu_tuning.pl accepts an optional JSON config via --config. The checked-in scripts/benchmark_config_tuning.json documents the full schema. Environment variables override config values (env wins), so the env-only invocations above and run_numa_sweeps.sh keep working unchanged.

perl ./scripts/sweep_cpu_tuning.pl --config ./scripts/benchmark_config_tuning.json

Config keys are grouped into three blocks; each maps to the corresponding environment variable:

Config key Env override Meaning
seed SEED Integer seed for the configuration-order shuffle.
sweep.libpopcnt_modes LIBPOPCNT_MODES Comma-separated 0/1 algorithm modes.
sweep.cpu_tiles CPU_TILES Comma-separated CPU_TILE values.
sweep.k_blocks K_BLOCKS Comma-separated BITVECTOR_TILE values.
sweep.shapes SHAPES Comma-separated ROWSxCOLS shapes.
sweep.unrolls UNROLLS Comma-separated OUTER_VEC_BLK values.
sweep.buffer_sizes BUFFER_SIZES Comma-separated BUFFER_SIZE values.
run.cc CC Compiler.
run.cores CORES CPU affinity mask (auto = every logical CPU from nproc --all, SMT siblings included, ignoring any current affinity restriction).
run.bits BITS Bitset length.
run.left / run.right LEFT / RIGHT Operand counts.
run.threads THREADS OpenMP thread count (auto = the nproc --all logical count, same as CORES).
run.reps / run.perf_reps REPS / PERF_REPS Benchmark / perf stat repetitions.
run.elevate / run.priority ELEVATE / PRIORITY Privilege escalation and scheduling.
run.max_configs MAX_CONFIGS Cap on configurations executed (0 = all).
output.results_dir RESULTS_DIR Root of tuning results.
output.arch_tag ARCH_TAG Architecture label (empty = auto-detect).
output.run_label RUN_LABEL Optional run label.
output.numa_policy / output.numa_cmd NUMA_POLICY / NUMA_CMD NUMA policy label and command.

PERF_PROFILES and PERF_EVENTS are deliberately environment-only and have no config-file keys. The per-architecture PMU event tables they select or override are hardware-mapping logic, not experiment design, so they stay in the script; set them via the environment (see the Performance Profiles section below).

The configuration list is shuffled before execution so run order is decorrelated from time (thermal/turbo drift). Set seed (or SEED) to make the shuffled order reproducible; omit it for a fresh order each run. The seed is recorded in the generated report. When MAX_CONFIGS is set, it now selects a random subset of the shuffled configurations rather than the first N.

To evaluate both algorithms, every default tuning parameter, and all 15 diagnostic profiles on one socket, run this from the repository root:

LIBPOPCNT_MODES=0,1 \
CORES=0-9 THREADS=10 \
REPS=5 PERF_REPS=3 \
RUN_LABEL=avx512 \
PERF_PROFILES=summary,cache-l1,cache-l2,cache-l3-dram,cache-stalls,buffers-pending,buffers-store,execution-uops,execution-ports,frontend,frequency,vectorization,tlb,uncore-numa,power-rapl \
ELEVATE=always \
./scripts/sweep_cpu_tuning.pl

This is a long, sequential measurement. Direct SIMD varies four CPU tiles, four K blocks, four microkernel shapes, and three unroll factors for 192 build configurations. The libpopcnt path varies the same tiles, blocks, and shapes plus four scratch-buffer sizes for another 256. Together, the two modes produce 448 clean builds and $448 \times 15 = 6{,}720$ separate perf stat commands.

The repetition controls work at different levels. PERF_REPS=3 becomes perf stat -r 3, so those 6,720 commands launch 20,160 benchmark processes. Each process receives REPS=5 and performs one untimed warm-up followed by five timed intersection calls. The script also runs the benchmark once outside the profile loop to collect its primary timing output. Compiler speed, workload size, PMU access, and host load determine the wall-clock duration, so use this as a machine specific profiler that can help you understand why the library performs (or not) in the given machine.

Start with a small trial after changing machines, compilers, PMU permissions, or event sets:

git switch main
MAX_CONFIGS=2 REPS=1 PERF_REPS=1 PERF_PROFILES=summary ELEVATE=always \
  perl ./scripts/sweep_cpu_tuning.pl

MAX_CONFIGS=2 stops after two build configurations, REPS=1 performs one timed call per benchmark process, and PERF_REPS=1 runs each profile once. For this toolchain and permission check, PERF_PROFILES=summary keeps profiling to the smallest general-purpose event set.

Sizing the Sweep for Your Host

The two host-shape controls are CORES (the taskset CPU mask the benchmark may use) and THREADS (the OpenMP worker count passed to the benchmark). For the full tuning picture, sweep both libpopcnt modes and the complete profile set. The invocations below are copy-paste complete; run the MAX_CONFIGS=2 smoke test above first on any new machine.

Host Topology CORES THREADS Entry point
Dual Xeon E5-2697 v4 2 x 18 cores/36 threads (36 cores / 72 logical) 0-35 36 run_numa_sweeps.sh (auto-discovery), or the manual dual call below
i7-11700 8 cores / 16 threads, 1 socket 0-15 16 direct tuner call
i9-7900X 10 cores / 20 threads, 1 socket 0-19 20 direct tuner call

Dual-socket Xeon E5-2697 v4 (preferred: the auto-discovering wrapper, which also produces the cross-experiment comparison table). The wrapper runs one worker per physical core by default -- see Why SMT is off by default:

git switch main
bash ./scripts/run_numa_sweeps.sh            # add --dry-run to preview first

or the equivalent single manual call (spread threads, interleaved memory):

git switch main
LIBPOPCNT_MODES=0,1 \
CORES=0-35 THREADS=36 \
OMP_PLACES=cores OMP_PROC_BIND=spread \
NUMA_CMD="numactl --interleave=0,1" NUMA_POLICY="interleave=0,1" \
REPS=5 PERF_REPS=3 RUN_LABEL=2socket-e5-2697v4 \
PERF_PROFILES=summary,cache-l1,cache-l2,cache-l3-dram,cache-stalls,buffers-pending,buffers-store,execution-uops,execution-ports,frontend,frequency,vectorization,tlb,uncore-numa,power-rapl \
ELEVATE=always \
./scripts/sweep_cpu_tuning.pl

i7-11700 (single socket, 8 cores / 16 threads). Use all logical CPUs:

git switch main
LIBPOPCNT_MODES=0,1 \
CORES=0-15 THREADS=16 \
REPS=5 PERF_REPS=3 RUN_LABEL=i7-11700 \
PERF_PROFILES=summary,cache-l1,cache-l2,cache-l3-dram,cache-stalls,buffers-pending,buffers-store,execution-uops,execution-ports,frontend,frequency,vectorization,tlb,uncore-numa,power-rapl \
ELEVATE=always \
./scripts/sweep_cpu_tuning.pl

To restrict to physical cores only on that part, use CORES=0-7 THREADS=8 (and OMP_PLACES=cores OMP_PROC_BIND=close) instead.

i9-7900X (single socket, 10 cores / 20 threads):

git switch main
LIBPOPCNT_MODES=0,1 \
CORES=0-19 THREADS=20 \
REPS=5 PERF_REPS=3 RUN_LABEL=i9-7900x \
PERF_PROFILES=summary,cache-l1,cache-l2,cache-l3-dram,cache-stalls,buffers-pending,buffers-store,execution-uops,execution-ports,frontend,frequency,vectorization,tlb,uncore-numa,power-rapl \
ELEVATE=always \
./scripts/sweep_cpu_tuning.pl

On these single-socket hosts there is no NUMA placement question, so no NUMA_CMD is set; the tuner's default OS policy applies. The equivalent CORES=auto THREADS=auto forms also work, but note that the tuner's auto expands to the full logical-CPU count from nproc --all (SMT siblings included, and ignoring any affinity restriction already in force) -- see the auto note in the variable table below.

Minimal vs maximal invocation

If you want every profile (assuming the host supports them), omit PERF_PROFILES -- the default is the full 15-profile set. The shortest complete invocations are:

# Minimal single-socket: all cores (auto) + all 15 profiles (default).
git switch main
LIBPOPCNT_MODES=0,1 CORES=auto THREADS=auto ELEVATE=always \
  ./scripts/sweep_cpu_tuning.pl

# Minimal dual-socket: pin to one socket's physical cores, all 15 profiles.
# This is one direct tuner run -- the same scope as one wrapper experiment.
# (2x18-core Xeon E5-2697 v4: socket 0 = CPUs 0-17, 18 physical cores.)
git switch main
LIBPOPCNT_MODES=0,1 CORES=0-17 THREADS=18 ELEVATE=always \
  ./scripts/sweep_cpu_tuning.pl

# To run the full four-experiment NUMA comparison (not a single run), use
# the wrapper: bash ./scripts/run_numa_sweeps.sh

To attempt only the profiles that actually resolve on the host, add PERF_PRUNE=1 (see Profile preflight).

The explicit, fine-control forms below are the same runs with every knob made visible -- use them when you want a fixed core mask or a recorded label rather than the auto-discovered values:

# Single-socket, all logical cores, explicit (i9-7900X: 10 cores / 20 threads).
git switch main
LIBPOPCNT_MODES=0,1 \
CORES=0-19 THREADS=20 \
REPS=5 PERF_REPS=3 RUN_LABEL=i9-7900x \
PERF_PROFILES=summary,cache-l1,cache-l2,cache-l3-dram,cache-stalls,buffers-pending,buffers-store,execution-uops,execution-ports,frontend,frequency,vectorization,tlb,uncore-numa,power-rapl \
ELEVATE=always \
./scripts/sweep_cpu_tuning.pl

# Dual-socket, all cores, explicit memory interleave (2x18-core, 36 threads).
git switch main
LIBPOPCNT_MODES=0,1 \
CORES=0-35 THREADS=36 \
OMP_PLACES=cores OMP_PROC_BIND=spread \
NUMA_CMD="numactl --interleave=0,1" NUMA_POLICY="interleave=0,1" \
REPS=5 PERF_REPS=3 RUN_LABEL=2socket-e5-2697v4 \
PERF_PROFILES=summary,cache-l1,cache-l2,cache-l3-dram,cache-stalls,buffers-pending,buffers-store,execution-uops,execution-ports,frontend,frequency,vectorization,tlb,uncore-numa,power-rapl \
ELEVATE=always \
./scripts/sweep_cpu_tuning.pl

# Dual socket, all cores and logical processors, explicit memory interleave (2x18 core, 72 threads)
git switch main
LIBPOPCNT_MODES=0,1 \
CORES=0-71 THREADS=72 \
OMP_PLACES=cores OMP_PROC_BIND=spread \
NUMA_CMD="numactl --interleave=0,1" NUMA_POLICY="interleave=0,1" \
REPS=5 PERF_REPS=3 RUN_LABEL=2socket-e5-2697v4-smt \
PERF_PROFILES=summary,cache-l1,cache-l2,cache-l3-dram,cache-stalls,buffers-pending,buffers-store,execution-uops,execution-ports,frontend,frequency,vectorization,tlb,uncore-numa,power-rapl \
ELEVATE=always \
./scripts/sweep_cpu_tuning.pl

The minimal and explicit forms measure the same thing; the explicit ones only add a fixed CORES/THREADS, a RUN_LABEL, and the spelled-out PERF_PROFILES list (which equals the default). On dual-socket hosts the minimal form uses one worker per physical core (matching the wrapper's default policy); see Why SMT is off by default.

All sweep variables are environment variables. Comma-separated values define a matrix; a single value fixes that dimension.

Variable Default Description
LIBPOPCNT_MODES 0 Algorithms to compare: 0 is direct SIMD; 1 is the libpopcnt scratch-buffer path.
CPU_TILES 4,8,16,32 Values compiled as CPU_TILE.
K_BLOCKS 256,512,768,1024 Values compiled as BITVECTOR_TILE.
SHAPES 1x1,2x2,2x4,4x2 Outer microkernel shapes, written as ROWSxCOLS.
UNROLLS 1,2,4 OUTER_VEC_BLK values, used for the direct-SIMD path.
BUFFER_SIZES 128,512,1024,4096 BUFFER_SIZE values, used for the libpopcnt path.
CC clang Compiler supplied to make.
CORES 0-9 CPU list supplied to taskset -c; choose physical cores where possible.
BITS 65536 Bitset length passed to openmp_bit_container.
LEFT, RIGHT 1000, 1000 Left and right packed-container sizes.
THREADS, REPS 10, 5 OpenMP thread count and timed repetitions.
PERF_REPS 3 Repetitions requested from perf stat for each profile.
PERF_PROFILES profile set Comma-separated profiles such as summary, cache-l1, cache-l2, cache-l3-dram, cache-stalls, buffers-pending, buffers-store, execution-uops, execution-ports, frontend, frequency, vectorization, tlb, uncore-numa, and power-rapl. Use summary while narrowing the matrix.
PERF_EVENTS unset Optional replacement event list for the summary profile.
ELEVATE auto never, auto, or always; elevation can be needed for performance counters or scheduling priority.
PRIORITY nice normal, nice, or real-time round-robin rr; elevated privileges are required where the operating system requires them.
MAX_CONFIGS 0 Stops after this many configurations; 0 means no limit.
ARCH_TAG detected Optional safe filename label for reports.
RUN_LABEL unset Optional label inserted into report and artifact names.
NUMA_POLICY default OS policy Descriptive policy text recorded in the Markdown report.
NUMA_CMD unset Optional numactl command prefixed to the benchmark process.
RESULTS_DIR tuning-results Directory for summary-<run-tag>.csv and llm-summary-<run-tag>.md.
OUT_DIR tuning-results/.work/<run-tag> Directory for per-configuration build, benchmark, and perf artifacts.
Performance Profiles

Each name in PERF_PROFILES is a separate perf stat invocation with its own event list and *.perf.csv artifact. The names describe diagnostic questions; the script maps them to PMU events for generic Intel, hybrid Intel P-core, AMD x86-64, generic AArch64, and Rockchip/Rock64-class systems.

Profile What it helps explain
summary Timing rank, instructions per cycle, branch behavior, and general cache-miss rate.
cache-l1 Retired-load L1 hits and misses.
cache-l2 Retired-load L2 behavior after L1.
cache-l3-dram Last-level-cache behavior and local DRAM demand-load misses.
cache-stalls Cycles stalled around L1D, L2, and L3 miss activity.
buffers-pending Fill-buffer saturation and pending-miss occupancy.
buffers-store Store-buffer and store-queue pressure plus outstanding data-read depth.
execution-uops Issued, executed, and retired micro-operations plus backend stalls.
execution-ports Distribution of work across execution ports.
frontend Undelivered micro-operations and low-delivery cycles.
frequency APERF/MPERF behavior, including possible AVX-512 frequency changes.
vectorization Packed SIMD work compared with scalar fallback indicators.
tlb Data and instruction TLB loads and misses.
uncore-numa Cross-socket, interconnect, and memory-controller traffic where supported.
power-rapl Package and RAM energy or power counters where supported.

The profile name remains stable across machines, but the underlying events do not. Some maps use cycles,instructions when a detailed event is unavailable; many Rockchip profiles and some Intel execution-port profiles intentionally fall back this way. Check the generated event list before comparing unlike architectures. PERF_EVENTS replaces the event list for summary only.

Profiles are kept separate rather than combined into one enormous event set. An individual profile can still exceed the available hardware counters, so use the running/scaling information from perf when interpreting multiplexed counts. A missing event or permission affects that profile; the benchmark timing remains available, and the profile CSV/log records what failed.

Profile preflight (PERF_PROBE / PERF_PRUNE). Because the event sets are architecture-specific, the script can probe the resolved list on the current host before building anything. With PERF_PROBE=1 (the default) it runs a trivial perf stat -e <profile events> -- true per profile and prints which of the 15 resolve (e.g. Profile preflight: 13/15 profiles resolve on this host (unresolvable: power-rapl,uncore-numa)); a profile is unresolvable when that probe exits non-zero or reports a "not supported" event. Set PERF_PRUNE=1 to additionally drop the unresolvable profiles from the run so only the supported ones are attempted (the summary profile is always kept). On a host where perf is entirely blocked (for example a high kernel.perf_event_paranoid or a container without CAP_PERFMON), every probe fails; the preflight says so, and with PERF_PRUNE=1 only summary remains. Set PERF_PROBE=0 to skip probing entirely. The probe honors the same privilege elevation (ELEVATE) as the real runs.

What perf Measures

The script runs:

build/openmp_bit_container <bits> <left-bitsets> <right-bitsets> <threads> <repetitions>

The executable allocates and initializes packed containers, runs one untimed BitDB_inter_count_store_cpu warm-up, performs the requested timed repetitions, and prints each timing plus best, average, Gqword-pairs/s, and a result checksum. perf wraps the complete process, so its counters include allocation, initialization, warm-up, timed calls, checksum, and teardown. Use the C nanosecond timings to rank the intersection kernel and the PMU profiles to understand the wider process behavior.

Each run produces compact, architecture-labelled outputs such as tuning-results/summary-<run-tag>.csv and tuning-results/llm-summary-<run-tag>.md. The accompanying .work/<run-tag>/ directory holds per-configuration build logs, benchmark output, and perf CSV files. A full matrix can be long-running, so reduce the matrix first and reserve the complete profile set for selected candidates.

3. Generic Dual-Socket NUMA Experiment: run_numa_sweeps.sh

run_numa_sweeps.sh implements a generic dual-socket experiment: establish a local-memory baseline on each socket, then compare a dual-socket default first-touch run with explicit memory interleaving. CPU affinity alone does not choose where pages are allocated. Because the focused benchmark initializes its shared input containers before OpenMP workers begin, ordinary Linux first-touch placement can put many pages on one node and make work on the other socket remote-memory heavy.

The script is generic: it auto-discovers the socket/CPU topology from lscpu and runs on any dual-socket host, not just one machine. It locates the repository root itself and may be started from another directory:

git switch main
bash ./scripts/run_numa_sweeps.sh

It requires numactl and lscpu. On any dual-socket host it runs these four comparable sweeps, deriving the CPU lists and worker counts from the discovered physical cores (one OpenMP thread per physical core):

  1. socket0-local: the first socket's physical cores, allocation bound to its NUMA node.
  2. socket1-local: the second socket's physical cores, allocation local to that node.
  3. dual-first-touch-spread: all discovered physical cores, spread OpenMP binding, and default Linux first-touch placement.
  4. dual-interleave: all discovered physical cores, spread OpenMP binding, and memory interleaved across both NUMA nodes.

The single-socket runs provide local-memory baselines. Comparing the two dual-socket runs helps distinguish an asymmetric first-touch placement effect from the effect of explicit interleaving. Interleaving balances allocation; it does not make every access local.

Preview the four resolved experiments (CPU lists, thread counts, NUMA commands, and the ARCH_TAG) without building anything:

bash ./scripts/run_numa_sweeps.sh --dry-run

On a host with a single socket the script exits with a clear message pointing you to sweep_cpu_tuning.pl directly, rather than running a degraded experiment.

Overriding discovery

Every value the script discovers can be overridden. Flags win over discovery; the environment variables documented for sweep_cpu_tuning.pl (LIBPOPCNT_MODES, REPS, PERF_REPS, PERF_PROFILES, ELEVATE, MAX_CONFIGS, CC, SEED, RESULTS_DIR, OUT_DIR) pass straight through.

Flag Default Purpose
--socket0-cpus LIST first socket's physical cores CPU list for the socket0-local run.
--socket1-cpus LIST second socket's physical cores CPU list for the socket1-local run.
--dual-cpus LIST union of the two socket lists CPU list for the two dual-socket runs.
--socket0-threads N size of the socket0 list OpenMP workers for socket0-local.
--socket1-threads N size of the socket1 list OpenMP workers for socket1-local.
--dual-threads N size of the dual list OpenMP workers for the dual runs.
--nodes N0,N1 first NUMA node seen on each socket NUMA node IDs; override on sub-NUMA/cluster-on-die hosts where a socket maps to more than one node.
--arch-tag TAG auto-detected ARCH_TAG passed to the tuner; set it to keep labels comparable with earlier runs.
--smt off Use every logical CPU (SMT siblings included) instead of one thread per physical core.
--dry-run off Print the four resolved experiments and exit without building.
-h, --help — Print the option summary.

Before building, the script validates that the CPU lists are nonempty and non-overlapping, that the CPUs are online, that the NUMA nodes exist, and that no thread count exceeds its CPU list size, and it reports the first problem it finds.

For example, on the reference dual Xeon E5-2697 v4 (18 physical cores per socket, 36 logical CPUs total, no SMT), --dry-run resolves to CPU lists 0-17 / 18-35 / 0-35, worker counts 18 / 18 / 36, and NUMA nodes 0,1 -- the historical hand-written mapping. On a 2x18-core host with SMT enabled (72 logical CPUs), the default physical-core policy resolves to the same 18/18/36 worker counts, while --smt produces 36/36/72.

Why SMT is off by default

Note that the default value of --smt is off (the flag is not passed on the command line): all four experiments run one OpenMP worker per physical core. SMT siblings share a physical core's execution ports and L1/L2 cache, so per-core kernel efficiency -- the quantity the perf profiles exist to measure -- is cleanest with one thread per core; a sibling thread adds contention noise to exactly the counters being compared. The default also keeps results comparable with the historical hand-written Xeon baseline (18 workers on 18 physical cores per socket), and it avoids confounding the experiment's independent variable, which is memory placement (first-touch vs interleave), not core occupancy. The tuner is a profiling instrument, not a maximum-throughput benchmark; if the question is aggregate throughput with every logical CPU busy, pass --smt explicitly. Note the contrast with invoking sweep_cpu_tuning.pl directly (standalone, without this wrapper): its auto sentinel expands to nproc --all, SMT siblings included -- the wrapper's physical-core policy is the deliberate choice for NUMA comparisons.

Where the results go

All four experiments write under <repo-root>/tuning-results/ (see Artifact Output Locations). Each experiment produces its own run tag, and the wrapper then writes a single cross-experiment table comparing the best configuration of each:

File (per run) Contents
tuning-results/summary-<arch>-<label>-<timestamp>.csv Raw per-configuration rows (all knobs + every perf counter).
tuning-results/llm-summary-<arch>-<label>-<timestamp>.md Ranked per-experiment table (avg ns, Gqword-pairs/s, IPC, cache/branch miss).
tuning-results/.work/<arch>-<label>-<timestamp>/ Per-configuration build, benchmark, and perf logs.
tuning-results/numa-compare-<timestamp>.md Cross-experiment table: experiment x best config x avg ns x Gqword-pairs/s.

The numa-compare-*.md table is the headline read for the dual-socket question: it shows whether the interleaved run beats default first-touch and how each compares with the socket-local baselines, in one place. There is no separate R visualization for this schema; the ranked Markdown tables are the presentation layer.

The runner forwards OMP_PLACES, OMP_PROC_BIND, NUMA_CMD, and the named NUMA policy to the tuning script. perf access is governed by the host's permissions and kernel.perf_event_paranoid; use ELEVATE=always only where permitted by local administration policy.

GPU Parameter Sweep (gpuOpt)

scripts/gpu_param_sweep.pl sweeps the experimental native benchmark matrix through Makefile_bench.mak. It supports --backend, --make-args, --iterations, --out-dir, --summary, --log, and --dry-run.

git switch gpuOpt

CUDA_VISIBLE_DEVICES=0 perl ./scripts/gpu_param_sweep.pl \
  --backend=NVIDIA \
  --make-args='CC=clang GPU_ARCH=sm_70'

ROCR_VISIBLE_DEVICES=0 perl ./scripts/gpu_param_sweep.pl \
  --backend=AMD \
  --make-args='CC=clang GPU_ARCH=gfx1010'

Choose the GPU with --backend; reserve --make-args for compiler, architecture, and other Make variables. By default, the script writes backend/architecture-labelled CSV and raw log files in benchmark_GPU_params/. The native CUDA/HIP workflow, its result files, and plot_performance.R belong to gpuOpt and are separate from the CPU sweep suite. Plot the collected CSV files with:

Rscript ./scripts/plot_performance.R

Benchmark Producers and Analytics

The script names suggest several pairings, but the file formats decide which ones work end to end:

  • GPU sweep and plot (gpuOpt): gpu_param_sweep.pl writes architecture-labelled CSV files under benchmark_GPU_params/. plot_performance.R reads those files using the same TILE_J, ILP, workload, timing-type, and throughput columns. This is the working Perl-to-R pair.
  • Broad CPU sweep and analytics: cpu_param_sweep.pl and cpu_profiling_analytics.R are intended companions: use the Perl script to generate the data and the R script to help you visualize them.
  • Focused CPU tuning: sweep_cpu_tuning.pl is self-contained. It writes summary-<run-tag>.csv, llm-summary-<run-tag>.md, and per-configuration build/benchmark/perf files under tuning-results/.work/; no R script in this repository currently consumes that schema.
  • NUMA orchestration: run_numa_sweeps.sh is not an analytics consumer. It invokes sweep_cpu_tuning.pl four times with socket-local, first-touch, and interleaved-memory settings, producing comparable tuning reports.

The R helpers use packages such as data.table, ggplot2, this.path, and bit64; consult each script for its exact package list and output behavior.

Branch Synchronization Helpers

Synchronization is available in both directions between main and gpuOpt, and both source branches can update inteliGPU:

Run from Helper Destination
main scripts/push_main_to_gpuOpt.sh gpuOpt
main scripts/push_main_to_inteliGPU.sh inteliGPU
gpuOpt scripts/push_gpuOpt_to_main.sh main
gpuOpt scripts/push_gpuOpt_to_inteliGPU.sh inteliGPU

Preview any synchronization without fetching, switching branches, staging, committing, or pushing:

./scripts/push_main_to_gpuOpt.sh --dry-run
# Use the helper available on the current source branch for another direction.

All four helpers require a clean source worktree and both local branches. They fetch and fast-forward the destination, copy the paths selected by that helper with git restore, create a commit when content changed, push the destination, and return to the starting branch. Pass --no-push to commit the sync on the destination branch WITHOUT pushing to origin (you then review and push manually). For one invocation, the selected source paths are authoritative: corresponding destination edits are replaced rather than merged, while files outside the selected set remain untouched.

The workflows mirror one another, and each helper copies the same explicitly curated shared library/test/benchmark paths plus the complete include/ tree. Branch-exclusive CPU and GPU benchmark files stay with their owning branch. Helpers targeting main or inteliGPU also remove stale gpuOpt-only benchmark files; the helper targeting gpuOpt never removes them.

README.md is selected by every helper, so a sync also replaces the destination branch's README with the source branch version.

The separate benchmarking-bits repository contains comparative C and Perl bitset/bitmap benchmarks. It is a research companion rather than a dependency of this library.1 This repository reflects the performance of an earlier version of Bit (the first release version).

Constraints and Current Status

  • Capacity: Bitsets have fixed, int-sized capacities. An extension to resize them is unlikely to be written in the form of an API function and this functionality resuts with the user.
  • Validation: Most pointer, index, shape, and allocation checks use assert. Defining NDEBUG removes them; callers must till provide valid indexes, equal-length operands, and correctly sized borrowed buffers. I admit that a memory safe extension would be great, but unlikely to evolve past the use of compiler level sanitizers.
  • Concurrency: GPU calls are synchronous in the current library path and this is not going to change. CPU concurrency safety is up to the caller, with the most significant challenge presented by applications that want to use nested parallelism or combine multiprocessing with multithreading. More details below
  • GPU residency: Update and release flags control device mappings. Internally the library transposes the right bitset container operand and uses a finite state machine to keep track of the orientation. This functionality is not exposed to the caller (it is part of the internal API), but there may be some value to slowly transition those to the public API.
  • Current research surfaces: Intel OpenMP offload and native CUDA/HIP benchmarks remain experimental, largely because I don't enough CUDA/HIP myself1 to verify the AI generated code

Concurrency and Execution

  • Individual bitsets are mutable buffers, so you are responsible for coordinating concurrent access to share objects.

  • GPU based container functions are synchronous. Device, update, and release options control data residency across calls; they do not provide asynchronous execution or cross-thread synchronization, i.e. the host thread blocks until the device has finished execution.

  • I have used the container API through a very ordinary, even boring fork-join path: one thread enters a call and OpenMP parallelizes the work inside it. Nested tasks, multiple controlling threads sharing operands, and fork after OpenMP initialization remain untested here. In particular be very aware of the use of Bit in the context of multi-processing (launching a process that will then use the multi-threading capabilities of Bit). Traditionally this was an unsafe use of OpenMP, until v 5.0 which introduced the omp_pause_resource and omp_pause_resource_all, which allow an OpenMP runtime to prepare a process before a subsequent fork. Please consult the the OpenMP 5.0 API3 to ensure that you are using this feature correctly e.g. these calls should occur outside an explicit parallel region, with explicit tasks completed before the run-time is paused (this means that one can screw the pooch if one is messing with OpenMP's blocking semantics) .

Applications

Bit is particularly useful for dense set and membership workloads such as:

  • Bioinformatics and genomic data processing, including k-mer-like encodings.
  • Network packet filtering and Bloom-filter-style membership tests.
  • High-performance set operations and all-pairs similarity searches (the context of the FAISS like application).

For genuinely sparse domains, a compressed representation such as a roaring bitmap can be a better fit than this uncompressed library. I have not attempted to figure out how big the capacity should be before a compressed respresentation wins out in performance.

Roadmap

  • Continue validating CPU, NVIDIA, AMD build paths.
  • Evaluate Intel Arc's architectures for offloads
  • Investigate offloads to FPGAs
  • Extend SIMD-oriented CPU work across more set-operation paths while retaining portable fallbacks.
  • Port or evaluate selected experimental gpuOpt CUDA/HIP implementations as an alternative to the OpenMP ones.
  • Add set-operation metrics such as Jaccard similarity.
  • Improve OS-agnostic build, profiling, and reproducibility workflows.
  • Investigate Unified Shared Memory where the target runtime supports it (this may be how one gets to use these ubiquitous integrated Intel GPUs!).

License

BSD 2-Clause License. See LICENSE for details.

Author

Christos Argyropoulos (April 2025 - May 2026)

AI Disclosure and Scientific Publication Transparency Statement

This session is intended to document the involvement of AI in this project and a roadmap to preserve, collect and characterize the involvement over time. In retrospect, some of the steps (in particular recovery of history from other machines) should have done much earlier than September 2026. The following few sections represent the use of AI in this project, and some post hoc rambling about how best to record the AI contributions vis-a-vis the human inspiration in future work.

Attribution of AI-assisted work

GitHub Copilot and Google Gemini assisted with generating and refactoring Makefile content, exploring test ideas for the OpenMP implementations, drafting and refactoring templated C work used for the CUDA and HIP implementations, and maintaining this README as the source evolved since the last quarter of 2025.

As focus shifted towards benchmarking and associated automation in 2026 generative AI assisted with script refactoring, Perl automation boilerplate, JSON configuration schemas, R authoring, OpenMP macro work inside the gpuOpt branch

The following model-specific roles are author-confirmed and are described as regular contributions, not as a complete per-file provenance record:

  • Google Gemini 3.1: Perl automation, R authoring, and OpenMP macro work.
  • Claude Sonnet 5 and Claude Sonnet 4.6: Makefile work.
  • Kimi K.3: the main model used since the summer of 2026.

Attribution Evidence and Limits

The repository does not use watermark analysis to identify authorship or assign source code to a particular AI model.1 While I wish there was such a framework, there is no universal source-code watermark detector, and any verification must use that provider's supported process, which I am not sure how to access. Therefore, I fear your must take my word when attributing parts of this work to AI. Model-level claims in this disclosure thus depend on my memory and frankly honesty to disclose. Here are some personal thoughts on how to prospectively collect and document AI assisted contributions for future work.

Recovering Chat History From Many Machines

For AI assisted work completed on multiple computers, collect first-party records instead of attempting retrospective source attribution:

  1. On each VS Code installation signed into the same account, enable chat.sessionSync.enabled and github.copilot.chat.localIndex.enabled.
  2. Run /chronicle reindex on each machine to index retained local sessions and synchronize them where the account configuration permits it.
  3. Preserve unpushed branches and reflogs from each checkout as work chronology, for example with git branch -avv and git reflog show --all.
  4. Retrieve any account-level Copilot history or usage export available to the account owner, then reconcile it with author-maintained records.
  5. Redact credentials, tokens, personal data, proprietary prompts, and other sensitive material before centralizing transcripts or exports.

These steps can recover only history still retained by the device or provider. They do not recreate deleted sessions and may not expose the model routed for each request.

Author Responsibility

All core problem framing, architectural decisions (including decoupling execution engines from target schemas), code validation, security reviews, and scientific evaluations were performed directly by the author. The author maintains responsibility for the accuracy, licensing, and integrity of all submitted code and materials.

Footnotes

  1. All statements marked with this footnote reflect the state of the codebase, benchmarks, and external ecosystem as of the dates indicated in the surrounding text (September 2026 unless otherwise noted). They are time-stamped observations, not permanent claims. ↩ ↩2 ↩3 ↩4 ↩5 ↩6

  2. Maurice V. Wilkes, David J. Wheeler, and Stanley Gill describe the Gillies-Miller method for sideways addition in The Preparation of Programs for an Electronic Digital Computer, 2nd ed., pp. 191-193 (1957). Wojciech Mula, Nathan Kurz, and Daniel Lemire later used the name “Wilkes-Wheeler-Gill” in “Faster Population Counts Using AVX2 Instructions,” The Computer Journal 61(1), 2018. ↩

  3. OpenMP Architecture Review Board. Openmp application programming interface, version 5.0, 2018. See the resource-pause run-time routines omp_pause_resource and omp_pause_resource_all. https://www. openmp.org/spec-html/5.0/openmpsu153.html. ↩