Abstract

Beyond a certain level, performance cannot be engineered into a library, product, or codebase, after the fact.

This presentation explores this thesis via investigating a common operation; JSON decoding.

During this presentation we’ll investigate the performance of the stdlib JSON decoder; exploring the places where time is spent and comparing that to a clean room decoder.

This presentation will introduce a new primitive for buffered I/O and explore how an API designed sympathetically with the needs of its callers can deliver higher performance.

Introduction

I’m going to use the example of building a high performance JSON parser. In comparison to its encoding counterpart, JSON decoding is expensive in both time and space. The goals of this parser are:

Reasonably compatible with the encoding/json package

This package offers the same high level json.Decoder API but higher throughput and reduced allocations.

Allocation free, or bounded API

In addition to the encoding/json API, provide an alternative, more efficient API.

Supports streaming operations

It’s unrealistic to expect to have the entire input in memory. Buffering in memory is a availability risk, input sizes are usually unknown and potentially unbounded. Buffering before processing introduces latency. Streaming reads lets you process data as it arrives and overlap that processing with reading.

  • Benchmarks provided are using Go 1.26.5 on an M4 Macbook Pro.

  • Comparisons against the upcoming json/v2 is an exercise for the reader.

Time complexity

Let’s talk about the time complexity of this problem.

JSON doesn’t use length markers; to know how much to read, we have to read it all. To parse the 1,000th element in JSON array, we have to read the 999 that come before it. This means the lower bounds on the time to process the input is the size of the input — you can’t skip ahead.

But reading isn’t the full story, we need to drive it through the JSON state machine to figure out where the tokens start and end. Thus the performance is at least read(N)+parse(N).

But there are other costs:

  • Ideally if we read N bytes, we want to process each byte only once. If we touch the same byte more than once, that adds overhead, and complicates processing if we have to keep those bytes around to come back and look at them again.

  • Just like we don’t want to process a byte more than once, we want to avoid processing a token more than once.

  • Limit function calls in the hot path inside the Scanner or Decoder. We want to limit the number of function calls to O(tokens), not O(bytes).

  • Limit copies. If we have a design that limits copying then we reduce the number times we (re)visit a byte.

  • Limit allocations. If you limit the number of times data is copied, then you naturally limit allocations, which reduces runtime in several ways:

    1. Reduce the overhead in taking the allocation. The heap is a shared resource, allocating on the heap requires working with shared data structures. This means locks, cache contention, etc. c.f. Amdahl’s Law [1]

    2. Reduce the overhead of freeing allocations. The less allocations you make, the less heap you consume and the less garbage you produce. Reducing these two factors reduces the overhead of background and foreground garbage collection.

Tokenisation

A JSON decoder has two main components:

  1. A scanner, or tokeniser, that converts a stream a bytes into a stream of JSON tokens.

  2. An unmarshaller that applies a stream of JSON tokens to a Go object.

What then, is a token?

JSON is regular, well defined grammar. json.org has a wonderful set of railroad diagrams that describe the grammar of JSON.

JSON Object JSON Value

{"a": 1, "b": true, "c": [1, "two", null]}

Is a stream of,

  • { the opening brace, signifying a collection of name/value pairs.

  • "a" the string a.

  • : a colon, the delimiter between the key and the value in the key/value pair.

  • 1 the number one.

  • , a comma, the delimiter between one key/value pair and the next.

  • "b" the string b.

  • :

  • true the boolean value for true.

  • ,

  • "c" the string c.

  • :

  • [ the opening square brace, signifying an ordered list of values.

  • 1

  • ,

  • "two"

  • ,

  • null a null or void value (rare).

  • ] closing square brace, terminates the list of values

  • } closing curly brace, terminating the key/value collection.

If wanted to parse this with encoding/json, we declare a json.Decoder, then call Token until err is non nil.

package main

import (
	"encoding/json"
	"fmt"
	"strings"
)

func main() {
	const input = `{"a": 1, "b": true, "c": [1, "two", null]}`
	dec := json.NewDecoder(strings.NewReader(input))
	for {
		tok, err := dec.Token()
		if err != nil {
			break
		}
		fmt.Printf("%v\t(%T)\n", tok, tok)
	}
}

When we run this we get the following output

{       (json.Delim)
a       (string)
1       (float64)
b       (string)
true    (bool)
c       (string)
[       (json.Delim)
1       (float64)
two     (string)
<nil>   (<nil>)
]       (json.Delim)
}       (json.Delim)

This is rather convenient, the type of the token returned is an interface{} so it can represent both the value of the token, and also its type. Strings are string, numbers are float64, booleans are true and false, even null is represented as a nil.

But there is a cost to this convenience, and a reason why Brad Fitzpatrick called the Token API a garbage factory.

Because of the design of the Decoder.Token API, the concrete value assigned to each token causes that value to escape to the heap. The number of allocations is tied to the number of tokens in the input.

Let’s look at the allocations for the simplest case, a single token.

package json_test

import (
	"encoding/json"
	"strings"
	"testing"
)

func BenchmarkJSONDecodeHello(b *testing.B) {
	input := `"hello"`
	r := strings.NewReader(input) // reads strings as []byte
	dec := json.NewDecoder(r)
	b.ReportAllocs()
	b.SetBytes(int64(len(input)))
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		r.Seek(0, 0)
		tok, _ := dec.Token()
		if tok != "hello" {
			b.Fatal()
		}
	}
}

Which results in

                  │ benchhello.txt │
                  │     sec/op     │
JSONDecodeHello-8      129.8n ± 0%

                  │ benchhello.txt │
                  │      B/s       │
JSONDecodeHello-8     51.40Mi ± 0%

                  │ benchhello.txt │
                  │      B/op      │
JSONDecodeHello-8       37.00 ± 0%

                  │ benchhello.txt │
                  │   allocs/op    │
JSONDecodeHello-8       3.000 ± 0%

Take away: API design influences allocation. Allocations can influence performance.

Implicit tokens

Let’s look back at the sequence of tokens; { "a" : 1 , "b" : true , "c" : [ 1 , "two" , null ] and }.

It turns out that the first character in the token tells you the type of the token.

  • {, } - collection start, end

  • [, ] - array start, end

  • t - true

  • f - false

  • n - null

  • " - string

  • -, 0-9 - a number

This is the first improvement we can make in our Decoder.NextToken APIs. Rather than converting the input []byte to a value, we just return the bytes representing the token straight from the input—​a simple subslice. The first character in the []byte will tell the type of the token.

package main

import (
	"fmt"
	"strings"

	"github.com/pkg/json"
)

