Opensource internals

How Go Finds a Substring: AVX2 Assembly in internal/bytealg

22 min read Jay Hubbert

strings.Index is not a loop over bytes: it dispatches to hand-written SSE and AVX2 assembly in internal/bytealg, with a Rabin-Karp fallback for long needles and a per-architecture build-tag switch.

TL;DR: strings.Index does not loop over bytes in Go. It hands the work to internal/bytealg, where there is hand-written x86 assembly that compares 16 bytes at a time with SSE or 32 bytes at a time with AVX2, plus a specialisation for finding a single byte, plus Rabin-Karp for needles longer than 63 bytes. Which one you get is decided at build time by //go:build tags and at run time by the CPU’s feature bits.

Searching for a substring is one of the most common operations in any program that touches text, and it is one of the easiest to make slow. The naive implementation — compare the needle at every offset — is O(n·m). The obvious fix is a skip table or Boyer-Moore, which is what most other languages do.

Go does something else, and the “something else” is worth understanding because it is a nice piece of systems programming: a tiered strategy that puts the cheapest possible scan in the hot path, uses the CPU’s vector units to compare whole chunks of the needle at a time, and falls back to Rabin-Karp only when the needle is too long for the vector path.

This is a walk through how it all works, based on reading the Go source tree (Go 1.28 development tree).

The tiered strategy, in Go

The whole policy lives in one function, internal/stringslite.Index:

go 
// src/internal/stringslite/strings.go:28
func Index(s, substr string) int {
	n := len(substr)
	switch {
	case n == 0 || substr == s:
		return 0
	case n == 1:
		return IndexByte(s, substr[0])
	case n >= len(s):
		return -1
	case n <= bytealg.MaxLen && len(s) <= bytealg.MaxBruteForce:
		// Use brute force when s and substr both are small
		return bytealg.IndexString(s, substr)
	}
	c0 := substr[0]
	c1 := substr[1]
	i := 0
	t := len(s) - n + 1
	fails := 0
	for i < t {
		if s[i] != c0 {
			// IndexByte is faster than bytealg.IndexString, so use it as long as
			// we're not getting lots of false positives.
			o := IndexByte(s[i+1:t], c0)
			if o < 0 {
				return -1
			}
			i += o + 1
		}
		if s[i+1] == c1 && s[i:i+n] == substr {
			return i
		}
		i++
		fails++
		if n <= bytealg.MaxLen && fails > bytealg.Cutover(i) {
			// Switch to bytealg.IndexString when IndexByte produces too many false positives.
			r := bytealg.IndexString(s[i:], substr)
			if r >= 0 {
				return r + i
			}
			return -1
		} else if n > bytealg.MaxLen && fails >= 4+i>>4 && i < t {
			// See comment in ../bytes/bytes.go.
			j := bytealg.IndexRabinKarp(s[i:], substr)
			if j < 0 {
				return -1
			}
			return i + j
		}
	}
	return -1
}

Read it as a ladder, from cheapest to most expensive:

text 
  strings.Index(s, substr)
        |
        v
  +--------------------------+
  | len(substr) == 0 ?       |--yes--> 0
  +--------------------------+
        |
        v
  +--------------------------+
  | len(substr) == 1 ?       |--yes--> IndexByte   (SIMD, 16/32 bytes/iter)
  +--------------------------+
        |
        v
  +--------------------------+
  | n <= MaxLen &&           |--yes--> bytealg.Index  (SIMD, needle-sized
  | len(s) <= MaxBruteForce? |          compare at every alignment)
  +--------------------------+
        |
        v
  +--------------------------+
  | loop: IndexByte to skip  |
  | to next first-byte match, |
  | check 2nd byte, verify    |
  | whole needle              |
  +--------------------------+
        |            ^
        | fails >    | fails > Cutover(i)
        | Cutover(i) |
        v            |
  bytealg.IndexString      |
  (SIMD)                   |
        |                  |
        | n > MaxLen       |
        v                  v
  bytealg.IndexRabinKarp   (loop continues)
  (rolling hash, O(n))
  1. Empty needle, or needle equal to the whole haystack → answer is 0.
  2. One-byte needle → IndexByte, which is the fastest thing in the package (see below).
  3. Needle no longer than bytealg.MaxLen and haystack no longer than bytealg.MaxBruteForce → straight to the SIMD assembly.
  4. Otherwise → a hand-rolled loop that uses IndexByte to skip to the next candidate position (the next occurrence of the needle’s first byte), checks the second byte, and then verifies the whole needle.

