圧縮アルゴリズムZopfliとBrotli
compressどちらもGoogleが開発した圧縮アルゴリズム。
puppetter-lambda-starter-kit のissueに 現在使っているgzipと、Zopfli、Brotliを比較したデータが上がっていたので調べてみた。
Zopfli
出力としてDeflateに対応している。
Deflate
LZ77(実際は改良版のLZSS)とハフマン記号による可逆圧縮アルゴリズム。 zip、zlib、gzip、pngなどで使われていて、これらはヘッダーやフッターが異なる。 LZSSはバイト列を見ていって同じ部分を発見したらそこを参照するように置き換えていく。
a b c a b c a b c d d d
=> a b c (距離3, 長さ6) d (距離１, 長さ2)
このLZSSにあたる部分をZopfliはがんばってやるので圧縮時間が結構かかるがサイズは小さくなるらしい。 展開は通常のDeflate通り。上げてくれたデータを見ても大体そんな感じだ。
$ git clone https://github.com/google/zopfli
$ cd zopfli
$ make zopfli
$ ./zopfli aaaa
Brotli
LZ77、ハフマン記号に加えて2nd order context modelingというのを使って圧縮する Deflateではない可逆圧縮アルゴリズム。 Safari以外のモダンなブラウザで既に対応しているか対応しているところ。 対応している場合、Accept-Encoding や Content-Encoding ヘッダに含まれるのはbr。 圧縮率も展開時間もかなり良さそう。
Nodeにもblotliのライブラリがあって、 圧縮はEmscriptenで本家のC++コードから変換し、 展開は手で移植しているようだ。
$ npm install blotli
const fs = require('fs');
const brotli = require('brotli');
const TARGET = process.env.TARGET;
const MODE = process.env.MODE;
const compress = () => {
const target = fs.readFileSync(TARGET);
const compressed = brotli.compress(target, {
quality: 11,
});
fs.writeFileSync(`${TARGET}.br`, compressed);
};
const decompress = () => {
const target = fs.readFileSync(TARGET);
const decompressed = brotli.decompress(target);
fs.writeFileSync(`${TARGET.replace('.br', '')}`, decompressed);
};
(async () => {
if (MODE === 'decompress') {
decompress();
} else {
compress();
}
})();
ただ、これで大きなファイルを圧縮しようとすると以下のようなエラーが出て失敗する。 設定を変えてコンパイルするのも面倒なので、圧縮はCLIでやることにした。
$ TARGET=headless_shell node compress.js
Cannot enlarge memory arrays. Either (1) compile with -s TOTAL_MEMORY=X with X higher than the current value 318767104, (2) compile with -s ALLOW_MEMORY_GROWTH=1 which adjusts the size at runtime but prevents some optimizations, (3) set Module.TOTAL_MEMORY to a higher value before the program runs, or if you want malloc to return NULL (0) instead of this abort, compile with -s ABORTING_MALLOC=0
リポジトリをcloneしてきてmake installする。
$ git clone https://github.com/google/brotli.git
$ cd brotli
$ mkdir out && cd out
$ ../configure-cmake
$ make
$ make test
$ make install
$ brotli --version
brotli 1.0.1
デフォルトで最高レベル(11)で圧縮することもあり、かなり時間がかかる。
$ time brotli headless_shell
$ time brotli headless_shell
real 18m41.814s
user 18m6.485s
sys 0m7.906s
gzipだと最高レベルで圧縮しても43MBまでのところ、33MBまで圧縮できた。
131M headless_shell
33M headless_shell.br
展開はすぐ。むしろgzipより速い。
$ time TARGET=aaaa.br MODE=decompress node compress.js
real 0m5.850s
user 0m4.626s
sys 0m1.030s
ということで、brotli対応版を出そうとしたが、Lambdaでdecompressしたら JavaScript heap out of memory になってしまった。