8000 Big ol' rewrite by mappum · Pull Request #15 · turbofish-org/merk · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Big ol' rewrite #15

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.

Sign up for GitHub

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

Jump to bottom
Merged
merged 111 commits into from
Aug 22, 2019
Merged

Big ol' rewrite #15

merged 111 commits into from
Aug 22, 2019

Conversation

mappum
Copy link
Collaborator
@mappum mappum commented Aug 16, 2019 •
edited
Loading

This WIP PR contains the changes I have been working on for the past few months, which have over time replaced all parts of the existing codebase. While the tree algorithms have not changed and feature-wise it is in the same place as a few months ago, the internal types and interfaces have changed a lot and have resulted in much better code (the second time around I'm more experienced with Rust).

Main improvements:

  • Caching/pruning - It is now possible to keep some or all tree nodes in memory across batches, meaning we don't have to fetch them from disk. This results in ~2.5x single-core performance increases if the entire tree can be held in memory, with the bottleneck then being disk writes.
  • Succinctness - Comparable functions have been reduced by 50% LOC throughout the codebase.
  • Maintainability - Saner abstractions in the internal interfaces, it will be much easier to change the code in the future.
  • Performance - Compared to the previous benchmark of 18k updates per second, we can now get ~32k on a single core with <30MB memory usage (or 76k with the tree fully held in RAM) due to various optimizations. (These figures are on my 2017 MBP, with a 1M node tree).

I'll finalize this PR once the core Merk store API is finished, leaving it where the master branch currently is.

mappum added 30 commits July 5, 2019 19:05
10000
@mappum
Lots of progress on op refactor
d5f1744
@mappum
Progress on refactor
06b3db2
@mappum
Wrote some tree operation code with a cleaner (and non-existent) tree…
6f5d5ad 
…-walking interface
@mappum
Applied new tree-walking interface to Tree::recurse
699aceb
@mappum
Moved op methods to Context
2e56804
@mappum
Cleared out existing code so we can start fresh
cb44864
@mappum
Added new Tree implementation
6d8ce8e
@mappum
Merge branch 'op-refactor' of github.com:mappum/merk into op-refactor
ee6d736
@mappum
Restored some deleted code, added OwnedWalker
e61b202
@mappum
Add Wrap trait
6420105
@mappum
Implement op methods on OwnedWalker
bc1b60c
@mappum
Started implementing ModTree
e29f5f3
@mappum
Progress on combining ModTree into Tree, removing Node Link fields
768376e
@mappum
Progress in refactoring Tree structure types (e.g. removed Node, adde…
7410199 
…d KV)
@mappum
Fixed compiler errors
14832b1
@mappum
OwnedWalker -> Walker
b9707e6
@mappum
Updated and enabled Tree unit tests
b33fa6b
@mappum
More Tree unit test coverage
d798eba
@mappum
Started implementing commit
939f25c
@mappum
Enable test cases that depended on commit
fa01684
@mappum
Updated child_hash test fixture
39d7309
@mappum
Added KV.take_key(), tree.take_key(), and link.to_pruned()
1e9c52f
@mappum
Updated walker tests
6941e1f
@mappum
Remove unnused Wrap trait
bf59a89
@mappum
Link unit tests
980adaa
@mappum
Remove unnused ModTree
ec6e219
@mappum
Added Owner type to allow temporary ownership via mutable references,…
e90a495 
… enforcing at compile-time that the value gets put back after it is no longer needed
@mappum
Use owned signature for Tree#detach(), but preserve same API for Walk…
110e02c 
…er#walk()
@mappum
Created dummy Tree#encode/decode methods
da71d11
@mappum
Resurrecting top-level Merk API
1cbb6e6
@mappum mappum mentioned this pull request Aug 22, 2019
Closed
@mappum mappum marked this pull request as ready for review August 22, 2019 21:00
@mappum
Copy link
Collaborator Author
mappum commented Aug 22, 2019

Merging these changes into develop because we're now at parity with what we had before the rewrite. Still needs a few things before a real release though.

@mappum mappum merged commit 01da1fc into develop Aug 22, 2019
@mappum mappum deleted the op-refactor branch August 22, 2019 21:01
@mappum mappum mentioned this pull request Aug 29, 2019
Open
@mappum mappum restored the op-refactor branch January 17, 2020 23:33
@mappum mappum deleted the op-refactor branch March 31, 2021 07:13
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@mappum @davebryson
0