6 releases
0.2.0 | Jul 14, 2024 |
---|---|
0.1.4 | Nov 28, 2023 |
#140 in Memory management
22 downloads per month
49KB
459 lines
Hash Cons Library
The Hash Cons Library (hash_cons
) is a Rust library that implements efficient hash consing techniques, making it a robust choice for both multi-threaded and single-threaded Rust applications.
At its core, the library is designed to focus on type-safety, efficiency, and zero-cost abstractions.
Hash Cons
Hash consing is an advanced technique used in optimizing memory usage and enhancing performance in data-intensive applications. It involves sharing of immutable data structures, reducing redundant memory allocation by ensuring that identical data is stored only once. This method is particularly beneficial in scenarios where repeated data structures, like trees or graphs, are prevalent. By employing hash consing, the library guarantees efficient memory management and rapid data access, leading to a significant boost in application performance. This technique is not only crucial for achieving optimal memory efficiency but also plays a vital role in ensuring the scalability and speed of your applications.
Efficiency and Idiomatic Rust
This library is designed to be inherently idiomatic to Rust, ensuring efficient memory management and optimal performance. It utilizes Rust's unique ownership and borrowing rules to manage immutable data structures. The key feature is its tunable memory management: when a value is no longer referred to anywhere in your program, the library automatically deallocates it due to enabled auto_cleanup
feature by default, preventing memory leaks and optimizing resource usage. This makes it an excellent tool for applications where duplicate data structures are common, ensuring memory efficiency.
Features
- auto_cleanup: Enabled by default, this feature allows the library to automatically clean up and manage memory efficiently by removing unused entries.
- single-threaded: Disabled by default, enabling this feature switches the library to a single-threaded implementation for environments where thread safety is not required. Users may notice some performance issues in multi-threaded environemnts.
Usage
To integrate hash_cons
into your project, add it as a dependency in your Cargo.toml
:
[dependencies]
hash_cons = "0.2.0" # Replace with the actual version
By default, the library operates in a multi-threaded environment with auto_cleanup enabled. For single-threaded support, enable the single-threaded
feature:
# Default multi-threaded with auto_cleanup enabled
hash_cons = "0.2.0"
# For single-threaded environments with auto_cleanup enabled
hash_cons = { version = "0.2.0", features = ["single-threaded"] }
# For multi-threaded environments with auto_cleanup disabled
hash_cons = { version = "0.2.0", default-features = false }
# For single-threaded environments with auto_cleanup disabled
hash_cons = { version = "0.2.0", default-features = false, features = ["single-threaded"] }
Examples
Multi-Threaded Usage (Default)
[dependencies]
hash_cons = "0.2.0" # Replace with the actual version
use hash_cons::{HcTable, Hc};
use std::thread;
#[derive(Hash, PartialEq, Eq)]
enum BoolExpr {
Const(bool),
And(Hc<BoolExpr>, Hc<BoolExpr>),
Or(Hc<BoolExpr>, Hc<BoolExpr>),
Not(Hc<BoolExpr>),
}
fn main() {
let table: HcTable<BoolExpr> = HcTable::new();
let thread_handle_hc_false = thread::spawn(move || {
table.hashcons(BoolExpr::Const(false))
});
let hc_false: Hc<BoolExpr> = thread_handle_hc_false.join().unwrap(); // Safe for concurrent use across threads
}
Single-Threaded Usage
[dependencies]
hash_cons = { version = "0.2.0", features = ["single-threaded"] }
use hash_cons::{HcTable, Hc};
#[derive(Hash, PartialEq, Eq)]
enum BoolExpr {
Const(bool),
And(Hc<BoolExpr>, Hc<BoolExpr>),
Or(Hc<BoolExpr>, Hc<BoolExpr>),
Not(Hc<BoolExpr>),
}
fn main() {
let table: HcTable<BoolExpr> = HcTable::new();
let const_true = BoolExpr::Const(true);
let hc_true: Hc<BoolExpr> = table.hashcons(const_true);
drop(hc_true);// hc_true is automatically removed from the table when dropped from the memory
}
Auto Cleanup Disabled for multi-threaded environments (Default)
[dependencies]
hash_cons = { version = "0.2.0", default-features = false }
use hash_cons::{HcTable, Hc};
use std::thread;
#[derive(Hash, PartialEq, Eq)]
enum BoolExpr {
Const(bool),
And(Hc<BoolExpr>, Hc<BoolExpr>),
Or(Hc<BoolExpr>, Hc<BoolExpr>),
Not(Hc<BoolExpr>),
}
fn main() {
let table: HcTable<BoolExpr> = HcTable::new();
let table_clone = table.clone();
let thread_handle_hc_true = thread::spawn(move || {
table_clone.hashcons(BoolExpr::Const(true))
});
let hc_true: Hc<BoolExpr> = thread_handle_hc_true.join().unwrap(); // Safe for concurrent use across threads
assert_eq!(table.len(), 1);
drop(hc_true);
table.cleanup(); //hc_true is removed from the table after it has been dropped and `cleanup()` is called on the table.
assert_eq!(table.len(), 0);
}
Auto Cleanup Disabled for single-threaded environments
[dependencies]
hash_cons = { version = "0.2.0", default-features = false, features = ["single-threaded"] }
use hash_cons::{HcTable, Hc};
#[derive(Hash, PartialEq, Eq)]
enum BoolExpr {
Const(bool),
And(Hc<BoolExpr>, Hc<BoolExpr>),
Or(Hc<BoolExpr>, Hc<BoolExpr>),
Not(Hc<BoolExpr>),
}
fn main() {
let table: HcTable<BoolExpr> = HcTable::new();
let const_true = BoolExpr::Const(true);
let hc_true: Hc<BoolExpr> = table.hashcons(const_true);
drop(hc_true);
assert_eq!(table.len(), 1);
table.cleanup();//hc_true is removed from the table after it has been dropped and `cleanup()` is called on the table.
assert_eq!(table.len(), 0);
}
Contributing
Contributions and suggestions are welcomed to make hash_cons
better. If you have ideas or improvements, feel free to submit a pull request or open an issue in the repository.
License
Licensed under the MIT License. See the LICENSE file for more details.