terrelln

Fusion is so useful though. It is easy to set up on ships because it requires no consumables other than the fuel cells, and it has a small footprint. It is easy to set up power on all planets by stamping down a blueprint, and requires minimal resources shipped to them. If you're not expanding the factory, you probably already have a setup that works, so I can see why it would feel useless. But, when you want to double, or 10x your power consumption, fusion makes it easy.

I ran into a fun crash a year or so ago in the interaction of clang’s profile guided speculative devirtualization and identical code folding (ICF) done by BOLT on the binary.

Clang relied on checking the address of a function pointer in the vtable to validate the class was the type it expected, but it wasn’t necessarily the function that is currently being called. But due to ICF two different subclasses with two different functions shared the same address, so the code made incorrect assumptions about the type. Then it promptly segfaulted.

Also making good progress on getting a slimmer version of zstd into the stdlib

Awesome! Please let me know if there is anything I can do to help

Yeah, it isn't quite that simple. E.g. `/bin/ksh` reports 1.4MB, but it is actually 2.4MB. Initially, I thought it was because the file was sparse, but there are only 493KB of zeros. So something else is going on. Perhaps some filesystem-level blocks are deduped from other files? Or APFS has transparent compression? I'm not sure.

It does still seem odd that APFS is reporting a significantly larger disk-size for these files. I'm not sure why that would ever be the case, unless there is something like deferred cleanup work.

I've figured out the issue. Use `wc -c` instead of `du`.

I can repro on my Mac with these steps with either `zstd` or `gzip`:

    $ rm -f ksh.zst
    $ zstd < /bin/ksh > ksh.zst
    $ du -h ksh.zst
    1.2M ksh.zst
    $ wc -c ksh.zst
     1240701 ksh.zst
    $ zstd < /bin/ksh > ksh.zst
    $ du -h ksh.zst
    2.0M ksh.zst
    $ wc -c ksh.zst
     1240701 ksh.zst
    
    $ rm -f ksh.gz
    $ gzip < /bin/ksh > ksh.gz
    $ du -h ksh.gz
    1.2M ksh.gz
    $ wc -c ksh.gz
     1246815 ksh.gz
    $ gzip < /bin/ksh > ksh.gz
    $ du -h ksh.gz
    2.1M ksh.gz
    $ wc -c ksh.gz
     1246815 ksh.gz

I'm a zstd developer, so I have a vested interest in accurate benchmarks, and finding & fixing issues :)

Ah I understand. In this benchmark, Zstd's decompression time is 284 MB/s, and Gzip's is 330 MB/s. This benchmark is likely dominated by file IO for the faster decompressors.

On the incompressible files, I'd expect decompression of any algorithm to approach the speed of `memcpy()`. And would generally expect zstd's decompression speed to be faster. For example, on a x86 core running at 2GHz, Zstd is decompressing a file at 660 MB/s, and on my M1 at 1276 MB/s.

You could measure locally either using a specialized tool like lzbench [0], or for zstd by just running `zstd -b22 --ultra /path/to/file`, which will print the compression ratio, compression speed, and decompression speed.

[0] https://github.com/inikep/lzbench

Yeah, `--adaptive` will enable adaptive compression, but it isn't enabled by default, so shouldn't apply here. But even with `--adaptive`, after compressing each block of 128KB of data, zstd checks that the output size is < 128KB. If it isn't, it emits an uncompressed block that is 128KB + 3B.

So it is very central to zstd that it will never emit a block that is larger than 128KB+3B.

I will try to reproduce, but I suspect that there is something unrelated to zstd going on.

What version of zstd are you using?

Zstd should not be slower than gzip to decompress here. Given that it has inflated the files to be bigger than the uncompressed data, it has to do more work to decompress. This seems like a bug, or somehow measuring the wrong thing, and not the expected behavior.

| 1.1M | 2.0M | 1.1M | 1.1M | 1.1M |

