Reduced dictionary feature for web content compression #332

New Issue

claunia · 2026-01-29T20:42:08Z

claunia commented

2026-01-29 20:42:08 +00:00

Originally created by @fhanau on GitHub (Aug 7, 2020).

As a part of my summer internship at Cloudflare, I worked on improving brotli dictionary compression for web data. Our changes implement a more thorough search of the dictionary for compression levels 5-9 with performance optimizations, resulting in a significant improvement in file size, particularly on small files, and a limited performance impact.
Measured at level 5 on a data set of HTML files smaller than 250kb, we achieve an average file size improvement of 6.8% (2.1% when weighted by file size). For CSS, the average file size is 2.8% lower (1% when weighted). The file improvement for other use cases or for larger files will be smaller. While the compression improvement comes with a 2% increase in CPU time, it is possible to get the performance of the current brotli code and thus improve compression without additional performance cost by using more aggressive heuristics while still retaining most of the compression improvement.

To achieve this, we use a different subset of the dictionary each for HTML, CSS and JS files and find matches using a combination of a bloom filter, a hash table and a radix trie, among other heuristics. Due to the nature of the dictionary and LZ compression, this will be primarily useful on small to medium-sized text files. While our work was focused on web content, extending it to plain text or for example XML data by generating a dictionary for these data types is also possible.

The code is available here. We think that the brotli project could also benefit from this, but there are some issues that should be considered before this can be integrated:

The code includes functions to create and load custom dictionaries, which is very useful for extending this work to new kinds of text data, but not needed for most users.
For performance reasons, a radix trie must be used. The current implementation uses a third-party radix trie library, which might not be an option for the brotli project.
Since initializing the radix trie takes some time, a dictionary object is created once and then used with one or several BrotliEncoderState objects, which is primarily useful when the dictionary is used with several files at once. This requires adding functions to the API and makes using the dictionary more complex.

