Repository files navigation

LZAV is a fast general-purpose in-memory data compression algorithm based onnow-classicLZ77 lossless datacompression method. LZAV holds a good position on the Pareto landscape offactors, among many similar in-memory (non-streaming) compression algorithms.

LZAV algorithm's code is portable, cross-platform, scalar, header-only,inlineable C (C++ compatible). It supports big- and little-endian platforms,and any memory alignment models. The algorithm is efficient on both 32- and64-bit platforms. Incompressible data almost does not expand. Compliant withWebAssembly (WASI libc), and runs at just twice lower performance than nativecode.

LZAV does not sacrifice internal out-of-bounds (OOB) checks for decompressionspeed. This means that LZAV can be used in strict conditions where OOB memorywrites (and especially reads) that lead to a trap, are unacceptable (e.g.,real-time, system, server software). LZAV can be used safely (causing nocrashing nor UB) even when decompressing malformed or damaged compressed data.Which means that LZAV does not require calculation of a checksum (or hash) ofthe compressed data. Only a checksum of the uncompressed data may be required,depending on application's guarantees.

The internal functions available in thelzav.h file allow you to easilyimplement, and experiment with, your own compression algorithms. LZAV streamformat and decompressor have a potential of high decompression speeds andcompression ratios, which depends on the way data is compressed.

To compress data:

#include"lzav.h"intmax_len=lzav_compress_bound(src_len );void*comp_buf=malloc(max_len );intcomp_len=lzav_compress_default(src_buf,comp_buf,src_len,max_len );if(comp_len==0&&src_len!=0 ){// Error handling.}

To decompress data:

#include"lzav.h"void*decomp_buf=malloc(src_len );intl=lzav_decompress(comp_buf,decomp_buf,comp_len,src_len );if(l<0 ){// Error handling.}

To compress data with a higher ratio, for non-time-critical uses (e.g.,compression of application's static assets):

#include"lzav.h"intmax_len=lzav_compress_bound_hi(src_len );// Note another bound function!void*comp_buf=malloc(max_len );intcomp_len=lzav_compress_hi(src_buf,comp_buf,src_len,max_len );if(comp_len==0&&src_len!=0 ){// Error handling.}

LZAV algorithm and its source code (which isISO C99) were quality-tested with:Clang, GCC, MSVC, Intel C++ compilers; on x86, x86-64 (Intel, AMD), AArch64(Apple Silicon) architectures; Windows 10, AlmaLinux 9.3, macOS 15.3.1.Full C++ compliance is enabled conditionally and automatically, when thesource code is compiled with a C++ compiler.

If for some reason, in C++ environment, it is undesired to export LZAV symbolsinto the global namespace, theLZAV_NS_CUSTOM macro can be definedexternally:

#defineLZAV_NS_CUSTOM lzav#include"lzav.h"

Similarly, LZAV symbols can be placed into any other custom namespace (e.g.,a namespace with data compression functions):

#defineLZAV_NS_CUSTOM my_namespace#include"lzav.h"

This way, LZAV symbols and functions can be referenced likemy_namespace::lzav_compress_default(...). Note that since all LZAV functionshave astatic inline specifier, there can be no ABI conflicts, even if theheader is included in unrelated, mixed C/C++, compilation units.

The tables below present performance ballpark numbers of LZAV algorithm(based on Silesia dataset).

While LZ4 there seems to be compressing faster, LZAV comparably provides 14.8%memory storage cost savings. This is a significant benefit in database andfile system use cases since compression is only about 35% slower while CPUsrarely run at their maximum capacity anyway (considering cached data writesare deferred in background threads), and disk I/O times are reduced due to abetter compression. In general, LZAV holds a very strong position in thisclass of data compression algorithms, if one considers all factors:compression and decompression speeds, compression ratio, and not lessimportant - code maintainability: LZAV is maximally portable and has a rathersmall independent codebase.

Performance of LZAV is not limited to the presented ballpark numbers.Depending on the data being compressed, LZAV can achieve 800 MB/s compressionand 5000 MB/s decompression speeds. Incompressible data decompresses at 10000MB/s rate, which is not far from the "memcpy". There are cases like theenwik9 dataset where LZAVprovides 21.7% higher memory storage savings compared to LZ4. However, onsmall data (below 50 KB), compression ratio difference between LZAV and LZ4diminishes, and LZ4 may have some advantage (due to smaller minimalback-reference length).

LZAV algorithm's geomean performance on a variety of datasets is 550 +/- 150MB/s compression and 3800 +/- 1300 MB/s decompression speeds, on 4+ GHz 64-bitprocessors released since 2019. Note that the algorithm exhibits adaptivequalities, and its actual performance depends on the data being compressed.LZAV may show an exceptional performance on your specific data, including, butnot limited to: sparse databases, log files, HTML/XML files.

It is also worth noting that compression methods like LZAV and LZ4 usuallyhave an advantage over dictionary- and entropy-based coding in thathash-table-based compression has a small operation and memory overhead whilethe classic LZ77 decompression has no overhead at all - this is especiallyrelevant for smaller data.

For a more comprehensive in-memory compression algorithms benchmark you mayvisitlzbench.

Silesia compression corpus

Silesia compression corpus

Silesia compression corpus

P.S. Popular Zstd's benchmark was not included here, because it is not a pureLZ77, much harder to integrate, and has a much larger code size - a differentleague, close to zlib. Here are author's Zstd measurements withTurboBench, on Ryzen 3700X,on Silesia dataset:

1. LZAV API is not equivalent to LZ4 nor Snappy API. For example, the "dstl"parameter in the decompressor should specify the original uncompressed length,which should have been previously stored in some way, independent of LZAV.

2. From a technical point of view, peak decompression speeds of LZAV have animplicit limitation arising from its more complex stream format, compared toLZ4: LZAV decompression requires more code branching. Another limiting factoris a rather big 8 MiB LZ77 window which is not CPU cache-friendly. On theother hand, without these features it would not be possible to achievecompetitive compression ratios while having fast compression speeds.

3. LZAV supports compression of continuous data blocks of up to 2 GB. Largerdata should be compressed in chunks of at least 32 MB. Using smaller chunksmay reduce the achieved compression ratio.

• Paul Dreik, for finding memcpy UB in thedecompressor.