That fourth step is the interesting one, and it is where the performance lives. IndexByte is vectorised and fast; the “skip” is done by asking it for the next occurrence of substr[0]. That converts the search from “compare at every offset” into “compare at every offset where the first byte matches”, which for realistic text is a tiny fraction of the input.

The fails counter is the adaptive part. If the first byte of the needle turns out to be common (think searching for "e" inside English prose, or a needle that starts with a space), the loop does a lot of false-positive work. Once fails exceeds bytealg.Cutover(i), the loop gives up and switches to the full SIMD search, which does not care about false positives.

Cutover is a one-liner:

go 
// src/internal/bytealg/index_amd64.go:19
// Cutover reports the number of failures of IndexByte we should tolerate
// before switching over to Index.
// n is the number of bytes processed so far.
// See the bytes.Index implementation for details.
func Cutover(n int) int {
	// 1 error per 8 characters, plus a few slop to start.
	return (n + 16) / 8
}

One false positive per eight bytes processed, plus sixteen bytes of slack at the start. It’s a heuristic, and it’s tuned for text.

Note that strings.Index itself is now a one-liner that delegates:

go 
// src/strings/strings.go:1288
func Index(s, substr string) int {
	return stringslite.Index(s, substr)
}

stringslite exists because os (and everything below it) needs a substring search but must not depend on the whole strings package. The strings package imports stringslite; stringslite imports only internal/bytealg and unsafe.

The lengths: MaxLen and MaxBruteForce

The two constants that decide the shape of the ladder are set by the assembly:

go 
// src/internal/bytealg/index_amd64.go:9
const MaxBruteForce = 64

func init() {
	if cpu.X86.HasAVX2 {
		MaxLen = 63
	} else {
		MaxLen = 31
	}
}

MaxLen is the longest needle the vectorised assembly can handle: 63 bytes with AVX2, 31 bytes without. MaxBruteForce is the longest haystack for which the assembly is used directly, because for very short haystacks the call overhead dominates.

MaxLen lives in the shared file, and it is zero on platforms that have no assembly at all:

go 
// src/internal/bytealg/bytealg.go:28
// MaxLen is the maximum length of the string to be searched for (argument b) in Index.
// If MaxLen is not 0, make sure MaxLen >= 4.
var MaxLen int

So on a platform without an assembly Index, MaxLen == 0, the branch n <= bytealg.MaxLen is never true, and the SIMD path is never reached at all. The Go-level loop and Rabin-Karp do all the work.

The build-tag switch

Which implementation exists is decided by build constraints, not by runtime dispatch. On amd64 (and arm64, loong64, s390x, ppc64):

go 
// src/internal/bytealg/index_native.go:5
//go:build amd64 || arm64 || loong64 || s390x || ppc64le || ppc64

package bytealg

// Index returns the index of the first instance of b in a, or -1 if b is not present in a.
// Requires 2 <= len(b) <= MaxLen.
//
//go:noescape
func Index(a, b []byte) int

// IndexString returns the index of the first instance of b in a, or -1 if b is not present in a.
// Requires 2 <= len(b) <= MaxLen.
//
//go:noescape
func IndexString(a, b string) int

and everywhere else:

