This is a follow up PR to #21464 which improves the memory usage and runtime of the reorg update logic. The main changes are:
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
Reviewers, this pull request conflicts with the following ones:
CTxMemPool from ArgsManager by dongcarl)If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
see the pr description of #18191
There’s potential for a better – but more sophisticated – algorithm that can be used taking advantage of epochs, but I figured it is better to do something that is simple and works first and upgrade it later as the other epoch mempool work proceeds as it makes the patches for the epoch algorithm simpler to understand, so you can consider this as preparatory work. It could either go in now if it is not controversial, or we could wait until the other patch is ready to go.
oh oops.
uh yeah TBH I forgot I had that other PR open.
They should be mostly the same.
The main difference is the earlier one also applies an optimization getting rid of setExclude and just using the cache line presence instead, which ends up being redundant with the setExclude.
We can add that optimization as a separate PR since it’s a little bit less obvious why it works, I left it out when I rewrote this one.
154+ }
155+ for (size_t i = 0, n_to_process = descendants.size(); i < n_to_process; ++i) {
156+ const CTxMemPoolEntry& descendant = *descendants[i];
157+ const CTxMemPoolEntry::Children& children = descendant.GetMemPoolChildrenConst();
158+ for (const CTxMemPoolEntry& childEntry : children) {
159+ cacheMap::iterator cacheIt = cachedDescendants.find(mapTx.iterator_to(childEntry));
descendant in cachedDescendants before fetching its children? If its descendant set is available there, you wasted a cycle looking at the first generation.
children is non-empty - this change should also allow getting rid of the current find call in the children loop and just add straight to descendants. The current logic in master of checking cachedDescendants is a bit odd as if there are three txn’s (t1 -> t2 -> t3) in a chain that depend on each other sequentially, then the find call will only get a “hit” when t3 is updateIt as it “skips” t2
166+ descendants.emplace_back(cacheEntry);
167+ // skip self-swap because of buggy std::swap implementations
168+ // on some platforms
169+ if (!(descendants.size() == i+2)) {
170+ std::swap(descendants[i+1], descendants.back());
171+ }
IIUC, you’re swapping here in order to insert all of the descendants between this child and the next entry in the descendants vector, so you can just increment i to skip to the next child in the same generation. Note that you’re still moving everything downwards n times where n is the number of cached descendants.
Approach-wise, perhaps a std::deque (linked list) is more appropriate if you really want the constant time insert at arbitrary position. Also, I’m not too familiar with the implementation of std::vector, but I feel like it should be optimized enough for you to feel okay using insert(i+1) without using swaps. It might even do that in the background.
Also, please add a comment because it was not immediately obvious that you’re doing swaps to maintain ordering.
I think you have it backwards kinda. we do not care about ordering whatsoever, we are keeping a “partition” of processed and unprocessed elements.
essentially we have a queue with processed and unprocessed elements and a pointer to where we should process next.
0// start
1
2[P1 P2 P3 P4 *U5 U6 U7 U8]
3
4// process element
5
6[P1 P2 P3 P4 P5 *U6 U7 U8]
7
8// insert processed element using push back and swap
9[P1 P2 P3 P4 P5 *U6 U7 U8 P9]
10[P1 P2 P3 P4 P5 *P9 U7 U8 U6]
11[P1 P2 P3 P4 P5 P9 *U7 U8 U6]
12// insert unprocessed element
13[P1 P2 P3 P4 P5 P9 *U7 U8 U6 U10]
If we were to try to do the same with inserts, it would cause N^2 behavior. As you can see, we also do not preserve order during the swap back approach.
If we were to do insert it would look like:
0[P1 P2 P3 P4 P5 *U6 U7 U8]
1// insert processed element using insert
2[P1 P2 P3 P4 P5 *P9 U6 U7 U8 P9]
3[P1 P2 P3 P4 P5 P9 *U6 U7 U8 P9]
And the shifting would cost O(N).
Deque is a good data structure, but has an awful lot of extra overhead making it a poor fit for a performance critical code section. One of the key benefits of this approach is that we keep our data structure quick to iterate/add to.
The swap approach is O(1) per element added, which is fine. If we used insert / shifting it would be O(N) per element, which would cause a quadratic blowup.
By preserve ordering, I merely meant that you’re keeping the unprocessed elements behind the processed ones. We’re saying the same thing, sorry for being unclear.
If we were to try to do the same with inserts, it would cause N^2 behavior.
Sure, this is the case if you’re shifting everything per-insert inside the vector. This is why I suggested using a deque, where it’s O(1) per element. It’d be the same performance as what you’re doing here, except you just call insert instead of swapping. But my concerns with the complexity/readability of the code will be gone if you just comment what you’re doing here.
142+ std::vector<txiter> descendants(children.size());
143+ size_t i = 0;
144+ for (const auto& child: children) {
145+ descendants[i] = mapTx.iterator_to(child);
146+ ++i;
147+ }
What is the purpose of i here? You’re re-assigning it later anyway.
Also, why can’t you just do a std::transform from children to populate descendants?
i is needed to index descendants which is allocated up front.
it could be a std::transform I suppose, but I don’t think std::transform provides a readability improvement here.
i is needed to index descendants which is allocated up front
Just push_back, and you don’t need to allocate anything
if i do a call to reserve instead of the sized constructor https://en.cppreference.com/w/cpp/container/vector/vector, that would work w/o extra allocations.
the sized constructor + default insert + indexed insert is a bit better IMO because there are some overheads to push_back/emplace_back in terms of updating the vec bookkeeping that the simple indexed insert above does not have, but it’s all something that would need measuring as the compiler probably does an OK job at it.
do you have a strong preference around this?
222+ // emplace into a new vector to guarantee we trim memory
223+ const auto& it = cachedDescendants.emplace(std::piecewise_construct,
224+ std::forward_as_tuple(updateIt),
225+ std::forward_as_tuple(descendants.begin(), included_upto));
226+ // swap with descendants to release it early!
227+ std::vector<txiter>().swap(descendants);
std::shrink_to_fit() https://www.cplusplus.com/reference/vector/vector/shrink_to_fit/ “guarantee we trim” or no?
descendants goes out of scope when we return.
from what you cited:
The request is non-binding, and the container implementation is free to optimize otherwise and leave the vector with a capacity greater than its size.
Ideally we would be happy trusting our shrink_to_fit, but I’d rather get exactly a trimmed vector here.
we do allocate (descendants_to_remove.insert), so it’s a cautious approach to free it explicitly when it will never be used again than later.
Sounds good.
And my other question - what’s the point of releasing descendants early?
e do allocate (descendants_to_remove.insert), so it’s a cautious approach to free it explicitly when it will never be used again than later.
137- descendants.insert(*cacheEntry);
138+ const CTxMemPoolEntry::Children& children = updateIt->GetMemPoolChildrenConst();
139+
140+ // initialize to hold all direct children
141+ // children guaranteed to be unique at this point
142+ std::vector<txiter> descendants(children.size());
UpdateForDescendants should have the LOCKS_EXCLUDED annotation for m_epoch in txmempool.h
🐙 This pull request conflicts with the target branch and needs rebase.
Want to unsubscribe from rebase notifications on this pull request? Just convert this pull request to a “draft”.