Switch regexp strategy for regexps that are just plain

src/jsregexp.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 90 matching lines @@
   Factory* factory = isolate->factory();
   Handle<FixedArray> elements = factory->NewFixedArray(2);
   elements->set(0, *pattern);
   elements->set(1, *error_text);
   Handle<JSArray> array = factory->NewJSArrayWithElements(elements);
   Handle<Object> regexp_err = factory->NewSyntaxError(message, array);
   isolate->Throw(*regexp_err);
 }
 
 
+// More makes code generation slower, less makes V8 benchmark score lower.
+const int kMaxLookaheadForBoyerMoore = 8;
+// In a 3-character pattern you can maximally step forwards 3 characters
+// at a time, which is not always enough to pay for the extra logic.
+const int kPatternTooShortForBoyerMoore = 2;
+
+
+// Identifies the sort of regexps where the regexp engine is faster
+// than the code used for atom matches.
+static bool HasFewDifferentCharacters(Handle<String> pattern) {
+  int length = Min(kMaxLookaheadForBoyerMoore, pattern->length());
+  if (length <= kPatternTooShortForBoyerMoore) return false;
+  const int kMod = 128;
+  bool character_found[kMod];
+  int different = 0;
+  memset(&character_found[0], 0, sizeof(character_found));
+  for (int i = 0; i < length; i++) {
+    int ch = (pattern->Get(i) & (kMod - 1));
+    if (!character_found[ch]) {
+      character_found[ch] = true;
+      different++;
+      if (different * 3 > length) return false;

[ulan, 2012/04/03 11:43:13]

A comment explaining '3' would be helpful.

+    }
+  }
+  return true;
+}
+
+
 // Generic RegExp methods. Dispatches to implementation specific methods.
 
 
 Handle<Object> RegExpImpl::Compile(Handle<JSRegExp> re,
                                    Handle<String> pattern,
                                    Handle<String> flag_str) {
   Isolate* isolate = re->GetIsolate();
   JSRegExp::Flags flags = RegExpFlagsFromString(flag_str);
   CompilationCache* compilation_cache = isolate->compilation_cache();
   Handle<FixedArray> cached = compilation_cache->LookupRegExp(pattern, flags);
@@ skipping 13 matching lines @@
   if (!RegExpParser::ParseRegExp(&reader, flags.is_multiline(),
                                  &parse_result)) {
     // Throw an exception if we fail to parse the pattern.
     ThrowRegExpException(re,
                          pattern,
                          parse_result.error,
                          "malformed_regexp");
     return Handle<Object>::null();
   }
 
-  if (parse_result.simple && !flags.is_ignore_case()) {
+  bool has_been_compiled = false;
+
+  if (parse_result.simple &&
+      !flags.is_ignore_case() &&
+      !HasFewDifferentCharacters(pattern)) {
     // Parse-tree is a single atom that is equal to the pattern.
     AtomCompile(re, pattern, flags, pattern);
+    has_been_compiled = true;
   } else if (parse_result.tree->IsAtom() &&
       !flags.is_ignore_case() &&
       parse_result.capture_count == 0) {
     RegExpAtom* atom = parse_result.tree->AsAtom();
     Vector<const uc16> atom_pattern = atom->data();
     Handle<String> atom_string =
         isolate->factory()->NewStringFromTwoByte(atom_pattern);
-    AtomCompile(re, pattern, flags, atom_string);
-  } else {
+    if (!HasFewDifferentCharacters(atom_string)) {
+      AtomCompile(re, pattern, flags, atom_string);
+      has_been_compiled = true;
+    }
+  }
+  if (!has_been_compiled) {
     IrregexpInitialize(re, pattern, flags, parse_result.capture_count);
   }
   ASSERT(re->data()->IsFixedArray());
   // Compilation succeeded so the data is set on the regexp
   // and we can store it in the cache.
   Handle<FixedArray> data(FixedArray::cast(re->data()));
   compilation_cache->PutRegExp(pattern, flags, data);
 
   return re;
 }
@@ skipping 3256 matching lines @@
   masm->Bind(&again);
   masm->LoadCurrentCharacter(max_lookahead, &cont, true);
   masm->CheckBitInTable(boolean_skip_table, &cont);
   masm->AdvanceCurrentPosition(skip_distance);
   masm->GoTo(&again);
   masm->Bind(&cont);
 
   return true;
 }
 
+
 /* Code generation for choice nodes.
  *
  * We generate quick checks that do a mask and compare to eliminate a
  * choice.  If the quick check succeeds then it jumps to the continuation to
  * do slow checks and check subsequent nodes.  If it fails (the common case)
  * it falls through to the next choice.
  *
  * Here is the desired flow graph.  Nodes directly below each other imply
  * fallthrough.  Alternatives 1 and 2 have quick checks.  Alternative
  * 3 doesn't have a quick check so we have to call the slow check.
@@ skipping 58 matching lines @@
  *        |   F/         |
  *        |   /          |
  *        |  R           |
  *        | /            |
  *   F    VL             |
  * <------U              |
  * back   |S             |
  *        \______________/
  */
 
-
 void ChoiceNode::Emit(RegExpCompiler* compiler, Trace* trace) {
   RegExpMacroAssembler* macro_assembler = compiler->macro_assembler();
   int choice_count = alternatives_->length();
 #ifdef DEBUG
   for (int i = 0; i < choice_count - 1; i++) {
     GuardedAlternative alternative = alternatives_->at(i);
     ZoneList<Guard*>* guards = alternative.guards();
     int guard_count = (guards == NULL) ? 0 : guards->length();
     for (int j = 0; j < guard_count; j++) {
       ASSERT(!trace->mentions_reg(guards->at(j)->reg()));
@@ skipping 50 matching lines @@
   macro_assembler->Bind(&second_choice);
 
   int first_normal_choice = greedy_loop ? 1 : 0;
 
   bool not_at_start = current_trace->at_start() == Trace::FALSE;
   const int kEatsAtLeastNotYetInitialized = -1;
   int eats_at_least = kEatsAtLeastNotYetInitialized;
 
   bool skip_was_emitted = false;
 
-  // More makes code generation slower, less makes V8 benchmark score lower.
-  const int kMaxLookaheadForBoyerMoore = 8;
-
   if (!greedy_loop && choice_count == 2) {
     GuardedAlternative alt1 = alternatives_->at(1);
     if (alt1.guards() == NULL || alt1.guards()->length() == 0) {
       RegExpNode* eats_anything_node = alt1.node();
       if (eats_anything_node->GetSuccessorOfOmnivorousTextNode(compiler) ==
           this) {
         // At this point we know that we are at a non-greedy loop that will eat
         // any character one at a time.  Any non-anchored regexp has such a
         // loop prepended to it in order to find where it starts.  We look for
         // a pattern of the form ...abc... where we can look 6 characters ahead
@@ skipping 2503 matching lines @@
   }
 
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal