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

Closed
wants to merge 1 commit into 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 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 February 28, 2021 23:26
@ldpl
Copy link
Contributor Author

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

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.

@ldpl
Copy link
Contributor Author

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

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 pull request Mar 1, 2021
JGRennison added a commit to JGRennison/OpenTTD-patches that referenced this pull request Mar 1, 2021
@glx22
Copy link
Contributor

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 commented Mar 1, 2021

Ok I have a fix here
CI tested here

Feel free to merge in your commit.

@JGRennison
Copy link
Contributor

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

Choose a reason for hiding this comment

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

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

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

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

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?

@TrueBrain
Copy link
Member

Last information I have, is that zstd in fact did not help for savegame filesize. Is this true? In that case, are we better off closing this PR? It seems nobody took an interest in all these years?

(open question, I don't mind if the answer is: nah, let's keep it open. As long as we have a reason for doing so :) )

Tnx!

@ldpl
Copy link
Contributor Author

ldpl commented Sep 13, 2023

Well, there is a bit of a chicken-egg problem. My testing ended up being inconclusive, need to try it in real conditions, collecting stats for player connections but that can't be done without implementing it first. Maybe I'll get around to it eventually and do some A/B testing with cmclient or smth. But for now you can close this PR if you want, I can always (ask to) reopen it later.

@TrueBrain
Copy link
Member

Okay, let's close it (and the network-handshake-for-compression) PR for now, but we are always interested in making savegames smaller, so if you can find the time, it would be very welcome.

@TrueBrain TrueBrain closed this Sep 13, 2023
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