Including:
This reduces the memory consumption of a maximal setAddrKnown by +- half.
Rebased on top of @gavinandresen’s #6066 (so that I don’t need the address hasher here).
Removed the boost::unordered_set usage for now, as it is incompatible with older boost versions (which don’t have unordered_set::reserve).
40- void clear()
41+ void clear(size_type nMaxSizeIn = 1)
42 {
43 set.clear();
44- queue.clear();
45+ std::vector<iterator>(nMaxSizeIn, set.end()).swap(order);
AFAIK too. Though this is only important if we expect the size to change (become smaller) dynamically.
I’m not sure I like having clear() double as set-maximum-size method. I’d prefer the maximum size to be passed to the constructor and be static over the lifetime of the object. If that’s not possible, let’s add a special resize() call for resizing (that happens to clear the structure too).
55- queue.pop_front();
56+ if (set.size() == nMaxSize + 1) {
57+ set.erase(order[first_used]);
58+ order[first_used] = set.end();
59+ first_used++;
60+ if (first_used == nMaxSize) { first_used = 0; }
Code review ACK– note I changed the CRollingBloomFilter implementation commit in #6066 .
Measured heap usage on OSX for a 1,000-entry mruset : 72,192 bytes. (before this change: 100,992 bytes).
I’m running a node with these changes now.
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>
39@@ -40,6 +40,17 @@ nFlags(nFlagsIn)
40 {
41 }
42
43+// Private constructor used by CRollingBloomFilter
44+CBloomFilter::CBloomFilter(unsigned int nElements, double nFPRate, unsigned int nTweakIn) :
45+vData((unsigned int)(-1 / LN2SQUARED * nElements * log(nFPRate)) / 8),
207@@ -197,3 +208,38 @@ void CBloomFilter::UpdateEmptyFull()
208 isFull = full;
209 isEmpty = empty;
210 }
211+
212+CRollingBloomFilter::CRollingBloomFilter(unsigned int nElements, double fpRate, unsigned int nTweak) :
213+ b1(nElements*2, fpRate, nTweak), b2(nElements*2, fpRate, nTweak)
214+{
215+ // Implemented using two bloom filters of nElements each.
two filters of nElements*2 each, if I understand the above initialization correctly?
226+ b1.clear();
227+ else if (nInsertions%nBloomSize == nBloomSize/2)
228+ b2.clear();
229+ b1.insert(vKey);
230+ b2.insert(vKey);
231+ ++nInsertions;
% operations, and also avoids trouble with integer overflows when UIINT_MAX is not divisible by nBloomSize.
4798@@ -4799,8 +4799,9 @@ bool SendMessages(CNode* pto, bool fSendTrickle)
4799 BOOST_FOREACH(const CAddress& addr, pto->vAddrToSend)
4800 {
4801 // returns true if wasn't already contained in the set
contains is self-documenting in contrast to insert’s second return value
109 }
110 }
111 }
112
113-// 16-bit permutation function
114-int static permute(int n)
Made several changes:
I think there is a significant improvement possible to the size of the rolling bloom filter, by using a different tweak for multiple filters, and checking several filters for a ‘contains’. I’ll check the math and write a separate PR for that if found useful.
Use a probabilistic bloom filter to keep track of which addresses
we think we have given our peers, instead of a list.
This uses much less memory, at the cost of sometimes failing to
relay an address to a peer-- worst case if the bloom filter happens
to be as full as it gets, 1-in-1,000.
Measured memory usage of a full mruset setAddrKnown: 650Kbytes
Constant memory usage of CRollingBloomFilter addrKnown: 37Kbytes.
This will also help heap fragmentation, because the 37K of storage
is allocated when a CNode is created (when a connection to a peer
is established) and then there is no per-item-remembered memory
allocation.
I plan on testing by restarting a full node with an empty peers.dat,
running a while with -debug=addrman and -debug=net, and making sure
that the 'addr' message traffic out is reasonable.
(suggestions for better tests welcome)
I think there is a significant improvement possible to the size of the rolling bloom filter, by using a different tweak for both, and checking both filters for a ‘contains’. I’ll check the math and write a separate PR for that if found useful. @sipa sounds great to me, although let’s do that in a later pull, this is already a great improvement compared to the current state, so let’s get this reviewed and merged.