Author: jcorvel
Date: Tue Nov 30 23:27:51 2010
New Revision: 1040825
URL: http://svn.apache.org/viewvc?rev=1040825&view=rev
Log:
On the diff-optimizations-bytes branch:
* BRANCH-README: Add some wild ideas (which were already mentioned in the
diff-optimizations-tokens branch).
Modified:
subversion/branches/diff-optimizations-bytes/BRANCH-README
Modified: subversion/branches/diff-optimizations-bytes/BRANCH-README
URL:
http://svn.apache.org/viewvc/subversion/branches/diff-optimizations-bytes/BRANCH-README?rev=1040825&r1=1040824&r2=1040825&view=diff
==============================================================================
--- subversion/branches/diff-optimizations-bytes/BRANCH-README (original)
+++ subversion/branches/diff-optimizations-bytes/BRANCH-README Tue Nov 30
23:27:51 2010
@@ -29,4 +29,13 @@ TODO:
(offers another 10% speedup)
* rev svn_diff.h#svn_diff_fns_t []
+Other wild ideas (may or may not be worth pursuing):
+ * Make prefix scanning able to skip 1 or a couple of non-matching lines, if
+ it is able to find strictly more matching lines after that, to keep the
+ prefix scanning going.
+ * Take advantage of the fact that matching lines often come in batches: when
+ inserting a new line into the token tree, and the previous line had a
+ match, first try to match the new token with the successor of the
+ previously matched line, before binary-searching the tree for a match.
+
[1]
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Reduce_the_problem_set
