tinc devel - May 2015 - Packet compression benchmark

Hello,

Darik Horn sent a pull request adding support for LZ4. LZ4 is supposed
to be a very fast compression algorithm, especially when it comes to
decompression. I did a quick benchmark with zlib, LZO and LZ4. Now,
there are many benchmarks you can find online, but most of them deal
with compressing large files. Tinc on the other hand has to compress
small packets individually. So I did the benchmark with two different
packet sizes; 1451 (which is the usual payload size of VPN packets that
tinc sents on MTU 1500 paths) and 8951 (the equivalent if you enable
jumbograms and your network supports it, not likely over the Internet).

Both the speed (higher is better) and the compression ratio (lower is
better) are benchmarked. The speed is measured for both compressing and
decompressing the data. If you are CPU bound and have a high bandwidth
network, then this is what you are interested in. If on the other hand
you are bandwidth limited, then the compression ratio is what is most
important.

I also used for different types of data; zero bytes (perfectly
compressible, but otherwise useless), HTML, binary executables, and
random data (totally incompressible).

The test was done with a single thread, and libraries were used provided
by the distribution used.

CPU:  Intel(R) Core(TM) i7-5930K CPU @ 3.50GHz
OS:   Debian unstable, updated 2015-05-10
zlib: 1.2.8.dfsg-2+b1
LZO:  2.0.8-1.2
LZ4:  0.0~r122-2

Packet size 1451:

Algorithm   Zero bytes                   HTML                         Binary
executables           Random bytes
-------------------------------------------------------------------------------------------------------------------------
zlib1:      59.17 MB/s, ratio 0.02       26.09 MB/s, ratio 0.44       20.55
MB/s, ratio 0.55       22.29 MB/s, ratio 1.01
zlib2:      68.50 MB/s, ratio 0.02       27.73 MB/s, ratio 0.43       21.52
MB/s, ratio 0.55       23.91 MB/s, ratio 1.01
zlib3:      58.83 MB/s, ratio 0.02       27.66 MB/s, ratio 0.43       21.28
MB/s, ratio 0.54       23.91 MB/s, ratio 1.01
zlib4:      56.40 MB/s, ratio 0.01       25.97 MB/s, ratio 0.42       20.42
MB/s, ratio 0.54       23.81 MB/s, ratio 1.01
zlib5:      56.43 MB/s, ratio 0.01       25.25 MB/s, ratio 0.42       19.57
MB/s, ratio 0.53       23.81 MB/s, ratio 1.01
zlib6:      56.40 MB/s, ratio 0.01       25.07 MB/s, ratio 0.42       18.98
MB/s, ratio 0.53       23.82 MB/s, ratio 1.01
zlib7:      56.38 MB/s, ratio 0.01       24.95 MB/s, ratio 0.42       18.54
MB/s, ratio 0.53       23.81 MB/s, ratio 1.01
zlib8:      56.31 MB/s, ratio 0.01       24.78 MB/s, ratio 0.42       17.67
MB/s, ratio 0.53       23.82 MB/s, ratio 1.01
zlib9:      56.23 MB/s, ratio 0.01       24.77 MB/s, ratio 0.42       17.64
MB/s, ratio 0.53       23.82 MB/s, ratio 1.01
lzo1x_1:   960.53 MB/s, ratio 0.03      262.21 MB/s, ratio 0.60      265.83
MB/s, ratio 0.68     1153.17 MB/s, ratio 1.01
lzo1x_999:  92.66 MB/s, ratio 0.01       22.01 MB/s, ratio 0.52       17.39
MB/s, ratio 0.59       21.94 MB/s, ratio 1.01
lz4:      1959.64 MB/s, ratio 0.01      259.62 MB/s, ratio 0.61      241.18
MB/s, ratio 0.69      737.30 MB/s, ratio 1.00
lz4hc:      91.20 MB/s, ratio 0.01       50.70 MB/s, ratio 0.58       53.35
MB/s, ratio 0.66       61.54 MB/s, ratio 1.00
-------------------------------------------------------------------------------------------------------------------------

Packet size 8951:

Algorithm   Zero bytes                   HTML                         Binary
executables           Random bytes
-------------------------------------------------------------------------------------------------------------------------
zlib1:     166.48 MB/s, ratio 0.01       50.99 MB/s, ratio 0.34       40.02
MB/s, ratio 0.47       61.11 MB/s, ratio 1.00
zlib2:     242.66 MB/s, ratio 0.01       61.03 MB/s, ratio 0.33       42.73
MB/s, ratio 0.47       67.24 MB/s, ratio 1.00
zlib3:     276.03 MB/s, ratio 0.01       59.23 MB/s, ratio 0.32       40.40
MB/s, ratio 0.46       67.26 MB/s, ratio 1.00
zlib4:     142.70 MB/s, ratio 0.00       51.44 MB/s, ratio 0.31       37.54
MB/s, ratio 0.45       65.27 MB/s, ratio 1.00
zlib5:     142.78 MB/s, ratio 0.00       46.27 MB/s, ratio 0.31       33.11
MB/s, ratio 0.45       65.31 MB/s, ratio 1.00
zlib6:     142.77 MB/s, ratio 0.00       44.13 MB/s, ratio 0.31       29.13
MB/s, ratio 0.45       65.31 MB/s, ratio 1.00
zlib7:     142.80 MB/s, ratio 0.00       42.94 MB/s, ratio 0.30       26.86
MB/s, ratio 0.45       65.29 MB/s, ratio 1.00
zlib8:     142.80 MB/s, ratio 0.00       40.08 MB/s, ratio 0.30       20.81
MB/s, ratio 0.45       65.28 MB/s, ratio 1.00
zlib9:     142.72 MB/s, ratio 0.00       38.73 MB/s, ratio 0.30       16.67
MB/s, ratio 0.45       65.28 MB/s, ratio 1.00
lzo1x_1:  1446.85 MB/s, ratio 0.01      275.53 MB/s, ratio 0.44      260.76
MB/s, ratio 0.59     3448.94 MB/s, ratio 1.00
lzo1x_999: 126.39 MB/s, ratio 0.01       21.76 MB/s, ratio 0.36       11.27
MB/s, ratio 0.50       21.47 MB/s, ratio 1.00
lz4:      3227.05 MB/s, ratio 0.01      310.78 MB/s, ratio 0.46      259.55
MB/s, ratio 0.62     1734.28 MB/s, ratio 1.00
lz4hc:     429.67 MB/s, ratio 0.01       89.88 MB/s, ratio 0.41       76.56
MB/s, ratio 0.57      105.71 MB/s, ratio 1.00
-------------------------------------------------------------------------------------------------------------------------

