lock-free 0.1.2

High-performance lock-free data structures for Rust with zero dependencies
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

# Lock-Free Data Structures for Rust

A high-performance collection of lock-free data structures implemented in pure Rust with zero external dependencies.

## Features

- 🚀 **World-class performance**: Stack (50M+ ops/sec), Queue (70M+ ops/sec), HashMap (250M+ ops/sec for reads)
- 🔒 **Lock-free**: No mutexes, no blocking, suitable for real-time systems
- 📦 **Zero dependencies**: Pure Rust implementation
- 🧵 **Thread-safe**: All structures are Send + Sync
- 💾 **Cache-friendly**: Optimized memory layout with cache-line alignment

## Data Structures

### Stack
- **Algorithm**: Treiber's algorithm
- **Performance**: 50-60M ops/sec
- **Use cases**: LIFO workloads, undo operations
- **⚠️ Warning**: Avoid high-concurrency mixed push/pop patterns. Use producer/consumer patterns for safety.

### Queue  
- **Algorithm**: Bounded array with sequence numbers
- **Performance**: 70-80M ops/sec
- **Use cases**: FIFO workloads, task queues, producer/consumer

### HashMap
- **Algorithm**: Robin Hood hashing with open addressing
- **Performance**: 15-25M ops/sec (mixed), 250M+ ops/sec (parallel reads)
- **Use cases**: Concurrent caching, shared state

### List (Skip List)
- **Algorithm**: Lock-free skip list
- **Performance**: 5-10M ops/sec
- **Use cases**: Ordered collections, range queries

## Quick Start

```rust
use lock_free::{Stack, Queue, HashMap};

// Stack example
let stack = Stack::new();
stack.push(42);
assert_eq!(stack.pop(), Some(42));

// Queue example  
let queue = Queue::new(1024); // Capacity must be power of 2
queue.enqueue("hello");
assert_eq!(queue.dequeue(), Some("hello"));

// HashMap example
let map = HashMap::new();
map.insert("key", "value");
assert_eq!(map.get(&"key"), Some("value"));
```

## Performance

All benchmarks on 8-core CPU:

| Structure | Single Thread | Multi Thread (8) | Notes |
|-----------|--------------|------------------|-------|
| Stack | 50M ops/sec | 20M ops/sec | Use producer/consumer pattern |
| Queue | 70M ops/sec | 25M ops/sec | World-class performance |
| HashMap | 15M ops/sec | 250M ops/sec (reads) | Excellent read scaling |
| SkipList | 5-10M ops/sec | Good scaling | O(log n) operations |

## Safety Notes

This library uses `unsafe` Rust for performance. While thoroughly tested, please note:

1. **Stack**: Has known issues with high-concurrency mixed push/pop operations. Use producer/consumer patterns.
2. **Memory ordering**: Uses relaxed ordering where safe for maximum performance.
3. **No memory reclamation**: Some structures may not immediately free memory (trade-off for performance).

## Building

```bash
cargo build --release
cargo test
cargo bench
```

## Examples

See the `examples/` directory for more usage patterns:
- `bench_all.rs` - Comprehensive benchmarks
- `test_simple.rs` - Basic functionality tests
- `bench_safe.rs` - Safe usage patterns

## License

MIT OR Apache-2.0 (dual licensed)

## Contributing

Contributions welcome! Please ensure:
- All tests pass
- Benchmarks show no regression
- Document any unsafe code
- Add tests for new features

## Acknowledgments

Inspired by:
- Treiber's Stack algorithm
- Michael & Scott Queue
- Harris's List
- Split-ordered lists for hash tables