[PATCH] Myers matcher performance improvement

[Piotr Piastucki <leech miranda gmail com>]

Hi,

I am attaching a patch with a small change in Myers matcher code that 
remove some operations from the inner loops and results in about 10% 
performance improvement.

Regards,
Piotr

>From 1f86605a58dcb073331688a82d3de56a1cf8fa02 Mon Sep 17 00:00:00 2001
From: Piotr Piastucki <the_leech users berlios de>
Date: Thu, 2 Feb 2012 23:25:29 +0100
Subject: [PATCH] Myers matcher performance improvement 
Slightly change inner loops to improve performance by about 10%

---
 meld/matchers.py |   27 ++++++++++++++++++---------
 1 files changed, 18 insertions(+), 9 deletions(-)

diff --git a/meld/matchers.py b/meld/matchers.py
index 7ed4f7b..f92d743 100644
--- a/meld/matchers.py
+++ b/meld/matchers.py
@@ -232,11 +232,14 @@ class MyersSequenceMatcher(difflib.SequenceMatcher):
                         yv, node = t
                     else:
                         yv += 1
-                    snake = x = yv - km + middle
-                    while x < m and yv < n and a[x] == b[yv]:
+                    x = yv - km + middle
+                    if x < m and yv < n and a[x] == b[yv]:
+                        snake = x
                         x += 1
                         yv += 1
-                    if x != snake:
+                        while x < m and yv < n and a[x] == b[yv]:
+                            x += 1
+                            yv += 1
                         snake = x - snake
                         snakes.append((node, x - snake, yv - snake, snake))
                         node = len(snakes) - 1
@@ -249,11 +252,14 @@ class MyersSequenceMatcher(difflib.SequenceMatcher):
                     if yh <= t[0]:
                         yh, node = t
                         yh += 1
-                    snake = x = yh - km + middle
-                    while x < m and yh < n and a[x] == b[yh]:
+                    x = yh - km + middle
+                    if x < m and yh < n and a[x] == b[yh]:
+                        snake = x
                         x += 1
                         yh += 1
-                    if x != snake:
+                        while x < m and yh < n and a[x] == b[yh]:
+                            x += 1
+                            yh += 1
                         snake = x - snake
                         snakes.append((node, x - snake, yh - snake, snake))
                         node = len(snakes) - 1
@@ -264,11 +270,14 @@ class MyersSequenceMatcher(difflib.SequenceMatcher):
                 else:
                     y, node = fp[delta - 1]
                     y += 1
-                snake = x = y - delta + middle
-                while x < m and y < n and a[x] == b[y]:
+                x = y - delta + middle
+                if x < m and y < n and a[x] == b[y]:
+                    snake = x
                     x += 1
                     y += 1
-                if x != snake:
+                    while x < m and y < n and a[x] == b[y]:
+                        x += 1
+                        y += 1
                     snake = x - snake
                     snakes.append((node, x - snake, y - snake, snake))
                     node = len(snakes) - 1
-- 
1.7.5.4