crate-crypto / go-eth-kzg

Apache License 2.0
29 stars 22 forks source link

chore: Use monomial form when computing the quotient #98

Open kevaundray opened 1 month ago

kevaundray commented 1 month ago

Need to take benchmarks to compute what the difference is before moving forward

kevaundray commented 1 month ago

Currently on master I get:

Running tool: /usr/local/bin/go test -benchmem -run=^$ -bench ^Benchmark$ github.com/crate-crypto/go-eth-kzg

goos: darwin
goarch: arm64
pkg: github.com/crate-crypto/go-eth-kzg
Benchmark/BlobToKZGCommitment-10                 129       9069520 ns/op      405012 B/op        153 allocs/op
Benchmark/ComputeKZGProof-10                     126       9790412 ns/op      930463 B/op        164 allocs/op
Benchmark/ComputeBlobKZGProof-10                 100      10086890 ns/op      930860 B/op        171 allocs/op
ok      github.com/crate-crypto/go-eth-kzg  33.101s

On this branch, I get:

Running tool: /usr/local/bin/go test -benchmem -run=^$ -bench ^Benchmark$ github.com/crate-crypto/go-eth-kzg

goos: darwin
goarch: arm64
pkg: github.com/crate-crypto/go-eth-kzg
Benchmark/BlobToKZGCommitment-10                 136       9300691 ns/op      405015 B/op        153 allocs/op
Benchmark/ComputeKZGProof-10                     100      10629476 ns/op     3681812 B/op      12439 allocs/op
Benchmark/ComputeBlobKZGProof-10                 100      11383314 ns/op     3682208 B/op      12446 allocs/op
PASS
ok      github.com/crate-crypto/go-eth-kzg  31.926s

So its about 10% slower though the allocations have grown

kevaundray commented 1 month ago

I created another branch that merges the iterative IFFT code into these changes, see #99 -- we get:

goos: darwin
goarch: arm64
pkg: github.com/crate-crypto/go-eth-kzg
Benchmark/BlobToKZGCommitment-10                 140       9368765 ns/op      405019 B/op        153 allocs/op
Benchmark/ComputeKZGProof-10                     120      11115686 ns/op      667633 B/op        179 allocs/op
Benchmark/ComputeBlobKZGProof-10                 100      10302858 ns/op      668033 B/op        186 allocs/op
kevaundray commented 1 month ago

So that branch has essentially the same performance, with the newer branch having a slighter better memory profile, but nothing significant

kevaundray commented 1 month ago

Note to self: local branch is named kw/simple-kzg-code