CRUSH 0.01 is here!

[encode]

Hi all!

Please welcome the CRUSH - my new LZ77 encoder designed for extremely fast decompression, while maintaining a good compression ratio.

Check out the LTCB results:

No code has to be inserted here.

Decompressing ENWIK9 within 3 secs?!

System specs:
Windows 7 Ultimate SP1
Intel Core i7-2600 @ 3.4 GHz
Kingston 8GB DDR3
WD VelociRaptor 10000RPM 600GB SATA3

As you can see, the CRUSH has three compression modes:

Fast:

crush cf enwik8 enwik8.cru

Designed for fast compression

Normal:

crush c enwik8 enwik8.cru

Designed for good balance between compression ratio and speed

Max:

crush cx enwik8 enwik8.cru

Designed for maximum compression!



I hope you'll enjoy my new program!

EDIT: Uploaded a Linux compile. Note, this one is slower than Windows compile!

[m^2]

X-Firefox 4 directory:
No code has to be inserted here.

[Matt Mahoney]

Tested.
http://mattmahoney.net/dc/text.html#2873
http://mattmahoney.net/dc/uiq/

[encode]

Thanks a lot!

[Cyan]

Wow, LZMH looks like a very strong contender in this category too.
Just out of curiosity, would you mind probing how ZhuffMax could compare with these compressors, from a decompression perspective, please ?

Rgds

[encode]

As a note, the decompression speed of CRUSH also depends on data type. And it's not that fair actually to compare LZOP and LZ4HC ("High Compression"), since ENWIK9 results are:

LZ4HC -> 392,102,544 bytes
LZOP -> 366,349,786 bytes
CRUSH -> 287,333,602 bytes

CRUSH is from different opera. Otherwise, you may add the LZMA to comparison.

BTW, where I can get LZMH?

[Surfer]

BTW, where I can get LZMH?

http://encode.su/threads/1117-LZHAM?...ll=1#post22513

[m^2]

Wow, LZMH looks like a very strong contender in this category too.
Just out of curiosity, would you mind probing how ZhuffMax could compare with these compressors, from a decompression perspective, please ?

Rgds

Sure.
No code has to be inserted here.
Honestly, I have no idea what's up with LZMH.
It's usually a clear leader in my tests, but that's just crazy.

[m^2]

I decided to do another test. 1/3 of file size is text.
ffmpeg.
No code has to be inserted here.

Note: in both tests all files got the data tarred, so LZMH probably doesn't use it's exe filters.

[Cyan]

Thanks for the tests.
Indeed, LZMH results are unexpectedly strong in this area.
That's very insteresting, because it provides a useful comparison point.

What kind of tool are you using to measure decompression time ? Something like Igor's timer program ?

Regards

[m^2]

Exactly Igor's timer.
I used user times for this thread.

[encode]

I decided to make CRUSH an Open Source project (Public Domain at SourceForge) Will do some optimizations and code changes (larger dictionary?) to make source portable and system independent.

[Matt Mahoney]

Glad to hear it. Now I can add it to the Silesia benchmark.

[m^2]

Thumbs up, Encode!
I longed to add it to my benchmark too.

[encode]

Just uploaded an original source from 2011, "AS-IS". So, please consider it as a "DRAFT".



I need to put some work on it.

Anyway, please check out the source and post your comments & suggestions!

[encode]

CRUSH with different window sizes (Default is 1M)

ENWIK9:
No code has to be inserted here.

ENWIK8:
No code has to be inserted here.

dickens:
No code has to be inserted here.

The decompression is equally fast; with cf/c modes CRUSH is fast enough with any window size. ex mode is for max compression anyway!

[m^2]

Here we go:
* porting to FreeBSD (only to make it run) has been easy, I guess that since you made a ubuntu binary, you did everything already.
* the code is nearly C-compatible. What do you think about switching language? It would make crush more portable.
* bit I/O...hmm...not a top performer and I don't immediately see a way to improve it. Still, crush used to be competitive.
* Would be good to have access to the latest sources. You did some porting already and published a binary, I'm interesting in what did you change.
* I need to convert crush to a library. Would you be willing to accept the patches in your trunk?
* It looks quite good for a draft.
* I'm positively surprised by memory usage.
* Overall, I'm pretty excited about it.

[encode]