The data would suggest that LZO is better than LZ4 in almost all
scenarios. Also, zlib with compression level 1 is worse in both speed
and compression ratio than level 2.

-- 
Met vriendelijke groet / with kind regards,
     Guus Sliepen <guus at tinc-vpn.org>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: Digital signature
URL:
<http://www.tinc-vpn.org/pipermail/tinc-devel/attachments/20150511/f5c23622/attachment.sig>

On Mon, May 11, 2015 at 01:17:29AM +0200, Guus Sliepen wrote:

[...]
> zlib1:      59.17 MB/s, ratio 0.02       26.09 MB/s, ratio 0.44       20.55
MB/s, ratio 0.55       22.29 MB/s, ratio 1.01
> zlib2:      68.50 MB/s, ratio 0.02       27.73 MB/s, ratio 0.43       21.52
MB/s, ratio 0.55       23.91 MB/s, ratio 1.01
[...]
> Also, zlib with compression level 1 is worse in both speed
> and compression ratio than level 2.
Oops, that's just because the cache is not hot for the first run of the
benchmark. So the zlib1 speed values are too low, redoing the tests with
a proper dry-run before each run makes the zlib1 values as expected
(marginally faster than zlib2). No significant changes for the other
values.

-- 
Met vriendelijke groet / with kind regards,
     Guus Sliepen <guus at tinc-vpn.org>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: Digital signature
URL:
<http://www.tinc-vpn.org/pipermail/tinc-devel/attachments/20150511/9b058ec7/attachment.sig>

On Sun, May 10, 2015 at 7:17 PM, Guus Sliepen <guus at tinc-vpn.org>
wrote:
>
> Darik Horn sent a pull request adding support for LZ4.
The PR is:

* https://github.com/gsliepen/tinc/pull/78

> LZ4 is supposed
> to be a very fast compression algorithm, especially when it comes to
> decompression. I did a quick benchmark with zlib, LZO and LZ4. Now,
> there are many benchmarks you can find online, but most of them deal
> with compressing large files. Tinc on the other hand has to compress
> small packets individually
The proposed 1.1-LZ4 branch implements block mode.  Given that you are
familiar with the code, is there a way to guarantee packet ordering at
the decompressor so that stream mode can also be implemented?

> The data would suggest that LZO is better than LZ4 in almost all
> scenarios. Also, zlib with compression level 1 is worse in both speed
> and compression ratio than level 2.
Even in block mode, I got the usual tradeoff for non-pathological
data:  LZ4 produces a slightly larger image for much less CPU time
than LZO.

I'm working on getting LZ4 baked into an OpenWRT build for further
testing, which is the kind of embedded system where Tinc really
shines.

On Sun, May 10, 2015 at 08:16:54PM -0400, Darik Horn wrote:
> > LZ4 is supposed
> > to be a very fast compression algorithm, especially when it comes to
> > decompression. I did a quick benchmark with zlib, LZO and LZ4. Now,
> > there are many benchmarks you can find online, but most of them deal
> > with compressing large files. Tinc on the other hand has to compress
> > small packets individually
> 
> The proposed 1.1-LZ4 branch implements block mode.  Given that you are
> familiar with the code, is there a way to guarantee packet ordering at
> the decompressor so that stream mode can also be implemented?
Yes, with TCPOnly. But then additional code would be required to
compress the stream going via TCP. The main drawback of TCPOnly is that
it lowers the performance of the VPN. It might very well be that this
negates any advantage of compression.
> Even in block mode, I got the usual tradeoff for non-pathological
> data:  LZ4 produces a slightly larger image for much less CPU time
> than LZO.
Please note that since LZ4 has a worse compression ratio than LZO and
zlib, the only advantage would be its use when you are not
bandwidth-limited. So the real benchmark for LZ4 is what transfer speed
you get when the sender side is using 100% of its CPU.
> I'm working on getting LZ4 baked into an OpenWRT build for further
> testing, which is the kind of embedded system where Tinc really
> shines.
It would indeed be very nice to see how the compression algorithms
perform on an embedded device.

-- 
Met vriendelijke groet / with kind regards,
     Guus Sliepen <guus at tinc-vpn.org>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: Digital signature
URL:
<http://www.tinc-vpn.org/pipermail/tinc-devel/attachments/20150511/39b2abf2/attachment.sig>