q9 significantly faster than q6 for specific input #206

New Issue

claunia · 2026-01-29T20:39:50Z

claunia commented

2026-01-29 20:39:50 +00:00

Originally created by @fasterthanlime on GitHub (Jan 9, 2018).

I've been in touch with Jyrki Alakuijala on twitter after I noticed compressing with q9 being faster than q6, and they mentioned q9 being faster "unusual".

The behavior was observed deep into a golang program using (non-official) cgo bindings, so I've been trying to reproduce it with vanilla brotli, and I was finally able to!

Exhibit

This is not a "benchmark done right", but I've been playing with various input files for dozens of runs for the last 48h and I've noticed this pattern quite a bit.

How I built brotli

I followed the instructions in README.md - this was run on windows-amd64, compiled with cmake:

$ mkdir out && cd out
$ cmake -DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX=./installed ..
$ cmake --build . --config Release --target install

CMake auto-detected and used Visual Studio 14 2015 to compile. Note that when I originally observed the performance difference, brotli's sources were built with gcc 7.2.0 (built by the MSYS2 project) via cgo.

The version of brotli I used was da254cffdb (HEAD of master at the time of this writing)

The data

Here's a none.br.zip file, which is a 2.3MB zip archive (due to github issues limitations) containing a brotli-q9-compressed version of my sample input.

📦 none.br.zip

The uncompressed input (none) is a 2.2GB file. Its SHA-256 checksum is:

352994da7a1b3f10e665e7eb4f477e9ebeaf5088742e4fddfacd7d4901d51df5

It compresses particularly well (brotli performs splendidly in particular) because it's a patch file inspired by the original BSDiff paper.

In particular, the file:

Starts with a 4-byte magic number
Is a stream of protobuf messages, prefixed by their length (dead-simple framing)
After a few header messages, most of the messages are bsdiff instructions (see the protobuf schema)

It's supposed to compress well because bsdiff is basically:

Find slices from the "old" file and the "new" file that are similar
Compute byte-wise differences between these slices
The patch instruction is slice start in old and new, length, and the byte-wise difference (a large binary blob which, if everything goes well, should be mostly zero, and the differences should have nice repeating patterns, think 00000029000000000000290000000000) - this is called diff data
If there's no slice similar enough, the new data is included as-is in the patch - this is called extra data

Other differences from the original bsdiff:

vanilla bsdiff uses bzip2 for its patch format
vanilla bsdiff patches are divided into three sections:
- all instructions (without data)
- all diff data
- all extra data
...whereas our version stores diff data and extra data directly after the relevant instruction - and limits an instruction's slice size. This lets us to streaming diff & apply with lower memory/disk requirements, with a slight compression penalty, I have a tweet thread about this for the curious.

Hypotheses

Although I've played with compression formats a lot, I cannot claim to understand its inner workings, but I've noticed the following:

In some parts of the code, LGBLOCK is adjusted differently for q>=9. I saw this here first, but I haven't checked that it doesn't appear somewhere else. Maybe q>=9 gets a smaller LGBLOCK, resulting in faster compression for this particular data ?
There's a speed up RLE-ish data compression commit (and this input data might be RLE-ish? depending on the meaning of it), but afaict I was seeing the performance difference before that commit.

Conclusion

At this point I'm tempted to use q=9 rather than q=6-8 (our diff process is much slower than brotli compression anyway, and we're running it on a machine with many cores, so it's not a bottleneck), but I figured it'd be interesting to brotli developers and I might learn a thing or two in the process :)

