Good ideas. There is the question of using sets for the data structure. The first commit 2898d65 "Rewrite parent txid loop of requested transactions" seems to break a number of functional tests for me locally. All the tests pass again after rebasing to keep only the second commit.

interface_rest.py                       | ✖ Failed  | 35 s
mempool_packages.py                     | ✖ Failed  | 3 s
p2p_segwit.py                           | ✖ Failed  | 23 s
rpc_rawtransaction.py                   | ✖ Failed  | 9 s
wallet_avoidreuse.py                    | ✖ Failed  | 6 s
wallet_avoidreuse.py --descriptors      | ✖ Failed  | 7 s
wallet_backup.py                        | ✖ Failed  | 9 s
wallet_balance.py                       | ✖ Failed  | 15 s
wallet_bumpfee.py                       | ✖ Failed  | 5 s
wallet_groups.py                        | ✖ Failed  | 12 s
wallet_listtransactions.py              | ✖ Failed  | 36 s

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

• p2p: refactor AlreadyHave(), CInv::type, INV/TX processing #19610 (p2p: refactor AlreadyHave(), CInv::type, INV/TX processing by jonatack)
• refactor: Replace RecursiveMutex with Mutex in CTxMemPool #19306 (refactor: Replace RecursiveMutex with Mutex in CTxMemPool by hebasto)

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.

It should be substantially faster and memory friendly for these big txns to fill the parents set as a vector of hashes, sort it, use std::unique to shift out the duplicates, and then erase garbage.

I think this is just:

