Cache hashes in CTLogVerifier tests

net/cert/ct_log_verifier_unittest.cc

Index: net/cert/ct_log_verifier_unittest.cc
diff --git a/net/cert/ct_log_verifier_unittest.cc b/net/cert/ct_log_verifier_unittest.cc
index 754d3e39073c50f89c3c83b1d3d623a7ef782659..a90ce08b912bca5d309073026193e61966d66356 100644
--- a/net/cert/ct_log_verifier_unittest.cc
+++ b/net/cert/ct_log_verifier_unittest.cc
@@ -6,8 +6,10 @@
 
 #include <stdint.h>
 
+#include <map>
 #include <memory>
 #include <string>
+#include <utility>
 
 #include "base/strings/string_number_conversions.h"
 #include "base/time/time.h"
@@ -24,6 +26,11 @@ 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) {
@@ -426,16 +433,34 @@ class TreeHasher {
 // 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;
+  }
+
+  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);
+
+    hash = ct::internal::HashNodes(
+        ReferenceMerkleTreeHash(&inputs[0], split),
+        ReferenceMerkleTreeHash(&inputs[split], input_size - split));
+  }
 
-  const uint64_t split = CalculateNearestPowerOfTwo(input_size);
+  if (kIsHashCacheEnabled)
+    cache[std::make_pair(inputs, input_size)] = hash;
 
-  return ct::internal::HashNodes(
-      ReferenceMerkleTreeHash(&inputs[0], split),
-      ReferenceMerkleTreeHash(&inputs[split], input_size - split));
+  return hash;
 }
 
 // Reference implementation of snapshot consistency. Returns a