[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.

2 files changed, 40 insertions, 32 deletions

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)
 	}