aboutsummaryrefslogtreecommitdiff
path: root/src/bloom.cpp
AgeCommit message (Collapse)Author
2018-05-06replace modulus with FastModMartin Ankerl
Replaces the slow modulo operation with a much faster 32bit multiplication & shift. This works because the hash should be uniformly distributed between 0 and 2^32-1. This speeds up the benchmark by a factor of about 1.3: RollingBloom, 5, 1500000, 3.73733, 4.97569e-07, 4.99002e-07, 4.98372e-07 # before RollingBloom, 5, 1500000, 2.86842, 3.81630e-07, 3.83730e-07, 3.82473e-07 # FastMod Be aware that this changes the position of the bits that are toggled, so this should probably not be used for CBloomFilter which is serialized.
2018-01-03Increment MIT Licence copyright header year on files modified in 2017Akira Takizawa
2017-11-16scripted-diff: Replace #include "" with #include <> (ryanofsky)MeshCollider
-BEGIN VERIFY SCRIPT- for f in \ src/*.cpp \ src/*.h \ src/bench/*.cpp \ src/bench/*.h \ src/compat/*.cpp \ src/compat/*.h \ src/consensus/*.cpp \ src/consensus/*.h \ src/crypto/*.cpp \ src/crypto/*.h \ src/crypto/ctaes/*.h \ src/policy/*.cpp \ src/policy/*.h \ src/primitives/*.cpp \ src/primitives/*.h \ src/qt/*.cpp \ src/qt/*.h \ src/qt/test/*.cpp \ src/qt/test/*.h \ src/rpc/*.cpp \ src/rpc/*.h \ src/script/*.cpp \ src/script/*.h \ src/support/*.cpp \ src/support/*.h \ src/support/allocators/*.h \ src/test/*.cpp \ src/test/*.h \ src/wallet/*.cpp \ src/wallet/*.h \ src/wallet/test/*.cpp \ src/wallet/test/*.h \ src/zmq/*.cpp \ src/zmq/*.h do base=${f%/*}/ relbase=${base#src/} sed -i "s:#include \"\(.*\)\"\(.*\):if test -e \$base'\\1'; then echo \"#include <\"\$relbase\"\\1>\\2\"; else echo \"#include <\\1>\\2\"; fi:e" $f done -END VERIFY SCRIPT-
2017-06-22scripted-diff: Remove #include <boost/foreach.hpp>Jorge Timón
-BEGIN VERIFY SCRIPT- sed -i ':a;N;$!ba;s/#include <boost\/foreach.hpp>\n//' ./src/*.h ./src/*.cpp ./src/*/*.h ./src/*/*.cpp ./src/*/*/*.h ./src/*/*/*.cpp -END VERIFY SCRIPT-
2017-06-05scripted-diff: Fully remove BOOST_FOREACHJorge Timón
-BEGIN VERIFY SCRIPT- sed -i 's/BOOST_FOREACH *(\(.*\),/for (\1 :/' ./src/*.h ./src/*.cpp ./src/*/*.h ./src/*/*.cpp ./src/*/*/*.h ./src/*/*/*.cpp ; -END VERIFY SCRIPT-
2017-05-18Merge #9750: Bloomfilter: parameter variables made constantWladimir J. van der Laan
64aa36e param variables made const (ロハン ダル) Tree-SHA512: 7c19f9e7dd574c8ce8a9468555f27196735b583efe349c1309c90e1e5d2949daf6891574b4bea7122d6c6aca0c7ee4a782fe3d24918d889f7bf89227084a51cd
2017-03-07Fix msvc compiler error C4146 (minus operator applied to unsigned type)kobake
On msvc14, the compiler error C4146 (unary minus operator applied to unsigned type, result still unsigned) had been occured. Use '0 - x' styled formula instead of '-x' so as to fix the error.
2017-02-13param variables made constロハン ダル
2017-01-27Refactor: Remove using namespace <xxx> from src/*.cpp.Karl-Johan Alm
2016-12-31Increment MIT Licence copyright header year on files modified in 2016isle2983
Edited via: $ contrib/devtools/copyright_header.py update .
2016-11-01trivial: fix bloom filter init to isEmpty = trueRobert McLaughlin
Fixes newly initialized bloom filters being constructed with isEmpty(false), which still works but loses the possible speedup when checking for key membership in an empty filter.
2016-09-27Do not shadow variablesPavel Janík
2016-04-28More efficient bitsliced rolling Bloom filterPieter Wuille
This patch changes the implementation from one that stores 16 2-bit integers in one uint32_t's, to one that stores the first bit of 64 2-bit integers in one uint64_t and the second bit in another. This allows for 450x faster refreshing and 2.2x faster average speed.
2016-01-05Merge pull request #7205Wladimir J. van der Laan
fa71669 [devtools] Use git pretty-format for year parsing (MarcoFalke) fa24439 Bump copyright headers to 2015 (MarcoFalke) fa6ad85 [devtools] Rewrite fix-copyright-headers.py (MarcoFalke)
2015-12-13Bump copyright headers to 2015MarcoFalke
2015-11-28Switch to a more efficient rolling Bloom filterPieter Wuille
For each 'bit' in the filter we really maintain 2 bits, which store either: 0: not set 1-3: set in generation N After (nElements / 2) insertions, we switch to a new generation, and wipe entries which already had the new generation number, effectively switching from the last 1.5 * nElements set to the last 1.0 * nElements set. This is 25% more space efficient than the previous implementation, and can (at peak) store 1.5 times the requested amount of history (though only 1.0 times the requested history is guaranteed). The existing unit tests should be sufficient.
2015-07-27Only use randomly created nonces in CRollingBloomFilter.Pieter Wuille
2015-07-27Make CRollingBloomFilter set nTweak for youPeter Todd
While CBloomFilter is usually used with an explicitly set nTweak, CRollingBloomFilter is only used internally. Requiring every caller to set nTweak is error-prone and redundant; better to have the class handle that for you with a high-quality randomness source. Additionally when clearing the filter it makes sense to change nTweak as well to recover from a bad setting, e.g. due to insufficient randomness at initialization, so the clear() method is replaced by a reset() method that sets a new, random, nTweak value.
2015-07-27Reuse vector hashing code for uint256Pieter Wuille
2015-07-27Add uint256 support to CRollingBloomFilterPeter Todd
2015-04-30Rolling bloom filter classGavin Andresen
For when you need to keep track of the last N items you've seen, and can tolerate some false-positives. Rebased-by: Pieter Wuille <pieter.wuille@gmail.com>
2014-12-19Added "Core" to copyright headerssandakersmann
Github-Pull: #5494 Rebased-From: 15de949bb9277e442302bdd8dee299a8d6deee60
2014-12-03MOVEONLY: core/ -> primitives/Luke Dashjr
2014-11-21Convert remaining comments in /src to doxygen formatMichael Ford
- Update comments in checkpoints to be doxygen compatible - Update comments in checkqueue to be doxygen compatible - Update coins to be doxygen compatible - Fix comment typo in crypter.h - Update licenses/copyright dates Closes #5325 #5184 #5183 #5182
2014-10-31boost: moveonly: split CPubKey and friends to new filesCory Fields
2014-10-27MOVEONLY: Separate CTransaction and dependencies from corejtimon
2014-10-22boost: split stream classes out of serialize.hCory Fields
serialization now has no dependencies.
2014-09-08Separate script/standardjtimon
2014-09-08Rename script.h/.cpp to scriptutils.h/.cpp (plus remove duplicated includes)jtimon
2014-09-02Discover some missing includesjtimon
2014-07-21CBloomFilter::clear() methodTom Harding
2014-07-21Revert "CBloomFilter::clear() method"Wladimir J. van der Laan
This reverts commit 8fbf03995df9a2003be603be1a930bc3373d56e0.
2014-06-27CBloomFilter::clear() methodTom Harding
2014-06-22Code simplifications after CTransaction::GetHash() cachingPieter Wuille
2014-03-20Fix bloom filter not to use bit_maskperyaudo
2013-11-10Cleanup code using forward declarations.Brandon Dahler
Use misc methods of avoiding unnecesary header includes. Replace int typedefs with int##_t from stdint.h. Replace PRI64[xdu] with PRI[xdu]64 from inttypes.h. Normalize QT_VERSION ifs where possible. Resolve some indirect dependencies as direct ones. Remove extern declarations from .cpp files.
2013-08-20Performance optimization for bloom filters.Gregory Maxwell
This reduces a peer's ability to attack network resources by using a full bloom filter, but without reducing the usability of bloom filters. It sets a default match everything filter for peers and it generalizes a prior optimization to cover more cases.
2013-06-24main.h->core.h include dependency improvements.Jeff Garzik
2013-02-24Short-circuit bloom checking if we will always return true.Matt Corallo
This allows full nodes to use bloom filters as an optimization.
2013-01-16Add nFlags to CBloomFilter to make filter updating optional.Matt Corallo
2013-01-16Add a nTweak to bloom filters to tweak the seed.Matt Corallo
2013-01-16Automatically add any matching outputs to a filter during matching.Matt Corallo
2013-01-16Replace RelayMessage with RelayTransaction.Matt Corallo
2013-01-16Add a CBloomFilter class for use as a transaction filter.Matt Corallo