fastset

Fast set implementation for dense, bounded integer collections. Provides quick updates and random access.

The fastset crate provides a custom Set implementation, optimized for managing collections of usize values. Use cases involve having to manage indices of other data structures of a special kind, whose elements are densely packed within a known range and the insert and delete operations are voluminous, i.e., operation predictability and performance take precedence over memory footprint.

Example use cases: - For storing lattice sites of interest in stochastic cellular automata simulations - Managing available or used indices in large arrays. - Tracking slots in memory pools.

fastset::Set is not a good solution for memory contrained applications or for applications with storage need for sparse elements spread over a extended range.

Features

• Specialized for usize: Tailored specifically for handling usize values, ideal for indexing scenarios.
• High-Performance Operations: Uses direct memory access for fast insertions, deletions, and random access.
• Random Access: Includes a random method to retrieve a random element from the set, essential for simulations and randomized algorithms.
• Optimized for Dense Elements: Efficiency is maximized when elements are closely packed within a pre-determined range.
• Predictable Memory Usage: Memory usage, even if will a large footprint, is predictable and directly related to the maximum element value.

Benchmarks

Benchmarks comparing fastset::Set with hashbrown::HashSet and std::collections::HashSet:

Benchmarks were conducted on a machine with the following specifications:

• Processor: AMD Ryzen™ 5 5600G with Radeon™ Graphics x 12
• Memory: 58.8 GiB
• Operating System: Guix System
• OS Type: 64-bit

Usage

use fastset::{set, Set};
use nanorand::WyRand;

fn main() {
    // Create a set with some initial elements
    let mut set = set![5, 10, 15, 20, 25, 30]; 

    // Check if certain elements are present in the set
    assert!(set.contains(&5));
    assert!(set.contains(&15));
    assert!(set.contains(&25));

    // Display the current elements and the set length
    println!("Initial set: {}, Length: {}", set, set.len());

    // Insert a new element into the set
    if set.insert(35) { println!("Inserted 35 into the set"); }
    println!("Set after inserting 35: {}, Length: {}", set, set.len());
    assert!(set.contains(&20));

    // Remove an element from the set
    if set.remove(&5) { println!("Removed 5 from the set"); }
    println!("Set after removal: {}, Length: {}", set, set.len());
    assert!(!set.contains(&5));

    // Try to take an element from the set, removing it in the process
    if let Some(taken) = set.take(&10) { println!("Took element {} from the set", taken); }
    println!("Set after take: {}, Length: {}", set, set.len());
    assert!(!set.contains(&10));

    // Use the random method to get a random element from the set
    let mut rng = WyRand::new();
    if let Some(element) = set.random(&mut rng) {
        println!("Randomly selected element: {}", element);
        assert!(set.contains(&element));
        set.remove(&element);
        println!("Removed {} from the set", element);
        assert!(!set.contains(&element));
    }
    println!("Set after removal: {}, Length: {}", set, set.len());

    // Display the current elements and the set length
    println!("Final set: {}, Length: {}", set, set.len());
}

Note

This crate was developed in the context of Monte Carlo simulations of spin systems. In such simulations, it's required to track and provide fast access to elements of a given sign (positive or negative energy) from an array whose elements (spin energies) are rapidly changing signs due to Monte Carlo updates. The fastset Set facilitates relatively efficient tracking and manipulation of these elements over extended periods, improving the performance of simulations.