Skip to content

Commit 2ba4ddf

Browse files
jb55fanquake
jb55
authored and
fanquake
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 3c776fd commit 2ba4ddf

File tree

4 files changed

+16
-45
lines changed

4 files changed

+16
-45
lines changed

‎src/bloom.cpp‎

Lines changed: 9 additions & 34 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,10 @@ 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(stream);
6463
}
6564

66-
void CBloomFilter::insert(const uint256& hash)
67-
{
68-
std::vector<unsigned char> data(hash.begin(), hash.end());
69-
insert(data);
70-
}
71-
72-
bool CBloomFilter::contains(const std::vector<unsigned char>& vKey) const
65+
bool CBloomFilter::contains(Span<const unsigned char> vKey) const
7366
{
7467
if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
7568
return true;
@@ -87,14 +80,7 @@ bool CBloomFilter::contains(const COutPoint& outpoint) const
8780
{
8881
CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
8982
stream << outpoint;
90-
std::vector<unsigned char> data(stream.begin(), stream.end());
91-
return contains(data);
92-
}
93-
94-
bool CBloomFilter::contains(const uint256& hash) const
95-
{
96-
std::vector<unsigned char> data(hash.begin(), hash.end());
97-
return contains(data);
83+
return contains(MakeUCharSpan(stream));
9884
}
9985

10086
bool CBloomFilter::IsWithinSizeConstraints() const
@@ -198,7 +184,8 @@ CRollingBloomFilter::CRollingBloomFilter(const unsigned int nElements, const dou
198184
}
199185

200186
/* Similar to CBloomFilter::Hash */
201-
static inline uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, const std::vector<unsigned char>& vDataToHash) {
187+
static inline uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, Span<const unsigned char> vDataToHash)
188+
{
202189
return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash);
203190
}
204191

@@ -210,7 +197,7 @@ static inline uint32_t FastMod(uint32_t x, size_t n) {
210197
return ((uint64_t)x * (uint64_t)n) >> 32;
211198
}
212199

213-
void CRollingBloomFilter::insert(const std::vector<unsigned char>& vKey)
200+
void CRollingBloomFilter::insert(Span<const unsigned char> vKey)
214201
{
215202
if (nEntriesThisGeneration == nEntriesPerGeneration) {
216203
nEntriesThisGeneration = 0;
@@ -241,13 +228,7 @@ void CRollingBloomFilter::insert(const std::vector<unsigned char>& vKey)
241228
}
242229
}
243230

244-
void CRollingBloomFilter::insert(const uint256& hash)
245-
{
246-
std::vector<unsigned char> vData(hash.begin(), hash.end());
247-
insert(vData);
248-
}
249-
250-
bool CRollingBloomFilter::contains(const std::vector<unsigned char>& vKey) const
231+
bool CRollingBloomFilter::contains(Span<const unsigned char> vKey) const
251232
{
252233
for (int n = 0; n < nHashFuncs; n++) {
253234
uint32_t h = RollingBloomHash(n, nTweak, vKey);
@@ -261,12 +242,6 @@ bool CRollingBloomFilter::contains(const std::vector<unsigned char>& vKey) const
261242
return true;
262243
}
263244

264-
bool CRollingBloomFilter::contains(const uint256& hash) const
265-
{
266-
std::vector<unsigned char> vData(hash.begin(), hash.end());
267-
return contains(vData);
268-
}
269-
270245
void CRollingBloomFilter::reset()
271246
{
272247
nTweak = GetRand(std::numeric_limits<unsigned int>::max());

‎src/bloom.h‎

Lines changed: 5 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,6 @@
1111

1212
class COutPoint;
1313
class CTransaction;
14-
class uint256;
1514

1615
//! 20,000 items with fp rate < 0.1% or 10,000 items and <0.0001%
1716
static const unsigned int MAX_BLOOM_FILTER_SIZE = 36000; // bytes
@@ -49,7 +48,7 @@ class CBloomFilter
4948
unsigned int nTweak;
5049
unsigned char nFlags;
5150

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

5453
public:
5554
/**
@@ -66,13 +65,11 @@ class CBloomFilter
6665

6766
SERIALIZE_METHODS(CBloomFilter, obj) { READWRITE(obj.vData, obj.nHashFuncs, obj.nTweak, obj.nFlags); }
6867

69-
void insert(const std::vector<unsigned char>& vKey);
68+
void insert(Span<const unsigned char> vKey);
7069
void insert(const COutPoint& outpoint);
71-
void insert(const uint256& hash);
7270

73-
bool contains(const std::vector<unsigned char>& vKey) const;
71+
bool contains(Span<const unsigned char> vKey) const;
7472
bool contains(const COutPoint& outpoint) const;
75-
bool contains(const uint256& hash) const;
7673

7774
//! True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash functions is <= MAX_HASH_FUNCS
7875
//! (catch a filter which was just deserialized which was too big)
@@ -112,10 +109,8 @@ class CRollingBloomFilter
112109
public:
113110
CRollingBloomFilter(const unsigned int nElements, const double nFPRate);
114111

115-
void insert(const std::vector<unsigned char>& vKey);
116-
void insert(const uint256& hash);
117-
bool contains(const std::vector<unsigned char>& vKey) const;
118-
bool contains(const uint256& hash) const;
112+
void insert(Span<const unsigned char> vKey);
113+
bool contains(Span<const unsigned char> vKey) const;
119114

120115
void reset();
121116

‎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(hash);
8787

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

0 commit comments

Comments
 (0)