VelocityX

A comprehensive lock-free data structures library designed for high-performance concurrent programming in Rust.

🌐 View Full Documentation

🚀 Features

• MPMC Queue - Multi-producer, multi-consumer bounded queue with zero locks
• Concurrent HashMap - Lock-free reads with concurrent modifications using striped locking
• Work-Stealing Deque - Chase-Lev deque for task scheduling and parallel workload distribution
• Zero-Cost Abstractions - Optimized for modern multi-core processors
• Memory Safety - Comprehensive safety guarantees through Rust's type system
• Ergonomic APIs - Designed to guide users toward correct concurrent programming patterns

Performance

Data Structures

MPMC Queue

Multi-producer, multi-consumer queues in both bounded and unbounded variants:

use velocityx::queue::MpmcQueue;

// Bounded queue for predictable memory usage
let queue: MpmcQueue<i32> = MpmcQueue::new(1000);
queue.push(42)?;
let value = queue.pop();
assert_eq!(value, Some(42));

// Consumer thread
let consumer = thread::spawn({
    let queue = queue.clone();
    move || {
        let mut sum = 0;
        while sum < 499500 { // Sum of 0..999
            if let Some(value) = queue.pop() {
                sum += value;
            }
        }
        sum
    }
});

producer.join().unwrap();
let result = consumer.join().unwrap();
assert_eq!(result, 499500);

Concurrent HashMap

use velocityx::map::ConcurrentHashMap;
use std::thread;

let map = ConcurrentHashMap::new();

// Writer thread
let writer = thread::spawn({
    let map = map.clone();
    move || {
        for i in 0..1000 {
            map.insert(i, i * 2);
        }
    }
});

// Reader thread
let reader = thread::spawn({
    let map = map.clone();
    move || {
        let mut sum = 0;
        for i in 0..1000 {
            if let Some(value) = map.get(&i) {
                sum += *value;
            }
        }
        sum
    }
});

writer.join().unwrap();
let result = reader.join().unwrap();
assert_eq!(result, 999000); // Sum of 0, 2, 4, ..., 1998

Work-Stealing Deque

use velocityx::deque::WorkStealingDeque;
use std::thread;

let deque = WorkStealingDeque::new(100);

// Owner thread (worker)
let owner = thread::spawn({
    let deque = deque.clone();
    move || {
        // Push work items
        for i in 0..100 {
            deque.push(i);
        }
        
        // Process own work
        while let Some(task) = deque.pop() {
            // Process task
            println!("Processing task: {}", task);
        }
    }
});

// Thief thread (stealer)
let thief = thread::spawn({
    let deque = deque.clone();
    move || {
        let mut stolen = 0;
        while stolen < 50 {
            if let Some(task) = deque.steal() {
                println!("Stolen task: {}", task);
                stolen += 1;
            }
        }
        stolen
    }
});

owner.join().unwrap();
let stolen_count = thief.join().unwrap();
println!("Stolen {} tasks", stolen_count);

📚 Documentation

API Documentation

Comprehensive API documentation is available on docs.rs.

Performance Characteristics

Thread Safety Guarantees

• MPMC Queue: Completely lock-free, safe for concurrent access from any number of threads
• Concurrent HashMap: Lock-free reads, striped locking for writes
• Work-Stealing Deque: Owner operations are lock-free, thief operations are lock-free

🏗️ Architecture

Design Principles

1. Cache-Line Alignment: Critical data structures are aligned to cache line boundaries to prevent false sharing
2. Memory Ordering: Careful use of memory ordering semantics for correctness and performance
3. ABA Prevention: Proper handling of ABA problems in lock-free algorithms
4. Incremental Operations: Non-blocking resize and rehash operations where possible

Memory Layout

┌─────────────────────────────────────────────────────┐
│                    VelocityX                         │
├─────────────────────────────────────────────────────┤
│  Queue Module                                        │
│  ├── MpmcQueue (lock-free ring buffer)              │
│  └── Cache-aligned atomic indices                    │
├─────────────────────────────────────────────────────┤
│  Map Module                                          │
│  ├── ConcurrentHashMap (striped locking)           │
│  ├── Robin hood hashing                              │
│  └── Incremental resizing                           │
├─────────────────────────────────────────────────────┤
│  Deque Module                                        │
│  ├── WorkStealingDeque (Chase-Lev)                  │
│  ├── Owner/thief operations                          │
│  └── Circular buffer                                 │
└─────────────────────────────────────────────────────┘

🧪 Testing

VelocityX includes comprehensive testing:

• Unit Tests: Individual operation correctness and edge cases
• Concurrency Tests: High-contention scenarios with multiple threads
• Stress Tests: Long-running stability tests
• Property-Based Tests: Randomized testing with invariants
• Memory Safety Tests: Drop safety and memory leak detection

Run tests with:

cargo test

For comprehensive testing including stress tests:

cargo test --features "test-stress"

📊 Benchmarks

Performance benchmarks comparing VelocityX against standard library alternatives:

cargo bench

Benchmark Results (Intel i7-9700K, Rust 1.65)

Results are approximate and may vary by hardware and workload.

🔧 Configuration

Feature Flags

• default: Standard library support
• serde: Serialization support for data structures
• unstable: Unstable features (requires nightly Rust)
• test-stress: Additional stress tests (for testing only)

Optimization Tips

1. Choose Right Capacity: Pre-size data structures to avoid resizing overhead
2. Monitor Contention: Use size() methods to detect backpressure
3. Batch Operations: When possible, batch operations to reduce atomic overhead
4. NUMA Awareness: Consider NUMA topology for large deployments

🚀 Use Cases

VelocityX is ideal for:

• High-Throughput Message Passing: Distributed systems, event sourcing
• Concurrent Task Scheduling: Async runtimes, thread pools
• Lock-Free Caching: Web applications, microservices
• Parallel Data Processing: ETL pipelines, analytics
• Real-Time Systems: Trading platforms, gaming servers

🤝 Contributing

We welcome contributions! Please see our Contributing Guide for details.

Development Setup

git clone https://github.com/velocityx/velocityx.git

cd velocityx

cargo build

cargo test

Code Quality

All code must pass:

cargo clippy -- -D warnings

cargo fmt --check

📞 Support & Community

• 📚 Full Documentation: quefep.uk/velocityx
• 📖 API Reference: docs.rs/velocityx
• 🐛 Issues: GitHub Issues
• 💬 Discussions: GitHub Discussions

📄 License

This project is dual-licensed under either:

• MIT License
• Apache License, Version 2.0

at your option.

🙏 Acknowledgments

VelocityX builds upon the foundational work of researchers and practitioners in concurrent programming:

• Maged Michael - Lock-free algorithms and memory reclamation
• Maurice Herlihy & Nir Shavit - Concurrent data structures theory
• Chase & Lev - Work-stealing deque algorithm
• Crossbeam Team - Excellent Rust concurrent primitives

VelocityX - High-performance concurrent data structures for Rust

🌐 quefep.uk/velocityx | 📦 crates.io/velocityx | 📚 docs.rs/velocityx