Swiftpack.co - facebook/zstd as Swift Package

Swiftpack.co is a collection of thousands of indexed Swift packages. Search packages.
See all packages published by facebook.
facebook/zstd zstd-0.4.2
Zstandard - Fast real-time compression algorithm
⭐️ 16,207
🕓 1 week ago
iOS macOS tvOS
.package(url: "https://github.com/facebook/zstd.git", from: "zstd-0.4.2")

Zstandard

Zstandard, or zstd as short version, is a fast lossless compression algorithm, targeting real-time compression scenarios at zlib-level and better compression ratios. It's backed by a very fast entropy stage, provided by Huff0 and FSE library.

Zstandard's format is stable and documented in RFC8878. Multiple independent implementations are already available. This repository represents the reference implementation, provided as an open-source dual BSD and GPLv2 licensed C library, and a command line utility producing and decoding .zst, .gz, .xz and .lz4 files. Should your project require another programming language, a list of known ports and bindings is provided on Zstandard homepage.

Development branch status:

Build Status Build status Build status Build status Fuzzing Status

Benchmarks

For reference, several fast compression algorithms were tested and compared on a desktop running Ubuntu 20.04 (Linux 5.11.0-41-generic), with a Core i7-9700K CPU @ 4.9GHz, using lzbench, an open-source in-memory benchmark by @inikep compiled with gcc 9.3.0, on the Silesia compression corpus.

Compressor name Ratio Compression Decompress.
zstd 1.5.1 -1 2.887 530 MB/s 1700 MB/s
zlib 1.2.11 -1 2.743 95 MB/s 400 MB/s
brotli 1.0.9 -0 2.702 395 MB/s 450 MB/s
zstd 1.5.1 --fast=1 2.437 600 MB/s 2150 MB/s
zstd 1.5.1 --fast=3 2.239 670 MB/s 2250 MB/s
quicklz 1.5.0 -1 2.238 540 MB/s 760 MB/s
zstd 1.5.1 --fast=4 2.148 710 MB/s 2300 MB/s
lzo1x 2.10 -1 2.106 660 MB/s 845 MB/s
lz4 1.9.3 2.101 740 MB/s 4500 MB/s
lzf 3.6 -1 2.077 410 MB/s 830 MB/s
snappy 1.1.9 2.073 550 MB/s 1750 MB/s

The negative compression levels, specified with --fast=#, offer faster compression and decompression speed at the cost of compression ratio (compared to level 1).

Zstd can also offer stronger compression ratios at the cost of compression speed. Speed vs Compression trade-off is configurable by small increments. Decompression speed is preserved and remains roughly the same at all settings, a property shared by most LZ compression algorithms, such as zlib or lzma.

The following tests were run on a server running Linux Debian (Linux version 4.14.0-3-amd64) with a Core i7-6700K CPU @ 4.0GHz, using lzbench, an open-source in-memory benchmark by @inikep compiled with gcc 7.3.0, on the Silesia compression corpus.

Compression Speed vs Ratio Decompression Speed
Compression Speed vs Ratio Decompression Speed

A few other algorithms can produce higher compression ratios at slower speeds, falling outside of the graph. For a larger picture including slow modes, click on this link.

The case for Small Data compression

Previous charts provide results applicable to typical file and stream scenarios (several MB). Small data comes with different perspectives.

The smaller the amount of data to compress, the more difficult it is to compress. This problem is common to all compression algorithms, and reason is, compression algorithms learn from past data how to compress future data. But at the beginning of a new data set, there is no "past" to build upon.

To solve this situation, Zstd offers a training mode, which can be used to tune the algorithm for a selected type of data. Training Zstandard is achieved by providing it with a few samples (one file per sample). The result of this training is stored in a file called "dictionary", which must be loaded before compression and decompression. Using this dictionary, the compression ratio achievable on small data improves dramatically.

The following example uses the github-users sample set, created from github public API. It consists of roughly 10K records weighing about 1KB each.

Compression Ratio Compression Speed Decompression Speed
Compression Ratio Compression Speed Decompression Speed

These compression gains are achieved while simultaneously providing faster compression and decompression speeds.

Training works if there is some correlation in a family of small data samples. The more data-specific a dictionary is, the more efficient it is (there is no universal dictionary). Hence, deploying one dictionary per type of data will provide the greatest benefits. Dictionary gains are mostly effective in the first few KB. Then, the compression algorithm will gradually use previously decoded content to better compress the rest of the file.

Dictionary compression How To:

  1. Create the dictionary

    zstd --train FullPathToTrainingSet/* -o dictionaryName

  2. Compress with dictionary

    zstd -D dictionaryName FILE

  3. Decompress with dictionary

    zstd -D dictionaryName --decompress FILE.zst

Build instructions

Makefile

If your system is compatible with standard make (or gmake), invoking make in root directory will generate zstd cli in root directory.

Other available options include:

  • make install : create and install zstd cli, library and man pages
  • make check : create and run zstd, tests its behavior on local platform

cmake

A cmake project generator is provided within build/cmake. It can generate Makefiles or other build scripts to create zstd binary, and libzstd dynamic and static libraries.

By default, CMAKE_BUILD_TYPE is set to Release.

Meson

A Meson project is provided within build/meson. Follow build instructions in that directory.

You can also take a look at .travis.yml file for an example about how Meson is used to build this project.

Note that default build type is release.

VCPKG

You can build and install zstd vcpkg dependency manager:

git clone https://github.com/Microsoft/vcpkg.git
cd vcpkg
./bootstrap-vcpkg.sh
./vcpkg integrate install
./vcpkg install zstd

The zstd port in vcpkg is kept up to date by Microsoft team members and community contributors. If the version is out of date, please create an issue or pull request on the vcpkg repository.

Visual Studio (Windows)

Going into build directory, you will find additional possibilities:

  • Projects for Visual Studio 2005, 2008 and 2010.
    • VS2010 project is compatible with VS2012, VS2013, VS2015 and VS2017.
  • Automated build scripts for Visual compiler by @KrzysFR, in build/VS_scripts, which will build zstd cli and libzstd library without any need to open Visual Studio solution.

Buck

You can build the zstd binary via buck by executing: buck build programs:zstd from the root of the repo. The output binary will be in buck-out/gen/programs/.

Testing

You can run quick local smoke tests by executing the playTest.sh script from the src/tests directory. Two env variables $ZSTD_BIN and $DATAGEN_BIN are needed for the test script to locate the zstd and datagen binary. For information on CI testing, please refer to TESTING.md

Status

Zstandard is currently deployed within Facebook. It is used continuously to compress large amounts of data in multiple formats and use cases. Zstandard is considered safe for production environments.

License

Zstandard is dual-licensed under BSD and GPLv2.

Contributing

The dev branch is the one where all contributions are merged before reaching release. If you plan to propose a patch, please commit into the dev branch, or its own feature branch. Direct commit to release are not permitted. For more information, please read CONTRIBUTING.

GitHub

link
Stars: 16208
Last commit: 1 hour ago
jonrohan Something's broken? Yell at me @ptrpavlik. Praise and feedback (and money) is also welcome.

Related Packages

Release Notes

Zstandard v1.5.1
3 weeks ago

Notice : it has been brought to our attention that the v1.5.1 library might be built with an executable stack on non-x64 architectures, which could end up being flagged as problematic by some systems with thorough security settings which disallow executable stack. We are currently reviewing the issue. Be aware of it if you build libzstd for non-x64 architecture.

Zstandard v1.5.1 is a maintenance release, bringing a good number of small refinements to the project. It also offers a welcome crop of performance improvements, as detailed below.

Performance Improvements

Speed improvements for fast compression (levels 1–4)

PRs #2749, #2774, and #2921 refactor single-segment compression for ZSTD_fast and ZSTD_dfast, which back compression levels 1 through 4 (as well as the negative compression levels). Speedups in the ~3-5% range are observed. In addition, the compression ratio of ZSTD_dfast (levels 3 and 4) is slightly improved.

Rebalanced middle compression levels

v1.5.0 introduced major speed improvements for mid-level compression (from 5 to 12), while preserving roughly similar compression ratio. As a consequence, the speed scale became tilted towards faster speed. Unfortunately, the difference between successive levels was no longer regular, and there is a large performance gap just after the impacted range, between levels 12 and 13.

v1.5.1 tries to rebalance parameters so that compression levels can be roughly associated to their former speed budget. Consequently, v1.5.1 mid compression levels feature speeds closer to former v1.4.9 (though still sensibly faster) and receive in exchange an improved compression ratio, as shown in below graph.

comparing v1.4.9 vs v1.5.0 vs 1.5.1on x64 (i7-9700k)

comparing v1.4.9 vs v1.5.0 vs 1.5.1 on arm64 (snapdragon 855)

Note that, since middle levels only experience a rebalancing, save some special cases, no significant performance differences between versions v1.5.0 and v1.5.1 should be expected: levels merely occupy different positions on the same curve. The situation is a bit different for fast levels (1-4), for which v1.5.1 delivers a small but consistent performance benefit on all platforms, as described in previous paragraph.

Huffman Improvements

Our Huffman code was significantly revamped in this release. Both encoding and decoding speed were improved. Additionally, encoding speed for small inputs was improved even further. Speed is measured on the Silesia corpus by compressing with level 1 and extracting the literals left over after compression. Then compressing and decompressing the literals from each block. Measurements are done on an Intel i9-9900K @ 3.6 GHz.

Compiler Scenario v1.5.0 Speed v1.5.1 Speed Delta
gcc-11 Literal compression - 128KB block 748 MB/s 927 MB/s +23.9%
clang-13 Literal compression - 128KB block 810 MB/s 927 MB/s +14.4%
gcc-11 Literal compression - 4KB block 223 MB/s 321 MB/s +44.0%
clang-13 Literal compression - 4KB block 224 MB/s 310 MB/s +38.2%
gcc-11 Literal decompression - 128KB block 1164 MB/s 1500 MB/s +28.8%
clang-13 Literal decompression - 128KB block 1006 MB/s 1504 MB/s +49.5%

Overall impact on (de)compression speed depends on the compressibility of the data. Compression speed improves from 1-4%, and decompression speed improves from 5-15%.

PR #2722 implements the Huffman decoder in assembly for x86-64 with BMI2 enabled. We detect BMI2 support at runtime, so this speedup applies to all x86-64 builds running on CPUs that support BMI2. This improves Huffman decoding speed by about 40%, depending on the scenario. PR #2733 improves Huffman encoding speed by 10% for clang and 20% for gcc. PR #2732 drastically speeds up the HUF_sort() function, which speeds up Huffman tree building for compression. This is a significant speed boost for small inputs, measuring in at a 40% improvement for 4K inputs.

Binary Size and Build Speed

zstd binary size grew significantly in v1.5.0 due to the new code added for middle compression level speed optimizations. In this release we recover the binary size, and in the process also significantly speed up builds, especially with sanitizers enabled.

Measured on x86-64 compiled with -O3 we measure libzstd.a size. We regained 161 KB of binary size on gcc, and 293 KB of binary size on clang. Note that these binary sizes are listed for the whole library, optimized for speed over size. The decoder only, with size saving options enabled, and compiled with -Os or -Oz can be much smaller.

Version gcc-11 size clang-13 size
v1.5.1 1177 KB 1167 KB
v1.5.0 1338 KB 1460 KB
v1.4.9 1137 KB 1151 KB

Change log

Featured user-visible changes

  • perf: rebalanced compression levels, to better match intended speed/level curve, by @senhuang42 and @cyan4973
  • perf: faster huffman decoder, using x64 assembly, by @terrelln
  • perf: slightly faster high speed modes (strategies fast & dfast), by @felixhandte
  • perf: smaller binary size and faster compilation times, by @terrelln and @nolange
  • perf: new row64 mode, used notably at highest lazy2 levels 11-12, by @senhuang42
  • perf: faster mid-level compression speed in presence of highly repetitive patterns, by @senhuang42
  • perf: minor compression ratio improvements for small data at high levels, by @cyan4973
  • perf: reduced stack usage (mostly useful for Linux Kernel), by @terrelln
  • perf: faster compression speed on incompressible data, by @bindhvo
  • perf: on-demand reduced ZSTD_DCtx state size, using build macro ZSTD_DECODER_INTERNAL_BUFFER, at a small cost of performance, by @bindhvo
  • build: allows hiding static symbols in the dynamic library, using build macro, by @skitt
  • build: support for m68k (Motorola 68000's), by @cyan4973
  • build: improved AIX support, by @Helflym
  • build: improved meson unofficial build, by @eli-schwartz
  • cli : fix : forward mtime to output file, by @felixhandte
  • cli : custom memory limit when training dictionary (#2925), by @embg
  • cli : report advanced parameters information when compressing in very verbose mode (-vv), by @Svetlitski-FB
  • cli : advanced commands in the form --long-param= can accept negative value arguments, by @binhdvo

PR full list

New Contributors

Full Changelog: https://github.com/facebook/zstd/compare/v1.5.0...v1.5.1

Swiftpack is being maintained by Petr Pavlik | @ptrpavlik | @swiftpackco | API | Analytics