From c15df35204f77aff6dcc04754e1d1af76cf545bf Mon Sep 17 00:00:00 2001
From: "iposva@chromium.org"
 <iposva@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Thu, 2 Jul 2009 19:46:28 +0000
Subject: [PATCH] - Cache on backtracking stack in the irregexp interpreter for
 future use. Review URL: http://codereview.chromium.org/149131

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@2341 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/interpreter-irregexp.cc | 57 ++++++++++++++++++++++++++++++++-----
 1 file changed, 50 insertions(+), 7 deletions(-)

diff --git a/src/interpreter-irregexp.cc b/src/interpreter-irregexp.cc
index 6d616ab65..0a8ae8cce 100644
--- a/src/interpreter-irregexp.cc
+++ b/src/interpreter-irregexp.cc
@@ -142,6 +142,49 @@ static int32_t Load16Aligned(const byte* pc) {
 }
 
 
+// A simple abstraction over the backtracking stack used by the interpreter.
+// This backtracking stack does not grow automatically, but it ensures that the
+// the memory held by the stack is released or remembered in a cache if the
+// matching terminates.
+class BacktrackStack {
+ public:
+  explicit BacktrackStack() {
+    if (cache_ != NULL) {
+      // If the cache is not empty reuse the previously allocated stack.
+      data_ = cache_;
+      cache_ = NULL;
+    } else {
+      // Cache was empty. Allocate a new backtrack stack.
+      data_ = NewArray<int>(kBacktrackStackSize);
+    }
+  }
+
+  ~BacktrackStack() {
+    if (cache_ == NULL) {
+      // The cache is empty. Keep this backtrack stack around.
+      cache_ = data_;
+    } else {
+      // A backtrack stack was already cached, just release this one.
+      DeleteArray(data_);
+    }
+  }
+
+  int* data() const { return data_; }
+
+  int max_size() const { return kBacktrackStackSize; }
+
+ private:
+  static const int kBacktrackStackSize = 10000;
+
+  int* data_;
+  static int* cache_;
+
+  DISALLOW_COPY_AND_ASSIGN(BacktrackStack);
+};
+
+int* BacktrackStack::cache_ = NULL;
+
+
 template <typename Char>
 static bool RawMatch(const byte* code_base,
                      Vector<const Char> subject,
@@ -149,13 +192,13 @@ static bool RawMatch(const byte* code_base,
                      int current,
                      uint32_t current_char) {
   const byte* pc = code_base;
-  static const int kBacktrackStackSize = 10000;
-  // Use a SmartPointer here to ensure that the memory gets freed when the
-  // matching finishes.
-  SmartPointer<int> backtrack_stack(NewArray<int>(kBacktrackStackSize));
-  int* backtrack_stack_base = *backtrack_stack;
+  // BacktrackStack ensures that the memory allocated for the backtracking stack
+  // is returned to the system or cached if there is no stack being cached at
+  // the moment.
+  BacktrackStack backtrack_stack;
+  int* backtrack_stack_base = backtrack_stack.data();
   int* backtrack_sp = backtrack_stack_base;
-  int backtrack_stack_space = kBacktrackStackSize;
+  int backtrack_stack_space = backtrack_stack.max_size();
 #ifdef DEBUG
   if (FLAG_trace_regexp_bytecodes) {
     PrintF("\n\nStart bytecode interpreter\n\n");
@@ -210,7 +253,7 @@ static bool RawMatch(const byte* code_base,
         break;
       BYTECODE(SET_SP_TO_REGISTER)
         backtrack_sp = backtrack_stack_base + registers[insn >> BYTECODE_SHIFT];
-        backtrack_stack_space = kBacktrackStackSize -
+        backtrack_stack_space = backtrack_stack.max_size() -
                                 (backtrack_sp - backtrack_stack_base);
         pc += BC_SET_SP_TO_REGISTER_LENGTH;
         break;
-- 
2.34.1