Might make more sense to put these on the class, rather than pass by-reference?

I'm working on a refactor of the BlockAssembler members separately (as part of a patch to exclude recent transactions from new blocks, when the fee difference is negligible), so I'd prefer to defer the decision of whether to include this in the class until I'm ready to PR that patch.

The old code used 50 for this. Does 1000 work good enough in practice?

Yes, well I also tried setting this to 100 and the performance was not really distinguishable.

Perhaps the additional condition(s) should be before incrementing, or we could end up just aborting immediately as we approach the max block weight even if we could easily fit a few more txs in.

I'm not following; every time we add a new tx to the block we reset the counter... Can you clarify?

Can you rename to nDescendantsUpdated to make clear that it should not be initialized to alreadyAdded.size()

This is a really interesting section. I got a bit nerd-sniped so apologies for long writeup.

Doing the following may be more efficient (I can code this up, but I don't want to step on your toes if you're operating here).

std::vector<txiter> diff(descendants.size());
auto end = std::set_difference(descendants.begin(), descendants.end(),
     alreadyAdded.begin(), alreadyAdded.end(), diff.begin()); // Linear time!
nDescendants += end - diff.begin();
for (auto it = diff.begin(); it != diff.end(); ++it) {
  // ....
} 

It requires an extra copy compared to the naive, but they're iterators so who cares (we can also reuse the vector for the entire call at the top of updatepackages)...

Let N = alreadyAdded.size()
Let M = descendants.size()
This does O(M+N) work (I think that most implementations actually do O(max(M, N)), but the standard specified 2*(M+N-1)), while what's currently happening would appear to be O(M*log(N)).

There is also a pre-loop-check one could do if it's likely they don't intersect.

// O(1)
if (descendants.back() < alreadyAdded.front() || descendants.front() > alreadAdded.back())
    // skip set_difference, descendants - alreadyAdded = descendants

And a pre-loop narrowing one could do to make it O(min(M, N)).

// O(log(M) + log(N))
auto range1 = descendants.equal_range(alreadyAdded.begin(), alreadyAdded.end())
auto range2 = alreadyAdded.equal_range(descendants.begin(), descendants.end())
std::vector<txiter> diff(range1.second - range1.first);
auto end = std::set_difference(range1.first, range1.second,
     range2.first, range2.second, diff.begin()); // Linear time!
nDescendants += end - diff.begin();
for (auto it = diff.begin(); it != diff.end(); ++it) {
  // ....
} 

Thanks, will try some of these out in future optimization efforts.

Could you add more of a comment on why resetting is correct behavior here?

It seems to me at first glance, that if we fail to add something earlier, we should continue to tally those as failures?
Perhaps:

Assuming that below a certain threshold `T` of probability
(i.e.,`T = P(success at M | failure at M-1....0)` where `M = 1000`) 
of adding something to the block we want to give up,
 we expect that 
`1000>D>0. P(success at N+D+1 | failure at N+D,... success at N, failure at N-1, ...) 
> P(success at N+D | failure at N, failure at N-1, ...)`?

Maybe not the most accurate, but would be helpful for future reviewers trying to understand what the intention is.

This is incremented whenever we fail (not just for failures after we're above a certain block weight), so it needs to be reset when adding a new tx.