Daily Archives: February 15, 2022

Boring Optimizations

I think the most important change in 2.3 is that it uses a new, compressed storage format for the world files. I told you about it in one of the previous posts. It is a more complex system compared to the old one, which stored raw block values divided into constant-size chunks.

Here’s some details. The new format divides the world into regions of 16×16 chunks (where chunk is 16x16x256 blocks). Each region gets a separate file. The chunks within the region file are compressed using a two-step process:

Step 1. RLE compression to exploit the repetitive nature of the world blocks.

RLE compression stores the value of the block followed by the repeat count, instead of storing all blocks separately. The count value is stored in the “light” section of the block data, so it doesn’t take any more space than the raw, uncompressed block (light value does not have to be saved – it is generated anyway). Only if the count is too large to fit in the light section (4 bits), a separate byte is allocated for the count.

Additionally, the order of blocks storage is changed from how they are kept in memory. This is to maximize gains from the RLE scheme. Block values are more repeatable in horizontal directions than in the vertical. Deep down you get hundreds and hundreds of the same granite/basalt blocks, up in the air it’s all air, obviously.

Step 2. Standard deflate compression (the same as used by zip format) on the resulting RLE-compressed data

This does not need much explanation. Deflate has been the workhorse of compression for many decades now. There are more modern and better compression algorithms – like Zstandard, which is both faster and provides better compression. Maybe one day I will switch to using it. But Deflate is so ubiquitous and so easy to use – it is good enough for us at the moment.

The main complication with the new format is that chunks no longer have the same size – some compress more, some less. A simple fixed-size system, as used in 2.2, cannot work. Therefore, within each region file there is a mini-filesystem, which handles variable-size compressed chunks. It uses a simple overprovisioning scheme, which leaves extra 1024 bytes after each chunk to accommodate small changes. Once a chunk grows out of this extra space, the entire region file is rewritten, with the file enlarged and chunks rearranged to get their 1024 spare bytes again. The rewriting does not happen too frequently – a large change to the chunk data, such as an explosion or digging/placement of many blocks, is required to use up the 1024 bytes and trigger the rewriting.

The result is quite satisfactory. I’ve already shown you this:

2.78GB to 26MB – that’s over 100x reduction in size! But we badly needed that. The large number of crash reports I have from the game are almost always caused by the device running out of storage space. Followed by running out of memory, when someone with a low-memory phone ups the visibility range to the max…

Such changes are always risky – we don’t want world data losses. To reduce the chance of this happening, I used both automated and manual testing. For the automated testing, the world was randomly modified and camera randomly shifted in quick succession. This was left to run overnight – for many, many hours – stress testing the new format. For manual testing, me and friends played 2.3 in many different settings, with up to 4 players, for many hours in total.

As far as I can tell, it works. There are no bugs. But we’ll see once YOU start using it :-)

The new file format is not the only optimization in 2.3. Memory allocations in terrain engine have been massively reduced by use of caching. This should reduce garbage collection-related stuttering. In 2.2 and earlier, as the player was moving quickly, the chunks which were going out of visibility range behind the player were immediately freed, and memory for the new chunks was allocated afresh. In 2.3, the blocks of memory from old chunks are cached for a while to see whether the new chunks will fit in them, instead of allocating fresh memory.

Nothing too clever, but it hugely reduces pressure on the garbage collector. We had a system like that back in the old days of Alpha 1.xx around 2013, but I had to take it out, because back then memory was more precious than gold dust. The game had to run on some Apple devices with just 256MB of RAM. Fortunately, Apple has changed its ways, and the worst we can expect from them is 1GB on iPhone 6, or 512MB on iPad 2 – would you believe that scores of people still play on that ancient museum piece? That’s the sole reason I keep supporting iOS 9.x.

There’s more optimizations to do with light propagation as well. As usual, the full list of changes will be published soon on the Updates History page.

By the way, if you read all the way to here without getting bored: I released 2.3 earlier today on all platforms. Should already be in the stores, apart from Amazon, which is still in review. Amazon will probably be out tomorrow.

Have fun!