Improved readability of ApproximateBestSubset #7183

vValue is sorted into ascending order before ApproximateBestSubset(...) is called.

Currently, after a new best set is found, the final element that was added gets removed from the set, and the inner loop continues to search through the remainder of vValue for a better set. It is however impossible for a better set to be achieved with a later element in vValue: As vValue is sorted in ascending order, any set formed with a later element will be of same size or bigger.

Therefore, the lines 1628 & 1629 are obsolete, and the inner loop should also stop on fReachedTarget.

vValue is not sorted in ascending order, the whole algorithm wouldn't make sense if it was...

@MarcoFalke: Sorry, apparently the links always refer to the current version and shift around because of that, however in CWallet::SelectCoinsMinConf(…) there are the following lines:

// Solve subset sum by stochastic approximation
sort(vValue.rbegin(), vValue.rend(), CompareValueOnly());
vector<char> vfBest;
CAmount nBest;

ApproximateBestSubset(vValue, nTotalLower, nTargetValue, vfBest, nBest);

As you can see vValue appears to get sorted into ascending order right before ApproximateBestSubset(…) gets called. I do think that it used to be different when I first started my other PR (September last year) though, because right now it does increase the probability of small inputs to get selected.

vValue is not sorted in ascending order, the whole algorithm wouldn't make sense if it was...

It actually is. (or is CompareValueOnly doing something else than I assumed it does? that'd be confusing...) Nope:

struct CompareValueOnly
{
    bool operator()(const pair<CAmount, pair<const CWalletTx*, unsigned int> >& t1,
                    const pair<CAmount, pair<const CWalletTx*, unsigned int> >& t2) const
    {
        return t1.first < t2.first;
    }
};

If you say this sorts it in descending order, I don't see where that happens.

If you say this sorts it in descending order, I don't see where that happens.

Right in the line where std::sort() is called: https://github.com/bitcoin/bitcoin/blob/5dc63ed1ca8aca62f28881ba9ef996d4036a23ea/src/wallet/wallet.cpp#L1719

r means reverse and the reverse of ascending is descending?

links always refer to the current version and shift around because of that @Xekyo If you want to link on GitHub, don't forget to press the y-Key before copy pasting the link

Yikes, that's easy to overlook, perhaps a comment.

And a unit test because this PR should not pass travis in the first place.

@Xekyo Can you take a look at this and add a comment above the "sort()-line"?

Yikes, that's easy to overlook, perhaps a comment.

Absolutely. I also had no idea that you could pass reverse iterators to std::sort and it would just work.

@MarcoFalke: TIL. I was unaware of that behaviour of sort(…) with reverse iterators. From what I’m reading using reverse iterators isn’t very efficient, though.

Instead of using reverse iterators, one could replace the line

 sort(vValue.rbegin(), vValue.rend(), CompareValueOnly());

with these two

sort(vValue.begin(), vValue.end(), CompareValueOnly());
reverse(vValue.begin(), vValue.end());

It would become much more readable, wouldn’t need a comment to clarify, and perhaps perform even faster.

Sounds ok to me. Are you planning to write the unit test as well?

@MarcoFalke: I could do that, yet I’m unsure what one would want to test. Since the sorting operation is in the middle of CWallet::SelectCoinsMinConf(…), it’s would require quite a bit of refactoring to isolate as vValue is only a transient variable in that function.

@Xekyo I mean a "high level" test like #7193, such that your initial commit will fail travis. (Would you mind to post the inital diff or commit hash for reference and testing, I forgot to save it.)

@MarcoFalke: Unfortunately, I also overwrote my commit when I rebased my branch (perhaps prematurely) and pushed it to my fork. Would it make sense to redo them and push them onto another branch?

I’ve added a test.

Provided by @Xekyo on IRC: $ git reflog show Fix-#7182@{one.day.ago}

b9ecfc7

diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index d23d54e..3d1f58c 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -1605,7 +1605,7 @@ static void ApproximateBestSubset(vector<pair<CAmount, pair<const CWalletTx*,uns
         bool fReachedTarget = false;
         for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
         {
-            for (unsigned int i = 0; i < vValue.size(); i++)
+            for (unsigned int i = 0; i < vValue.size() && !fReachedTarget; i++)
             {
                 //The solver here uses a randomized algorithm,
                 //the randomness serves no real security purpose but is just
@@ -1625,8 +1625,6 @@ static void ApproximateBestSubset(vector<pair<CAmount, pair<const CWalletTx*,uns
                             nBest = nTotal;
                             vfBest = vfIncluded;
                         }
-                        nTotal -= vValue[i].first;
-                        vfIncluded[i] = false;
                     }
                 }
             }

utACK 047cf77e324817594ce58e0ff53e5d817d1a9bc1.

Nit: you could use std::sort and std:reverse to prevent follow up commits.

Edited to include the nit. :)

trivial re-ACK 96efcad

utACK 96efcadfc0d8a84066982533c676072d3b5d8314

utACK 96efcad

Is there some reason not to just invert the CompareValueOnly function?

And call it ReverseCompareValueOnly, yes that would have been the other option. But let's leave it as it is now, there's no need to shedpaint this.