Fast String Searching in Go With strings and bytes

Most programs search text far more than they parse it: finding a marker in a log line, looking for a delimiter, checking whether a request contains a word, counting a character. The standard library's strings and bytes packages are tuned for this, down to assembly on common processors, and the gap between the best and the worst way to answer the same question is two orders of magnitude. This article measures a set of searches over 990 KB of text on Go 1.25, from single byte scans at 63 GB/s to case folding at 0.4 GB/s, and gives the order in which to try the options.

It follows why regular expressions in Go are safe but often slow and complements regexp against manual parsing. For building text instead of searching it, read the strings Builder. The cornerstone is the Go performance guide.

The haystack

990,020 bytes made of one sentence repeated 22,000 times with "needle in a haystack" appended, so a search for the needle reads the entire text. Each row is the best of 25 runs. The laptop had a load average near 5, which matters: the same function (strings.Contains is strings.Index underneath) measured 245 µs and 347 µs in two rows of one run. Read the table for orders of magnitude, not for differences under about 40 percent.

package main

import (
	"bytes"
	"fmt"
	"strings"
	"time"
	"unicode"
)

func best(f func()) time.Duration {
	f()
	b := time.Hour
	for i := 0; i < 25; i++ {
		t := time.Now()
		f()
		if d := time.Since(t); d < b {
			b = d
		}
	}
	return b
}

func naiveIndex(s, sub string) int {
	for i := 0; i+len(sub) <= len(s); i++ {
		j := 0
		for j < len(sub) && s[i+j] == sub[j] {
			j++
		}
		if j == len(sub) {
			return i
		}
	}
	return -1
}

func lowerContains(s, sub string) bool {
	return strings.Contains(strings.ToLower(s), strings.ToLower(sub))
}

func foldContains(s, sub string) bool {
	n := len(sub)
	for i := 0; i+n <= len(s); i++ {
		if strings.EqualFold(s[i:i+n], sub) {
			return true
		}
	}
	return false
}

var sinkI int
var sinkB bool

func main() {
	text := strings.Repeat("the quick brown fox jumps over the lazy dog. ", 22000)
	text += "needle in a haystack"
	tb := []byte(text)
	mb := float64(len(text)) / 1e6
	fmt.Printf("haystack of %d bytes; the needle is at the very end, so every search reads it all\n\n", len(text))
	row := func(name string, f func()) {
		d := best(f)
		fmt.Printf("  %-44s %12v %9.0f MB/s\n", name, d, mb/d.Seconds())
	}
	row("strings.Index(text, \"needle\")", func() { sinkI = strings.Index(text, "needle") })
	row("bytes.Index(tb, \"needle\")", func() { sinkI = bytes.Index(tb, []byte("needle")) })
	row("strings.Contains(text, \"needle\")", func() { sinkB = strings.Contains(text, "needle") })
	row("naive double loop", func() { sinkI = naiveIndex(text, "needle") })
	row("strings.IndexByte(text, 'N') absent byte", func() { sinkI = strings.IndexByte(text, 'N') })
	row("strings.IndexRune(text, 'é') absent rune", func() { sinkI = strings.IndexRune(text, 'é') })
	row("strings.IndexAny(text, \"xyz!\")  (set of bytes)", func() { sinkI = strings.IndexAny(text, "Q!") })
	row("strings.IndexFunc(text, unicode.IsUpper)", func() { sinkI = strings.IndexFunc(text, unicode.IsUpper) })
	row("strings.Count(text, \"fox\")", func() { sinkI = strings.Count(text, "fox") })
	row("strings.Count(text, \"o\") one byte", func() { sinkI = strings.Count(text, "o") })
	fmt.Println()
	fmt.Println("case insensitive search for \"NEEDLE\"")
	row("ToLower both, then Contains", func() { sinkB = lowerContains(text, "NEEDLE") })
	row("EqualFold at every offset", func() { sinkB = foldContains(text, "NEEDLE") })
	fmt.Println()
	fmt.Println("a needle that looks like the haystack (many partial matches)")
	hay := strings.Repeat("a", 1<<20) + "b"
	need := strings.Repeat("a", 50) + "b"
	hmb := float64(len(hay)) / 1e6
	for _, c := range []struct {
		name string
		f    func()
	}{
		{"strings.Index", func() { sinkI = strings.Index(hay, need) }},
		{"naive double loop", func() { sinkI = naiveIndex(hay, need) }},
	} {
		d := best(c.f)
		fmt.Printf("  %-44s %12v %9.0f MB/s\n", c.name, d, hmb/d.Seconds())
	}
}

