Skip to content

Commit be8c3b4

Browse files
jb55jb55
committed
bloom: use Span instead of std::vector for insert and contains
We can avoid many unnecessary std::vector allocations by changing CBloomFilter to take Spans instead of std::vector's for the `insert` and `contains` operations. CBloomFilter currently converts types such as CDataStream and uint256 to std::vector on `insert` and `contains`. This is unnecessary because CDataStreams and uint256 are already std::vectors internally. We just need a way to point to the right data within those types. Span gives us this ability. Signed-off-by: William Casarin <[email protected]>
1 parent 328da33 commit be8c3b4

File tree

4 files changed

+20
-24
lines changed

4 files changed

+20
-24
lines changed

‎src/bloom.cpp‎

Lines changed: 13 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -37,13 +37,13 @@ CBloomFilter::CBloomFilter(const unsigned int nElements, const double nFPRate, c
3737
{
3838
}
3939

40-
inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, const std::vector<unsigned char>& vDataToHash) const
40+
inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, Span<const unsigned char> vDataToHash) const
4141
{
4242
// 0xFBA4C795 chosen as it guarantees a reasonable bit difference between nHashNum values.
4343
return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) % (vData.size() * 8);
4444
}
4545

46-
void CBloomFilter::insert(const std::vector<unsigned char>& vKey)
46+
void CBloomFilter::insert(Span<const unsigned char> vKey)
4747
{
4848
if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
4949
return;
@@ -59,17 +59,15 @@ void CBloomFilter::insert(const COutPoint& outpoint)
5959
{
6060
CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
6161
stream << outpoint;
62-
std::vector<unsigned char> data(stream.begin(), stream.end());
63-
insert(data);
62+
insert(MakeUCharSpan(stream));
6463
}
6564

6665
void CBloomFilter::insert(const uint256& hash)
6766
{
68-
std::vector<unsigned char> data(hash.begin(), hash.end());
69-
insert(data);
67+
insert(MakeUCharSpan(hash));
7068
}
7169

72-
bool CBloomFilter::contains(const std::vector<unsigned char>& vKey) const
70+
bool CBloomFilter::contains(Span<const unsigned char> vKey) const
7371
{
7472
if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
7573
return true;
@@ -87,14 +85,12 @@ bool CBloomFilter::contains(const COutPoint& outpoint) const
8785
{
8886
CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
8987
stream << outpoint;
90-
std::vector<unsigned char> data(stream.begin(), stream.end());
91-
return contains(data);
88+
return contains(MakeUCharSpan(stream));
9289
}
9390

9491
bool CBloomFilter::contains(const uint256& hash) const
9592
{
96-
std::vector<unsigned char> data(hash.begin(), hash.end());
97-
return contains(data);
93+
return contains(MakeUCharSpan(hash));
9894
}
9995

10096
bool CBloomFilter::IsWithinSizeConstraints() const
@@ -198,7 +194,8 @@ CRollingBloomFilter::CRollingBloomFilter(const unsigned int nElements, const dou
198194
}
199195

200196
/* Similar to CBloomFilter::Hash */
201-
static inline uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, const std::vector<unsigned char>& vDataToHash) {
197+
static inline uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, Span<const unsigned char> vDataToHash)
198+
{
202199
return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash);
203200
}
204201

@@ -210,7 +207,7 @@ static inline uint32_t FastMod(uint32_t x, size_t n) {
210207
return ((uint64_t)x * (uint64_t)n) >> 32;
211208
}
212209

213-
void CRollingBloomFilter::insert(const std::vector<unsigned char>& vKey)
210+
void CRollingBloomFilter::insert(Span<const unsigned char> vKey)
214211
{
215212
if (nEntriesThisGeneration == nEntriesPerGeneration) {
216213
nEntriesThisGeneration = 0;
@@ -243,11 +240,10 @@ void CRollingBloomFilter::insert(const std::vector<unsigned char>& vKey)
243240

244241
void CRollingBloomFilter::insert(const uint256& hash)
245242
{
246-
std::vector<unsigned char> vData(hash.begin(), hash.end());
247-
insert(vData);
243+
insert(MakeUCharSpan(hash));
248244
}
249245

250-
bool CRollingBloomFilter::contains(const std::vector<unsigned char>& vKey) const
246+
bool CRollingBloomFilter::contains(Span<const unsigned char> vKey) const
251247
{
252248
for (int n = 0; n < nHashFuncs; n++) {
253249
uint32_t h = RollingBloomHash(n, nTweak, vKey);
@@ -263,8 +259,7 @@ bool CRollingBloomFilter::contains(const std::vector<unsigned char>& vKey) const
263259

264260
bool CRollingBloomFilter::contains(const uint256& hash) const
265261
{
266-
std::vector<unsigned char> vData(hash.begin(), hash.end());
267-
return contains(vData);
262+
return contains(MakeUCharSpan(hash));
268263
}
269264

270265
void CRollingBloomFilter::reset()

‎src/bloom.h‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -49,7 +49,7 @@ class CBloomFilter
4949
unsigned int nTweak;
5050
unsigned char nFlags;
5151

52-
unsigned int Hash(unsigned int nHashNum, const std::vector<unsigned char>& vDataToHash) const;
52+
unsigned int Hash(unsigned int nHashNum, Span<const unsigned char> vDataToHash) const;
5353

5454
public:
5555
/**
@@ -66,11 +66,11 @@ class CBloomFilter
6666

6767
SERIALIZE_METHODS(CBloomFilter, obj) { READWRITE(obj.vData, obj.nHashFuncs, obj.nTweak, obj.nFlags); }
6868

69-
void insert(const std::vector<unsigned char>& vKey);
69+
void insert(Span<const unsigned char> vKey);
7070
void insert(const COutPoint& outpoint);
7171
void insert(const uint256& hash);
7272

73-
bool contains(const std::vector<unsigned char>& vKey) const;
73+
bool contains(Span<const unsigned char> vKey) const;
7474
bool contains(const COutPoint& outpoint) const;
7575
bool contains(const uint256& hash) const;
7676

@@ -112,9 +112,9 @@ class CRollingBloomFilter
112112
public:
113113
CRollingBloomFilter(const unsigned int nElements, const double nFPRate);
114114

115-
void insert(const std::vector<unsigned char>& vKey);
115+
void insert(Span<const unsigned char> vKey);
116116
void insert(const uint256& hash);
117-
bool contains(const std::vector<unsigned char>& vKey) const;
117+
bool contains(Span<const unsigned char> vKey) const;
118118
bool contains(const uint256& hash) const;
119119

120120
void reset();

‎src/hash.cpp‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
44

55
#include <hash.h>
6+
#include <span.h>
67
#include <crypto/common.h>
78
#include <crypto/hmac_sha512.h>
89

‎src/test/bloom_tests.cpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -83,7 +83,7 @@ BOOST_AUTO_TEST_CASE(bloom_create_insert_key)
8383
CBloomFilter filter(2, 0.001, 0, BLOOM_UPDATE_ALL);
8484
filter.insert(vchPubKey);
8585
uint160 hash = pubkey.GetID();
86-
filter.insert(std::vector<unsigned char>(hash.begin(), hash.end()));
86+
filter.insert(MakeUCharSpan(hash));
8787

8888
CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
8989
stream << filter;

0 commit comments

Comments
 (0)