Understanding and improving the game's savefiles, serialization and compression

[Ivelieu]

Over the past week or so, I've been determined to figure something out: why are save files so huge in vintage story? Over a similar spatial area, the map files take up hundreds of times more space compared to modded minecraft savefiles that I'm accustomed to. While they are of course not the same game, many of the underlying data storage approaches are similar, and I wanted to figure out the disrepancy. Sqlite, compression, palettes, serialization- there are many different moving parts, and judging from what I could find in the discord, I don't think many people understand how they are used in vintage story, so I thought it could be useful to write about. A good part of this is due to much of the heavy lifting being done inside of the closed-source VintagestoryLib.dll, My understanding is that decompiling it is encouraged and in some cases even required for modding, but that does have limitations of not showing comments and most variable names getting lost. My goals with this post are:
- to explain what I've learned from reading the source code.
- pointing out areas where improvements can be made with reducing savefile sizes and IL code
- explaining why I think most of the savefile and chunk I/O be moved out of VintagestoryLib in the interest of improving performance.

Diagnosing the problem

I learn that .vcdbs files are sqlite databases with protobuf encoded blobs in them, so I decide to pull them up in a sqlite viewer. Protocol buffers, or protobuf for short, is a pretty simple serialization data format. Messages are serialized into a binary wire format which is compact, forward- and backward-compatible, but not self-describing (that is, there is no way to tell the names, meaning, or full datatypes of fields without an external specification). The dotnet implementation, protobuf-net, does not include any compression, but it does use something called a varint encoding by default (also possible standalone in dotnet), which reduces the space used by small values by storing in each byte, 7 bits of payload, and 1 most significant bit indicating "there's another byte to read". I found vs-proto which can be used to generate and has a recent copy of the "schema" file which describes all the protobuf objects and their data types, and they can also be figured out by looking at the source code. 

The contents of the sqlite tables is explained at a high level on the wiki, and I can quickly make a table of my survival world with a total size of 245M:

As indicated by the wiki and reading the source code, the chunk table is the only one that stores 3d data of blocks in the world. mapchunk and mapregion store 2d data, so why is mapchunk bigger? I put a breakpoint in Vintagestorylib's ServerMapChunk.FastSerialize which catches the data just as it is getting sent to protobuf for being stored in sqlite. 

These all the arrays stored in mapchunk protobuf blob: 
RainHeightMap: ushort[1024]
TopRockIdMapOld: int[1024]
WorldGenTerrainHeightMap: ushort[1024]
NewBlockEntities: Pretty small
CaveHeightDistort: byte[1024]
SedimentaryThicknessMap: ushort[1024]
TopRockIdMap: int[1024]

This alone is 2048*3 + 4096*2 + 1024 = 15360 B per chunk column, and it doesn't get compressed other than from protobuf varints. It turns out that the chunk table is usually smaller than this, which is the simple answer why mapchunk is bigger. 

It's pretty remarkable to me how I can get a half decent 2d layout of ore maps just by ripping a save's mapregion sqlite blobs, mapping to utf-8 and stretching a text box.

Palette basics

In minecraft the term used for optimising chunk storage is local palettes. A similar idea is indexed colors in images, where the png format allows for encoding directly in an indexed format as opposed to a big RGB/A array.

This is the same general principle behind the LZ77 family of compression algorithms in combination with huffman encodings (gzip/DEFLATE). There are a few advantage of doing this at the program level instead of relying on an external compression algorithm for indexing the chunk data:

• different spatial cutoffs can by dynamically chosen to minimise size. For example, there are cases where 32x(32x1x32) spatial indexing with 32 index tables will outperform 1x(32x32x32) indexing with one index table, and vice versa. This is because the varint encoding saves space, and a concatenated huffman encoding can save more space. Depending on the size of the index, it's also possible to save space by electing to use less than a 7-bit varint payload. It can be difficult to make efficient algorithms to recalculate spatial cutoffs, palettes, and huffman codes however.
• The chunk data is fundamentally spatial, which means it can be described using linear interpolation, 2d or 3d raster vectorization, and spatial clustering algorithms. A combination of these is likely to far surpass compression ratios compred to an approach that only uses palettes.