go 
// src/internal/bytealg/index_generic.go:5
//go:build !amd64 && !arm64 && !loong64 && !s390x && !ppc64le && !ppc64

package bytealg

const MaxBruteForce = 0

// Index returns the index of the first instance of b in a, or -1 if b is not present in a.
// Requires 2 <= len(b) <= MaxLen.
func Index(a, b []byte) int {
	panic("unimplemented")
}

The generic file does not even implement the function — it panics — because the MaxLen == 0 guard means it is never called. It’s a stub to satisfy the compiler.

//go:noescape is the other half of the story: it tells the compiler that the pointers passed in do not escape, so the arguments do not have to be heap-allocated when the call is inlined.

The x86 assembly: a ladder of vector widths

The amd64 implementation is one file with a shared body. The two entry points just shuffle arguments into registers and jump:

asm 
// src/internal/bytealg/index_amd64.s:8
TEXT ·Index(SB),NOSPLIT,$0-56
	MOVQ a_base+0(FP), DI
	MOVQ a_len+8(FP), DX
	MOVQ b_base+24(FP), R8
	MOVQ b_len+32(FP), AX
	MOVQ DI, R10
	LEAQ ret+48(FP), R11
	JMP  indexbody<>(SB)

TEXT ·IndexString(SB),NOSPLIT,$0-40
	MOVQ a_base+0(FP), DI
	MOVQ a_len+8(FP), DX
	MOVQ b_base+16(FP), R8
	MOVQ b_len+24(FP), AX
	MOVQ DI, R10
	LEAQ ret+32(FP), R11
	JMP  indexbody<>(SB)

and the body documents its own register contract:

asm 
// src/internal/bytealg/index_amd64.s:26
// AX: length of string, that we are searching for
// DX: length of string, in which we are searching
// DI: pointer to string, in which we are searching
// R8: pointer to string, that we are searching for
// R11: address, where to put return value
// Note: We want len in DX and AX, because PCMPESTRI implicitly consumes them
TEXT indexbody<>(SB),NOSPLIT,$0
	CMPQ AX, DX
	JA fail
	CMPQ DX, $16
	JAE sse42
no_sse42:
	CMPQ AX, $2
	JA   _3_or_more

The body then dispatches on the needle length through a ladder of specialised loops: 2 bytes, 3 bytes, 4 bytes, 5–7 bytes, 8 bytes, 9–15 bytes, 16 bytes, 17–31 bytes, 32–63 bytes. Each rung compares the leading chunk of the needle against the haystack using the widest instruction that fits, then verifies the tail.

The 16-byte rung is the SSE2 core, and it is the whole trick:

asm 
// src/internal/bytealg/index_amd64.s:145
_16_or_more:
	CMPQ AX, $16
	JA   _17_or_more
	MOVOU (R8), X1
	LEAQ -15(DI)(DX*1), DX
loop16:
	MOVOU (DI), X2
	PCMPEQB X1, X2
	PMOVMSKB X2, SI
	CMPQ  SI, $0xffff
	JE   success
	ADDQ $1,DI
	CMPQ DI,DX
	JB loop16
	JMP fail

MOVOU loads 16 bytes unaligned. PCMPEQB compares them byte by byte in parallel and writes a mask of 0x00/0xff. PMOVMSKB pulls the sign bits of those 16 bytes into a 16-bit integer. If the mask is all ones (0xffff), every byte matched, so we have a hit.

Note that this is a sliding window, not a chunked scan: it advances by one byte per iteration, so it examines every possible alignment. That is the O(n·m)-with-huge-constants approach, vectorised. The skipping between candidate positions is done one level up, in Go, by IndexByte.

The AVX2 rung does the same thing with 32-byte registers:

asm 
// src/internal/bytealg/index_amd64.s:187
// We can get here only when AVX2 is enabled and cutoff for indexShortStr is set to 63
// So no need to check cpuid
_32_or_more:
	CMPQ AX, $32
	JA   _33_to_63
	VMOVDQU (R8), Y1
	LEAQ -31(DI)(DX*1), DX
