LZF - Optimized LZF compressor

[encode]

A quick VS2013 compile is here:
http://compressme.net/

LTCB results:

Z:\>lzf c enwik8 enwik8.z
Compressing enwik8: 100000000->48947532 in 0.924s

Z:\>lzf cx enwik8 enwik8.z
Compressing enwik8: 100000000->46318130 in 1.611s

Z:\>lzf d enwik8.z e8
Decompressing enwik8.z: 46318130->100000000 in 0.244s

Z:\>lzf c enwik9 enwik9.z
Compressing enwik9: 1000000000->440862551 in 8.503s

Z:\>lzf cx enwik9 enwik9.z
Compressing enwik9: 1000000000->416377741 in 14.477s

Z:\>lzf d enwik9.z e9
Decompressing enwik9.z: 416377741->1000000000 in 2.271s

It is compatible with LibLZF compression library, but not with an original LZF compressor (my LZF produces raw compression streams with no headers and/or checksums).
Also, keep in mind, my LZF is not based or delivered from this library - I've tested many (well, nearly all) LZ77/LZSS ideas and designed this compression format independently, after, comparing it to existing compressors I've found that it is similar to the LZF, so I named it accordingly. Actually, it utilizes some ideas from LZCB (by Charles Bloom) and also it is somewhat similar to LZOP. Thus, the original LZF carry no new data compression ideas or tricks.
All in all, it is a very fast byte-aligned LZ77 with an 8 KB window!

Well, enjoy new release!

[Matt Mahoney]

Updated LTCB. I used your timing results and it looks like it made the Pareto frontier. Same hardware? http://mattmahoney.net/dc/text.html#4164

[encode]

Yep, it's my 3770K PC

[nburns]

Wait till Matt tests it on his really slow computer. Then it won't look as hot.

[encode]

Well, actually, the goal of my LZF is produce the smallest possible output with such a simplest compression format. Much like optimized deflate tools.
And, it can be faster for sure. Currently it's just not that super-optimized Visual Studio compile. Intel C++ compile might be faster a bit. In addition, since the decoder is very simple (simplest) it can be implemented in ASM in 1 minute. Please read the original LZF format description.

[encode]

Haste makes a waste - a quick performance fix / recompile - LZF v1.01 is here:
http://compressme.net/

+ Optimized compression routines
+ Recompiled using VS2013 Express (vs VS2013 RC). Tested the latest Intel C++ and VS2010 - VS2013 compiled a faster code! Now it's my favorite!

New ENWIK9 timings:

Z:\>lzf c enwik9 enwik9.z
Compressing enwik9: 1000000000->440862551 in 7.971s

Z:\>lzf cx enwik9 enwik9.z
Compressing enwik9: 1000000000->416377741 in 12.464s

Z:\>lzf d enwik9.z e9
Decompressing enwik9.z: 416377741->1000000000 in 2.262s

[nburns]

+ Optimized compression routines
+ Recompiled using VS2013 Express (vs VS2013 RC). Tested the latest Intel C++ and VS2010 - VS2013 compiled a faster code! Now it's my favorite!

You're not giving away the source code? Are you sure you didn't miss any options on the Intel compiler that might have helped (or use any that might have hurt)? Since you're comparing compilers, it would be interesting to see how gcc and clang do.

[encode]

Intel C++ is not always faster. Visual C++ 2013 is goddamn good! Actually, I briefly tested ICL with switches I usually use, and in many cases Intel is faster indeed! However, in some cases (LZF, PPMX) it is not.
LZF source is not compatible with GCC - I intensively use Microsoft Visual C++ specific stuff and happy with it.
As to Open Source - I release source of a program only if it's obsolete in terms of novel compression ideas and/or implementation tricks. New LZF is a good base for any LZ77 (LZH, LZ77+ARI) compressor and it is a step forward from e.g. CRUSH internals. There's no such thing as a free lunch! This is my policy.

[nburns]

Intel C++ is not always faster. Visual C++ 2013 is goddamn good! Actually, I briefly tested ICL with switches I usually use, and in many cases Intel is faster indeed! However, in some cases (LZF, PPMX) it is not.
LZF source is not compatible with GCC - I intensively use Microsoft Visual C++ specific stuff and happy with it.

