11
$\begingroup$

I've come across compression algorithms, I tried creating a simple run-length encoding algorithm but I notice that when I searched other algorithms I was shocked to know that some algorithms can process thousands of megabits per second how is this possible? I tried compressing a 1GB length text it was taking some time for me.

How do is this achievable? or am I missing something here?

compression image

I can't code well in C, so I created my simple program in Python can these speeds only be available in C?

$\endgroup$
7
  • 14
    $\begingroup$ From the tour it says "Computational Science is a question and answer site for questions and answers about computational methods used in technical disciplines". Given compression is important for use in handling the large datasets required in a number of disciplines, I don't see why this is OT here. $\endgroup$
    – Ian Bush
    Aug 15 at 13:36
  • 10
    $\begingroup$ @Federico: Computational Science is not just numerical. $\endgroup$
    – Richard
    Aug 15 at 20:16
  • 2
    $\begingroup$ This is just something I was told once, so take it with a grain of salt, but I believe the computationally intensive parts of some of the common encryption and compression algorithms are implemented in hardware, which gives them a massive speedup. $\endgroup$
    – craq
    Aug 16 at 7:27
  • 9
    $\begingroup$ There is basically no chance python code will ever compete with well-written C code, even with pypy JIT compilation. And data compression happens to be one of those low-level byte manipulation tasks very well suited for C. $\endgroup$
    – qwr
    Aug 16 at 7:36
  • 4
    $\begingroup$ @craq: Encryption yes, for example x86 CPUs since Nehalem have had AES hardware support which makes quite a big difference. Compression no. There aren't any x86 instructions that specifically accelerate lossless compression. (Maybe you're thinking of lossy video compression, where SIMD instructions like psadbw can accelerate motion-search for similar blocks, giving sum-of-absolute-differences for 2x 8-byte chunks at a time, i.e. rows of two 8x8 blocks. But lossless compression only wants exact matches; pcmpeqb is a[i] == b[i] for 16 bytes may be useful to find a candidate start point) $\endgroup$ Aug 16 at 21:40

5 Answers 5

27
$\begingroup$

The short answer to your question is this:

If your goal is speed (as it is in typical applications of data compression), then (i) you need to choose a programming language that allows you to write algorithms close to the hardware, and (ii) you will spend a very large amount of time benchmarking and profiling your software to find where it is slow, and then fix these places by using better algorithms and better ways of implementing these algorithms.

The authors of the compression packages you mention have not chosen to use magic to achieve the speed shown in the table. They have just put a large effort (probably years of work) into making their software fast.

$\endgroup$
6
  • 10
    $\begingroup$ Also, with typical well-engineered packages there is almost always a trade-off available between compression efficiency and time taken. That is, they nearly always allow taking more time and getting more compressed results. $\endgroup$ Aug 16 at 4:03
  • 6
    $\begingroup$ Computers are really, really fast today but you have to make an effort to use all of that speed, especially to use multiple CPU cores. I suppose a naive Python program will only use a single CPU core. $\endgroup$
    – idspispopd
    Aug 16 at 7:11
  • 3
    $\begingroup$ @idspispopd yes and you have to fight a battle with the GIL for multithreaded performance $\endgroup$
    – qwr
    Aug 16 at 7:38
  • 1
    $\begingroup$ @idspispopd You also have to choose an algorithm that can take advantage of parallelism. E.g. split your data into chunks and compress them separately on different cores. This might be a tradeoff between speed and best compression ratio. $\endgroup$
    – Barmar
    Aug 16 at 13:42
  • 3
    $\begingroup$ "The authors of the compression packages you mention have not chosen to use magic" - This is the problem with wizards moonlighting as developers. They like to do stuff the hard way, depriving us of faster compression libraries. $\endgroup$ Aug 18 at 4:09
11
$\begingroup$

I have written compression software in Rust. The answer is not simple, but compression algorithms are usually designed to be reasonably quick. RFC 1951 has two steps, the first stage is to find patterns that occurred earlier in the input, which can be compressed as a pointer to the earlier pattern. This is generally done using a hash lookup.

The second stage is to use Huffman encoding to efficiently represent the values needed for the encoding, using variable (bit) length codes. Values which occur frequently use shorter codes, less frequent values use longer codes.

My software is probably a bit unusual in that it runs the two stages in parallel, which can be faster if your computer has more than one CPU.

There tend to be trade-offs between how much compression is achieved and how fast the compression runs. Finally, the answer is partly that modern computers are very fast.

$\endgroup$
1
  • $\begingroup$ Very fast and if the software makes use of threading it just get's even faster. Modern computer speeds are absolutely insane, only surpassed by some applications ability to still respond slowly $\endgroup$
    – Hobbamok
    Aug 19 at 8:32
7
$\begingroup$

There are actually two questions that can be answered:

Why is decompression so much faster than compression?

The key point to understand here is, that compression typically involves searching for matching byte sequences, while the compressed format is basically an extremely dense format for instructions on how to create the original byte stream. I.e. while decompression simply means decoding and following the instructions in the compressed file, one step at a time, compression usually means considering many alternatives and selecting one that leads to the smallest amount of required instructions for reconstruction.

A simple corollary of this is, that decompression throughput is significantly higher for highly compressed data (less instructions to decode) than for virtually incompressible data.

Why are the standard tools so much faster on doing compression than a naive implementation?

Now that we know that it is the searching for matching byte sequences that consumes most time in a naive compressor implementation, it is clear how the compressors can be optimized: They achieve their speed by aggressively avoiding searching and considering alternatives. Key part of this is typically some form of hash table, or other quick lookup data structure that allows finding matching sequences rather quickly. And then those standard tools employ heuristics for looking up good matches rather than just matches, allowing them to cut down on the number of matches they will consider before committing to using one of them. One of these heuristics can be that a match is selected when it is "good enough", whatever that means, and that the search continues for longer when the considered matches do not meet this criterion.

