Documentation
¶
Overview ¶
Package swar finds the first byte of a slice that belongs to a set, a word at a time: SIMD within a register (SWAR), on the standard library alone. It is a kernel primitive — stdlib-only and domain-neutral: a slice, two bytes, a bound, and no header, no escape and no token in a signature.
Three searches, each returning the index of the FIRST match or -1:
swar.IndexByte2(b, '\r', '\n') // either of two bytes
swar.IndexLess(b, 0x20) // a byte below a bound: a control byte
swar.NewSet('"', '\\', 0x20, true).Index(b)
// a quote, a backslash, a control byte,
// or a byte from 0x80 up
There is no search for one byte: bytes.IndexByte is an assembly loop over thirty-two bytes at a time, and on the machine it was measured on (an Apple M1, BENCH.md) it beat the word loop at every length but eight bytes. Use it for one byte; IndexByte2 with the byte passed twice also finds one.
How a word is searched ¶
The slice is read eight bytes at a time as a little-endian word, and a lane test turns the word into one flag per byte. The tests are EXACT: a flag is set for a byte that matches and for no other, because the sum behind each test cannot carry out of its lane. The classic borrowing form (v - 0x01..) &^ v & 0x80.. is not used: it flags a byte above a true match too, so only its lowest bit can be trusted, and a caller that walks the others reads false hits. Here every flag is a real match, and the lowest is the first.
A comparison against a bound is exact for a bound of 128 or less. A larger one has no exact lane test, so IndexLess and a Set with such a bound read byte by byte: correct, and no faster than a loop.
What is read ¶
Nothing past the length. Every load is a bounds-checked slice of eight bytes within len(b), the last bytes are read one at a time, and the capacity beyond len(b) is never touched — whatever it holds, a "\r\n" left by an earlier request included. There is no unsafe in the package.
The vector form ¶
Built with GOEXPERIMENT=simd on amd64, the package also carries an AVX2 form of each search that reads thirty-two bytes at a time, used for a slice of thirty-two bytes or more on a CPU that reports AVX2 when the program starts. The SWAR form is in the same binary and takes every other call: a slice of under thirty-two bytes, any slice on a CPU without AVX2, and IndexLess with a bound of zero. Without AVX2 (and in a build without the experiment, which has only the SWAR form) IndexByte2 hands a slice of 64 bytes or more to two scans of bytes.IndexByte instead. Both forms answer alike, and the suite holds them to the same oracle. The experiment's package, simd/archsimd, is not covered by the Go 1 promise: the vector form may stop compiling on a new Go version, and a consumer that cannot afford that builds without the experiment.
Those scans read faster than the word loop from 64 bytes on.
Cost ¶
Nothing here allocates. BENCH.md has the figures against the byte loop and bytes.IndexByte, and says for which lengths each form wins.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func IndexByte2 ¶
IndexByte2 returns the index of the first byte of b equal to c1 or to c2, or -1 when there is none: the search for a line end, '\r' or '\n'. A slice of 64 bytes or more goes to two scans of bytes.IndexByte where the build has no AVX2 form.
Example ¶
ExampleIndexByte2 finds the first bare or paired line end, and searches for a single byte by passing it twice.
package main
import (
"fmt"
"github.com/kitsunium/sdk/internal/kernel/swar"
)
func main() {
fmt.Println(swar.IndexByte2([]byte("Host: x\r\nAccept: */*"), '\r', '\n'))
fmt.Println(swar.IndexByte2([]byte("Host: x\nAccept: */*"), '\r', '\n'))
fmt.Println(swar.IndexByte2([]byte("GET /users/7 HTTP/1.1\r\n"), '\n', '\n'))
}
Output: 7 7 22
func IndexLess ¶
IndexLess returns the index of the first byte of b below n, or -1 when there is none. A bound of zero holds no byte. The search is a word at a time for a bound of 128 or less, and byte by byte above it.
Example ¶
ExampleIndexLess finds the first control byte of a header value.
package main
import (
"fmt"
"github.com/kitsunium/sdk/internal/kernel/swar"
)
func main() {
fmt.Println(swar.IndexLess([]byte("text/plain; charset=utf-8"), 0x20))
fmt.Println(swar.IndexLess([]byte("text/plain;\tcharset"), 0x20))
}
Output: -1 11
Types ¶
type Set ¶
type Set struct {
// contains filtered or unexported fields
}
Set is a set of byte values: the two bytes it was built with, the bytes below its bound, and optionally the bytes from 0x80 up. NewSet computes what a search reads once, and Set.Index only reads it, so a Set is safe for any number of goroutines. The zero Set holds the byte 0x00 alone.
func NewSet ¶
NewSet returns the set of the bytes first and second, the bytes below below, and — when upper is true — the bytes from 0x80 up. Pass the same byte twice for a set of one, and a below of zero for none below.
A below above 128 is accepted; Set.Index then reads byte by byte.
func (Set) Index ¶
Index returns the index of the first byte of b that is in the set, or -1 when there is none. It reads nothing past len(b).
Example ¶
ExampleSet_Index finds the first byte a quoted string must escape: a quote, a backslash, a control byte, or a byte that starts a multi-byte character.
package main
import (
"fmt"
"github.com/kitsunium/sdk/internal/kernel/swar"
)
func main() {
escape := swar.NewSet('"', '\\', 0x20, true)
fmt.Println(escape.Index([]byte("plain ascii text")))
fmt.Println(escape.Index([]byte(`say "hi"`)))
fmt.Println(escape.Index([]byte("tab\there")))
fmt.Println(escape.Index([]byte("café")))
}
Output: -1 4 3 3
Source Files