Compression algorithms explanation [LZ4,zstd,lizard]

[fibersel]

Hi, right now I study at University and work at my coursework, related to compression algorithms.
And I consider Lizard library, compared to ZSTD and LZ4.
Can anyone provide explanations of these algorithms and why Lizard provides better performance than LZ4?

[Shelwien]

Well,
https://en.wikipedia.org/wiki/Zstandard#Design
https://en.wikipedia.org/wiki/LZ4_(c...orithm)#Design
"Lizard" (https://github.com/inikep/lizard; aka LZ5) is simply a branch of LZ4 with added optional huffman coding.
There could be also some unique speed optimizations, but nothing noticeable: https://github.com/inikep/lizard#benchmarks
and likely the only way to compare LZ4 vs lizard would be to directly analyze the sources... or get @inikep to explain, but I don't think he has time for that.
To start, you'd have to actually benchmark the algorithms on your own - LZ4 and zstd also kept updating, so I don't think there's an up-to-date benchmark anywhere.

Also keep in mind that "levels" are arbitrary, they're simply indices in a table with detailed compressor parameter profiles:
https://github.com/inikep/lizard/blo..._common.h#L234
But only zstd has a dedicated tool for optimization of these level profiles - https://github.com/facebook/zstd/blo...mgrill.c#L2632
so manually chosen profiles in other compressors may have worse performance,
while not actually reflecting the best possible performance of the algorithm (with optimal parameters for given data).

[lz77]

why Lizard provides better performance than LZ4?

I guess, because LZ4 has only one codeword type: 16 bit for offset, and 4 bit for literal/match length counter. This is wasteful.

[fibersel]

Lizard has more codeword types?

[lz77]

I don't know about Lizard, but LZ5 has 4 or 5 codeword types.

[Dresdenboy]

I don't know about Lizard, but LZ5 has 4 or 5 codeword types.

This still seems to be the case:

The token is a one byte. Token decribes:

• how many literals should be copied from Literals_Stream
• if offset should be read from 16-bit_Offsets_Stream or 24-bit_Offsets_Stream
• how many bytes are part of a match and should be copied from a sliding window

Lizard uses 4 types of tokens:

• [0_MMMM_LLL] - 3-bit literal length (0-7+), use offset from 16-bit_Offsets_Stream, 4-bit match length (4-15+)
• [1_MMMM_LLL] - 3-bit literal length (0-7+), use last offset, 4-bit match length (0-15+)
• token 31 - no literal length, use offset from 24-bit_Offsets_Stream, match length (47+)
• token 0-30 - no literal length, use offset from 24-bit_Offsets_Stream, 31 match lengths (16-46)

​lizard/lizard_Block_format.md at lizard · inikep/lizard · GitHub

[lz77]

Yes, I saw these codewords in LZ5 a few years ago. They make me smile.
I'm planning to write simple LZ-type compressor (without preprocessor for the/and/.../E8/E9 etc.) that compresses enwik8 up to ~40.5% and (de)compresses it faster than zstd -1 (ratio = 40.8%). Or maybe I'm trying in vain and there are already such compressors?

[lz77]

4 questions about the fastest compression mode (zstd.exe -1 ...)

1. Does zstd use additional compression (Huffman, FSE) besides LZ?
2. Is there any optimization (E8/E9 etc.) or analysis of source data to configure the compression algorithm?
3. What is the size of the hash table with this option (how many cells and are there chains)?
4. What is the size of the input buffer?

Thanks.

[Shelwien]

0) -1 is not the fastest mode (--fast=# ones are faster).
It seems that --fast disables huffman coding for literals, but still keeps FSE for matches.
1) Yes, huffman for literals, FSE for matches - or nothing if block is incompressible
2) No. Certainly no preprocessing, but maybe you'd say that "--adapt" mode is related.
3) https://github.com/facebook/zstd/blo...mpress.c#L5003 - 16k cells
4) The library works with user buffers of whatever size, zstdcli seems to load 128KB blocks with fread.
https://github.com/facebook/zstd/blo...ib/zstd.h#L108

[lz77]

Wow, I guess I finishing writing (for now in Delphi 7) not bad simple pure LZ77-type compressor called notbadlz. I'm trying to beat zstd at fast levels for sporting interest. I set in my compressor 128K input buffer and 16K cells, here are results:
(zstd-v1.4.4-win64)

A:\>timer.exe zstd.exe --fast -f --no-progress --single-thread enwik8

Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
enwik8               : 51.82%   (100000000 => 51817322 bytes, enwik8.zst)


Kernel Time  =     0.062 = 00:00:00.062 =   7%
User Time    =     0.781 = 00:00:00.781 =  90%
Process Time =     0.843 = 00:00:00.843 =  98%
Global Time  =     0.859 = 00:00:00.859 = 100%
***