As with decompression, each "instruction" in the compressed format requires the compressor to find a (good) match. As such, compression is also fastest for highly compressible data as fewer matches need to be found. Also quite a visible effect when benchmarking compression algorithms.

$\endgroup$
1
  • $\begingroup$ An example of this can be find in the description of xz --extreme option: «Use a slower variant of the selected compression preset level to hopefully get a little bit better compression ratio, but with bad luck this can also make it worse.» You use different algorithms, but there is no certainty you will find the best compression (or even a better one than with the standard options). $\endgroup$
    – Ángel
    Aug 18 at 23:14
1
$\begingroup$

In low-level languages, for example C or C++, your code will be directly translated to machine instructions. And then you find that a modern processor can perform a few billion machine instructions per second. Take a statement x = y << (64 - n); which could be translated to (assuming x, y and n are in registers)

move 64 to register tmp
subtract register n from register tmp
move y to register x
shift register x to the left by (register tmp) bits

That will happen in two processor cycles, so at say 3 GHz it can be performed 1.5 billion times per second. That's the kind of speed you can get if you use a low-level language. zstd for example runs at 136MB/sec according to your table; at three GHz that is 22 cycles per byte. Probably 44 machine instructions per byte.

And then you can use vector instructions, which can operate say on 16 bytes at a time, and you could use multiple cores; I assume that lz4 uses that. And the programmer tries out many possible ways to write their code to find the one that runs fastest; they may even have different code for different processors.

Python on the other hand doesn't even know that these variables x, y and n are integers. And that they are small integers. It has to do a lot of work before it can even start to perform one of these instructions.

$\endgroup$
0
$\begingroup$

I can't code well in C, so I created my simple program in Python can these speeds only be available in C?

Yes.

C and possibly C++ are two of the few that are about as close to hardware as most programmers are able to get. (assembly language is not very cross-platform) Aggressively processing hundreds, thousands, millions, billions, or more of iterations to convert one long bitstream to a smaller bitstream is right at home there.

These things are also tuned every way to Sunday to figure out WHAT they are trying to compress. Is it text, audio (and what format?), video (again what format? mp4, vp6, something decades older. what wrapper? avi, mkv, ogg), microsoft documents, and then there are files that are all of these bundled into a tar (or similar) archive that the user did you the service of not having gzipped the archive to make it harder for you to "squeeze juice" out of? If you are not using metal, or close to metal, something slow like python will suffer no matter how well you tune it.

On the other hand, Python is not that. It is designed for little, short tasks where it doesn't really matter if they are done inefficiently, because they are (relatively) rare. Where with C or C++, finding some little thing on some webpage (oh, and you have to write how to find the thing... and it might miss) to populate a part of a table (oops, the thing is totally too wide for that column because it wasn't the proper hit), all of these difficulties are handled already... with the deal with the devil being speed. For little one-off tasks, speed isn't critical. Millions or trillions of iterations, it will choke.

Then, even if python could "speed itself up" by summoning the functions of the more hardware-centric protocols/methods, it would probably be doing so inefficiently. It would gain on the sub-task, but lose on calling and returning from the sub-task, with maybe a marginal net gain. Then also the "misdiagnosis" where an audio block is requested to be treated as a video block because python misdiagnosed it.

Sorry if this is a bit long-winded.

$\endgroup$
8
  • 3
    $\begingroup$ For the most performance-critical parts of performance-critical libraries such as compression libraries, assembly is sometimes chosen. (The rest is still written in C or something similar, to avoid uniformly slow Python code) $\endgroup$
    – user253751
    Aug 16 at 17:22
  • 4
    $\begingroup$ C, C++, Rust, and Julia and others compile to native code with good ahead-of-time compilers (like GCC or LLVM optimizers) and would be suitable for this. Many other languages come very close, having fairly good optimizing JITs, like C# and Java. Even JavaScript has good JITs, but to work with binary data I assume you'd have to be careful what types you used. Python is extremely slow compared to most languages for manual looping over elements of arrays, with the standard implementation being a pure interpreter. $\endgroup$ Aug 16 at 21:46
  • 2
    $\begingroup$ e.g. a naive C program might be close to optimal with optimization enabled, or might be missing out on a factor of 10 or more if manual SIMD vectorization is possible, and/or if better algorithms are possible. But a Python version of the same C program might be 200x slower than the naive C. Not remotely in the same ballpark for looking at bytes 1 at a time. So there's plenty of room to be close to C and way faster than Python. $\endgroup$ Aug 16 at 21:47
  • 4
    $\begingroup$ Lossless compressors don't generally try to figure out what the content is. e.g. zstd won't detect that it's video and call libx264 functions in lossless mode, even though that could potentially save more bits if your input was uncompressed video data. But if your input was already MP4 with h.264 video, recompressing it isn't going to save anything if you need a bit-exact reconstruction of the MP4 file. Also note the question talks about implementing a simple RLE algorithm, run-length encoding. That can be done even faster than lz4, esp. the compression part since there's no search $\endgroup$ Aug 16 at 21:52
  • 1
    $\begingroup$ I don't think it's accurate to say compressors are tuned to figure out what they are trying to compress. Or what "misdiagnosis" means in your answer. If a program does this (I'm not aware of any of the usual tools that bother detecting media type) it's usually very simple or known a priori what media type is being worked on. $\endgroup$
    – qwr
    Aug 17 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.