Reduce memory use of GetLevenshteinDistance() by almost 50%

components/ssl_errors/error_classification.cc

Index: components/ssl_errors/error_classification.cc
diff --git a/components/ssl_errors/error_classification.cc b/components/ssl_errors/error_classification.cc
index f55d754faab06869a23309177189c4418ca6c128..076fc6a1868e4fe94fe67d3e6125f3406dd4b0b6 100644
--- a/components/ssl_errors/error_classification.cc
+++ b/components/ssl_errors/error_classification.cc
@@ -67,37 +67,6 @@ void RecordSSLInterstitialCause(bool overridable, SSLInterstitialCause event) {
   }
 }
 
-// Returns the Levenshtein distance between |str1| and |str2|.
-// Which is the minimum number of single-character edits (i.e. insertions,
-// deletions or substitutions) required to change one word into the other.
-// https://en.wikipedia.org/wiki/Levenshtein_distance
-size_t GetLevenshteinDistance(const std::string& str1,
-                              const std::string& str2) {
-  if (str1 == str2)
-    return 0;
-  if (str1.size() == 0)
-    return str2.size();
-  if (str2.size() == 0)
-    return str1.size();
-  std::vector<size_t> kFirstRow(str2.size() + 1, 0);
-  std::vector<size_t> kSecondRow(str2.size() + 1, 0);
-
-  for (size_t i = 0; i < kFirstRow.size(); ++i)
-    kFirstRow[i] = i;
-  for (size_t i = 0; i < str1.size(); ++i) {
-    kSecondRow[0] = i + 1;
-    for (size_t j = 0; j < str2.size(); ++j) {
-      int cost = str1[i] == str2[j] ? 0 : 1;
-      kSecondRow[j + 1] =
-          std::min(std::min(kSecondRow[j] + 1, kFirstRow[j + 1] + 1),
-                   kFirstRow[j] + cost);
-    }
-    for (size_t j = 0; j < kFirstRow.size(); j++)
-      kFirstRow[j] = kSecondRow[j];
-  }
-  return kSecondRow[str2.size()];
-}
-
 std::vector<HostnameTokens> GetTokenizedDNSNames(
     const std::vector<std::string>& dns_names) {
   std::vector<HostnameTokens> dns_name_tokens;
@@ -149,6 +118,37 @@ base::LazyInstance<base::Time> g_testing_build_time = LAZY_INSTANCE_INITIALIZER;
 
 }  // namespace
 
+// Returns the Levenshtein distance between |str1| and |str2|.
+// Which is the minimum number of single-character edits (i.e. insertions,
+// deletions or substitutions) required to change one word into the other.
+// https://en.wikipedia.org/wiki/Levenshtein_distance
+size_t GetLevenshteinDistance(const std::string& str1,
+                              const std::string& str2) {
+  if (str1 == str2)
+    return 0;
+  if (str1.size() == 0)
+    return str2.size();
+  if (str2.size() == 0)
+    return str1.size();
+
+  std::vector<size_t> row(str2.size() + 1);
+  for (size_t i = 0; i < row.size(); ++i)
+    row[i] = i;
+
+  for (size_t i = 0; i < str1.size(); ++i) {
+    row[0] = i + 1;
+    size_t previous = i;
+    for (size_t j = 0; j < str2.size(); ++j) {
+      size_t old_row = row[j + 1];
+      int cost = str1[i] == str2[j] ? 0 : 1;
+      row[j + 1] = std::min(std::min(row[j], row[j + 1]) + 1, previous + cost);
+      previous = old_row;
+    }
+  }
+  return row[str2.size()];
+}
+
+
 void RecordUMAStatistics(bool overridable,
                          const base::Time& current_time,
                          const GURL& request_url,
@@ -388,11 +388,11 @@ bool IsCertLikelyFromMultiTenantHosting(const GURL& request_url,
   // considered as a shared certificate. Include the host name in the URL also
   // while comparing.
   dns_names.push_back(host_name);
-  static const size_t kMinimumEditDsitance = 5;
+  static const size_t kMinimumEditDistance = 5;
   for (size_t i = 0; i < dns_names_size; ++i) {
     for (size_t j = i + 1; j < dns_names_size; ++j) {
       size_t edit_distance = GetLevenshteinDistance(dns_names[i], dns_names[j]);
-      if (edit_distance < kMinimumEditDsitance)
+      if (edit_distance < kMinimumEditDistance)
         return false;
     }
   }