• (sizeof(int) == 4) with most 32 and 64-bit compilers (except of an old 16-bit DOS stuff). I might change it to int32_t eventually. Anyway, I'm a Visual C++ guy
• C++ gives me more freedom in some cases
• As to library, I already added a Crush namespace: Crush::Src=xxx; Crush::Dst=yyy; Crush::Compress(0);
• I might enlarge the default window size to 2 MB

[encode]

BTW, I'll never try to keep source to be compiled with any compiler on any platform with no warnings at all - it's not really possible. Or else, CRUSH source will look like LZOP - completely unreadable...

[m^2]

(sizeof(int) == 4) with most 32 and 64-bit compilers (except of an old 16-bit DOS stuff). I might change it to int32_t eventually. Anyway, I'm a Visual C++ guy

Ah, I've mistaken it with long, you're right.

C++ gives me more freedom in some cases

OK. It's just that the published code didn't really use it.

As to library, I already added a Crush namespace: Crush::Src=xxx; Crush:st=yyy; Crush::Compress(0);

I suggest making it an object, so it can be thread-safe.

I might enlarge the default window size to 2 MB

What do you think about making it a runtime variable? Or, if it makes compiler optimise less, a template?

BTW, I'll never try to keep source to be compiled with any compiler on any platform with no warnings at all - it's not really possible. Or else, CRUSH source will look like LZOP - completely unreadable...

It can be portable and readable. Look at LZ4, if not for speed optimisations, it would be very fine. Though adding a ton of definitions is not avoidable really.
BTW, with compiles cleanly with gcc 4.6 with -Wall -Wextra -pedantic already. Though it's not so good with Clang.

[Matt Mahoney]

I thought the code was easy enough to figure out, so I posted a description of the algorithm to http://mattmahoney.net/dc/text.html#2873
Please let me know if I misunderstood. I didn't re-test, but I recalculated the size based on the source code being smaller.

Edit: updated Silesia benchmark. http://mattmahoney.net/dc/silesia.html

[encode]

Just one thing, match finder hashes 3 and 4-byte strings - not an order-3 and order-4 contexts. (Context is a preceding bytes of a current position, string - followed bytes.)
"Penalty" scheme works in main string searching routine too. Thus compressor will prefer short matches at close distances rather than slightly longer matches at extremely far distances. And penalty is 1-byte per 4 extra bits of offset compared to previous closest offset. Accordingly, at Lazy Matching the compressor will not drop a current match if next match is longer, but has too distant offset compared to the current one.

[Matt Mahoney]

Thanks. I updated the wording so I hope it is more clear. With regard to the poll on window size, I'm not sure why this should have a big effect on speed. Does it implicitly increase the length of the hash chain? I did a comparison of crush cx enwik8 with zpaq -method 2 -threads 1 on a 2.0 GHz T3200 (Win32), since crush is single threaded and both use 64 MB blocks. I used -threads 1 to decompress also to make the comparison fair.

crush -> 32,577,338, 448s, 1.27s
zpaq -> 32,785,289, 29s, 4.3s

zpaq takes longer to decompress partly because it verifies SHA-1 checksums. Turning this off with -fragile cuts the time to 3.4s, which is still slower than crush, but still faster than my disk can write.

zpaq doesn't implement 1 byte look ahead, but I am inspired by your code to try it. But it seems to me that testing a hash chain of 4K each for a direct match and a 1 byte look ahead seems excessive. Also, if the look ahead wins, crush just codes a literal and repeats the search on the next iteration. I think it would be faster if the result of that search was saved. One optimization I plan to try is to start the search from the second byte to find the longest match, then test if the first byte is the same and code accordingly.

What I currently do with -method 2 compression is have 2 hash tables of 8 and 4 byte strings with 16 pointers in each bucket instead of a linked list. The long strings are tested first. If a match of length 8 is found, the second set is skipped. If a match of 128 or longer is found at any point, it is taken immediately. Ties are broken by choosing the smaller offset, which I guess is not optimal because offset code lengths can vary by 23 bits.

The buckets are aligned on 64 byte cache boundaries. To reduce cache misses when searching the output buffer, zpaq packs the low 6 bits of the first byte with the 26 bit pointers and compares it first before comparing the strings in the buffer. For bigger blocks, fewer bits are packed. I do need to try your idea of comparing the last byte of the match first.