loop32:
	VMOVDQU (DI), Y2
	VPCMPEQB Y1, Y2, Y3
	VPMOVMSKB Y3, SI
	CMPL  SI, $0xffffffff
	JE   success_avx2
	ADDQ $1,DI
	CMPQ DI,DX
	JB loop32
	JMP fail_avx2

And crucially, at the end it cleans up after itself:

asm 
// src/internal/bytealg/index_amd64.s:228
fail_avx2:
	VZEROUPPER
fail:
	MOVQ $-1, (R11)
	RET
success_avx2:
	VZEROUPPER
	JMP success

VZEROUPPER zeroes the upper 128 bits of the YMM registers. Without it, the dirty upper halves of the YMM registers would cause a penalty on every subsequent SSE instruction — the classic AVX/SSE transition penalty. Every AVX2 exit path pays it.

The SSE4.2 path, and why it is conditional

There is a third path, using the PCMPESTRI instruction, which does a 16-byte string compare and reports the index of the first match, in one instruction:

asm 
// src/internal/bytealg/index_amd64.s:236
sse42:
#ifndef hasSSE42
	CMPB internal∕cpu·X86+const_offsetX86HasSSE42(SB), $1
	JNE no_sse42
#endif
	CMPQ AX, $12
	// PCMPESTRI is slower than normal compare,
	// so using it makes sense only if we advance 4+ bytes per compare
	// This value was determined experimentally and is the ~same
	// on Nehalem (first with SSE42) and Haswell.
	JAE _9_or_more
	LEAQ 16(R8), SI
	TESTW $0xff0, SI
	JEQ no_sse42
	MOVOU (R8), X1
	LEAQ -15(DI)(DX*1), SI
	MOVQ $16, R9
	SUBQ AX, R9 // We advance by 16-len(sep) each iteration, so precalculate it into R9
	PCALIGN $16
loop_sse42:
	// 0x0c means: unsigned byte compare (bits 0,1 are 00)
	// for equality (bits 2,3 are 11)
	// result is not masked or inverted (bits 4,5 are 00)
	// and corresponds to first matching byte (bit 6 is 0)
	PCMPESTRI $0x0c, (DI), X1
	// CX == 16 means no match,
	// CX > R9 means partial match at the end of the string,
	// otherwise sep is at offset CX from X1 start
	CMPQ CX, R9
	JBE sse42_success
	ADDQ R9, DI
	CMPQ DI, SI
	JB loop_sse42

Three things to note:

  1. The CPU feature check is done at runtime (internal/cpu·X86+...HasSSE42), not at build time, because the same binary has to run on both kinds of x86 chip. The #ifndef hasSSE42 is a build-time variant for the purego/generic builds.
  2. It is only used for needles of 12 bytes or more, because PCMPESTRI has a fixed latency and the comment says it is “slower than normal compare” — it only pays off if you advance 4+ bytes per compare.
  3. The needle must be 16-byte aligned (TESTW $0xff0, SI) or the whole path is skipped, because PCMPESTRI requires aligned memory operands.

IndexByte is the workhorse. It gets its own assembly file, and it is noticeably different in shape from Index — it uses a chunked scan with BSFL to find the first set bit, rather than a sliding window:

asm 
// src/internal/bytealg/indexbyte_amd64.s:29
TEXT	indexbytebody<>(SB), NOSPLIT, $0
	// Shuffle X0 around so that each byte contains
	// the character we're looking for.
	MOVD AX, X0
	PUNPCKLBW X0, X0
	PUNPCKLBW X0, X0
	PSHUFL $0, X0, X0

	CMPQ BX, $16
	JLT small

	MOVQ SI, DI

	CMPQ BX, $32
	JA avx2
