search

axieinfinity / ronin

A DPoS blockchain.
GNU Lesser General Public License v3.0
67 stars 30 forks source link

trie, trie_prefetcher: don't copy when we are the exclusive owner of the trie #592

Open minh-bq opened 3 weeks ago

minh-bq commented 3 weeks ago

Currently, to make the trie copy perform well, we only copy the trie's node on write. However, there is no tracking on whether the trie is copied or not, so we always perform copy-on-write even though we are the only owner of the trie. This commit adds a shared bool to trie, this is set when trie copy is performed. When the trie is not shared, it is safe to do all the modification in-place without the need of creating a new copy.

> go test -test.v -test.run=^$ -test.bench=BenchmarkUpdate

           │    old.txt    │               new.txt                │
           │    sec/op     │    sec/op     vs base                │
UpdateBE-8   1247.0n ± 36%   378.4n ± 34%  -69.66% (p=0.000 n=10)
UpdateLE-8   1675.5n ±  1%   430.8n ± 31%  -74.29% (p=0.000 n=10)
geomean       1.445µ         403.7n        -72.07%

           │   old.txt    │              new.txt               │
           │     B/op     │    B/op     vs base                │
UpdateBE-8    1796.0 ± 0%   226.0 ± 0%  -87.42% (p=0.000 n=10)
UpdateLE-8    1848.0 ± 0%   228.5 ± 1%  -87.64% (p=0.000 n=10)
geomean      1.779Ki        227.2       -87.53%

           │  old.txt   │              new.txt               │
           │ allocs/op  │ allocs/op   vs base                │
UpdateBE-8   9.000 ± 0%   4.000 ± 0%  -55.56% (p=0.000 n=10)
UpdateLE-8   9.000 ± 0%   4.000 ± 0%  -55.56% (p=0.000 n=10)
geomean      9.000        4.000       -55.56%

Trie's modification is more optimized when it's marked as unshared. When the prefetched trie is requested, the prefetcher is stopped and the caller can become the exclusive owner of the trie in most case. When the prefetcher is not copied (active prefetcher), when possible, the returned trie is marked as unshared. However, we need to be careful as there might be the case that 2 same storage trie are prefetched. In that case, don't mark the trie as unshared when returning to caller.