[tests] Reduced number of validations in tx_validationcache_tests #13533

lucash-dev · 2018-06-25T00:55:03Z

Following a suggestion in the comments, changed ValidateCheckInputsForAllFlags from testing all possible flag combinations to testing a random subset. Also created a new enum constant for the highest flag, so that this test doesn’t keep testing an incomplete subset in case a new flag is added.

Timing for checkinputs_test:

Before:   6.8s
After:    3.7s
----------------
Saved:    3.1s (45%)

This PR was split from #13050. Also see #10026.

DrahtBot · 2018-06-26T11:17:59Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

Implement BIP-119 Validation (CheckTemplateVerify) #21702 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.

src/test/txvalidationcache_tests.cpp

DrahtBot · 2019-08-16T13:49:16Z

The last travis run for this pull request was 312 days ago and is thus outdated. To trigger a fresh travis build, this pull request should be closed and re-opened.

adamjonas · 2019-10-30T19:01:19Z

Concept ACK

I was looking at this before the conflict popped up and the savings on my machine was:

Before: 3.7s
After: 2.8s
------------
Saved 0.9s (24%).

My rebase is here for reference.

lucash-dev · 2019-10-30T21:44:18Z

Thx @adamjonas.
Will be away for a few days, probably will rebase over the weekend.

lucash-dev · 2019-11-05T22:52:47Z

@adamjonas rebased. thx

theStack

Concept ACK
Though on the current master branch enumerating through all possible script-verify-flags combinations is still feasible (running tx_validationcache_tests takes less than 2 seconds on my machine), the execution time for the validation loop would obviously increase exponentially with each script-verify-flag added.

theStack · 2020-01-23T20:41:47Z

src/script/interpreter.h

+    // Constants to point to the highest flag in use. Add new flags above this line.
+    //
+    HIGHEST_FLAG_PLUS_ONE,
+    HIGHEST_FLAG = HIGHEST_FLAG_PLUS_ONE - 1


I'd suggest to prefix those two constants with SCRIPT_VERIFY_ as well. Otherwise ever single translation unit including script/interpreter.h will have a bare HIGHEST_FLAG {_PLUS_ONE} constant in its global namespace and there isn't any reference in the name to which flags it refers to.

theStack · 2020-01-23T20:42:42Z

src/test/txvalidationcache_tests.cpp

+
+    FastRandomContext insecure_rand(true);
+
+    for (uint32_t count=0; count < 10000; count++) {


Now that the loop variable is a simple counter, not representing a bitfield anymore, I'd change the data type to just a plain int.

theStack · 2020-01-23T20:48:03Z

src/test/txvalidationcache_tests.cpp

+        // Randomly selects flag combinations
+        unsigned int test_flags = (unsigned int) insecure_rand.randrange(HIGHEST_FLAG << 1);


nit: The data type was an explicit uint32_t before, so I'd also that type here now rather than the more general unsigned int (in practice it won't matter though, so feel free to ignore).

lucash-dev · 2020-02-13T06:05:19Z

Concept ACK
Though on the current master branch enumerating through all possible script-verify-flags combinations is still feasible (running tx_validationcache_tests takes less than 2 seconds on my machine), the execution time for the validation loop would obviously increase exponentially with each script-verify-flag added.

Hi, @theStack. Thank you for reviewing this PR. I agree with your comments and will implement them. Just a little bit busy, but hopefully will have some time for that in the next few weeks.

thanks!

lucash-dev · 2020-03-04T19:07:08Z

hi @theStack. finally implemented the changes you suggested, also rebased -- and test are passing.

theStack

ACK 9364bf6 🍻

adamjonas · 2020-06-16T19:09:34Z

Hi @lucash-dev, pinging for a rebase. Mine is here for reference.

lucash-dev · 2020-06-23T05:28:34Z

thx @adamjonas. rebased.

kallewoof

Concept ACK; the change looks reasonable, and cutting down on redundant testing is definitely desirable.

src/script/interpreter.h

kallewoof · 2020-08-26T01:43:36Z

src/script/interpreter.h

+    // Constants to point to the highest flag in use. Add new flags above this line.
+    //
+    SCRIPT_VERIFY_HIGHEST_FLAG_PLUS_ONE,
+    SCRIPT_VERIFY_HIGHEST_FLAG = SCRIPT_VERIFY_HIGHEST_FLAG_PLUS_ONE - 1


Suggest you call this SCRIPT_VERIFY_END_MARKER, and then use < SCRIPT_VERIFY_END_MARKER logic instead of this, i.e. only add one.

kallewoof · 2020-08-26T01:44:45Z

src/test/txvalidationcache_tests.cpp