func main() {
	const input = `{"a": 1, "b": true, "c": [1, "two", null]}`
	dec := json.NewDecoder(strings.NewReader(input))
	for {
		tok, err := dec.NextToken()
		if err != nil {
			break
		}
		fmt.Printf("%s\t(%T)\n", tok, tok)
	}
}
{       ([]uint8)
"a"     ([]uint8)
1       ([]uint8)
"b"     ([]uint8)
true    ([]uint8)
"c"     ([]uint8)
[       ([]uint8)
1       ([]uint8)
"two"   ([]uint8)
null    ([]uint8)
]       ([]uint8)
}       ([]uint8)

There are a few subtleties with this API.

  1. Because the output is a subslice of the input, not a copy, there are restrictions on how long the output is valid for. This is similar to the bufio.Scanner API.

  2. Sometimes people want to know type of the token; collection, array, string, number, etc, sometimes they want the token value, the string, the number, in a form they can work with. Decoder.NextToken isn’t convenient for that, but can be used to build higher level abstractions.

func BenchmarkJSONDecoderToken(b *testing.B) {
	const input = `{"a": 1, "b": true, "c": [1, "two", null]}`
	var buf [8 << 10]byte

	b.Run("encoding/json.NewDecoder.Token", func(b *testing.B) {
		b.ReportAllocs()
		b.SetBytes(int64(len(input)))
		b.ResetTimer()
		for range b.N {
			dec := json.NewDecoder(strings.NewReader(input))
			for {
				_, err := dec.Token()
				if err != nil {
					break
				}
			}
		}
	})

	b.Run("pkg/json.Decoder.NextToken", func(b *testing.B) {
		b.ReportAllocs()
		b.SetBytes(int64(len(input)))
		b.ResetTimer()
		for range b.N {
			dec := pkgjson.NewDecoderBuffer(strings.NewReader(input), buf[:])
			for {
				_, err := dec.NextToken()
				if err != nil {
					break
				}
			}
		}
	})
}
BenchmarkJSONDecoderToken/encoding/json.NewDecoder.Token-16               943509              1318 ns/op          31.87 MB/s        1800 B/op         52 allocs/op
BenchmarkJSONDecoderToken/pkg/json.Decoder.NextToken-16                  9566983               128.3 ns/op       327.30 MB/s         152 B/op          3 allocs/op

Exercise to the reader; re-run the benchmark without the buffer

Reading

Let’s talk about reading data. This can be tricky to do efficiently because JSON is not length delimited, you have to read to the end of the token to find token.

io.Reader problems

The traditional way to do this is with an io.Reader.

buf := make([]byte, 4 << 10)
read, err := r.Read(buf)

But this comes with a number of problems:

  • io.Reader.Read copies data from the reader into a buffer. That copying takes time.

  • io.Reader.Read makes buffer management the problem of the caller.

    1. You can read one byte at a time, but you need a place to store the thing you’re walking over, also might need to put the byte back.

    2. You can read into a large buffer, then look in buffer for start and end of token. If the end token isn’t in the buffer you need to do a lot of bookkeeping and copying to move the data around the the buffer or grow the buffer to make room for more data.

This is tricky to get right, and inefficient even if you do. bufio.Reader is the canonical std library solution.

An alternative ByteReader

The alternative is an idea inspired by Steven Schveighoffer’s iopipe [2] and Phil Pearl [3] which I adapted into a type called a ByteReader. ByteReader operates similarly to bufio.Reader but has a more efficient API.

ByteReader? More like Bytescanner if you ask me

The other inspiration for this type comes from bufio.Scanner, specifically it’s Next() bool and Bytes() []bytes API.

  • The Next() API separates iteration from error handling. Next() returns true whenever there is data to process, which fits neatly into a for scanner.Next() { …​ } loop. Next() returns false when an error occurs, neatly rolling io.EOF into the general case, and are processed after iteration, not during.

  • The Bytes() API allows a way for the caller to "peak" into the scanner’s buffer to process the current item without having to copy it. This "peak" API comes with some caviets, the []byte slice is not valid beyond that iteration, but as processing an item involves transforming it, this is usually an acceptable tradeoff.

The ByteReader API

// A ByteReader implements a sliding window over an io.Reader.
type ByteReader struct {
	data   []byte
	offset int
	r      io.Reader
	err    error
}

// Window returns the current Window.
// The Window is invalidated by calls to release or extend.
func (b *ByteReader) Window() []byte {
	return b.data[b.offset:]
}

// Release discards n bytes from the front of the window.
func (b *ByteReader) Release(n int) {
	b.offset += n
}

