go-json

Fast JSON encoder/decoder compatible with encoding/json for Go

Installation

go get github.com/goccy/go-json

How to use

Replace import statement from

encoding/json

github.com/goccy/go-json

-import "encoding/json"
+import "github.com/goccy/go-json"

JSON library comparison

| name | encoder | decoder | compatible with

encoding/json

• json-iterator/go

  isn't compatible with

  encoding/json

  in many ways, but it hasn't been supported for a long time.

Benchmarks

$ cd benchmarks
$ go test -bench .

Encode

Decode

How it works

go-json

go-json

encoding/json

Here, we explain the various speed-up techniques implemented by

go-json

Basic technique

The techniques listed here are the ones used by most of the libraries listed above.

Buffer reuse

Since the only value required for the result of

json.Marshal(interface{}) ([]byte, error)

[]byte

[]byte

Also, as the number of allocations increases, the performance will be affected, so the number of allocations should be kept as low as possible when creating

[]byte

Therefore, there is a technique to reduce the number of times a new buffer must be allocated by reusing the buffer used for the previous encoding by using

sync.Pool

Finally, you allocate a buffer that is as long as the resulting buffer and copy the contents into it, you only need to allocate the buffer once in theory.

type buffer struct {
    data []byte
}

var bufPool = sync.Pool{
    New: func() interface{} {
        return &buffer{data: make([]byte, 0, 1024)}
    },
}
buf := bufPool.Get().(*buffer)
data := encode(buf.data) // reuse buf.data
newBuf := make([]byte, len(data))
copy(newBuf, buf)
buf.data = data
bufPool.Put(buf)

Elimination of reflection

As you know, the reflection operation is very slow.

