simdvec

README

simdvec

A vector index for embedding search. Built on simd.go. No cgo, and the same code runs on amd64, arm64, riscv64, s390x, ppc64le and loong64.

go get github.com/sebishogun/simdvec

ix := simdvec.New(768, simdvec.Cosine)

for id, emb := range embeddings {
	ix.Add(id, emb)
}

hits, err := ix.Search(query, 10)

Numbers

Against the loop a Go program writes today — vectors in a [][]float32, a dot product each, sort. Zen 5, worse of two runs:

	naive	simdvec
100,000 × 768	66.3 ms	3.68 ms	18.0×
100,000 × 384	47.6 ms	2.19 ms	21.7×
10,000 × 768	5.79 ms	0.15 ms	38.4×
10,000 × 384	3.01 ms	0.09 ms	32.1×

Why it is faster

The obvious implementation is N dot products. That is N calls, and for a 768-dimension vector each one is over before the call overhead is amortised.

The vectors are stored instead as one contiguous N×D matrix, so the entire scan is a single matrix-vector product — one GemvParallelInto across every core, not a hundred thousand dots. Selection is then a quickselect over the scores, because only k of N are wanted and N is very much larger.

That is also why Add copies. The layout is the optimisation.

Metrics

Cosine, DotProduct and Euclidean.

Cosine normalises on insert and on query, which turns the comparison into a plain dot product — the division happens once per vector instead of once per comparison. Euclidean is computed from the dot product and precomputed norms rather than by subtracting, so it is the same single matrix-vector product as the others.

There is no int8 index, and that was measured

One was written, tested and deleted. Quantizing to int8 is a quarter of the memory and the recall was fine — 0.954 to 0.982 at k=10 across 128, 384 and 768 dimensions. It is also slower, by a lot.

Searching one query becomes an n×dim by dim×1 integer multiply, and a single output column is a degenerate shape for a matrix-multiply kernel whose blocking assumes a wide result. On 100,000 vectors of 768 dimensions:

	ms per query
int8, one query at a time	311.7
int8, batches of 8	37.5
int8, batches of 32	1.25
int8, batches of 128	1.11
float32, one query	0.21

Batching helps and does not rescue it. The best int8 arrangement is five times slower than the float32 scan, because GemvParallelInto is parallel and reads memory in the order the prefetcher wants, and four times the elements per register does not make up for either.

So this stores float32. If memory matters more than latency, quantize before inserting — the index does not need to know.

What this is not

Not approximate. Every search scans every vector. That is the right structure up to a few hundred thousand embeddings, because one pass over a contiguous block is bound by memory bandwidth rather than arithmetic, and an approximate index only starts to win once the scan stops fitting in cache. Above that, use one.

Not persistent, and not concurrent. The index is memory, and Add and Search are not safe to call at the same time. Both are deliberate for a first release; say if you need them.

Correctness

Every result is compared against a naive implementation — score everything with a plain loop, sort, take k — across three metrics, four dimensions and four index sizes. Ranks and scores must both match.

go test ./...

Status

Early, and measured on amd64 only. The simd package underneath is verified on amd64 and arm64 NEON and under emulation elsewhere.

License

MIT — see LICENSE. Depends on simd.go (MIT).

Documentation

Overview

Package simdvec is a vector index for embedding search, built on [simd.go](https://github.com/sebishogun/simd). No cgo, and the same code runs on amd64, arm64, riscv64, s390x, ppc64le and loong64.

ix := simdvec.New(768, simdvec.Cosine)
ix.Add("doc-1", embedding)
hits := ix.Search(query, 10)

Why this is fast

The obvious way to search N embeddings is N dot products. That is N calls, and for a 768-dimension vector each one is over before the call overhead is amortised.

The vectors are stored instead as one contiguous N×D matrix, which makes the entire scan a single matrix-vector product: simd.GemvParallelInto computes every score in one call, across every core. Searching a hundred thousand embeddings is one Gemv, not a hundred thousand dots.

That is also why Add copies into the matrix rather than keeping a pointer. The layout is the optimisation.

There is no int8 index, and that was measured

An int8 index was written, tested and deleted. Quantizing to int8 is a quarter of the memory and its recall was fine — 0.954 to 0.982 at k=10 — but it is slower, not faster, and by a lot.

The scan becomes simd.QMatMulInt8Into, and searching one query is an n×dim by dim×1 multiply. One output column is a degenerate shape for a matrix-multiply kernel, whose blocking assumes a wide result. Batching helps and does not rescue it, on 100,000 vectors of 768 dimensions:

int8, one query at a time   311.7 ms/query
int8, batches of 8           37.5 ms/query
int8, batches of 32           1.25 ms/query
int8, batches of 128          1.11 ms/query
float32, one query            0.21 ms/query

The best int8 arrangement is five times slower than the float32 scan, because GemvParallelInto is parallel and reads memory in the order the prefetcher wants, and four times the elements per register does not make up for either.

So this package stores float32. If the memory matters more than the latency, quantize before inserting — the index does not need to know.

Index

• Variables
• type Index
  • func New(dim int, metric Metric) *Index
  • func (ix *Index) Add(id string, vec []float32) error
  • func (ix *Index) Dim() int
  • func (ix *Index) Len() int
  • func (ix *Index) Search(query []float32, k int) ([]Result, error)
• type Metric
  • func (m Metric) String() string
• type Result

Variables

var ErrDim = errors.New("simdvec: wrong vector dimension")

ErrDim is returned when a vector's length does not match the index.

Types

type Index

type Index struct {
	// contains filtered or unexported fields
}

Index is a flat (brute-force) index over float32 embeddings.

Every search scans every vector. That is the right structure up to a few hundred thousand embeddings, because one matrix-vector product over a contiguous block is bound by memory bandwidth rather than by arithmetic, and an approximate index only starts to win once the scan no longer fits in cache.

func New

func New(dim int, metric Metric) *Index

New returns an empty index for vectors of the given dimension.

func (*Index) Add

func (ix *Index) Add(id string, vec []float32) error

Add indexes a vector under id.

The vector is copied into the index's matrix; the caller's slice is not retained. For Cosine the copy is normalised on the way in, so the query-time comparison is a plain dot product.

func (*Index) Dim

func (ix *Index) Dim() int

Dim returns the vector dimension.

func (*Index) Len

func (ix *Index) Len() int

Len returns the number of indexed vectors.

func (*Index) Search

func (ix *Index) Search(query []float32, k int) ([]Result, error)

Search returns the k best matches for query.

The whole index is scored with one matrix-vector product, then the k best are selected. Scoring is the expensive half and it is one call; selection is a partial sort over the scores.

type Metric

type Metric int

Metric is how two vectors are compared.

const (
	// Cosine compares direction and ignores magnitude. Vectors are normalised
	// on insert and on query, which turns the comparison into a dot product —
	// the division is done once per vector rather than once per comparison.
	Cosine Metric = iota
	// DotProduct compares without normalising, for models whose magnitude
	// carries meaning.
	DotProduct
	// Euclidean is straight-line distance. Computed from the dot product and
	// the precomputed norms rather than by subtracting, so it is the same one
	// matrix-vector product as the others.
	Euclidean
)

func (Metric) String

func (m Metric) String() string

type Result

type Result struct {
	ID    string
	Score float32 // higher is better for Cosine and DotProduct; lower for Euclidean
}

Result is one hit.