Comments (6)
A naive benchmark shows no significant difference, kilic even being faster with 256:
kilic:
goos: linux
goarch: amd64
pkg: github.com/gballet/go-verkle
BenchmarkCommitLeaves/insert/leaves/1000/width/10-8 1 1474368639 ns/op 292095272 B/op 3192268 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/1000/width/10-8 7 155914651 ns/op 22354277 B/op 65587 allocs/op
BenchmarkCommitLeaves/insert/leaves/10000/width/10-8 1 1376285817 ns/op 146847120 B/op 636855 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/10000/width/10-8 1 1661157609 ns/op 156908680 B/op 709441 allocs/op
BenchmarkCommitLeaves/insert/leaves/1000/width/8-8 7 152014956 ns/op 12296058 B/op 65042 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/1000/width/8-8 6 179306638 ns/op 14418436 B/op 79603 allocs/op
BenchmarkCommitLeaves/insert/leaves/10000/width/8-8 1 1419358018 ns/op 111304536 B/op 667735 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/10000/width/8-8 1 1755614599 ns/op 120034984 B/op 731625 allocs/op
BenchmarkCommitFullNode/width/10-8 34 33119308 ns/op 799179 B/op 10952 allocs/op
BenchmarkCommitFullNode/width/8-8 100 11298582 ns/op 225296 B/op 2840 allocs/op
PASS
ok github.com/gballet/go-verkle 15.269s
herumi:
goos: linux
goarch: amd64
pkg: github.com/gballet/go-verkle
BenchmarkCommitLeaves/insert/leaves/1000/width/10-8 1 1259425911 ns/op 15187432 B/op 16579 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/1000/width/10-8 6 171992046 ns/op 14097186 B/op 15976 allocs/op
BenchmarkCommitLeaves/insert/leaves/10000/width/10-8 1 1432095986 ns/op 60271552 B/op 118016 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/10000/width/10-8 1 1500091174 ns/op 61187144 B/op 136318 allocs/op
BenchmarkCommitLeaves/insert/leaves/1000/width/8-8 8 139774493 ns/op 3760832 B/op 13300 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/1000/width/8-8 6 167537888 ns/op 3897029 B/op 16084 allocs/op
BenchmarkCommitLeaves/insert/leaves/10000/width/8-8 1 1317603382 ns/op 18962752 B/op 117465 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/10000/width/8-8 1 1418402187 ns/op 19791336 B/op 134347 allocs/op
BenchmarkCommitFullNode/width/10-8 19 59106862 ns/op 463930 B/op 8781 allocs/op
BenchmarkCommitFullNode/width/8-8 73 14779280 ns/op 116086 B/op 2188 allocs/op
PASS
ok github.com/gballet/go-verkle 13.406s
It looks like kilic is much faster than herumi when the nodes are really full, and seems to be even more pronounced when nodes are wider. So far comparisons only occured on a width of 256, I'll run benchmarks with width 1024.
from go-verkle.
One explanation could be that we set the "lincomb" threshold based on herumi's numbers, and kilic could work with an ever lower/higher threshold. @s1na do you remember which bignum library you used to find a threshold of 110?
from go-verkle.
As expected, when comparing the time taken to translate a mainnet trie into a verkle tree, it is noticeably faster but still 40% slower. ~10h(herumi) vs ~14h (kilic).
from go-verkle.
Running the benchmarks on an AWS instance x5.large
herumi:
goos: linux
goarch: amd64
pkg: github.com/gballet/go-verkle
cpu: Intel(R) Xeon(R) Platinum 8175M CPU @ 2.50GHz
BenchmarkProofCalculation-4 6 177339859 ns/op 1005608 B/op 21452 allocs/op
BenchmarkProofVerification-4 487 2486951 ns/op 20368 B/op 73 allocs/op
BenchmarkCommitLeaves/insert/leaves/1000/width/10-4 10 108025027 ns/op 13653744 B/op 11873 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/1000/width/10-4 8 127878044 ns/op 13799688 B/op 14880 allocs/op
BenchmarkCommitLeaves/insert/leaves/10000/width/10-4 2 981093258 ns/op 58890640 B/op 108000 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/10000/width/10-4 1 1075515054 ns/op 59779912 B/op 126228 allocs/op
BenchmarkCommitLeaves/insert/leaves/1000/width/8-4 12 99175598 ns/op 3594284 B/op 12271 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/1000/width/8-4 9 117806597 ns/op 3727641 B/op 15046 allocs/op
BenchmarkCommitLeaves/insert/leaves/10000/width/8-4 2 923288118 ns/op 17821912 B/op 107731 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/10000/width/8-4 1 1004784412 ns/op 18645288 B/op 124762 allocs/op
BenchmarkCommitFullNode/width/10-4 28 40760101 ns/op 324521 B/op 7757 allocs/op
BenchmarkCommitFullNode/width/8-4 100 10180493 ns/op 81221 B/op 1932 allocs/op
BenchmarkModifyLeaves-4 1 15078576557 ns/op 130852168 B/op 1251054 allocs/op
kilic:
goos: linux
goarch: amd64
pkg: github.com/gballet/go-verkle
cpu: Intel(R) Xeon(R) Platinum 8175M CPU @ 2.50GHz
BenchmarkProofCalculation-4 9 122313086 ns/op 2421853 B/op 34401 allocs/op
BenchmarkProofVerification-4 663 1834717 ns/op 65265 B/op 421 allocs/op
BenchmarkCommitLeaves/insert/leaves/1000/width/10-4 10 100830027 ns/op 19457588 B/op 47432 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/1000/width/10-4 8 129216877 ns/op 21877086 B/op 63958 allocs/op
BenchmarkCommitLeaves/insert/leaves/10000/width/10-4 1 1227360081 ns/op 145180104 B/op 626447 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/10000/width/10-4 1 1347071574 ns/op 155180896 B/op 698801 allocs/op
BenchmarkCommitLeaves/insert/leaves/1000/width/8-4 8 126863070 ns/op 12174806 B/op 64138 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/1000/width/8-4 7 153912399 ns/op 14287331 B/op 78662 allocs/op
BenchmarkCommitLeaves/insert/leaves/10000/width/8-4 1 1259118860 ns/op 110126448 B/op 658312 allocs/op
BenchmarkCommitLeaves/insertOrdered/leaves/10000/width/8-4 1 1370844519 ns/op 118980800 B/op 723114 allocs/op
BenchmarkCommitFullNode/width/10-4 45 26299748 ns/op 667911 B/op 9927 allocs/op
BenchmarkCommitFullNode/width/8-4 135 8771252 ns/op 192461 B/op 2584 allocs/op
BenchmarkModifyLeaves-4 1 8808043081 ns/op 455726400 B/op 3727681 allocs/op
Building the trie with kilic is noticeably slower, however calculating proofs / root commitments is noticeably faster 🤔
from go-verkle.
After changing multiExpThreshold
to 26, the conversion comes down to ~11 hours, which indicates that knowing when to call LinComb
has a significant impact on performance.
CPU profiling output of a conversion:
from go-verkle.
We are no longer using KZG or BLS, closing this tracker issue.
from go-verkle.
Related Issues (20)
- conversion: use Copy on Write with `InsertOrdered` HOT 2
- Invalid labels for values in ToDot
- double commitment deserialization for HashedNode in InsertStem HOT 1
- condrieu: method handler crashed HOT 1
- Proposal: don't use serialized point as node reference
- Avoid panics HOT 1
- go build HOT 6
- Don't commit storage tries HOT 2
- Try overlay conversion with a flat preimage file
- use snake case in proof serialization
- encode stem info as a list of bytes, not a hex number
- use slice instead of pointer to [32]byte array in SuffixDiff
- Use go-ipa for Multiproof point deserialization HOT 1
- kaustinen: keys that are read but not written end up in the post values
- Possible redundant code in proof reconstruction
- Resolve the GO-R1005 cases
- Fix the CI replay action
- No right padding for values
- Code chunks all have suffix 0x1 in dora HOT 1
- proposal: encode EoAs in extension node HOT 10
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from go-verkle.