Therefore, using the fact that the address position where the type information is stored is fixed for each binary ( we call this

typeptr

For example, you can get the address to the type information from

interface{}

To process without reflection, pass a pointer (

unsafe.Pointer

type emptyInterface struct {
    typ unsafe.Pointer
    ptr unsafe.Pointer
}

var typeToEncoder = map[uintptr]func(unsafe.Pointer)([]byte, error){}
func Marshal(v interface{}) ([]byte, error) {
    iface := (*emptyInterface)(unsafe.Pointer(&v)
    typeptr := uintptr(iface.typ)
    if enc, exists := typeToEncoder[typeptr]; exists {
        return enc(iface.ptr)
    }
    ...
}

※ In reality,

typeToEncoder

Unique speed-up technique

Encoder

Do not escape arguments of

Marshal

json.Marshal

json.Unmarshal

interface{}

reflect

reflect.Type

interface

reflect.Type

Therefore, the arguments for

Marshal

Unmarshal

go-json

reflect.Type

reflect.Type

interface

reflect.Type

rtype

reflect

reflect.Type

*reflect.rtype

Therefore, by directly handling

*reflect.rtype

reflect.Type

interface

struct

The technique for working with

*reflect.rtype

go-json

Also, the same technique is cut out as a library ( https://github.com/goccy/go-reflect )

Initially this feature was the default behavior of

go-json

json.Marshal()

Therefore, this feature will be provided as an optional until this issue is resolved.

To use it, add

NoEscape

MarshalNoEscape()

Encoding using opcode sequence

I explained that you can use

typeptr

In other libraries, this dedicated process is processed by making it an function calling like anonymous function, but function calls are inherently slow processes and should be avoided as much as possible.

Therefore,

go-json

If it is the first type to encode, create the opcode ( instruction ) sequence required for encoding. From the second time onward, use

typeptr

json.Marshal(struct{
    X int `json:"x"`
    Y string `json:"y"`
}{X: 1, Y: "hello"})

When encoding a structure like the one above, create a sequence of opcodes like this:

- opStructFieldHead ( `{` )
- opStructFieldInt ( `"x": 1,` )
- opStructFieldString ( `"y": "hello"` )
- opStructEnd ( `}` )
- opEnd

※ When processing each operation, write the letters on the right.

In addition, each opcode is managed by the following structure ( Pseudo code ).

type opType int
const (
    opStructFieldHead opType = iota
    opStructFieldInt
    opStructFieldStirng
    opStructEnd
    opEnd
)
type opcode struct {
    op opType
    key []byte
    next *opcode
}

The process of encoding using the opcode sequence is roughly implemented as follows.

func encode(code *opcode, b []byte, p unsafe.Pointer) ([]byte, error) {
    for {
        switch code.op {
        case opStructFieldHead:
            b = append(b, '{')
            code = code.next
        case opStructFieldInt:
            b = append(b, code.key...)
            b = appendInt((*int)(unsafe.Pointer(uintptr(p)+code.offset)))
            code = code.next
        case opStructFieldString:
            b = append(b, code.key...)
            b = appendString((*string)(unsafe.Pointer(uintptr(p)+code.offset)))
            code = code.next
        case opStructEnd:
            b = append(b, '}')
            code = code.next
        case opEnd:
            goto END
        }
    }
END:
    return b, nil
}

In this way, the huge

switch-case

Opcode sequence optimization

One of the advantages of encoding using the opcode sequence is the ease of optimization. The opcode sequence mentioned above is actually converted into the following optimized operations and used.

- opStructFieldHeadInt ( `{"x": 1,` )
- opStructEndString ( `"y": "hello"}` )
- opEnd

It has been reduced from 5 opcodes to 3 opcodes ! Reducing the number of opcodees means reducing the number of branches with

switch-case

In

go-json

Change recursive call from CALL to JMP

Recursive processing is required during encoding if the type is defined recursively as follows:

type T struct {
    X int
    U *U
}

type U struct {
    T *T
}
b, err := json.Marshal(&T{
    X: 1,
    U: &U{
        T: &T{
            X: 2,
        },
    },
})
fmt.Println(string(b)) // {"X":1,"U":{"T":{"X":2,"U":null}}}

In

go-json

opStructFieldRecursive

In this operation, after acquiring the opcode sequence used for recursive processing, the function is not called recursively as it is, but the necessary values ​​are saved by itself and implemented by moving to the next operation.

The technique of implementing recursive processing with the

JMP

CALL

For more details, please refer to the article ( but Japanese only ).

Dispatch by typeptr from map to slice

When retrieving the data cached from the type information by

typeptr

sync.Map

However, this is slow, so it's a good idea to use the

atomic

segmentio/encoding/json

This implementation slows down the set instead of speeding up the get, but it works well because of the nature of the library, it encodes much more for the same type.

However, as a result of profiling, I noticed that

runtime.mapaccess2

There is an API named

typelinks

runtime

reflect

The fact that all type information can be acquired means that by constructing slices in advance with the acquired total number of type information, it is possible to look up with the value of

typeptr

However, if there is too much type information, it will use a lot of memory, so by default we will only use this optimization if the slice size fits within 2Mib .

If this approach is not available, it will fall back to the

atomic

If you want to know more, please refer to the implementation here

Decoder

Dispatch by typeptr from map to slice

Like the encoder, the decoder also uses typeptr to call the dedicated process.

Faster termination character inspection using NUL character

In order to decode, you have to traverse the input buffer character by position. At that time, if you check whether the buffer has reached the end, it will be very slow.

buf

[]byte

cursor

int64

buflen := len(buf)
for ; cursor < buflen; cursor++ { // compare cursor and buflen at all times, it is so slow.
    switch buf[cursor] {
    case ' ', '\n', '\r', '\t':
    }
}

Therefore, by adding the

NUL

\000

for {
    switch buf[cursor] {
    case ' ', '\n', '\r', '\t':
    case '\000':
        return nil
    }
    cursor++
}

Use Boundary Check Elimination

Due to the

NUL

buf[cursor]

Therefore,

go-json

func char(ptr unsafe.Pointer, offset int64) byte {
    return *(*byte)(unsafe.Pointer(uintptr(ptr) + uintptr(offset)))
}

p := (*sliceHeader)(&unsafe.Pointer(buf)).data
for {
    switch char(p, cursor) {
    case ' ', '\n', '\r', '\t':
    case '\000':
        return nil
    }
    cursor++
}

Checking the existence of fields of struct using Bitmaps

I found by the profiling result, in the struct decode, lookup process for field was taking a long time.

For example, consider decoding a string like

{"a":1,"b":2,"c":3}

type T struct {
    A int `json:"a"`
    B int `json:"b"`
    C int `json:"c"`
}

At this time, it was found that it takes a lot of time to acquire the decoding process corresponding to the field from the field name as shown below during the decoding process.

fieldName := decodeKey(buf, cursor) // "a" or "b" or "c"
decoder, exists := fieldToDecoderMap[fieldName] // so slow
if exists {
    decoder(buf, cursor)
} else {
    skipValue(buf, cursor)
}

To improve this process,

json-iterator/go

gojay

switch-case

go-json

The range of values ​​per character can be represented by

[256]byte

int8

• Base ( 8bit ):

  00000000

• Key "a":

  00000001

  ( assign key "a" to the first bit )
• Key "b":

  00000010

  ( assign key "b" to the second bit )
• Key "c":

  00000100

  ( assign key "c" to the third bit )

Bitmap structure is the following

        | key index(0) |
------------------------
 0      | 00000000     |
 1      | 00000000     |
~~      |              |
97 (a)  | 00000001     |
98 (b)  | 00000010     |
99 (c)  | 00000100     |
~~      |              |
255     | 00000000     |

You can think of this as a Bitmap with a height of

256

[maxFieldKeyLength][256]int8`

When decoding a field character, check whether the corresponding character exists by referring to the pre-built bitmap like the following.

var curBit int8 = math.MaxInt8 // 11111111

c := char(buf, cursor)
bit := bitmap[keyIdx][c]
curBit &= bit
if curBit == 0 {
    // not found field
}

If

curBit

0

• input:

  {"a":1}

  go
  type T struct {
  X int `json:"abc"`
  }
  

  ※ Since

  a

  is shorter than

  abc

  , it can decode to the end of the field character without

  curBit

  being 0.

Rest assured. In this case, it doesn't matter because you can tell if you hit by comparing the string length of

a

abc

Finally, calculate the position of the bit where

1

Using this technique, field lookups are possible with only bitwise operations and access to slices.

go-json

[maxKeyLen][256]int16

Currently, this optimization is not performed when the maximum length of the field name is long (specifically, 64 bytes or more) in addition to the limitation of the number of fields from the viewpoint of saving memory usage.

Others

I have done a lot of other optimizations. I will find time to write about them. If you have any questions about what's written here or other optimizations, please visit the

#go-json

gophers.slack.com

Reference

Regarding the story of go-json, there are the following articles in Japanese only.

• https://speakerdeck.com/goccy/zui-su-falsejsonraiburariwoqiu-mete
• https://engineering.mercari.com/blog/entry/1599563768-081104c850/

License

MIT