Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
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?
I can't code well in C, so I created my simple program in Python can these speeds only be available in C?
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.
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.
There are actually two questions that can be answered:
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.
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.
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.
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, 2022 at 21:52
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.
psadbwcan 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;pcmpeqbis a[i] == b[i] for 16 bytes may be useful to find a candidate start point) $\endgroup$