terrelln

I've implemented counters exactly like this. I actually migrated away from the tls_counter to something like the cas_multi_counter.

The problem with the tls_counter is memory usage that scales with the number of threads. In this example you need 16 bytes per thread because only one counter is supported, I believe we ended up with 48 bytes per thread. So with 10,000 threads you can end up with >=160KB of data for every counter. And 10,000 threads isn't that far-fetched if most are sleeping (though not ideal). Then you end up with 10,000 counters and you're spending >= 1.6 GB of RAM on counters. Where the cas_multi_counter would only be using 40.96 MB. And read() scales with the number of threads, so can get pretty slow, but that is secondary.

One optimization you can use to make the cas_multi_counter more memory efficient is to share the backing memory. You have 4096 bytes, but are only using the first 8 bytes of each 64-byte stripe. You can multiplex 8 counters into the same 4096 byte storage. The first counter gets offset 0, the second offset 8, and so on. This only adds 1 indirection in the hot operator++() path, and doesn't add any extra false sharing as long as the 4096 byte buffer is 64-byte aligned. Construction and destruction is more expensive, but not terribly so, and that is probably cold anyway. Now you're at 512 bytes per counter, and the size is independent of the cache-line size. If you can count the number of active CPUs you can dynamically size your buffer to only have # CPUs cachelines, further saving memory.

Convince means the verifier can prove to itself what the provers are telling it in polynomial time, without trusting the provers.

Zstd by default will write sparse files when it detects runs of zeros during decompression, but isn't aware of it when reading a file.

Zstd has a 32-bit checksum over the uncompressed data, which is enabled by default on the CLI.

This is an important trick for LZ4's speed. But, there is a bit more to it than this. Some important tricks are:

* LZ4 can represent a literal length of 14, and a match length of 18 in a single byte [0]. Most LZ4 sequences will have a literal length LL <= 14, and most LZ4 sequences will have a match length ML <= 18. Instead of copying LL and ML bytes, we can copy 14 bytes and 18 bytes. Then only if LL > 14 we copy extra bytes, and same for ML > 18.

* The case of overlapping matches (e.g. offset = 1, and ML = 100) needs to be handled specially, otherwise you will run into store forwarding problems.

* Always copy 16 or 32 bytes at a time and allow overwrites. Allowing overcopies simplifies the copy routine, improves branch prediction, and reduces store forwarding issues, at the expense of ensuring you always have enough slack at the end of your buffers.

[0] https://github.com/lz4/lz4/blob/dev/doc/lz4_Block_format.md

Slightly off topic, but one great way to diff is to compress the new file using the old file as a dictionary. Both zlib and zstd support this (but zlib is limited to a 32KB file).

You can tune how much CPU you want to spend getting a better diff by adjusting the compression ratio, the compressor is well tuned for speed and is generally more efficient than a diffing algorithm, it can find repetitions in the new content, and you get entropy coding.

Zstd also has a multithreaded mode. On the CLI `zstd -T0` tells zstd to use all available cores.

Zstd's dictionaries contain two things:

