Optimize StringImpl::find when searching for patterns with length > 1

third_party/WebKit/Source/wtf/text/StringImpl.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2001 Dirk Mueller ( mueller@kde.org )
  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2013 Apple Inc. All rights reserved.
  * Copyright (C) 2006 Andrew Wellington (proton@wiretapped.net)
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
@@ skipping 1228 matching lines @@
 
 template <typename SearchCharacterType, typename MatchCharacterType>
 ALWAYS_INLINE static size_t findInternal(const SearchCharacterType* searchCharacters, const MatchCharacterType* matchCharacters, unsigned index, unsigned searchLength, unsigned matchLength)
 {
     // Optimization: keep a running hash of the strings,
     // only call equal() if the hashes match.
 
     // delta is the number of additional times to test; delta == 0 means test only once.
     unsigned delta = searchLength - matchLength;
 
+    // Find on a single character is very fast, so first do that to figure out
+    // where to start.
+    size_t start = WTF::find(searchCharacters, searchLength, matchCharacters[0]);
+    if (start == kNotFound || start > delta)
+        return kNotFound;
+
+    // TODO(esprehn): Consider using Boyer-Moore-Horspool or a hybrid approach
+    // like v8/src/string-search.h, also investigate the badness factor used
+    // by v8 where they use single char find() repeatedly until they think
+    // it's too costly then switch to Boyer-Moore-Horspool.
+
     unsigned searchHash = 0;
     unsigned matchHash = 0;
 
     for (unsigned i = 0; i < matchLength; ++i) {
-        searchHash += searchCharacters[i];
+        searchHash += searchCharacters[start + i];
         matchHash += matchCharacters[i];
     }
 
-    unsigned i = 0;
+    unsigned i = start;
     // keep looping until we match
     while (searchHash != matchHash || !equal(searchCharacters + i, matchCharacters, matchLength)) {
         if (i == delta)
             return kNotFound;
         searchHash += searchCharacters[i + matchLength];
         searchHash -= searchCharacters[i];
         ++i;
     }
     return index + i;
 }
@@ skipping 1090 matching lines @@
         } else if (localeIdMatchesLang(localeIdentifier, "lt")) {
             // TODO(rob.buis) implement upper-casing rules for lt
             // like in StringImpl::upper(locale).
         }
     }
 
     return toUpper(c);
 }
 
 } // namespace WTF