-
Notifications
You must be signed in to change notification settings - Fork 2k
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
Using Zstandard for mapblock compression? #4495
Comments
Thumbs up for replacing zlib ! Speed tests I did for minetestmapper a while ago showed that about 50% (IIRC) of the running time was actually spent in zlib code, decompressing map data... As the comparison table on the zstd page shows about 25% worse compression for lz4, but with the benefit of a 2-3 times speed increase, I'd welcome an implementation that allows different compression algorithms to be used, so that depending on CPU speed, disk speed and disk size, a server operator can choose for faster or for more compact compression. The actual algorithm that was used should obviously be encoded in a block's data. At the same time, instead of only compressing the node data, all of the block's data could be compressed. IIRC, one important reason LevelDB databases are often smaller, is that LevelDB uses snappy to compress all data it stores. |
The compression ratio is not much better compared to zlib but for the same ratio it is able to process much more data, that's very nice. I am not sure about the compatibility with our supported OS' but it looks well maintained there. |
I'm suspicious of zstandard's licensing at first, their example code isn't even licensed properly, so you can't even use their example code freely. I would wait and see in a year or so if this is actually taking off anywhere.... |
If we're going the new shiny stuff™ route, we should also consider https://github.com/google/brotli. |
For the Germans amongst us, here's a relevant blog post: https://blog.fefe.de/?ts=a90c6783 |
Here's a testing branch with brotli support: https://github.com/sfan5/minetest/tree/brotli Do not use this branch with your existing worlds, they will become unreadable to a "normal" Minetest. |
Nice work, @sfan5 ! I would prefer zstd over brotli, as it seems to be better, unless its proven to perform worse for our use case. One problem for both brotli and zstd will be however that we'd have to discontinue support for older distros (like ubuntu 12.04, the one @PilzAdam uses) which don't have the library. Both brotli and zstd only first appear in ubuntu 16.04. Its the same issue as for C++11, all over again :( Although one could argue that its much much easier to install or download + compile a new library than installing a totally new C++ compiler. |
Actually _lib_brotli isn't in any package repositories right now afaik, brotli doesn't have an official API (yet). zstd does so we wouldn't have that problem. However, if we intend to support ubuntu 12.04 out of the box then we need to bundle brotli/zstd anyway and this won't matter. |
i prefer lz4 than zlib, it's very fast and i already have a working version in my own version :). lz4 is cpu free |
Bundling might be an idea, yeah. I hate the concept but if we want brotli/zstd any time soon we might be forced to. |
We already bundle jsoncpp, lua, gmp and maybe other things too. |
lz4 bundling is easy, 3 files. |
Edit: see here Here's the steps I took to compare:
|
World size is not very important , but performance |
@nerzhul Which means that while performance should be about the same while the world is smaller. |
@sfan5 is it possible for you to check the duration for the decompression too? I suspect there's a lot more decompression than compression going on. The numbers in lz4 benchmarks look very attractive, though. |
We have to compare those against lz4 now. |
@sfan5 noted. I think you should benchmark various mapblock serialization times |
I've ran the test by @sfan5 for my zstd branch. (not the most recent commit, but the commit called "unittest"). I got in fact an increase in space required (944148 K with the zlib compression, and 1062140 K with the zstd compression, an increase by 12%). Note that I didn't use a dictionary, while brotli has a hardcoded dictionary, and for the minetest use case a dictionary would be really useful I think, as it perfectly matches the dictionary use case (few KB of data). So there is certainly room for improvement. The decompression time however is really really great. For zstd:
For zlib:
A bit odd was that when I rewrote the code to use the streaming API, it suddenly got horribly slow (20x decrease). The benchmarks are from using the non streaming API. |
Brotli supports dictionaries too, I agree that we should try that approach. We might need/want different dicts for block data vs. metadata too. The problem however is that every application that wants to read the Minetest's data needs the same dictionary and we can't ever change the dict. Unless we add dictionary versioning which would also require that applications keep up with dict updates done in Minetest.
The numbers from using the non-streaming API don't matter, to compare we need the benchmark while using the final design (streaming API). |
So I did all of the benchmarks again with some improvements I made to the statistics it outputs: map.sqlite zlib:
Decompression benchmark:
|
I wonder how faster unpacking will affect stuttering ingame. |
Yes, only the final design should matter, which is the streaming API one way or another. However, the non streaming API shouldn't be slower that much, meaning that there is either a bug in zstd, or in the code to use it. So the only numbers matter when/if that bug has been removed. |
The slowness with using the streaming API might be caused by the need to call
No, currently the only way to compare zlib and whatever else in a fair way is not to fix the bug. |
@est31: I did some more investigation using perf and strace, and it turns out the One would have thought Anyway, this can be fixed (workaround-style: the real problem is obviously with malloc and/or zstd) by using Comparison graphs for zstd (original code, initial patch, and final code): New compression graphs (including a few more zstd levels): It can be seen that in spite of the significant additional compression effort at higher levels, much further reduction is not achieved. The reason is most probably that even at lower levels, much of the data is already compressed from 16KB down to an amount ranging from 20 to at most a few 100 bytes. There simply isn't much more redundancy to squeeze out. |
Why was this just closed? |
Note that you should also take a look at #3946 if this is implemented. You might be able to get better performance by compressing the whole mapblock instead of compressing several sections separately and there are a number of other improvements to be made if you're going to break the serialization format. |
Zstd support (comp and decomp) included in newest linux 4.14 for Btrfs https://lkml.org/lkml/2017/6/29/816 (and for squashfs according to phoronix).
License was changed 29 days ago. Zstd readme now says "Zstandard is dual-licensed under BSD and GPLv2."
I think if you want to introduce new compression algo, do it now for 0.5.0. IMO I would prefer speed over disk space, speed advantage that lz4, zstd, etc give is huuuge compared to slightly bigger database size. |
zstd will be supported for ZFS and LZ4 was choosen too |
Linux Kernel people say LZO is the fastest. |
So, what do we select? I think it's good to start voting. |
On my server, the OS provides AVX512 accelerated zlib libraries, so I strongly prefer to stay on zlib. There are also negative implications: Alternative compression algorithms are NOT backwards compatible with old releases and should be non-default to begin with. Maps will break and it may be impossible to make downloadable player maps that are widely supported by older clients. All the talk about "oh the kernel has FOO support" is nonsense because that support IS NOT EXPORTED TO USER SPACE. It won't do minetest any good that your kernel has zstd. Minetest can't use it. You will need to rely on a completely different implementation for user space, and that will probably lack things like decent parallelism and AVX512 acceleration, and therefore lag in performance compared to ... zlib. |
🤔 🤔 🤔 https://blog.cloudflare.com/on-the-dangers-of-intels-frequency-scaling/
Old maps are going to be readable by new Minetest versions as usual.
It's certainly possible to write a tool that deserializes maps in and serializes them again in a format understood e.g. by 0.4.16, this could also be integrated into Minetest itself (similar to
Since we're mostly compressing 12k bytes at once I doubt threading has much effect (if it is used at all). |
And it's pure Intel, arm and AMD cpu doesn't benefit from that.No need to convert the whole map, just add format version to 1 for legacy mapblocks and write new mapblocks using zstd when written or loaded
|
Many Intel optimizations also benefit AMD. Check out the various performance tests that phoronix has run on AMD's threadripper platform where they compare ClearLinux against non-specifically Intel optimized distros - you can decide for yourself based on the data whether "pure intel" (a complete misnomer) is such a bad thing for the competition. Article link because you're lazy: https://www.phoronix.com/scan.php?page=article&item=tr1950x-7900x-3os&num=2 |
I stay on using zlib. It is stable and many processors has optimizations for it. |
What optimizations exactly? And zstd is faster than zlib in any case, as seen from countless benchmarks. |
no processor has optimization for a such algorithm, zlib and zstd has optimisations for processors. |
Zstd is faster and equal in size or better than gzip, and in my work projects we are actively implementing zstd compression.
So yes, it would have my support.
|
It also has multithreading support built in which speeds up compression even more at absolutely no loss of compression ratio from my tests at least. |
It also has multithreading support built in which speeds up compression
Minetest should already multithread mapblocks saves, but this isn't as much of a factor of importance IMHO
even more at absolutely no loss of compression ratio from my tests at
least.
As I already stated. The biggest point is that it's faster to compress to the same size (and decompress too)
|
I took the liberty of documenting my #engine post from the Discord server so it isn't lost in an endless stream of comments. Zstandard can perform significantly better than almost any other option with training. This YouTube video by Stanford Research Talks highlights a number of gains by using an unmutable, locked and always memory-loaded custom dictionary for referencing small and large data. They claim that the compression ratio can be improved by 3.5x to 10x, the compression speed by 3.6x over baseline, and decompression speed by 5.4x over baseline when using these features. Alternative compression/decompression algorithms can be discovered by keeping up-to-date on encode.su, the Hutter Challenge groups and Matthew Mahoney's ranking page, and on the GDCC (ru). Many algorithms based off of L-STM, Transformer/Few-shot learning, and Attention Matrices may work better in the future when these are more stable and developed. See also similar closed issue #3946, where JPEG XL is suggested for 3D mapblock data compression. JPEG XL is a standard which incorporated some of Alexander Rhatushnyak's algorithms, which he still hold the best overall ratio-to-performance ranking of any contestant in the Hutter Competition. Generally, whether it is cryptanalysis, compression, or social prediction models, adding dimensions and ways for the solver to look at the problem can significantly improve performance. On heavy servers, such a system may begin to learn and differentiate between player-built architectural designs, and how player interact and cause modifications. It may enhance cheat detection and prevention, and trivialize some lag sources which has previously appeared chaotic and random. The custom dictionary may function better if it is per-biome, or we can fiddle around with it to see what works best. Can anyone explain to me how I would start figuring that out? I'm still a noob when it comes to coding. |
Done in #10788 |
Glad it was done! Thanks! |
https://github.com/facebook/zstd
We could train zstd for minetest, or use multiple dictionaries per map.
The text was updated successfully, but these errors were encountered: