ktsu.Containers
A high-performance collection library for .NET providing specialized container implementations with focus on performance, memory efficiency, and developer experience.
๐ Features
- OrderedCollection: Maintains elements in sorted order with efficient binary search operations
- OrderedSet: Unique elements maintained in sorted order with full ISet support
- RingBuffer: Fixed-size circular buffer optimized for streaming data scenarios
- Comprehensive Benchmarking: World-class performance validation against .NET collections
๐ฆ Collections
OrderedCollection
A collection that maintains elements in sorted order with efficient insertion and search operations.
Key Features:
- O(log n) insertion maintaining sort order
- O(log n) search operations via binary search
- Multiple constructors with capacity and comparer support
- Implements ICollection, IReadOnlyCollection, IReadOnlyList
Best Use Cases:
- Incremental sorted data building
- Frequent search operations on ordered data
- Scenarios requiring both order and random access
OrderedSet
A set implementation that maintains unique elements in sorted order.
Key Features:
- O(log n) Add/Remove/Contains operations
- Full ISet interface support (Union, Intersection, Except, etc.)
- Sorted enumeration without additional sorting cost
- Memory-efficient list-based implementation
Best Use Cases:
- Unique sorted collections
- Set operations with maintained order
- Mathematical set operations with sorted results
RingBuffer
A fixed-size circular buffer optimized for continuous data streams.
Key Features:
- O(1) insertion and access operations
- Automatic wrapping when capacity is reached
Length and IsFull tell whether the next push evicts the oldest element
- Index-based access to buffer elements
- Resizing and resampling capabilities
- Power-of-two sizing for optimal performance
Best Use Cases:
- Streaming data processing
- Fixed-size caches
- Sliding window algorithms
- Audio/signal processing buffers
๐ Performance & Benchmarking
We've implemented a comprehensive benchmarking system using BenchmarkDotNet that validates our implementations against standard .NET collections.
Benchmark Categories
๐ฏ Container-Specific Benchmarks
- OrderedCollection vs List + Sort vs SortedList
- OrderedSet vs HashSet vs SortedSet
- RingBuffer vs Queue vs List with size limiting
๐ Standard Collection Baselines
Performance baselines for all major .NET collections:
- List, HashSet, SortedSet
- Dictionary<TKey,TValue>, SortedDictionary<TKey,TValue>
- Queue, Stack
- ConcurrentDictionary<TKey,TValue>, ConcurrentQueue
๐ Cross-Collection Comparisons
Direct comparisons for common scenarios:
- Building ordered collections (incremental vs bulk)
- Set operations across different implementations
- Memory efficiency patterns
- Real-world usage workflows
๐ Performance Analysis
Advanced scenarios including:
- Scalability testing (1K to 100K+ elements)
- Edge cases and worst-case scenarios
- Memory pressure analysis
- Specialized use cases (sliding windows, priority queues)
Running Benchmarks
Quick Start
The benchmarks are a BenchmarkDotNet console app. Everything after -- goes to BenchmarkDotNet.
# Fast development feedback (short job, fewer iterations)
dotnet run --project Containers.Benchmarks --configuration Release -- --filter "*" --job short
# Compare specific containers
dotnet run --project Containers.Benchmarks --configuration Release -- --filter "*.OrderedSetBenchmarks.*" --exporters html
# Cross-collection analysis
dotnet run --project Containers.Benchmarks --configuration Release -- --filter "*.CrossCollectionComparisonBenchmarks.*" --exporters html csv json
# Full benchmark suite
dotnet run --project Containers.Benchmarks --configuration Release -- --filter "*" --exporters html
Filters
| Filter |
Description |
*.OrderedCollectionBenchmarks.* |
OrderedCollection vs alternatives |
*.OrderedSetBenchmarks.* |
OrderedSet vs alternatives |
*.RingBufferBenchmarks.* |
RingBuffer vs alternatives |
*.StandardCollectionBenchmarks.* |
Built-in .NET collection baselines |
*.CrossCollectionComparisonBenchmarks.* |
Direct cross-collection comparisons |
*.PerformanceAnalysisBenchmarks.* |
Scalability and edge case analysis |
* |
Complete benchmark suite |
Add --job short to any of these for a quicker, less precise run. Run with no --filter to pick benchmarks from an interactive menu.
Command Line Options
# Manual benchmark execution
dotnet run --project Containers.Benchmarks --configuration Release
# Filtered benchmarks
dotnet run --project Containers.Benchmarks --configuration Release -- --filter "*Add*"
# Export results
dotnet run --project Containers.Benchmarks --configuration Release -- --exporters html,csv,json
๐ Installation
<PackageReference Include="ktsu.Containers" Version="1.0.0" />
๐ง Usage Examples
OrderedCollection
// Create and populate
var collection = new OrderedCollection<int>();
collection.Add(3);
collection.Add(1);
collection.Add(2);
// Collection automatically maintains order: [1, 2, 3]
// Efficient search
bool contains = collection.Contains(2); // O(log n) binary search
// Access by index
int first = collection[0]; // 1
// Add a batch in one sorted merge rather than one insert per element
collection.AddRange([5, 0, 4]); // [0, 1, 2, 3, 4, 5]
OrderedSet
// Create with initial data
var set = new OrderedSet<int> { 3, 1, 4, 1, 5 };
// Set contains unique elements in order: [1, 3, 4, 5]
// Set operations
var other = new OrderedSet<int> { 4, 5, 6 };
set.UnionWith(other); // [1, 3, 4, 5, 6]
RingBuffer
// Create fixed-size buffer
var buffer = new RingBuffer<int>(3);
buffer.PushBack(1);
buffer.PushBack(2);
buffer.PushBack(3);
buffer.PushBack(4); // Overwrites first element
// Buffer contains: [2, 3, 4]
// Index access
int latest = buffer[buffer.Count - 1]; // 4 (most recent)
// Length is the size given to the constructor, Resize or Resample
bool evictsNext = buffer.IsFull; // true: Count == Length == 3
buffer.Resample(buffer.Length * 2);
๐ ๏ธ Development
Building
dotnet build
Testing
dotnet test
Benchmarking
# Quick performance check
dotnet run --project Containers.Benchmarks --configuration Release -- --filter "*" --job short
# Comprehensive analysis
dotnet run --project Containers.Benchmarks --configuration Release -- --filter "*" --exporters html
๐ Performance Characteristics
OrderedCollection
- โ
Excellent for: Incremental sorted insertions, frequent searches
- โ ๏ธ Consider alternatives for: Large bulk operations (List + Sort may be faster)
- ๐ฏ Sweet spot: 100-10,000 elements with mixed insert/search operations
OrderedSet
- โ
Excellent for: Unique sorted collections, set operations with order
- โ ๏ธ Consider alternatives for: Pure membership testing (HashSet is faster)
- ๐ฏ Sweet spot: Mathematical set operations requiring sorted results
RingBuffer
- โ
Excellent for: Streaming data, fixed-size caches, sliding windows
- โ ๏ธ Consider alternatives for: Dynamic growth requirements
- ๐ฏ Sweet spot: Continuous data streams with occasional random access
๐ค Contributing
- Fork the repository
- Create a feature branch
- Make your changes
- Add comprehensive tests
- Run benchmarks to validate performance
- Submit a pull request
Adding New Containers
When adding new containers:
- Implement the container in
Containers/
- Add comprehensive tests in
Containers.Test/
- Create benchmark comparisons in
Containers.Benchmarks/
- Update documentation
๐ License
Licensed under the MIT License. See LICENSE.md for details.
๐๏ธ Architecture
The library is built with performance and reliability in mind:
- Zero-allocation operations where possible
- Power-of-two sizing for optimal memory access patterns
- Binary search algorithms for O(log n) performance
- Comprehensive test coverage ensuring reliability
- Benchmark-driven development validating performance claims
๐ฏ Design Principles
- Performance First: Every operation is optimized for speed and memory efficiency
- Standard Compliance: Full compatibility with .NET collection interfaces
- Predictable Behavior: Clear performance characteristics and edge case handling
- Developer Experience: Intuitive APIs with comprehensive documentation
- Validation: Extensive testing and benchmarking ensures reliability
This library provides high-performance alternatives to standard .NET collections while maintaining familiar APIs and adding specialized functionality for common use cases.