perf(crypto/merkle): reduce allocations in HashFromByteSlices (celest…

…iaorg#1365) ## Description ~~Reduce allocations in `HashAlternatives` by adding `case 2` which is very common and doesn't require 2 additional recursive calls. As a result 20% less allocations and 10% less CPU time.~~ We can have better solution by using fact that `hash.Hash` implements `io.Writer`. Instead of allocation slice that we want to hash we can do this step by step. Results are even better (30% less CPU and 60% less allocations): ``` celestia-core % go-perftuner bstat a.txt b.txt args: [a.txt b.txt]name old time/op new time/op delta HashAlternatives/recursive-10 31.7µs ± 3% 21.8µs ± 0% -31.23% (p=0.002 n=6+6) HashAlternatives/iterative-10 32.1µs ± 3% 31.9µs ± 1% ~ (p=0.537 n=5+6) name old alloc/op new alloc/op delta HashAlternatives/recursive-10 25.7kB ± 0% 6.6kB ± 0% -74.45% (p=0.002 n=6+6) HashAlternatives/iterative-10 28.4kB ± 0% 28.4kB ± 0% ~ (all equal) name old allocs/op new allocs/op delta HashAlternatives/recursive-10 502 ± 0% 202 ± 0% -59.76% (p=0.002 n=6+6) HashAlternatives/iterative-10 503 ± 0% 503 ± 0% ~ (all equal) ``` Note: same solutions is used in `cometbft` (see: https://github.com/cometbft/cometbft/blob/main/crypto/merkle/hash.go#L26) <details> <summary>Old benchmark</summary> ``` celestia-core % go-perftuner bstat a.txt b.txt args: [a.txt b.txt]name old time/op new time/op delta HashAlternatives/recursive-10 31.6µs ± 3% 27.9µs ± 0% -11.66% (p=0.002 n=6+6) HashAlternatives/iterative-10 32.3µs ± 3% 31.9µs ± 2% ~ (p=0.240 n=6+6) name old alloc/op new alloc/op delta HashAlternatives/recursive-10 25.4kB ± 0% 22.2kB ± 0% -12.59% (p=0.002 n=6+6) HashAlternatives/iterative-10 28.1kB ± 0% 28.1kB ± 0% ~ (all equal) name old allocs/op new allocs/op delta HashAlternatives/recursive-10 497 ± 0% 397 ± 0% -20.12% (p=0.002 n=6+6) HashAlternatives/iterative-10 498 ± 0% 498 ± 0% ~ (all equal) ``` </details> Also, changing benchmark by 1 digit: instead of 100 nodes create 101 to cover all code branches (a bit better code coverage). --- #### PR checklist - [x] Tests written/updated - [ ] Changelog entry added in `.changelog` (we use [unclog](https://github.com/informalsystems/unclog) to manage our changelog) - [ ] Updated relevant documentation (`docs/` or `spec/`) and code comments
KYVENetwork · May 28, 2024 · ab3f8bd · ab3f8bd
1 parent 7317834
commit ab3f8bd
Show file tree

Hide file tree

Showing 4 changed files with 61 additions and 7 deletions.
diff --git a/crypto/merkle/hash.go b/crypto/merkle/hash.go
@@ -1,10 +1,11 @@
 package merkle
 
 import (
+	"hash"
+
 	"github.com/cometbft/cometbft/crypto/tmhash"
 )
 
-// TODO: make these have a large predefined capacity
 var (
 	leafPrefix  = []byte{0}
 	innerPrefix = []byte{1}
@@ -20,7 +21,24 @@ func leafHash(leaf []byte) []byte {
 	return tmhash.Sum(append(leafPrefix, leaf...))
 }
 
+// returns tmhash(0x00 || leaf)
+func leafHashOpt(h hash.Hash, leaf []byte) []byte {
+	h.Reset()
+	h.Write(leafPrefix)
+	h.Write(leaf)
+	return h.Sum(nil)
+}
+
 // returns tmhash(0x01 || left || right)
 func innerHash(left []byte, right []byte) []byte {
 	return tmhash.Sum(append(innerPrefix, append(left, right...)...))
 }
+
+// returns tmhash(0x01 || left || right)
+func innerHashOpt(h hash.Hash, left []byte, right []byte) []byte {
+	h.Reset()
+	h.Write(innerPrefix)
+	h.Write(left)
+	h.Write(right)
+	return h.Sum(nil)
+}
diff --git a/crypto/merkle/hash_test.go b/crypto/merkle/hash_test.go
@@ -0,0 +1,28 @@
+package merkle
+
+import (
+	"testing"
+
+	"github.com/cometbft/cometbft/crypto/tmhash"
+	cmtrand "github.com/cometbft/cometbft/libs/rand"
+	"github.com/stretchr/testify/require"
+)
+
+func TestHash(t *testing.T) {
+	leaf := cmtrand.Bytes(tmhash.Size)
+	left := cmtrand.Bytes(tmhash.Size)
+	right := cmtrand.Bytes(tmhash.Size)
+
+	require.Equal(t,
+		leafHash(leaf),
+		leafHashOpt(tmhash.New(), leaf),
+	)
+	require.Equal(t,
+		innerHash(left, right),
+		innerHashOpt(tmhash.New(), left, right),
+	)
+	require.NotEqual(t,
+		innerHash(right, left),
+		innerHashOpt(tmhash.New(), left, right),
+	)
+}
diff --git a/crypto/merkle/tree.go b/crypto/merkle/tree.go
@@ -1,26 +1,33 @@
 package merkle
 
 import (
+	"hash"
 	"math/bits"
+
+	"github.com/cometbft/cometbft/crypto/tmhash"
 )
 
 // HashFromByteSlices computes a Merkle tree where the leaves are the byte slice,
 // in the provided order. It follows RFC-6962.
 func HashFromByteSlices(items [][]byte) []byte {
+	return hashFromByteSlices(tmhash.New(), items)
+}
+
+func hashFromByteSlices(h hash.Hash, items [][]byte) []byte {
 	switch len(items) {
 	case 0:
 		return emptyHash()
 	case 1:
-		return leafHash(items[0])
+		return leafHashOpt(h, items[0])
 	default:
 		k := getSplitPoint(int64(len(items)))
-		left := HashFromByteSlices(items[:k])
-		right := HashFromByteSlices(items[k:])
-		return innerHash(left, right)
+		left := hashFromByteSlices(h, items[:k])
+		right := hashFromByteSlices(h, items[k:])
+		return innerHashOpt(h, left, right)
 	}
 }
 
-// HashFromByteSliceIterative is an iterative alternative to
+// HashFromByteSlicesIterative is an iterative alternative to
 // HashFromByteSlice motivated by potential performance improvements.
 // (#2611) had suggested that an iterative version of
 // HashFromByteSlice would be faster, presumably because
@@ -59,6 +66,7 @@ func HashFromByteSlices(items [][]byte) []byte {
 // Finally, considering that the recursive implementation is easier to
 // read, it might not be worthwhile to switch to a less intuitive
 // implementation for so little benefit.
+// Deprecated: use HashFromByteSlices instead.
 func HashFromByteSlicesIterative(input [][]byte) []byte {
 	items := make([][]byte, len(input))
 

diff --git a/crypto/merkle/tree_test.go b/crypto/merkle/tree_test.go
@@ -116,7 +116,7 @@ func TestHashAlternatives(t *testing.T) {
 }
 
 func BenchmarkHashAlternatives(b *testing.B) {
-	total := 100
+	total := 101
 
 	items := make([][]byte, total)
 	for i := 0; i < total; i++ {