LZFSE - New Apple Data Compression

[dnd]

Claiming better compression, 3 times faster (compression) than zlib and 60% reduction in energy use.

Reference:
iOS Developer Library
LZFSE is a new algorithm, matching the compression ratio of ZLIB level 5,
but with much higher energy efficiency and speed (between 2x and 3x) for both encode and decode operations.


LZFSE is only present in iOS and OS X, so it can’t be used when the compressed payload has to be shared to other platforms (Linux, Windows).
In all other cases, LZFSE is recommended as a replacement for ZLIB.


Presentation at Apple Conference WWDC 2015:
(begin ~25:50)

More References:
- Release Notes
- Discussion at Hacker-News

Benchmarks:
I've included LZFSE in TurboBench and benchmarked the fastest compressors with similar compression ratio.

TurboBench: CPU i7-2600k at 4,2 GHz (all compressors with latest version 18 JUN 2016)

      C Size  ratio%     C MB/s     D MB/s   Name            File              (bold = pareto) MB=1.000.0000
    36775168    36.7      66.85    1460.28   lzturbo 32      app3.tar
    46562400    46.5     198.73    1220.31   lzturbo 31      app3.tar
    46804845    46.8      50.60     964.08   zstd 9          app3.tar
    48788658    48.7      83.87     350.78   brotli 4        app3.tar
    49159780    49.1     133.69     880.02   zstd 4          app3.tar
    49521949    49.5      69.80     622.48   lzfse           app3.tar
    49784097    49.7      51.23    2011.81   lzturbo 22      app3.tar
    49962678    49.9      35.23     308.44   zlib 6          app3.tar
    50152281    50.1      43.90     306.01   zlib 5          app3.tar

      C Size  ratio%     C MB/s     D MB/s   Name            File              (bold = pareto) MB=1.000.0000
    59827047    28.2      53.30    1002.34   lzturbo 32      silesia.tar
    60416836    28.5      48.19     839.14   zstd 9          silesia.tar
    66035804    31.2     183.94    1020.04   lzturbo 31      silesia.tar
    66404949    31.3     130.11     736.24   zstd 4          silesia.tar
    66858972    31.5      80.24     452.16   brotli 4        silesia.tar
    67624724    31.9      69.51     734.42   lzfse           silesia.tar
    68225985    32.2      32.61     362.39   zlib 6          silesia.tar
    69159650    32.6      45.93     355.86   zlib 5          silesia.tar
    73815607    34.8      54.92    1821.74   lzturbo 22      silesia.tar

The benchmark shows LzTurbo compress better, 3 times faster and decompress up to 2,5 times faster than lzfse.

lzfse compress only 1,5 times faster than zlib 5, whereas Apple is claiming between 2 and 3 times faster.

[Jarek]

"LZFSE is an Apple-developed algorithm that is faster than ZLIB, and generally achieves a better compression ratio. However, it is slower than LZ4 and does not compress as well as LZMA, so you will still want to use LZ4 if speed is critical or LZMA if compression ratio is critical"

LZ+FSE?
zhuff or ZSTD-like?
Any benchmarks?

Update: indeed "Lempel Ziv finite state entropy"

[Jarek]

http://devstreaming.apple.com/videos...accelerate.pdf
"LZFSE = Lempel-Ziv + Finite State Entropy"
it says that comparing to zlib:
1.02x better compression ratio
energy efficiency on arm64: 2.42x for decode, 2.24x for encode
speed on arm64: 3.04x decode, 2.30x encode
also API is introduced.

[dnd]

Reference iOS Developer Library updated. LZFSE is only present in iOS and OS X

[calthax]

LZFSE is basically proprietary ZSTD. ZSTD will eventually become better and faster
Also I have a question to ask dnd Is this LZFSE yours

[dnd]

No, from Apple

[Jarek]

LZFSE is available in OS X 10.11+ through hdiutil - some test: http://forums.macrumors.com/threads/...#post-21529699
iTunes v12.1.2 to a disk image (sparse, 512 MB) to
zlib -5: 157528377 35.9Mbytes/sec (encoding?)
LZFSE: 152603202 59.0Mbytes/sec

