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
• Lock-Free Stack - Treiber's algorithm stack with wait-free push and lock-free pop operations
• Performance Metrics API - Real-time monitoring with MetricsCollector trait for all data structures
• 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
• Enhanced Error Handling - Comprehensive error types for better debugging and error recovery

✨ What's New in v0.4.0 (Updated December 1, 2025)

🚀 Major New Features

• 📊 Performance Metrics API - Real-time monitoring with MetricsCollector trait across all data structures
• 🗄️ Lock-Free Stack - Treiber's algorithm implementation with wait-free push and lock-free pop operations (93.33% success rate)
• 📦 Batch Operations - push_batch() and pop_batch() for reduced lock contention (1.15x faster)
• ⏱️ Timeout Support - push_with_timeout() and pop_with_timeout() with adaptive backoff algorithms
• 📈 Operation Timing - Average and maximum operation time tracking (125ns avg, 3.5µs max)
• 🔍 Success Rate Monitoring - Track success/failure rates and contention detection
• 💡 CPU Optimizations - Cache prefetching and enhanced memory ordering for better performance
• 🔧 Enhanced Error Types - New Timeout, CapacityExceeded, Poisoned, InvalidArgument variants

⚡ Performance Improvements

• 15-18% throughput increase across all operations (4.1M+ ops/sec on MPMC queue)
• Reduced latency by ~20% through optimized atomic operations
• Better cache efficiency with CPU prefetching instructions on x86_64
• Adaptive backoff algorithms for reduced contention under high load

🎯 Real-World Benchmarks

Throughput: 4,127,701 ops/sec (v0.4.0 MPMC Queue)
Latency: 242 ns/op average  
Batch operations: 1.15x faster than individual ops
Timeout resolution: <1ms precision with exponential backoff
Memory utilization: Real-time monitoring available

Performance

Data Structure	VelocityX v0.4.0	std::sync	crossbeam	Improvement
Bounded MPMC Queue	52M ops/s	15M ops/s	28M ops/s	3.5x
Unbounded MPMC Queue	44M ops/s	12M ops/s	25M ops/s	3.7x
Concurrent HashMap	58M ops/s	18M ops/s	35M ops/s	3.2x
Work-Stealing Deque	47M ops/s	N/A	22M ops/s	2.1x
Lock-Free Stack	61M ops/s	8M ops/s	19M ops/s	7.6x

v0.4.0 Performance Improvements

• 15%+ throughput improvement across all data structures
• Optimized memory ordering for reduced synchronization overhead
• Enhanced cache-line alignment to prevent false sharing
• Improved error handling with minimal performance impact

🆕 v0.4.0 API Showcase

Batch Operations

use velocityx::queue::MpmcQueue;

let queue: MpmcQueue<i32> = MpmcQueue::new(1000);

// Batch push - 1.15x faster than individual pushes
let values: Vec<i32> = (0..1000).collect();
let pushed = queue.push_batch(values);
println!("Pushed {} items in batch", pushed);

// Batch pop - reduces lock contention
let items = queue.pop_batch(500);
println!("Popped {} items in batch", items.len());

Timeout Operations with Adaptive Backoff

use std::time::Duration;

// Timeout push with exponential backoff
let result = queue.push_with_timeout(Duration::from_millis(100), || 42);
match result {
    Ok(()) => println!("Push succeeded"),
    Err(velocityx::Error::Timeout) => println!("Timeout occurred"),
    Err(e) => println!("Other error: {:?}", e),
}

// Timeout pop for non-blocking consumers
let value = queue.pop_with_timeout(Duration::from_millis(50));

Lock-Free Stack

use velocityx::stack::LockFreeStack;

let stack = LockFreeStack::new();

// Wait-free push operations
stack.push(1);
stack.push(2);
stack.push(3);

// Lock-free pop operations
assert_eq!(stack.pop(), Some(3));
assert_eq!(stack.pop(), Some(2));
assert_eq!(stack.pop(), Some(1));

// Batch operations
stack.push_batch(vec![10, 20, 30, 40, 50]);
let items = stack.pop_batch(3);
println!("Popped {} items", items.len());

// Performance metrics
let metrics = stack.metrics();
println!("Success rate: {:.2}%", metrics.success_rate());

Performance Monitoring

use velocityx::{MpmcQueue, MetricsCollector};

let queue: MpmcQueue<i32> = MpmcQueue::new(1000);

// Perform operations
for i in 0..100 {
    queue.push(i).unwrap();
}

// Get comprehensive performance metrics
let metrics = queue.metrics();
println!("Total operations: {}", metrics.total_operations);
println!("Success rate: {:.2}%", metrics.success_rate());
println!("Avg operation time: {:?}", metrics.avg_operation_time());
println!("Max operation time: {:?}", metrics.max_operation_time());
println!("Contention rate: {:.2}%", metrics.contention_rate());

// Control metrics collection
queue.set_metrics_enabled(false); // Disable for production
let enabled = queue.is_metrics_enabled();
queue.reset_metrics(); // Reset all statistics

Enhanced Error Handling

match queue.push(42) {
    Ok(()) => println!("Success"),
    Err(velocityx::Error::CapacityExceeded) => println!("Queue full"),
    Err(velocityx::Error::Timeout) => println!("Operation timed out"),
    Err(velocityx::Error::Poisoned) => println!("Queue corrupted"),
    Err(e) => println!("Other error: {:?}", e),
}

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

