Fasthttp: Brotli compression

[thomasvvugt]

Hi Fasthttp,

I was wondering if you see any potential in supporting Brotli as an additional compression algorithm next to Gzip, Deflate and ZLib.

According to Google; Brotli is a generic-purpose lossless compression algorithm that compresses data using a combination of a modern variant of the LZ77 algorithm, Huffman coding and 2nd order context modeling, with a compression ratio comparable to the best currently available general-purpose compression methods. It is similar in speed with deflate but offers more dense compression.
https://github.com/google/brotli

EDIT: Also see https://github.com/google/brotli/tree/master/go/cbrotli, and apparently someone already ported Google's Brotli code to Go: https://github.com/andybalholm/brotli

I'd love to hear your opionions!
Kind regards.

[erikdubbelboer]

https://github.com/andybalholm/brotli seems to be very slow with many heap allocations: https://github.com/caddyserver/caddy/pull/2590#issuecomment-511933469 and https://github.com/andybalholm/brotli/issues/11

Brotli compression is quite slow compared to gzip. It's great for responses that you can compress once and keep serving (like static content). But not so great for on the fly compression of responses.

If you don't mind brotli being slow at compressing responses on the fly you are probably also better off just using net/http instead of fasthttp.

I don't want to include https://github.com/google/brotli/tree/master/go/cbrotli in fasthttp by default as it would mean it's not a pure Go package any more and requires cgo which stops a lot of people from using it.

Maybe we could make a small middleware in a different package that uses https://github.com/andybalholm/brotli to compress responses on the fly as an example.

[andybalholm]

cbrotli isn't always faster than the Go version. After fixing https://github.com/andybalholm/brotli/issues/11, I adapted some benchmarks from compress/flate to brotli. Here is the benchstat output, with old=cbrotli and new=andybalholm/brotli:

name                             old speed      new speed          delta
Decode/Digits/Speed/1e4-8        45.2MB/s ± 1%      51.9MB/s ± 2%         +14.79%  (p=0.029 n=4+4)
Decode/Digits/Speed/1e5-8        39.7MB/s ± 2%      48.0MB/s ± 2%         +21.07%  (p=0.029 n=4+4)
Decode/Digits/Speed/1e6-8        39.6MB/s ± 2%      48.5MB/s ± 4%         +22.61%  (p=0.029 n=4+4)
Decode/Digits/Default/1e4-8      35.6MB/s ± 1%      46.9MB/s ± 1%         +31.89%  (p=0.029 n=4+4)
Decode/Digits/Default/1e5-8      47.1MB/s ± 1%      62.0MB/s ±11%         +31.72%  (p=0.029 n=4+4)
Decode/Digits/Default/1e6-8       194MB/s ± 2%       302MB/s ± 1%         +55.26%  (p=0.029 n=4+4)
Decode/Digits/Compression/1e4-8  43.5MB/s ± 1%      58.5MB/s ± 1%         +34.46%  (p=0.029 n=4+4)
Decode/Digits/Compression/1e5-8  48.0MB/s ± 2%      64.4MB/s ± 1%         +34.13%  (p=0.029 n=4+4)
Decode/Digits/Compression/1e6-8   196MB/s ± 2%       299MB/s ± 2%         +52.99%  (p=0.029 n=4+4)
Decode/Newton/Speed/1e4-8        43.3MB/s ± 1%      57.8MB/s ± 4%         +33.55%  (p=0.029 n=4+4)
Decode/Newton/Speed/1e5-8        59.4MB/s ± 1%      79.3MB/s ± 1%         +33.43%  (p=0.029 n=4+4)
Decode/Newton/Speed/1e6-8        61.9MB/s ± 2%      82.6MB/s ± 7%         +33.35%  (p=0.029 n=4+4)
Decode/Newton/Default/1e4-8      45.7MB/s ± 1%      64.3MB/s ± 2%         +40.73%  (p=0.029 n=4+4)
Decode/Newton/Default/1e5-8      77.7MB/s ± 1%     105.0MB/s ± 1%         +35.09%  (p=0.029 n=4+4)
Decode/Newton/Default/1e6-8       151MB/s ± 2%       207MB/s ± 1%         +37.12%  (p=0.029 n=4+4)
Decode/Newton/Compression/1e4-8  44.7MB/s ± 3%      64.9MB/s ± 3%         +45.28%  (p=0.029 n=4+4)
Decode/Newton/Compression/1e5-8  76.7MB/s ± 1%     107.9MB/s ± 1%         +40.63%  (p=0.029 n=4+4)
Decode/Newton/Compression/1e6-8   151MB/s ± 1%       224MB/s ± 3%         +48.14%  (p=0.029 n=4+4)
Encode/Digits/Speed/1e4-8        54.4MB/s ± 3%      38.4MB/s ± 1%         -29.34%  (p=0.029 n=4+4)
Encode/Digits/Speed/1e5-8        46.9MB/s ± 3%      34.9MB/s ± 1%         -25.59%  (p=0.029 n=4+4)
Encode/Digits/Speed/1e6-8        92.7MB/s ± 4%      55.7MB/s ± 2%         -39.90%  (p=0.029 n=4+4)
Encode/Digits/Default/1e4-8      8.39MB/s ± 2%      7.30MB/s ± 0%         -13.02%  (p=0.029 n=4+4)
Encode/Digits/Default/1e5-8      6.94MB/s ± 4%      7.86MB/s ± 2%         +13.22%  (p=0.029 n=4+4)
Encode/Digits/Default/1e6-8      52.3MB/s ± 6%      62.9MB/s ± 2%         +20.24%  (p=0.029 n=4+4)
Encode/Digits/Compression/1e4-8   265kB/s ± 2%       340kB/s ± 3%         +28.30%  (p=0.029 n=4+4)
Encode/Digits/Compression/1e5-8   230kB/s ± 4%       332kB/s ± 2%         +44.57%  (p=0.029 n=4+4)
Encode/Digits/Compression/1e6-8  2.06MB/s ± 5%      2.95MB/s ± 2%         +43.20%  (p=0.029 n=4+4)
Encode/Newton/Speed/1e4-8        42.0MB/s ± 3%      32.4MB/s ± 1%         -22.86%  (p=0.029 n=4+4)
Encode/Newton/Speed/1e5-8        67.4MB/s ± 3%      52.7MB/s ± 2%         -21.84%  (p=0.029 n=4+4)
Encode/Newton/Speed/1e6-8        51.7MB/s ± 4%      37.3MB/s ± 1%         -27.97%  (p=0.029 n=4+4)
Encode/Newton/Default/1e4-8      9.12MB/s ± 3%      8.55MB/s ± 1%          -6.20%  (p=0.029 n=4+4)
Encode/Newton/Default/1e5-8      9.62MB/s ± 7%     10.20MB/s ± 1%          +5.95%  (p=0.029 n=4+4)
Encode/Newton/Default/1e6-8      14.6MB/s ± 6%      18.5MB/s ± 1%         +27.16%  (p=0.029 n=4+4)
Encode/Newton/Compression/1e4-8   210kB/s ± 0%       300kB/s ± 0%         +42.86%  (p=0.029 n=4+4)
Encode/Newton/Compression/1e5-8   205kB/s ± 2%       315kB/s ± 2%         +53.66%  (p=0.029 n=4+4)
Encode/Newton/Compression/1e6-8   310kB/s ± 3%       467kB/s ± 4%         +50.81%  (p=0.029 n=4+4)

