search

filecoin-project / go-amt-ipld

Implementation of an array mapped trie using go and ipld
Other
9 stars 15 forks source link

feat: implement parallel diffing #67

Closed frrist closed 2 years ago

frrist commented 2 years ago

Why

Explored idea in https://github.com/filecoin-project/go-amt-ipld/pull/62 with bench-marking and was able to achieve a 2-3x speed up (bitwidth of 5-6) vs serial diffing. Furthermore https://github.com/filecoin-project/go-amt-ipld/pull/62 was used in a test branch of lily https://github.com/filecoin-project/lily/pull/880 where we observed a significant speed up (from mins to milliseconds) in its processing pipeline (diffing actor states, state-trees, miner and market AMTs).

What

parallelDiffNode is mostly a copy of diffNode with the addition of an errgroup to parallelize recursive access. parallelDiffNode is called from within diffAndAssertLength for all tests.

codecov-commenter commented 2 years ago

Codecov Report

Merging #67 (742d422) into master (267d1e7) will increase coverage by 3.65%. The diff coverage is 75.22%.

Impacted file tree graph

@@            Coverage Diff             @@
##           master      #67      +/-   ##
==========================================
+ Coverage   60.94%   64.60%   +3.65%     
==========================================
  Files           8        9       +1     
  Lines         973     1308     +335     
==========================================
+ Hits          593      845     +252     
- Misses        257      313      +56     
- Partials      123      150      +27
Impacted Files Coverage Δ
diff_parallel.go 75.22% <75.22%> (ø)