TurboRLE-Fastest Run Length Encoding

Related tags

Compilers c java c-plus-plus benchmark rle sse simd avx2 run-length-encoding sse2
Overview

TurboRLE: Turbo Run Length Encoding Build Status

Efficient and fastest Run Length Encoding library

  • 🆕 The fastest now up to 50% more faster incl. SSE/AVX2 + improved compression

  • 🆕 ARM NEON support

  • 100% C (C++ compatible headers), without inline assembly

  • Most efficient compression

  • No other RLE compress or decompress faster with better compression

  • ✨ faster compression and 2x faster decompression with 👍 SIMD

  • 👍 Java Critical Natives Interface. Access TurboRLE incl. SIMD! from Java

  • Compress better and up to 12 times faster and decompress up to 6 times faster than other fast RLEs

  • Can be faster than memcpy!

  • 👍 ZERO! byte overhead

  • No modification of the raw data, preserving compressibility for further postprocessing (ex. entropy coding)

  • Order preserving

TurboRLE
  • TRLE: TurboRLE - Efficient and fast Run Length Encoding
  • SRLE: TurboRLE Escape - Fast Run Length Encoding with automatic escape determination

Benchmark:

  • Single thread with TurboBench
  • Realistic and practical benchmark with large files and different distributions
External functions benchmarked
  • MRLE: Mespotine RLE: Run Length Encoding
  • RLE8: A fast 8 bit Run Length Encoding (SSE/AVX2)

CPU: Skylake i7-6700 3.4GHz, gcc 8.3 (2019-08)

(bold = pareto) MB=1.000.000

C Size ratio% C MB/s D MB/s Name / 2019-08
2623680 0.6 2089 11385 trle
4148455 1.0 2095 12521 srle 0 (auto escape)
4482384 1.1 378 12302 mrle
4744806 1.2 11307 13205 srle 8
5901235 1.5 890 11998 rle8 1
8431844 2.1 7368 12693 srle 16
13722311 3.4 11090 13188 srle 32
19839711 4.9 16269 13733 srle 64
403920054 100.0 13978 14001 memcpy
  • Checkers program "End Game Table Base": 1034.db
C Size ratio% C MB/s D MB/s Name / 2019-08
73108990 17.4 774 3020 trle
84671759 20.2 764 5113 srle 0
88055360 21.0 262 1491 mrle
88666372 21.2 456 2669 rle8 1
92369164 22.0 1101 5967 srle 8
113561548 27.1 2028 7114 srle 16
136918311 32.7 3588 9026 srle 32
165547365 39.5 5972 10120 srle 64
419225625 100.0 13938 14017 memcpy
C Size ratio% C MB/s D MB/s Name / 2019-08
375094084 37.5 472 1743 trle
415597104 41.6 461 3563 srle 0
419263924 41.9 568 4310 srle 8
487430623 48.7 1347 6287 srle 16
549202860 54.9 2780 8238 srle 32
576619941 57.7 207 553 mrle
577685250 57.8 260 675 rle8 1
605759578 60.6 5356 9471 srle 64
1000000008 100.0 13931 13926 memcpy

CPU: ARM A73-ODROID-N2 1.8GHz, gcc 8.3 (2019-08)

C Size ratio% C MB/s D MB/s Name / 2019-08
2623680 0.6 594 3399 trle
4148455 1.0 589 3799 srle 0
4482384 1.1 144 3712 mrle
4744806 1.2 3365 3790 srle 8
8431844 2.1 1313 3784 srle 16
13722311 3.4 1771 4573 srle 32
19839711 4.9 4184 6020 srle 64
403920054 100.0 3345 3376 memcpy
C Size ratio% C MB/s D MB/s Name / 2019-08
375094084 37.5 184 722 trle
415597104 41.6 180 681 srle 0
419263924 41.9 244 693 srle 8
487430623 48.7 455 1203 srle 16
549202860 54.9 825 2094 srle 32
576619941 57.7 94 249 mrle
605759578 60.6 1677 3662 srle 64
1000000008 100.0 3830 3841 memcpy
  • Post-processing: Entropy Coding after Run Length Encoding
    Direct entropy encoding after "trle" (no additional "move to front" or other transformation)