sse:
	LEAQ	-16(SI)(BX*1), AX	// AX = address of last 16 bytes
	JMP	sseloopentry

	PCALIGN $16
sseloop:
	// Move the next 16-byte chunk of the data into X1.
	MOVOU	(DI), X1
	// Compare bytes in X0 to X1.
	PCMPEQB	X0, X1
	// Take the top bit of each byte in X1 and put the result in DX.
	PMOVMSKB X1, DX
	// Find first set bit, if any.
	BSFL	DX, DX
	JNZ	ssesuccess
	// Advance to next block.
	ADDQ	$16, DI

PUNPCKLBW + PUNPCKLBW + PSHUFL $0 is a hand-rolled broadcast: it takes the single byte in AL and smears it across all 16 bytes of X0. Then PCMPEQB compares all 16 haystack bytes against it in one instruction, PMOVMSKB gathers the results into a bitmask, and BSFL (“bit scan forward, long”) finds the index of the lowest set bit — the position of the first matching byte.

The AVX2 version uses a dedicated broadcast instruction and VPTEST to check the whole mask at once:

asm 
// src/internal/bytealg/indexbyte_amd64.s:120
avx2:
#ifndef hasAVX2
	CMPB   internal∕cpu·X86+const_offsetX86HasAVX2(SB), $1
	JNE sse
#endif
	MOVD AX, X0
	LEAQ -32(SI)(BX*1), R11
	VPBROADCASTB  X0, Y1

	PCALIGN $32
avx2_loop:
	VMOVDQU (DI), Y2
	VPCMPEQB Y1, Y2, Y3
	VPTEST Y3, Y3
	JNZ avx2success
	ADDQ $32, DI
	CMPQ DI, R11
	JLT avx2_loop
	MOVQ R11, DI
	VMOVDQU (DI), Y2
	VPCMPEQB Y1, Y2, Y3
	VPTEST Y3, Y3
	JNZ avx2success
	VZEROUPPER
	MOVQ $-1, (R8)
	RET

VPBROADCASTB broadcasts the target byte to all 32 bytes of Y1 in one instruction — no shuffling needed. VPTEST sets the flags if any bit of the comparison mask is set, so a single JNZ decides whether the chunk contains the byte at all. Only on a hit does it pay for VPMOVMSKB + BSFL to find the exact position.

The small path handles haystacks shorter than 16 bytes, and it is where the careful programmers had to be:

asm 
// src/internal/bytealg/indexbyte_amd64.s:88
// handle for lengths < 16
small:
	TESTQ	BX, BX
	JEQ	failure

	// Check if we'll load across a page boundary.
	LEAQ	16(SI), AX
	TESTW	$0xff0, AX
	JEQ	endofpage

	MOVOU	(SI), X1 // Load data
	PCMPEQB	X0, X1	// Compare target byte with each byte in data.
	PMOVMSKB X1, DX	// Move result bits to integer register.
	BSFL	DX, DX	// Find first set bit.
	JZ	failure	// No set bit, failure.
	CMPL	DX, BX
	JAE	failure	// Match is past end of data.
	MOVQ	DX, (R8)
	RET

A 16-byte load that straddles a page boundary can fault, even if only one byte of the string is valid. So the code checks whether SI+16 crosses a 4 KiB page; if it does, it loads the 16 bytes ending at the end of the string instead (endofpage), which is always in-bounds.

Rabin-Karp, for needles that are too long

A needle longer than 63 bytes cannot use the vector path. For those, Go switches to Rabin-Karp — rolling hash, O(n) regardless of needle length:

go 
// src/internal/bytealg/bytealg.go:32
// primeRK is the prime base used in Rabin-Karp algorithm.
const primeRK = 16777619