haystack of 990020 bytes; the needle is at the very end, so every search reads it all

  strings.Index(text, "needle")                   244.625µs      4047 MB/s
  bytes.Index(tb, "needle")                         405.5µs      2441 MB/s
  strings.Contains(text, "needle")                 347.25µs      2851 MB/s
  naive double loop                              1.187167ms       834 MB/s
  strings.IndexByte(text, 'N') absent byte         15.625µs     63361 MB/s
  strings.IndexRune(text, 'é') absent rune         15.542µs     63700 MB/s
  strings.IndexAny(text, "xyz!")  (set of bytes)    507.583µs      1950 MB/s
  strings.IndexFunc(text, unicode.IsUpper)         920.25µs      1076 MB/s
  strings.Count(text, "fox")                      299.542µs      3305 MB/s
  strings.Count(text, "o") one byte                19.166µs     51655 MB/s

case insensitive search for "NEEDLE"
  ToLower both, then Contains                    1.056208ms       937 MB/s
  EqualFold at every offset                      2.278625ms       434 MB/s

a needle that looks like the haystack (many partial matches)
  strings.Index                                  1.299375ms       807 MB/s
  naive double loop                             25.224333ms        42 MB/s

Results: exact searches

One byte is a different problem

IndexByte and a one byte Count ran at over 50 GB/s, 12 to 15 times faster than a multi byte search. On amd64 and arm64 they are written in assembly that compares 16 or 32 bytes per instruction. The rune search for é took the same time because for a rune of more than one byte the function searches for the last byte of its encoding with the same primitive and checks the rest. So if a question can be reduced to a single byte, ask it that way: find the newline, the comma, the colon, the quote. A parser that splits on newlines should use IndexByte in a loop.

A literal needle is also fast

strings.Index for "needle" ran at about 4 GB/s. For short needles the implementation uses the same vector search on the first byte and then verifies the rest; for longer ones, a hashing strategy (Rabin Karp) and, on some processors, a vector assisted routine. All of these are about five times faster than the naive loop. bytes.Index on a []byte is the same algorithm and measured within noise of the string version.

Sets and predicates are slower

strings.IndexAny(text, "xyz!") checks every byte against a set, and at 1.9 GB/s was half the speed of a literal search. strings.IndexFunc(text, unicode.IsUpper) calls a function for each rune and decodes UTF-8 as it goes: 1.1 GB/s. They are the right tools when the question really is a set or a predicate. When the set is small and ASCII, several IndexByte calls (taking the minimum) can beat IndexAny.

The naive loop is not terrible on this text, and terrible on other text

At 834 MB/s the double loop was only five times slower than Index on prose, because most positions fail at the first byte. The next test is where it falls over.

A haystack that fights back

Searching a megabyte of the letter a for fifty a's followed by b:

The naive loop compares up to 50 bytes at every offset before failing, so it did 19 times the work. strings.Index avoids rework with a rolling hash and still took 1.3 ms, a sign that even the library has a worst case. Real text rarely does this, but inputs that are repetitive (padding, base64 runs, 0 columns) can look like it, and a hand written search will find it.

Case insensitive search

Neither is close to the 4 GB/s of the exact search. Lower casing the text allocates a second copy of it (990 KB here) and runs through every rune; EqualFold at each offset avoids the allocation and is slower. Three better options exist. If you search the same text many times, lower case it once and keep it. If the needle is ASCII, search for the lower and upper case forms of its rarest letter with IndexByte and verify around the hits. If it is a one off, accept the cost. A regexp with (?i) is slower still, 59 MB/s in the previous article.

Choosing

1. Single byte or rune: IndexByte, IndexRune, Count with one byte.
2. Literal substring: Index, Contains, HasPrefix, Cut.
3. Several literals: loop over Index for each, or build an Aho Corasick automaton from a library if the set is large (hundreds).
4. A set of bytes: IndexAny, or IndexByte for each member when the set has two or three.
5. A predicate: IndexFunc.
6. A pattern: regexp, with a literal prefix, compiled once.
7. Many searches in the same text: build an index once (a map of words, a suffix array, a trigram index) instead of scanning each time.

strings.Cut(s, sep) is worth knowing: it finds a separator and returns the pieces before and after it in one call, and most "find it, then slice around it" code is shorter and no slower with it.

Mistakes that cost more than the search

• Converting between string and []byte to use the other package. Each conversion copies the text (990 KB here). Pick one type and stay in it (string and byte conversions).
• strings.ToLower on the haystack for every search. Allocates a copy each time.
• Contains in a loop over a large slice of needles against a large text. That is quadratic. Index the text or the needles.
• Using Split to find one thing. It allocates a slice of every piece. Cut or Index finds the first without it.

Checklist

• Reduce the question to a byte when you can: 63 GB/s.
• Literal searches ran at about 4 GB/s; naive loops 5 to 25 times slower.
• Sets, predicates and case folding cost 2 to 9 times more than a literal.
• Do not measure differences under 40 percent on a loaded machine.
• Index text you search repeatedly.

The functions are documented in the strings package and the bytes package, and the assembly in the Go source.