cr-ack 6d1779d -- one of my earlier versions looked a lot like that.

I'd also suggest another optimization to make the vector a prevector with say 20 outputs so we can avoid the allocation on most txns.

May I suggest using adjacent_find with std::equal instead of your own loop?
https://en.cppreference.com/w/cpp/algorithm/adjacent_find

I prefer this to #14387, but I have the same question for @sipa as I asked Jeremy in that PR:

This makes block propagation faster, but do we have an understanding of how much these milliseconds matter? Is there a way we can determine whether the increased complexity introduced is a reasonable price to pay for the performance win?

Granted, the complexity added here is minimal compared to 14387, but I'd still like to understand the cost/benefit analysis.

@jnewbery Yeah, that's fair. I just wanted to show an alternative which is a smaller improvement but at much lower review complexity. I'm not convinced we need either approach.

For what it's worth, bitcoinperf didn't show any significant performance regression for IBD or reindex after the merge of #14247, so it's not clear that either changeset is needed.

@jamesob I think this is not so much about ibd but rather propagation

@MarcoFalke correct.

It's something like 13ms slower.

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #14400 (Add Benchmark to test input de-duplication worst case by JeremyRubin)

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.

Even block propagation is no longer critical for this: When the prior optimization went in, we didn't have relay-before-validate. I'm not opposed to this change-- as it's pretty straight forward to review-- but since this particular validity criteria is pure (a function of the tx itself with no dependency on external state) effort might be better spent reorging things so that this test ends up covered by the wtxid validity caching which, although complementary, would likely give a bigger improvement.

Is there an explanation of what purpose the duplicate input check will serve if the connect block code is fixed to check for valid spends?

@ryanofsky Making block connection alone check for duplicate inputs isn't sufficient: The whole reason this code was initially added in PR #443 was to keep duplicate inputs out of the mempool-- block connection did originally prevent the dupes. If both block-connection and mempool processing prevented duplicate inputs, then, indeed, there should be no reason for this code.

I think both set+insert (the existing one) and sort (this PR) are O(NlogN). So sort is faster as it is more optimized?

@jl2012 You get better memory locality and lower allocation overhead by representing things as a vector rather than a set. The set permits much faster updating though, but that's not something we need here.

There hasn't been much activity lately and the patch still needs rebase, so I am closing this for now. Please let me know when you want to continue working on this, so the pull request can be re-opened.