Module atomic

A thread-safe, compressed vector of integers with fixed-width encoding.

This module provides AtomicFixedVec, a data structure that behaves like FixedVec but allows for concurrent access and modification from multiple threads. It is designed for scenarios where a large collection of integers must be shared and mutated in a parallel environment.

All operations that modify the vector’s contents are implemented using atomic instructions (e.g., compare-and-swap loops), ensuring thread safety without requiring a global lock.

Atomicity Guarantees and Locking

The atomicity of operations depends on the configured bit_width.

• Power-of-Two bit_width: When the bit_width is a power of two (e.g., 2, 4, 8, 16, 32), and it evenly divides the 64-bit word size, most operations can be performed with lock-free atomic instructions. This is because each element is guaranteed to be fully contained within a single AtomicU64 word.

• Non-Power-of-Two bit_width: When the bit_width is not a power of two, an element’s value may span across the boundary of two AtomicU64 words. Modifying such an element requires updating two words simultaneously, which cannot be done in a single atomic hardware instruction.

To handle this case, AtomicFixedVec uses a technique called lock striping. It maintains a pool of parking_lot::Mutex locks. When an operation needs to modify a value that spans two words, it acquires a lock for that specific memory region. This ensures that the two-word update is itself atomic with respect to other threads, while still allowing concurrent operations on different parts of the vector. This approach avoids a single global lock, preserving a high degree of parallelism.

Future version may introduce a more sophisticated locking strategy

Performance Considerations

The trade-off is between memory compactness and performance. While a non-power-of-two bit_width provides the most space-efficient storage, it may incur a performance overhead for write operations that span word boundaries due to locking.

For write-heavy, performance-critical workloads, choosing a power-of-two bit_width (e.g., by using BitWidth::PowerOfTwo) is recommended to ensure all operations remain lock-free.

Examples

Basic Usage

use compressed_intvec::prelude::*;
use compressed_intvec::fixed::{AtomicFixedVec, UAtomicFixedVec};
use std::sync::Arc;
use std::thread;
use std::sync::atomic::Ordering;

// Create from a slice using the builder.
let initial_data: Vec<u32> = vec![10, 20, 30, 40];
let atomic_vec: Arc<UAtomicFixedVec<u32>> = Arc::new(
    AtomicFixedVec::builder()
        .build(&initial_data)
        .unwrap()
);

// Share the vector across threads.
let mut handles = vec![];
for i in 0..4 {
    let vec_clone = Arc::clone(&atomic_vec);
    handles.push(thread::spawn(move || {
        // Each thread atomically updates its own slot.
        vec_clone.store(i, 63, Ordering::SeqCst);
    }));
}
for handle in handles {
    handle.join().unwrap();
}
assert_eq!(atomic_vec.load(3, Ordering::SeqCst), 63);

Storing Signed Integers

AtomicFixedVec can also store signed integers. The underlying Storable trait uses zig-zag encoding to store signed values efficiently, so that small negative numbers require few bits, just like small positive numbers.

use compressed_intvec::prelude::*;
use compressed_intvec::fixed::{AtomicFixedVec, SAtomicFixedVec};
use std::sync::Arc;
use std::sync::atomic::Ordering;

// The values range from -2 to 1. To also store -3 later, we need 3 bits.
let initial_data: Vec<i16> = vec![-2, -1, 0, 1];
let atomic_vec: Arc<SAtomicFixedVec<i16>> = Arc::new(
    AtomicFixedVec::builder()
        .bit_width(BitWidth::Explicit(3)) // Explicitly set bit width
        .build(&initial_data)
        .unwrap()
);

assert_eq!(atomic_vec.bit_width(), 3);
assert_eq!(atomic_vec.load(0, Ordering::SeqCst), -2);

// Atomically update a value.
atomic_vec.store(0, -3, Ordering::SeqCst);
assert_eq!(atomic_vec.load(0, Ordering::SeqCst), -3);

//! ## Parallel Iteration

When the parallel feature is enabled (by default is enabled), you can use par_iter to process the vector’s elements concurrently.

use compressed_intvec::prelude::*;
use compressed_intvec::fixed::{AtomicFixedVec, UAtomicFixedVec};
use rayon::prelude::*;

let data: Vec<u32> = (0..10_000).collect();
let vec: UAtomicFixedVec<u32> = AtomicFixedVec::builder()
    .build(&data)
    .unwrap();

// Use the parallel iterator to find the sum of all even numbers.
let sum_of_evens: u32 = vec.par_iter()
    .filter(|&x| x % 2 == 0)
    .sum();

let expected_sum: u32 = (0..10_000).filter(|&x| x % 2 == 0).sum();
assert_eq!(sum_of_evens, expected_sum);

Memory Ordering and Locking

The memory Ordering specified in methods like load, store, or fetch_add is always respected, but its interaction with the internal locking mechanism is important to understand.

• Lock-Free Path: When an element is fully contained within a single u64 word, the specified Ordering is applied directly to the underlying atomic instructions, providing the standard guarantees described in the Rust documentation.

• Locked Path: When an element spans two u64 words, a fine-grained mutex is acquired. This lock ensures that the two-word operation is atomic with respect to other locked operations on the same memory region. The specified Ordering is then applied to the atomic writes performed within the locked critical section. This guarantees that the effects of the operation become visible to other threads according to the chosen ordering, but the visibility is still mediated by the mutual exclusion provided by the lock.

Modules

builder

AtomicFixedVec Builder

macros

Macros for AtomicFixedVec

Structs

AtomicFixedVec

A thread-safe, compressed, randomly accessible vector of integers with fixed-width encoding, backed by u64 atomic words.

AtomicFixedVecIter

An iterator over the elements of a borrowed AtomicFixedVec.

AtomicMutProxy

A proxy object for mutable access to an element within an AtomicFixedVec during parallel iteration.

Type Aliases

SAtomicFixedVec

A thread-safe FixedVec for signed integers.

UAtomicFixedVec

A thread-safe FixedVec for unsigned integers.