Fossil SCM

Optimize the inner loop of the LCS algorithm for the main diff generator.

drh 2012-02-07 18:13 trunk
Commit 4ab6071145a7fe02a114661ee94ea006f0e44a4e
Parent 030035345c802bb…
1 file changed +20 -9
~ src/diff.c
M src/diff.c
+20 -9
--- src/diff.c
+++ src/diff.c
@@ -897,10 +897,15 @@
897897
 *piEX = iSXb + mxLength;
898898
 *piSY = iSYb;
899899
 *piEY = iSYb + mxLength;
900900
 }
901901
902
+/*
903
+** Minimum of two values
904
+*/
905
+static int minInt(int a, int b){ return a<b ? a : b; }
906
+
902907
 /*
903908
 ** Compare two blocks of text on lines iS1 through iE1-1 of the aFrom[]
904909
 ** file and lines iS2 through iE2-1 of the aTo[] file. Locate a sequence
905910
 ** of lines in these two blocks that are exactly the same. Return
906911
 ** the bounds of the matching sequence.
@@ -923,11 +928,13 @@
923928
 int iS2, int iE2, /* Range of lines in p->aTo[] */
924929
 int *piSX, int *piEX, /* Write p->aFrom[] common segment here */
925930
 int *piSY, int *piEY /* Write p->aTo[] common segment here */
926931
 ){
927932
 double bestScore = -1e30; /* Best score seen so far */
928
- int i, j; /* Loop counters */
933
+ int i, j, k; /* Loop counters */
934
+ int n; /* Loop limit */
935
+ DLine *pA, *pB; /* Pointers to lines */
929936
 int iSX, iSY, iEX, iEY; /* Current match */
930937
 double score; /* Current score */
931938
 int skew; /* How lopsided is the match */
932939
 int dist; /* Distance of match from center */
933940
 int mid; /* Center of the span */
@@ -956,20 +963,24 @@
956963
 assert( i>=iSXb && i>=iSXp );
957964
 if( i<iEXb && j>=iSYb && j<iEYb ) continue;
958965
 if( i<iEXp && j>=iSYp && j<iEYp ) continue;
959966
 iSX = i;
960967
 iSY = j-1;
961
- while( iSX>iS1 && iSY>iS2 && same_dline(&p->aFrom[iSX-1],&p->aTo[iSY-1]) ){
962
- iSX--;
963
- iSY--;
964
- }
968
+ pA = &p->aFrom[iSX-1];
969
+ pB = &p->aTo[iSY-1];
970
+ n = minInt(iSX-iS1, iSY-iS2);
971
+ for(k=0; k<n && same_dline(pA,pB); k++, pA--, pB--){}
972
+ iSX -= k;
973
+ iSY -= k;
965974
 iEX = i+1;
966975
 iEY = j;
967
- while( iEX<iE1 && iEY<iE2 && same_dline(&p->aFrom[iEX],&p->aTo[iEY]) ){
968
- iEX++;
969
- iEY++;
970
- }
976
+ pA = &p->aFrom[iEX];
977
+ pB = &p->aTo[iEY];
978
+ n = minInt(iE1-iEX, iE2-iEY);
979
+ for(k=0; k<n && same_dline(pA,pB); k++, pA++, pB++){}
980
+ iEX += k;
981
+ iEY += k;
971982
 skew = (iSX-iS1) - (iSY-iS2);
972983
 if( skew<0 ) skew = -skew;
973984
 dist = (iSX+iEX)/2 - mid;
974985
 if( dist<0 ) dist = -dist;
975986
 score = (iEX - iSX) - 0.05*skew - 0.05*dist;
976987
--- src/diff.c
+++ src/diff.c
@@ -897,10 +897,15 @@
897 *piEX = iSXb + mxLength;
898 *piSY = iSYb;
899 *piEY = iSYb + mxLength;
900 }
901
 
 
 
 
 