// hashStr returns the hash and the appropriate multiplicative
// factor for use in Rabin-Karp algorithm.
func hashStr[T string | []byte](sep T) (uint32, uint32) {
	hash := uint32(0)
	for i := 0; i < len(sep); i++ {
		hash = hash*primeRK + uint32(sep[i])
	}
	var pow, sq uint32 = 1, primeRK
	for i := len(sep); i > 0; i >>= 1 {
		if i&1 != 0 {
			pow *= sq
		}
		sq *= sq
	}
	return hash, pow
}
go 
// src/internal/bytealg/bytealg.go:69
// IndexRabinKarp uses the Rabin-Karp search algorithm to return the index of the
// first occurrence of sep in s, or -1 if not present.
func IndexRabinKarp[T string | []byte](s, sep T) int {
	// Rabin-Karp search
	hashss, pow := hashStr(sep)
	n := len(sep)
	var h uint32
	for i := 0; i < n; i++ {
		h = h*primeRK + uint32(s[i])
	}
	if h == hashss && string(s[:n]) == string(sep) {
		return 0
	}
	for i := n; i < len(s); {
		h *= primeRK
		h += uint32(s[i])
		h -= pow * uint32(s[i-n])
		i++
		if h == hashss && string(s[i-n:i]) == string(sep) {
			return i - n
		}
	}
	return -1
}

The rolling update is the classic h = h*primeRK + new - pow*old: the multiplicative factor pow is primeRK^(len(sep)-1) computed by exponentiation by squaring, so removing the outgoing byte costs one multiply. Hash matches are always verified with a real comparison, so Rabin-Karp here is exact, not probabilistic.

The base 16777619 is the 32-bit prime used by FNV-1a. It is chosen for good avalanche behaviour in the low bits, which matters because the comparison is on the full 32-bit hash.

bytes and the other entry points

bytes.Index has the same ladder but is written out separately, with the comments that explain the reasoning:

go 
// src/bytes/bytes.go:1317
// Index returns the index of the first instance of sep in s, or -1 if sep is not present in s.
func Index(s, sep []byte) int {
	n := len(sep)
	switch {
	case n == 0:
		return 0
	case n == 1:
		return IndexByte(s, sep[0])
	case n == len(s):
		if Equal(sep, s) {
			return 0
		}
		return -1
	case n > len(s):
		return -1
	case n <= bytealg.MaxLen:
		// Use brute force when s and sep both are small
		if len(s) <= bytealg.MaxBruteForce {
			return bytealg.Index(s, sep)
		}
		c0 := sep[0]
		c1 := sep[1]
		i := 0
		t := len(s) - n + 1
		fails := 0
		for i < t {
			if s[i] != c0 {
				// IndexByte is faster than bytealg.Index, so use it as long as
				// we're not getting lots of false positives.
				o := IndexByte(s[i+1:t], c0)
				if o < 0 {
					return -1
				}
				i += o + 1
			}
			if s[i+1] == c1 && Equal(s[i:i+n], sep) {
				return i
			}
			fails++
			i++
			// Switch to bytealg.Index when IndexByte produces too many false positives.
			if fails > bytealg.Cutover(i) {
				r := bytealg.Index(s[i:], sep)
				if r >= 0 {
					return r + i
				}
				return -1
			}
		}
		return -1
	}

and then the long-needle case, which has a completely different cutover rule and an honest comment about it:

go 
// src/bytes/bytes.go:1384
		i++
		fails++
		if fails >= 4+i>>4 && i < t {
			// Give up on IndexByte, it isn't skipping ahead
			// far enough to be better than Rabin-Karp.
			// Experiments (using IndexPeriodic) suggest
			// the cutover is about 16 byte skips.
			// TODO: if large prefixes of sep are matching
			// we should cutover at even larger average skips,
			// because Equal becomes that much more expensive.
			// This code does not take that effect into account.
			j := bytealg.IndexRabinKarp(s[i:], sep)
			if j < 0 {
				return -1
			}
			return i + j
		}

4+i>>4 is roughly “one false positive per 16 bytes”, matching the comment’s “about 16 byte skips”. The TODO is a real one: the cutover ignores the cost of the verification Equal, which grows with the needle length.

The simpler entry points are thin:

go 
// src/strings/strings.go:61
// Contains reports whether substr is within s.
func Contains(s, substr string) bool {
	return Index(s, substr) >= 0
}
go 
// src/bytes/bytes.go:77
// Contains reports whether subslice is within b.
func Contains(b, subslice []byte) bool {
	return Index(b, subslice) != -1
}

and strings.IndexByte / bytes.IndexByte go straight to the assembly:

go 
// src/bytes/bytes.go:98
// IndexByte returns the index of the first instance of c in b, or -1 if c is not present in b.
func IndexByte(b []byte, c byte) int {
	return bytealg.IndexByte(b, c)
}

The odd one out: LastIndexByte has no assembly

Worth knowing, because it surprises people: searching backwards for a single byte is a plain Go loop.

go 
// src/internal/bytealg/lastindexbyte_generic.go:7
func LastIndexByte(s []byte, c byte) int {
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == c {
			return i
		}
	}
	return -1
}

