From 42133b63c3acb66ac263a13ce14e4d64a44d6698 Mon Sep 17 00:00:00 2001 From: Dev Ojha Date: Thu, 2 May 2024 06:19:12 -0700 Subject: [PATCH 1/3] perf(internal/bits): Speedup extended commit.BitArray() (#2959) Speedup ExtendedCommit.BitArray() by making a direct constructor that does not go through mutexes. I expect this to be a 10x performance improvement. (It also removes the duffcopies and reduces setIndex proportion of time here) This removes this time (which is mostly coming from mutex calls): ![image](https://github.com/cometbft/cometbft/assets/6440154/da11d57d-6bea-40ea-a0fa-9209ea3e22f8) Later on we should instead make an API that lets us randomly sample from a bit array with no bit array copying needed. (But that makes the interface messier) --- #### PR checklist - [x] Tests written/updated - [x] Changelog entry added in `.changelog` (we use [unclog](https://github.com/informalsystems/unclog) to manage our changelog) - [x] Updated relevant documentation (`docs/` or `spec/`) and code comments - [x] Title follows the [Conventional Commits](https://www.conventionalcommits.org/en/v1.0.0/) spec (cherry picked from commit edb297be1e584df5af272864c569e0106c4b49e9) # Conflicts: # libs/bits/bit_array.go # libs/bits/bit_array_test.go --- ...eedup-initialized-bitarray-construction.md | 2 ++ libs/bits/bit_array.go | 24 +++++++++++++++++++ libs/bits/bit_array_test.go | 18 +++++++++++++- types/block.go | 6 ++--- 4 files changed, 46 insertions(+), 4 deletions(-) create mode 100644 .changelog/unreleased/improvements/2959-speedup-initialized-bitarray-construction.md diff --git a/.changelog/unreleased/improvements/2959-speedup-initialized-bitarray-construction.md b/.changelog/unreleased/improvements/2959-speedup-initialized-bitarray-construction.md new file mode 100644 index 00000000000..7c1b2181d08 --- /dev/null +++ b/.changelog/unreleased/improvements/2959-speedup-initialized-bitarray-construction.md @@ -0,0 +1,2 @@ +- `[internal/bits]` 10x speedup creating initialized bitArrays, which speedsup extendedCommit.BitArray(). This is used in consensus vote gossip. + ([\#2959](https://github.com/cometbft/cometbft/pull/2841)). diff --git a/libs/bits/bit_array.go b/libs/bits/bit_array.go index 18daf50119c..93b48594473 100644 --- a/libs/bits/bit_array.go +++ b/libs/bits/bit_array.go @@ -32,7 +32,31 @@ func NewBitArray(bits int) *BitArray { } } +<<<<<<< HEAD:libs/bits/bit_array.go // Size returns the number of bits in the bitarray +======= +// NewBitArrayFromFn returns a new bit array. +// It returns nil if the number of bits is zero. +// It initializes the `i`th bit to the value of `fn(i)`. +func NewBitArrayFromFn(bits int, fn func(int) bool) *BitArray { + if bits <= 0 { + return nil + } + bA := &BitArray{ + Bits: bits, + Elems: make([]uint64, (bits+63)/64), + } + for i := 0; i < bits; i++ { + v := fn(i) + if v { + bA.Elems[i/64] |= (uint64(1) << uint(i%64)) + } + } + return bA +} + +// Size returns the number of bits in the bitarray. +>>>>>>> edb297be1 (perf(internal/bits): Speedup extended commit.BitArray() (#2959)):internal/bits/bit_array.go func (bA *BitArray) Size() int { if bA == nil { return 0 diff --git a/libs/bits/bit_array_test.go b/libs/bits/bit_array_test.go index 1c74d29c306..328a06827c8 100644 --- a/libs/bits/bit_array_test.go +++ b/libs/bits/bit_array_test.go @@ -21,6 +21,7 @@ var ( func randBitArray(bits int) (*BitArray, []byte) { src := cmtrand.Bytes((bits + 7) / 8) +<<<<<<< HEAD:libs/bits/bit_array_test.go bA := NewBitArray(bits) for i := 0; i < len(src); i++ { for j := 0; j < 8; j++ { @@ -32,6 +33,12 @@ func randBitArray(bits int) (*BitArray, []byte) { } } return bA, src +======= + srcIndexToBit := func(i int) bool { + return src[i/8]&(1< 0 + } + return NewBitArrayFromFn(bits, srcIndexToBit) +>>>>>>> edb297be1 (perf(internal/bits): Speedup extended commit.BitArray() (#2959)):internal/bits/bit_array_test.go } func TestAnd(t *testing.T) { @@ -59,8 +66,13 @@ func TestAnd(t *testing.T) { } func TestOr(t *testing.T) { +<<<<<<< HEAD:libs/bits/bit_array_test.go bA1, _ := randBitArray(51) bA2, _ := randBitArray(31) +======= + bA1 := randBitArray(57) + bA2 := randBitArray(31) +>>>>>>> edb297be1 (perf(internal/bits): Speedup extended commit.BitArray() (#2959)):internal/bits/bit_array_test.go bA3 := bA1.Or(bA2) bNil := (*BitArray)(nil) @@ -68,7 +80,7 @@ func TestOr(t *testing.T) { require.Equal(t, bA1.Or(nil), bA1) require.Equal(t, bNil.Or(nil), (*BitArray)(nil)) - if bA3.Bits != 51 { + if bA3.Bits != 57 { t.Error("Expected max bits") } if len(bA3.Elems) != len(bA1.Elems) { @@ -80,6 +92,10 @@ func TestOr(t *testing.T) { t.Error("Wrong bit from bA3", i, bA1.GetIndex(i), bA2.GetIndex(i), bA3.GetIndex(i)) } } + if bA3.getNumTrueIndices() == 0 { + t.Error("Expected at least one true bit. " + + "This has a false positive rate that is less than 1 in 2^80 (cryptographically improbable).") + } } func TestSub(t *testing.T) { diff --git a/types/block.go b/types/block.go index 4a504c64899..8263349ec02 100644 --- a/types/block.go +++ b/types/block.go @@ -1179,12 +1179,12 @@ func (ec *ExtendedCommit) Size() int { // Implements VoteSetReader. func (ec *ExtendedCommit) BitArray() *bits.BitArray { if ec.bitArray == nil { - ec.bitArray = bits.NewBitArray(len(ec.ExtendedSignatures)) - for i, extCommitSig := range ec.ExtendedSignatures { + initialBitFn := func(i int) bool { // TODO: need to check the BlockID otherwise we could be counting conflicts, // not just the one with +2/3 ! - ec.bitArray.SetIndex(i, extCommitSig.BlockIDFlag != BlockIDFlagAbsent) + return ec.ExtendedSignatures[i].BlockIDFlag != BlockIDFlagAbsent } + ec.bitArray = bits.NewBitArrayFromFn(len(ec.ExtendedSignatures), initialBitFn) } return ec.bitArray } From 8d9e7ae3775d3fd26f76eb58163a3232e6689a1e Mon Sep 17 00:00:00 2001 From: Anton Kaliaev Date: Thu, 2 May 2024 17:55:44 +0400 Subject: [PATCH 2/3] fix conflicts --- libs/bits/bit_array.go | 4 ---- libs/bits/bit_array_test.go | 27 ++++----------------------- 2 files changed, 4 insertions(+), 27 deletions(-) diff --git a/libs/bits/bit_array.go b/libs/bits/bit_array.go index 93b48594473..f9744f9c7b4 100644 --- a/libs/bits/bit_array.go +++ b/libs/bits/bit_array.go @@ -32,9 +32,6 @@ func NewBitArray(bits int) *BitArray { } } -<<<<<<< HEAD:libs/bits/bit_array.go -// Size returns the number of bits in the bitarray -======= // NewBitArrayFromFn returns a new bit array. // It returns nil if the number of bits is zero. // It initializes the `i`th bit to the value of `fn(i)`. @@ -56,7 +53,6 @@ func NewBitArrayFromFn(bits int, fn func(int) bool) *BitArray { } // Size returns the number of bits in the bitarray. ->>>>>>> edb297be1 (perf(internal/bits): Speedup extended commit.BitArray() (#2959)):internal/bits/bit_array.go func (bA *BitArray) Size() int { if bA == nil { return 0 diff --git a/libs/bits/bit_array_test.go b/libs/bits/bit_array_test.go index 328a06827c8..628247c9450 100644 --- a/libs/bits/bit_array_test.go +++ b/libs/bits/bit_array_test.go @@ -19,31 +19,17 @@ var ( full64bits = full16bits + full16bits + full16bits + full16bits ) -func randBitArray(bits int) (*BitArray, []byte) { +func randBitArray(bits int) *BitArray { src := cmtrand.Bytes((bits + 7) / 8) -<<<<<<< HEAD:libs/bits/bit_array_test.go - bA := NewBitArray(bits) - for i := 0; i < len(src); i++ { - for j := 0; j < 8; j++ { - if i*8+j >= bits { - return bA, src - } - setBit := src[i]&(1< 0 - bA.SetIndex(i*8+j, setBit) - } - } - return bA, src -======= srcIndexToBit := func(i int) bool { return src[i/8]&(1< 0 } return NewBitArrayFromFn(bits, srcIndexToBit) ->>>>>>> edb297be1 (perf(internal/bits): Speedup extended commit.BitArray() (#2959)):internal/bits/bit_array_test.go } func TestAnd(t *testing.T) { - bA1, _ := randBitArray(51) - bA2, _ := randBitArray(31) + bA1 := randBitArray(57) + bA2 := randBitArray(31) bA3 := bA1.And(bA2) var bNil *BitArray @@ -66,13 +52,8 @@ func TestAnd(t *testing.T) { } func TestOr(t *testing.T) { -<<<<<<< HEAD:libs/bits/bit_array_test.go - bA1, _ := randBitArray(51) - bA2, _ := randBitArray(31) -======= bA1 := randBitArray(57) bA2 := randBitArray(31) ->>>>>>> edb297be1 (perf(internal/bits): Speedup extended commit.BitArray() (#2959)):internal/bits/bit_array_test.go bA3 := bA1.Or(bA2) bNil := (*BitArray)(nil) @@ -292,7 +273,7 @@ func TestEmptyFull(t *testing.T) { func TestUpdateNeverPanics(_ *testing.T) { newRandBitArray := func(n int) *BitArray { - ba, _ := randBitArray(n) + ba := randBitArray(n) return ba } pairs := []struct { From 2270a7442c2f83e8b7d7e9c124bff63509f73491 Mon Sep 17 00:00:00 2001 From: Anton Kaliaev Date: Thu, 2 May 2024 17:59:24 +0400 Subject: [PATCH 3/3] revert back TestAnd --- libs/bits/bit_array_test.go | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/libs/bits/bit_array_test.go b/libs/bits/bit_array_test.go index 628247c9450..0f7351f346e 100644 --- a/libs/bits/bit_array_test.go +++ b/libs/bits/bit_array_test.go @@ -28,7 +28,7 @@ func randBitArray(bits int) *BitArray { } func TestAnd(t *testing.T) { - bA1 := randBitArray(57) + bA1 := randBitArray(51) bA2 := randBitArray(31) bA3 := bA1.And(bA2)