I'll do you a favor and translate it into straight C if you want.



C++ is a mixed blessing, because it tends to make your code dependent on specific compilers. Nothing C++ does for you is any help in writing a tightly-optimized routine, because you can't afford to blindly trust the compiler and libraries to do things for you, anyway, right? The only thing it has over C that might tend, on balance, to help make code more performant is templates, but all they do is copy and paste, nothing you couldn't do without.

Edit: Don't take this too critically -- you obviously get superb code out of VC++, and I'm interested to know how. I know Microsoft treats their C compiler with a bit of neglect, and writing code that extracts every last drop of performance from the CPU isn't a subject I'm all that well versed in. Portability is worth aiming for, though, and -- all else being equal -- I would expect that C can be optimized just as effectively as C++.

[moinakg]

... Portability is worth aiming for, though, and -- all else being equal -- I would expect that C can be optimized just as effectively as C++.

IMHO, for low level optimized code, C++ is just syntactic sugar compared to C. However C++ actually eases development of large complex applications.

[Matt Mahoney]

Updated results on my slow computer http://mattmahoney.net/dc/text.html#4164

[nburns]

Updated results on my slow computer http://mattmahoney.net/dc/text.html#4164

My impression is that you probably have a few computers, but one is really old and slow. That would be the one you used to benchmark my BWTS code.

[nburns]

IMHO, for low level optimized code, C++ is just syntactic sugar compared to C. Howevler C++ actually eases development of large complex applications.

It is almost entirely syntactic sugar on top of C. Before it had its own compilers, it had a program that just expanded the sugar back to C and you compiled the C. Even now they share the same compiler.

Nothing stops you from writing parts of your app in C and the rest in C++. Nothing, except shaming from C++ zealots.

[Matt Mahoney]

Mostly I use one computer for Windows and a slightly newer one for Linux. Well, I don't see any good reason to get a new one as long as the old ones still work, and new ones for the same price aren't much faster. It seems like Moore's Law has stalled in the last few years, or maybe it has just shifted to phones and tablets.

My original LTCB results were on an even older computer. I am kind of encouraging people to buy fast computers and run their own tests.

[nburns]

Mostly I use one computer for Windows and a slightly newer one for Linux. Well, I don't see any good reason to get a new one as long as the old ones still work, and new ones for the same price aren't much faster. It seems like Moore's Law has stalled in the last few years, or maybe it has just shifted to phones and tablets.

My original LTCB results were on an even older computer. I am kind of encouraging people to buy fast computers and run their own tests.

I haven't followed CPUs much lately, but if Moore's law stopped, it's news to me. The problem is that Moore's law is only incidentally related to performance. I'm going out on a limb here a bit with my knowledge of electronics, but I think what physically mattered to performance was the amount of work needed to charge up the chip each clock cycle, which I believe corresponds to this equation I stole from wikipedia:



For a while, Moore's law helped by shrinking the amount of charge needed (q), but, eventually, as the wires got too small, the bottom dropped out on the ability to hold the charge (capacitance, C). So the amount of work went down for a while and then hit bottom, which was probably predictable from elementary principles all along. We just didn't know when it would happen. It turned out to be around 2006.

Every performance increase since has been about rearranging transistors to find the design that executes the most instructions per clock, but that is heading for some constant limit. Rearranging transistors gives diminishing returns.

That's the grim truth as I see it.

[Matt Mahoney]

Clock speeds stalled several years ago. The next barrier is transistor size. Now we have 22 nm features, which is about 100 atoms. You can't make components smaller than atoms.

[nburns]

The next barrier is transistor size.

Transistor size isn't directly related to processing speed, though. Smaller ones helped only until we hit a minimum in the energy curve. Small helps give you more of them for the same cost, but you still have to conttain the power, and you have to find something meaningful to do with them. The variable most closely dependent on size is cost, because more chips fit on a wafer.

The width of a feature shrinks by the square root of 2 each generation, so you can calculate the ultimate limit on Moore's law. If I did the math right, that gives us 20 years until we hit an atom.