[Jarek]

Both iOS9 and OS X 10.11 are in public beta now - can be downloaded for free.
It would be interesting to test LZFSE, compare to ZSTD, verify that it uses FSE (Huffman can be excluded by testing skewed distribution, range coding by speed), the license of FSE says that they should clearly mention using it. If it is close to ZSTD, it could be doable to have a PC decoder ...
Maybe someone has some i-stuff?

update: they probably also improved image compression: https://twitter.com/Jato_BZ/status/6...159232/photo/1
"the iOS 9 .car files appear to use either LZ4 or LSFSE compression to store image files too. Not just for the watch(...)OS 8.4 SpringBoard assets.car is 1MB, on iOS 9 b1 it's 180KB & has the header ZZZZ-packed asset 1.0.0"

[Jarek]

The using LZFSE: iOS9, watchOS 2, OS X 10.11 are already released (16th or 30th September), used by millions of users.

But I still couldn't find any serious benchmark - maybe you know somebody who knows ... who use iStuff?
Especially that we still don't know if its Finite State Entropy is Yann's, what should be seen in benchmarks, and which license says:
"Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution."
Shouldn't Apple state anything anywhere?

As iOS has shrank from 4.6GB to 1.3GB, another interesting question is how much is compressed there - are we going to the age of OS compressed by default?

[Cyan]

Apple's CoreOS teams typically like to rewrite code themselves.
So I guess they used FSE as a blueprint, and rewrote their own version, potentially using direct assembler for hot segments.
That's what they did for LZ4, and there is little reason they would do differently for FSE.

Apple have an history of not necessarily complying with Open Source license terms.
So the presence of the BSD license notice is not guaranteed.
But anyway, in this case, they have respected the name, which I believe is great.

[Jarek]

Some benchmarks for DropDMG of creating image of boot partition of MacBook Air: http://mjtsai.com/blog/2015/10/07/lz...in-el-capitan/
name savings throughput
zlib (10.10) 21.4% 63.5 MB/s
zlib (10.11) 22.3% 36.8 MB/s
LZFSE (10.11) 23.8% 107.7 MB/s
bzip2 (10.11) 23.2% 11.7 MB/s
none 0% 114.4 MS/s

[Jyrki Alakuijala]

Note, that these results were obtained with different input files, with possibly different characteristics. This is unusual for a compression benchmark.

[Jarek]

Sure, these are not serious benchmarks - which additionally should be rather performed in-memory.
But we are talking about compressor which is already (unknowingly) used by hundreds of millions of users - until there are serious tests, we should at least have some poor ones to get a general picture.
Another conclusion is that quick compressors suggest that default compression of even system files might be a good idea - and ZSTD-like compressor is perfect for dynamical files.

It seems they also use LZFSE in lossless image compression:
http://stackoverflow.com/questions/3...application-bu
https://twitter.com/Jato_BZ/status/6...159232/photo/1

There is also important question of compatibility - is Apple planning to release e.g. Windows decompressor?
Or maybe it would be worth to try to develop a LZFSE-compatible branch of ZSTD? How would it look from the legal side?

[dnd]

Added

Benchmarks:
- Disk Image Compression incl I/O lzfse,zlib,bzip: El Capitan/DropDMG

[nemequ]

Apple has an open-source implementation up on GitHub now: https://github.com/lzfse/lzfse

It seems quite buggy ATM; asyoulik.txt segfaults, round-tripping some random data sometimes fails… but still, at least we have details of the LZFSE format, as well as a way to play with it a bit outside of OS X.

[ebainville]

Bug fixed. Thanks for reporting it.
For best results, try compiling with clang -Os and target your CPU (ex: -march=haswell).

[nemequ]

Bug fixed. Thanks for reporting it.

