diff options
| author | Kenneth Finnegan <kennethfinnegan2007@gmail.com> | 2022-09-15 10:12:02 -0700 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2022-09-15 10:12:02 -0700 |
| commit | 8fe8cfd60af417f5467f7723075f5ad050b806c8 (patch) | |
| tree | 2b10155ae2f61267def7831ca33c29b4614510bd /generator.c | |
| parent | 7a2dbf717794655a3fd82439fdb1e3d8b4730c74 (diff) | |
| download | rsync-8fe8cfd60af417f5467f7723075f5ad050b806c8.tar.gz | |
Use string length diff heuristic to skip Levenshtein Algo (#369)
When using the --fuzzy option to try and find close matches locally,
the edit distance algorithm used is O(N^2), which can get painful on
CPU constrained systems when working in folders with tens of thousands
of files in it.
The lower bound on the calculated Levenshtein distance is the difference
of the two strings being compared, so if that difference is larger than
the current best match, the calculation of the exact edit distance between
the two strings can be skipped.
Testing on the OpenSUSE package repo has shown a 50% reduction in the CPU time
required to plan the rsync transaction.
Diffstat (limited to 'generator.c')
| -rw-r--r-- | generator.c | 9 |
1 files changed, 6 insertions, 3 deletions
diff --git a/generator.c b/generator.c index 935c84f9..21c4a595 100644 --- a/generator.c +++ b/generator.c @@ -875,9 +875,12 @@ static struct file_struct *find_fuzzy(struct file_struct *file, struct file_list len = strlen(name); suf = find_filename_suffix(name, len, &suf_len); - dist = fuzzy_distance(name, len, fname, fname_len); - /* Add some extra weight to how well the suffixes match. */ - dist += fuzzy_distance(suf, suf_len, fname_suf, fname_suf_len) * 10; + dist = fuzzy_distance(name, len, fname, fname_len, lowest_dist); + /* Add some extra weight to how well the suffixes match unless we've already disqualified + * this file based on a heuristic. */ + if (dist < 0xFFFF0000U) { + dist += fuzzy_distance(suf, suf_len, fname_suf, fname_suf_len, 0xFFFF0000U) * 10; + } if (DEBUG_GTE(FUZZY, 2)) { rprintf(FINFO, "fuzzy distance for %s = %d.%05d\n", f_name(fp, NULL), (int)(dist>>16), (int)(dist&0xFFFF)); |