Faster search for fixed patterns with Go

go get



bmatch is faster fixed pattern search for Go.

Go provides different search mechanisms to find the indices of a fixed string or byte pattern, that are backed by different search algorithms:

  • strings.Index switches by the pattern length
    • 1: generic assembler function strings•IndexByte(..) (i.e. for OSX/darwin see /usr/local/go/src/runtime/asm_amd64.s)
    • 1-31: generic assembler function strings•indexShortString(..) (i.e. for OSX/darwin see /usr/local/go/src/runtime/asm_amd64.s)
    • >31 calling a Rabin-Karp search algorithm using a rolling addition hash and use string comparison to prove the result
  • strings.Replace for single string replacing invokes a Boyer-Moore search over a string in /usr/local/go/src/strings/search.go implementing a stringFinder type
  • bytes.Index using generic assembler code (bytes•IndexByte(..)) to find the index of the first element of the pattern (i.e. for OSX/darwin see /usr/local/go/src/runtime/asm_amd64.s) and then compares the following sequence using another assembler function (Equal(..)).

The before mentioned assembler routines compare each byte of the haystack one by one. See unsafeMEMCHR.go for a faster approach. All but the Boyer-Moore search are relatively slow - even in comparison to python str.find function (implemented in C). bmatch's underlying algorithms outperform all of Go's search functions.


Install bmatch by the usual

go get

In your go code use import "" and apply it on []byte types of the haystack (byte sequence to search in) and needle (pattern to search for).

index, err := bmatch.Index(&haystack, &needle) gives the first (left) index or -1 if not present,

indices, err := bmatch.FindAll(&haystack, &needle) to get an []int array with indices of (overlapping!) occurrences, or

count, err := bmatch.Count(&haystack, &needle) to get the number of (overlapping!) occurences of needle in haystack.

Benchmarks (go test -bench . cpu=1)

 Haystack: ./ loaded (3013205 bytes)
 Alphabet size: 93

 BenchmarkM_Bmatch_10_C                    1    1002289595 ns/op 
 BenchmarkM_BoyerMoore_10_C                1    2683892806 ns/op
 BenchmarkM_BytesIndex_10_C                1    2630128009 ns/op
 BenchmarkM_Bmatch_30_C                    2     528011588 ns/op
 BenchmarkM_BoyerMoore_30_C                1    1402345246 ns/op
 BenchmarkM_BytesIndex_30_C                1    2654263863 ns/op
 BenchmarkM_Bmatch_1024_C                 20     105107250 ns/op
 BenchmarkM_BoyerMoore_1024_C              5     214846485 ns/op
 BenchmarkM_BytesIndex_1024_C              1    2592599288 ns/op
 BenchmarkM_Bmatch_30_FI                  10     104080809 ns/op
 BenchmarkM_BoyerMoore_30_FI               5     245957698 ns/op
 BenchmarkM_StringsIndex_30_FI             3     392142229 ns/op
 BenchmarkM_BytesIndex_30_FI               2     776670641 ns/op
 BenchmarkM_Bmatch_1024_FI                30      43820654 ns/op
 BenchmarkM_BoyerMoore_1024_FI            10     103821315 ns/op
 BenchmarkM_StringsIndex_1024_FI           1    1306085958 ns/op
 BenchmarkM_BytesIndex_1024_FI             1    1276277951 ns/op

on a MacBookPro 2013 with i7 and 8GB Ram searching for 500 random patterns plus 20 patterns that are not present in the "1995 CIA World Factbook" (~3MB english natural text). Benchmark naming: .._searchFunction_patternMaximumLength_C=count|FI=first left Index

go test will try to download the test corpus from if it is not present in the folder.

bmatch.go (C)opyright 2016 Andreas Briese, eduToolbox@Bri-C GmbH, Sarstedt, with MIT license - see the headers in the code in the subfolders of the various search algorithms for details and reference to their predecessors (C-code mostly taken from the SMART tool v.13.02).