From 20d2274a9383c5e585b87b1225a7da3cf1dcb194 Mon Sep 17 00:00:00 2001 From: John Hawthorn Date: Sat, 13 Oct 2018 14:05:10 -0700 Subject: 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 --- src/match.c | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-) 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]; -- cgit v1.2.3