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 261 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;

[Søren Thygesen Gjesse, 2011/05/31 08:09:19]

set -> Set (times 4)

[Peter Rybin, 2011/05/31 15:02:23]

Oh sorry, cannot properly switch to C++ again. :(
Done

+  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) {

[Søren Thygesen Gjesse, 2011/05/31 08:09:19]

common_suffix_len -> common_suffix_len > 0

[Peter Rybin, 2011/05/31 15:02:23]

Thanks, missed this!
Done

+    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 102 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() {

[Søren Thygesen Gjesse, 2011/05/31 08:09:19]

get -> Get

[Peter Rybin, 2011/05/31 15:02:23]

Done.

-    return line_ends1_.length();
+    return subrange_len1_;
   }
   int getLength2() {
-    return line_ends2_.length();
+    return subrange_len2_;
   }
   bool equals(int index1, int index2) {

[Søren Thygesen Gjesse, 2011/05/31 08:09:19]

equals -> Equals

[Peter Rybin, 2011/05/31 15:02:23]

Done.

+    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