ycdemo / fzf / src/ algo/ SIMD.md

SIMD byte search: indexByteTwo / lastIndexByteTwo

What these functions do

indexByteTwo(s []byte, b1, b2 byte) int -- returns the index of the first occurrence of b1 or b2 in s, or -1.

lastIndexByteTwo(s []byte, b1, b2 byte) int -- returns the index of the last occurrence of b1 or b2 in s, or -1.

They are used by the fuzzy matching algorithm (algo.go) to skip ahead during case-insensitive search. Instead of calling bytes.IndexByte twice (once for lowercase, once for uppercase), a single SIMD pass finds both at once.

File layout

FilePurpose
indexbyte2_arm64.goGo declarations (//go:noescape) for ARM64
indexbyte2_arm64.sARM64 NEON assembly (32-byte aligned blocks, syndrome extraction)
indexbyte2_amd64.goGo declarations + AVX2 runtime detection for AMD64
indexbyte2_amd64.sAMD64 AVX2/SSE2 assembly with CPUID dispatch
indexbyte2_other.goPure Go fallback for all other architectures
indexbyte2_test.goUnit tests, exhaustive tests, fuzz tests, and benchmarks

How the SIMD implementations work

ARM64 (NEON):

  • Broadcasts both needle bytes into NEON registers (VMOV).
  • Processes 32-byte aligned chunks. For each chunk, compares all bytes against both needles (VCMEQ), ORs the results (VORR), and builds a 64-bit syndrome with 2 bits per byte.
  • indexByteTwo uses RBIT + CLZ to find the lowest set bit (first match).
  • lastIndexByteTwo scans backward and uses CLZ on the raw syndrome to find the highest set bit (last match).
  • Handles alignment and partial first/last blocks with bit masking.
  • Adapted from Go's internal/bytealg/indexbyte_arm64.s.

AMD64 (AVX2 with SSE2 fallback):

  • At init time, cpuHasAVX2() checks CPUID + XGETBV for AVX2 and OS YMM support. The result is cached in _useAVX2.
  • AVX2 path (inputs >= 32 bytes, when available):
    • Broadcasts both needles via VPBROADCASTB.
    • Processes 32-byte blocks: VPCMPEQB against both needles, VPOR, then VPMOVMSKB to get a 32-bit mask.
    • 5 instructions per loop iteration (vs 7 for SSE2) at 2x the throughput.
    • VZEROUPPER before every return to avoid SSE/AVX transition penalties.
  • SSE2 fallback (inputs < 32 bytes, or CPUs without AVX2):
    • Broadcasts via PUNPCKLBW + PSHUFL.
    • Processes 16-byte blocks: PCMPEQB, POR, PMOVMSKB.
    • Small inputs (<16 bytes) are handled with page-boundary-safe loads.
  • Both paths use BSFL (forward) / BSRL (reverse) for bit scanning.
  • Adapted from Go's internal/bytealg/indexbyte_amd64.s.

Fallback (other platforms):

  • indexByteTwo uses two bytes.IndexByte calls with scope-limiting (search b1 first, then limit the b2 search to s[:i1]).
  • lastIndexByteTwo uses a simple backward for loop.

Running tests

# Unit + exhaustive tests
go test ./src/algo/ -run 'TestIndexByteTwo|TestLastIndexByteTwo' -v

# Fuzz tests (run for 10 seconds each)
go test ./src/algo/ -run '^
		
		
		
		
	

 -fuzz FuzzIndexByteTwo -fuzztime 10s
go test ./src/algo/ -run '^
		
		
		
		
	

 -fuzz FuzzLastIndexByteTwo -fuzztime 10s

# Cross-architecture: test amd64 on an arm64 Mac (via Rosetta)
GOARCH=amd64 go test ./src/algo/ -run 'TestIndexByteTwo|TestLastIndexByteTwo' -v
GOARCH=amd64 go test ./src/algo/ -run '^
		
		
		
		
	

 -fuzz FuzzIndexByteTwo -fuzztime 10s
GOARCH=amd64 go test ./src/algo/ -run '^
		
		
		
		
	

 -fuzz FuzzLastIndexByteTwo -fuzztime 10s

Running micro-benchmarks

# All indexByteTwo / lastIndexByteTwo benchmarks
go test ./src/algo/ -bench 'IndexByteTwo' -benchmem

# Specific size
go test ./src/algo/ -bench 'IndexByteTwo_1000'

Each benchmark compares the SIMD asm implementation against reference implementations (2xIndexByte using bytes.IndexByte, and a simple loop).

Correctness verification

The assembly is verified by three layers of testing:

  1. Table-driven tests -- known inputs with expected outputs.
  2. Exhaustive tests -- all lengths 0–256, every match position, no-match cases, and both-bytes-present cases, compared against a simple loop reference.
  3. Fuzz tests -- randomized inputs via testing.F, compared against the same loop reference.
-fuzz FuzzIndexByteTwo -fuzztime 10s\ngo test ./src/algo/ -run '^ -fuzz FuzzLastIndexByteTwo -fuzztime 10s\n\n# Cross-architecture: test amd64 on an arm64 Mac (via Rosetta)\nGOARCH=amd64 go test ./src/algo/ -run 'TestIndexByteTwo|TestLastIndexByteTwo' -v\nGOARCH=amd64 go test ./src/algo/ -run '^ -fuzz FuzzIndexByteTwo -fuzztime 10s\nGOARCH=amd64 go test ./src/algo/ -run '^ -fuzz FuzzLastIndexByteTwo -fuzztime 10s\n```\n\n## Running micro-benchmarks\n\n```bash\n# All indexByteTwo / lastIndexByteTwo benchmarks\ngo test ./src/algo/ -bench 'IndexByteTwo' -benchmem\n\n# Specific size\ngo test ./src/algo/ -bench 'IndexByteTwo_1000'\n```\n\nEach benchmark compares the SIMD `asm` implementation against reference\nimplementations (`2xIndexByte` using `bytes.IndexByte`, and a simple `loop`).\n\n## Correctness verification\n\nThe assembly is verified by three layers of testing:\n\n1. **Table-driven tests** -- known inputs with expected outputs.\n2. **Exhaustive tests** -- all lengths 0–256, every match position, no-match\n cases, and both-bytes-present cases, compared against a simple loop\n reference.\n3. **Fuzz tests** -- randomized inputs via `testing.F`, compared against the\n same loop reference.\n","preview":null,"history":null,"version":"330fc865db30cdaee3a8ff822ed7f83cf80eb12a"},"/_session?shell=1":null,"#fences":[["snippet.bash\u0000# Unit + exhaustive tests\ngo test ./src/algo/ -run 'TestIndexByteTwo|TestLastIndexByteTwo' -v\n\n# Fuzz tests (run for 10 seconds each)\ngo test ./src/algo/ -run '^ -fuzz FuzzIndexByteTwo -fuzztime 10s\ngo test ./src/algo/ -run '^ -fuzz FuzzLastIndexByteTwo -fuzztime 10s\n\n# Cross-architecture: test amd64 on an arm64 Mac (via Rosetta)\nGOARCH=amd64 go test ./src/algo/ -run 'TestIndexByteTwo|TestLastIndexByteTwo' -v\nGOARCH=amd64 go test ./src/algo/ -run '^ -fuzz FuzzIndexByteTwo -fuzztime 10s\nGOARCH=amd64 go test ./src/algo/ -run '^ -fuzz FuzzLastIndexByteTwo -fuzztime 10s",[[{"text":"# Unit + exhaustive tests","color":"var(--code-6a737d, #6A737D)"}],[{"text":"go","color":"var(--code-6f42c1, #6F42C1)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"test","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"./src/algo/","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-run","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"'TestIndexByteTwo|TestLastIndexByteTwo'","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-v","color":"var(--code-005cc5, #005CC5)"}],[],[{"text":"# Fuzz tests (run for 10 seconds each)","color":"var(--code-6a737d, #6A737D)"}],[{"text":"go","color":"var(--code-6f42c1, #6F42C1)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"test","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"./src/algo/","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-run","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"'^ ","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-fuzz","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"FuzzIndexByteTwo","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-fuzztime","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"10s","color":"var(--code-032f62, #032F62)"}],[{"text":"go","color":"var(--code-6f42c1, #6F42C1)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"test","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"./src/algo/","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-run","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"'^ ","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-fuzz","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"FuzzLastIndexByteTwo","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-fuzztime","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"10s","color":"var(--code-032f62, #032F62)"}],[],[{"text":"# Cross-architecture: test amd64 on an arm64 Mac (via Rosetta)","color":"var(--code-6a737d, #6A737D)"}],[{"text":"GOARCH","color":"var(--code-24292e, #24292E)"},{"text":"=","color":"var(--code-d73a49, #D73A49)"},{"text":"amd64","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"go","color":"var(--code-6f42c1, #6F42C1)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"test","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"./src/algo/","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-run","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"'TestIndexByteTwo|TestLastIndexByteTwo'","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-v","color":"var(--code-005cc5, #005CC5)"}],[{"text":"GOARCH","color":"var(--code-24292e, #24292E)"},{"text":"=","color":"var(--code-d73a49, #D73A49)"},{"text":"amd64","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"go","color":"var(--code-6f42c1, #6F42C1)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"test","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"./src/algo/","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-run","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"'^ ","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-fuzz","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"FuzzIndexByteTwo","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-fuzztime","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"10s","color":"var(--code-032f62, #032F62)"}],[{"text":"GOARCH","color":"var(--code-24292e, #24292E)"},{"text":"=","color":"var(--code-d73a49, #D73A49)"},{"text":"amd64","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"go","color":"var(--code-6f42c1, #6F42C1)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"test","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"./src/algo/","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-run","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"'^ ","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-fuzz","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"FuzzLastIndexByteTwo","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-fuzztime","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"10s","color":"var(--code-032f62, #032F62)"}]]],["snippet.bash\u0000# All indexByteTwo / lastIndexByteTwo benchmarks\ngo test ./src/algo/ -bench 'IndexByteTwo' -benchmem\n\n# Specific size\ngo test ./src/algo/ -bench 'IndexByteTwo_1000'",[[{"text":"# All indexByteTwo / lastIndexByteTwo benchmarks","color":"var(--code-6a737d, #6A737D)"}],[{"text":"go","color":"var(--code-6f42c1, #6F42C1)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"test","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"./src/algo/","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-bench","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"'IndexByteTwo'","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-benchmem","color":"var(--code-005cc5, #005CC5)"}],[],[{"text":"# Specific size","color":"var(--code-6a737d, #6A737D)"}],[{"text":"go","color":"var(--code-6f42c1, #6F42C1)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"test","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"./src/algo/","color":"var(--code-032f62, #032F62)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"-bench","color":"var(--code-005cc5, #005CC5)"},{"text":" ","color":"var(--code-24292e, #24292E)"},{"text":"'IndexByteTwo_1000'","color":"var(--code-032f62, #032F62)"}]]]]}