Vintage story uses both palettes and compression for chunk data, but as I'll explain, I think there are pretty large flaws in the implementations of both. Assuming a world height of 256 which is configurable, data is partitioned into vertical chunks in the WorldChunk class (32x256x32), and further partitioned into ChunkData, containing multiple ChunkDataLayers which contain 32x32x32 spatial regions. There's a layer for blocks, fluids and light - the fluid one is often empty, but all three store their information using the same palette system. The liquid and block layers are actually BlockChunkDataLayers, but they do essentially the same thing as ChunkDataLayer. The light layer is actually fully populated for all ChunkData instances. This is my first observation: Considering how easy it is to compute, it's incredibly wasteful, I would think, to give a full integer's worth of light level to every single block, especially those completely surrounded by blocks, and to store that in the savefile. In a ChunkDataLayer with some trees or cave entrances, they can even take up more space than the block layer for the same spatial region! I don't know how it's ended up like that, but having water stored separately is not such a bad idea since it simplifies implementing waterlogging and in-world crafting, and the data is empty if there's no water in a chunk.

Chunk format

Before going over the palette system, I'll explain the coordinate system used inside ChunkDataLayers - a single integer is divided up into an x, y and z coordinate, each with 5 bits worth that can describe any of 32 values along that axis inside the region. The ChunkDataLayer arrays stored in WorldChunk and ChunkColumnLoadRequest are stored in ascending height in their arrays too. Every time a block is accessed, this encoded coordinate integer is passed - and it only uses 15 of the 32 bits inside an int. Technically, the chunksize is paramaterized in some places in VintagestoryLib, but due to needing to optimise around this value so much, I am very doubtful it could ever be changed. 

 

Palette implementation (Vintagestorylib.dll:ChunkDataLayer.cs)

The reason why this coordinate system is important, is the way palette data is stored requires cutting up the int to use it. Each individual ChunkDataLayer contains an int[] palette and an int[][] dataBits. When the layer is first created, the palette starts out with just a single entry or key-value pair, and dataBits starts as an int[0][1024]. As blocks get added to the chunk, they get added to the palette if they aren't there, and the first dimension of dataBits changes size to int[X][1024], where X is the number of bits in the palette count. So if the palette has 13 key-value pairs, 4 bits are needed to describe that number 13, so dataBits would be of the shape int[4][1024] and it only takes 4 bits to describe the palette's key, which corresponds to a value (for blocks, a block ID). 

In the example below, the palette is almost entirely full - just for sake of example, almost every single block in the chunk has a different ID, and the palette's size has a bitwidth of 15. To determine what block is present at a particular (x,y,z) coordinate inside the ChunkDataLayer, the first five bits are used as a left bitshift on the stored integer. Unlike in most other languages, in dotnet bitshift operators can bitshift by values larger than the bit-width of the target, and the operation just truncates to the correct bit width. Supposing we want to know (x: 3, y: 15, z: 31), 15*32+31=511, so the coordinate for the first bit of the palette key is stored at dataBits[0][511] << 3. To get the full key, this is iterated over the bitwidth of the palette, so the next bit is dataBits[1][511] << 3, all the way to dataBits[14][511] << 3. All 15 of these bits represent a palette key, and looking up the value in the palette table with palette[4017] gives the block ID.

Here is the decompiled code of the function behind what I just explained, with some comments I've added:

// BlockChunkDataLayer.cs
private Block getBlockGeneralCase(int index3d)
{
  int num1 = index3d % 32; // num1 = the x coordinate
  index3d /= 32; // what's left: y * 32 + z
  int num2 = 1; // Which value corresponds to the 
  int index1 = 0;
  for (int index2 = 0; index2 < this.bitsize; ++index2) // Which bit position are we reading?
  {
    index1 += (this.dataBits[index2][index3d] >> num1 & 1) * num2;
    // The bitshift happens before the logical AND. 
    // This makes the bracket expansion equal to the value of the i'th bit of dataBits[index2][index3d],
    // where i is the position of the x coordinate (num1)
    // index3d looks up the correct position on the (y,z) slice of dataBits, and index2 indicates which
    // bit to read
    num2 *= 2; // num2 = 2^index2
  }
  return BlockChunkDataLayer.blocksByPaletteIndex[index1]; // Lookup with the key
}