// Extend extends the window with data from the underlying reader.
func (b *ByteReader) Extend() int {
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

{

"

a

"

:

1

,

"

b

"

:

t

r

u

e

,

"

c

"

:

[

1

,

"

t

w

o

Window()

Because the window is a []byte slice, any operation which is valid on a slice; ranging, contains, etc is available without overhead or error checking. This is the same as using a buffer after calling io.Reader.Read, except you don’t need to provide the buffer, and copies are avoided.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

{

"

a

"

:

1

,

"

b

"

:

t

r

u

e

,

"

c

"

:

[

1

,

"

t

w

o

Release(4)

Window()

Once a portion of the window is not needed it can be signalled with the Release() method. If the window is exhausted, calling Extend() will refill it, without discarding any data that has not been Released(). This means you don’t have to keep a temporary copy of partial data, it will still be there after Extend().

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

{

"

a

"

:

1

,

"

b

"

:

t

r

u

e

,

"

c

"

:

[

1

,

"

t

w

o

Window()

Extend()

After Extend() ing the previous window is invalid and Window() must be called again. Any data which was not Release() d will remain visibile in the window, at its same offset from the start of the []byte.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

{

"

a

"

:

1

,

"

b

"

:

t

r

u

e

,

"

c

"

:

[

1

,

"

t

w

o

Window()

Extend()

Error checking only occurs during Extend() which returns 0 as a sigil, leaving the caller to retrieve the error. This is also inspired by bufio.Scanner’s `Next and Err methods.

Example: whitespace

JSON Whitespace

JSON contains a mixture of tokens and whitespace. Space, tab, newline and carriage return can occur between tokens and are ignored, thus the search for a token begins with a search for the first non whitespace character.

This is a good time to talk about the search for whitespace with an example of using a ByteReader.

{"a": 1, "b": true, "c": [1, "two", null]}
var whitespace = [256]bool{
	' ':  true,
	'\t': true,
	'\n': true,
	'\r': true,
}

func BenchmarkCountWhitespace(b *testing.B) {
	b.Run("ByteReader", withFixtures(benchmarkCountWhitespace))
	b.Run("bufio.Reader", withFixtures(benchmarkCountWhitespaceBufio))
}

func benchmarkCountWhitespace(b *testing.B, input []byte, want int) {
	var buf [8 << 10]byte
	b.ReportAllocs()
	b.SetBytes(int64(len(input)))
	b.ResetTimer()
	for range b.N {
		br := &ByteReader{
			data: buf[:0],
			r:    bytes.NewReader(input),
		}
		n := countWhitespace(br)
		if n != want {
			b.Fatalf("expected: %v, got: %v", want, n)
		}
	}
}

func countWhitespace(br *ByteReader) int {
	n := 0
	for {
		w := br.Window()
		for _, c := range w {
			if whitespace[c] {
				n++
			}
		}
		br.Release(len(w))
		if br.Extend() == 0 {
			return n
		}
	}
}


func benchmarkCountWhitespaceBufio(b *testing.B, input []byte, want int) {
	b.ReportAllocs()
	b.SetBytes(int64(len(input)))
	b.ResetTimer()
	for range b.N {
		br := bufio.NewReader(bytes.NewReader(input))
		n := countWhitespaceBufioReader(br)
		if n != want {
			b.Fatalf("expected: %v, got: %v", want, n)
		}
	}
}

func countWhitespaceBufioReader(br *bufio.Reader) int {
	n := 0
	for {
		c, err := br.ReadByte()
		if err != nil {
			return n
		}
		if whitespace[c] {
			n++
		}
	}
}

This does the minimum, visit each character and test if it matches a whitespace character. Any (useful) JSON decoder code cannot go faster that this.

CountWhitespace/ByteReader/code.json-16               512.2µ ± 1%
CountWhitespace/ByteReader/citm.json-16               454.0µ ± 1%
CountWhitespace/ByteReader/example.json-16            3.409µ ± 1%
CountWhitespace/ByteReader/twitter.json-16            166.8µ ± 1%
CountWhitespace/ByteReader/sample.json-16             182.9µ ± 1%
CountWhitespace/bufio.Reader/canada.json-16           4.203m ± 1%
CountWhitespace/bufio.Reader/code.json-16             3.617m ± 0%
CountWhitespace/bufio.Reader/citm.json-16             3.136m ± 0%
CountWhitespace/bufio.Reader/example.json-16          24.09µ ± 0%
CountWhitespace/bufio.Reader/twitter.json-16          1.147m ± 0%
CountWhitespace/bufio.Reader/sample.json-16           1.261m ± 0%
geomean                                               411.0µ

                                             │ whitespace-tmp.txt │
                                             │        B/s         │
CountWhitespace/ByteReader/canada.json-16            3.627Gi ± 0%
CountWhitespace/ByteReader/code.json-16              3.528Gi ± 1%
CountWhitespace/ByteReader/citm.json-16              3.543Gi ± 1%
CountWhitespace/ByteReader/example.json-16           3.558Gi ± 1%
CountWhitespace/ByteReader/twitter.json-16           3.527Gi ± 1%
CountWhitespace/ByteReader/sample.json-16            3.500Gi ± 1%
CountWhitespace/bufio.Reader/canada.json-16          510.8Mi ± 1%
CountWhitespace/bufio.Reader/code.json-16            511.7Mi ± 0%
CountWhitespace/bufio.Reader/citm.json-16            525.2Mi ± 0%
CountWhitespace/bufio.Reader/example.json-16         515.6Mi ± 0%
CountWhitespace/bufio.Reader/twitter.json-16         524.9Mi ± 0%
CountWhitespace/bufio.Reader/sample.json-16          520.0Mi ± 0%
geomean                                              1.340Gi

                                             │ whitespace-tmp.txt │
                                             │        B/op        │
CountWhitespace/ByteReader/canada.json-16              48.00 ± 0%
CountWhitespace/ByteReader/code.json-16                48.00 ± 0%
CountWhitespace/ByteReader/citm.json-16                48.00 ± 0%
CountWhitespace/ByteReader/example.json-16             48.00 ± 0%
CountWhitespace/ByteReader/twitter.json-16             48.00 ± 0%
CountWhitespace/ByteReader/sample.json-16              48.00 ± 0%
CountWhitespace/bufio.Reader/canada.json-16          4.047Ki ± 0%
CountWhitespace/bufio.Reader/code.json-16            4.047Ki ± 0%
CountWhitespace/bufio.Reader/citm.json-16            4.047Ki ± 0%
CountWhitespace/bufio.Reader/example.json-16         4.047Ki ± 0%
CountWhitespace/bufio.Reader/twitter.json-16         4.047Ki ± 0%
CountWhitespace/bufio.Reader/sample.json-16          4.047Ki ± 0%
geomean                                                446.0

                                             │ whitespace-tmp.txt │
                                             │     allocs/op      │
CountWhitespace/ByteReader/canada.json-16              1.000 ± 0%
CountWhitespace/ByteReader/code.json-16                1.000 ± 0%
CountWhitespace/ByteReader/citm.json-16                1.000 ± 0%
CountWhitespace/ByteReader/example.json-16             1.000 ± 0%
CountWhitespace/ByteReader/twitter.json-16             1.000 ± 0%
CountWhitespace/ByteReader/sample.json-16              1.000 ± 0%
CountWhitespace/bufio.Reader/canada.json-16            2.000 ± 0%
CountWhitespace/bufio.Reader/code.json-16              2.000 ± 0%
CountWhitespace/bufio.Reader/citm.json-16              2.000 ± 0%
CountWhitespace/bufio.Reader/example.json-16           2.000 ± 0%
CountWhitespace/bufio.Reader/twitter.json-16           2.000 ± 0%
CountWhitespace/bufio.Reader/sample.json-16            2.000 ± 0%
geomean                                                1.414

So this is our baseline.

Take away:

  • moved from one call per character to one call per underlying window fill (extend)

  • window size grows as required, but initial size determines the overhead. Modest window sizes, which can be pooled, quickly ameliorate underling Read calls to refill.

Scanning

Now we can tell which characters are tokens and which are simply whitespace, let’s step up a level and talk about scanning.

// Next returns a []byte referencing the the next lexical token in the stream.
// The []byte is valid until Next is called again.
// If the stream is at its end, or an error has occurred, Next returns a zero
// length []byte slice.
//
// A valid token begins with one of the following:
//
//	{ Object start
//	[ Array start
//	} Object end
//	] Array End
//	, Literal comma
//	: Literal colon
//	t JSON true
//	f JSON false
//	n JSON null
//	" A string, possibly containing backslash escaped entites.
//	-, 0-9 A number
func (s *Scanner) Next() []byte {
	s.br.Release(s.offset) // release the previous token
	s.offset = 0

	c := s.token() // align to the next token
	length := 0
	switch c {
	case ObjectStart, ObjectEnd, Colon, Comma, ArrayStart, ArrayEnd:
		length = 1
		s.offset = 1
	case True:
		length = validateToken(&s.br, "true")
		s.offset = length
	case False:
		length = validateToken(&s.br, "false")
		s.offset = length
	case Null:
		length = validateToken(&s.br, "null")
		s.offset = length
	case String:
		length = parseString(&s.br)
		if length < 2 {
			return nil
		}
		s.offset = length
	case 0:
		// eof
		return nil
	default:
		length = s.parseNumber()
		if length < 0 {
			return nil
		}
	}
	return s.br.Window()[:length]
}

This is the core loop of Scanner.Next. Scanner.Next skips over any intermediate whitespace, determines the token from the first character in the window, then continues to read until the token is read or we hit the end of the input.

Let’s look at how token works, then we’ll talk about some optimisations

// token positions the scanner at the next token in the stream
// and returns the first byte of the token.
func (s *Scanner) token() byte {
	w := s.br.Window()
	offset := 0
	for {
		for _, c := range w {
			if whitespace[c] {
				offset++
				continue
			}

			// release whitespace
			s.br.Release(offset)
			return c
		}
		if s.br.Extend() == 0 {
			// eof
			return 0
		}
		w = s.br.Window()[offset:]
	}
}

  • We start by getting the current window from the ByteReader. This is a []byte slice of all the data that is yet to be read.

  • We’re looking for the first non whitespace character. If the character is a whitespace we increment offset to ignore the character and loop around.

  • If we do find a non whitespace character, we release offset characters from the front of the window. Now the start of the window is properly aligned with the first character of the token.

  • It turns out that we also get the first character of the token for free, it’s in c, so we can return that as a hint to Scanner.Next.

  • If we run out of characters without hitting a token then we called Extend() to grow the window.

  • If we couldn’t grow, then we’ve run out of input and haven’t got a token, so give up.

  • Otherwise update w with a new window.

Some things to note:

  • Note the lack of error handling, it’s not part of the inner loop, it only happens when we have to read more data from the underlying reader via Extend. [4]

  • Extend hides the process of reading into, growing, refilling the buffer, etc. The makes the caller--Scanner.token--simpler; if there is data in the window, process it, extend if you need too. If you can’t extend, give up.

  • Release is similar, it shrinks the start of the window to exclude data that no longer care about.

  • Extend is not in the hot path, so there is no need to optimise it, its performance is a function of the buffer it is given. In practice an initial buffer of a few kilobytes is sufficient.

Let’s talk about the performance of this code.

                        │ scanner1.txt │
                        │     B/s      │
Scanner/canada-16         939.1Mi ± 2%
Scanner/citm_catalog-16   1.522Gi ± 1%
Scanner/twitter-16        1.192Gi ± 1%
Scanner/code-16           842.1Mi ± 3%
Scanner/example-16        1.179Gi ± 1%
Scanner/sample-16         1.891Gi ± 1%
geomean                   1.204Gi

Comparing the performance of Scanner.Next to our whitespace benchmark we can see that we’re between 1/4 and 2/5ths of our baseline.

Question: why do scanning benchmarks differ by input?

Answer

The answer is different inputs have different amounts of whitespace. For example canada only has 33 whitespace characters whereas citm has 1,227,563.

Inlining

There is a larger improvement we can make for the runtime of this code, and it relates to inlining. Inlining is the process of automatically (or manually) copying the body of a function into, in line with, its caller. This avoids the overhead of the function call.

The Go compiler has reasonable support for inlining, but has a number of limitations.

% go build -gcflags=-m=2 2>&1 | grep cannot | grep -v decoder | head -n2
./reader.go:31:6: cannot inline (*ByteReader).Extend: function too complex: cost 187 exceeds budget 80
./scanner.go:63:6: cannot inline (*Scanner).Next: function too complex: cost 460 exceeds budget 80
./scanner.go:125:6: cannot inline (*Scanner).token: function too complex: cost 117 exceeds budget 80

For example, ByteReader.Extend, Scanner.Next, and Scanner.token cannot be inlined because they are too complex. [5]

Let’s go back to the constraints:

  • Scanner.Next is called for each token in the input.

  • This means that Scanner.token is called for each token in the input.

  • Scanner.token cannot be automatically inlined into its caller because it is too complex.

  • Therefore we’re paying two function calls per token.

We can remove one of these by manually inlining Scanner.token into its caller.

func (s *Scanner) Next() []byte {
	// release the previous token
	s.br.Release(s.offset)
	w := s.br.Window()
	offset := 0
	for {
		for _, c := range w {
			if whitespace[c] {
				offset++
				continue
			}

			// release whitespace
			s.br.Release(offset)

			length := 0
			switch c {
			case ObjectStart, ObjectEnd, Colon, Comma, ArrayStart, ArrayEnd:
				length = 1
				s.offset = 1
			case True:
				length = validateToken(&s.br, "true")
				s.offset = length
			case False:
				length = validateToken(&s.br, "false")
				s.offset = length
			case Null:
				length = validateToken(&s.br, "null")
				s.offset = length
			case String:
				// string
				length = parseString(&s.br)
				if length < 2 {
					return nil
				}
				s.offset = length
			default:
				// ensure the number is correct.
				length = s.parseNumber()
				if length < 0 {
					return nil
				}
			}
			return s.br.Window()[:length]
		}
		if s.br.Extend() == 0 {
			// eof
			return nil
		}
		w = s.br.Window()[offset:]
	}
}

The results support our thesis:

                        │ scanner1.txt │             scanner2.txt             │
                        │     B/s      │      B/s       vs base               │
Scanner/canada-16         903.0Mi ± 2%   1014.7Mi ± 1%  +12.38% (p=0.002 n=6)
Scanner/citm_catalog-16   1.534Gi ± 2%    1.678Gi ± 1%   +9.39% (p=0.002 n=6)
Scanner/twitter-16        1.166Gi ± 2%    1.284Gi ± 1%  +10.08% (p=0.002 n=6)
Scanner/code-16           823.9Mi ± 3%    892.3Mi ± 5%   +8.31% (p=0.002 n=6)
Scanner/example-16        1.156Gi ± 1%    1.253Gi ± 1%   +8.38% (p=0.002 n=6)
Scanner/sample-16         1.994Gi ± 1%    2.058Gi ± 1%   +3.23% (p=0.002 n=6)
geomean                   1.196Gi         1.299Gi        +8.59%

By saving the function call we’ve improved throughput by 9-12%. The largest improvement comes from canada, which basically contained no whitespace, so the call to Scanner.token almost always returned immediately having done no work!

To recap:

  • Scanner.Next and Scanner.token were effectively one function spread over two. Each are too large to be inlined, so we’re paying for an extra function call per token. Manually inlining them increased the indentation depth of the function, but delivered substantial speedups.

  • Most JSON contains some whitespace, it’s moderately optimised for human readability. It turns out, the more whitespace, the faster pkg/json decodes! citm is over 45% of the baseline, sample is nearly 55%.

Take away: Avoiding function calls can improve performance in the hot path.

Bonus points: does Go’s profile guided optimisation obsolete this advice?

Decoding

So far we have a Scanner which tokenises input up to 50% of the whitespace baseline. But there are a few more things we need to make it fully functional.

The first part of that is validation.

Validation

JSON is a state machine. Depending on the current token, only certain subsequent tokens are valid. For example, if you’ve read these tokens {, "username", then the only valid token is :. To track this we need to layer some logic on top of Scanner.Next to assert that a sequence of token is valid. This is the role of Decoder.NextToken:

const (
	stateValue        = 0
	stateObjectString = iota
	stateObjectColon
	stateObjectValue
	stateObjectComma
	stateArrayValue
	stateArrayComma
	stateEnd
)

func (d *Decoder) NextToken() ([]byte, error) {
	tok := d.scanner.Next()
	if len(tok) < 1 {
		return nil, io.EOF
	}
	switch d.state {
	case stateValue:
		return d.stateValue(tok)
	case stateObjectString:
		return d.stateObjectString(tok)
	case stateObjectColon:
		return d.stateObjectColon(tok)
	case stateObjectValue:
		return d.stateObjectValue(tok)
	case stateObjectComma:
		return d.stateObjectComma(tok)
	case stateArrayValue:
		return d.stateArrayValue(tok)
	case stateArrayComma:
		return d.stateArrayComma(tok)
	case stateEnd:
		fallthrough
	default:
		return nil, io.EOF
	}
}

This is pretty straightforward stuff. We take track the current state in d.state and based on its value we dispatch to the various state methods which assert token is valid and update the state.

Click to see the source for the various state methods. 
func (d *Decoder) stateObjectString(tok []byte) ([]byte, error) {
	switch tok[0] {
	case '}':
		inObj := d.pop()
		switch {
		case d.len() == 0:
			d.state = stateEnd
		case inObj:
			d.state = stateObjectComma
		case !inObj:
			d.state = stateArrayComma
		}
		return tok, nil
	case '"':
		d.state = stateObjectColon
		return tok, nil
	default:
		return nil, fmt.Errorf("stateObjectString: missing string key")
	}
}

func (d *Decoder) stateObjectColon(tok []byte) ([]byte, error) {
	switch tok[0] {
	case Colon:
		d.state = stateObjectValue
		return d.NextToken()
	default:
		return tok, fmt.Errorf("stateObjectColon: expecting colon")
	}
}

func (d *Decoder) stateObjectValue(tok []byte) ([]byte, error) {
	switch tok[0] {
	case '{':
		d.state = stateObjectString
		d.push(true)
		return tok, nil
	case '[':
		d.state = stateArrayValue
		d.push(false)
		return tok, nil
	default:
		d.state = stateObjectComma
		return tok, nil
	}
}

func (d *Decoder) stateObjectComma(tok []byte) ([]byte, error) {
	switch tok[0] {
	case '}':
		inObj := d.pop()
		switch {
		case d.len() == 0:
			d.state = stateEnd
		case inObj:
			d.state = stateObjectComma
		case !inObj:
			d.state = stateArrayComma
		}
		return tok, nil
	case Comma:
		d.state = stateObjectString
		return d.NextToken()
	default:
		return tok, fmt.Errorf("stateObjectComma: expecting comma")
	}
}

func (d *Decoder) stateArrayValue(tok []byte) ([]byte, error) {
	switch tok[0] {
	case '{':
		d.state = stateObjectString
		d.push(true)
		return tok, nil
	case '[':
		d.state = stateArrayValue
		d.push(false)
		return tok, nil
	case ']':
		inObj := d.pop()
		switch {
		case d.len() == 0:
			d.state = stateEnd
		case inObj:
			d.state = stateObjectComma
		case !inObj:
			d.state = stateArrayComma
		}
		return tok, nil
	case ',':
		return nil, fmt.Errorf("stateArrayValue: unexpected comma")
	default:
		d.state = stateArrayComma
		return tok, nil
	}
}

func (d *Decoder) stateArrayComma(tok []byte) ([]byte, error) {
	switch tok[0] {
	case ']':
		inObj := d.pop()
		switch {
		case d.len() == 0:
			d.state = stateEnd
		case inObj:
			d.state = stateObjectComma
		case !inObj:
			d.state = stateArrayComma
		}
		return tok, nil
	case Comma:
		d.state = stateArrayValue
		return d.NextToken()
	default:
		return nil, fmt.Errorf("stateArrayComma: expected comma, %v", d.stack)
	}
}

func (d *Decoder) stateValue(tok []byte) ([]byte, error) {
	switch tok[0] {
	case '{':
		d.state = stateObjectString
		d.push(true)
		return tok, nil
	case '[':
		d.state = stateArrayValue
		d.push(false)
		return tok, nil
	case ',':
		return nil, fmt.Errorf("stateValue: unexpected comma")
	default:
		d.state = stateEnd
		return tok, nil
	}
}

Let’s look at the results.

                                              │ decoder1.txt │
                                              │     B/s      │
DecoderNextToken/pkgjson/canada-16              730.7Mi ± 1%
DecoderNextToken/encodingjson/canada-16         85.03Mi ± 0%
DecoderNextToken/pkgjson/citm_catalog-16        1.244Gi ± 2%
DecoderNextToken/encodingjson/citm_catalog-16   198.9Mi ± 1%
DecoderNextToken/pkgjson/twitter-16             991.5Mi ± 1%
DecoderNextToken/encodingjson/twitter-16        113.5Mi ± 1%
DecoderNextToken/pkgjson/code-16                628.1Mi ± 4%
DecoderNextToken/encodingjson/code-16           58.64Mi ± 1%
DecoderNextToken/pkgjson/example-16             957.9Mi ± 1%
DecoderNextToken/encodingjson/example-16        107.4Mi ± 1%
DecoderNextToken/pkgjson/sample-16              1.834Gi ± 1%
DecoderNextToken/encodingjson/sample-16         423.8Mi ± 2%
geomean                                         363.6Mi

Compared to encoding/json we’re 8-10x faster. But there are some things we can do to improve:

Linear search

Central to the operation of Decoder.NextToken is the switch statement. In the general case, switch is implemented as a sequence of if statements. Effectively what the compiler sees is

func (d *Decoder) NextToken() ([]byte, error) {
	tok := d.scanner.Next()
	if len(tok) < 1 {
		return nil, io.EOF
	}
	if d.state == stateValue {
		return d.stateValue(tok)
	}
	if d.state == stateObjectString {
		return d.stateObjectString(tok)
	}
	if d.state == stateObjectColon {
		return d.stateObjectColon(tok)
	}
	if d.state == stateObjectValue {
		return d.stateObjectValue(tok)
	}
	if d.state == stateObjectComma {
		return d.stateObjectComma(tok)
	}
	if d.state == stateArrayValue {
		return d.stateArrayValue(tok)
	}
	if d.state == stateArrayComma {
		return d.stateArrayComma(tok)
	}
	return nil, io.EOF
}

switch is convenient, but not optimal in the hot path because that long sequence of if statements breaks up the instruction stream, and the puts pressure on the CPU’s branch predictor. Mispredicting a branch is expensive, the CPU has to flush the pipeline, rewind, and take the other branch.

This problem turns up in many places; bytecode interpreters are a classic example. One of the optimisations we could make is is to turn this linear search into a table. This can be space efficient if the state space is small and dense (often it is not), and the result might be something like this

var stateTable = [...]func(*Decoder, []byte) ([]byte, error){
	stateValue:        (*Decoder).stateValue,
	stateObjectString: (*Decoder).stateObjectString,
	stateObjectColon:  (*Decoder).stateObjectColon,
	stateObjectValue:  (*Decoder).stateObjectValue,
	stateObjectComma:  (*Decoder).stateObjectComma,
	stateArrayValue:   (*Decoder).stateArrayValue,
	stateArrayComma:   (*Decoder).stateArrayComma,
	stateEnd:          (*Decoder).stateEnd,
}

func (d *Decoder) NextToken() ([]byte, error) {
	tok := d.scanner.Next()
	if len(tok) < 1 {
		return nil, io.EOF
	}
	return stateTable[d.state](d, tok)
}
Unfortunately this won’t compile because there is an initalisation loop. 
./decoder.go:115:5: initialization loop:
        /Users/davecheney/devel/json/decoder.go:115:5: stateTable refers to
        /Users/davecheney/devel/json/decoder.go:155:19: (*Decoder).stateObjectColon refers to
        /Users/davecheney/devel/json/decoder.go:126:19: (*Decoder).NextToken refers to
        /Users/davecheney/devel/json/decoder.go:115:5: stateTable
FAIL    github.com/pkg/json [build failed\]

But there is a better trick that we can use that is more space efficient than this table, and is sometimes called a computed goto.

Computed Goto

If you look at the table above there is a pattern. Each state enumeration is matched with exactly one method. What we store in d.state is a proxy for the method we want to call, but to call the method, we have to switch on d.state to find the appropriate method.

What if we could just store the method directly and call it directly? And infact, we can do just that with some old Go 1.0 magic, method expression.

// A Decoder decodes JSON values from an input stream.
type Decoder struct {
	scanner *Scanner
	state   func(*Decoder, []byte) ([]byte, error)
	stack   // keeps track of whether we're in an object or array
}

func (d *Decoder) NextToken() ([]byte, error) {
	tok := d.scanner.Next()
	if len(tok) < 1 {
		return nil, io.EOF
	}
	return d.state(d, tok)
}

Let’s see how this performs.

                                              │ decoder1.txt │            decoder4.txt            │
                                              │     B/s      │     B/s       vs base              │
DecoderNextToken/pkgjson/canada-16              730.7Mi ± 1%   719.5Mi ± 1%  -1.53% (p=0.015 n=6)
DecoderNextToken/encodingjson/canada-16         85.03Mi ± 0%   84.14Mi ± 2%       ~ (p=0.065 n=6)
DecoderNextToken/pkgjson/citm_catalog-16        1.244Gi ± 2%   1.190Gi ± 2%  -4.31% (p=0.002 n=6)
DecoderNextToken/encodingjson/citm_catalog-16   198.9Mi ± 1%   201.6Mi ± 1%  +1.38% (p=0.041 n=6)
DecoderNextToken/pkgjson/twitter-16             991.5Mi ± 1%   970.0Mi ± 1%  -2.17% (p=0.002 n=6)
DecoderNextToken/encodingjson/twitter-16        113.5Mi ± 1%   112.4Mi ± 2%       ~ (p=0.180 n=6)
DecoderNextToken/pkgjson/code-16                628.1Mi ± 4%   600.8Mi ± 1%  -4.35% (p=0.002 n=6)
DecoderNextToken/encodingjson/code-16           58.64Mi ± 1%   59.07Mi ± 1%  +0.74% (p=0.026 n=6)
DecoderNextToken/pkgjson/example-16             957.9Mi ± 1%   936.5Mi ± 0%  -2.23% (p=0.002 n=6)
DecoderNextToken/encodingjson/example-16        107.4Mi ± 1%   109.0Mi ± 1%  +1.53% (p=0.009 n=6)
DecoderNextToken/pkgjson/sample-16              1.834Gi ± 1%   1.833Gi ± 1%       ~ (p=0.818 n=6)
DecoderNextToken/encodingjson/sample-16         423.8Mi ± 2%   436.2Mi ± 2%  +2.95% (p=0.002 n=6)
geomean                                         363.6Mi        360.5Mi       -0.86%

The results aren’t that promising, but now we can unlock our final optimisation.

Outlining

Compare the previous version of Decoder.NextToken

func (d *Decoder) NextToken() ([]byte, error) {
	tok := d.scanner.Next()
	if len(tok) < 1 {
		return nil, io.EOF
	}
	return d.state(d, tok)
}

with the version after outlining.

func (d *Decoder) NextToken() ([]byte, error) {
	return d.state(d)
}

func (d *Decoder) stateObjectColon() ([]byte, error) {
	tok := d.scanner.Next()
	if len(tok) < 1 {
		return nil, io.ErrUnexpectedEOF
	}
	switch tok[0] {
	case Colon:
		d.state = (*Decoder).stateObjectValue
		return d.NextToken()
	default:
		return tok, fmt.Errorf("stateObjectColon: expecting colon")
	}
}

// repeated for each Decoder.state... method

Moving the tok := d.scanner.Next() call into each state method might seem like a step backwards, but it has several positive effects.

  • The first is not passing tok into each state method. This saves 3 words on the call stack.

  • The second is, by moving the if len(tok) < 1 into the same function as the switch, it enables bounds check elimination.

    Previously, when the len(tok) check happened in Decoder.NextToken, Decoder.stateObjectColon doesn’t know anything about the length of tok because it can’t be inlined because we’re calling it via a method expression. When the compiler encounters switch tok[0], it needs to put a bounds check to make sure tok is at least 1 element long.

    When the if check is moved into the same function, the compiler knows that if we get further than the check then tok is at least 1 element long, so the bounds check is not needed.

    We can see this in the debug information.

% go build -gcflags=-d=ssa/prove/debug=2 2>&1 | grep decoder.go:100
./decoder.go:100:13: Proved IsInBounds (v26)

  • The final optimisation occurs because Decoder.NextToken, which was previously too complex to inline

% go build -gcflags=-m=2 2>&1 | grep Decoder..NextToken | head -n1
./decoder.go:92:6: cannot inline (*Decoder).NextToken: function too complex: cost 144 exceeds budget 80

is now inlinable

% go build -gcflags=-m=2 2>&1 | grep Decoder..NextToken | head -n1
./decoder.go:91:6: can inline (*Decoder).NextToken with cost 71 as: method(*Decoder) func() ([]byte, error) { return ([]byte)(.autotmp_3), .autotmp_4 }

Which means, calls to dec.NextToken()

for {
    _, err := dec.NextToken()
    if err == io.EOF {
        break
    }
    check(b, err)
    n++
}

becomes a direct call to the current state method.

for {
    _, err := dec.state(dec) // this is what the compiler sees
    if err == io.EOF {
        break
    }
    check(b, err)
    n++
}

Eliminating the cost of the function call.

                                              │ decoder1.txt │             decoder5.txt             │
                                              │     B/s      │      B/s       vs base               │
DecoderNextToken/pkgjson/canada-16              730.7Mi ± 1%    809.9Mi ± 1%  +10.84% (p=0.002 n=6)
DecoderNextToken/encodingjson/canada-16         85.03Mi ± 0%    85.38Mi ± 1%   +0.41% (p=0.002 n=6)
DecoderNextToken/pkgjson/citm_catalog-16        1.244Gi ± 2%    1.315Gi ± 1%   +5.73% (p=0.002 n=6)
DecoderNextToken/encodingjson/citm_catalog-16   198.9Mi ± 1%    200.7Mi ± 1%   +0.92% (p=0.009 n=6)
DecoderNextToken/pkgjson/twitter-16             991.5Mi ± 1%   1071.3Mi ± 1%   +8.05% (p=0.002 n=6)
DecoderNextToken/encodingjson/twitter-16        113.5Mi ± 1%    114.0Mi ± 1%        ~ (p=0.258 n=6)
DecoderNextToken/pkgjson/code-16                628.1Mi ± 4%    726.6Mi ± 6%  +15.67% (p=0.002 n=6)
DecoderNextToken/encodingjson/code-16           58.64Mi ± 1%    58.52Mi ± 1%        ~ (p=0.589 n=6)
DecoderNextToken/pkgjson/example-16             957.9Mi ± 1%   1050.5Mi ± 1%   +9.66% (p=0.002 n=6)
DecoderNextToken/encodingjson/example-16        107.4Mi ± 1%    108.2Mi ± 1%        ~ (p=0.240 n=6)
DecoderNextToken/pkgjson/sample-16              1.834Gi ± 1%    1.867Gi ± 1%   +1.77% (p=0.002 n=6)
DecoderNextToken/encodingjson/sample-16         423.8Mi ± 2%    431.2Mi ± 2%   +1.76% (p=0.002 n=6)
geomean                                         363.6Mi         380.1Mi        +4.53%

Results

At the lowest level pkg/json.Scanner can tokenize streaming JSON without allocation (provided it is supplied a few kilobytes of buffer).

BenchmarkScanner/canada-16         	    5574	   2045248 ns/op	1100.63 MB/s	       0 B/op	       0 allocs/op
BenchmarkScanner/citm_catalog-16   	   12433	    967019 ns/op	1786.11 MB/s	       0 B/op	       0 allocs/op
BenchmarkScanner/twitter-16        	   25790	    464796 ns/op	1358.69 MB/s	       0 B/op	       0 allocs/op
BenchmarkScanner/code-16           	    5846	   1977379 ns/op	 981.34 MB/s	       0 B/op	       0 allocs/op
BenchmarkScanner/example-16        	 1000000	     10366 ns/op	1256.39 MB/s	       0 B/op	       0 allocs/op
BenchmarkScanner/sample-16         	   36334	    327182 ns/op	2101.25 MB/s	       0 B/op	       0 allocs/op
PASS
ok  	github.com/pkg/json	87.771s

At the next level pkg/json.Decoder.Token is 2-3x faster than encoding/json.Decoder.Token.

BenchmarkDecoderToken/pkgjson/canada-16         	    1618	   7779987 ns/op	 289.34 MB/s	  889457 B/op	  111152 allocs/op
BenchmarkDecoderToken/encodingjson/canada-16    	     489	  24541641 ns/op	  91.72 MB/s	15091244 B/op	  777969 allocs/op
BenchmarkDecoderToken/pkgjson/citm_catalog-16   	    5520	   2200021 ns/op	 785.09 MB/s	  802787 B/op	   67602 allocs/op
BenchmarkDecoderToken/encodingjson/citm_catalog-16         	    1496	   8060600 ns/op	 214.28 MB/s	 5100727 B/op	  283595 allocs/op
BenchmarkDecoderToken/pkgjson/twitter-16                   	   10000	   1031721 ns/op	 612.10 MB/s	  724747 B/op	   37480 allocs/op
BenchmarkDecoderToken/encodingjson/twitter-16              	    2324	   5548863 ns/op	 113.81 MB/s	 3300643 B/op	  161149 allocs/op
BenchmarkDecoderToken/pkgjson/code-16                      	    1837	   6595105 ns/op	 294.23 MB/s	 3282422 B/op	  268916 allocs/op
BenchmarkDecoderToken/encodingjson/code-16                 	     375	  31699323 ns/op	  61.21 MB/s	20892445 B/op	 1152644 allocs/op
BenchmarkDecoderToken/pkgjson/example-16                   	  532418	     22527 ns/op	 578.15 MB/s	   15016 B/op	     872 allocs/op
BenchmarkDecoderToken/encodingjson/example-16              	  105230	    116274 ns/op	 112.01 MB/s	   75408 B/op	    3716 allocs/op
BenchmarkDecoderToken/pkgjson/sample-16                    	   27946	    428172 ns/op	1605.65 MB/s	  186584 B/op	    4252 allocs/op
BenchmarkDecoderToken/encodingjson/sample-16               	    7603	   1541239 ns/op	 446.06 MB/s	  676765 B/op	   22453 allocs/op
PASS
ok  	github.com/pkg/json	159.058s

Because allocations make up a large proportion of the Decoder.Token API, pkg/json.Decoder provides an alternative API that produces significantly fewer allocations and is 8-10x faster.

BenchmarkDecoderNextToken/pkgjson/canada-16         	    4412	   2549832 ns/op	 882.83 MB/s	     120 B/op	       2 allocs/op
BenchmarkDecoderNextToken/encodingjson/canada-16    	     490	  24381827 ns/op	  92.33 MB/s	15091241 B/op	  777969 allocs/op
BenchmarkDecoderNextToken/pkgjson/citm_catalog-16   	   10000	   1182494 ns/op	1460.65 MB/s	     120 B/op	       2 allocs/op
BenchmarkDecoderNextToken/encodingjson/citm_catalog-16         	    1489	   7936643 ns/op	 217.62 MB/s	 5100731 B/op	  283595 allocs/op
BenchmarkDecoderNextToken/pkgjson/twitter-16                   	   21836	    549587 ns/op	1149.07 MB/s	     136 B/op	       3 allocs/op
BenchmarkDecoderNextToken/encodingjson/twitter-16              	    2361	   5174887 ns/op	 122.03 MB/s	 3300643 B/op	  161149 allocs/op
BenchmarkDecoderNextToken/pkgjson/code-16                      	    4698	   2445576 ns/op	 793.46 MB/s	     232 B/op	       5 allocs/op
BenchmarkDecoderNextToken/encodingjson/code-16                 	     387	  31100841 ns/op	  62.39 MB/s	20892475 B/op	 1152644 allocs/op
BenchmarkDecoderNextToken/pkgjson/example-16                   	 1000000	     11681 ns/op	1114.94 MB/s	     136 B/op	       3 allocs/op
BenchmarkDecoderNextToken/encodingjson/example-16              	  106668	    113124 ns/op	 115.13 MB/s	   75408 B/op	    3716 allocs/op
BenchmarkDecoderNextToken/pkgjson/sample-16                    	   36633	    325299 ns/op	2113.42 MB/s	    1128 B/op	       8 allocs/op
BenchmarkDecoderNextToken/encodingjson/sample-16               	    7701	   1499278 ns/op	 458.55 MB/s	  676765 B/op	   22453 allocs/op
PASS
ok  	github.com/pkg/json	160.110s

At the highest level, pkg/json can unmarshal data into a Go object with the same API as encoding/json at roughly 2x the throughput.

BenchmarkDecoderDecodeInterfaceAny/pkgjson/canada-16         	    1200	   9975801 ns/op	 225.65 MB/s	 7938449 B/op	  281386 allocs/op
BenchmarkDecoderDecodeInterfaceAny/encodingjson/canada-16    	     772	  15716807 ns/op	 143.23 MB/s	18970385 B/op	  392532 allocs/op
BenchmarkDecoderDecodeInterfaceAny/pkgjson/citm_catalog-16   	    3668	   3069114 ns/op	 562.77 MB/s	 5114419 B/op	   90164 allocs/op
BenchmarkDecoderDecodeInterfaceAny/encodingjson/citm_catalog-16         	    1443	   8349801 ns/op	 206.86 MB/s	 9323325 B/op	   95881 allocs/op
BenchmarkDecoderDecodeInterfaceAny/pkgjson/twitter-16                   	    8314	   1536467 ns/op	 411.02 MB/s	 2021419 B/op	   31045 allocs/op
BenchmarkDecoderDecodeInterfaceAny/encodingjson/twitter-16              	    3460	   3409804 ns/op	 185.21 MB/s	 4172212 B/op	   32141 allocs/op
BenchmarkDecoderDecodeInterfaceAny/pkgjson/code-16                      	    1652	   7383495 ns/op	 262.81 MB/s	 7205733 B/op	  232049 allocs/op
BenchmarkDecoderDecodeInterfaceAny/encodingjson/code-16                 	     986	  12218418 ns/op	 158.82 MB/s	12109811 B/op	  271283 allocs/op
BenchmarkDecoderDecodeInterfaceAny/pkgjson/example-16                   	  400965	     30058 ns/op	 433.30 MB/s	   48760 B/op	     761 allocs/op
BenchmarkDecoderDecodeInterfaceAny/encodingjson/example-16              	  170695	     70480 ns/op	 184.79 MB/s	   80568 B/op	     805 allocs/op
BenchmarkDecoderDecodeInterfaceAny/pkgjson/sample-16                    	   23772	    507928 ns/op	1353.52 MB/s	  395785 B/op	    5584 allocs/op
BenchmarkDecoderDecodeInterfaceAny/encodingjson/sample-16               	    4297	   2709884 ns/op	 253.70 MB/s	 2651002 B/op	    7570 allocs/op
PASS
ok  	github.com/pkg/json	156.885s

Thematic ideas

Allocations affect performance

The garbage collector might be fast to allocate and efficient to collect, but not allocating will always be faster.

Eliminating allocations through API design

Most of the speedups of this package come from reducing allocations; specifically the time not spent in the heap allocation path, and the time not spent in GC cycles, is available for scanning.

API design influences performance

The encoding/json.Decoder API requires allocations as returning a primitive value via an interface causes it to escape to the heap — it effectively becomes a pointer to the value. When dealing with data, allocations, can be the biggest performance cost of an algorithm. You’re benchmarking the garbage collector at that point.

Careful attention to the per byte and per token overheads

Optimising the hot path to convert functions per byte into per token functions is the second biggest performance win.

Beyond this is the domain of micro optimisations. Things like moving statements across function call boundaries to play inlining tricks. Don’t reach for the tricks I showed here without addressing the big O effects in your api. It won’t move the needle.

I started this project because I believed that it was possible to implement an efficient JSON parser based on my assumption that encoding/json was slower than it could be because of its API.

It turned out there is 2-3x performance in some unmarshalling paths and between 8x and 10x performance in tokenisation, if you’re prepared to accept a different API.

One more thing

io.Reader.Read and io.Writer.Write take their API directly from Unix’s read(2) and write(2). One reads into the buffer provided, the other writes the provided buffer. It’s nice, neat, symetrical, but it’s also inefficient.

If the goal is to read data from one place and send it someplace else without any inspection, even that is insufficent as we see hacks like sendfile(2), io.ReaderFrom.ReadFrom, and io.WriterTo.WriteTo proliferate.

Yes, io.Reader.Read is safe in that it cannot be blamed for data corruption. At a minimum io.Reader.Read pushes the management of reader buffers to the caller, then adds the complexity of managing partially read buffers, extending them.

ByteReader is small enough to fit on a page, and provides a more efficient way to read from a stream of data, which is almost always what you want to do because that data needs to be decoded, trasformed, and operated on at a higher level.

I’ve extracted the ByteReader type into a small package github.com/davecheney/bytereader for your experimentation. One open question is what would it look like if we integrated Go 1.23’s iter.Seq API to avoid having to expose Window()/Release()/Extend(), simply range over a ByteReader as forward only view of an io.Reader.

Thank you

The git timestamps on this project date back to 2020, circa Go 1.14. The code has been modernised several times, but realistically should work with moderately older versions of Go, and with a little finagling, significantly older versions. Thus, it is a useful candidate to benchmark the major improvements in the Go compiler, and runtime, over the years.

1. en.wikipedia.org/wiki/Amdahl%27s_law
2. DConf 2017: IOPipe: a High Performance I/O Library — Steven Schveighoffer www.youtube.com/watch?v=un-bZdyumog
3. philpearl.github.io/post/reader/
4. John Ousterhout, Define errors out of existence. youtu.be/bmSAYlu0NcY?si=WjC1ouEN1ad2OWjp&t=1312
5. Complexity is determined by giving each statement a weighting. The weightings are somewhat arbitrary, but more or less each token costs 1, function calls cost 52. github.com/golang/go/issues/17566 covers improving the inlining cost model.