TBB-Based Inverted Lists: Parallelism Without the Drama

The core insight is embarrassingly simple: FAISS's original inverted lists use OpenMP for parallelism, which works great until you try to compose it with other parallel libraries. Then you get into this weird situation where threads are fighting over locks, waiting for each other like cars at a four-way stop where everyone arrived at the same time.

Intel's Threading Building Blocks (TBB) takes a different approach. Instead of "here are 8 threads, go wild," it says "here are tasks that might be independent, let me figure out the optimal execution." It's like having a really smart scheduler that actually understands dependencies.

Our OnDiskInvertedListsTBB replaces OpenMP primitives with TBB parallel patterns:

// Instead of #pragma omp parallel for
tbb::parallel_for(
    tbb::blocked_range<size_t>(0, n, grain_size),
    [&](const tbb::blocked_range<size_t>& range) {
        // Process range.begin() to range.end()
    }
);

size_t OnDiskInvertedListsTBB::calculate_cache_aware_grain_size(
        size_t n, size_t element_size) {
    size_t l3_size = get_l3_cache_size();
    size_t max_concurrency = tbb::this_task_arena::max_concurrency();

    // How many elements fit in L3 per thread?
    size_t cache_per_thread = l3_size / max_concurrency;
    size_t elements_per_cache = cache_per_thread / element_size;

    // Use 1/4 of cache to leave room for other data
    return elements_per_cache / 4;
}

Here's where things get interesting. The original FAISS uses a single file pointer with seek+read. That works fine with a global lock, but kills parallelism. We use POSIX pread/pwrite instead:

// Thread-safe read without moving file pointer
size_t bytes_read = data_stream_->pread(
    codes->data(),    // buffer
    1,                // element size
    codes_size,       // count
    offset           // absolute position
);

Each thread reads from its own position without coordination. No locks, no seeks, just parallel I/O. The kernel handles the complexity.

const uint8_t* OnDiskInvertedListsTBB::get_codes(size_t list_no) const {
    // Check cache first (with TBB concurrent_hash_map)
    if (cache_) {
        return tbb_cache->get_or_load_codes(list_no, [this, list_no]() {
            // Read lock (allows multiple readers)
            tbb::spin_rw_mutex::scoped_lock lock(
                list_rw_mutexes_[list_no]->mutex, false);

            // pread doesn't need exclusive access
            data_stream_->pread(codes.data(), 1, codes_size, offset);
            return codes;
        });
    }
}

Search is where TBB really shines. We use a three-stage pipeline:

1. 1
   Serial input stage: Generate query-list pairs in order
2. 2
   Parallel processing stage: Compute distances for each query
3. 3
   Serial output stage: Write results in order

tbb::parallel_pipeline(
    n,  // max tokens in flight

    // Stage 1: Generate queries
    tbb::make_filter<void, std::pair<size_t, idx_t>>(
        tbb::filter_mode::serial_in_order,
        [&](tbb::flow_control& fc) -> std::pair<size_t, idx_t> {
            if (*idx >= n) {
                fc.stop();
                return {0, -1};
            }
            return std::make_pair(*idx, assign[*idx]);
        }
    ) &

    // Stage 2: Process in parallel
    tbb::make_filter<std::pair<size_t, idx_t>, SearchResult>(
        tbb::filter_mode::parallel,
        [&](std::pair<size_t, idx_t> input) -> SearchResult {
            // Compute distances, keep top-k
            // Each query runs in parallel
        }
    ) &

    // Stage 3: Write results in order
    tbb::make_filter<SearchResult, void>(
        tbb::filter_mode::serial_in_order,
        [&](const SearchResult& result) {
            // Copy to output arrays
        }
    )
);

The pipeline maintains query order (important for reproducibility) while parallelizing the expensive distance computations. And because it's a pipeline, there's natural prefetching - while stage 2 processes query N, stage 1 is already preparing query N+1.