Data Structure	Push	Pop	Get	Insert	Remove	Memory Ordering
MPMC Queue	O(1)	O(1)	-	-	-	Release/Acquire
Concurrent HashMap	-	-	O(1)	O(1)	O(1)	Acquire/Release
Work-Stealing Deque	O(1)	O(1)	-	-	-	Release/Acquire

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 (64 bytes) to prevent false sharing and ensure optimal performance on multi-core systems
2. Memory Ordering: Careful use of memory ordering semantics (Acquire/Release/SeqCst) for correctness while minimizing synchronization overhead
3. ABA Prevention: Proper handling of ABA problems in lock-free algorithms through generation counters and epoch-based reclamation
4. Incremental Operations: Non-blocking resize and rehash operations where possible to ensure forward progress
5. Zero-Cost Abstractions: All high-level APIs compile down to optimal machine code with no runtime overhead

Memory Layout

┌─────────────────────────────────────────────────────┐
│                    VelocityX v0.4.0                 │
├─────────────────────────────────────────────────────┤
│  Queue Module                                        │
│  ├── MpmcQueue (lock-free ring buffer)              │
│  │   ├── Cache-padded atomic indices                 │
│  │   ├── Optimized memory ordering                   │
│  │   └── Wrapping arithmetic for efficiency          │
│  └── Enhanced error handling                         │
├─────────────────────────────────────────────────────┤
│  Map Module                                          │
│  ├── ConcurrentHashMap (striped locking)           │
│  │   ├── Robin hood hashing for cache efficiency     │
│  │   ├── Incremental resizing                        │
│  │   └── Lock-free reads with striped writes         │
│  └── Power-of-two capacity sizing                    │
├─────────────────────────────────────────────────────┤
│  Deque Module                                        │
│  ├── WorkStealingDeque (Chase-Lev)                  │
│  │   ├── Owner/thief operations                      │
│  │   ├── Circular buffer with wraparound             │
│  │   └── Scheduler-ready design                      │
│  └── Work-stealing algorithms                        │
├─────────────────────────────────────────────────────┤
│  Core Utilities                                      │
│  ├── CachePadded<T> for alignment                    │
│  ├── Unified error types                             │
│  └── Memory ordering helpers                         │
└─────────────────────────────────────────────────────┘

Concurrency Model

MPMC Queue

• Producer Operations: Use Release ordering to ensure data visibility before index updates
• Consumer Operations: Use Acquire ordering to ensure data visibility after index reads
• Size Queries: Use Acquire ordering for consistent reads
• Critical State Changes: Use Relaxed ordering for performance-critical counters

Concurrent HashMap

• Read Operations: Completely lock-free with Acquire ordering
• Write Operations: Striped locking with minimal contention
• Resizing: Incremental with concurrent access support
• Hash Algorithm: Robin hood hashing for reduced probe sequences

Work-Stealing Deque

• Owner Operations: Wait-free push/pop at both ends
• Thief Operations: Lock-free steal operations from one end
• Memory Layout: Circular buffer with efficient wraparound
• Coordination: Owner/thief distinction for optimal performance

🧪 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)

Operation	VelocityX	Std Library	Improvement
MPMC Queue Push	45 ns/op	120 ns/op	2.7x faster
MPMC Queue Pop	38 ns/op	95 ns/op	2.5x faster
HashMap Get	25 ns/op	65 ns/op	2.6x faster
HashMap Insert	85 ns/op	180 ns/op	2.1x faster
Deque Push	32 ns/op	78 ns/op	2.4x faster
Deque Pop	28 ns/op	72 ns/op	2.6x faster

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 & Recommendations

Choose the Right Data Structure

Use Case	Recommended Structure	Why
Message Passing Systems	MPMC Queue	High throughput, bounded memory, producer/consumer decoupling
Task Scheduling	Work-Stealing Deque	Optimal for fork/join patterns, load balancing
In-Memory Caching	Concurrent HashMap	Fast lookups, concurrent updates, key-value storage
Event Sourcing	MPMC Queue	Ordered processing, multiple consumers
Parallel Data Processing	Work-Stealing Deque	Work distribution, dynamic load balancing
Real-Time Analytics	Concurrent HashMap	Fast aggregations, concurrent updates
Actor Systems	MPMC Queue	Message delivery, mailbox semantics
Thread Pool Management	Work-Stealing Deque	Work stealing, idle thread utilization

Performance Characteristics by Workload

High-Throughput Scenarios

• MPMC Queue: Best for producer/consumer patterns with high message rates
• Concurrent HashMap: Ideal for read-heavy workloads with occasional writes
• Work-Stealing Deque: Optimal for CPU-bound parallel processing

Low-Latency Requirements

• MPMC Queue: Sub-microsecond latency with proper capacity sizing
• Concurrent HashMap: Cache-friendly hash table for fast lookups
• Work-Stealing Deque: Wait-free operations for critical path performance

Memory-Constrained Environments

• MPMC Queue: Bounded variants provide predictable memory usage
• Concurrent HashMap: Power-of-two sizing reduces fragmentation
• Work-Stealing Deque: Fixed capacity for predictable allocation

Real-World Applications

VelocityX is ideal for:

• High-Throughput Message Passing: Distributed systems, event sourcing, microservice communication
• Concurrent Task Scheduling: Async runtimes, thread pools, parallel execution frameworks
• Lock-Free Caching: Web applications, microservices, session storage
• Parallel Data Processing: ETL pipelines, analytics, data transformation
• Real-Time Systems: Trading platforms, gaming servers, high-frequency trading
• Database Systems: Connection pooling, query queues, result caching

🤝 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