That was quick, thanks. Fixing that is enough that all of Squash's unit tests, at least on platforms where we can get LZFSE built (basically, everywhere except MSVC), so I've gone ahead and merged an LZFSE plugin into master. I'll try to post some benchmarking results tomorrow.

[jibz]

The biggest issue for MSVC compatibility is the use of labels as values in lzvn_decode_base.c .. but I don't know if there is any interest in supporting other compilers than GCC/Clang.

[Zyzzyva]

First of all, it's great to see this open sourced! I know that such a thing can be difficult at some companies, and I appreciate the work that may have gone into it.

The license appears to be 3-clause BSD.

I don't think the format is officially described anywhere yet, but here are my notes from an initial reading of the code (beware: I may have made a few errors):

There are four block types:

* Uncompressed
* LZVN
* LZFSE, uncompressed tables
* LZFSE, compressed tables

LZVN is byte oriented, with no entropy coding. The encoder uses it for buffers less than 4096 bytes. Otherwise, it uses LZFSE.

For LZFSE, the FSE-encoded alphabets are:

Literals (size=256)
Literal run length slots (size=20)
Match length slots (size=20)
Match offset slots (size=64)

For each LZFSE block, literals are encoded separately with 4 interleaved FSE streams, then the main symbol stream is encoded as sequences of {literal run length, match length, match distance}, called {L, M, D} in the code. The maximums are L=315, M=2359, D=262139. The minimum match length is unclear and might even be "0" (which would be strange) but it looks like the encoder uses length >= 3 only. Offset slot 0 represents "last offset".

The way FSE states are assigned to symbols may be suboptimal. The Apple code looks like it just initializes the states in order --- so you would have the states for symbol 0, then symbol 1, etc. all in order. The approach used by Yann Collett's code, on the other hand, is to step through the table in increments of about 5/8 the table size. This distributes the states fairly evenly and worked well when I tried it.

The method of count normalization for FSE is basically to sort the symbols by increasing count, then set:

normalized_count = (double)count * ((double)num_states_remaining / (double)total_count_remaining);

I wonder how well that works.

