Remove redundant shuffle in KnapsackSolver #15752

It's a bit simpler to unconditionally shuffle once in SelectCoins instead of in SelectCoinsMinConf which is repeatedly called.

NACK this is not redundant, e.g.

https://github.com/bitcoin/bitcoin/blob/c83442e17412b96f00bc29d30763b28184c95f1e/src/wallet/test/coinselector_tests.cpp#L507-L517

@Empact the comment is wrong...

The reason it sometimes fails and sometimes succeeds is because of the randomization here: https://github.com/bitcoin/bitcoin/blob/e21129e78e38935eb3310207c5be7cf2b1f422e7/src/wallet/coinselection.cpp#L195

but note at that stage it's iterating over a sorted list:

https://github.com/bitcoin/bitcoin/blob/e21129e78e38935eb3310207c5be7cf2b1f422e7/src/wallet/coinselection.cpp#L255

The tests are failing, so they need to be updated in the same commit

What happens if there are ties in the sort or multiple smallest elements >= N?

@gmaxwell I doubt it matters, but fair enough point. That's easy enough to fix with: 856b0a7bd015551d166cb8001ac45460e659b28d to just unconditionally shuffle before all the calls to SelectCoinsMinConf

Rebased, updated original post (description) and removed the test of randomness in SelectCoinsMinConf as it's no longer applicable and SelectCoins doesn't make it easy to do the same test.

That looks better to me, but if deterministic output is significant to privacy, I'd rather have less efficient operation covered by a test than more efficient operation without one, particularly wrt coin selection.

@Empact even without the shuffle (which it has), the privacy implications are tiny. It only makes a difference in an extreme edge case: if BnB fails (does its own sorting), and if the sum of < N is <N fails (has its own randomization) and if the smallest >= N input has ties.

And even then, the privacy difference between "This is the smallest >= N input (first tie-breaking)" and "This is a smallest >= N input (random tie-breaking)" is going pretty negligible.

Why bother with the change however? I'm not really seeing the motivation for it, saving say 0.5ms in a 500ms operation isn't particularly interesting. Actually figuring out if the privacy difference is material isn't free....

Agree with @gmaxwell here.

I'd like to see significant performance numbers before considering this change. I'd suspect an extra shuffle is almost free, and the human work of reviewing this is considerable and likely better spent on other PRs.