Re: Caching merged diffs

[Kai Willadsen <kai willadsen gmail com>]

2009/7/18 Piotr Piastucki <leech miranda gmail com>:
> 2009/7/11 Stephen Kennedy <stevek gnome org>:
>>>
>>> It's reasonable then to put the diff computation & most of the i/o in a
>>> subprocess, which would make the ui much more responsive.
>>>
>
> Regarding ui responsiveness, I am sending a patch that tries to improve
> performance of inline highlighting.
> Test case:
> 1) run "meld filediff.py meldapp.py"
> 2) type something in either of the panes
> 3) wait.... :)
> I know it is not a real-life example, but it shows exactly what the issue
> is.
> Patch:
> I added a simple cache that stores replace chunks. The cache is updated and
> checked in _update_highlighting(). Chunks that did not change are not taken
> into account and as a result inline highlighting becomes somewhat
> incremental.

Amusingly enough, I looked at exactly the same issue yesterday. I went
for a simpler approach though (patch attached), and just cached the
SequenceMatcher calls; I'm pretty sure that that's the only really
expensive part of the updating. My version is missing cache-clearing,
but that's fairly easy to add.

> Moreover I could not find any place where "delete line", "conflict line" or
> "replace line" tags are set so I changed this piece of code and remove_tag()
> is called for "inline line" only.

Right - that's a separate issue, and should be fixed regardless. I
believe that of the tags we currently set up, only edited and inline
are used. One could imagine that tagging the whole buffer
appropriately might be useful in some way... but I'm not really sure
how.

Kai

From 2ffcbe2c770582a315e50a6541859b5846b18fce Mon Sep 17 00:00:00 2001
From: Kai Willadsen <kai willadsen gmail com>
Date: Fri, 17 Jul 2009 12:58:39 +1000
Subject: [PATCH] Cache inline-diff results to avoid rediffing unchanged blocks

---
 filediff.py |   17 +++++++++++++++--
 1 files changed, 15 insertions(+), 2 deletions(-)

diff --git a/filediff.py b/filediff.py
index acc1546..e4ccdff 100644
--- a/filediff.py
+++ b/filediff.py
@@ -46,6 +46,19 @@ gdk = gtk.gdk
 
 MASK_SHIFT, MASK_CTRL = 1, 2
 
+class CachedSequenceMatcher(object):
+    def __init__(self):
+        self.cache = {}
+
+    def __call__(self, text1, textn):
+        try:
+            return self.cache[(text1, textn)]
+        except KeyError:
+            matcher = difflib.SequenceMatcher(None, text1, textn)
+            opcodes = matcher.get_opcodes()
+            self.cache[(text1, textn)] = opcodes
+            return opcodes
+
 def get_iter_at_line_or_eof(buffer, line):
     if line >= buffer.get_line_count():
         return buffer.get_end_iter()
@@ -91,6 +104,7 @@ class FileDiff(melddoc.MeldDoc, gnomeglade.Component):
         self._sync_vscroll_lock = False
         self._sync_hscroll_lock = False
         self.linediffer = diffutil.Differ()
+        self.cached_match = CachedSequenceMatcher()
         for text in self.textview:
             text.set_wrap_mode( self.prefs.edit_wrap_lines )
         for buf in self.textbuffer:
@@ -648,10 +662,9 @@ class FileDiff(melddoc.MeldDoc, gnomeglade.Component):
                             bufs[i].apply_tag(tags[i], starts[i], ends[i])
                         continue
 
-                    matcher = difflib.SequenceMatcher(None, text1, textn)
                     #print "<<<\n%s\n---\n%s\n>>>" % (text1, textn)
                     back = (0,0)
-                    for o in matcher.get_opcodes():
+                    for o in self.cached_match(text1, textn):
                         if o[0] == "equal":
                             if (o[2]-o[1] < 3) or (o[4]-o[3] < 3):
                                 back = o[4]-o[3], o[2]-o[1]
-- 
1.6.0.6