diff options
| author | John Hawthorn <john@hawthorn.email> | 2018-10-13 14:05:10 -0700 |
|---|---|---|
| committer | John Hawthorn <john@hawthorn.email> | 2018-10-13 14:57:17 -0700 |
| commit | 20d2274a9383c5e585b87b1225a7da3cf1dcb194 (patch) | |
| tree | 8c374a4842364b7c8c7bc609d408e902fe2d0909 | |
| parent | f5d41e726cd997ba038815e218c48017228a8f0e (diff) | |
Precompute tolower in match_positions
This makes match_positions significantly faster on MacOS by calling
tolower() O(N) times instead of O(N*N)
Before:
$ time ./fzy -e linux --benchmark < linux_files.txt
./fzy -e linux --benchmark < linux_files.txt 13.24s user 0.03s system 381% cpu 3.483 total
After:
$ time ./fzy -e linux --benchmark < linux_files.txt
./fzy -e linux --benchmark < linux_files.txt 4.57s user 0.02s system 381% cpu 1.204 total
| -rw-r--r-- | src/match.c | 11 |
1 files changed, 10 insertions, 1 deletions
diff --git a/src/match.c b/src/match.c index 3fa24b8..2a0b058 100644 --- a/src/match.c +++ b/src/match.c @@ -94,6 +94,15 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi return SCORE_MIN; } + char lower_needle[n]; + char lower_haystack[m]; + + for (int i = 0; i < n; i++) + lower_needle[i] = tolower(needle[i]); + + for (int i = 0; i < m; i++) + lower_haystack[i] = tolower(haystack[i]); + score_t match_bonus[m]; score_t D[n][m], M[n][m]; @@ -108,7 +117,7 @@ score_t match_positions(const char *needle, const char *haystack, size_t *positi score_t gap_score = i == n - 1 ? SCORE_GAP_TRAILING : SCORE_GAP_INNER; for (int j = 0; j < m; j++) { - if (tolower(needle[i]) == tolower(haystack[j])) { + if (lower_needle[i] == lower_haystack[j]) { score_t score = SCORE_MIN; if (!i) { score = (j * SCORE_GAP_LEADING) + match_bonus[j]; |