README
¶
simdjson
JSON parsing for Go that finds the whole document's structure in a few vector passes, then walks that instead of the bytes. Built on simd.go.
No cgo, and it runs the same on amd64, arm64, riscv64, s390x, ppc64le and loong64. The established Go port, minio/simdjson-go, is amd64 with AVX2 and hand-written assembly. This is 1.4–1.7× faster than it on amd64 and also runs on the other five architectures.
It is still slower than gjson at pulling a field out of a document, by about 2×, and the numbers say so plainly.
go get github.com/sebishogun/simdjson
doc, err := simdjson.Parse(data)
if err != nil {
return err
}
name := doc.Get("user", "name").String()
age := doc.Get("user", "age").Int()
doc.Get("items").ForEach(func(v simdjson.Value) bool {
total += v.Key("score").Float()
return true
})
Numbers, including the ones that are bad
Against other index-building parsers, this wins
minio/simdjson-go, the established Go port, in hand-written AVX2. Both validate. Worse of two runs of six for this package, better of two for the others, at load under 2:
| get one field | encoding/json | minio | Parse |
vs stdlib | vs minio |
|---|---|---|---|---|---|
| 100 items | 0.095 ms | 0.025 ms | 0.0145 ms | 6.57× | 1.73× |
| 1,000 items | 0.951 ms | 0.221 ms | 0.142 ms | 6.68× | 1.55× |
| 10,000 items | 9.62 ms | 2.030 ms | 1.449 ms | 6.64× | 1.40× |
Scan, which builds the same index and skips validation, is 3.8 µs / 36 µs /
371 µs on the same three documents. That is 5.5× minio at 10,000 items, but it
is not the same operation — minio validates and Scan does not, so the table
above is the comparison to read.
Against lazy scanners, it still loses
gjson and jsonparser do not parse the document. They scan for the path and stop at the first match.
That makes the obvious comparison unfair in gjson's favour, because gjson.Get
is not the same operation as Parse. It does not validate, and it will answer
from a document that is not JSON:
| input | gjson.Get returns |
actually valid |
|---|---|---|
{"a" 1} — no colon |
"1" |
no |
{"a":1 — unterminated |
"1" |
no |
{"a":01} — invalid number |
"01" |
no |
So the comparison has to put validation on both sides. On a 10,000-item document:
| gjson | this | ||
|---|---|---|---|
both validating — gjson.Valid+Get against Parse+Get |
694 µs | 1.449 ms | gjson 2.09× |
neither validating — gjson.Get against Scan+Get |
53.3 ns | 371 µs | gjson 6,960× |
Correcting the comparison moves it by two orders of magnitude and does not reverse it. gjson is faster at getting a field out of a document, whether or not either side checks the document first.
The gap on the validating row was 13.9× and is now 2.09×. What closed it was stage one: bitmasks instead of offset lists, which took the scan from 1.76 ms to 371 µs, and string validation done once over the whole document with masks instead of a byte walk per string. What is left is one thing:
The grammar walk still reads bytes. Parse costs 1.449 ms where Scan
costs 371 µs, so proving the document well-formed is 1.08 ms of it. The
recursive descent steps through the input skipping whitespace a byte at a time,
while the structural index beside it already records where every brace, colon
and comma is.
The obvious fix — index every token start, so stepping to the next token is an array read — was built and is 2.7× slower, because it makes the index bigger than the document. That is written up in docs/wrong.md; it is the second-most useful thing in this repository.
Container extents no longer cost anything: stage one pairs every bracket in one
stack pass over the class array, so finding where an object ends is a lookup
rather than a depth-counting walk. Index(j) is still linear in j, but each
step is now a lookup instead of a walk over the subtree it is skipping.
Use gjson or jsonparser unless you need encoding/json-grade validation, an
architecture minio does not support, or the whole document indexed once and
queried many times.
How it works
Two stages, which is the design simdjson introduced.
Stage one classifies the document with vector compares and answers everything that follows with bit arithmetic. Three passes produce a bitmask each — one bit per input byte — for the quotes, the backslashes and the six structural characters. A conventional parser reads a byte and branches on what it is, which is a dependent and unpredictable branch per byte. This has no per-byte branch at all.
Stage two walks the surviving positions. A megabyte document might have fifty thousand structural characters, so the second stage sees fifty thousand items rather than a million bytes.
The difficulty is entirely in stage one. A { inside a string is text, and a
" preceded by an odd number of backslashes does not close anything — in
"a\\" the quote follows two backslashes and does close the string, while in
"a\" it follows one and does not. Both are resolved before any position is
interpreted, and both are resolved as arithmetic over sixty-four bytes at a
time:
- which quotes are escaped — adding the odd-length backslash-run starts back into the backslash mask propagates a carry through each run and lands it one past the run's end, which turns "the parity of this run" into a single add;
- which bytes are inside a string — an inclusive prefix XOR of the surviving quote mask, six shift-and-xor steps per word, with the parity carried into the next word by sign-extending its top bit;
- which structural characters survive — an and-not.
None of that costs anything per match, which is the point. The version before
it built lists of offsets instead, one per character class. That is the
natural thing to build on a simd.IndexAll primitive and it is the wrong
representation: this document is about 40% structural characters, so the offset
list came out four times the size of the document it described, and every
question asked afterwards cost a scalar step per entry.
Replacing it was worth 4.8× on stage one. Two other things were tried first and are recorded in docs/wrong.md — windowing the input to keep it in cache, which a sweep from 4 KiB to 64 MiB showed changed nothing, and indexing every token start the way C++ simdjson's pseudo-structural characters do, which is 2.7× slower here because it makes the index bigger than the document.
Parse or Scan
Parse validates. It checks every value against JSON's grammar and rejects
exactly what encoding/json rejects. Use it for anything from outside.
Scan does not. It builds the index and identifies the root, and skips the
recursive descent that proves the parts you never look at are well-formed.
Malformed input then gives wrong answers rather than errors — nothing reads out
of bounds and nothing panics, but the result is not to be trusted. Use it when
you produced the bytes.
Validation is most of the cost, and skipping work you did not ask for is the whole reason a structural index exists.
Parser reuses its index between documents, which is what a server handling
a stream of payloads wants. Reuse cuts allocation by about 3,170× — 1,008 KB to
318 B per parse — and 17% of the time: 345 µs against 286 µs on a 230 KB
document. The allocation is the part worth removing.
Correctness
Defined as agreeing with encoding/json, and tested that way: hand-written
cases, 2000 randomised documents built from atoms chosen to collide (structure
inside strings, escaped quotes, escaped backslashes, surrogate pairs), and
fuzzing — 49 million executions, clean.
The fuzzer found four real bugs in its first three minutes, none of which the hand-written tests caught:
| input | bug |
|---|---|
{"":"\x82"} |
invalid UTF-8 returned raw; encoding/json coerces it to U+FFFD |
{"":{"":[{"\x00":0}]}} |
raw control character in a string, which JSON forbids |
{"":"\0"} |
invalid escape accepted — unquote returned a false flag the parse path ignored |
{"":10.} |
strconv.ParseFloat accepts 10.; JSON's grammar does not |
It then found a fifth failure that was in the test: 1E700 is valid JSON
that does not fit a float64. Comparing against Unmarshal, which converts,
made a conversion limit look like a syntax rule. The oracle for accept-or-reject
is json.Valid.
go test ./...
go test -run '^$' -fuzz FuzzAgainstStdlib -fuzztime 60s
What this is not
Not a replacement for encoding/json. No struct unmarshalling, no tags, no
interfaces, no streaming, no encoding. If you want a Go value, use the standard
library.
Not faster at everything. Parse, which validates every value, costs about
what encoding/json costs and builds an index on top; use it for untrusted
input and Scan when you produced the bytes. Walking a whole document is slower
than the standard library's single fused decode. Reaching into a document is
what an index buys; reading all of it is what it does not.
Not zero-copy for strings with escapes. A string with no backslash is returned without copying out of the document; one with an escape is decoded into a new string.
Status
Early, and measured on amd64 only. The simd package underneath is verified on
amd64 and arm64 NEON and under emulation elsewhere.
The rest of the family
All built on simd.go, which generates its kernels once from C and ships them as committed assembly for nine instruction sets — so none of these needs cgo, and none is amd64-only.
| simd.go | 467 operations over slices, bytes and text. The kernels everything else is built from. |
| simdblas | A BLAS backend for gonum. One blas64.Use call and mat, stat and optimize run on it. |
| simdcsv | CSV reading on one vector scan per record. |
| simdvec | Embedding search whose whole index scan is one matrix-vector product. |
License
Documentation
¶
Overview ¶
Package simdjson parses JSON by finding the whole document's structure in a few vector passes, then walking that instead of the bytes.
It is built on [simd.go](https://github.com/sebishogun/simd), so it needs no cgo and runs the same way on amd64, arm64, riscv64, s390x, ppc64le and loong64 — unlike the existing Go ports of simdjson, which are amd64 with hand-written assembly.
doc, err := simdjson.Parse(data)
name := doc.Get("user", "name").String()
age := doc.Get("user", "age").Int()
How it works ¶
Two stages, which is the design simdjson introduced.
Stage one finds every structural character — the braces, brackets, colons and commas — in one vector pass each, and works out which quotes really open and close strings rather than being escaped. A conventional parser reads a byte and branches on what it is, which is a dependent and unpredictable branch per byte; this makes eight branch-free passes over the document instead, and eight passes with no branches beat one pass with a branch per byte.
Stage two walks those positions. A document of a megabyte might have fifty thousand structural characters, so the second stage sees fifty thousand items rather than a million bytes.
What it is for ¶
Pulling a few values out of a document, which is most of what JSON is used for and the case encoding/json is worst at — it decodes everything to reach anything. Doc.Get navigates the index without decoding what it passes.
It is not a replacement for encoding/json. There is no struct unmarshalling, no tags, no interfaces, no streaming. If you want a Go value, use the standard library; if you want three fields out of a large payload, this is several times faster.
Example ¶
The case this package is for: a few values out of a document, without decoding the rest of it.
package main
import (
"fmt"
"github.com/sebishogun/simdjson"
)
func main() {
data := []byte(`{
"user": {"name": "ada", "age": 36, "tags": ["math", "engines"]},
"meta": {"page": 1}
}`)
doc, err := simdjson.Parse(data)
if err != nil {
fmt.Println("bad json:", err)
return
}
fmt.Println(doc.Get("user", "name").String())
fmt.Println(doc.Get("user", "age").Int())
fmt.Println(doc.Get("user", "tags").Index(1).String())
}
Output: ada 36 engines
Index ¶
- type Doc
- type Kind
- type Parser
- type Value
- func (v Value) Bool() bool
- func (v Value) Exists() bool
- func (v Value) Float() float64
- func (v Value) ForEach(fn func(Value) bool)
- func (v Value) ForEachKey(fn func(string, Value) bool)
- func (v Value) Index(n int) Value
- func (v Value) Int() int64
- func (v Value) IsNull() bool
- func (v Value) Key(name string) Value
- func (v Value) Kind() Kind
- func (v Value) Len() int
- func (v Value) Raw() []byte
- func (v Value) String() string
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Doc ¶
type Doc struct {
// contains filtered or unexported fields
}
Doc is a parsed document. It holds the input and its structural index; no values are decoded until they are asked for.
func Parse ¶
Parse indexes data and validates its structure.
The returned Doc keeps data — it is not copied, and every string a Value yields points into it unless the string contains an escape.
Example (StringsHideStructure) ¶
Structure inside a string is text, which is the whole difficulty of stage one and is handled before any of it is interpreted.
package main
import (
"fmt"
"github.com/sebishogun/simdjson"
)
func main() {
doc, err := simdjson.Parse([]byte(`{"a":"},{\"b\":2},[","c":1}`))
if err != nil {
fmt.Println("err:", err)
return
}
fmt.Printf("%q\n", doc.Get("a").String())
fmt.Println(doc.Get("c").Int())
}
Output: "},{\"b\":2},[" 1
func Scan ¶
Scan indexes data without validating it.
Parse walks the whole document and checks every value against JSON's grammar, which is what makes it safe for input you did not produce — and it is most of the cost. If the goal is three fields out of a payload your own service just serialised, validating the other nine thousand is work nobody asked for.
Scan skips it. The structural index is still built, so navigation works exactly as it does after Parse; what is gone is the recursive descent that proves the parts you never look at are well-formed.
What that costs ¶
Malformed input gives wrong answers rather than errors. A missing colon, a trailing comma, a number like 10., an invalid escape — all are accepted, and the values around them may come back wrong or absent instead of failing. The index itself is still consistent, so nothing reads out of bounds and nothing panics; the result is simply not to be trusted.
Two things are still checked, because the index cannot be built without them: every string is terminated, and quotes balance. A document that fails either is rejected here too.
Use Parse for anything from outside. Use Scan when you produced the bytes.
func (*Doc) Get ¶
Get walks a path of object keys and returns the value at the end.
A missing key, or a path that runs into a non-object, yields an Invalid Value rather than an error — chaining is the common case and an error at every step would be unusable. Check Value.Exists.
type Parser ¶
type Parser struct {
// contains filtered or unexported fields
}
Parser parses documents, reusing its index buffers between them.
A server handling many payloads should keep one per goroutine: Parse allocates a fresh index each time, and for a document of a few hundred kilobytes that index is several times the size of the document itself. A Parser reuses it, so the second and later documents allocate almost nothing.
A Parser is not safe for concurrent use.
Example ¶
A Parser reuses its index between documents, which is what a server handling a stream of payloads wants. The Doc it returns is only valid until the next Parse on the same Parser.
package main
import (
"fmt"
"github.com/sebishogun/simdjson"
)
func main() {
var p simdjson.Parser
for _, payload := range [][]byte{
[]byte(`{"id":1}`),
[]byte(`{"id":2}`),
} {
doc, err := p.Parse(payload)
if err != nil {
return
}
fmt.Println(doc.Get("id").Int())
}
}
Output: 1 2
type Value ¶
type Value struct {
// contains filtered or unexported fields
}
Value is one JSON value inside a document.
func (Value) Exists ¶
Exists reports whether the value was found.
Example ¶
A missing key yields a Value that does not exist rather than an error, so a path can be walked without checking every step.
package main
import (
"fmt"
"github.com/sebishogun/simdjson"
)
func main() {
doc, _ := simdjson.Parse([]byte(`{"a":{"b":1}}`))
fmt.Println(doc.Get("a", "b").Exists())
fmt.Println(doc.Get("a", "zzz").Exists())
fmt.Println(doc.Get("nope", "deeper").Exists())
}
Output: true false false
func (Value) ForEach ¶
ForEach calls fn for each element of an array until it returns false.
Example ¶
Iterating an array without building one.
package main
import (
"fmt"
"github.com/sebishogun/simdjson"
)
func main() {
doc, _ := simdjson.Parse([]byte(`{"scores":[10,20,30]}`))
total := int64(0)
doc.Get("scores").ForEach(func(v simdjson.Value) bool {
total += v.Int()
return true
})
fmt.Println(total)
}
Output: 60
func (Value) ForEachKey ¶
ForEachKey calls fn for each field of an object until it returns false.
Example ¶
Iterating an object's fields.
package main
import (
"fmt"
"github.com/sebishogun/simdjson"
)
func main() {
doc, _ := simdjson.Parse([]byte(`{"a":1,"b":2}`))
doc.Root().ForEachKey(func(k string, v simdjson.Value) bool {
fmt.Printf("%s=%d\n", k, v.Int())
return true
})
}
Output: a=1 b=2
func (Value) Key ¶
Key returns the value of a field in an object.
The scan walks the object's structural entries rather than its bytes, so passing over a large nested value costs one bracket match instead of a parse. A missing key gives an Invalid Value; see Value.Exists.
Source Files