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 75 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_(1000 /* max_size */),

[Brian Ryner, 2011/08/08 22:08:00]

Maybe make this a class constant, like the other knobs that we have for this
extractor?

[Garrett Casto, 2011/08/08 23:19:51]

Done.

       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();

[Brian Ryner, 2011/08/08 22:08:00]

Hm... I could imagine there being some benefit to maintaining the cache across
pages, but perhaps it's not as big as the win from using StringPiece and
avoiding the string copies on lookup.  We could have it both ways, I guess, if
we kept separate internal storage for the strings that are in
negative_word_cache_, but maybe not worth it.

[Garrett Casto, 2011/08/08 23:19:51]

So I thought about this as well. It's rather hard to test because we don't know
what exactly people's browsing history is going to be like. I did do a bunch of
iterations in row at one point before I switched to using StringPiece16, and the
difference between the first task and subsequent ones was rather small, and
that's basically the optimal situation. Admittedly I didn't write down any
numbers, but I think that using StringPiece16 is better. If this comes up again
I can look into it.

   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