func LastIndexByteString(s string, c byte) int {
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == c {
			return i
		}
	}
	return -1
}

There is no lastindexbyte_amd64.s in the tree. The forward search is vectorised; the backward one is not. Presumably because the forward IndexByte is used on the hot skip path of Index while LastIndexByte is rarely on a hot path at all.

LastIndex for multi-byte needles uses Rabin-Karp run backwards:

go 
// src/strings/strings.go:83
func LastIndex(s, substr string) int {
	n := len(substr)
	switch {
	case n == 0:
		return len(s)
	case n == 1:
		return bytealg.LastIndexByteString(s, substr[0])
	case n == len(s):
		if substr == s {
			return 0
		}
		return -1
	case n > len(s):
		return -1
	}
	return bytealg.LastIndexRabinKarp(s, substr)
}

Compare: the same trick, for ordering

While we’re here: bytealg.Compare is the function behind strings.Compare and, via go:linkname, behind the runtime’s own cmpstring. It shares the same structure — a ladder of widths, with a runtime AVX2 check:

asm 
// src/internal/bytealg/compare_amd64.s:9
TEXT ·Compare<ABIInternal>(SB),NOSPLIT,$0-56
	// AX = a_base (want in SI)
	// BX = a_len  (want in BX)
	// CX = a_cap  (unused)
	// DI = b_base (want in DI)
	// SI = b_len  (want in DX)
	// R8 = b_cap  (unused)
	MOVQ	SI, DX
	MOVQ	AX, SI
	JMP	cmpbody<>(SB)

TEXT runtime·cmpstring<ABIInternal>(SB),NOSPLIT,$0-40
asm 
// src/internal/bytealg/compare_amd64.s:55
loop:
	CMPQ	R8, $16
	JBE	_0through16
	MOVOU	(SI), X0
	MOVOU	(DI), X1
	PCMPEQB X0, X1
	PMOVMSKB X1, AX
	XORQ	$0xffff, AX	// convert EQ to NE
	JNE	diff16	// branch if at least one byte is not equal
	ADDQ	$16, SI
	ADDQ	$16, DI
	SUBQ	$16, R8
	JMP	loop

The comparison version chunks forward (16 bytes at a time, advancing by 16) rather than sliding, because it only needs to find the first differing byte, not the first match. PMOVMSKB + BSFQ gives the index of the first difference directly.

Trade-offs

What the tiered design buys: strings.Index on a 1 MB haystack with a 20-byte needle is a handful of vectorised scans, not 20 million byte comparisons. The IndexByte skip turns the common case into “find the first byte, check the second byte, verify the rest”, and the vectorised assembly makes even the “find the first byte” step cheap.

