Optimizing HQP using vectors manually. This is just a CL to be able

components/omnibox/browser/url_index_private_data.cc

 // Copyright (c) 2012 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 "components/omnibox/browser/url_index_private_data.h"
 
 #include <stdint.h>
 
 #include <functional>
 #include <iterator>
@@ skipping 504 matching lines @@
   word_id_history_map_.clear();
   history_id_word_map_.clear();
   history_info_map_.clear();
   word_starts_map_.clear();
 }
 
 URLIndexPrivateData::~URLIndexPrivateData() {}
 
 HistoryIDSet URLIndexPrivateData::HistoryIDSetFromWords(
     const String16Vector& unsorted_words) {
+  using HistoryIDMoveIterator = std::move_iterator<HistoryIDVector::iterator>;
   // Break the terms down into individual terms (words), get the candidate
   // set for each term, and intersect each to get a final candidate list.
   // Note that a single 'term' from the user's perspective might be
   // a string like "http://www.somewebsite.com" which, from our perspective,
   // is four words: 'http', 'www', 'somewebsite', and 'com'.
-  HistoryIDSet history_id_set;
+  HistoryIDVector history_id_set;
   String16Vector words(unsorted_words);
   // Sort the words into the longest first as such are likely to narrow down
   // the results quicker. Also, single character words are the most expensive
   // to process so save them for last.
   std::sort(words.begin(), words.end(), LengthGreater);
   for (String16Vector::iterator iter = words.begin(); iter != words.end();
        ++iter) {
     base::string16 uni_word = *iter;
-    HistoryIDSet term_history_set = HistoryIDsForTerm(uni_word);
+    HistoryIDVector term_history_set = HistoryIDsForTerm(uni_word);
     if (term_history_set.empty()) {
       history_id_set.clear();
       break;
     }
     if (iter == words.begin()) {
-      history_id_set.swap(term_history_set);
+      history_id_set = std::move(term_history_set);
     } else {
-      HistoryIDSet new_history_id_set = base::STLSetIntersection<HistoryIDSet>(
-          history_id_set, term_history_set);
-      history_id_set.swap(new_history_id_set);
+      history_id_set.erase(
+          std::set_intersection(HistoryIDMoveIterator(term_history_set.begin()),
+                                HistoryIDMoveIterator(term_history_set.end()),
+                                history_id_set.begin(), history_id_set.end(),
+                                history_id_set.begin()),
+          history_id_set.end());
     }
   }
-  return history_id_set;
+  return HistoryIDSet(history_id_set.begin(), history_id_set.end());
 }
 
