LZ77 Performance Issues

[david_werecat]

Hello, I'm new here. I came to this forum because I have a general interest in data compression.

I have written code for several simple compression algorithms, and most of them are working correctly. However, the performance for the LZ77 based code is very poor. I use a ring buffer for IO buffering and store the offset to the next byte of the same value in the buffer, so that not every position in the window is checked for a match. It currently runs at about 100 kb/s for a 1kb window on a 2ghz computer. I was wondering if anyone had any suggestions to improve the performance of the algorithm. Thanks to everyone in advance.



Also, I created a fast preprocessor for entropy coders. It runs at over 100 mb/s and has moderate gains on compression ratio. Here are some benchmarks:

enwik8 100,000,000 bytes
enwik8 -> Huff0 -> output 63,081,072 bytes
enwik8 -> PrePred -> Huff0 -> output 50,986,908 bytes

7z.dll 1,478,656 bytes
7z.dll -> Huff0 -> output 1,059,865 bytes
7z.dll -> PrePred -> Huff0 -> output 892,123 bytes

[Bulat Ziganshin]

i suggest you to start with the same thing as eugene roshal or igor pavlov started m,any years ago - download and learn zlib sources. lz77 part is in deflate.c and it's greatly documented

[david_werecat]

Thanks! I'll look into that.

[Sesse]

I use a ring buffer for IO buffering and store the offset to the next byte of the same value in the buffer, so that not every position in the window is checked for a match. It currently runs at about 100 kb/s for a 1kb window on a 2ghz computer. I was wondering if anyone had any suggestions to improve the performance of the algorithm. Thanks to everyone in advance.

First of all, I'd run a profiler over your code ? it sounds like your match checking is what's taking up time, but it's always hard to say without a profiler.

FWIW, the usual way of speeding up match finding is storing not just a pointer to the previous _byte_ with the same value, but the previous 3 or 4 bytes (or whatever is your minimum match length). This is typically done using a hash table, and then just ignoring any results you get that are outside your window.

/* Steinar */

[david_werecat]

Thanks! That should give a large efficiency increase. I'm still trying to work with the zlib source code, but this is probably easier to implement.