Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add: Support Zstandard(zstd) savegame compression #8773

Open
wants to merge 1 commit into
base: master
Choose a base branch
from

Conversation

ldpl
Copy link
Contributor

@ldpl ldpl commented Feb 28, 2021

Motivation / Problem

Zstd offers a blazingly fast compression/decompression while keeping a reasonable compression ratio. Making it an excellent option for a network server.

Description

For an estimated client connection time on 10 MB/s (compress + download + decompress) it is about 3x faster than lzma:2(default) and 1.5x than zlib:2 and lzo (next best choices). For some cases (e.g. 4kx4k map + no pause on join) it's basically a lifesaver. Yet I didn't make it a default compression since it produces about 25-40% large saves than lzma:2 making it a poor choice for singleplayer. Also, it's a new addition and would be bad if some unexpected issue were to appear for a default compression method.

To compare the performance I did a completely scientific benchmark in python on totally unbiased corpus of 516 savegames in my OpenTTD folder:

lib:level size(MB) compress decompress connect compress% decompress% connect%
lzo:0 2.41 0.0122 0.0164 0.2699 3.37 24.96 51.20
lzma:0 1.19 0.2577 0.0825 0.4592 71.29 125.57 87.12
lzma:2 1.00 0.3615 0.0657 0.5271 100.00 100.00 100.00
lzma:4 0.89 1.0415 0.0589 1.1898 288.11 89.65 225.73
zlib:0 15.11 0.0099 0.0106 1.5315 2.74 16.13 290.55
zlib:2 1.68 0.0874 0.0260 0.2817 24.18 39.57 53.44
zlib:4 1.48 0.1340 0.0319 0.3143 37.07 48.55 59.63
zlib:6 1.36 0.3160 0.0286 0.4802 87.41 43.53 91.10
zstd:-10 2.06 0.0114 0.0134 0.2304 3.15 20.40 43.71
zstd:-5 1.86 0.0119 0.0133 0.2110 3.29 20.24 40.03
zstd:-3 1.78 0.0124 0.0128 0.2033 3.43 19.48 38.57
zstd:-1 1.70 0.0128 0.0130 0.1963 3.54 19.79 37.24
zstd:1 1.43 0.0131 0.0134 0.1695 3.62 20.40 32.16
zstd:2 1.44 0.0182 0.0154 0.1779 5.03 23.44 33.75
zstd:3 1.42 0.0236 0.0141 0.1801 6.53 21.46 34.17
zstd:5 1.37 0.0375 0.0146 0.1892 10.37 22.22 35.89
zstd:7 1.29 0.0609 0.0129 0.2031 16.85 19.63 38.53
zstd:9 1.26 0.1002 0.0127 0.2384 27.72 19.33 45.23
zstd:11 1.26 0.1615 0.0126 0.2996 44.67 19.18 56.84
zstd:13 1.22 0.4370 0.0116 0.5705 120.89 17.66 108.23
zstd:15 1.21 0.6622 0.0106 0.7938 183.18 16.13 150.60
lz4:0 2.43 0.0128 0.0126 0.2687 3.54 19.18 50.98
lz4:3 1.86 0.0955 0.0114 0.2931 26.42 17.35 55.61
  • % columns are relative to default compression (lzma:2)
  • conect = compress + decompress + size / 10
  • miraculously average savegame size for default compression just happened to be exactly 1 MB

Interestingly lz4 doesn't seem to be of any use in the OpenTTD case.

Benchmark script: slcompressioncmp.zip

Limitations

  • It may have better performance if used with buffer sizes recommended by zstd itself but I don't see any simple way to benchmark that.
  • My performance results don't match the ones mentioned in the comments to other compression methods.
  • I've no idea wtf I'm doing with cmake.

Checklist for review

Some things are not automated, and forgotten often. This list is a reminder for the reviewers.

  • The bug fix is important enough to be backported? (label: 'backport requested')
  • This PR affects the save game format? (label 'savegame upgrade')
  • This PR affects the GS/AI API? (label 'needs review: Script API')
    • ai_changelog.hpp, gs_changelog.hpp need updating.
    • The compatibility wrappers (compat_*.nut) need updating.
  • This PR affects the NewGRF API? (label 'needs review: NewGRF')