-HistoryIDSet URLIndexPrivateData::HistoryIDsForTerm(
+HistoryIDVector URLIndexPrivateData::HistoryIDsForTerm(
     const base::string16& term) {
   if (term.empty())
-    return HistoryIDSet();
+    return {};
 
   // TODO(mrossetti): Consider optimizing for very common terms such as
   // 'http[s]', 'www', 'com', etc. Or collect the top 100 more frequently
   // occuring words in the user's searches.
 
   size_t term_length = term.length();
-  WordIDSet word_id_set;
+  WordIDVector word_id_set;
   if (term_length > 1) {
     // See if this term or a prefix thereof is present in the cache.
     base::string16 term_lower = base::i18n::ToLower(term);
     SearchTermCacheMap::iterator best_prefix(search_term_cache_.end());
     for (SearchTermCacheMap::iterator cache_iter = search_term_cache_.begin();
          cache_iter != search_term_cache_.end(); ++cache_iter) {
       if (base::StartsWith(term_lower,
                            base::i18n::ToLower(cache_iter->first),
                            base::CompareCase::SENSITIVE) &&
           (best_prefix == search_term_cache_.end() ||
@@ skipping 12 matching lines @@
       if (prefix_length == term_length) {
         best_prefix->second.used_ = true;
         return best_prefix->second.history_id_set_;
       }
 
       // Otherwise we have a handy starting point.
       // If there are no history results for this prefix then we can bail early
       // as there will be no history results for the full term.
       if (best_prefix->second.history_id_set_.empty()) {
         search_term_cache_[term] = SearchTermCacheItem();
-        return HistoryIDSet();
+        return {};
       }
       word_id_set = best_prefix->second.word_id_set_;
       prefix_chars = Char16SetFromString16(best_prefix->first);
       leftovers = term.substr(prefix_length);
     }
 
     // Filter for each remaining, unique character in the term.
     Char16Set leftover_chars = Char16SetFromString16(leftovers);
     Char16Set unique_chars =
         base::STLSetDifference<Char16Set>(leftover_chars, prefix_chars);
 
     // Reduce the word set with any leftover, unprocessed characters.
     if (!unique_chars.empty()) {
-      WordIDSet leftover_set(WordIDSetForTermChars(unique_chars));
+      WordIDVector leftover_set(WordIDSetForTermChars(unique_chars));
       // We might come up empty on the leftovers.
       if (leftover_set.empty()) {
         search_term_cache_[term] = SearchTermCacheItem();
-        return HistoryIDSet();
+        return {};
       }
       // Or there may not have been a prefix from which to start.
       if (prefix_chars.empty()) {
         word_id_set.swap(leftover_set);
       } else {
-        WordIDSet new_word_id_set = base::STLSetIntersection<WordIDSet>(
-            word_id_set, leftover_set);
-        word_id_set.swap(new_word_id_set);
+        word_id_set.erase(
+            std::set_intersection(word_id_set.begin(), word_id_set.end(),
+                                  leftover_set.begin(), leftover_set.end(),
+                                  word_id_set.begin()),
+            word_id_set.end());
       }
     }
 
     // We must filter the word list because the resulting word set surely
     // contains words which do not have the search term as a proper subset.
-    for (WordIDSet::iterator word_set_iter = word_id_set.begin();
-         word_set_iter != word_id_set.end(); ) {
-      if (word_list_[*word_set_iter].find(term) == base::string16::npos)
-        word_id_set.erase(word_set_iter++);
-      else
-        ++word_set_iter;
-    }
+    word_id_set.erase(std::remove_if(word_id_set.begin(), word_id_set.end(),
+                                     [this, &term](const WordID& id) {
+                                       return word_list_[id].find(term) ==
+                                              base::string16::npos;
+                                     }),
+                      word_id_set.end());
   } else {
     word_id_set = WordIDSetForTermChars(Char16SetFromString16(term));
   }
 
   // If any words resulted then we can compose a set of history IDs by unioning
   // the sets from each word.
-  HistoryIDSet history_id_set;
-  if (!word_id_set.empty()) {
-    for (WordIDSet::iterator word_id_iter = word_id_set.begin();
-         word_id_iter != word_id_set.end(); ++word_id_iter) {
-      WordID word_id = *word_id_iter;
-      WordIDHistoryMap::iterator word_iter = word_id_history_map_.find(word_id);
-      if (word_iter != word_id_history_map_.end()) {
-        HistoryIDSet& word_history_id_set(word_iter->second);
-        history_id_set.insert(word_history_id_set.begin(),
-                              word_history_id_set.end());
-      }
+  HistoryIDVector history_id_set;
+
+  for (const WordID word_id : word_id_set) {
+    WordIDHistoryMap::iterator word_iter = word_id_history_map_.find(word_id);
+    if (word_iter != word_id_history_map_.end()) {
+      HistoryIDSet& word_history_id_set(word_iter->second);
+      history_id_set.insert(history_id_set.end(), word_history_id_set.begin(),
+                            word_history_id_set.end());
     }
   }
 
+  std::sort(history_id_set.begin(), history_id_set.end());
+  history_id_set.erase(
+      std::unique(history_id_set.begin(), history_id_set.end()),
+      history_id_set.end());
+
   // Record a new cache entry for this word if the term is longer than
   // a single character.
   if (term_length > 1)
     search_term_cache_[term] = SearchTermCacheItem(word_id_set, history_id_set);
 
   return history_id_set;
 }
 
-WordIDSet URLIndexPrivateData::WordIDSetForTermChars(
+WordIDVector URLIndexPrivateData::WordIDSetForTermChars(
     const Char16Set& term_chars) {
-  WordIDSet word_id_set;
+  WordIDVector word_id_set;
   for (Char16Set::const_iterator c_iter = term_chars.begin();
        c_iter != term_chars.end(); ++c_iter) {
     CharWordIDMap::iterator char_iter = char_word_map_.find(*c_iter);
     if (char_iter == char_word_map_.end()) {
       // A character was not found so there are no matching results: bail.
       word_id_set.clear();
       break;
     }
     WordIDSet& char_word_id_set(char_iter->second);
     // It is possible for there to no longer be any words associated with
     // a particular character. Give up in that case.
     if (char_word_id_set.empty()) {
       word_id_set.clear();
       break;
     }
 
     if (c_iter == term_chars.begin()) {
       // First character results becomes base set of results.
-      word_id_set = char_word_id_set;
+      word_id_set = {char_word_id_set.begin(), char_word_id_set.end()};
     } else {
-      // Subsequent character results get intersected in.
-      WordIDSet new_word_id_set = base::STLSetIntersection<WordIDSet>(
-          word_id_set, char_word_id_set);
-      word_id_set.swap(new_word_id_set);
+      word_id_set.erase(
+          std::set_intersection(word_id_set.begin(), word_id_set.end(),
+                                char_word_id_set.begin(),
+                                char_word_id_set.end(), word_id_set.begin()),
+          word_id_set.end());
     }
   }
   return word_id_set;
 }
 
 bool URLIndexPrivateData::IndexRow(
     history::HistoryDatabase* history_db,
     history::HistoryService* history_service,
     const history::URLRow& row,
     const std::set<std::string>& scheme_whitelist,
@@ skipping 546 matching lines @@
 bool URLIndexPrivateData::URLSchemeIsWhitelisted(
     const GURL& gurl,
     const std::set<std::string>& whitelist) {
   return whitelist.find(gurl.scheme()) != whitelist.end();
 }
 
 
 // SearchTermCacheItem ---------------------------------------------------------
 
 URLIndexPrivateData::SearchTermCacheItem::SearchTermCacheItem(
-    const WordIDSet& word_id_set,
-    const HistoryIDSet& history_id_set)
-    : word_id_set_(word_id_set), history_id_set_(history_id_set), used_(true) {
-}
+    WordIDVector word_id_set,
+    HistoryIDVector history_id_set)
+    : word_id_set_(std::move(word_id_set)),
+      history_id_set_(std::move(history_id_set)),
+      used_(true) {}
 
 URLIndexPrivateData::SearchTermCacheItem::SearchTermCacheItem() : used_(true) {
 }
 
 URLIndexPrivateData::SearchTermCacheItem::SearchTermCacheItem(
     const SearchTermCacheItem& other) = default;
 
 URLIndexPrivateData::SearchTermCacheItem::~SearchTermCacheItem() {
 }
 
@@ skipping 82 matching lines @@
   // First cut: typed count, visit count, recency.
   // TODO(mrossetti): This is too simplistic. Consider an approach which ranks
   // recently visited (within the last 12/24 hours) as highly important. Get
   // input from mpearson.
   if (r1.typed_count() != r2.typed_count())
     return (r1.typed_count() > r2.typed_count());
   if (r1.visit_count() != r2.visit_count())
     return (r1.visit_count() > r2.visit_count());
   return (r1.last_visit() > r2.last_visit());
 }