diff options
author | William Casarin <jb55@jb55.com> | 2020-05-01 20:03:43 -0700 |
---|---|---|
committer | fanquake <fanquake@gmail.com> | 2021-09-29 09:40:10 +0800 |
commit | 2ba4ddf31d27bebc144b3729479967b40bbe0b6a (patch) | |
tree | 6be2168585922040490ea0b56f982de1bf40cf6b /src | |
parent | 3c776fdcec176ffaa2056633fa2b4e737cda29ce (diff) | |
download | bitcoin-2ba4ddf31d27bebc144b3729479967b40bbe0b6a.tar.xz |
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 <jb55@jb55.com>
Diffstat (limited to 'src')
-rw-r--r-- | src/bloom.cpp | 43 | ||||
-rw-r--r-- | src/bloom.h | 15 | ||||
-rw-r--r-- | src/hash.cpp | 1 | ||||
-rw-r--r-- | src/test/bloom_tests.cpp | 2 |
4 files changed, 16 insertions, 45 deletions
diff --git a/src/bloom.cpp b/src/bloom.cpp index d0128a26d7..78ef1897c9 100644 --- a/src/bloom.cpp +++ b/src/bloom.cpp @@ -37,13 +37,13 @@ CBloomFilter::CBloomFilter(const unsigned int nElements, const double nFPRate, c { } -inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, const std::vector<unsigned char>& vDataToHash) const +inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, Span<const unsigned char> vDataToHash) const { // 0xFBA4C795 chosen as it guarantees a reasonable bit difference between nHashNum values. return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) % (vData.size() * 8); } -void CBloomFilter::insert(const std::vector<unsigned char>& vKey) +void CBloomFilter::insert(Span<const unsigned char> vKey) { if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700) return; @@ -59,17 +59,10 @@ void CBloomFilter::insert(const COutPoint& outpoint) { CDataStream stream(SER_NETWORK, PROTOCOL_VERSION); stream << outpoint; - std::vector<unsigned char> data(stream.begin(), stream.end()); - insert(data); + insert(stream); } -void CBloomFilter::insert(const uint256& hash) -{ - std::vector<unsigned char> data(hash.begin(), hash.end()); - insert(data); -} - -bool CBloomFilter::contains(const std::vector<unsigned char>& vKey) const +bool CBloomFilter::contains(Span<const unsigned char> vKey) const { if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700) return true; @@ -87,14 +80,7 @@ bool CBloomFilter::contains(const COutPoint& outpoint) const { CDataStream stream(SER_NETWORK, PROTOCOL_VERSION); stream << outpoint; - std::vector<unsigned char> data(stream.begin(), stream.end()); - return contains(data); -} - -bool CBloomFilter::contains(const uint256& hash) const -{ - std::vector<unsigned char> data(hash.begin(), hash.end()); - return contains(data); + return contains(MakeUCharSpan(stream)); } bool CBloomFilter::IsWithinSizeConstraints() const @@ -198,7 +184,8 @@ CRollingBloomFilter::CRollingBloomFilter(const unsigned int nElements, const dou } /* Similar to CBloomFilter::Hash */ -static inline uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, const std::vector<unsigned char>& vDataToHash) { +static inline uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, Span<const unsigned char> vDataToHash) +{ return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash); } @@ -210,7 +197,7 @@ static inline uint32_t FastMod(uint32_t x, size_t n) { return ((uint64_t)x * (uint64_t)n) >> 32; } -void CRollingBloomFilter::insert(const std::vector<unsigned char>& vKey) +void CRollingBloomFilter::insert(Span<const unsigned char> vKey) { if (nEntriesThisGeneration == nEntriesPerGeneration) { nEntriesThisGeneration = 0; @@ -241,13 +228,7 @@ void CRollingBloomFilter::insert(const std::vector<unsigned char>& vKey) } } -void CRollingBloomFilter::insert(const uint256& hash) -{ - std::vector<unsigned char> vData(hash.begin(), hash.end()); - insert(vData); -} - -bool CRollingBloomFilter::contains(const std::vector<unsigned char>& vKey) const +bool CRollingBloomFilter::contains(Span<const unsigned char> vKey) const { for (int n = 0; n < nHashFuncs; n++) { uint32_t h = RollingBloomHash(n, nTweak, vKey); @@ -261,12 +242,6 @@ bool CRollingBloomFilter::contains(const std::vector<unsigned char>& vKey) const return true; } -bool CRollingBloomFilter::contains(const uint256& hash) const -{ - std::vector<unsigned char> vData(hash.begin(), hash.end()); - return contains(vData); -} - void CRollingBloomFilter::reset() { nTweak = GetRand(std::numeric_limits<unsigned int>::max()); diff --git a/src/bloom.h b/src/bloom.h index fdaa8abfb2..391e2cc888 100644 --- a/src/bloom.h +++ b/src/bloom.h @@ -11,7 +11,6 @@ class COutPoint; class CTransaction; -class uint256; //! 20,000 items with fp rate < 0.1% or 10,000 items and <0.0001% static const unsigned int MAX_BLOOM_FILTER_SIZE = 36000; // bytes @@ -49,7 +48,7 @@ private: unsigned int nTweak; unsigned char nFlags; - unsigned int Hash(unsigned int nHashNum, const std::vector<unsigned char>& vDataToHash) const; + unsigned int Hash(unsigned int nHashNum, Span<const unsigned char> vDataToHash) const; public: /** @@ -66,13 +65,11 @@ public: SERIALIZE_METHODS(CBloomFilter, obj) { READWRITE(obj.vData, obj.nHashFuncs, obj.nTweak, obj.nFlags); } - void insert(const std::vector<unsigned char>& vKey); + void insert(Span<const unsigned char> vKey); void insert(const COutPoint& outpoint); - void insert(const uint256& hash); - bool contains(const std::vector<unsigned char>& vKey) const; + bool contains(Span<const unsigned char> vKey) const; bool contains(const COutPoint& outpoint) const; - bool contains(const uint256& hash) const; //! True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash functions is <= MAX_HASH_FUNCS //! (catch a filter which was just deserialized which was too big) @@ -112,10 +109,8 @@ class CRollingBloomFilter public: CRollingBloomFilter(const unsigned int nElements, const double nFPRate); - void insert(const std::vector<unsigned char>& vKey); - void insert(const uint256& hash); - bool contains(const std::vector<unsigned char>& vKey) const; - bool contains(const uint256& hash) const; + void insert(Span<const unsigned char> vKey); + bool contains(Span<const unsigned char> vKey) const; void reset(); diff --git a/src/hash.cpp b/src/hash.cpp index 3465caa3a9..92c923fbd2 100644 --- a/src/hash.cpp +++ b/src/hash.cpp @@ -3,6 +3,7 @@ // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include <hash.h> +#include <span.h> #include <crypto/common.h> #include <crypto/hmac_sha512.h> diff --git a/src/test/bloom_tests.cpp b/src/test/bloom_tests.cpp index 5a98558240..23ef2062ef 100644 --- a/src/test/bloom_tests.cpp +++ b/src/test/bloom_tests.cpp @@ -83,7 +83,7 @@ BOOST_AUTO_TEST_CASE(bloom_create_insert_key) CBloomFilter filter(2, 0.001, 0, BLOOM_UPDATE_ALL); filter.insert(vchPubKey); uint160 hash = pubkey.GetID(); - filter.insert(std::vector<unsigned char>(hash.begin(), hash.end())); + filter.insert(hash); CDataStream stream(SER_NETWORK, PROTOCOL_VERSION); stream << filter; |