Originally created by @fasterthanlime on GitHub (Jan 9, 2018). I've been in touch with Jyrki Alakuijala on twitter after I noticed compressing with q9 being faster than q6, and they mentioned q9 being faster "unusual". The behavior was observed deep into a golang program using (non-official) cgo bindings, so I've been trying to reproduce it with vanilla brotli, and I was finally able to! --- ### Exhibit ![brotli-q6-vs-q9](https://user-images.githubusercontent.com/7998310/34720298-7c503464-f53e-11e7-8c71-adaeb7fc273d.png) This is not a "benchmark done right", but I've been playing with various input files for dozens of runs for the last 48h and I've noticed this pattern quite a bit. ### How I built brotli I followed the instructions in `README.md` - this was run on windows-amd64, compiled with cmake: ``` $ mkdir out && cd out $ cmake -DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX=./installed .. $ cmake --build . --config Release --target install ``` CMake auto-detected and used `Visual Studio 14 2015` to compile. Note that when I originally observed the performance difference, brotli's sources were built with gcc 7.2.0 (built by the MSYS2 project) via cgo. The version of brotli I used was https://github.com/google/brotli/commit/da254cffdb160bd6ac1cd6ea01944099978cbb71 (HEAD of master at the time of this writing) ### The data Here's a `none.br.zip` file, which is a 2.3MB zip archive (due to github issues limitations) containing a brotli-q9-compressed version of my sample input. :package: [none.br.zip](https://github.com/google/brotli/files/1615018/none.br.zip) The uncompressed input (`none`) is a **2.2GB file**. Its SHA-256 checksum is: `352994da7a1b3f10e665e7eb4f477e9ebeaf5088742e4fddfacd7d4901d51df5` It compresses particularly well (brotli performs splendidly in particular) because it's a patch file inspired by the original [BSDiff paper](http://www.daemonology.net/papers/bsdiff.pdf). In particular, the file: * Starts with a 4-byte magic number * Is a stream of protobuf messages, prefixed by their length (dead-simple framing) * After a few header messages, most of the messages are bsdiff instructions (see the [protobuf schema](https://github.com/itchio/wharf/blob/master/bsdiff/bsdiff.proto)) It's supposed to compress well because bsdiff is basically: * Find slices from the "old" file and the "new" file that are similar * Compute byte-wise differences between these slices * The patch instruction is slice start in old and new, length, and the byte-wise difference (a large binary blob which, if everything goes well, should be *mostly* zero, and the differences should have nice repeating patterns, think `00000029000000000000290000000000`) - this is called `diff data` * If there's no slice similar enough, the new data is included as-is in the patch - this is called `extra data` Other differences from the original bsdiff: * vanilla bsdiff uses bzip2 for its patch format * vanilla bsdiff patches are divided into three sections: * all instructions (without data) * all `diff data` * all `extra data` * ...whereas our version stores `diff data` and `extra data` directly after the relevant instruction - and limits an instruction's slice size. This lets us to streaming diff & apply with lower memory/disk requirements, with a slight compression penalty, I have a [tweet thread](https://twitter.com/fasterthanlime/status/790617515009437701) about this for the curious. ### Hypotheses Although I've played with compression formats a lot, I cannot claim to understand its inner workings, but I've noticed the following: * In some parts of the code, LGBLOCK is adjusted differently for q>=9. I saw this [here](https://github.com/kothar/brotli-go/blob/771231d473d6c4896e97c2b6e3855f1afc0cdada/enc/encode.go#L23-L27) first, but I haven't checked that it doesn't appear somewhere else. Maybe q>=9 gets a smaller LGBLOCK, resulting in faster compression for this particular data ? * There's a `speed up RLE-ish data compression` commit (and this input data might be RLE-ish? depending on the meaning of it), but afaict I was seeing the performance difference before that commit. ### Conclusion At this point I'm tempted to use q=9 rather than q=6-8 (our diff process is much slower than brotli compression anyway, and we're running it on a machine with many cores, so it's not a bottleneck), but I figured it'd be interesting to brotli developers and I might learn a thing or two in the process :)

claunia referenced this issue

2026-01-29 20:50:59 +00:00

[PR #206] [MERGED] Encoder bug fixes. #804

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: starred/brotli#206