Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2178153003:
Cache hashes in CTLogVerifier tests (Closed)
|
Created:
4 years, 4 months ago by Rob Percival Modified:
4 years, 4 months ago CC:
chromium-reviews, rsleevi+watch_chromium.org, certificate-transparency-chrome_googlegroups.com, cbentzel+watch_chromium.org Base URL:
https://chromium.googlesource.com/chromium/src.git@master Target Ref:
refs/pending/heads/master Project:
chromium Visibility:
Public. |
DescriptionCache hashes in CTLogVerifier tests
This reduces the duration of the long-running test case by ~50%.
This is particularly valuable given that a similarly long-running test
will shortly be added for testing audit proof verification.
BUG=598406
Patch Set 1 #
Total comments: 2
Messages
Total messages: 15 (4 generated)
Patchset #1 (id:1) has been deleted
Patchset #1 (id:20001) has been deleted
robpercival@chromium.org changed reviewers: + eranm@chromium.org, rsleevi@chromium.org
PTAL - just adds caching of hashes in CTLogVerifier tests.
https://codereview.chromium.org/2178153003/diff/40001/net/cert/ct_log_verifie... File net/cert/ct_log_verifier_unittest.cc (right): https://codereview.chromium.org/2178153003/diff/40001/net/cert/ct_log_verifie... net/cert/ct_log_verifier_unittest.cc:31: // significantly higher memory usage. Can you say how much or point to a calculation later in the file? https://codereview.chromium.org/2178153003/diff/40001/net/cert/ct_log_verifie... net/cert/ct_log_verifier_unittest.cc:440: static std::map<std::pair<std::string*, uint64_t>, std::string> cache; As discussed offline, there are two issues with using a string* as a part of the key: - This is counter-intuitive and the reason it works should be explicitly documented. - The memoization does not benefit multiple test cases, as each test case is likely to re-allocate strings itself. Using the string value as a part of the key will consume more memory but means multiple cases will benefit from the same cache.
I'm not terribly enthused by this approach. We have one problem, and now we have two, due to memoization. I'm concerned this is going to add to the cognitive and computational overhead. Has there been any consideration to splitting out the long-running test into a permutation test, given that you're effectively testing the permutations of paths between leaves and roots? That at least makes them distinct, small tests.
On 2016/07/26 18:39:02, Ryan Sleevi (extremely slow) wrote: > I'm not terribly enthused by this approach. We have one problem, and now we have > two, due to memoization. I'm concerned this is going to add to the cognitive and > computational overhead. Can you be explicit what's the second problem is? > > Has there been any consideration to splitting out the long-running test into a > permutation test, given that you're effectively testing the permutations of > paths between leaves and roots? That at least makes them distinct, small tests. Are you referring to something like: https://cs.chromium.org/chromium/src/net/quic/quic_connection_test.cc?sq=pack... ? You're right that the test tests consistency proof between all possible combinations of trees (i.e. for each tree of size N, build trees of size 0 .. N-1 and check that consistency proof generated by the reference generator verifies by the production code). Is the example linked above the right way to break it down to small tests?
On 2016/07/26 18:56:57, Eran Messeri wrote: > Can you be explicit what's the second problem is? The computational overhead? The whole reason for adding the memoization seems to be predicated on we're adding more slow tests; that is, the memoization encourages a test design that does a ton of work in a monolithic test, which is a test anti-pattern. > Are you referring to something like: > https://cs.chromium.org/chromium/src/net/quic/quic_connection_test.cc?sq=pack... > ? I would first point to https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... as the guidance. In particular, https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... and https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... Particularly relevant is the documentation note, as per https://github.com/google/googletest/blob/master/googletest/include/gtest/gte... Since you picked a rather large test, I'll point to a smaller test, such as https://cs.chromium.org/chromium/src/net/cert/x509_certificate_unittest.cc?rc... > > You're right that the test tests consistency proof between all possible > combinations of trees (i.e. for each tree of size N, build trees of size 0 .. > N-1 and check that consistency proof generated by the reference generator > verifies by the production code). > Is the example linked above the right way to break it down to small tests? The above examples may be simpler to evaluate the 'right' way
On 2016/07/26 19:06:02, Ryan Sleevi (slow) wrote: > On 2016/07/26 18:56:57, Eran Messeri wrote: > > Can you be explicit what's the second problem is? > > The computational overhead? The whole reason for adding the memoization seems to > be predicated on we're adding more slow tests; that is, the memoization > encourages a test design that does a ton of work in a monolithic test, which is > a test anti-pattern. > > > Are you referring to something like: > > > https://cs.chromium.org/chromium/src/net/quic/quic_connection_test.cc?sq=pack... > > ? > > I would first point to > https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... > as the guidance. > > In particular, > https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... > and > https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... > > Particularly relevant is the documentation note, as per > https://github.com/google/googletest/blob/master/googletest/include/gtest/gte... > > Since you picked a rather large test, I'll point to a smaller test, such as > https://cs.chromium.org/chromium/src/net/cert/x509_certificate_unittest.cc?rc... > > > > > You're right that the test tests consistency proof between all possible > > combinations of trees (i.e. for each tree of size N, build trees of size 0 .. > > N-1 and check that consistency proof generated by the reference generator > > verifies by the production code). > > Is the example linked above the right way to break it down to small tests? > > The above examples may be simpler to evaluate the 'right' way Unfortunately it's not trivial to make value-parameterised tests when there are two parameters, one of which is dependent on the other (i.e. we want all permutations where 1 <= tree_size <= 128 and 1 <= snapshot <= tree_size). Nevertheless, I've written an iterator that achieves this (see https://codereview.chromium.org/2187043004). The code is more complex, and we don't reduce the overall test duration this way, but each test case executes in ~3ms now, rather than there being a single ~13s test case. That single test case is now 8513 separate test cases. The overhead of that many extra test cases appears to have increased the overall test duration to ~24s.
On 2016/07/28 03:27:46, Rob Percival wrote: > On 2016/07/26 19:06:02, Ryan Sleevi (slow) wrote: > > On 2016/07/26 18:56:57, Eran Messeri wrote: > > > Can you be explicit what's the second problem is? > > > > The computational overhead? The whole reason for adding the memoization seems > to > > be predicated on we're adding more slow tests; that is, the memoization > > encourages a test design that does a ton of work in a monolithic test, which > is > > a test anti-pattern. > > > > > Are you referring to something like: > > > > > > https://cs.chromium.org/chromium/src/net/quic/quic_connection_test.cc?sq=pack... > > > ? > > > > I would first point to > > > https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... > > as the guidance. > > > > In particular, > > > https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... > > and > > > https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... > > > > Particularly relevant is the documentation note, as per > > > https://github.com/google/googletest/blob/master/googletest/include/gtest/gte... > > > > Since you picked a rather large test, I'll point to a smaller test, such as > > > https://cs.chromium.org/chromium/src/net/cert/x509_certificate_unittest.cc?rc... > > > > > > > > You're right that the test tests consistency proof between all possible > > > combinations of trees (i.e. for each tree of size N, build trees of size 0 > .. > > > N-1 and check that consistency proof generated by the reference generator > > > verifies by the production code). > > > Is the example linked above the right way to break it down to small tests? > > > > The above examples may be simpler to evaluate the 'right' way > > Unfortunately it's not trivial to make value-parameterised tests when there are > two parameters, one of which is dependent on the other (i.e. we want all > permutations where 1 <= tree_size <= 128 and 1 <= snapshot <= tree_size). > Nevertheless, I've written an iterator that achieves this (see > https://codereview.chromium.org/2187043004). The code is more complex, and we > don't reduce the overall test duration this way, but each test case executes in > ~3ms now, rather than there being a single ~13s test case. That single test case > is now 8513 separate test cases. The overhead of that many extra test cases > appears to have increased the overall test duration to ~24s. Never mind, I came up with a relatively straightforward way of implementing this. It
On 2016/07/28 03:27:46, Rob Percival wrote: > On 2016/07/26 19:06:02, Ryan Sleevi (slow) wrote: > > On 2016/07/26 18:56:57, Eran Messeri wrote: > > > Can you be explicit what's the second problem is? > > > > The computational overhead? The whole reason for adding the memoization seems > to > > be predicated on we're adding more slow tests; that is, the memoization > > encourages a test design that does a ton of work in a monolithic test, which > is > > a test anti-pattern. > > > > > Are you referring to something like: > > > > > > https://cs.chromium.org/chromium/src/net/quic/quic_connection_test.cc?sq=pack... > > > ? > > > > I would first point to > > > https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... > > as the guidance. > > > > In particular, > > > https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... > > and > > > https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... > > > > Particularly relevant is the documentation note, as per > > > https://github.com/google/googletest/blob/master/googletest/include/gtest/gte... > > > > Since you picked a rather large test, I'll point to a smaller test, such as > > > https://cs.chromium.org/chromium/src/net/cert/x509_certificate_unittest.cc?rc... > > > > > > > > You're right that the test tests consistency proof between all possible > > > combinations of trees (i.e. for each tree of size N, build trees of size 0 > .. > > > N-1 and check that consistency proof generated by the reference generator > > > verifies by the production code). > > > Is the example linked above the right way to break it down to small tests? > > > > The above examples may be simpler to evaluate the 'right' way > > Unfortunately it's not trivial to make value-parameterised tests when there are > two parameters, one of which is dependent on the other (i.e. we want all > permutations where 1 <= tree_size <= 128 and 1 <= snapshot <= tree_size). > Nevertheless, I've written an iterator that achieves this (see > https://codereview.chromium.org/2187043004). The code is more complex, and we > don't reduce the overall test duration this way, but each test case executes in > ~3ms now, rather than there being a single ~13s test case. That single test case > is now 8513 separate test cases. The overhead of that many extra test cases > appears to have increased the overall test duration to ~24s. Never mind, I came up with a relatively straightforward way of implementing this. It
On 2016/07/28 04:55:34, Rob Percival wrote: > On 2016/07/28 03:27:46, Rob Percival wrote: > > On 2016/07/26 19:06:02, Ryan Sleevi (slow) wrote: > > > On 2016/07/26 18:56:57, Eran Messeri wrote: > > > > Can you be explicit what's the second problem is? > > > > > > The computational overhead? The whole reason for adding the memoization > seems > > to > > > be predicated on we're adding more slow tests; that is, the memoization > > > encourages a test design that does a ton of work in a monolithic test, which > > is > > > a test anti-pattern. > > > > > > > Are you referring to something like: > > > > > > > > > > https://cs.chromium.org/chromium/src/net/quic/quic_connection_test.cc?sq=pack... > > > > ? > > > > > > I would first point to > > > > > > https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... > > > as the guidance. > > > > > > In particular, > > > > > > https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... > > > and > > > > > > https://github.com/google/googletest/blob/master/googletest/docs/AdvancedGuid... > > > > > > Particularly relevant is the documentation note, as per > > > > > > https://github.com/google/googletest/blob/master/googletest/include/gtest/gte... > > > > > > Since you picked a rather large test, I'll point to a smaller test, such as > > > > > > https://cs.chromium.org/chromium/src/net/cert/x509_certificate_unittest.cc?rc... > > > > > > > > > > > You're right that the test tests consistency proof between all possible > > > > combinations of trees (i.e. for each tree of size N, build trees of size 0 > > .. > > > > N-1 and check that consistency proof generated by the reference generator > > > > verifies by the production code). > > > > Is the example linked above the right way to break it down to small tests? > > > > > > The above examples may be simpler to evaluate the 'right' way > > > > Unfortunately it's not trivial to make value-parameterised tests when there > are > > two parameters, one of which is dependent on the other (i.e. we want all > > permutations where 1 <= tree_size <= 128 and 1 <= snapshot <= tree_size). > > Nevertheless, I've written an iterator that achieves this (see > > https://codereview.chromium.org/2187043004). The code is more complex, and we > > don't reduce the overall test duration this way, but each test case executes > in > > ~3ms now, rather than there being a single ~13s test case. That single test > case > > is now 8513 separate test cases. The overhead of that many extra test cases > > appears to have increased the overall test duration to ~24s. > > Never mind, I came up with a relatively straightforward way of implementing > this. > It ... still has the same performance overhead though.
Safe to close this out?
Description was changed from ========== Cache hashes in CTLogVerifier tests This reduces the duration of the long-running test case by ~50%. This is particularly valuable given that a similarly long-running test will shortly be added for testing audit proof verification. BUG=598406 ========== to ========== Cache hashes in CTLogVerifier tests This reduces the duration of the long-running test case by ~50%. This is particularly valuable given that a similarly long-running test will shortly be added for testing audit proof verification. BUG=598406 ==========
Message was sent while issue was closed.
On 2016/08/01 18:56:09, Ryan Sleevi (slow) wrote: > Safe to close this out? Done. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