[encode]

g++ compile (MinGW g++ (GCC) 4.8.1)

Z:\>lzf cx enwik9 enwik9.z
Compressing ENWIK9: 1000000000->416377741 in 13.815s

Z:\>lzf d enwik9.z e9
Decompressing enwik9.z: 416377741->1000000000 in 2.68s

i.e. - it is slower...

[nburns]

g++ compile (MinGW g++ (GCC) 4.8.1)

Z:\>lzf cx enwik9 enwik9.z
Compressing ENWIK9: 1000000000->416377741 in 13.815s

Z:\>lzf d enwik9.z e9
Decompressing enwik9.z: 416377741->1000000000 in 2.68s

i.e. - it is slower...

So it's about 11% slower for compression and about 19% slower for decompression? It's a step closer to being portable, though, and you can't argue with that.

[encode]

Yep, but I removed Unicode and Large File support for that...

[Skymmer]

Intel C++ is not always faster. Visual C++ 2013 is goddamn good!

Sad but true - Intel Compiler is not a cake anymore. New versions have a tendency to generate a slower code than previous ones in some cases. And both GCC and MSVC quite often beat the IC. For example IC versions of reflate's dlls are notably slower then MSVC. And SREP GCC versions are faster (at least on some modes) than IC. Probably this was the reason Bulat made GCC compiles to be default.
From another point of view there is PGO in IC. Sometimes it can give a realy good boost.
Anyway, I talked with Shelwien months ago about the IntelC and by his opinion the best version (in terms of speed) is 11.1 so if you're going to squeez out the maximum speed then this version is probably worth trying

[nburns]

Yep, but I removed Unicode and Large File support for that...

Why do you need unicode support?

[encode]

Unicode is a must have these days! As example, LZF can handle Russian, Chinese, etc. etc. file names. Why not?

[nburns]

Unicode is a must have these days! As example, LZF can handle Russian, Chinese, etc. etc. file names. Why not?

Ok. It makes sense in the file name. It wouldn't make sense inside the file. I'm not familiar with how windows file names work. Are they utf-16 like everything else? Of course, there must be portable ways to handle that.

[encode]

To sum up, here's the comparison of byte-aligned compressors I've released so far.

Test file - bf4.exe - Battlefield 4 game 64-bit executable (37,079,552 bytes)

No code has to be inserted here.

Compressors marked with * are not byte-aligned. Yep, LZOP uses different algorithms - not just one.

And yes, 8 KB window is too small for real world.

[encode]

If get rid of slow getc()/putc(), changing interface from buf->file, file->buf to buf->buf, we will get:

Z:\>lzf c enwik9 enwik9.z
Compressing enwik9: 1000000000->440862791 in 6.926s

Z:\>lzf cx enwik9 enwik9.z
Compressing enwik9: 1000000000->416377981 in 11.497s

Z:\>lzf d enwik9.z e9
Decompressing enwik9.z: 416377981->1000000000 in 1.825s

Size differs, since here we need to store 32-bit compressed size per each block compressed

[nburns]

What is the penalty associated with getc/putc? stdio is supposed to buffer for you, but it doesn't seem to quite replace manual buffering. There isn't much documentation on how stdio buffers that I can find.

[encode]

It's about "if" statement per each byte read/write. Writing own getc()/putc() help just a little. setvbuf() might slightly improve performance as well.
In other words, if we deal with an algorithm that is about the same complexity as memcpy(), everything counts (even in small amounts )

[nburns]

It's about "if" statement per each byte read/write. Writing own getc()/putc() help just a little. setvbuf() might slightly improve performance as well.
In other words, if we deal with an algorithm that is about the same complexity as memcpy(), everything counts (even in small amounts )

Okay. So the penalty is very small, then.

[encode]

Well, just added a new super cruncher mode to the upcoming LZF v1.02 with the insane string parser. It's okay, since the purpose of the Maximum mode is the maximum compression within a given format, at any cost. Normal mode will have about the same compression and a slightly higher compression speed. New version will be fully compatible with the older one.

Testing results:

No code has to be inserted here.