Hacker News Reader

terrellnon Appending to an std:string character-by-character: how does the capacity grow?

folly provides functions to resize std::string & std::vector without initialization [0].

[0] https://github.com/facebook/folly/blob/3c8829785e3ce86cb821c...

terrellnon Honey, I shrunk the NPM package

That said, this is an interesting article, and I love to see people experimenting with modern compression algorithms for package management! There are a lot of easy wins in this space.

terrellnon Honey, I shrunk the NPM package

In parts (1) and (2) comparing the default setting of Zstd (level 3) against the default setting of Brotli (level 11) is a bit misleading. It shows Brotli compressing ~30% better than Zstd, but Brotli's default level is >100x slower than Zstd's default level. Zstd level 3 is expected to run at hundreds of MB/s, and Brotli level 11 is expected to run at ~2 MB/s. The compression speed is only 30% slower because that benchmark includes the time to tar the directory, which is likely more expensive than the compression itself. As @sfink already suggested, just running lzbench on the npm-9.7.1.tar would be a better benchmark.

In part (3), because its running only on lib/npm.js which is 13KB, you are getting skewed results which aren't directly applicable to the compression of npm-9.7.1.tar. Brotli excels at compressing small Javascript files, as this is where its dictionary provides the most benefit. The benefits of the dictionary for a large tar file will be negligible.

However, in the npm-9.7.1.tar scenario we still expect Brotli level 11 to produce slightly smaller files than Zstd level 19. Likely ~5% smaller. But we do expect Zstd to provide significantly faster decompression speed.

terrellnon Intel QuickAssist Technology Zstandard Plugin for Zstandard

Yeah, that is definitely a limitation with QAT. It isn't a great fit for larger data, as it can quickly lose compression ratio due to its smaller window. However, there is a lot of compression done on data that is <64KB. E.g. compression in RocksDB.

We also have some half baked ideas to combine a fast SW match finder that only looks for matches >64KB away, and supplements the matches that QAT finds.

terrellnon “csinc”, the AArch64 instruction you didn’t know you wanted

Awesome post, TIL about that instruction. I just found myself wanting a `csinc` instruction when optimizing a function to merge sorted lists.

Looking forward to your future posts!

terrellnon Fibonacci Hashing: An optimization that the world forgot (2018)

This style of hash function is used by zstd, lz4, and many other LZ algorithms in their hash tables as a fast hash with good enough quality

terrellnon When Debug Symbols Get Large

I've seen a multi MB symbol coming from generated code

terrellnon Bit twiddling with Arm Neon: beating SSE movemasks, counting bits and more

Awesome work! We were very happy to receive the patches to zstd to optimize ARM performance!

terrellnon Lz_xor

This is very interesting!

I've tried something somewhat similar in the past. I was looking at implementing an extremely fast decompressor, with ratio similar to LZ4. I was able to get 2x the decompression speed of LZ4, but struggled with compression ratio. The idea was to have 16 byte matches, and allow the matches to apply a 16-bit mask, telling whether each byte is part of the match or a literal. Then I restricted the compressor to only be able to use 16 distinct masks.

This was extremely fast to decompress, because each 16-byte match is: load the 16-byte match into an AVX2 register, load 16 bytes of literals, load the mask you're using, shuffle the literals, then blend the literals and the match. And because the matches are fixed size, you can start the fetch for multiple matches in parallel.

However, the problem I ran into, and would love to solve, is that I also wanted fast-ish compression speed. And it is very hard to search for good matches quickly. Since you have holes in the match.

I guess the author is looking at GPU compression, so they are taking a somewhat brute-force approach. But I'd be interested to see how they're doing the match finding, and what kind of speed they're getting.

terrellnon Parallelising Huffman decoding and x86 disassembly by synchronising prefix codes

https://github.com/weissenberger/gpuhd

The authors of this repo/paper use the self-synchronizing property of almost all Huffman codes to implement parallel Huffman decoding on the GPU at ~10 GB/s. In practice, I haven't found this to be useful to do Huffman decoding on the CPU, since the GPU round-trip outweighs the speed of the GPU. But if your data is already on the GPU, this is a really cool way to to Huffman decoding.

terrellnon Branch/Cmove and Compiler Optimizations

It can still matter. You can have a common function that is inlined everywhere that takes a ton of CPU in aggregate, but each callsite is small. E.g Map::find().

terrellnon Faster CRC32 on the Apple M1

Thanks for the pointer, will have to take a look!

terrellnon Faster CRC32 on the Apple M1

Could you combine both techniques to run both the SIMD version on some chunks and the crc32 instruction on other chunks, in parallel? Of course this would only work if they execute on different ports.

terrellnon Zstandard Worked Example

Yeah thats correct. I'll just point out that they use a larger window size, so they will use more memory to decompress, but will still be fast.

terrellnon Zstandard Worked Example

Yes! You can build a decompressor only version of zstd that is only 95 KB with my version of gcc.

    > make -j libzstd ZSTD_LIB_MINIFY=1 ZSTD_LIB_COMPRESSION=0 ZSTD_LIB_DICTBUILDER=0 ZSTD_LEGACY_SUPPORT=0 ZSTD_LIB_DEPRECATED=0
    > wc -c libzstd.so
    95824 libzstd.so

Longer term, we want to offer a stripped version of the library that includes the compression code, but only includes some of our compression levels. That way you can save code size for unused compression levels.

We've optimized pretty heavily in favor of speed over code size. But we want to offer better configurability, we just need to find the time to do it. We'd happily take PRs that go in this direction!

terrellnon Zstandard Worked Example

We're still reserving the right to fiddle around with the meaning of our negative compression levels. We think that we may be able to offer more compression at the same speeds by completely changing our search strategies for very fast compression speeds. But, there is only so much time in the day, and we haven't had time to investigate it yet. So we don't want to lock ourselves into a particular scheme right now.

terrellnon Zstandard Worked Example

Thanks for the feedback! I've opened an issue to track this [0]

* Levels 1-19 are the "standard" compression levels.

* Levels 20-22 are the "ultra" levels which require --ultra to use on the CLI. They allocate a lot of memory and are very slow.

* Level 0 is the default compression level, which is 3.

* Levels < 0 are the "fast" compression levels. They achieve speed by turning off Huffman compression, and by "accelerating" compression by a factor. Level -1 has acceleration factor 1, -2 has acceleration factor 2, and so on. So the minimum supported negative compression level is -131072, since the maximum acceleration factor is our block size. But in practice, I wouldn't think a negative level lower than -10 or -20 would be all that useful.

[0] https://github.com/facebook/zstd/issues/3133

terrellnon Zstandard Worked Example

> Does zstd benefit today from ISAs like AVX-512, AVX-2, etc.?

Zstd benefits mostly from BMI(2), it takes advantage of shlx, shrx, and bsf during entropy (de)coding. We do use SSE2 instructions in our lazy match finder to filter matches based on a 1-byte hash, in a similar way that F14 and Swiss hash tables do. We also use vector loads/stores to do our copies during decompression.

We don't currently benefit from AVX2. There are strategies to use AVX2 for Huffman & FSE compression, but they don't fit well with zstd's format, so we don't use them there. Additionally, our latest Huffman decoder is very competitive with the AVX2 decoder on real data. And a Huffman format that is fast for AVX2 is often slow for scalar decoding, so it is hard to opt into it unless you know you will only run on CPUs that support AVX2. Lastly, AVX2 entropy decoders rely on a fast gather instruction, which isn't available on AMD machines.

> Do you foresee the need in the future to offload compression/decompression to an accelerator?

Yes, there are trends in this direction. Intel QAT supports zlib hardware acceleration. The PS5 has accelerated decompression. I'm pretty sure Microsoft has also released a paper about a HW accelerated algorithm. Compression & decompression take up a significant portion of datacenter CPU, so it makes sense to hardware accelerate it.

> what hardware platform(s) do you use to test new versions of zstd for regressions/improvements?