Something is going terribly wrong with `zstd` here, where it is reported to compress a file of 1.1MB to 2MB. Zstd should never grow the file size by more than a very small percent, like any compressor. Am I interpreting it correctly that you're doing something like `zstd -22 --ultra $FILE && wc -c $FILE.zst`?

If you can reproduce this behavior, can you please file an issue with the zstd version you are using, the commands used, and if possible the file producing this result.

Its slang that has made its way from queer culture into mainstream. It is not meant to satisfy anyones ego, other than it just has vague positive connotations. It is used in a pretty equivalent way as "take that money, dude".

Out of curiosity, what was the input file format?

We actually worked on a demo WAV compressor a while back. We are currently missing codecs to run the types of predictors that FLAC runs. We expect to add this kind of functionality in the future, in a generic way that isn't specific to audio, and can be used across a variety of domains.

But, generally we wouldn't expect to generally beat FLAC. But, be able to offer specialized compressors for many types of data that previously weren't important enough to spawn a whole field of specialized compressors, by significantly lowering the bar for entry.

Amazing, thank you!

I will take a look as soon as I get a chance. Looking at the BAM format, it looks like the tokenization portion will be easy. Which means I can focus on the compression side, which is more interesting.

You could have an LLM generate the SDDL description [0] for you, or even have it write a C++ or Python tokenizer. If compression succeeds, then it is guaranteed to round trip, as the LLM-generated logic lives only on the compression side, and the decompressor is agnostic to it.

It could be a problem that is well-suited to machine learning, as there is a clear objective function: Did compression succeed, and if so what is the compressed size.

[0] https://openzl.org/api/c/graphs/sddl/

The charts in the "Results With OpenZL" section compare against all levels of zstd, xz, and zlib.

On highly structured data where OpenZL is able to understand the format, it blows Zstandard and Xz out of the water. However, not all data fits this bill.

We left it out of the paper because it is an implementation detail that is absolutely going to change as we evolve the format. This is the function that actually does it [0], but there really isn't anything special here. There are some bit-packing tricks to save some bits, but nothing crazy.

Down the line, we expect to improve this representation to shrink it further, which is important for small data. And to allow to move this representation, or parts of it, into a dictionary, for tiny data.

[0] https://github.com/facebook/openzl/blob/d1f05d0aa7b8d80627e5...

Do you happen to have a pointer to a good open source dataset to look at?

Naively and knowing little about CRAM, I would expect that OpenZL would beat Zstd handily out of the box, but need additional capabilities to match the performance of CRAM, since genomics hasn't been a focus as of yet. But it would be interesting to see how much we need to add is generic to all compression (but useful for genomics), vs. techniques that are specific only to genomics.

We're planning on setting up a blog on our website to highlight use cases of OpenZL. I'd love to make a post about this.

You'd have to tell OpenZL what your format looks like by writing a tokenizer for it, and annotating which parts are which. We aim to make this easier with SDDL [0], but today is not powerful enough to parse JSON. However, you can do that in C++ or Python.

Additionally, it works well on numeric data in native format. But JSON stores it in ASCII. We can transform ASCII integers into int64 data losslessly, but it is very hard to transform ASCII floats into doubles losslessly and reliably.

However, given the work to parse the data (and/or massage it to a more friendly format), I would expect that OpenZL would work very well. Highly repetitive, numeric data with a lot of structure is where OpenZL excels.

[0] https://openzl.org/api/c/graphs/sddl/

Is openzl indexable

Not today. However, we are considering this as we are continuing to evolve the frame format, and it is likely we will add this feature in the future.

Exactly! SDDL [0] provides a toolkit to do this all with no-code, but today is pretty limited. We will be expanding its feature set, but in the meantime you can also write code in C++ or Python to parse your format. And this code is compression side only, so the decompressor is agnostic to your format.

[0] https://openzl.org/api/c/graphs/sddl/

There's a Quick Start guide here:

https://openzl.org/getting-started/quick-start/

