Changeset 28164 in webkit

Timestamp:

Nov 29, 2007, 3:25:16 AM (17 years ago)

Author:

eric@webkit.org

Message:

2007-11-24 Eric Seidel <​eric@webkit.org>

Reviewed by Maciej.

Remove redundant match_call_count and move recursion check out of super-hot code path
SunSpider says this is at least an 8% speedup for regexp.

• pcre/pcre_exec.cpp: (MatchStack::MatchStack): (MatchStack::pushNewFrame): (MatchStack::popCurrentFrame): (MatchStack::popAllFrames): (match): (jsRegExpExecute):
• pcre/pcre_internal.h:

Location:

trunk/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• pcre/pcre_exec.cpp (modified) (10 diffs)
• pcre/pcre_internal.h (modified) (1 diff)

trunk/JavaScriptCore/ChangeLog

@@ -20 +20 @@
         (MatchStack::pushNewFrame):
         (match):
+
+2007-11-24  Eric Seidel  <eric@webkit.org>
+
+        Reviewed by Maciej.
+
+        Remove redundant match_call_count and move recursion check out of super-hot code path
+        SunSpider says this is at least an 8% speedup for regexp.
+
+        * pcre/pcre_exec.cpp:
+        (MatchStack::MatchStack):
+        (MatchStack::pushNewFrame):
+        (MatchStack::popCurrentFrame):
+        (MatchStack::popAllFrames):
+        (match):
+        (jsRegExpExecute):
+        * pcre/pcre_internal.h:
 
 2007-11-24  Eric Seidel  <eric@webkit.org>

trunk/JavaScriptCore/pcre/pcre_exec.cpp

@@ -125 +125 @@
 
 struct MatchData {
-  unsigned long int match_call_count;
   int*   offset_vector;         /* Offset vector */
   int    offset_end;            /* One past the end */
@@ -285 +284 @@
     stack.pushNewFrame((ra), (rb), RMATCH_WHERE(num)); \
     is_group_start = (rc);\
-    ++rdepth;\
+    if (stack.size >= MATCH_LIMIT_RECURSION) \
+        return matchError(JSRegExpErrorRecursionLimit, stack); \
     DPRINTF(("restarting from line %d\n", __LINE__));\
     goto RECURSE;\
 RRETURN_##num:\
     stack.popCurrentFrame(); \
-    --rdepth;\
     DPRINTF(("did a goto back to line %d\n", __LINE__));\
   }
@@ -330 +329 @@
         framesEnd = frames + sizeof(frames) / sizeof(frames[0]);
         currentFrame = frames;
+        size = 0;
     }
     
@@ -338 +338 @@
     MatchFrame* framesEnd;
     MatchFrame* currentFrame;
+    unsigned size;
     
     inline bool canUseStackBufferForNextFrame()
@@ -361 +362 @@
         newframe->args.eptrb = eptrb;
         newframe->returnLocation = returnLocation;
+        size++;
 
         currentFrame = newframe;
@@ -376 +378 @@
         if (!frameIsStackAllocated(oldFrame))
             delete oldFrame;
+        size--;
     }
 
-    void unrollAnyHeapAllocatedFrames()
+    void popAllFrames()
     {
-        while (!frameIsStackAllocated(currentFrame)) {
-            MatchFrame* oldFrame = currentFrame;
-            currentFrame = currentFrame->previousFrame;
-            delete oldFrame;
-        }
+        while (size)
+            popCurrentFrame();
     }
 };
@@ -390 +390 @@
 static int matchError(int errorCode, MatchStack& stack)
 {
-    stack.unrollAnyHeapAllocatedFrames();
+    stack.popAllFrames();
     return errorCode;
 }
@@ -418 +418 @@
     int c;
     
-    unsigned rdepth = 0;
-    
     bool cur_is_word;
     bool prev_is_word;
@@ -464 +462 @@
      complicated macro. It has to be used in one particular way. This shouldn't,
      however, impact performance when true recursion is being used. */
-    
-    /* First check that we haven't called match() too many times, or that we
-     haven't exceeded the recursive call limit. */
-    
-    if (md.match_call_count++ >= MATCH_LIMIT)
-        return matchError(JSRegExpErrorMatchLimit, stack);
-    if (rdepth >= MATCH_LIMIT_RECURSION)
-        return matchError(JSRegExpErrorRecursionLimit, stack);
     
     /* At the start of a bracketed group, add the current subject pointer to the
@@ -2266 +2256 @@
          if certain parts of the pattern were not used. */
         
-        match_block.match_call_count = 0;
-        
-        
         /* The code starts after the JSRegExp block and the capture name table. */
         const uschar* start_code = (const uschar*)(re + 1);

trunk/JavaScriptCore/pcre/pcre_internal.h

@@ -86 +86 @@
 #define LINK_SIZE   2
 
-/* The value of MATCH_LIMIT determines the default number of times the internal
-match() function can be called during a single execution of pcre_exec(). There
-is a runtime interface for setting a different limit. The limit exists in order
-to catch runaway regular expressions that take for ever to determine that they
-do not match. The default is set very large so that it does not accidentally
-catch legitimate cases. On systems that support it, "configure" can be used to
-override this default default. */
-
-#define MATCH_LIMIT 10000000
-
-/* The above limit applies to all calls of match(), whether or not they
-increase the recursion depth. In some environments it is desirable to limit the
-depth of recursive calls of match() more strictly, in order to restrict the
-maximum amount of stack (or heap, if NO_RECURSE is defined) that is used. The
-value of MATCH_LIMIT_RECURSION applies only to recursive calls of match(). To
-have any useful effect, it must be less than the value of MATCH_LIMIT. There is
-a runtime method for setting a different limit. On systems that support it,
-"configure" can be used to override this default default. */
-
-#define MATCH_LIMIT_RECURSION MATCH_LIMIT
+/* The below limit restricts the number of recursive match calls in order to
+limit the maximum amount of stack (or heap, if NO_RECURSE is defined) that is used. The
+value of MATCH_LIMIT_RECURSION applies only to recursive calls of match(). */
+
+#define MATCH_LIMIT_RECURSION 10000000
 
 #define _pcre_default_tables kjs_pcre_default_tables