--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -2990,10 +2990,12 @@ void ProcessMessage(
 
             // Deduplicate parent txids, so that we don't have to loop over
             // the same parent txid more than once down below.
-            std::set<uint256> unique_parents;
+            std::vector<uint256> unique_parents;
+            unique_parents.reserve(tx.vin.size());
             for (const CTxIn& txin : tx.vin) {
-                unique_parents.insert(txin.prevout.hash);
+                unique_parents.push_back(txin.prevout.hash);
             }
+            std::sort(unique_parents.begin(), unique_parents.end());
+            unique_parents.erase(std::unique(unique_parents.begin(), unique_parents.end()), unique_parents.end());
             for (const uint256& parent_txid : unique_parents) {
                 if (recentRejects->contains(parent_txid)) {
                     fRejectedParents = true;

I think I agree the vector/sort/unique approach is better -- temporarily allocating up to twice the space it takes to store the transaction seems fine, and allocating memory at once rather than for each input seems better; but not sure it should matter all that much.

Alternatively, could maybe do it as:

    for (txin : tx.vin) {
        if (recentRejects->contains(txin.prevout.hash)) {
            fRejectedParents = true;
        }
    }
    if (!fRejectedParents && pfrom.m_tx_relay != nullptr) {
        LOCK(pfrom.m_tx_relay->cs_tx_inventory);
        for (txin : tx.vin) {
            if (pfrom.m_tx_relay->filterInventoryKnown.contains(txin.prevout.hash)) continue;
            if (AlreadyHave(CInv(MSG_TX | nFetchFlags, txin.prevout.hash))) continue;
            pfrom.m_tx_relay->filterInventoryKnown.insert(txin.prevout.hash)
            RequestTx(txin.prevout.hash);
        }
    }

and rely on both recentRejects and filterInventoryKnown lookups being quick enough that duplicates don't matter, and use filterInventoryKnown to ensure the slow ops only get queried once per tx, rather than once per prevout.

(travis reports a lock order violation btw)

Thanks all for the quick review! @ajtowns I grabbed your code for using a vector instead of a set, and hopefully fixed the lock inversion problem.

@jonatack I'm surprised by the test failures, is it possible the lock inversion caused that?

Code review ACK 842f908

I don't understand where the locking failure is coming from. Is it possibly fixed now?

I don't understand where the locking failure is coming from. Is it possibly fixed now?

@sipa Yes it should be fixed now; when I opened the PR initially, I wasn't letting go of the mempool lock before acquiring the others in the first commit.

@jnewbery Overhead of a set over a vector is the size of 3 pointers and an int (for red black tree structure), plus 2 pointers (for malloc overhead), and that rounded up to the next multiple of 2 pointers' worth.

For 64-bit systems that means between 48 and 63 bytes overhead.

Thanks @sipa!

If that's not clear for anyone reading along, because I frequently have to re-check this logic...

the implementation we assume for std::set is a red black tree, with a layout of:

template <typename T>
struct node {
int color;
void* parent;
void* left;
void* right;
T element;
}

This sums to 8 bytes * 4 (int has 4 bytes padding) = 32 bytes of overhead, no extra alignment for T required (unless there's some external alignment requirement > 32). But in std::set, every node is individually alloc'd with malloc (as opposed to using an arena, which would reduce overhead). Malloc typically requires an extra 16 bytes of data (but can be higher or lower platform dependent, not counting whatever other internal bookkeeping memory overhead heap may required?), and then pads out the allocation to a 16 byte boundary. If you look at MallocUsage, it's ((s + 31) >> 4 <<4), but the 31 is really +16 (for malloc metadata) and +15 >>4 <<4 for the padding.

This means that for a 32 byte hash, you need an estimated 80 bytes per element in a std::set (so 2.5x, a bit better than 3x, but still excessive). The main issue IMO is less so the memory and more so the calls to malloc itself. E.g., if vector used 2x memory and std::set used 1x memory, it still might be preferable to use the vector to avoid N calls to malloc.

Thanks @JeremyRubin! Very interesting.

Has unordered_set been evaluated?

unordered_set... ah the promise of O(1) accesses. I don't think it makes sense to do here since N is small. Here's my overall thinking:

This piece of code isn't exactly adversarial. Whatever algorithm we pick -- sorting or hash tabling, is going to be good enough. This is mostly about picking something with good average runtime and acceptable worst case runtime, and preferably low memory on average.

For unordered_set we use about 72 bytes per entry (32 bytes, 1 pointer, padded out to 64 bytes, and then 8 more for the buckets), and still need do O(n) allocations (unless we do a custom arena allocator, then we can save it!). Then we get an implementation that will be O(N) instead of O(N log N). However I think the largest N is about 100kb/40b (largest standard txn divided by size of input), so we're looking at about 2,500 inputs, and log2(2500) is about 11. However, if you think about sorting a vector of bytearrays, I think that should be pretty performant compared to all the pointer chasing, hashing, and allocating that a hash map will make you do. And in the common case, which is smaller numbers of inputs, the log N will matter less.

So I think a plain hash map, which better big O, is going to be worse on average and not much better worst case, if any better at all.

if you did want to make a simple competitive algorithm for doing this based on hash sets, here's what I would do:

1. allocate a std::vector 8x the size of the number of inputs in bits and a vector for N elements
2. get 5 x 12 bits of entropy for each entry, and check and set the bit in the vector for each by using the projecting trick.
   a. If all 5 bits are already set, insert the item into a std::set or std::unordered_set named likely_dups.
   b. otherwise, push back element onto the vector
3. iterate over the vector removing anything in the set (quit if set empty)
4. extend the end of the vector with whatever is left in the set

This algorithm is correct because every item with no perfect overlapped bits in the set is unique. So by step 3, the vector is unique, and the std::unordered_set has all the likely non unique entries (but is also, conveniently, unique). We then attempt to remove from the set every element in the vector, guaranteeing the set only has what's not in the vector. Then we add those to the vector, and the vector contains all unique elements from the original vector of elems.

However this algorithm works really nicely for the expected case (no colliding) because we only have to make 2 malloc calls and emplace everything into our vector after checking the filter (which should have low prob of collision), so it should be pretty speedy! And in the case where there are a lot of duplicates, we don't end up allocating that much memory in the likely set because they are duplicated! The worst case is where every element has exactly 1 duplicate, then we end up doing extra work.

However, this is a lot of work to do and get right so I think the sort remove technique is fine.

Rebased and addressed @jnewbery's feedback.

Code review ACK 4c0731f