1. Predefined statistics based on the training data for literals (bytes we couldn't find matches for), literal lengths, match lengths, and offset codes. These allow us to use tuned statistics without the cost of putting the tables in the headers, which saves us 100-200 bytes. 2. Content. Unstructured excerpts from the training data that are very common. This gets "prefixed" the the data before compression and decompression, to seed the compressor with some common history.

Dictionaries are very powerful tools for small data, but they stop being effective once you get to 100KB or more.

In this competition, and in similar competitions, the size of the binary used to decompress is taken into account. If you wanted to use a dictionary, you would need to pay for it in binary size. In this competition, the file must be self-decompressing.

Dictionaries are powerful tools when compressing small data. But once the data is large enough they stop mattering so much. See the dictionary compression section of https://engineering.fb.com/core-data/zstandard/.

Brotli is great at compressing static web content, zstd without a dictionary is unlikely to outperform it. For static content you'd probably rather save 5% of space over some decompression costs, since Brotli decompression is fast enough.

Zstd has an advantage if you don't have the CPU to compress at the maximum level, since zstd is generally faster than Brotli at the lower levels.

Even still, for web compression, Brotli has the advantage of already being present in the browsers, so you're betting off using Brotli for web compression as it stands today.

lz4 compresses and decompresses faster than snappy, and compresses similarly. You can see some comparisons on the GitHub's readme https://github.com/lz4/lz4.

There aren't any technical limitations to adding multithreaded decompression zstd. We just need a compelling enough use case to justify the work it would take to add it.

pzstd is now obsoleted by zstd -T0, but it offers multithreaded decompression for files compressed by pzstd (it will still be single threaded for files compressed by zstd).

A comparable zstd call that uses a 64 MB window size and all cores is:

    zstd --long=26 -T0

From there you can tune the compression level, or increase the window size up to 2 GB (--long=31). zstd won't beat the compression of xz, but it can compress much faster if you trade off some space.

Starting with zstd-1.3.8 we support the `ZSTD_CLEVEL` environment variable. We've started with a small scope for the variable, because we don't want users to unexpectedly remove the source fie, for instance.

If you want to pass extra options, you can pipe the output to zstd, which is exactly what tar is doing internally.

tar-1.3.1 added support for zstd with the option `--zstd` and `-a`, the auto-decompression flag, also supports zstd. Older tar versions also have the `-I` flag which you can use to (de)compress with zstd.

We're working to improve zstd support in the ecosystem over time, but this work moves slowly, and it takes a long time for upstream work to make it to users systems, especially LTS systems.

The next GRUB release (grub-2.04) includes my patch to add support for zstd compressed BtrFS filesystems, which should solve one of the major pain points of Zstd BtrFS compression.

Disclaimer: I'm a maintainer of zstd, so I'm biased.

Brotli dominates HTTP compression. Zstd just got its RFC approved a few months ago, but Brotli has been present in browsers for years.

However, zstd is more widely adopted everywhere else, especially in lower level systems. Zstd is present in compressed file systems (BtrFS, SquashFS, and ZFS), Mercurial, databases, caches, tar, libarchive, package managers (rpm and soon pacman). There is a pretty complete list here https://facebook.github.io/zstd/.

Again, I'm biased because I know almost everywhere where zstd is deployed, but not everywhere that Brotli is.

The images are high res, but you have to download them to view the larger image.

I believe that this is just the initial release for testing, and the author plans to clean up the header file to separate out the interface from the implementation, and add documentation.

I believe you are looking at XXH64 and XXH32, which is the old version. The new version XXH3 is located in https://github.com/Cyan4973/xxHash/blob/dev/xxh3.h which exposes the public prototypes `XXH3_64bits()` and `XXH3_128bits()` (and variants with seeds).

I've tested XXH3 using xxhash's built-in benchmark tool with clang-7.0.1 and gcc-8.2.1 on an Intel i9-9900K. The processor was otherwise idle, and was running at 5 GHz. The command I tested is `xxhsum -b5i10`.

    SSE2: CFLAGS=-O3
    AVX2: CFLAGS="-O3 -mavx2"
    ARCH: CFLAGS="-O3 -march=native"

    Compiler  Mode  Speed
    gcc-8     SSE2  32.8 GB/s
    clang-7   SSE2  36.5 GB/s 
    gcc-8     AVX2  44.1 GB/s
    clang-7   AVX2  68.3 GB/s
    gcc-8     ARCH  60.9 GB/s
    clang-7   ARCH  69.7 GB/s

gcc nearly catches up with clang when compiled with -march=native, but with only -mavx2 it isn't performing as well.

That site claims 0.99 BPC, which I guess means the compressed size is 10^8 * 0.99 / 8 ~= 12,375,000.

Does that include the size of the model, or is this just the cost to encode the errors?

I definitely agree that parallelism isn’t held back by fundamentally serial work. Even with LZ decompression, most algorithms entropy encode the LZ sequences, and these sequences can be decoded in parallel with the LZ decoder.

I've generally found that thread-local storage is easily misused. My general rule of thumb is to avoid thread-locals wherever possible, but if they are required keep thread-local state constant sized, not one per object. The memory usage can grow rapidly when your library is used with many objects and many threads. In places where you would want one thread-local per object, instead try core-locals.

A lot of compression ends up being compress once, decompress one to a few times, so the faster end of the spectrum fits well. Additionally, compression has to fit into the existing system, and existing systems already have tight constraints, so it is an easier sell to say "hey, we can compress faster AND stronger" than what you have right now. For our larger services, we will tune the compression level more carefully, and end up at different places for different services, but still normally around the faster levels.

That said, we still see users of the stronger compression levels.

Looking at the brotli API, I believe I spotted the source of our disagreements. Brotli separates out the window size from the quality, but in zstd the level implies the window size, unless you use advanced parameters. For example, level 3 has a 1 MB window size.

When you are comparing brotli and zstd, are you focusing on the highest quality/compression level, but varying the window size?

For us, lower compression levels (1-3) are our primary focus. We care about the highest levels for benchmarks, but it isn't our focus. When we are benchmarking zstd we focus on the lower levels, since they are the most important to us. When we think about a smaller window size, we generally think about faster compression.

When we comparing against brotli, the question we're asking is, how does brotli compare to level 3. When you're benchmarking zstd, I suspect you're asking the question, how does the highest zstd level compare to the highest brotli quality for the same window size, is that right?

Levels above 19, which has a 8 MB window size, may only be used with the --ultra flag, whose documentation says "requires more memory".

We recently added negative compression levels that extends the fast end of the spectrum significantly. We are also working on incrementally improving the strong end of the compression ratio spectrum. We don't expect plain zstd to compress stronger than xz, but we hope to close the gap some.

There are a few reasons we haven't used the wrapper.

* The larger services require tuning to get the best performance out of zstd, and we use some advanced options.

* We have a "Managed Compression" library which does zstd dictionary compression, which doesn't work with the wrapper.

* We have our own automatic decompression framework that handles many algorithms [0].

* A lot of use cases switched over from other algorithms than zlib.

* A lot of use cases switched over to zstd organically, without our involvement, since it was such a clear win.

[0] https://github.com/facebook/folly/blob/master/folly/compress...

Porting is generally very easy.

* If you already have the compression algorithm tagged, through a file extension, or a field, then you can use that to dispatch to the right decompression algorithm.

* Zlib, gzip, xz, zstd, ... all have headers. If you are using zlib, and switching to zstd, you simply have to check the first 4 bytes for the zstd header using ZSTD_isFrame() [0], or attempting to decompress with zstd and if it fails fall back to the previous decompression algorithm.

* The zstd CLI can decompress both zstd and zlib/gzip if compiled with zlib support.

* Zstd provides a wrapper around the zlib API so you could transparently switch to zstd. [1]

[0] https://github.com/facebook/zstd/blob/dev/lib/zstd.h#L1409 [1] https://github.com/facebook/zstd/tree/dev/zlibWrapper