We mostly test and optimize for x86-64 CPUs, on a mix of server and consumer CPUs. But, we also test on ARM devices to make sure we don't have major regressions. We've found that optimizing for x86-64 has done a good job of getting good baseline performance on other architectures, though there is certainly room left to improve.

terrellnon Zstandard Worked Example

Awesome post, it's great to see someone diving into the details of Zstd!

Maintainer of Zstd here, AMA

terrellnon Zstandard Worked Example

Zstd has a 4-byte magic number, which is used to check if the data is zstd encoded. In addition to that, this example has a 2 byte frame header (including the decompressed size), a 3 byte block header, and a 4 byte checksum at the end (which can be disabled with `--no-check`).

Zstd does have a mode that passes-through incompressible data, both for incompressible literals, and completely incompressible blocks (128 KB chunks).

For small inputs, we recommend using dictionary compression. But even with dictionary compression, because of our header costs, you won't generally see benefits until your data is at least ~50 bytes. But YMMV depending on your data.

terrellnon Zstandard v1.5.0

Yeah, it is.

The Linux kernel is currently using zstd-1.3.1, and I'm working on getting it updated to the latest zstd version.

terrellnon What Is Huffman Coding?

I recently reworked how zstd builds its Huffman decoding tables (not decoding itself) to avoid unpredictable branches and speed the table building up by about ~2x [0]. This is insignificant for large decompressions, but if you're decompressing only a few KB, the table building time can dominate the actual decompression.

It sort of goes to show that while Huffman codes have been around for ages, implementations can still improve, especially as the hardware we use changes.

[0] https://github.com/facebook/zstd/pull/2271

terrellnon Zstandard v1.4.7

Also, if you give zstd binary delta a try, we would be super interested in hearing the results you get! Especially around the tradeoff between compressed size, compression time, and decompression time. Opening an issue would be the best way to communicate it.

terrellnon Zstandard v1.4.7

You're right that a totally fair comparison would use zstd. I didn't personally run these benchmarks, but I believe that the dominate time was computing the binary subtraction mappings, so I would expect similar results.

terrellnon Zstandard v1.4.7

Zstd fully supports binary deltas. If you're computing a delta between `old` and `new` you would do this to round trip it:

zstd --patch-from=old new -c | zstd -d --patch-from=old

Using the library this can be achieved by using the old file as a dictionary. If you have very large files (MB-GB range) you will also want to enable long range mode, otherwise zstd might not be able to find the repetition. --patch-from on the CLI will manage this automatically.

The release notes from zstd-1.4.5 [0] contain some details about the speed/size tradeoff of "patch-from" mode, compared to other delta engines. There is also a wiki page detailing how to use zstd as a delta engine [1].

[0] https://github.com/facebook/zstd/releases/tag/v1.4.5

[1] https://github.com/facebook/zstd/wiki/Zstandard-as-a-patchin...

terrellnon Zstandard v1.4.7

One of the maintainers of zstd here, AMA

terrellnon A Concurrency Cost Hierarchy

Lets say you have 8 independent counters and 4 CPUs. Each gets 4 slots in 4-cacheline = 256 byte storage. Counter0 gets slots 0, 64, 128, and 192. Counter1 gets slots 8, 72, 136, and 200. And so on. Then you map CPU0 to slot 0, CPU1 to slot 1, CPU2 to slot 2, and CPU3 to slot 3.

Since we share the mapping between all counters. Any bump of any counter on CPU0 touches only cache line 0. So there isn't any false sharing.

In practice, mapping CPU to slot isn't quite so easy. But you can get a pretty good mapping using the strategy in this post, or something like folly::AccessSpreader::cachedCurrent() [0]. In new kernels, I believe there is kernel support for getting this mapping, using the rseq library. The kernel will update the current CPU in a thread local on every context switch.

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

terrellnon A Concurrency Cost Hierarchy

That’s true. But, I can’t tell all applications that use the counter library to reduce the number of threads they use.

terrellnon A Concurrency Cost Hierarchy

Yeah that’s right. All the counters use the same indexing scheme, so all accesses to the same cache line should be on the same core.

terrellnon A Concurrency Cost Hierarchy

I'm hoping to eventually migrate to restartable sequences.