C Size ratio% C MB/s D MB/s Name / CPU Skylake 3.4 GHz (2019-06)
180510948 18.1 154 132 trle + TurboRC o0 (order 0 bitwise Range Coder)
187099490 18.7 23 2560 trle + TurboHF 0 (Huffman Coding)
192420471 19.2 1527 3834 trle + TurboANX 12 (Asymmetric Numeral Systems)
193455670 19.3 2192 2986 trle + TurboHF 12
197974078 19.8 1078 1406 trle + fse (Finite State Entropy)
229693376 23.0 126 106 rle8 + TurboRC o0
254312056 25.4 119 105 mrle + TurboRC o0

for more info, see also: Entropy Coding Benchmark

Compile:

	git clone git://github.com/powturbo/Turbo-Run-Length-Encoding.git
    cd Turbo-Run-Length-Encoding
Linux + Windows MingW
	make
    or
	make AVX2=1
Windows Visual C++
	nmake /f makefile.vs
    or
	nmake AVX2=1 /f makefile.vs

Testing Run Length Encoding libraries:

    ./trle file
    ./trle -e# file

	# = function id (see file trle.c)

Environment:

OS/Compiler (32 + 64 bits):
  • Windows: MinGW-w64 makefile
  • Windows: Visual c++ (>=VS2008) - makefile.vs (for nmake)
  • Windows: Visual Studio project file - vs/vs2017
  • Linux amd64: GNU GCC (>=4.6)
  • Linux amd64: Clang (>=3.2)
  • Linux arm64: 64 bits aarch64 ARMv8: gcc (>=6.3)
  • Linux arm64: 64 bits aarch64 ARMv8: clang
  • MaxOS: XCode (>=9)
  • PowerPC ppc64le (incl. SIMD): gcc (>=8.0)

Run Length Encoding References:

Last update: 25 FEB 2020

Comments
  • Copyleft licensing

    Copyleft licensing

    I have noticed that you use GPLv2 in some of your repositories, such as this one. This prevents code reuse in permissively licensed open source projects. I wanted to check if this is your intent, and, if so, if you would be willing to choose a permissive license such as Apache 2.0.

    opened by wesm 3
  • Compress less than 1 byte symbol data

    Compress less than 1 byte symbol data

    Can I compress data with using less than 1 byte per symbol, for example 5bits? I have some image data using only 32 colors - 5 bits per pixel, and so I need to compress it 🔢 :) How can I do that? Or only 1 byte per pixel?

    opened by cevek 2
  • Is there any detail usage for TurboRLE?

    Is there any detail usage for TurboRLE?

    I'm a new guy for TurboRLE, I know something about Run Length Encoding, and I found TurboRLE in Github. I download the src code and make it with gcc.

    My question is there any detail usage for TurboRLE? Is the only function of TurboRLE is "trle.exe filename" ? Can I get a compressed file by trle.exe ? Such as, I have a file "foo.txt", how can I use trle.exe to compress this "foo.txt" to "foo2.txt" ?

    I didn't see any further guide or usage.

    opened by linrongbin16 2
  • Improve const-correctness

    Improve const-correctness

    I suggest to add the key word "const" to the type specifiers for parameters like "in" (function "_srlec8"). Would you like to apply the advices from an article to more places in your source files?

    opened by elfring 2
  • reserved identifier violation

    reserved identifier violation

    I would like to point out that an identifier like "_x__" does eventually not fit to the expected naming convention of the C++ language standard. Would you like to adjust your selection for unique names?

    opened by elfring 2
  • add support for macOS 10.12

    add support for macOS 10.12

    When I built the project the error occurred as follow:

    cc -O3 -march=native -minline-all-stringops trlec.c -c -o trlec.o cc -O3 -march=native -minline-all-stringops trled.c -c -o trled.o cc -O2 -march=native -minline-all-stringops -c trle.c -o trle.o In file included from trle.c:39: ./time_.h:78:9: warning: 'CLOCK_REALTIME' macro redefined [-Wmacro-redefined] #define CLOCK_REALTIME 0 ^ /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.12.sdk/usr/include/time.h:154:9: note: previous definition is here #define CLOCK_REALTIME CLOCK_REALTIME ^ In file included from trle.c:39: ./time.h:79:9: warning: 'CLOCK_MONOTONIC' macro redefined [-Wmacro-redefined] #define CLOCK_MONOTONIC 0 ^ /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.12.sdk/usr/include/time.h:156:9: note: previous definition is here #define CLOCK_MONOTONIC CLOCK_MONOTONIC ^ In file included from trle.c:39: ./time.h:80:5: error: conflicting types for 'clock_gettime' int clock_gettime(int /clk_id/, struct timespec* t) { ^ /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.12.sdk/usr/include/time.h:177:5: note: previous declaration is here int clock_gettime(clockid_t clock_id, struct timespec _tp); ^ In file included from trle.c:39: ./time.h:80:33: error: parameter name omitted int clock_gettime(int /clk_id/, struct timespec t) { ^ ./time.h:90:80: warning: while loop has empty body [-Wempty-body] ...tm_t tminit() { tm_t t0=tmtime(),ts; while((ts = tmtime())==t0); return ts; } ^ ./time.h:90:80: note: put the semicolon on a separate line to silence this warning 3 warnings and 2 errors generated. make: *** [trle.o] Error 1

    Apple has implemented clock_gettime since 10.12 so there is no need to define it .

    And maybe the library lrt is not available on MacOS (It works without -lrt).

    opened by YaoC 0
Owner
powturbo
Turbo Data Compression, InformationRetrieval. InvertedIndex, Integer Compression, InMemoryDB, SIMD, Data Structures, Algorithms, BigData, Databases
powturbo
GitHub
Project #1: Run-length Encoding (Computer Architecture, Fall 2021)

4190.308 Computer Architecture (Fall 2021) Project #1: Run-length Encoding Due: 11:59PM, September 26 (Sunday) Introduction In this project, you need

SNU Systems Software & Architecture Laboratory 8 Dec 13, 2022
COBS framing with implicit run-length-encoding, optimized for data containing statistically a bit more 0 and FF bytes in a row, as data often carry 16, 32 or 64 bit numbers with small values.

TCOBS Table of Contents About The project TCOBS Specification TCOBS code Getting Started 4.1. Prerequisites 4.2. Installation 4.3. Usage in Go 4.3.1.

Thomas Höhenleitner 17 Nov 6, 2022
SimpleBaseLib4CPP is a simple C++11 Base Encoding library that provides at the moment support for encoding and decoding various bases such as Base16, Base32 (various variants), Base58 (various variants), Base64 (various variants).

SimpleBaseLib4CPP SimpleBaseLib4CPP is a simple C++11 Base Encoding library that provides at the moment support for encoding and decoding various base

Telepati 2 Nov 29, 2021
A collection of various algorithms to produce length-limited prefix codes

Introduction This is a collection of various algorithms to produce length-limited prefix codes. My library is written in plain C with tons of comments

Stephan Brumme 15 Nov 7, 2022
Explore building a hash table with two different hash functions that balances chain length

hash-duo Explore building a hash table with two different hash functions that balances chain length. There is a really cool article called Don't Throw

Terence Parr 3 May 7, 2022
C++ class for creating and computing arbitrary-length integers

BigNumber BigNumber is a C++ class that allows for the creation and computation of arbitrary-length integers. The maximum possible length of a BigNumb

Limeoats 143 Dec 14, 2022
C Program to input a string and adjust memory allocation according to the length of the string.

C-String C Program to input a string and adjust memory allocation according to the length of the string. With the help of this program, we have replic

Kunal Kumar Sahoo 1 Jan 20, 2022
The fastest feature-rich C++11/14/17/20 single-header testing framework

master branch Windows All dev branch Windows All doctest is a new C++ testing framework but is by far the fastest both in compile times (by orders of

Viktor Kirilov 4.5k Jan 5, 2023
Jsmn is a world fastest JSON parser/tokenizer. This is the official repo replacing the old one at Bitbucket

JSMN jsmn (pronounced like 'jasmine') is a minimalistic JSON parser in C. It can be easily integrated into resource-limited or embedded projects. You

Serge Zaitsev 3.2k Jan 9, 2023
Fastest Integer Compression

TurboPFor: Fastest Integer Compression TurboPFor: The new synonym for "integer compression" ?? (2019.11) ALL functions now available for 64 bits ARMv8

powturbo 647 Dec 26, 2022
The fastest feature-rich C++11/14/17/20 single-header testing framework

master branch Windows All dev branch Windows All doctest is a new C++ testing framework but is by far the fastest both in compile times (by orders of

Viktor Kirilov 4.5k Jan 4, 2023
hashcat is the world's fastest and most advanced password recovery utility

hashcat is the world's fastest and most advanced password recovery utility, supporting five unique modes of attack for over 300 highly-optimized hashing algorithms. hashcat currently supports CPUs, GPUs, and other hardware accelerators on Linux, Windows, and macOS, and has facilities to help enable distributed password cracking.

null 16.3k Dec 30, 2022
Python bindings for Wasm3, the fastest WebAssembly interpreter

pywasm3 Python bindings for Wasm3, the fastest WebAssembly interpreter Main repository: Wasm3 project Install # Latest release: pip3 install pywasm3

Wasm3 Labs 49 Dec 27, 2022
A local DNS server to obtain the fastest website IP for the best Internet experience

A local DNS server to obtain the fastest website IP for the best Internet experience

Nick Peng 5.7k Jan 4, 2023
Typesafe, Generic & Fastest Set Data structure implementation in C

Typesafe & Fast as fuck Set in C Key Features Extremely fast non-cryptographic hash algorithm XXHash Complete Typesafe APIs Double Hashing to avoid bo

Robus Gauli 4 Sep 6, 2021
LAppS - Lua Application Server for micro-services with default communication over WebSockets. The fastest and most vertically scalable WebSockets server implementation ever. Low latency C++ <-> Lua stack roundtrip.

LAppS - Lua Application Server This is an attempt to provide very easy to use Lua Application Server working over WebSockets protocol (RFC 6455). LApp

null 48 Oct 13, 2022
The fastest database-library on Android OS.

Android SQLite3 NDK 封装 Demo下载 （操作：按钮新增 按钮查询 点按编辑 长按删除） 写在前面 sqlite3 开源、集成简单（现在的版本只有2个文件 sqlite3.h sqlite3.c） 这个库抽离自 Telegram 的开源代码、作者：DrKLO 我个人感觉 Tele

水银灯、 2 Dec 27, 2021
Elofetch - The fastest neofetch ever made

Elofetch Elofetch - The fastest neofetch ever made Elofetch is a fast program written in C. Like neofetch, this program will show you software and har

ProX 6 Nov 20, 2022
Fastest-lap is an optimal laptime simulator, written in C++, and with a python API.

Fastest-lap ?? ?? Fastest-lap is an optimal laptime simulator, written in C++, and with a python API. What can be done Numerical G-G diagram: given a

Juan Manzanero 390 Jan 2, 2023
React-native-quick-sqlite - ⚡️ The fastest SQLite implementation for react-native.

React Native Quick SQLite The **fastest** SQLite implementation for react-native. Copy typeORM patch-package from example dir npm i react-nati

Oscar Franco 423 Dec 30, 2022