simd

func Memchr ¶

func Memchr(haystack []byte, needle byte) int

Memchr returns the index of the first instance of needle in haystack, or -1 if needle is not present in haystack.

This function is equivalent to bytes.IndexByte but uses SIMD instructions (AVX2/SSE4.2) when available on x86-64 platforms. It automatically falls back to pure Go implementation on other architectures.

Performance characteristics (on x86-64 with AVX2):

• Small inputs (< 64 bytes): approximately same as bytes.IndexByte
• Medium inputs (64B - 4KB): 2-5x faster than bytes.IndexByte
• Large inputs (> 4KB): 8-15x faster than bytes.IndexByte

The function uses aligned vector loads and processes 32 bytes per iteration when AVX2 is available, or 16 bytes with SSE4.2.

Example:

haystack := []byte("hello world")
pos := simd.Memchr(haystack, 'o')
if pos != -1 {
    fmt.Printf("Found 'o' at position %d\n", pos) // Output: Found 'o' at position 4
}

Example with not found:

haystack := []byte("hello world")
pos := simd.Memchr(haystack, 'x')
if pos == -1 {
    fmt.Println("Character 'x' not found")
}

func Memchr2 ¶

func Memchr2(haystack []byte, needle1, needle2 byte) int

Memchr2 returns the index of the first instance of either needle1 or needle2 in haystack, or -1 if neither is present.

This function is significantly faster than calling Memchr twice or using a loop, as it checks both bytes simultaneously using SIMD instructions. The order of needles does not affect performance.

Performance characteristics (on x86-64 with AVX2):

• Processes both needle comparisons in parallel using vector operations
• Same throughput as Memchr (no overhead for checking two bytes)
• 5-10x faster than sequential search on large inputs

The function returns the position of whichever needle appears first in haystack. If both needles appear at the same position (impossible unless needle1 == needle2), the result is deterministic but unspecified.

Example:

haystack := []byte("hello world")
pos := simd.Memchr2(haystack, 'o', 'w')
if pos != -1 {
    fmt.Printf("Found 'o' or 'w' at position %d\n", pos) // Output: Found 'o' or 'w' at position 4
}

Example searching for punctuation:

text := []byte("Hello, world!")
pos := simd.Memchr2(text, ',', '!')
if pos != -1 {
    fmt.Printf("Found punctuation at position %d\n", pos) // Output: Found punctuation at position 5
}

func Memchr3 ¶

func Memchr3(haystack []byte, needle1, needle2, needle3 byte) int

Memchr3 returns the index of the first instance of needle1, needle2, or needle3 in haystack, or -1 if none are present.

This function checks three bytes simultaneously using SIMD instructions, making it much faster than multiple sequential searches or a loop with three comparisons per iteration.

Performance characteristics (on x86-64 with AVX2):

• Processes all three needle comparisons in parallel
• Same throughput as Memchr and Memchr2
• Ideal for searching character classes (e.g., whitespace, delimiters)

The function returns the position of whichever needle appears first in haystack. The order of needle parameters does not affect performance.

Example searching for whitespace:

text := []byte("hello\tworld\nfoo")
pos := simd.Memchr3(text, ' ', '\t', '\n')
if pos != -1 {
    fmt.Printf("Found whitespace at position %d\n", pos) // Output: Found whitespace at position 5
}

Example searching for multiple delimiters:

csv := []byte("name,age;city")
pos := simd.Memchr3(csv, ',', ';', '|')
if pos != -1 {
    fmt.Printf("Found delimiter at position %d\n", pos) // Output: Found delimiter at position 4
}

func Memmem ¶

func Memmem(haystack, needle []byte) int

Memmem returns the index of the first instance of needle in haystack, or -1 if needle is not present in haystack.

This is equivalent to bytes.Index but uses SIMD acceleration via memchr for the first byte search, followed by fast verification. The implementation combines a rare byte heuristic with SIMD-accelerated scanning to achieve significant speedup over stdlib.

Performance characteristics (vs bytes.Index):

• Short needles (2-8 bytes): 3-5x faster
• Medium needles (8-32 bytes): 5-10x faster
• Long needles (> 32 bytes): 2-5x faster

Algorithm:

The function uses a rare byte heuristic combined with SIMD acceleration:

1. Identify the rarest byte in needle (using position-based heuristic)
2. Use Memchr to find candidates for this byte in haystack (SIMD-accelerated)
3. For each candidate, verify the full needle match
4. Return position of first match or -1 if not found

For longer needles (> 32 bytes), a simplified Two-Way string matching approach is used to maintain O(n+m) complexity and avoid pathological cases.

Example:

haystack := []byte("hello world")
needle := []byte("world")
pos := simd.Memmem(haystack, needle)
// pos == 6

Example with not found:

haystack := []byte("hello world")
needle := []byte("xyz")
pos := simd.Memmem(haystack, needle)
// pos == -1

Example with repeated patterns:

haystack := []byte("aaaaaabaaaa")
needle := []byte("aab")
pos := simd.Memmem(haystack, needle)
// pos == 5

package main

import (
	"fmt"

	"github.com/coregx/coregex/simd"
)

func main() {
	haystack := []byte("hello world")
	needle := []byte("world")

	pos := simd.Memmem(haystack, needle)
	if pos != -1 {
		fmt.Printf("Found at position %d\n", pos)
	} else {
		fmt.Println("Not found")
	}
}

Output:

Found at position 6

package main

import (
	"fmt"

	"github.com/coregx/coregex/simd"
)

func main() {
	haystack := []byte("hello")
	needle := []byte("")

	pos := simd.Memmem(haystack, needle)
	fmt.Printf("Empty needle found at position %d\n", pos)
}

Output:

Empty needle found at position 0

package main

import (
	"fmt"

	"github.com/coregx/coregex/simd"
)

func main() {
	header := []byte("Content-Type: application/json\r\nContent-Length: 1234\r\n")
	needle := []byte("Content-Length:")

	pos := simd.Memmem(header, needle)
	if pos != -1 {
		fmt.Printf("Found header at position %d\n", pos)
	}
}

Output:

Found header at position 32

package main

import (
	"fmt"

	"github.com/coregx/coregex/simd"
)

func main() {
	json := []byte(`{"name":"John","age":30,"city":"New York"}`)
	needle := []byte(`"age"`)

	pos := simd.Memmem(json, needle)
	if pos != -1 {
		fmt.Printf("Found 'age' key at position %d\n", pos)
	}
}

Output:

Found 'age' key at position 15

package main

import (
	"fmt"

	"github.com/coregx/coregex/simd"
)

func main() {
	haystack := []byte("hello world")
	needle := []byte("xyz")

	pos := simd.Memmem(haystack, needle)
	if pos == -1 {
		fmt.Println("Not found")
	}
}

Output:

Not found

package main

import (
	"fmt"

	"github.com/coregx/coregex/simd"
)

func main() {
	dna := []byte("ATATATGCGCGC")
	pattern := []byte("GCGC")

	pos := simd.Memmem(dna, pattern)
	if pos != -1 {
		fmt.Printf("Pattern found at position %d\n", pos)
		fmt.Printf("Context: %s\n", dna[pos:pos+len(pattern)])
	}
}

Output:

Pattern found at position 6
Context: GCGC