Karmem

Karmem is a fast binary serialization optimized for Golang and TinyGo, and also available to Zig, AssemblyScript, C and Swift.

Github Downloads

Introduction

Karmem is a fast binary serialization format. The priority of Karmem is to be easy to use while been fast as possible. It's optimized to take Golang and TinyGo's maximum performance and is efficient for repeatable reads, reading different content of the same type. Karmem has proven to be ten times faster than Google Flatbuffers, with the additional overhead of bounds-checking included.

Motivation

Karmem was designed to tackle the most prominent issue: sharing data between wasm-hosts, wasm-guests, and native guests. Currently, we use something similar to a "command-event pattern", where multiple wasm-instances receive the same event/data and then return one command/data. But, first, calling exported/imported functions are expensive and almost prohibitive. So we tried many options as possible.

First, why not choose Witx? It is a good project and aimed at WASM. However, it seems more complex to use and not limited to serialization. Furthermore, that project was not intended to be portable to non-wasm and doesn't support Golang, our primary language.

Why not use Flatbuffers? We tried, but it's not fast enough and causes panic due to the lack of bound-checking. Also, decoding using to struct (using "Object-API) is terrible and generates too much garbage.

Why not use Cap'n'Proto? It's a good alternative but lacks implementation for Zig and AssemblyScript, which is a top priority. It also has more allocations, and the generated API is more complicated to use than Karmem.

Compare

How Karmem work compared with other serializers?

  • Read without parsing/decode: Karmem offers random-access for data. You can access any data directly without parsing/unpacking. Reading fields have almost zero performance overhead compared to reading native structs.

  • Backward Compatibility: Karmem was designed to offer backward compatibility, regardless of the language. That is achieved using tables (struct name table), allowing new fields to be appended at anytime.

  • Schema Defined: Karmem was built with a custom schema language. The schema eliminates the need for runtime parsing, increasing performance and reliability.

  • Null-Safety: Null is hard to handle and may cause more issues than benefits. That is not an issue if null is not part of the schema. Karmem doesn't handle pointers or null or optional fields. That may be a compromise, but that makes deserialization predictable, reusable, faster and safer in our tests.

  • Native Slices: Karmem uses native-slice where possible, Zig and Golang currently support it, which means you don't have functions like SomeList.Get(index) to access each field.

  • Fixed Offset Source: Unlike other schemas, Karmem doesn't use offsets based on the value position. That may introduce some security issues, mitigated using Limited Arrays, but makes it easier to implement in any language.

Performance

Performance varies across each compiler and language, Golang is based language for comparison and was compiled using GC (Golang Compiler) for native platforms and TinyGo for WebAssembly/WASI.

In the following benchmarks, consider "Reading" as random-accessing some fields of the serialized data, "Decode" as decoding/unmarshalling the entire serialized data to an native struct, "Encode" as the process of encoding/marshalling an native struct to Karmem/Flatbuffers.

Struct VS Karmem VS Flatbuffers @ Native

Performance comparison with Flatbuffers and Karmem using similar schemas, with same amount of data. Also, comparing performance with native-struct.

Flatbuffers VS Karmem @ WebAssembly

Performance comparison with Flatbuffers and Karmem using similar schemas, with same amount of data. Running on Wazero.

Karmem VS Karmem @ WebAssembly

Performance between Karmem implementation. Notice, the decoded schema contains strings, which penalizes some non-UTF8 string.

Introduction

Code-generator is required to write and read serialized data. We use a code-generator to provide the best performance possible in any language.

Download

There's few ways to get Karmem generator. Remember to add the binary into your PATH environment variable.

Install via Golang

If you have Golang installed, you can download it by:

go install karmem.org/cmd/karmem

Install manually

You can download the pre-compiled binaries on Github, click here.

Usage

Once you have a schema defined, you can generate the code. First, you need to karmem installed, get it from the releases page or run it with go.

karmem build --assemblyscript -o "output-folder" your-schema.km

If you already have Golang installed, you can use go karmem.org/cmd/karmem build --zig -o "output-folder" your-schema.km instead.

Commands

Currently, Karmem supports the following commands:

build
karmem build {arguments}

Supported arguments:

  • --zig: Enable generation for Zig

  • --golang: Enable generation for Golang

  • --assemblyscript: Enable generation for AssemblyScript

  • --swift: Enable generation for Swift

  • --c: Enable generation for C

  • -o <dir>: Defines the output folder

  • <input-file>: Defines the input schema

Introduction

The syntax of the schema language (also known as Interface Definition Language) is similar to C and Golang, it should look familiar to other IDL languages, such as Protobuf and Flatbuffers too.

Example

Take a look at one simple example, which describes one player and one message which contains a list of players.

karmem MyGame;

enum Color uint8 { None; Red; Green; Blue; }

struct Vec3 inline {
  X float32;
  Y float32;
  Z float32;
}

struct PlayerData table {
  Pos       Vec3;
  Mana      int16;
  HP        uint32;
  Name      []char;
  IsFriendly  bool;
  Inventory []byte;
  Color     Color;
}

struct Player inline {
  Data PlayerData;
}

struct GameState table {
  Players []Player;
}

Types

Karmem uses a strict-type, here we can see what types are supported and how you can use them.

Primitive

Primitive types are always inlined with the schema, the size varies from 1 byte to 8 bytes.

  • Unsigned Integers: uint8, uint16, uint32, uint64
  • Signed Integers: int8, int16, int32, int64
  • Floats: float32, float64
  • Boolean: bool
  • Byte: byte, char
Arrays