// ChunkDataLayer.cs
// The code is almost identical.
protected int GetGeneralCase(int index3d)
{
  int index1 = (index3d & (int) short.MaxValue) / 32; 
  int num = 1;
  int index2 = 0;
  this.readWriteLock.AcquireReadLock();
  for (int index3 = 0; index3 < this.bitsize; ++index3)
  {
    index2 += (this.dataBits[index3][index1] >> index3d & 1) * num;
    num *= 2;
  }
  this.readWriteLock.ReleaseReadLock();
  return this.palette[index2];
}

These are called "general case" functions, because they are actually not the only ones. The palette lookup is implemented with a function pointer, or in dotnet known as a "delegate". There are functions one through five which do the same thing, except they have an unrolled loop:

private Block getBlockOne(int index3d)
{
  int num = index3d % 32;
  index3d /= 32;
  return BlockChunkDataLayer.blocksByPaletteIndex[this.dataBit0[index3d] >> num & 1];
}

private Block getBlockTwo(int index3d)
{
  int num = index3d % 32;
  index3d /= 32;
  return BlockChunkDataLayer.blocksByPaletteIndex[(this.dataBit0[index3d] >> num & 1) + 2 * (this.dataBit1[index3d] >> num & 1)];
}

This is a critical function for speed, so it's understandable to want to optimise it, and loop unrolling would help. These functions are not inlined however, so they still take function call overhead. More importantly though, the approach of storing only one bit of the value in each integer at a time requires reading multiple integers which are explicitly non-contiguous in memory. That means multiple clock cycles. The decompiler isn't super helpful with variable names, but the IL doesn't lie - this approach gets slowed down. That being said, there's another function ChunkDataLayer.GetUnsafe which, despite its name, seems to do about the same thing as these other Get functions and just throws an exception if the palette isn't configured properly. But this one doesn't have function call overhead.

The ChunkDataLayer.Set function is a little more confusingly written by the decompiler:

public void Set(int index3d, int value) {
  // [...]
  // index1 = the key in the palette array corresponding to 'value'
  // it has a basic cache lookup, but this is the important part:
  int num1 = 1 << index3d; // Store the x component of the coordinate
  int num2 = ~num1;
  index3d /= 32; // Drop the x component of the coordinate
  this.readWriteLock.AcquireWriteLock();
  if ((index1 & 1) != 0)
    this.dataBit0[index3d] |= num1;
  else
    this.dataBit0[index3d] &= num2;
  for (int index2 = 1; index2 < this.bitsize; ++index2)
  {
    if ((index1 & 1 << index2) != 0)
      // "If the i'th bit of the block ID is 1..."
      this.dataBits[index2][index3d] |= num1;
      // Add a 1 to the bit in the dataBits int corresponding to the (x,y,z) coordinate
    else
      this.dataBits[index2][index3d] &= num2;
      // Add a 0 to the bit in the dataBits int corresponding to the (x,y,z) coordinate
  }
  this.readWriteLock.ReleaseWriteLock();
}

My thoughts on it at this point:

Advantages:

• Fully packs bits into integers using bitwise arithmetic
• Only 32x32x32 regions that contain blocks need to be stored
• The number of bits in the palette is dynamically resized as needed
• The data array can be resized dynamically without needing to iterate over all blocks

Disadvantages:

• All blocks require the same number of bits to store regardless of their frequency; i.e. no Huffman coding is used
• The bitwise separation of the palette keys in dataBits fragments data in such a way that compression algorithms must work harder to save less space 
• Because it is in VintagestoryLib.dll, it's unreasonable for modders to modify elements of data storage using fragile harmony patches. The current implementation is not designed to be interoperable with alternative chunk data formats.
• Resizing the palette or freeing unused elements in it (ChunkDataLayer.CleanUpPalette) requires inspecting every block in the chunk
• The bitwise separation of palettte keys in dataBits compiles to inefficient IL; branch prediction is not needed, but each separate array integer needs to be read in a separate cycle; using delegate functions also prevents inlining of this very frequently called function.

Compression

