From 1d4057c20907b7d263d6f2b8cb4350a024859dfe Mon Sep 17 00:00:00 2001 From: Junegunn Choi Date: Sun, 14 Aug 2016 00:39:44 +0900 Subject: [perf] Avoid allocating rune array for ascii string In the best case (all ascii), this reduces the memory footprint by 60% and the response time by 15% to 20%. In the worst case (every line has non-ascii characters), 3 to 4% overhead is observed. --- src/algo/algo.go | 66 ++++++++++++++++++++++++++++----------------------- src/algo/algo_test.go | 6 +++-- 2 files changed, 40 insertions(+), 32 deletions(-) (limited to 'src/algo') diff --git a/src/algo/algo.go b/src/algo/algo.go index d8e2fec2..9bf476fd 100644 --- a/src/algo/algo.go +++ b/src/algo/algo.go @@ -15,11 +15,18 @@ import ( * In short: They try to do as little work as possible. */ -func runeAt(runes []rune, index int, max int, forward bool) rune { +func indexAt(index int, max int, forward bool) int { if forward { - return runes[index] + return index } - return runes[max-index-1] + return max - index - 1 +} + +func runeAt(text util.Chars, index int, max int, forward bool) rune { + if forward { + return text.Get(index) + } + return text.Get(max - index - 1) } // Result conatins the results of running a match function. @@ -42,14 +49,14 @@ const ( charNumber ) -func evaluateBonus(caseSensitive bool, runes []rune, pattern []rune, sidx int, eidx int) int32 { +func evaluateBonus(caseSensitive bool, text util.Chars, pattern []rune, sidx int, eidx int) int32 { var bonus int32 pidx := 0 lenPattern := len(pattern) consecutive := false prevClass := charNonWord for index := 0; index < eidx; index++ { - char := runes[index] + char := text.Get(index) var class charClass if unicode.IsLower(char) { class = charLower @@ -107,7 +114,7 @@ func evaluateBonus(caseSensitive bool, runes []rune, pattern []rune, sidx int, e } // FuzzyMatch performs fuzzy-match -func FuzzyMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) Result { +func FuzzyMatch(caseSensitive bool, forward bool, text util.Chars, pattern []rune) Result { if len(pattern) == 0 { return Result{0, 0, 0} } @@ -125,11 +132,11 @@ func FuzzyMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) sidx := -1 eidx := -1 - lenRunes := len(runes) + lenRunes := text.Length() lenPattern := len(pattern) - for index := range runes { - char := runeAt(runes, index, lenRunes, forward) + for index := 0; index < lenRunes; index++ { + char := runeAt(text, index, lenRunes, forward) // This is considerably faster than blindly applying strings.ToLower to the // whole string if !caseSensitive { @@ -142,7 +149,7 @@ func FuzzyMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) char = unicode.To(unicode.LowerCase, char) } } - pchar := runeAt(pattern, pidx, lenPattern, forward) + pchar := pattern[indexAt(pidx, lenPattern, forward)] if char == pchar { if sidx < 0 { sidx = index @@ -157,7 +164,7 @@ func FuzzyMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) if sidx >= 0 && eidx >= 0 { pidx-- for index := eidx - 1; index >= sidx; index-- { - char := runeAt(runes, index, lenRunes, forward) + char := runeAt(text, index, lenRunes, forward) if !caseSensitive { if char >= 'A' && char <= 'Z' { char += 32 @@ -166,7 +173,7 @@ func FuzzyMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) } } - pchar := runeAt(pattern, pidx, lenPattern, forward) + pchar := pattern[indexAt(pidx, lenPattern, forward)] if char == pchar { if pidx--; pidx < 0 { sidx = index @@ -182,7 +189,7 @@ func FuzzyMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) } return Result{int32(sidx), int32(eidx), - evaluateBonus(caseSensitive, runes, pattern, sidx, eidx)} + evaluateBonus(caseSensitive, text, pattern, sidx, eidx)} } return Result{-1, -1, 0} } @@ -194,12 +201,12 @@ func FuzzyMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) // // We might try to implement better algorithms in the future: // http://en.wikipedia.org/wiki/String_searching_algorithm -func ExactMatchNaive(caseSensitive bool, forward bool, runes []rune, pattern []rune) Result { +func ExactMatchNaive(caseSensitive bool, forward bool, text util.Chars, pattern []rune) Result { if len(pattern) == 0 { return Result{0, 0, 0} } - lenRunes := len(runes) + lenRunes := text.Length() lenPattern := len(pattern) if lenRunes < lenPattern { @@ -208,7 +215,7 @@ func ExactMatchNaive(caseSensitive bool, forward bool, runes []rune, pattern []r pidx := 0 for index := 0; index < lenRunes; index++ { - char := runeAt(runes, index, lenRunes, forward) + char := runeAt(text, index, lenRunes, forward) if !caseSensitive { if char >= 'A' && char <= 'Z' { char += 32 @@ -216,7 +223,7 @@ func ExactMatchNaive(caseSensitive bool, forward bool, runes []rune, pattern []r char = unicode.To(unicode.LowerCase, char) } } - pchar := runeAt(pattern, pidx, lenPattern, forward) + pchar := pattern[indexAt(pidx, lenPattern, forward)] if pchar == char { pidx++ if pidx == lenPattern { @@ -229,7 +236,7 @@ func ExactMatchNaive(caseSensitive bool, forward bool, runes []rune, pattern []r eidx = lenRunes - (index - lenPattern + 1) } return Result{int32(sidx), int32(eidx), - evaluateBonus(caseSensitive, runes, pattern, sidx, eidx)} + evaluateBonus(caseSensitive, text, pattern, sidx, eidx)} } } else { index -= pidx @@ -240,13 +247,13 @@ func ExactMatchNaive(caseSensitive bool, forward bool, runes []rune, pattern []r } // PrefixMatch performs prefix-match -func PrefixMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) Result { - if len(runes) < len(pattern) { +func PrefixMatch(caseSensitive bool, forward bool, text util.Chars, pattern []rune) Result { + if text.Length() < len(pattern) { return Result{-1, -1, 0} } for index, r := range pattern { - char := runes[index] + char := text.Get(index) if !caseSensitive { char = unicode.ToLower(char) } @@ -256,20 +263,19 @@ func PrefixMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) } lenPattern := len(pattern) return Result{0, int32(lenPattern), - evaluateBonus(caseSensitive, runes, pattern, 0, lenPattern)} + evaluateBonus(caseSensitive, text, pattern, 0, lenPattern)} } // SuffixMatch performs suffix-match -func SuffixMatch(caseSensitive bool, forward bool, input []rune, pattern []rune) Result { - runes := util.TrimRight(input) - trimmedLen := len(runes) +func SuffixMatch(caseSensitive bool, forward bool, text util.Chars, pattern []rune) Result { + trimmedLen := text.Length() - text.TrailingWhitespaces() diff := trimmedLen - len(pattern) if diff < 0 { return Result{-1, -1, 0} } for index, r := range pattern { - char := runes[index+diff] + char := text.Get(index + diff) if !caseSensitive { char = unicode.ToLower(char) } @@ -281,16 +287,16 @@ func SuffixMatch(caseSensitive bool, forward bool, input []rune, pattern []rune) sidx := trimmedLen - lenPattern eidx := trimmedLen return Result{int32(sidx), int32(eidx), - evaluateBonus(caseSensitive, runes, pattern, sidx, eidx)} + evaluateBonus(caseSensitive, text, pattern, sidx, eidx)} } // EqualMatch performs equal-match -func EqualMatch(caseSensitive bool, forward bool, runes []rune, pattern []rune) Result { +func EqualMatch(caseSensitive bool, forward bool, text util.Chars, pattern []rune) Result { // Note: EqualMatch always return a zero bonus. - if len(runes) != len(pattern) { + if text.Length() != len(pattern) { return Result{-1, -1, 0} } - runesStr := string(runes) + runesStr := text.ToString() if !caseSensitive { runesStr = strings.ToLower(runesStr) } diff --git a/src/algo/algo_test.go b/src/algo/algo_test.go index 3c954588..d6a5d487 100644 --- a/src/algo/algo_test.go +++ b/src/algo/algo_test.go @@ -3,13 +3,15 @@ package algo import ( "strings" "testing" + + "github.com/junegunn/fzf/src/util" ) -func assertMatch(t *testing.T, fun func(bool, bool, []rune, []rune) Result, caseSensitive, forward bool, input, pattern string, sidx int32, eidx int32, bonus int32) { +func assertMatch(t *testing.T, fun func(bool, bool, util.Chars, []rune) Result, caseSensitive, forward bool, input, pattern string, sidx int32, eidx int32, bonus int32) { if !caseSensitive { pattern = strings.ToLower(pattern) } - res := fun(caseSensitive, forward, []rune(input), []rune(pattern)) + res := fun(caseSensitive, forward, util.RunesToChars([]rune(input)), []rune(pattern)) if res.Start != sidx { t.Errorf("Invalid start index: %d (expected: %d, %s / %s)", res.Start, sidx, input, pattern) } -- cgit v1.2.3