feat: compute leaf hashes in the Push method

staheri14 commented 1 year ago

Overview

Closes #108 and https://github.com/celestiaorg/nmt/issues/143

Checklist

[x] New and updated code has appropriate documentation
[x] New and updated code has new and/or updated testing
[x] Required CI checks are passing
[x] Visual proof for any user facing features like CLI or documentation updates
[x] Linked issues closed with keywords

codecov[bot] commented 1 year ago

Codecov Report

Merging #172 (5b53987) into master (1884bfb) will decrease coverage by 0.43%. The diff coverage is 80.00%.

@@            Coverage Diff             @@
##           master     #172      +/-   ##
==========================================
- Coverage   96.19%   95.76%   -0.43%     
==========================================
  Files           5        5              
  Lines         525      519       -6     
==========================================
- Hits          505      497       -8     
- Misses         12       13       +1     
- Partials        8        9       +1

Impacted Files	Coverage Δ
nmt.go	`97.94% <66.66%> (-1.08%)`	:arrow_down:
hasher.go	`97.54% <100.00%> (+0.08%)`	:arrow_up:

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.

staheri14 commented 1 year ago

cc: @evan-forbes Please find the benchmark comparison below. It's worth noting that the change introduced by this PR doesn't affect the ComputeRoot() benchmark test result. This is because the time measurement captures the total time taken to push N items and then compute the root. Before this change, the items were hashed inside the Root() method, whereas now they are hashed within the Push() method. As a result, the total number of hashes remains unchanged, and therefore the performance for this particular benchmark test does not improve.

goos: darwin
goarch: arm64
pkg: github.com/celestiaorg/nmt
                          │   master.txt   │              hash-and-push.txt               │
                          │   sec/op    │   sec/op     vs base               │
ComputeRoot/64-leaves-10    36.28µ ± 1%   38.10µ ± 0%  +5.00% (p=0.000 n=10)
ComputeRoot/128-leaves-10   72.23µ ± 0%   75.29µ ± 0%  +4.24% (p=0.000 n=10)
ComputeRoot/256-leaves-10   146.4µ ± 1%   152.7µ ± 1%  +4.30% (p=0.000 n=10)
geomean                     72.66µ        75.94µ       +4.51%

staheri14 commented 1 year ago

@rootulp Can you please review the recent changes 🙏🏼

celestiaorg / nmt