The encoder seems fairly standard, given that fast encoding is a goal. Stronger encoders would be possible, of course, but are not provided yet. It looks like it usually chooses the longest match, though there are a few details that I still need to work though. The matchfinder is a hash table with 2^14 buckets, each containing 4 entries. The entries are 8 bytes each: 4 for the match position and 4 for the first 4 bytes of the match. The hash function is standard (same as LZ4's, for example): hash = (first_4_bytes * 2654435761) >> (32 - 14). New FSE tables are sent as soon as there have been 10000 matches or 40000 literals.

A couple oddities that need more investigation: it looks like the encoder checks for length 3 matches, yet only uses 4 byte hashing. I'm not sure how this works. It also seemed to sometimes extend matches backwards. Also, there are a few places in the code hardcoded to do things 8 bytes at a time, which may be suboptimal on 32-bit platforms.

Otherwise it usually seems to have the typical optimizations, such as doing word accesses instead of byte accesses.

Overall the format and implementation is about what I expected. Nothing super magical has jumped out at me, but it seems pretty solid and probably is a good zlib alternative. At a high level it shares a lot of similarities with ZSTD and also my experimental format, XPACK.

[Zyzzyva]

LZFSE's frequency normalization algorithm (how the compressor decides how many FSE states to assign to each symbol) actually doesn't work too well and hurts the compression ratio a little bit. I opened a pull request to change it to the algorithm I'm using in XPACK, which is also more similar to the one used in FiniteStateEntropy and ZSTD. The improvement on the Silesia corpus is from 67,809,153 bytes to 67,628,688 bytes.

The way LZFSE assigns symbols to FSE states is definitely somewhat poor as well. Fixing it to distribute the symbols more evenly improved compression on the Silesia corpus from 67,809,153 bytes to 67,539,396 bytes. Unfortunately, this particular problem can't be fixed if the compression format is already stable, as it would require changing the decompressor.

It's still a pretty good format regardless, though --- most other things seem to have been done right.

[Jarek]

Indeed the symbols are spread in ranges like in Huffman - it is still an improvement (no restriction to use a power-of-two appearances), but it is better to spread them more uniformly:
https://github.com/JarekDuda/Asymmet...SystemsToolkit

[ebainville]

I didn't have time to introduce myself yesterday. My name is Eric Bainville, and I will be maintaining the LZFSE repository on Github.
Thanks for all the suggestions you already made, this is great! Also, thanks Jarek for your articles on ANS.

[Zyzzyva]

I didn't have time to introduce myself yesterday. My name is Eric Bainville, and I will be maintaining the LZFSE repository on Github.
Thanks for all the suggestions you already made, this is great! Also, thanks Jarek for your articles on ANS.

Out of curiosity, are you also the original author of the code?

[Jyrki Alakuijala]

Simple test for compression density for the web. Tried today from latest github for brotli, lzfse, zstd (0.7.0) on three web pages, comparing these three algorithms with zopfli as 100 % reference, and gzip, bzip2 and xz as additional data points:

1. wget http://web.archive.org/web/201606172...oft.com/en-us/
2. wget http://web.archive.org/web/201606170...w.sina.com.cn/
3. wget http://web.archive.org/web/201606180...rakuten.co.jp/

bro -q 11
bzip2 -9
gzip -9
zstd -22
lzfse, xz and zopfli without quality settings
also, hacked up version of brotli without static dictionary matches

97389 index.html.1
19750 index.html.1.gzip9 +3.4 %
19095 index.html.1.gz 0.0 %
20022 index.html.1.lzfse +4.8 %
18474 index.html.1.zst -3.3 %
17912 index.html.1.xz -6.2 %
19340 index.html.1.bz2 +1.3 %
17497 index.html.1.br (no static dict) -8.4 %
16084 index.html.1.br -15.8 %

635069 index.html.2
132362 index.html.2.gzip9 +3.8%
127560 index.html.2.gz 0.0 %
128415 index.html.2.lzfse +0.6 %
109069 index.html.2.zst -14.5 %
102392 index.html.2.xz -19.7 %
98591 index.html.2.bz2 -22.7 %
99611 index.html.2.br (no static dict) -21.8 %
97508 index.html.2.br -23.6 %

356195 index.html.3
66435 index.html.3.gzip9 +3.7 %
64040 index.html.3.gz 0.0 %
64192 index.html.3.lzfse +0.2 %
55383 index.html.3.zst -13.5 %
52324 index.html.3.xz -18.3 %
52798 index.html.3.bz2 -17.6 %
51291 index.html.3.br (no static dict) -20.0 %
49761 index.html.3.br -22.3 %

[jibz]

FWIW I got lzfse working on Windows with mingw-w64, MSVC 2015, Clang, and Clang/C2. Only tested on a few files so far though.

Attached are 64-bit binaries compiled with mingw-w64 and MSVC for comparison. They were compiled with:

gcc -s -DNDEBUG -D_FILE_OFFSET_BITS=64 -D__USE_MINGW_ANSI_STDIO=1 -O2 -flto -mtune=native -o lzfse_gcc.exe *.c -static
cl /O2 /fp:fast /GL /DNDEBUG /Felzfse_msvc.exe *.c /link /opt:ref,icf /subsystem:console,5.02 /release

Edit: I compiled it with Clang, and it appears to be faster than the other builds, so attached are now also 64-bit binaries compiled with Clang targeting mingw-w64 and MSVC respectively. Here are some timings for enwik9 on a Core-i5 (compresses to 319756993):

Comp.      Encode       Decode
GCC    41.52 MB/s  404.69 MB/s
MSVC   37.04 MB/s  368.45 MB/s
Clang  46.57 MB/s  323.97 MB/s

[dnd]

see http://encode.su/threads/2221-LZFSE-...ll=1#post44117

[Zyzzyva]

Here are a few initial numbers I collected for compressing the Silesia corpus on x86_64, with the caveat that I was unable to include vaporware such as lzturbo which has no source code:

                              Csize (bytes)  Ctime (ms) Dtime (ms)
Brotli, -6 -w 19              60,285,238     12457      786 
Brotli, -6 -w 18              61,100,491     11176      813 
ZSTD -7                       61,975,738     6326       468
XPACK -6 (chunk size 524288)  62,216,855     7922       419
ZSTD -6                       62,981,472     4723       476
ZSTD -5                       65,006,998     3315       489
XPACK -5 (chunk size 262144)  65,330,086     4292       443
DEFLATE, libdeflate -7        67,611,241     5076       452
LZFSE                         67,628,688     4708       464
DEFLATE, libdeflate -6        67,929,556     4073       450
DEFLATE, libz -7              67,940,580     14471      940
DEFLATE, libz -6              68,229,313     11941      942

Interestingly, LZFSE didn't really do any better than a properly optimized DEFLATE implementation, but it certainly was much faster than the one almost everyone uses. LZFSE also has larger sliding window size than DEFLATE (262144 vs. 32768 bytes), and I believe a significantly stronger LZFSE encoder would be possible, compared with the one currently available.

I am going to try this benchmark on ARM next.

Edit: recompiled LZFSE with clang; this improved decompression speed by about 10% over gcc.

[Zyzzyva]

Here are some results for ARM on the Silesia corpus. All code was compiled for 32-bit ARM with GCC 4.9 from the Android SDK and run on an Android phone with an ARMv7 processor. I used custom benchmark programs which timed the compression and decompression only --- no I/O.

Method                        Csize (bytes)  Ctime (ms) Dtime(ms)
----------------------------- -------------  ---------- ---------
Brotli, -6 -w 19              60285238       123318     3679      
Brotli, -6 -w 18              61100491       91707      3663      
XPACK -7, chunk size 524288   61716701       91185      2236      
ZSTD -7                       61973220       51132      3596      
XPACK -6, chunk size 524288   62216855       60510      2210      
ZSTD -6                       62978944       36774      3592      
XPACK -5, chunk size 262144   64163392       32086      2205      
ZSTD -5                       65003387       25196      3683      
DEFLATE, libdeflate -7        67611241       35879      1929      
LZFSE                         67628688       27318      2866      
DEFLATE, libdeflate -6        67929556       30768      1933      
DEFLATE, libz -7              67940580       50505      2448      
DEFLATE, libz -6              68229313       42472      2455      
DEFLATE, libdeflate -5        68497168       27259      1943      
DEFLATE, libz -5              69163650       31478      2490      
XPACK -1, chunk size 131072   72597325       13250      2673      
DEFLATE, libdeflate -1        73319223       20543      2113      
ZSTD -1                       73659639       9425       3153      
DEFLATE, libz -1              77261079       15627      2703

I was not too impressed with the LZFSE results. It wasn't even that much better than standard zlib and actually decompressed more slowly. As I suggested before, the LZFSE implementation appeared to be optimized for 64-bit platforms only. I would guess that either Apple was only interested in AArch64 and not traditional ARM (I don't currently have an AArch64 device to test), or they have a more optimized version of the code which hasn't been publicly released.

[Jyrki Alakuijala]

Here are some results for ARM on the Silesia corpus. All code was compiled for 32-bit ARM with GCC 4.9 from the Android SDK and run on an Android phone with an ARMv7 processor. I used custom benchmark programs which timed the compression and decompression only --- no I/O.

Brotli -q 11 -w 24 compresses Silesia to 50297179 bytes, 19 % smaller than the top algorithm on your list. It would be interesting to know how it compares in your benchmark for decoding speed. I'm predicting 3600 ms, since brotli tends to be 35 % slower than zlib on 32-bit arm.

[nemequ]

Here is a version of the squash benchmark with LZFSE and LZVN:

https://quixdb.github.io/squash-benchmark/unstable/

Note that Squash doesn't yet expose LZVN, it's blocked on a pull request to the LZFSE repo.

Note that there is a link to the CSV in the "Choose a machine" section if you want the raw data.