However, OpenZL is different in that you need to tell the compressor how to compress your data. The CLI tool has a few builtin "profiles" which you can specify with the `--profile` argument. E.g. csv, parquet, or le-u64. They can be listed with `./zli list-profiles`.

You can always use the `serial` profile, but because you haven't told OpenZL anything about your data, it will just use Zstandard under the hood. Training can learn a compressor, but it won't be able to learn a format like `.tar` today.

If you have raw numeric data you want to throw at it, or Parquets or large CSV files, thats where I would expect OpenZL to perform really well.

Yeah, backend compression in columnar data formats is a natural fit for OpenZL. Knowing the data it is compressing is numeric, e.g. a column of i64 or float, allows for immediate wins over Zstandard.

You can also use general purpose compressors like Zstandard to create a generic patch:

    zstd --patch-from old.json new.json -o patch.zst
    zstd --patch-from old.json -d patch.zst -o updated.json

Meta drove the Zstandard content encoding, but Google drove the adoption of Zstandard in Chrome.

The faster Brotli levels could probably be made to match Zstandard’s compression speed. But we’ve invested a lot in optimizing these levels, so it would likely take significant investment to match. Google is also contributing to improving the speed of Zstandard compression.

A cheaper conversion from Zstandard to Brotli is possible, but I wouldn’t really expect an improvement to compressed size. The encoding scheme impacts how efficient a LZ coding is, so for Brotli to beat Zstandard, it would likely want a different LZ than Zstandard uses. The same applies for a conversion from Brotli to Zstandard.

The latest Zstandard exposes several parameters which are useful for reducing time to first byte latency in web compression. They make Zstandard cut the compressed data into smaller blocks, e.g. 4 KB, with the goal to fit a compressed block within a small number of packets, so the browswer can start to decompress without waiting for a full 128 KB block to be sent.

These parameters are described in the v1.5.6 release notes [0]. ZSTD_c_targetCBlockSize is the most notable, but ZSTD_c_maxBlockSize can also be used for a lower CPU cost but larger compressed size.

Are you using these features at Cloudflare? If you need any help using these, or have any questions, please open an issue on Zstandard's GitHub!

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

I believe that the "more private" part is referencing the "Encrypted Client Hello (ECH)" section in the later part of the post.

Variable-length integer schemes are great when you are encoding one integer. But when you are encoding a list of integers, you should really consider a different scheme.

Variable-length integer schemes generally interleave the control bits & data bits. This means you don't know where the next integer starts until you at least partially decode the current integer.

When encoding a list of integers, you would rather put all the control information together, and all the data together. This generally allows for significantly more efficient decoding using SIMD.

I agree, this is a very exciting direction. We shouldn’t let existing formats stifle innovation, but there is a lot of value in back porting modern techniques to existing encoders.

I went through this course online a few summers ago, and learned a ton. I highly recommend it!

It was very engaging to put up PRs for small issues in the Bril IR, and work with the professor to fix them.

We also regularly run into hardware issues with Zstd. Often the decompressor is the first thing to interact with data coming over the network. Or like in this case the decompressor is generally very sensitive to bit-flips, with or without checksumming enabled, so notices other hardware problems more than other processes running on the same host.

One decision that Zstd made was to include only a checksum of the original data. This is sufficient to ensure data integrity. But, it makes it harder to rule out the decompressor as the source of the corruption, because you can't determine if the compressed data is corrupt.

I've recently started playing Factorio for the first time, and was thinking about using SAT solvers for automated sub-factory blueprint design with beacons. E.g. for a given recipe how do I design a sub-factory that builds the recipe with the minimum number of entities (or a given total entity weight, to allow for weighting buildings based on their impact on UPS). I've seen a paper [0] on a similar problem, but it doesn't take beacons into account. It seems like beacons make the problem significantly harder, because now positioning matters in order to share beacons. Does anyone have any ideas on how to approach this?

[0] https://arxiv.org/pdf/2310.01505.pdf