What it costs:

  • A long needle is slower than a short one, even when the needle is absent. The vector path compares 16 or 32 bytes of the needle against every alignment, so cost grows with needle length up to 63 bytes. Past 63 bytes you drop to Rabin-Karp, which is O(n) but with a much bigger constant (a multiply per byte).
  • The worst case is still O(n·m). There is no skip table. If the haystack is full of the needle’s first byte and the needle never matches, the Go-level loop does O(n) candidate checks — mitigated by the Cutover heuristic, which eventually hands off to the vector path.
  • The assembly is arch-specific and hand-maintained. Seven architectures have an Index implementation; the rest fall back to the generic path.
  • The CPU feature check is at runtime, so the branch predictor has to deal with it, and the code paths differ between chips.

Caveats

The behaviour differs by architecture. On a platform without assembly, bytealg.MaxLen is 0 and the whole vector path disappears. A program that is fast on amd64 may be several times slower on, say, a 32-bit ARM target for the same search.

strings.Index is not UTF-8 aware. It finds a byte sequence, not a character sequence. Searching for a multi-byte rune works only because the rune’s UTF-8 encoding is what you are looking for. There is no strings.IndexRune-style rune search in the standard library beyond IndexRune, which decodes runes.

The generic Index panics. internal/bytealg.Index on a non-assembly platform is panic("unimplemented"). It is unreachable from strings/bytes because of the MaxLen guard, but it means you cannot call bytealg.Index directly on those platforms.

bytealg.Index requires 2 <= len(needle) <= MaxLen. Calling it with a longer or shorter needle is undefined; the callers in strings and bytes enforce the bounds themselves.

Rabin-Karp is not probabilistic here. It verifies every hash hit with a real comparison, so it is exact. But it does mean a pathological input (all bytes equal, needle of zeros) can produce many hash hits.

LastIndexByte is not vectorised. If you are scanning backwards over large buffers in a hot loop, you are leaving a lot on the table.

Wrapping up

The one thing to remember: strings.Index is a dispatcher, not an algorithm. The algorithm is a tiered ladder — single byte, then short needle in vectorised assembly, then Rabin-Karp for long needles — and the tiering decisions are made from bytealg.MaxLen, bytealg.MaxBruteForce and the Cutover heuristic, all of which are architecture-dependent.

The part people get wrong: assuming there is a skip table. There is not. The x86 assembly compares the needle against the haystack in 16- or 32-byte chunks at every alignment; the skipping between candidate positions is done one level up in Go, by IndexByte on the needle’s first byte. If you are porting a Boyer-Moore implementation into Go expecting it to beat the standard library, measure first.

What to go do about it: if you are doing repeated searches, hoist the first-byte check yourself — search for the first byte, then verify — and keep needles under 63 bytes so the vector path stays available. And benchmark on the architecture you actually ship to; the difference between the assembly path and the generic path is large.

Further reading

  • src/internal/bytealg/index_amd64.s — the x86 Index / IndexString assembly
  • src/internal/bytealg/index_amd64.go — MaxLen, MaxBruteForce, Cutover
  • src/internal/bytealg/index_native.go — the //go:build gate for assembly platforms
  • src/internal/bytealg/index_generic.go — the stub for platforms without assembly
  • src/internal/bytealg/indexbyte_amd64.s — the single-byte search assembly
  • src/internal/bytealg/indexbyte_generic.go — the generic single-byte search
  • src/internal/bytealg/lastindexbyte_generic.go — the un-vectorised backwards search
  • src/internal/bytealg/bytealg.go — hashStr, IndexRabinKarp, LastIndexRabinKarp
  • src/internal/bytealg/compare_amd64.s — Compare and runtime.cmpstring
  • src/internal/stringslite/strings.go — the shared Index used by strings and os
  • src/strings/strings.go — Contains, IndexByte, LastIndex, LastIndexByte
  • src/bytes/bytes.go — Contains, Index, IndexByte, LastIndex

GoInternalsStringsAssemblyPerformance