-
Notifications
You must be signed in to change notification settings - Fork 2
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Optimize performance #44
Comments
Depending on how large the serialized tree is we may want to store only part of the tree. All we need to store really are the bottom-layer leaf nodes, but this means we have to reconstruct the tree each time we want to generate an inclusion proof. We could store the top |
Interesting to note that de-referencing a heap variable well copy it to the stack (at least for a box): https://doc.rust-lang.org/rust-by-example/std/box.html If you do the same memory check with a vector you see that it takes 24 bytes on the stack no matter how many elements you push to it: use std::mem;
let mut a = Vec::<Coordinate>::new();
for i in 0..10000 {
a.push(Coordinate {
x: i,
y: i as u8,
});
}
println!("Vec occupies {} bytes on the stack",
mem::size_of_val(&a)); |
A note from inside single_threaded::build_node
|
A note from multi_threaded::get_num_nodes_left_of
|
Serialization/deserialization of the tree might be too slow at the input sizes we will be operating the code on, so it might be a good idea to try using a database as storage of the tree nodes as apposed to a hashmap. Some further details on other options here: #68 Also: |
Ideally we should move the storage of nodes to a database. It will allow instant save & load of the tree, at the cost of being more expensive to build. |
The performance of the Bulletproofs generation and verification is not something we have full control over in this repo so that is not the topic of this issue.
What we do have full control over is tree construction and path generation / verification. There is likely a bunch of optimization that can be done here if by just using better Rust progamming technique.
Currently the store of the tree is a hashmap but maybe this is not the best data structure to use. Reading material:
There may also be some ways to improve performance by minimizing the amount of data that is copied (rather passing pointers around). Reading material:
Another thing we can do to improve the tree constructor performance is try to find a pre-defined binary tree data structure that allows sparse trees and a custom merge function. This has been tried before (#12) and was not fruitful but it might be worth taking another look. It might be useful to read the BTree implementation code to get some inspiration on optimizations.
The thing with the tree is that we need to access it from the bottom up (for inclusion proof calculation), which seems to rule out linked nodes because of Rust's ownership model. But
Rc<T>
allows for multiple references to the same data. Rc doesn't work when doing concurrency but there seems to be an alternate to use there.A lot of the structs defined in the code have an underlying 256 piece of data represented as a u8 array. Arrays of this type may be stored on the stack so we need to check that these are actually stored on the heap to prevent stack overflow. We could possibly wrap the values in a Box to make sure they are stored on the heap. Generally the data stored in these u8 arrays does not change, it only needs to change ownership. So the heap seems to be the best place for this data to be stored.
The text was updated successfully, but these errors were encountered: