density

Superfast compression library

1015

DENSITY

Superfast compression library

DENSITY is a free C99, open-source, BSD licensed compression library.

It is focused on high-speed compression, at the best ratio possible. All three of DENSITY’s algorithms are currently at the pareto frontier of compression speed vs ratio (cf. here for an independent benchmark).

DENSITY features a simple API to enable quick integration in any project.

Branch	Linux & MacOS	Windows
master
dev

Why is it so fast ?

One of the biggest assets of DENSITY is that its work unit is not a byte like other libraries, but a group of 4 bytes.

When other libraries consume one byte of data and then apply an algorithmic processing to it, DENSITY consumes 4 bytes and then applies its algorithmic processing.

That’s why DENSITY’s algorithms were designed from scratch. They have to alleviate for 4-byte work units and still provide interesting compression ratios.

Speed pedigree traits

4-byte work units
heavy use of registers as opposed to memory for processing
avoidance of or use of minimal branching when possible
use of low memory data structures to favor processor cache Lx accesses
library wide inlining
specific unrollings
prefetching and branching hints
restricted pointers to maximize compiler optimizations

A “blowup protection” is provided, dramatically increasing the processing speed of incompressible input data. Also, the output, compressed data size will never exceed the original uncompressed data size by more than 1% in case of incompressible, reasonably-sized inputs.

Benchmarks

Quick benchmark

DENSITY features an integrated in-memory benchmark. After building the project (see build), a benchmark executable will be present in the build directory. If run without arguments, usage help will be displayed.

File used : enwik8 (100 MB)

Platform : MacBook Pro, MacOS 10.13.3, 2.3 GHz Intel Core i7, 8Gb 1600 MHz DDR, SSD, compiling with Clang/LLVM 9.0.0

Timing : using the time function, and taking the best user output after multiple runs. In the case of density, the in-memory integrated benchmark’s best value (which uses the same usermode CPU timing) is used.

_Library	_Algorithm	_Compress	_Decompress	_Size	_Ratio	_{Round trip}
_{density 0.14.2}	_Chameleon	_{0.092s (1085 MB/s)}	_{0.059s (1684 MB/s)}	_{61 524 084}	_61,52%	_0.151s
_{lz4 r129}	_-1	_{0.468s (214 MB/s)}	_{0.115s (870 MB/s)}	_{57 285 990}	_57,29%	_0.583s
_{lzo 2.08}	_-1	_{0.367s (272 MB/s)}	_{0.309s (324 MB/s)}	_56 709 096	_56,71%	_0.676s
_{density 0.14.2}	_Cheetah	_{0.170s (587 MB/s)}	_{0.126s (796 MB/s)}	_{53 156 668}	_53,16%	_0.296s
_{density 0.14.2}	_Lion	_{0.303s (330 MB/s)}	_{0.288s (347 MB/s)}	_{47 817 692}	_47,82%	_0.591s
_{lz4 r129}	_-3	_{1.685s (59 MB/s)}	_{0.118s (847 MB/s)}	_{44 539 940}	_44,54%	_1.803s
_{lzo 2.08}	_-7	_{9.562s (10 MB/s)}	_{0.319s (313 MB/s)}	_{41 720 721}	_41,72%	_9.881s

Other benchmarks

Here are a few other benchmarks featuring DENSITY (non exhaustive list) :

squash is an abstraction layer for compression algorithms, and has an extremely exhaustive set of benchmark results, including density’s, available here.
lzbench is an in-memory benchmark of open-source LZ77/LZSS/LZMA compressors.
fsbench is a command line utility that enables real-time testing of compression algorithms, but also hashes and much more. A fork with density releases is available here for easy access.
The original author’s repository can be found here.

Build

DENSITY can be built on a number of platforms, via the provided makefiles.

It was developed and optimized against Clang/LLVM which makes it the preferred compiler, but GCC and MSVC are also supported. Please use the latest compiler versions for best performance.

MacOS

On MacOS, Clang/LLVM is the default compiler, which makes things simpler.

Get the source code :

    git clone https://github.com/k0dai/density.git
    cd density

Build and test :

    make
    build/benchmark -f

Alternatively, thanks to the Homebrew project, DENSITY can also be installed with a single command on MacOS:

    brew install density

Linux

On Linux, Clang/LLVM is not always available by default, but can be easily added thanks to the provided package managers.
The following example assumes a Debian or Ubuntu distribution with apt-get.

From the command line, install Clang/LLVM (optional, GCC is also supported if Clang/LLVM can’t be used) and other prerequisites.

    sudo apt-get install clang git

Get the source code :

    git clone https://github.com/k0dai/density.git
    cd density

Build and test :

    make

    make CC=gcc-... AR=gcc-ar-...

    make CC=clang-... AR=llvm-ar-...

to choose alternative compilers. For a quick test of resulting binaries, run

    build/benchmark -f

Windows

Please install git for Windows to begin with.

On Windows, density can be built in different ways.
The first method is to use mingw’s gcc compiler; for that it is necessary to download and install mingw-w64.

Once mingw-w64 is installed, get the source :

    git clone https://github.com/k0dai/density.git
    cd density

Build and test :

    mingw32-make.exe
    build/benchmark.exe -f

As an alternative, MSYS2 also offers a linux-like environment for Windows.

The second method is to download and install Microsoft’s Visual Studio IDE community edition. It comes with Microsoft’s own compilers and is free.

Once Visual Studio is installed, open a developer command prompt and type :

    git clone https://github.com/k0dai/density.git
    cd density\msvc

Build and test :

    msbuild Density.sln
    bin\Release\benchmark.exe -f

An extra recommended step would be to install Clang/LLVM for Windows. It is downloadable from this link. Once installed, open the Visual Studio IDE by double-clicking on Density.sln, then right-click on project names and change the platform toolsets to LLVM. Rebuild the solution to generate binaries with Clang/LLVM.

Output format

DENSITY outputs compressed data in a simple format, which enables file storage and optional parallelization for both compression and decompression.

A very short header holding vital informations (like DENSITY version and algorithm used) precedes the binary compressed data.

APIs

DENSITY features a straightforward API, simple yet powerful enough to keep users’ creativity unleashed.

For advanced developers, it allows use of custom dictionaries and exportation of generated dictionaries after a compression session. Although using the default, blank dictionary is perfectly fine in most cases, setting up your own, tailored dictionaries could somewhat improve compression ratio especially for low sized input datum.

Please see the quick start at the bottom of this page.

About the algorithms

Chameleon ( DENSITY_ALGORITHM_CHAMELEON )

Chameleon is a dictionary lookup based compression algorithm. It is designed for absolute speed and usually reaches a 60% compression ratio on compressible data.
Decompression is just as fast. This algorithm is a great choice when main concern is speed.

Cheetah ( DENSITY_ALGORITHM_CHEETAH )

Cheetah was developed with inputs from Piotr Tarsa.
It is derived from chameleon and uses swapped double dictionary lookups and predictions. It can be extremely good with highly compressible data (ratio reaching 10% or less).
On typical compressible data compression ratio is about 50% or less. It is still extremely fast for both compression and decompression and is a great, efficient all-rounder algorithm.

Lion ( DENSITY_ALGORITHM_LION )

Lion is a multiform compression algorithm derived from cheetah. It goes further in the areas of dynamic adaptation and fine-grained analysis.
It uses multiple swapped dictionary lookups and predictions, and forms rank entropy coding.
Lion provides the best compression ratio of all three algorithms under any circumstance, and is still very fast.

Quick start (a simple example using the API)

Using DENSITY in your application couldn’t be any simpler.

First you need to include this file in your project :

density_api.h

When this is done you can start using the DENSITY API :

    #include <string.h>
    #include "density_api.h"

    char* text = "This is a simple example on how to use the simple Density API.  This is a simple example on how to use the simple Density API.";
    uint64_t text_length = (uint64_t)strlen(text);

    // Determine safe buffer sizes
    uint_fast64_t compress_safe_size = density_compress_safe_size(text_length);
    uint_fast64_t decompress_safe_size = density_decompress_safe_size(text_length);

    // Allocate required memory
    uint8_t *outCompressed   = malloc(compress_safe_size * sizeof(char));
    uint8_t *outDecompressed = malloc(decompress_safe_size * sizeof(char));
    density_processing_result result;

    // Compress
    result = density_compress(text, text_length, outCompressed, compress_safe_size, DENSITY_ALGORITHM_CHAMELEON);
    if(!result.state)
        printf("Compressed %llu bytes to %llu bytes\n", result.bytesRead, result.bytesWritten);

    // Decompress
    result = density_decompress(outCompressed, result.bytesWritten, outDecompressed, decompress_safe_size);
    if(!result.state)
        printf("Decompressed %llu bytes to %llu bytes\n", result.bytesRead, result.bytesWritten);

    // Free memory_allocated
    free(outCompressed);
    free(outDecompressed);

And that’s it ! We’ve done a compression/decompression round trip with a few lines !

Related projects

SHARC (archiver using density algorithms) https://github.com/gpnuma/sharc
fsbench-density (in-memory transformations benchmark) https://github.com/gpnuma/fsbench-density
densityxx (c++ port of density) https://github.com/charlesw1234/densityxx