Karmem also have arrays and slices, holding set of inlined values at once.

  • Fixed: [{Length}]{Type} (example: [123]uint16, [3]float32)
  • Dynamic: []{Type} (example: []char, []uint64)
  • Limited: [<{Length}]{Type} (example: [<512]float64, [<42]byte)

In all cases, {Type} must be an inline type. It cannot be Enum or Table struct.

Struct

Currently, Karmem has two structs types: inline and table.

Inline Struct

Inline structs, as the name suggests, are inlined when used. That reduces the size and may improve the performance. However, it can't have their definition changed. In order words: you can't edit the description of one inline struct without breaking compatibility.

struct Vec3 inline {
 X float32;
 Y float32;
 Z float32;
}

That struct is exactly the same of [3]float32 and will have the same serialization result. Because of that, any change of this struct (for instance, change it to float64 or adding new fields) will break the compatibility.

Table Struct

Table can be used when backward compatibility is important. For example, tables can have new fields append at the bottom without breaking compatibility.

struct User table {
 Name []char;
 Email []char;
 Password []char;
}

Let's consider that you need another field... For tables, it's not an issue:

struct User table {
 Name []char;
 Email []char;
 Password []char;
 Telephone []char;
}

Since it's a table, you can add new fields at the bottom of the struct, and both versions are compatible between them.

Enums

Enums can be used as an alias to Integers type, such as uint8.

enum Team uint8 {
 Unknown;
 Humans;
 Orcs;
 Zombies = 255;
}

Enums must start with a zero value, the default value in all cases. If the value of any enum is omitted, it will use the order of enum as value.

Primitive

All types are serialized as Little-Endian, and may not work on Big-Endian machines.

Bool
true = {0x00} | true = {0x01} ~ {0xFF}
uint8/Byte
42 = {0x2a}
int8
-42 = {0xd6}
uint16
420 = {0xa4, 0x01}
int16
-420 = {0x5c, 0xfe}
uint32
42000 = {0x10, 0xa4, 0x00, 0x00}
int32
-42000 = {0xf0, 0x5b, 0xff, 0xff}
uint64
420000000000 = {0x00, 0x68, 0xf3, 0xc9, 0x61, 0x00, 0x00, 0x00}
int64
-420000000000 = {0x00, 0x98, 0x0c, 0x36, 0x9e, 0xff, 0xff, 0xff}
float32
420000000000 = {0x00, 0x68, 0xf3, 0xc9, 0x61, 0x00, 0x00, 0x00}
float64
-420000000000 = {0x00, 0x98, 0x0c, 0x36, 0x9e, 0xff, 0xff, 0xff}
char

Char is similar to Byte. However, it assumes that the string is UTF8, when arrays are used.

"A" = {0x10}

Enum

Enum are represented using the defined type, see above how numeric types are represented.

Fixed Arrays

All fixed arrays are represented as sequence of primitive types

[3]Uint8
[1,2,3] = {0x01, 0x02, 0x03}

Inline Struct

All inline structs are represented similar to Fixed Array, see above how it is represented.

Struct are "packed", without padding between values. However, the struct size must be multiple of 8, end-padding is added if the struct is shorter.

struct example inline{isValid bool; year uint16;}
{true, 2022} = {0x01, 0xe6, 0x07, 0x00, 0x00, 0x00, 0x00, 0x00}

Dynamic Arrays

All dynamic arrays are represented with 3x uint32. See above how uint32 are represented.

All
{offset, size, size_each}

The Offset is the pointer where the data is, offset = 0 is the begging of the message. Size is the size, in bytes, of the entire array. Size Each is the size of each item, currently it's not used that much.

struct example inline{Data []uint16;}
{[1,2,3]} = {
    00: 0x10, 01: 0x00, 02: 0x00, 03: 0x00,
    04: 0x06, 05: 0x00, 06: 0x00, 07: 0x00,
    08: 0x02, 09: 0x00, 10: 0x00, 11: 0x00,
    12: 0x00, 13: 0x00, 14: 0x00, 15: 0x00,
    16: 0x01, 17: 0x00, 18: 0x02, 19: 0x00,
    20: 0x03, 21: 0x00,
}

In order to simplify, the array is {offset = 0x10, length = 0x06, size = 0x02}. The start of our array ([1,2,3]) is at position 0x10 (16), as mentioned on offset. The size is 0x06 (6), because it takes 6 bytes. The size_each is 0x02 (2) because each uint16 occupy 2 bytes. In that case we know that exists 3 items, because 6/2 (size/size_each).

Table Struct

Table is the most complex structures we have. It acts like a pointer, and modified struct.

Source
{offset}

Anyone that have a struct with Table-Struct as value, will have just one offset, which is 1x uint32

Table
{size, ... fields ...}

Table struct is similar to Inline struct, however it contains a new metadata field, which we call "size". The size field is always at index 0.

Table struct must have size multiple of 8, otherwise padding is added.

Example

Schema

karmem main;

struct Card table {
    Number uint64;
}

struct Player inline {
    Data card;
}

Data

Player{
    Data: Card{
        Number: 42,
    },
}

Encoded

00: 0x08, 01: 0x00, 02: 0x00, 03: 0x00,
04: 0x00, 05: 0x00, 06: 0x00, 07: 0x00,
08: 0x10, 09: 0x00, 10: 0x00, 11: 0x00,
12: 0x2a, 13: 0x00, 14: 0x00, 15: 0x00,
16: 0x00, 17: 0x00, 18: 0x00, 19: 0x00,
20: 0x00, 18: 0x00, 20: 0x00, 21: 0x00,