[andybalholm]

Those benchmarks were with brotli libraries that I had compiled from source myself. When I reinstalled brotli with Homebrew, the new version was more than twice as fast. I'm not sure what I did wrong compiling the old install; I definitely did check to make sure it was passing -O2 to the compiler.

If the C version is compiled with the right options, I still have lots of room for improvement to beat it on performance :-P.

[erikdubbelboer]

@andrewheberle nice improvements! But for compressing something like the google.com HTML I still see 36 allocations per use. It seems like your brotli encoder is around 3 times slower than gzip on my machine for only 10% size reduction. For static content that is great, but for dynamic content, especially content that needs to be super fast (and thus uses fasthttp) it is not so good I think.

% GOGC=1 go test -bench . -benchmem -benchtime 4s
goos: darwin
goarch: amd64
BenchmarkBrotli-16          5272        848862 ns/op       60848 B/op         36 allocs/op
BenchmarkGzip-16           15091        316284 ns/op          54 B/op          0 allocs/op
PASS
ok      12.845s

% go run test.go 
brotli allocs per run: 36
gzip allocs per run: 0
brotli: 5240235 gzip: 5835830 ratio: 0.10205831903945106

[andybalholm]

Have you tried different compression levels (besides the default)? If you just use NewWriter, you get gzip level 5 and brotli level 6. Brotli level 4 is more-or-less comparable to gzip level 9, in both compression ratio and performance. If being super fast is your priority, you should be using level 1 or 2 on gzip and level 0 or 1 on brotli.

[erikdubbelboer]

I have just made a pull request to reduce the average number of allocations to 0: https://github.com/andybalholm/brotli/pull/12

The dafault level for gzip is 6.
When comparing this to brotli level 4 I get a slightly smaller result than gzip but still 1.5 times slower.

gzip 9 is still slightly faster than brotli 4 but also still slightly bigger.
And gzip 9 is slightly slower than brotli 3 but also slightly smaller.
gzip 1 is slightly faster than brotli 1 but also slightly bigger.

I think overall the choice of which algorithm to use depends on your payload and your use case.

After my pull request I'm in favor of adding support to fasthttp as it seems fast enough and causes no extra GC pressure.

My test code to can be found here: https://gist.github.com/erikdubbelboer/3e7b044e300be6a7ff2b76e6922052ec

[thomasvvugt]

Thanks for adding this in, really much appreciated!

[erikdubbelboer]

Made a pull request to add support to fasthttp: https://github.com/valyala/fasthttp/pull/810