@michicc
Copy link
Member

@michicc michicc commented Feb 28, 2021

One could imagine having different defaults for on-disk saves and for network-transfer saves.

@ldpl ldpl force-pushed the zstd-compression branch 2 times, most recently from eba9544 to 6f0aeaf Compare Feb 28, 2021
@ldpl
Copy link
Contributor Author

@ldpl ldpl commented Mar 1, 2021

Ran the benchmark for all public server (180) saves. Interestingly on this dataset zstd:9 approaches lzma:2 savegame sizes really close while still being significantly faster. zstd:1 is still the best for network though.

lib:lvl size(MB) comp decomp connect size% comp% decomp% connect%
lzo:0 3.89 0.0186 0.0216 0.4294 189.54 2.52 17.54 40.31
lzma:0 2.18 0.4395 0.1431 0.8003 106.03 59.65 116.24 75.13
lzma:2 2.05 0.7368 0.1231 1.0652 100.00 100.00 100.00 100.00
lzma:4 1.88 2.2687 0.1158 2.5729 91.70 307.92 94.12 241.53
zlib:2 2.69 0.1388 0.0372 0.4452 131.09 18.84 30.23 41.79
zlib:4 2.43 0.2132 0.0466 0.5027 118.30 28.93 37.85 47.19
zlib:6 2.27 0.5803 0.0427 0.8505 110.79 78.76 34.71 79.85
zstd:-10 3.67 0.0244 0.0190 0.4101 178.58 3.31 15.47 38.50
zstd:-1 3.00 0.0301 0.0192 0.3490 145.98 4.08 15.59 32.76
zstd:1 2.38 0.0317 0.0196 0.2893 115.97 4.30 15.89 27.16
zstd:2 2.40 0.0357 0.0209 0.2968 117.00 4.84 16.96 27.86
zstd:7 2.20 0.1671 0.0190 0.4058 107.02 22.79 15.19 38.16
zstd:8 2.18 0.2205 0.0184 0.4564 105.96 30.08 14.71 42.93
zstd:9 2.15 0.3243 0.0186 0.5580 104.78 44.01 15.12 52.39
zstd:10 2.15 0.3870 0.0193 0.6215 104.80 52.80 15.46 58.45
zstd:11 2.15 0.4638 0.0195 0.6984 104.79 62.61 15.75 65.30
zstd:12 2.13 0.6816 0.0180 0.9128 103.81 92.03 14.59 85.34
zstd:13 2.09 1.1767 0.0175 1.4028 101.61 158.87 14.14 131.16
lz4:0 4.03 0.0176 0.0142 0.4350 196.40 2.38 11.51 40.84

@JGRennison
Copy link
Contributor

@JGRennison JGRennison commented Mar 1, 2021

I was a bit confused at first looking through this as the the methods used seemed to be mismatched relative to the documentation.

For the decompresser, it seems that the method names in the documentation are: ZSTD_createDStream, ZSTD_freeDStream, ZSTD_decompressStream.
The deprecated aliases are: ZBUFF_createDCtx, ZBUFF_freeDCtx, ZBUFF_decompressContinue.
ZBUFF_DCtx is the deprecated alias of ZSTD_DStream.

Likewise for the compressor.

The code here seems to mix and match old and new names.

src/saveload/saveload.cpp Outdated Show resolved Hide resolved
src/saveload/saveload.cpp Outdated Show resolved Hide resolved
@ldpl
Copy link
Contributor Author

@ldpl ldpl commented Mar 1, 2021

@JGRennison where did you find ZSTD_createDCtx and ZSTD_freeDCtx being called deprecated?
It seems to be the same thing, yes, but if anything I'd say it's ZSTD_createDStream/ZSTD_freeDStream that were deprecated as zstd examples were switched from them to the DCtx/CCtx notation at some point:
facebook/zstd@f5cbee9#diff-2cdd2a54099975862a2024d0f2846195208874a126023526391c946c132a275b
facebook/zstd@de58910#diff-7a164944570ed22ca8cfeb57c5b2f520664b8ec14221c4d1fd413aa87cb6850c