Also, I don't let the hash chain get arbitrarily long. I use a quick pseudo-random hash of the current buffer position to choose one of the 16 bucket elements at random to update. Previously I used the low bits of the buffer position to choose an element, which works almost as well.

I think that the coding efficiencies are similar. Instead of coding a literal in 9 bits, zpaq emits a 2 bit code and the literal length code using an Elias Gamma code, i.e. coding an n bit number using 2n-1 bits. Instead of 1..5 literals being coded in 9, 18, 27, 36, 45 bits, it would be 11, 21, 29, 39, 47 bits. Long literal strings would be coded slightly smaller. For match lengths, I again use an Elias Gamma code for the high bits and code the low 2 bits directly.

For match offsets, zpaq uses 5 bits to code the number of offset bits over 24 possibilities like 0..23 for 16 MB blocks or 2..25 for 64 MB blocks. This is similar to crush except for allowing longer offsets and implicitly assigning a probability of 3/4 to a match instead of 1/2. The correct value depends on the source, but I think we agree pretty much on the distribution of match lengths and offsets. An offset of n has probability proportional to about 1/(n+16). A match length of n has a probability proportional to 1/(n+4)^2. I found literals of length n have probability proportional to 1/n^2.

[encode]

Yep, for a large dictionary we must hash 5-byte strings or use something more advanced than just simple hash chains - a la binary tree or such. With 4-byte strings hash chains are way too long, especially with text data.
ZLib/GZip uses Lazy Evaluation you described. CRUSH is intended to use with "c" and "cf" modes, "cx" is uncompromized mode for max compression at any cost. Also my approach is suitable for 2-byte lookahead optimized matching (check my GZip Hack), unfortunately such thing is not suitable for coders that simply store the literals.
Literal runs may complicate parsing optimization - you must take into account literal run state - i.e. no reason to drop a match (produce a literal) if previously we code a match (literal run = 0)

[m^2]

encode, I vote for 8 MB. "ex mode is for max compression anyway!"

[encode]

Added 9 compression levels - from Fast to Extreme

CRUSH by Ilya Muravyov, v1.00
Usage: CRUSH command infile outfile
Commands:
  c[1..9] Compress (Fast..Extreme)
  d       Decompress

[encode]

Timings on ENWIK8 (2 MB dictionary)
1 - 100000000 -> 41166959 in 1.533s
2 - 100000000 -> 38966076 in 1.689s
3 - 100000000 -> 37282880 in 2.011s
4 - 100000000 -> 35967018 in 2.708s
5 - 100000000 -> 34938903 in 3.856s
6 - 100000000 -> 33566700 in 10.079s
7 - 100000000 -> 32890930 in 26.581s
8 - 100000000 -> 32635677 in 49.457s
9 - Not yet implemented

5 is the default, 8 and 9 are Max and Extreme modes for maniacs

[Nania Francesco]

Very nice results!

[encode]

Well, CRUSH source was completely rewritten - I've changed the programming style to be more clean and neat, added some comments. Some parts of code was optimized - now decompressor is slightly faster. Checked Linux compatibility (KNOPPIX LiveCD) - for full compatibility, I'm thinking to remove that X -> X in X sec stuff.
Now I'm (re)optimizing the bit codes for match length with my brute force optimizer, as well as other parameters like penalty function etc. My goal is a higher compression compared to original CRUSH with the same window size!
Please vote for window(dictionary) size above!

[encode]

I almost finished working on CRUSH. Bit codes are pretty adequate, so I'll keep the compression format as is. Slightly improved parsing:

ENWIK8:

CRUSH 1M:
cf - 100000000 -> 37408925 in 1.918s
c - 100000000 -> 33581076 in 13.166s
cx - 100000000 -> 32529467 in 52.572s

CRUSH 2M
cf - 100000000 -> 37308893 in 2.043s
c - 100000000 -> 32878537 in 25.24s
cx - 100000000 -> 31731711 in 121.243s

world95.txt:

CRUSH 1M:
cf - 2988578 -> 870204 in 0.062s
c - 2988578 -> 722986 in 0.249s
cx - 2988578 -> 693217 in 1.06s

CRUSH 2M:
cf - 2988578 -> 867591 in 0.078s
c - 2988578 -> 709912 in 0.358s
cx - 2988578 -> 678869 in 1.653s