Use ZSTD for savegame compression (much faster, smaller)

Post your ideas and suggestions how to improve the game.
Post Reply
User avatar
hansinator
Fast Inserter
Fast Inserter
Posts: 160
Joined: Sat Sep 10, 2016 10:42 pm
Contact:

Use ZSTD for savegame compression (much faster, smaller)

Post by hansinator » Thu Oct 13, 2016 6:53 pm

Hi,

I've got a map that produces a 58mb zip file savegame. It takes around 5 seconds to do this and autosave becomes quite annoying. It looks like you are using deflate already with the fastest setting for compression. Letting deflate run on the raw data with its fastest settings gives me a compression time of 4 seconds.
I've got a hexa-core broadwell-e overclocked to 4,2GHz and NVMe SSDs so the bottleneck is most likely not the CPU+disk and not the game's save routines but the compression.

I suggest you use Zstd instead (http://facebook.github.io/zstd/). It compresses the same data in 1 second while producing a 53mb file (using level 3, 1 is lowest and even faster). Zstd is in most aspects superior to deflate. I've tested a couple of large savegames all with consistent results. This would reduce the time it takes to produce a savegame roughly by factor 4.

I suppose you are not able to snapshot the game state in-memory and let the game continue while the snapshot is compressed and written out to disk on a separate thread?

User avatar
ssilk
Global Moderator
Global Moderator
Posts: 10462
Joined: Tue Apr 16, 2013 10:35 pm
Contact:

Re: Use ZSTD for savegame compression (much faster, smaller)

Post by ssilk » Fri Oct 14, 2016 1:20 am

Hm. Not against this. But I need to give you the discussion from that time.
I think I remember the arguments:
1. Zip is standard. Zip-Standard (ZSTD) is not!
2. Faster plays no role: The unpacking is done by the second CPU in parallel. The serialization/deserialisation is the problem (memory-speed!).
3. Less size of files. Always good. But i it worth the adfford?
Cool suggestion: Eatable MOUSE-pointers.
Have you used the Advanced Search today?
Need help, question? FAQ - Wiki - Forum help
I still like small signatures...

Rseding91
Factorio Staff
Factorio Staff
Posts: 9216
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Use ZSTD for savegame compression (much faster, smaller)

Post by Rseding91 » Fri Oct 14, 2016 5:34 am

hansinator wrote:I suppose you are not able to snapshot the game state in-memory and let the game continue while the snapshot is compressed and written out to disk on a separate thread?
Currently the game state is copied out in one thread while another thread does the compression and writing to disk. 5 seconds for a 50 MB save file sounds like it's waiting on your computer. When I implemented the threaded compression during saving for 0.13.0 I was testing with a 65 MB save file and it would save in 3.2 seconds. Of that 3.2 seconds 2.5~ worth was copying the memory around and the remaining 0.7~ was spent compressing and writing to disk.

So, compression is not near as much time as you'd think.
If you want to get ahold of me I'm almost always on Discord.

Supercheese
Filter Inserter
Filter Inserter
Posts: 834
Joined: Mon Sep 14, 2015 7:40 am
Contact:

Re: Use ZSTD for savegame compression (much faster, smaller)

Post by Supercheese » Fri Oct 14, 2016 6:02 am

Rseding91 wrote:So, compression is not near as much time as you'd think.
Perhaps the compression ratio could then be improved, since performance is already quite nice.

Rseding91
Factorio Staff
Factorio Staff
Posts: 9216
Joined: Wed Jun 11, 2014 5:23 am
Contact:

Re: Use ZSTD for savegame compression (much faster, smaller)

Post by Rseding91 » Fri Oct 14, 2016 6:32 am

Supercheese wrote:
Rseding91 wrote:So, compression is not near as much time as you'd think.
Perhaps the compression ratio could then be improved, since performance is already quite nice.
Increasing the compression increases the time spent so it does have an impact. It's just the percentage spent compressing right now is quite small compared to the total time spent.
If you want to get ahold of me I'm almost always on Discord.

User avatar
hansinator
Fast Inserter
Fast Inserter
Posts: 160
Joined: Sat Sep 10, 2016 10:42 pm
Contact:

Re: Use ZSTD for savegame compression (much faster, smaller)

Post by hansinator » Fri Oct 14, 2016 9:51 am

Rseding91 wrote: Currently the game state is copied out in one thread while another thread does the compression and writing to disk. 5 seconds for a 50 MB save file sounds like it's waiting on your computer. When I implemented the threaded compression during saving for 0.13.0 I was testing with a 65 MB save file and it would save in 3.2 seconds. Of that 3.2 seconds 2.5~ worth was copying the memory around and the remaining 0.7~ was spent compressing and writing to disk.

So, compression is not near as much time as you'd think.
I am pretty sure it is not waiting for my computer.. I made sure my CPUs+disk are not busy and the system itself is just one of the fastest you can get for a desktop PC right now so it should be on par with your results or faster, unless you got an even faster system which is unlikely.

How did you measure the time that was spent on compression?
Did you try uncompress a save file to a ramdisk and then just compress it using a zlib based cmdline utilty and measure the time?
That's what I did and it repeatedly takes about 4 seconds (a little less) using the fastest deflate setting. The uncompressed size of my test data is 122MB.
Either there must be something else to it or one of us obtained bogus results.

It's really not hard to implement zstd, you're done in less than an hour. Then you would know if it improves the concrete situation when saving a game.
I don't really see an argument against it.

User avatar
hansinator
Fast Inserter
Fast Inserter
Posts: 160
Joined: Sat Sep 10, 2016 10:42 pm
Contact:

Re: Use ZSTD for savegame compression (much faster, smaller)

Post by hansinator » Fri Oct 14, 2016 10:07 am

ssilk wrote:Hm. Not against this. But I need to give you the discussion from that time.
I think I remember the arguments:
1. Zip is standard. Zip-Standard (ZSTD) is not!
2. Faster plays no role: The unpacking is done by the second CPU in parallel. The serialization/deserialisation is the problem (memory-speed!).
3. Less size of files. Always good. But i it worth the adfford?
1. Zip is a de-facto standard, not a standard
1.1 Zip is a file format, not a compression algorithm, the algorithm is called deflate and it merely has an RFC
2. I have got quad channel DDR4 memory with a peak bandwidth of 45GByte/s. I benchmarked the memory speed so its no theoretical value. It can't be the memory speed.
3. It is basically no effort to integrate Zstd. It supports single-call interfaces as well as a zlib-style API for drop-in replacement. I strongly believe it already took more effort discussing it here.

It even doesn't matter if Zstd is a standard or not - why should it? The compression format is stable right now so it probably won't change a lot in the future. And even if it does it is no problem, because Factorio savegames only need to be read by Factorio and the devs have full control over which library version they use.
Last edited by hansinator on Fri Oct 14, 2016 10:36 am, edited 1 time in total.

User avatar
hansinator
Fast Inserter
Fast Inserter
Posts: 160
Joined: Sat Sep 10, 2016 10:42 pm
Contact:

Re: Use ZSTD for savegame compression (much faster, smaller)

Post by hansinator » Fri Oct 14, 2016 10:26 am

I've run some additional benchmarks.
My disk can read with 2.8GByte/s and write with ~880MByte/s.
Deflate (zlib) achieves around 90MByte/s from RAM to disk when compressing a 1GB file (source code). It reaches only 55MByte/s when I compress ~600MB of raw Factorio savegame data.
Zstd reaches 220Mbyte/s.

My results for deflate throughput are consistent with this paper from Google employees: https://cran.r-project.org/web/packages ... -09-22.pdf
My results for Zstd (and deflate, too) are somewhat consistent with the "official" benchmarks by Zstd. The used lzbench and only did in-memory compression.

@rseding
If you say you had a 65MB save let's assume it is at least 100MB uncompressed. With roughly 90MB/s we get a theoretical compression time of 1.1 seconds.
You said you have measured 0.7 seconds. Either you have a special hand-tweaked deflate algorithm that is faster than what everybody else is using or your measurement method is flawed or there is something special with Factorio data that makes it speedier to compress. The latter case is unlikely, because my results show less than ideal throughput on Factorio data. The numbers contradict yours.

With Zstd you can still cut the time by a factor of approx 3.5. That would mean instead of 1s compression time we get 280ms _and_ smaller files!
Last edited by hansinator on Fri Oct 14, 2016 1:26 pm, edited 3 times in total.

User avatar
hansinator
Fast Inserter
Fast Inserter
Posts: 160
Joined: Sat Sep 10, 2016 10:42 pm
Contact:

Re: Use ZSTD for savegame compression (much faster, smaller)

Post by hansinator » Fri Oct 14, 2016 10:48 am

Going through the debug symbols it shows you are indeed using Zlib. As I said, Zstd has a Zlib-style API for drop-in replacement. It'll take you a couple of minutes to try using that, including download and compilation. No effort.

Edit:
I've used the undecorator mod to remove all decorations from my largest savegame. It the size reduced approximately in half from currently 58MB to 26MB. The time needed to save the game reduced from roughly 5 seconds to ~1 second. Thats odd, right? One might suspect that serialization is the slowest component.. but I can confirm an increase in compression throughput on undecorated savegames.

I've used several decoration-stripped savegames and made a folder with 60MB of uncompressed save data. The compression speed on this data increases and I can measure about 1.1 seconds from ramdisk to disk using a command line utility.

It seems to me that savegames with a lot of decorations make deflate have less throughput. Could it be that you have benchmarked the speeds with a version that produces less decorated savegames?

User avatar
ssilk
Global Moderator
Global Moderator
Posts: 10462
Joined: Tue Apr 16, 2013 10:35 pm
Contact:

Re: Use ZSTD for savegame compression (much faster, smaller)

Post by ssilk » Fri Oct 14, 2016 8:16 pm

I added this thread to
viewtopic.php?f=80&t=21367 Game Save File ans -Speed Related Suggestions

Please avoid double (triple) postings. :) No good style. ;)
hansinator wrote:One might suspect that serialization is the slowest component. but I can confirm an increase in compression throughput on undecorated savegames.
That lets room for interpretatoin. IMHO: The serialization is much slower than the compression. :)

Without the tools to measure this correctly, it is a dig in the mud. ;)

And I'm sure you know much about compression etc. But to improve save-speed (load-speed), it is needed, that you find the smallest bottleneck, and this (and other) discussion came to the conclusion, that that isn't compression.
Cool suggestion: Eatable MOUSE-pointers.
Have you used the Advanced Search today?
Need help, question? FAQ - Wiki - Forum help
I still like small signatures...

Post Reply

Return to “Ideas and Suggestions”

Who is online

Users browsing this forum: Google [Bot]