+
+    FastRandomContext insecure_rand(true);
+
+    for (int count=0; count < 10000; count++) {


Style-nit: spacing, ++ before varname:

for (int count = 0; count < 10000; ++count) {

kallewoof · 2020-08-26T01:48:47Z

src/test/txvalidationcache_tests.cpp

        TxValidationState state;
+
+        // Randomly selects flag combinations
+        uint32_t test_flags = (uint32_t) insecure_rand.randrange(SCRIPT_VERIFY_HIGHEST_FLAG << 1);


Using the marker style, to get the same you'd randrange((SCRIPT_VERIFY_END_MARKER - 1) << 1) here.

However, I'm not sure why you are doing << 1 here (1U << 17), as the original code only goes up to SCRIPT_VERIFY_END_MARKER - 1 (i.e. (1U << 16)). To retain the same, this would be randrange(SCRIPT_VERIFY_END_MARKER - 1);

Hi, @kalewoof. Thanks for reviewing.
The reason for that is that we want to possibly test all flag combinations (or a random subset thereof). The lowest value possible with all flags off is 0, the highest would be the sum of all constants. So if the highest constant is 1<<16, having the maximum value used for test be 1<<16 would preclude testing combinations of that flag being used. We need to test from 0 to 1111111111111111 (1<<17 -1). Because of the range being exclusive of the highest value, I pass 1<<17 = (SCRIPT_VERIFY_END_MARKER - 1) << 1
Hope that clarifies.

The test currently only going to 1<<16 is probably a mistake caused by adding a flag but not updating the test.

Test created in e3f9c05. Not updated after the new flag added in 9dabfe4

lucash-dev · 2020-09-15T15:29:58Z

Hi @fanquake
What’s the reason for closing it now?
I was meaning to implement the latest round of requested changes and it has concept acks.
Should I work on this, open a new one or just move on?
Just looking for clarification— don’t want to waste anyone’s time if maintainers don’t want this change. I know you have plenty on your plate.
Thanks!

fanquake · 2020-09-15T22:09:33Z

Hi @lucash-dev. I closed this because of the length of time it's been open overall, the length of time it's been since comments were left and had been unaddressed, and after looking at your GitHub profile it seemed that you were no-longer active here (hence throwing it up for grabs). However if you are going to address the concerns, I'll re-open this.

lucash-dev · 2020-09-16T00:20:27Z

Thanks @fanquake. Sorry for leaving this PR unattended for so long.

lucash-dev · 2020-09-16T00:25:30Z

Updated PR to fix @kallewoof's NIT's.

kallewoof · 2020-09-16T05:21:45Z

src/test/txvalidationcache_tests.cpp

        TxValidationState state;
+
+        // Randomly selects flag combinations
+        uint32_t test_flags = (uint32_t) insecure_rand.randrange((SCRIPT_VERIFY_END_MARKER - 1) << 1);


You want to swap the - and <<; right now you get 111...0, i.e.

Suggested change

uint32_t test_flags = (uint32_t) insecure_rand.randrange((SCRIPT_VERIFY_END_MARKER - 1) << 1);

uint32_t test_flags = (uint32_t) insecure_rand.randrange((SCRIPT_VERIFY_END_MARKER << 1) - 1);

Not really.
Right now the last flag is 1<<16.
Bc of the way the enum works my new constant becomes (1<<16)+1. That’s why I used the “...PLUS_ONE” constant before.
So the argument to the range is (((1<<16)+1)-1)<<1 = (1<<16)<<1 = 1<<17
Because the range is exclusive, the highest possible value is (1<<17)-1 = 1111111111111111b

Ahh, I misread it as a mask for some reason.

…he run time reasonable. Following a suggestion in the comments, changed `ValidateCheckInputsForAllFlags` from testing all possible flag combinations to testing a random subset. Also created a new enum constant for the highest flag, so that this test doesn’t keep testing an incomplete subset in case a new flag is added.

lucash-dev · 2020-10-16T18:14:38Z

Rebased.

@kallewoof would you mind ACK-ing since I addressed your comments (or otherwise make further comments)?

I think this PR has become (more) important after the new taproot flags were introduced -- since none of those flags are tested by this test case in master.

leonardojobim

tACK c3e111a.
Tested on Ubuntu 20.04 on VMWAre.

Average tests execution time:
. Master branch: 1.02s
. This PR branch: 0.60s

These values have remained consistent across several runs.

kallewoof

ACK c3e111a

theStack

re-ACK c3e111a

lucash-dev · 2021-07-26T19:31:44Z

Thanks everyone!

I know reviewing PRs is a lot of work, and this one wasn't a priority -- so I'm really glad to see it finally merged.

I learned a lot from writing it and from your feedback!

…dationcache_tests c3e111a Reduced number of validations in `tx_validationcache_tests` to keep the run time reasonable. (lucash-dev) Pull request description: Following a suggestion in the comments, changed `ValidateCheckInputsForAllFlags` from testing all possible flag combinations to testing a random subset. Also created a new enum constant for the highest flag, so that this test doesn’t keep testing an incomplete subset in case a new flag is added. Timing for `checkinputs_test`: ``` Before: 6.8s After: 3.7s ---------------- Saved: 3.1s (45%) ``` This PR was split from bitcoin#13050. Also see bitcoin#10026. ACKs for top commit: leonardojobim: tACK bitcoin@c3e111a. kallewoof: ACK c3e111a theStack: re-ACK c3e111a Tree-SHA512: bef49645bdd4f61ec73cc77a9f028b95d9856db9446d2e7fc9a48867a6f0e94c2c9f150cb771a30fe852db0efb0a1bd15d38b00d712651793ccb59ff6157a7b4

fanquake added the Tests label Jul 1, 2018

laanwj reviewed Jul 5, 2018

View reviewed changes

src/test/txvalidationcache_tests.cpp Outdated Show resolved Hide resolved

DrahtBot closed this Aug 25, 2018

DrahtBot reopened this Aug 25, 2018

DrahtBot mentioned this pull request Sep 7, 2018

[Policy] Reject SIGHASH_SINGLE with output out of bound #13360

Closed

practicalswift reviewed Oct 4, 2018

View reviewed changes

src/test/txvalidationcache_tests.cpp Outdated Show resolved Hide resolved

DrahtBot closed this Aug 16, 2019

DrahtBot reopened this Aug 16, 2019

DrahtBot added the Needs rebase label Oct 30, 2019

DrahtBot removed the Needs rebase label Nov 5, 2019

theStack reviewed Jan 23, 2020

View reviewed changes

DrahtBot mentioned this pull request Feb 11, 2020

Implement BIP 340-342 validation (Schnorr/taproot/tapscript) #17977

Closed

4 tasks

theStack approved these changes Mar 4, 2020

View reviewed changes

DrahtBot mentioned this pull request Apr 16, 2020

tests: Don't initialize PrecomputedTransactionData in txvalidationcache tests #18675

Merged

DrahtBot added the Needs rebase label Apr 19, 2020

DrahtBot removed the Needs rebase label Jun 19, 2020

kallewoof reviewed Aug 26, 2020

View reviewed changes

fanquake added the Up for grabs label Sep 15, 2020

fanquake closed this Sep 15, 2020

fanquake reopened this Sep 15, 2020

fanquake removed the Up for grabs label Sep 15, 2020

kallewoof reviewed Sep 16, 2020

View reviewed changes

This was referenced Sep 19, 2020

Implement BIP 340-342 validation (Schnorr/taproot/tapscript) #19953

Merged

History for Taproot PR #19953 #19997

Closed

DrahtBot added the Needs rebase label Oct 15, 2020

DrahtBot removed the Needs rebase label Oct 15, 2020

leonardojobim reviewed Feb 23, 2021

View reviewed changes

DrahtBot mentioned this pull request Apr 15, 2021

Implement BIP-119 Validation (CheckTemplateVerify) #21702

Closed

kallewoof reviewed Jul 17, 2021

View reviewed changes

theStack approved these changes Jul 18, 2021

View reviewed changes

maflcko merged commit fd557ce into bitcoin:master Jul 24, 2021

bitcoin locked as resolved and limited conversation to collaborators Aug 18, 2022


		FastRandomContext insecure_rand(true);

		for (uint32_t count=0; count < 10000; count++) {

		// Randomly selects flag combinations
		unsigned int test_flags = (unsigned int) insecure_rand.randrange(HIGHEST_FLAG << 1);


		FastRandomContext insecure_rand(true);

		for (int count=0; count < 10000; count++) {

	uint32_t test_flags = (uint32_t) insecure_rand.randrange((SCRIPT_VERIFY_END_MARKER - 1) << 1);
	uint32_t test_flags = (uint32_t) insecure_rand.randrange((SCRIPT_VERIFY_END_MARKER << 1) - 1);

[tests] Reduced number of validations in tx_validationcache_tests #13533

[tests] Reduced number of validations in tx_validationcache_tests #13533

Uh oh!

Conversation

lucash-dev commented Jun 25, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Jun 26, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

Uh oh!

Uh oh!

DrahtBot commented Aug 16, 2019

Uh oh!

adamjonas commented Oct 30, 2019

Uh oh!

lucash-dev commented Oct 30, 2019

Uh oh!

lucash-dev commented Nov 5, 2019

Uh oh!

theStack left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

lucash-dev commented Feb 13, 2020

Uh oh!

lucash-dev commented Mar 4, 2020

Uh oh!

theStack left a comment

Choose a reason for hiding this comment

Uh oh!

adamjonas commented Jun 16, 2020

Uh oh!

lucash-dev commented Jun 23, 2020

Uh oh!

kallewoof left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

kallewoof Aug 26, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

lucash-dev commented Sep 15, 2020

Uh oh!

fanquake commented Sep 15, 2020

Uh oh!

lucash-dev commented Sep 16, 2020

Uh oh!

lucash-dev commented Sep 16, 2020

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

lucash-dev commented Oct 16, 2020

Uh oh!

leonardojobim left a comment

Choose a reason for hiding this comment

Uh oh!

kallewoof left a comment

Choose a reason for hiding this comment

lucash-dev commented Jun 25, 2018 •

edited

Loading

DrahtBot commented Jun 26, 2018 •

edited

Loading

kallewoof Aug 26, 2020 •

edited

Loading