Cache hashes in CTLogVerifier tests

net/cert/ct_log_verifier_unittest.cc

 // Copyright 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/cert/ct_log_verifier.h"
 
 #include <stdint.h>
 
+#include <map>
 #include <memory>
 #include <string>
+#include <utility>
 
 #include "base/strings/string_number_conversions.h"
 #include "base/time/time.h"
 #include "crypto/secure_hash.h"
 #include "net/base/hash_value.h"
 #include "net/cert/ct_log_verifier_util.h"
 #include "net/cert/merkle_consistency_proof.h"
 #include "net/cert/signed_certificate_timestamp.h"
 #include "net/cert/signed_tree_head.h"
 #include "net/test/ct_test_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace net {
 
 namespace {
 
+// Enables the node hash cache used to accelerate some of the tests.
+// The cache reduces the duration of some tests by at least 50%, in exchange for
+// significantly higher memory usage.

[Eran Messeri, 2016/07/26 15:45:37]

Can you say how much or point to a calculation later in the file?

+const bool kIsHashCacheEnabled = true;
+
 // Calculate the power of two nearest to, but less than, |n|.
 // |n| must be at least 2.
 uint64_t CalculateNearestPowerOfTwo(uint64_t n) {
   DCHECK_GT(n, 1u);
 
   uint64_t ret = UINT64_C(1) << 63;
   while (ret >= n)
     ret >>= 1;
 
   return ret;
@@ skipping 382 matching lines @@
 
     return std::string(reinterpret_cast<const char*>(sha256.data),
                        sizeof(sha256.data));
   }
 };
 
 // Reference implementation of Merkle hash, for cross-checking.
 // Recursively calculates the hash of the root given the leaf data
 // specified in |inputs|.
 std::string ReferenceMerkleTreeHash(std::string* inputs, uint64_t input_size) {
-  if (!input_size)
-    return TreeHasher::HashEmpty();
-  if (input_size == 1)
-    return TreeHasher::HashLeaf(inputs[0]);
+  // Memoize function - this requires 34 bytes of memory per unique pair of
+  // |inputs| and |input_size|, plus std::map and std::string overhead.
+  // This results in a ~50% reduction in time required to run the
+  // *FromReferenceGenerator tests.
+  static std::map<std::pair<std::string*, uint64_t>, std::string> cache;

[Eran Messeri, 2016/07/26 15:45:37]

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.

+  if (kIsHashCacheEnabled) {
+    auto iter = cache.find(std::make_pair(inputs, input_size));
+    if (iter != cache.end())
+      return iter->second;
+  }
 
-  const uint64_t split = CalculateNearestPowerOfTwo(input_size);
+  std::string hash;
+  if (input_size == 0) {
+    hash = TreeHasher::HashEmpty();
+  } else if (input_size == 1) {
+    hash = TreeHasher::HashLeaf(inputs[0]);
+  } else {
+    const uint64_t split = CalculateNearestPowerOfTwo(input_size);
 
-  return ct::internal::HashNodes(
-      ReferenceMerkleTreeHash(&inputs[0], split),
-      ReferenceMerkleTreeHash(&inputs[split], input_size - split));
+    hash = ct::internal::HashNodes(
+        ReferenceMerkleTreeHash(&inputs[0], split),
+        ReferenceMerkleTreeHash(&inputs[split], input_size - split));
+  }
+
+  if (kIsHashCacheEnabled)
+    cache[std::make_pair(inputs, input_size)] = hash;
+
+  return hash;
 }
 
 // Reference implementation of snapshot consistency. Returns a
 // consistency proof between two snapshots of the tree designated
 // by |inputs|.
 // Call with have_root1 = true.
 std::vector<std::string> ReferenceSnapshotConsistency(std::string* inputs,
                                                       uint64_t snapshot2,
                                                       uint64_t snapshot1,
                                                       bool have_root1) {
@@ skipping 61 matching lines @@
           ReferenceSnapshotConsistency(data.data(), tree_size, snapshot, true);
       root1 = ReferenceMerkleTreeHash(data.data(), snapshot);
       VerifierConsistencyCheck(snapshot, tree_size, root1, root2, proof);
     }
   }
 }
 
 }  // namespace
 
 }  // namespace net