Originally created by @fhanau on GitHub (Aug 7, 2020). As a part of my summer internship at Cloudflare, I worked on improving brotli dictionary compression for web data. Our changes implement a more thorough search of the dictionary for compression levels 5-9 with performance optimizations, resulting in a significant improvement in file size, particularly on small files, and a limited performance impact. Measured at level 5 on a data set of HTML files smaller than 250kb, we achieve an average file size improvement of 6.8% (2.1% when weighted by file size). For CSS, the average file size is 2.8% lower (1% when weighted). The file improvement for other use cases or for larger files will be smaller. While the compression improvement comes with a 2% increase in CPU time, it is possible to get the performance of the current brotli code and thus improve compression without additional performance cost by using more aggressive heuristics while still retaining most of the compression improvement. To achieve this, we use a different subset of the dictionary each for HTML, CSS and JS files and find matches using a combination of a bloom filter, a hash table and a radix trie, among other heuristics. Due to the nature of the dictionary and LZ compression, this will be primarily useful on small to medium-sized text files. While our work was focused on web content, extending it to plain text or for example XML data by generating a dictionary for these data types is also possible. The code is available [here](https://github.com/fhanau/brotli/tree/cloudflare-reduced_dict). We think that the brotli project could also benefit from this, but there are some issues that should be considered before this can be integrated: - The code includes functions to create and load custom dictionaries, which is very useful for extending this work to new kinds of text data, but not needed for most users. - For performance reasons, a radix trie must be used. The current implementation uses a third-party radix trie [library](https://github.com/antirez/rax), which might not be an option for the brotli project. - Since initializing the radix trie takes some time, a dictionary object is created once and then used with one or several BrotliEncoderState objects, which is primarily useful when the dictionary is used with several files at once. This requires adding functions to the API and makes using the dictionary more complex.

claunia commented

2026-01-29 20:42:09 +00:00

@eustas commented on GitHub (Aug 26, 2020):

Thanks, Felix.
Going to update this issue as the code gets integrated.

@eustas commented on GitHub (Aug 26, 2020): Thanks, Felix. Going to update this issue as the code gets integrated.

claunia commented

2026-01-29 20:42:09 +00:00

@polarathene commented on GitHub (May 5, 2021):

Related Cloudflare blog post from the author (published in Nov 2020).

The linked repo with two commits implementing the dictionary, will these be sent as a PR? Sounds like a nice improvement, but as it ages I am concerned that it will not as easily rebase onto upstream adding more friction towards seeing the improvements upstreamed.

From a quick glance, it does look like it'll need more time invested through review feedback to be merged. Is this something the author is going to have time for, or that Cloudflare is interested in sponsoring to be upstreamed or does it need to be deferred to someone else?

@polarathene commented on GitHub (May 5, 2021): [Related Cloudflare blog post from the author](https://blog.cloudflare.com/brotli-compression-using-a-reduced-dictionary/) (published in Nov 2020). The linked repo with two commits implementing the dictionary, will these be sent as a PR? Sounds like a nice improvement, but as it ages I am concerned that it will not as easily rebase onto upstream adding more friction towards seeing the improvements upstreamed. From a quick glance, it does look like it'll need more time invested through review feedback to be merged. Is this something the author is going to have time for, or that Cloudflare is interested in sponsoring to be upstreamed or does it need to be deferred to someone else?

claunia commented

2026-01-29 20:42:09 +00:00

@fhanau commented on GitHub (May 5, 2021):

I developed this feature as a part of an internship at Cloudflare, so Cloudflare and I are no longer involved with the feature. I think for integrating the code rebasing will be less of an issue than figuring out how to approach the caveats mentioned above. The additions to the API and the addition of an external library might not be ideal for the brotli project.
I think in the current form the code shows that the brotli dictionary shows a lot more potential than what is currently by the brotli code, in particular for compressing web content, but adding this feature to the main project will require some additional design decisions and likely writing more code.

@fhanau commented on GitHub (May 5, 2021): I developed this feature as a part of an internship at Cloudflare, so Cloudflare and I are no longer involved with the feature. I think for integrating the code rebasing will be less of an issue than figuring out how to approach the caveats mentioned above. The additions to the API and the addition of an external library might not be ideal for the brotli project. I think in the current form the code shows that the brotli dictionary shows a lot more potential than what is currently by the brotli code, in particular for compressing web content, but adding this feature to the main project will require some additional design decisions and likely writing more code.

claunia commented

2026-01-29 20:42:09 +00:00

@polarathene commented on GitHub (May 5, 2021):

I developed this feature as a part of an internship at Cloudflare, so Cloudflare and I are no longer involved with the feature.

Ah ok. So assuming Cloudflare kept the feature and is maintaining their own internal version instead of allocating resources to upstream it here, I guess it's unlikely any progress or further discussion is going to happen in the near future?

If I understand correctly, the gist of the feature was compatible with any brotli client, the feature was focused on optimizing compressing with the existing static dictionary as detailed in your excellent blog post; thus if ports of brotli in other languages did want to add the feature, they just need to add their own radix trie implementations and your feature logic and it'd work all the same? (as far as clients are concerned)

Dropbox has rust-brotli for example which provides a drop-in replacement C FFI. They've added various additions that upstream has not. I'm not sure about other implementations.

Thanks for contributing the feature and open-sourcing it along with the blog post. Hopefully it won't go to waste.

@polarathene commented on GitHub (May 5, 2021): > I developed this feature as a part of an internship at Cloudflare, so Cloudflare and I are no longer involved with the feature. Ah ok. So assuming Cloudflare kept the feature and is maintaining their own internal version instead of allocating resources to upstream it here, I guess it's unlikely any progress or further discussion is going to happen in the near future? If I understand correctly, the gist of the feature was compatible with any brotli client, the feature was focused on optimizing compressing with the existing static dictionary as detailed in your excellent blog post; thus if ports of brotli in other languages did want to add the feature, they just need to add their own radix trie implementations and your feature logic and it'd work all the same? (as far as clients are concerned) Dropbox has `rust-brotli` for example which provides a drop-in replacement C FFI. They've added various additions that upstream has not. I'm not sure about other implementations. Thanks for contributing the feature and open-sourcing it along with the blog post. Hopefully it won't go to waste.

claunia referenced this issue

2026-01-29 20:51:42 +00:00

[PR #332] [CLOSED] build: create an encoder and decoder library #929

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: starred/brotli#332