A Rust implementation of a persistent data structure that provides O(1) append and concatenation operations through structural sharing.
- O(1) Append/Prepend Operations: Add elements to your chunk in constant time
- O(1) Concatenation: Combine two chunks efficiently
- Immutable/Persistent: All operations create new versions while preserving the original
- Memory Efficient: Uses structural sharing via reference counting
- Safe Rust: Implemented using 100% safe Rust
This implementation is inspired by the concepts presented in Hinze and Paterson's work on Finger Trees1, though simplified for our specific use case. While our implementation differs in structure, it shares similar performance goals and theoretical foundations.
Finger Trees are a functional data structure that supports:
- Access to both ends in amortized constant time
- Concatenation in logarithmic time
- Persistence through structural sharing
Our Chunk implementation achieves similar goals through a simplified approach:
- We use
Appendnodes for constant-time additions - The
Concatvariant enables efficient concatenation Rc(Reference Counting) provides persistence and structural sharing
Like Finger Trees, our structure can be viewed as an extension of Okasaki's implicit deques2, but optimized for our specific use cases. While Finger Trees offer a more general-purpose solution with additional capabilities, our implementation focuses on providing:
- Simpler implementation
- More straightforward mental model
- Specialized performance characteristics for append/concat operations
While Finger Trees achieve logarithmic time for concatenation, our implementation optimizes for constant-time operations through lazy evaluation. This means:
- Append, Prepend and concatenation are always O(1)
- The cost is deferred to when we need to materialize the sequence (via
as_vec()) - Memory usage grows with the number of operations until materialization
This trade-off is particularly beneficial in scenarios where:
- Write operations need to be performed extensively
- Multiple transformations are chained
- Not all elements need to be materialized
- Structural sharing can be leveraged across operations
Add this to your Cargo.toml:
[dependencies]
tailcall-chunk = "0.1.0"use chunk::Chunk;
// Create a new chunk and append some elements
let chunk1 = Chunk::default()
.append(1)
.append(2);
// Create another chunk
let chunk2 = Chunk::default()
.append(3)
.append(4);
// Concatenate chunks in O(1) time
let combined = chunk1.concat(chunk2);
// Convert to vector when needed
assert_eq!(combined.as_vec(), vec![1, 2, 3, 4]);use chunk::Chunk;
#[derive(Debug, PartialEq)]
struct Person {
name: String,
age: u32,
}
let people = Chunk::default()
.append(Person {
name: "Alice".to_string(),
age: 30
})
.append(Person {
name: "Bob".to_string(),
age: 25
});
// Access elements
let people_vec = people.as_vec();
assert_eq!(people_vec[0].name, "Alice");
assert_eq!(people_vec[1].name, "Bob");The Chunk type uses structural sharing through reference counting (Rc), which means:
- Appending or concatenating chunks doesn't copy the existing elements
- Memory is automatically freed when no references remain
- Multiple versions of the data structure can coexist efficiently
use chunk::Chunk;
let original = Chunk::default().append(1).append(2);
let version1 = original.clone().append(3); // Efficient cloning
let version2 = original.clone().append(4); // Both versions share data| Operation | Time Complexity | Space Complexity |
|---|---|---|
new() |
O(1) | O(1) |
append() |
O(1) | O(1) |
concat() |
O(1) | O(1) |
transform() |
O(1) | O(1) |
transform_flatten() |
O(1) | O(1) |
as_vec() |
O(n) | O(n) |
clone() |
O(1) | O(1) |
The following table compares the actual performance of Chunk vs Vector operations based on our benchmarks (lower is better):
| Operation | Chunk Performance | Vector Performance | Faster |
|---|---|---|---|
| Append | 604.02 µs | 560.58 µs | Vec is ~1.08 times faster |
| Prepend | 1.63 ms | 21.95 ms | Chunk is ~13.47 times faster |
| Concat | 71.17 ns | 494.45 µs | Chunk is ~6,947 times faster |
| Clone | 4.16 ns | 1.10 µs | Chunk is ~264 times faster |
Note: These benchmarks represent specific test scenarios and actual performance may vary based on usage patterns. Chunk operations are optimized for bulk operations and scenarios where structural sharing provides benefits. View the complete benchmark code and results in our operations.rs benchmark file.
The Chunk<A> type is implemented as an enum with four variants:
Empty: Represents an empty chunkSingle: Represents a chunk with a single elementConcat: Represents the concatenation of two chunksTransformFlatten: Represents a lazy transformation and flattening of elements
The data structure achieves its performance characteristics through:
- Structural sharing using
Rc - Lazy evaluation of concatenation and transformations
- Immutable operations that preserve previous versions
We welcome contributions! Here's how you can help:
- Fork the repository
- Create your feature branch (
git checkout -b feature/amazing-feature) - Commit your changes (
git commit -am 'Add some amazing feature') - Push to the branch (
git push origin feature/amazing-feature) - Open a Pull Request
Please make sure to:
- Update documentation
- Add tests for new features
- Follow the existing code style
- Update the README.md if needed
This project is licensed under either of
- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.