Fossil SCM
Performance improvement in LCS length computation used for side-by-side diff coloring.
Commit
08d970d68fb6d6c13f47436d659bd0c110d0f6ab
Parent
0661d65cbdea96c…
1 file changed
+3
-3
+3
-3
| --- src/diff.c | ||
| +++ src/diff.c | ||
| @@ -962,23 +962,23 @@ | ||
| 962 | 962 | if( nA>250 ) nA = 250; |
| 963 | 963 | if( nB>250 ) nB = 250; |
| 964 | 964 | avg = (nA+nB)/2; |
| 965 | 965 | if( avg==0 ) return 0; |
| 966 | 966 | if( nA==nB && memcmp(zA, zB, nA)==0 ) return 0; |
| 967 | - memset(aFirst, 0, sizeof(aFirst)); | |
| 967 | + memset(aFirst, 0xff, sizeof(aFirst)); | |
| 968 | 968 | zA--; zB--; /* Make both zA[] and zB[] 1-indexed */ |
| 969 | 969 | for(i=nB; i>0; i--){ |
| 970 | 970 | c = (unsigned char)zB[i]; |
| 971 | 971 | aNext[i] = aFirst[c]; |
| 972 | 972 | aFirst[c] = i; |
| 973 | 973 | } |
| 974 | 974 | best = 0; |
| 975 | 975 | for(i=1; i<=nA-best; i++){ |
| 976 | 976 | c = (unsigned char)zA[i]; |
| 977 | - for(j=aFirst[c]; j>0 && j<nB-best; j = aNext[j]){ | |
| 977 | + for(j=aFirst[c]; j<nB-best && memcmp(&zA[i],&zB[j],best)==0; j = aNext[j]){ | |
| 978 | 978 | int limit = minInt(nA-i, nB-j); |
| 979 | - for(k=1; k<=limit && zA[k+i]==zB[k+j]; k++){} | |
| 979 | + for(k=best; k<=limit && zA[k+i]==zB[k+j]; k++){} | |
| 980 | 980 | if( k>best ) best = k; |
| 981 | 981 | } |
| 982 | 982 | } |
| 983 | 983 | score = (best>avg) ? 0 : (avg - best)*100/avg; |
| 984 | 984 | |
| 985 | 985 |
| --- src/diff.c | |
| +++ src/diff.c | |
| @@ -962,23 +962,23 @@ | |
| 962 | if( nA>250 ) nA = 250; |
| 963 | if( nB>250 ) nB = 250; |
| 964 | avg = (nA+nB)/2; |
| 965 | if( avg==0 ) return 0; |
| 966 | if( nA==nB && memcmp(zA, zB, nA)==0 ) return 0; |
| 967 | memset(aFirst, 0, sizeof(aFirst)); |
| 968 | zA--; zB--; /* Make both zA[] and zB[] 1-indexed */ |
| 969 | for(i=nB; i>0; i--){ |
| 970 | c = (unsigned char)zB[i]; |
| 971 | aNext[i] = aFirst[c]; |
| 972 | aFirst[c] = i; |
| 973 | } |
| 974 | best = 0; |
| 975 | for(i=1; i<=nA-best; i++){ |
| 976 | c = (unsigned char)zA[i]; |
| 977 | for(j=aFirst[c]; j>0 && j<nB-best; j = aNext[j]){ |
| 978 | int limit = minInt(nA-i, nB-j); |
| 979 | for(k=1; k<=limit && zA[k+i]==zB[k+j]; k++){} |
| 980 | if( k>best ) best = k; |
| 981 | } |
| 982 | } |
| 983 | score = (best>avg) ? 0 : (avg - best)*100/avg; |
| 984 | |
| 985 |
| --- src/diff.c | |
| +++ src/diff.c | |
| @@ -962,23 +962,23 @@ | |
| 962 | if( nA>250 ) nA = 250; |
| 963 | if( nB>250 ) nB = 250; |
| 964 | avg = (nA+nB)/2; |
| 965 | if( avg==0 ) return 0; |
| 966 | if( nA==nB && memcmp(zA, zB, nA)==0 ) return 0; |
| 967 | memset(aFirst, 0xff, sizeof(aFirst)); |
| 968 | zA--; zB--; /* Make both zA[] and zB[] 1-indexed */ |
| 969 | for(i=nB; i>0; i--){ |
| 970 | c = (unsigned char)zB[i]; |
| 971 | aNext[i] = aFirst[c]; |
| 972 | aFirst[c] = i; |
| 973 | } |
| 974 | best = 0; |
| 975 | for(i=1; i<=nA-best; i++){ |
| 976 | c = (unsigned char)zA[i]; |
| 977 | for(j=aFirst[c]; j<nB-best && memcmp(&zA[i],&zB[j],best)==0; j = aNext[j]){ |
| 978 | int limit = minInt(nA-i, nB-j); |
| 979 | for(k=best; k<=limit && zA[k+i]==zB[k+j]; k++){} |
| 980 | if( k>best ) best = k; |
| 981 | } |
| 982 | } |
| 983 | score = (best>avg) ? 0 : (avg - best)*100/avg; |
| 984 | |
| 985 |