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 <[email protected]>
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
_______________________________________________
meld-list mailing list
[email protected]
http://mail.gnome.org/mailman/listinfo/meld-list
