Optimize phishing page term feature extraction.

chrome/renderer/safe_browsing/phishing_term_feature_extractor.cc

 // Copyright (c) 2011 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 "chrome/renderer/safe_browsing/phishing_term_feature_extractor.h"
 
 #include <list>
 #include <map>
 
 #include "base/compiler_specific.h"
@@ skipping 17 matching lines @@
 
 // Experimenting shows that we get a reasonable gain in performance by
 // increasing this up to around 10, but there's not much benefit in
 // increasing it past that.
 const int PhishingTermFeatureExtractor::kClockCheckGranularity = 10;
 
 // This should be longer than we expect feature extraction to take on any
 // actual phishing page.
 const int PhishingTermFeatureExtractor::kMaxTotalTimeMs = 500;
 
+// The maximum size of the negative word cache.
+const int PhishingTermFeatureExtractor::kMaxNegativeWordCacheSize = 1000;
+
 // All of the state pertaining to the current feature extraction.
 struct PhishingTermFeatureExtractor::ExtractionState {
   // Stores up to max_words_per_ngram_ previous words separated by spaces.
   std::string previous_words;
 
   // Stores the sizes of the words in previous_words.  Note: the size includes
   // the space after each word.  In other words, the sum of all sizes in this
   // list is equal to the length of previous_words.
   std::list<size_t> previous_word_sizes;
 
@@ skipping 38 matching lines @@
 };
 
 PhishingTermFeatureExtractor::PhishingTermFeatureExtractor(
     const base::hash_set<std::string>* page_term_hashes,
     const base::hash_set<std::string>* page_word_hashes,
     size_t max_words_per_term,
     FeatureExtractorClock* clock)
     : page_term_hashes_(page_term_hashes),
       page_word_hashes_(page_word_hashes),
       max_words_per_term_(max_words_per_term),
+      negative_word_cache_(kMaxNegativeWordCacheSize),
       clock_(clock),
       ALLOW_THIS_IN_INITIALIZER_LIST(method_factory_(this)) {
   Clear();
 }
 
 PhishingTermFeatureExtractor::~PhishingTermFeatureExtractor() {
   // The RenderView should have called CancelPendingExtraction() before
   // we are destroyed.
   CheckNoPendingExtraction();
 }
@@ skipping 46 matching lines @@
       return;
     }
     state_->position_initialized = true;
   }
 
   int num_words = 0;
   for (int next = ubrk_next(state_->iterator);
        next != UBRK_DONE; next = ubrk_next(state_->iterator)) {
     if (ubrk_getRuleStatus(state_->iterator) != UBRK_WORD_NONE) {
       // next is now positioned at the end of a word.
-      HandleWord(string16(*page_text_, state_->position,
-                          next - state_->position));
+      HandleWord(base::StringPiece16(page_text_->data() + state_->position,
+                                     next - state_->position));
       ++num_words;
     }
     state_->position = next;
 
     if (num_words >= kClockCheckGranularity) {
       num_words = 0;
       base::TimeTicks now = clock_->Now();
       if (now - state_->start_time >=
           base::TimeDelta::FromMilliseconds(kMaxTotalTimeMs)) {
         DLOG(ERROR) << "Feature extraction took too long, giving up";
@@ skipping 15 matching lines @@
                             chunk_elapsed);
         MessageLoop::current()->PostTask(
             FROM_HERE,
             method_factory_.NewRunnableMethod(
                 &PhishingTermFeatureExtractor::ExtractFeaturesWithTimeout));
         return;
       }
       // Otherwise, continue.
     }
   }
+  // We need to clear the cache because the data that it depends on (page_text_)
+  // is going away.
+  negative_word_cache_.Clear();
   RunCallback(true);
 }
 
-void PhishingTermFeatureExtractor::HandleWord(const string16& word) {
+void PhishingTermFeatureExtractor::HandleWord(
+    const base::StringPiece16& word) {
+  // Quickest out if we have seen this word before and know that it's not
+  // part of any term. This avoids the SHA256, lowercasing, and UTF conversion,
+  // all of which are relatively expensive.
+  if (negative_word_cache_.Get(word) != negative_word_cache_.end()) {
+    return;
+  }
+
   std::string word_lower = UTF16ToUTF8(base::i18n::ToLower(word));
   std::string word_hash = crypto::SHA256HashString(word_lower);
 
   // Quick out if the word is not part of any term, which is the common case.
   if (page_word_hashes_->find(word_hash) == page_word_hashes_->end()) {
     // Word doesn't exist in our terms so we can clear the n-gram state.
     state_->previous_words.clear();
     state_->previous_word_sizes.clear();
+    // Insert into negative cache so that we don't try this again.
+    negative_word_cache_.Put(word, true);
     return;
   }
 
   // Find all of the n-grams that we need to check and compute their hashes.
   // We already have the hash for word_lower, so we don't compute that again.
   std::map<std::string /* hash */, std::string /* plaintext */>
       hashes_to_check;
   hashes_to_check[word_hash] = word_lower;
 
   // Combine the new word with the previous words to find additional n-grams.
   // Note that we don't yet add the new word length to previous_word_sizes,
   // since we don't want to compute the hash for the word by itself again.
   //
-  // TODO(bryner): Use UMA stats to determine whether this is too slow.
-  // If it is, there are a couple of cases that we could optimize:
-  //  - We could cache plaintext words that are not in page_word_hashes_, so
-  //    that we can avoid hashing these again.
-  //  - We could include positional information about words in the n-grams,
-  //    rather than just a list of all of the words.  For example, we could
-  //    change the term format so that each word is hashed separately, or
-  //    we could add extra data to the word list to indicate the position
-  //    at which the word appears in an n-gram, and skip checking the word if
-  //    it's not at that position.
   state_->previous_words.append(word_lower);
   std::string current_term = state_->previous_words;
   for (std::list<size_t>::iterator it = state_->previous_word_sizes.begin();
        it != state_->previous_word_sizes.end(); ++it) {
     hashes_to_check[crypto::SHA256HashString(current_term)] = current_term;
     current_term.erase(0, *it);
   }
 
   // Add features for any hashes that match page_term_hashes_.
   for (std::map<std::string, std::string>::iterator it =
@@ skipping 43 matching lines @@
 }
 
 void PhishingTermFeatureExtractor::Clear() {
   page_text_ = NULL;
   features_ = NULL;
   done_callback_.reset(NULL);
   state_.reset(NULL);
 }
 
 }  // namespace safe_browsing