A:\>timer.exe notbadlz.exe


Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
Source size 100000000, packed size: 47086177 ratio 0.47086
Done in 1.35210


Kernel Time  =     0.078 = 00:00:00.078 =   5%
User Time    =     1.359 = 00:00:01.359 =  93%
Process Time =     1.437 = 00:00:01.437 =  98%
Global Time  =     1.453 = 00:00:01.453 = 100%
***

A:\>timer.exe zstd.exe -d -f --no-progress --single-thread enwik8.zst -o enwik


Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
enwik8.zst          : 100000000 bytes


Kernel Time  =     0.109 = 00:00:00.109 =  24%
User Time    =     0.203 = 00:00:00.203 =  44%
Process Time =     0.312 = 00:00:00.312 =  68%
Global Time  =     0.453 = 00:00:00.453 = 100%

A:\>timer notbadlzunp.exe


Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
Compressed size: 47086177 Decompressed size: 100000000
Done in 0.52653 sec.


Kernel Time  =     0.093 = 00:00:00.093 =  12%
User Time    =     0.515 = 00:00:00.515 =  68%
Process Time =     0.609 = 00:00:00.609 =  81%
Global Time  =     0.750 = 00:00:00.750 = 100%

With 128K cells and input buffer size = 256 Mb notbadlz compresses enwik8 better than zstd -1. Zstd does it faster, but I have in stock asm 64, prefetch etc. Now I'm thinking whether it's worth porting my program in FASM...

[Shelwien]

Maybe increase window size for zstd? "-1" default is 512kb
Also test newer zstd? They made significant speed improvements in 1.4.5, and extra 5% in 1.4.7 too.

[fcorbelli]

Wow, I guess I finishing writing (for now in Delphi 7) not bad simple pure LZ77-type compressor called notbadlz. I'm trying to beat zstd at fast levels for sporting interest. I set in my compressor 128K input buffer and 16K cells, here are results:
(zstd-v1.4.4-win64)

A:\>timer.exe zstd.exe --fast -f --no-progress --single-thread enwik8

Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
enwik8               : 51.82%   (100000000 => 51817322 bytes, enwik8.zst)


Kernel Time  =     0.062 = 00:00:00.062 =   7%
User Time    =     0.781 = 00:00:00.781 =  90%
Process Time =     0.843 = 00:00:00.843 =  98%
Global Time  =     0.859 = 00:00:00.859 = 100%
***

A:\>timer.exe notbadlz.exe


Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
Source size 100000000, packed size: 47086177 ratio 0.47086
Done in 1.35210


Kernel Time  =     0.078 = 00:00:00.078 =   5%
User Time    =     1.359 = 00:00:01.359 =  93%
Process Time =     1.437 = 00:00:01.437 =  98%
Global Time  =     1.453 = 00:00:01.453 = 100%
***

A:\>timer.exe zstd.exe -d -f --no-progress --single-thread enwik8.zst -o enwik


Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
enwik8.zst          : 100000000 bytes


Kernel Time  =     0.109 = 00:00:00.109 =  24%
User Time    =     0.203 = 00:00:00.203 =  44%
Process Time =     0.312 = 00:00:00.312 =  68%
Global Time  =     0.453 = 00:00:00.453 = 100%

A:\>timer notbadlzunp.exe


Timer 3.01  Copyright (c) 2002-2003 Igor Pavlov  2003-07-10
Compressed size: 47086177 Decompressed size: 100000000
Done in 0.52653 sec.


Kernel Time  =     0.093 = 00:00:00.093 =  12%
User Time    =     0.515 = 00:00:00.515 =  68%
Process Time =     0.609 = 00:00:00.609 =  81%
Global Time  =     0.750 = 00:00:00.750 = 100%

With 128K cells and input buffer size = 256 Mb notbadlz compresses enwik8 better than zstd -1. Zstd does it faster, but I have in stock asm 64, prefetch etc. Now I'm thinking whether it's worth porting my program in FASM...

Can you please post the Delphi source?

[lz77]

> Can you please post the Delphi source?

Pardon, I have another plans. I do not receive a salary either on Google or on Facebook. I want to sell this algorithm and sources (in C) as a shareware. Perhaps the students will be interested in this. Maybe in the next GDC this algorithm will help me win a prize.

Maybe increase window size for zstd? "-1" default is 512kb
Also test newer zstd? They made significant speed improvements in 1.4.5, and extra 5% in 1.4.7 too.

zstd ver. 1.4.7 in fast mode and single thread shows the same results: 50% faster than notbadlz, but ratio worse on 4%.

notbadlz with input buffer size = 100 Mb and hash table size = 2 Mb compresses enwik8 up to 38.75%, silesia.tar up to 35%.