Inclusive bounds for thresh()'s threshold
#55
Conversation
7b93186 to
71a52e0
Compare
71a52e0 to
b3329b9
Compare
compiler.cpp
Outdated
| strats.push_back(MakeStrat(store, Strat::Type::THRESH, subs, node.k, (double)node.k / subs.size())); | ||
| } | ||
| if (node.k == 1 || node.k == node.sub.size()) { | ||
| } else if ((node.k == 1 && node.sub.size() < 10) || node.k == node.sub.size()) { |
There was a problem hiding this comment.
Where is this limit 10 coming from?
EDIT: I see, it is avoiding inefficiencies. Does this not result in worse results in some cases?
There was a problem hiding this comment.
It does, but at least it results at some point :)
There was a problem hiding this comment.
In that case I'd prefer to fix that in other ways (e.g. have a simpler or/and strategy that doesn't consider all probabilities).
There was a problem hiding this comment.
Hmm ok so i think it was a bit clumsy for me to try to solve this in this PR since it gets outside the scope and was a hack for the specific thresh case but a decent solution would also encompass the existing nested-or()s case.
How about leaving this as a follow-up? This PR does not make the existing situation worse (but still opens up a new situation where this can be encountered..).
There was a problem hiding this comment.
Yeah, sure - I just noticed too late this PR was changing more than what I had expected it to do.
compiler.cpp
Outdated
| while (subs.size() > 1) { | ||
| auto rep = MakeStrat(store, node.k == 1 ? Strat::Type::OR : Strat::Type::AND, Vector(*(subs.rbegin() + 1), subs.back()), 1.0 / subs.size()); | ||
| subs.pop_back(); | ||
| subs.pop_back(); | ||
| subs.push_back(MakeStrat(store, Strat::Type::CACHE, Vector(rep))); | ||
| } | ||
| strats.push_back(subs[0]); | ||
| } else { |
There was a problem hiding this comment.
I don't think there is a reason for this sequence of if/then/elses. Just use all applicable strategies. The compiler will use the best one.
There was a problem hiding this comment.
Right. The first else if was an oversight, but the else part i'm not sure. I figured that it would put unnecessary burden on the compiler to add the thresh strategy if:
- The policy is just a (smallish) multisig
- The policy can be represented as nested
or()s orand()s
as these would always be more efficient than the raw addition of all sub-policies. But maybe my intuition is wrong for the latter?
Anyways, amended :)
There was a problem hiding this comment.
You may be right, but the code is more obviously going to find the optimal one if it just tries everything.
Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
Signed-off-by: Antoine Poinsot <darosior@protonmail.com>
b3329b9 to
38b046f
Compare
|
utACK 38b046f |
3c9a837 test: inclusive bounds for thresh()'s threshold (Antoine Poinsot) Pull request description: #55 didn't come with any test. This fixes it. Based on #58 to benefit from the update and avoid needless conflicts. ACKs for top commit: sipa: ACK 3c9a837 Tree-SHA512: 38d5a271271c665267d50750b563c4312ccda497f42a6a4bf6750542232880a8839ad68cd0348cb3158b236a51c3439ebee1ee278c0c0a66195acc7606c35a5d
As per #39 and discussions on IRC this removes the exclusion of
k = 1andk = subs.size()forthresh.This is the opposite of rust-bitcoin/rust-miniscript#242 (adapting the Rust implementation to the C++ one) after sanket1729 's feedback.
Fixes #39