And in general, I've been mostly following those examples as documentation itself is kinda crappy
https://github.com/facebook/zstd/blob/dev/examples/streaming_decompression.c
https://github.com/facebook/zstd/blob/dev/examples/streaming_compression.c

@JGRennison
Copy link
Contributor

@JGRennison JGRennison commented Mar 1, 2021

I think you're right and I've misunderstood it. I first looked at the documentation from here: https://facebook.github.io/zstd/zstd_manual.html, which implies that the two sets of functions do different things.
Then I found some aliases and deprecation tags in https://github.com/facebook/zstd/blob/dev/lib/deprecated/zbuff.h but looking again these are actually for a 3rd set of name variations...

This issue seems to explain it: facebook/zstd#1510
It seems a wacky way to define an API in any case.

JGRennison added a commit to JGRennison/OpenTTD-patches that referenced this issue Mar 1, 2021
JGRennison added a commit to JGRennison/OpenTTD-patches that referenced this issue Mar 1, 2021
@glx22
Copy link
Contributor

@glx22 glx22 commented Mar 1, 2021

I updated workflows in master to solve the cache issue. You'll need to rebase and increase the number at the end of key in all Enable vcpkg cache steps.

I still need to find why CMake doesn't find zstd on windows (and it's probably also related to macos failure)

@glx22
Copy link
Contributor

@glx22 glx22 commented Mar 1, 2021

Ok I have a fix here
CI tested here

Feel free to merge in your commit.

@JGRennison
Copy link
Contributor

@JGRennison JGRennison commented Mar 3, 2021

Cmake should probably be set to only accept version 1.4 or later, as compilation fails on some of the CI release targets, which have 1.3.x versions.
e.g. JGRennison/OpenTTD-patches@64dd3c2

Copy link
Member

@TrueBrain TrueBrain left a comment

Given this requires zstd 1.4+, that would mean that accepting this PR would also effectively remove Ubuntu 18.04 and Debian Buster release targets (and I think that should even be part of this PR, in a different commit). As of course it would be rather silly if we distribute binaries where it is not possible to join a multiplayer server with :D
To be clear, I have no opinion about this, I am merely stating what it would effectively mean :)

{"zstd", TO_BE32X('OTTS'), CreateLoadFilter<ZSTDLoadFilter>, CreateSaveFilter<ZSTDSaveFilter>, 0, 101, 122},
#else
{"zstd", TO_BE32X('OTTS'), nullptr, nullptr, 0, 0, 0},
#endif
Copy link
Member

@TrueBrain TrueBrain Mar 3, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If I remember correctly, putting it here doesn't make it a default for anyone. Would it be wise to add code that depending on network-save / local-save it picks zstd? As just adding it for the sake of adding it feels a bit mute to me. Opinions? Ideas?

Copy link
Contributor Author

@ldpl ldpl Mar 3, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Well, my idea was to just add it first and decide what to do with it later (1.12?) so there is enough time for it to be tested by those who wish to.

Copy link
Member

@TrueBrain TrueBrain Mar 3, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Personally not a big fan of using upstream for this, but that is just my take in this :) Mainly because I also think that adding it isn't a lot of work, and would benefit many people :) (in the end, we know it is faster for sure, and sizes on network games do not matter that much after all). But again, just my take on it, curious if others agree/disagree :)

* a good choice for multiplayer servers. And zstd level 1 seems to be the optimal one for client connection speed
* (compress + 10 MB/s download + decompress time), about 3x faster than lzma:2 and 1.5x than zlib:2 and lzo.
* As zstd has negative compression levels the values were increased by 100 moving zstd level range -100..22 into
* openttd 0..122. Also note that value 100 mathes zstd level 0 which is a special value for default level 3 (openttd 103) */
Copy link
Member

@TrueBrain TrueBrain Mar 3, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This might be very unclear to people that use the config file setting for this. How are we going to make sure it is clear to them that this is happening?
I wonder if we wouldn't be better off making the parameter for compression level signed instead. That avoids this hack, and makes the configuration a bit more understandable for the average user?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

5 participants