Although there is gzip, deflate and zstd written up with wrapper classes, only zstd is used with a hardcoded -3 compression level. (It was news to me that negative compression levels even exist.) It seems strange to hard code something like that, especially given the way it is used to compress byte arrays that often increase in size post-compression. From what I can see, this zstd compression is only used for the chunk data and packets. The problem here is more that it's only used at one step of the serialization process towards becoming an sqlite blob. 

Juast as a proof of concept, I wrote some simple harmony hooks to replace all of the tables with compressed versions right before gettting sent to sqlite. I had a look for a few libraries and found GrindCore.net, a bundle of easy to use c compression implementations, the one I was looking for being fast-lzma2. This snippet only shows the hook for one of the tables, but I made one for each table, which is why I set the block size so high.

using Nanook.GrindCore;

public static byte[] compressLZMAGrindcore(byte[] input) {
  var compressor = CompressionBlockFactory.Create(CompressionAlgorithm.FastLzma2, CompressionType.Level3, blockSize: 4194304);
  byte[] output = new byte[compressor.RequiredCompressOutputSize];
  int compressedSize = output.Length;


  [HarmonyPatch(typeof(SQLiteDbConnectionv2), "SetChunks")]
  [HarmonyPrefix]
  public static bool encodeSetChunks(IEnumerable<DbChunk> chunks, SQLiteDbConnectionv2 __instance, SqliteConnection ___sqliteConn,
                                     SqliteCommand ___setMapChunksCmd) {
    lock (__instance.transactionLock) {
      using (SqliteTransaction sqliteTransaction = ___sqliteConn.BeginTransaction()) {
        ___setMapChunksCmd.Transaction = sqliteTransaction;
        foreach (DbChunk chunk in chunks) {
          byte[] dataCompressed = compressLZMAGrindcore(chunk.Data);
          ___setMapChunksCmd.Parameters["position"].Value = (object)chunk.Position.ToChunkIndex();
          ___setMapChunksCmd.Parameters["data"].Value = (object)dataCompressed;
          ___setMapChunksCmd.ExecuteNonQuery();
        }
        sqliteTransaction.Commit();
      }
    }
    return false;
  }

I generated two worlds on a fixed seed - with and without the patches. I don't move, set the render distance to a few hundred, wait for chunks to generate then quit. I do a csv export to compare tables.

It's not meant to be a robust experiment, in part because I don't want to spend a lot of time writing Harmony patches that will go outdated very quickly. But I think it gives a good indicator of how much wasted space there is in these files. Doing this alone I was able to get an overall compression ratio of 3.4, with no noticeable change in map save/load times. For the chunk data specifically, I got a compression ratio of about 12. Adding compression steps at other stages in serialization is likely to take this further, but the most effective approach would be to change the internal palette representation to export using 3d raster vectorization, clustering, dynamic chunk spatial region sizes and huffman coding on the palette.

It's not surprising to me that MapChunk did not get a large boost, since it's mostly filled with psuedorandom ints, and it seems like most of its fields could be stored using IntDataMap2d- "A datastructure to hold 2 dimensional data in the form of ints. Can be used to perfrom bilinear interpolation between individual values". The ones that can't be encoded using that, I struggle to see an argument for why they should be saved in the world file at all as opposed to a generating seed and parameters where applicable, as they are expensive to store - at least in their current format - and cheap to compute. 

ArrayConvert

Incedentally while profiling save/loading, I came across ArrayConvert.Build. It's called by ArrayConvert.CompressAndCombine, which is ultimately used for WorldChunk.Pack. It has some very interesting decompiled code to me:

  internal static byte[] Build(int lengthA, byte[] dataA, byte[] data, int length)
  {
    byte[] numArray = new byte[length + lengthA + 4];
    if (length + lengthA == 0)
      return numArray;
    numArray[0] = (byte) lengthA;
    numArray[1] = (byte) (lengthA >> 8);
    numArray[2] = (byte) (lengthA >> 16);
    numArray[3] = (byte) (lengthA >> 24);
    int index1 = 4;
    int num1 = lengthA / 4 * 4;
    int index2;
    for (index2 = 0; index2 < num1; index2 += 4)
    {
      numArray[index1] = dataA[index2];
      numArray[index1 + 1] = dataA[index2 + 1];
      numArray[index1 + 2] = dataA[index2 + 2];
      numArray[index1 + 3] = dataA[index2 + 3];
      index1 += 4;
    }
    while (index2 < lengthA)
      numArray[index1++] = dataA[index2++];
    int num2 = length / 4 * 4;
    int index3;
    for (index3 = 0; index3 < num2; index3 += 4)
    {
      numArray[index1] = data[index3];
      numArray[index1 + 1] = data[index3 + 1];
      numArray[index1 + 2] = data[index3 + 2];
      numArray[index1 + 3] = data[index3 + 3];
      index1 += 4;
    }
    while (index3 < length)
      numArray[index1++] = data[index3++];
    return numArray;
  }

What it does is convert two int[] objects into a single byte[] object, by storing in order, the first array's size, the first array, then the second array's size and the second array. It could be done with four Buffer.BlockCopy calls, which seems to be the most efficient way to do a bitwise memory copy. I was just surprised to see all these loops, and all these explicit int to byte conversions - at first I thought the decompiler was being weird, but I think the IL is telling the truth here. My understanding is the dotnet runtime is not going to try optimising something like this away. Here is a single one of those loops, where each step is expanded to its own copy/addittion: 

// start of loop, entry point: IL_0066

// [116 7 - 116 39]
IL_003a: ldloc.0      // numArray
IL_003b: ldloc.2      // index1
IL_003c: ldarg.1      // dataA
IL_003d: ldloc.1      // index2
IL_003e: ldelem.u1
IL_003f: stelem.i1

// [117 7 - 117 47]
IL_0040: ldloc.0      // numArray
IL_0041: ldloc.2      // index1
IL_0042: ldc.i4.1
IL_0043: add
IL_0044: ldarg.1      // dataA
IL_0045: ldloc.1      // index2
IL_0046: ldc.i4.1
IL_0047: add
IL_0048: ldelem.u1
IL_0049: stelem.i1

// [118 7 - 118 47]
IL_004a: ldloc.0      // numArray
IL_004b: ldloc.2      // index1
IL_004c: ldc.i4.2
IL_004d: add
IL_004e: ldarg.1      // dataA
IL_004f: ldloc.1      // index2
IL_0050: ldc.i4.2
IL_0051: add
IL_0052: ldelem.u1
IL_0053: stelem.i1

// [119 7 - 119 47]
IL_0054: ldloc.0      // numArray
IL_0055: ldloc.2      // index1
IL_0056: ldc.i4.3
IL_0057: add
IL_0058: ldarg.1      // dataA
IL_0059: ldloc.1      // index2
IL_005a: ldc.i4.3
IL_005b: add
IL_005c: ldelem.u1
IL_005d: stelem.i1

// [120 7 - 120 18]
IL_005e: ldloc.2      // index1
IL_005f: ldc.i4.4
IL_0060: add
IL_0061: stloc.2      // index1

There's also this inoccuous line 

int num1 = lengthA / 4 * 4;

which does exist in IL and does have the probably-unintended side effect of num1 = lengthA - (lengthA mod 4). Which, for a specifically engineered palette size, would probably actually corrupt the chunk.

I guess all this makes me think is that there is a lot of low hanging fruit to improve performance in this game. But with so much of it around this VintagestoryLib.dll library, even with the amazing modding API this game has, it feels discouraging that the most important improvements I would want to make aren't realistically possible for me to do in a mod.

Please let me know if I got anything wrong or missed something important! At least, I hope this post is helpful to others and that it stimulates discussion on one of this less looked-at areas of the game.

Edited February 15 by Ivelieu
rm duplicate images

[zsuatem]

That last ArrayConvert.Build method made me curious, so I ran a quick BenchmarkDotNet comparison between the original loop-based version and a simple Buffer.BlockCopy implementation.

Release build, .NET 10.0.3.

Method	Size	Mean	Error	StdDev	Median	Ratio	RatioSD	Gen0	Gen1	Gen2	Allocated	Alloc Ratio
Original	4096	4,094.5 ns	74.51 ns	73.17 ns	4,078.0 ns	1.00	0.02	0.9766	-	-	8.03 KB	1.00
BlockCopy	4096	366.6 ns	15.12 ns	44.35 ns	353.9 ns	0.09	0.01	0.9823	-	-	8.03 KB	1.00
Original	16384	16,381.6 ns	322.53 ns	345.11 ns	16,307.2 ns	1.00	0.03	3.8757	-	-	32.03 KB	1.00
BlockCopy	16384	1,409.2 ns	28.47 ns	75.50 ns	1,399.4 ns	0.09	0.00	3.9043	-	-	32.03 KB	1.00
Original	65536	86,562.0 ns	1,688.07 ns	2,474.35 ns	85,771.1 ns	1.00	0.04	41.6260	41.6260	41.6260	128.04 KB	1.00
BlockCopy	65536	36,093.2 ns	713.88 ns	1,192.74 ns	35,702.5 ns	0.42	0.02	41.6260	41.6260	41.6260	128.04 KB	1.00

For smaller sizes (4–16 KB) the difference is roughly ~10×.
For larger buffers (64 KB) the gap shrinks, but it’s still noticeably faster.

Allocations are identical in both cases (one byte[] per call), so this is purely a copy-performance difference.

Just sharing the numbers since your post made me dig into this part out of curiosity

 

 

For reference, this is the version I tested:

Spoiler

using System;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using System.Buffers.Binary;
using System.Runtime.CompilerServices;


[MemoryDiagnoser]
public class ChunkBuildBenchmark
{
    private byte[] dataA;
    private byte[] data;

    [Params(4096, 16384, 65536)]
    public int Size;

    [GlobalSetup]
    public void Setup()
    {
        dataA = new byte[Size];
        data = new byte[Size];

        Random.Shared.NextBytes(dataA);
        Random.Shared.NextBytes(data);
    }

    [Benchmark(Baseline = true)]
    public byte[] Original()
        => BuildOriginal.Build(dataA.Length, dataA, data, data.Length);

    [Benchmark]
    public byte[] BlockCopy()
        => BuildBlockCopy.Build(dataA.Length, dataA, data, data.Length);
    
}

internal static class BuildOriginal
{
    public static byte[] Build(int lengthA, byte[] dataA, byte[] data, int length)
    {
        byte[] numArray = new byte[length + lengthA + 4];
        if (length + lengthA == 0)
            return numArray;

        numArray[0] = (byte)lengthA;
        numArray[1] = (byte)(lengthA >> 8);
        numArray[2] = (byte)(lengthA >> 16);
        numArray[3] = (byte)(lengthA >> 24);

        int index1 = 4;
        int num1 = lengthA / 4 * 4;
        int index2;

        for (index2 = 0; index2 < num1; index2 += 4)
        {
            numArray[index1] = dataA[index2];
            numArray[index1 + 1] = dataA[index2 + 1];
            numArray[index1 + 2] = dataA[index2 + 2];
            numArray[index1 + 3] = dataA[index2 + 3];
            index1 += 4;
        }

        while (index2 < lengthA)
            numArray[index1++] = dataA[index2++];

        int num2 = length / 4 * 4;
        int index3;

        for (index3 = 0; index3 < num2; index3 += 4)
        {
            numArray[index1] = data[index3];
            numArray[index1 + 1] = data[index3 + 1];
            numArray[index1 + 2] = data[index3 + 2];
            numArray[index1 + 3] = data[index3 + 3];
            index1 += 4;
        }

        while (index3 < length)
            numArray[index1++] = data[index3++];

        return numArray;
    }
}

internal static class BuildBlockCopy
{
    public static byte[] Build(int lengthA, byte[] dataA, byte[] data, int length)
    {
        var result = new byte[lengthA + length + 4];
        BinaryPrimitives.WriteInt32LittleEndian(result, lengthA);
        Buffer.BlockCopy(dataA, 0, result, 4, lengthA);
        Buffer.BlockCopy(data, 0, result, 4 + lengthA, length);
        return result;
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        BenchmarkRunner.Run<ChunkBuildBenchmark>();
    }
}

 

 

Edited February 15 by zsuatem

[Tyron]

Thanks for the input! This is good stuff. We will take a closer look at this likely for 1.23. For 1.22 its a little late already. 

[hex37]

This was super cool to read through, thank you.