902 /*
903 ** Compare two blocks of text on lines iS1 through iE1-1 of the aFrom[]
904 ** file and lines iS2 through iE2-1 of the aTo[] file. Locate a sequence
905 ** of lines in these two blocks that are exactly the same. Return
906 ** the bounds of the matching sequence.
@@ -923,11 +928,13 @@
923 int iS2, int iE2, /* Range of lines in p->aTo[] */
924 int *piSX, int *piEX, /* Write p->aFrom[] common segment here */
925 int *piSY, int *piEY /* Write p->aTo[] common segment here */
926 ){
927 double bestScore = -1e30; /* Best score seen so far */
928 int i, j; /* Loop counters */
 
 
929 int iSX, iSY, iEX, iEY; /* Current match */
930 double score; /* Current score */
931 int skew; /* How lopsided is the match */
932 int dist; /* Distance of match from center */
933 int mid; /* Center of the span */
@@ -956,20 +963,24 @@
956 assert( i>=iSXb && i>=iSXp );
957 if( i<iEXb && j>=iSYb && j<iEYb ) continue;
958 if( i<iEXp && j>=iSYp && j<iEYp ) continue;
959 iSX = i;
960 iSY = j-1;
961 while( iSX>iS1 && iSY>iS2 && same_dline(&p->aFrom[iSX-1],&p->aTo[iSY-1]) ){
962 iSX--;
963 iSY--;
964 }
 
 
965 iEX = i+1;
966 iEY = j;
967 while( iEX<iE1 && iEY<iE2 && same_dline(&p->aFrom[iEX],&p->aTo[iEY]) ){
968 iEX++;
969 iEY++;
970 }
 
 
971 skew = (iSX-iS1) - (iSY-iS2);
972 if( skew<0 ) skew = -skew;
973 dist = (iSX+iEX)/2 - mid;
974 if( dist<0 ) dist = -dist;
975 score = (iEX - iSX) - 0.05*skew - 0.05*dist;
976
--- src/diff.c
+++ src/diff.c
@@ -897,10 +897,15 @@
897 *piEX = iSXb + mxLength;
898 *piSY = iSYb;
899 *piEY = iSYb + mxLength;
900 }
901
902 /*
903 ** Minimum of two values
904 */
905 static int minInt(int a, int b){ return a<b ? a : b; }
906
907 /*
908 ** Compare two blocks of text on lines iS1 through iE1-1 of the aFrom[]
909 ** file and lines iS2 through iE2-1 of the aTo[] file. Locate a sequence
910 ** of lines in these two blocks that are exactly the same. Return
911 ** the bounds of the matching sequence.
@@ -923,11 +928,13 @@
928 int iS2, int iE2, /* Range of lines in p->aTo[] */
929 int *piSX, int *piEX, /* Write p->aFrom[] common segment here */
930 int *piSY, int *piEY /* Write p->aTo[] common segment here */
931 ){
932 double bestScore = -1e30; /* Best score seen so far */
933 int i, j, k; /* Loop counters */
934 int n; /* Loop limit */
935 DLine *pA, *pB; /* Pointers to lines */
936 int iSX, iSY, iEX, iEY; /* Current match */
937 double score; /* Current score */
938 int skew; /* How lopsided is the match */
939 int dist; /* Distance of match from center */
940 int mid; /* Center of the span */
@@ -956,20 +963,24 @@
963 assert( i>=iSXb && i>=iSXp );
964 if( i<iEXb && j>=iSYb && j<iEYb ) continue;
965 if( i<iEXp && j>=iSYp && j<iEYp ) continue;
966 iSX = i;
967 iSY = j-1;
968 pA = &p->aFrom[iSX-1];
969 pB = &p->aTo[iSY-1];
970 n = minInt(iSX-iS1, iSY-iS2);
971 for(k=0; k<n && same_dline(pA,pB); k++, pA--, pB--){}
972 iSX -= k;
973 iSY -= k;
974 iEX = i+1;
975 iEY = j;
976 pA = &p->aFrom[iEX];
977 pB = &p->aTo[iEY];
978 n = minInt(iE1-iEX, iE2-iEY);
979 for(k=0; k<n && same_dline(pA,pB); k++, pA++, pB++){}
980 iEX += k;
981 iEY += k;
982 skew = (iSX-iS1) - (iSY-iS2);
983 if( skew<0 ) skew = -skew;
984 dist = (iSX+iEX)/2 - mid;
985 if( dist<0 ) dist = -dist;
986 score = (iEX - iSX) - 0.05*skew - 0.05*dist;
987

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button