LiveEdit: Optimize compare by stripping common suffix and prefix.

src/liveedit.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 48 matching lines @@
   USE(no_failure);
 }
 
 // A simple implementation of dynamic programming algorithm. It solves
 // the problem of finding the difference of 2 arrays. It uses a table of results
 // of subproblems. Each cell contains a number together with 2-bit flag
 // that helps building the chunk list.
 class Differencer {
  public:
   explicit Differencer(Comparator::Input* input)
-      : input_(input), len1_(input->getLength1()), len2_(input->getLength2()) {
+      : input_(input), len1_(input->GetLength1()), len2_(input->GetLength2()) {
     buffer_ = NewArray<int>(len1_ * len2_);
   }
   ~Differencer() {
     DeleteArray(buffer_);
   }
 
   void Initialize() {
     int array_size = len1_ * len2_;
     for (int i = 0; i < array_size; i++) {
       buffer_[i] = kEmptyCellValue;
@@ skipping 64 matching lines @@
 
   // Computes result for a subtask and optionally caches it in the buffer table.
   // All results values are shifted to make space for flags in the lower bits.
   int CompareUpToTail(int pos1, int pos2) {
     if (pos1 < len1_) {
       if (pos2 < len2_) {
         int cached_res = get_value4(pos1, pos2);
         if (cached_res == kEmptyCellValue) {
           Direction dir;
           int res;
-          if (input_->equals(pos1, pos2)) {
+          if (input_->Equals(pos1, pos2)) {
             res = CompareUpToTail(pos1 + 1, pos2 + 1);
             dir = EQ;
           } else {
             int res1 = CompareUpToTail(pos1 + 1, pos2) +
                 (1 << kDirectionSizeBits);
             int res2 = CompareUpToTail(pos1, pos2 + 1) +
                 (1 << kDirectionSizeBits);
             if (res1 == res2) {
               res = res1;
               dir = SKIP_ANY;
@@ skipping 107 matching lines @@
                               Handle<String> s2, int pos2, int len) {
   for (int i = 0; i < len; i++) {
     if (s1->Get(i + pos1) != s2->Get(i + pos2)) {
       return false;
     }
   }
   return true;
 }
 
 
+// Additional to Input interface. Lets switch Input range to subrange.
+// More elegant way would be to wrap one Input as another Input object
+// and translate positions there, but that would cost us additional virtual
+// call per comparison.
+class SubrangableInput : public Comparator::Input {
+ public:
+  virtual void SetSubrange1(int offset, int len) = 0;
+  virtual void SetSubrange2(int offset, int len) = 0;
+};
+
+
+class SubrangableOutput : public Comparator::Output {
+ public:
+  virtual void SetSubrange1(int offset, int len) = 0;
+  virtual void SetSubrange2(int offset, int len) = 0;
+};
+
+
+static int min(int a, int b) {
+  return a < b ? a : b;
+}
+
+
+// Finds common prefix and suffix in input. This parts shouldn't take space in
+// linear programming table. Enable subranging in input and output.
+static void NarrowDownInput(SubrangableInput* input,
+    SubrangableOutput* output) {
+  const int len1 = input->GetLength1();
+  const int len2 = input->GetLength2();
+
+  int common_prefix_len;
+  int common_suffix_len;
+
+  {
+    common_prefix_len = 0;
+    int prefix_limit = min(len1, len2);
+    while (common_prefix_len < prefix_limit &&
+        input->Equals(common_prefix_len, common_prefix_len)) {
+      common_prefix_len++;
+    }
+
+    common_suffix_len = 0;
+    int suffix_limit = min(len1 - common_prefix_len, len2 - common_prefix_len);
+
+    while (common_suffix_len < suffix_limit &&
+        input->Equals(len1 - common_suffix_len - 1,
+        len2 - common_suffix_len - 1)) {
+      common_suffix_len++;
+    }
+  }
+
+  if (common_prefix_len > 0 || common_suffix_len > 0) {
+    int new_len1 = len1 - common_suffix_len - common_prefix_len;
+    int new_len2 = len2 - common_suffix_len - common_prefix_len;
+
+    input->SetSubrange1(common_prefix_len, new_len1);
+    input->SetSubrange2(common_prefix_len, new_len2);
+
+    output->SetSubrange1(common_prefix_len, new_len1);
+    output->SetSubrange2(common_prefix_len, new_len2);
+  }
+}
+
+
 // A helper class that writes chunk numbers into JSArray.
 // Each chunk is stored as 3 array elements: (pos1_begin, pos1_end, pos2_end).
 class CompareOutputArrayWriter {
  public:
   CompareOutputArrayWriter()
       : array_(FACTORY->NewJSArray(10)), current_size_(0) {}
 
   Handle<JSArray> GetResult() {
     return array_;
   }
@@ skipping 20 matching lines @@
 // Represents 2 strings as 2 arrays of tokens.
 // TODO(LiveEdit): Currently it's actually an array of charactres.
 //     Make array of tokens instead.
 class TokensCompareInput : public Comparator::Input {
  public:
   TokensCompareInput(Handle<String> s1, int offset1, int len1,
                        Handle<String> s2, int offset2, int len2)
       : s1_(s1), offset1_(offset1), len1_(len1),
         s2_(s2), offset2_(offset2), len2_(len2) {
   }
-  virtual int getLength1() {
+  virtual int GetLength1() {
     return len1_;
   }
-  virtual int getLength2() {
+  virtual int GetLength2() {
     return len2_;
   }
-  bool equals(int index1, int index2) {
+  bool Equals(int index1, int index2) {
     return s1_->Get(offset1_ + index1) == s2_->Get(offset2_ + index2);
   }
 
  private:
   Handle<String> s1_;
   int offset1_;
   int len1_;
   Handle<String> s2_;
   int offset2_;
   int len2_;
@@ skipping 55 matching lines @@
   Handle<FixedArray> ends_array_;
   int string_len_;
 
   int GetPosAfterNewLine(int index) {
     return Smi::cast(ends_array_->get(index))->value() + 1;
   }
 };
 
 
 // Represents 2 strings as 2 arrays of lines.
-class LineArrayCompareInput : public Comparator::Input {
+class LineArrayCompareInput : public SubrangableInput {
  public:
   LineArrayCompareInput(Handle<String> s1, Handle<String> s2,
                         LineEndsWrapper line_ends1, LineEndsWrapper line_ends2)
       : s1_(s1), s2_(s2), line_ends1_(line_ends1),
-        line_ends2_(line_ends2) {
+        line_ends2_(line_ends2),
+        subrange_offset1_(0), subrange_offset2_(0),
+        subrange_len1_(line_ends1_.length()),
+        subrange_len2_(line_ends2_.length()) {
   }
-  int getLength1() {
-    return line_ends1_.length();
+  int GetLength1() {
+    return subrange_len1_;
   }
-  int getLength2() {
-    return line_ends2_.length();
+  int GetLength2() {
+    return subrange_len2_;
   }
-  bool equals(int index1, int index2) {
+  bool Equals(int index1, int index2) {
+    index1 += subrange_offset1_;
+    index2 += subrange_offset2_;
+
     int line_start1 = line_ends1_.GetLineStart(index1);
     int line_start2 = line_ends2_.GetLineStart(index2);
     int line_end1 = line_ends1_.GetLineEnd(index1);
     int line_end2 = line_ends2_.GetLineEnd(index2);
     int len1 = line_end1 - line_start1;
     int len2 = line_end2 - line_start2;
     if (len1 != len2) {
       return false;
     }
     return CompareSubstrings(s1_, line_start1, s2_, line_start2,
                              len1);
   }
+  void SetSubrange1(int offset, int len) {
+    subrange_offset1_ = offset;
+    subrange_len1_ = len;
+  }
+  void SetSubrange2(int offset, int len) {
+    subrange_offset2_ = offset;
+    subrange_len2_ = len;
+  }
 
  private:
   Handle<String> s1_;
   Handle<String> s2_;
   LineEndsWrapper line_ends1_;
   LineEndsWrapper line_ends2_;
+  int subrange_offset1_;
+  int subrange_offset2_;
+  int subrange_len1_;
+  int subrange_len2_;
 };
 
 
 // Stores compare result in JSArray. For each chunk tries to conduct
 // a fine-grained nested diff token-wise.
-class TokenizingLineArrayCompareOutput : public Comparator::Output {
+class TokenizingLineArrayCompareOutput : public SubrangableOutput {
  public:
   TokenizingLineArrayCompareOutput(LineEndsWrapper line_ends1,
                                    LineEndsWrapper line_ends2,
                                    Handle<String> s1, Handle<String> s2)
-      : line_ends1_(line_ends1), line_ends2_(line_ends2), s1_(s1), s2_(s2) {
+      : line_ends1_(line_ends1), line_ends2_(line_ends2), s1_(s1), s2_(s2),
+        subrange_offset1_(0), subrange_offset2_(0) {
   }
 
   void AddChunk(int line_pos1, int line_pos2, int line_len1, int line_len2) {
+    line_pos1 += subrange_offset1_;
+    line_pos2 += subrange_offset2_;
+
     int char_pos1 = line_ends1_.GetLineStart(line_pos1);
     int char_pos2 = line_ends2_.GetLineStart(line_pos2);
     int char_len1 = line_ends1_.GetLineStart(line_pos1 + line_len1) - char_pos1;
     int char_len2 = line_ends2_.GetLineStart(line_pos2 + line_len2) - char_pos2;
 
     if (char_len1 < CHUNK_LEN_LIMIT && char_len2 < CHUNK_LEN_LIMIT) {
       // Chunk is small enough to conduct a nested token-level diff.
       HandleScope subTaskScope;
 
       TokensCompareInput tokens_input(s1_, char_pos1, char_len1,
                                       s2_, char_pos2, char_len2);
       TokensCompareOutput tokens_output(&array_writer_, char_pos1,
                                           char_pos2);
 
       Comparator::CalculateDifference(&tokens_input, &tokens_output);
     } else {
       array_writer_.WriteChunk(char_pos1, char_pos2, char_len1, char_len2);
     }
   }
+  void SetSubrange1(int offset, int len) {
+    subrange_offset1_ = offset;
+  }
+  void SetSubrange2(int offset, int len) {
+    subrange_offset2_ = offset;
+  }
 
   Handle<JSArray> GetResult() {
     return array_writer_.GetResult();
   }
 
  private:
   static const int CHUNK_LEN_LIMIT = 800;
 
   CompareOutputArrayWriter array_writer_;
   LineEndsWrapper line_ends1_;
   LineEndsWrapper line_ends2_;
   Handle<String> s1_;
   Handle<String> s2_;
+  int subrange_offset1_;
+  int subrange_offset2_;
 };
 
 
 Handle<JSArray> LiveEdit::CompareStrings(Handle<String> s1,
                                          Handle<String> s2) {
   s1 = FlattenGetString(s1);
   s2 = FlattenGetString(s2);
 
   LineEndsWrapper line_ends1(s1);
   LineEndsWrapper line_ends2(s2);
 
   LineArrayCompareInput input(s1, s2, line_ends1, line_ends2);
   TokenizingLineArrayCompareOutput output(line_ends1, line_ends2, s1, s2);
 
+  NarrowDownInput(&input, &output);
+
   Comparator::CalculateDifference(&input, &output);
 
   return output.GetResult();
 }
 
 
 static void CompileScriptForTracker(Isolate* isolate, Handle<Script> script) {
   // TODO(635): support extensions.
   PostponeInterruptsScope postpone(isolate);
 
@@ skipping 1176 matching lines @@
 
 bool LiveEditFunctionTracker::IsActive(Isolate* isolate) {
   return false;
 }
 
 #endif  // ENABLE_DEBUGGER_SUPPORT
 
 
 
 } }  // namespace v8::internal