Entropy evaluation : small changes in benchmark corpus

You can't easily improve what you can't measure. That's why test tools are so important.
For compression, benchmark corpus is an essential tool to measure performance and check consistency.
Its main drawback, however, is to influence development in a way which make the benchmark look better, forgetting or even worsening situations which are not in the corpus.

Therefore, carefully choosing elements within the corpus, and even changing them from time to time, is a sensible thing to do.

For entropy evaluation, the different categories selected seem right. However, evaluating with just a single filetype example is misleading.
I started by changing the LZ4 output by the LZ4HC output, producing different pattern. I then added 2 files, Win98.vmdk, a virtual hard disk with many cab files, and Open Office directory, a mostly binary input. Here are the results :

		Huff0 v0.6			Range0	v0.7
	Ratio	Compress	Decoding	Ratio	Compress	Decoding
Not compressible
enwik8.7z	1.000	810 MB/s	1.93 GB/s	1.000	885 MB/s	1.93 GB/s
Hardly compressible
win98-lz4hc-lit	1.024	465 MB/s	600 MB/s	1.019	374 MB/s	262 MB/s
audio1	1.070	285 MB/s	280 MB/s	1.071	174 MB/s	83 MB/s
Distributed
enwik8-lz4hc-lit	1.290	205 MB/s	194 MB/s	1.296	150 MB/s	77 MB/s
Lightly Ordered
enwik8-lz4hc-offh	1.131	197 MB/s	184 MB/s	1.133	145 MB/s	79 MB/s
Ordered
enwik8-lz4hc-ml	2.309	214 MB/s	195 MB/s	2.326	160 MB/s	77 MB/s
Squeezed
office-lz4hc-run	3.152	218 MB/s	202 MB/s	3.157	164 MB/s	98 MB/s
enwik8-lz4hc-run	4.959	245 MB/s	224 MB/s	5.788	188 MB/s	148 MB/s
Ultra compressible
loong	278	785 MB/s	2.93 GB/s	1430	555 MB/s	427 MB/s

There are several interesting learnings here.
Win98-lz4hc-lit is the literals part only extracted by lz4hc. But wait, why is it not into the "distributed" category ? Well, since this file contains many incompressible chunks, the literal sub-section end up being mostly incompressible. This is an important real-world example, showing that incompressible segment detection makes real impact.

lz4hc produces less literals and less matches, but longer ones, than the fast version. As consequence, run length are much more compressible, while match length are not. It perfectly shows that the more squeezed the distribution, the better Range0 compression advantage.

One could think that run length is a typical situation which should always benefit Range0. Alas, it is not that simple. Such conclusion is biaised, as a result of focusing too much on enwik8 for tests.
Most binary files feature a very different pattern : much less frequent matches, but much longer ones. As a consequence, literals tend to be quite more numerous, their compressibility being also not guaranteed. And as a side effect, run lengths end up being larger.

This is showed by office example : although the distribution is still "squeezed", resulting in a pretty good x3 compression ratio, this is still not enough to make Range0 distinctly better. In fact, considering the very small difference with Huff0, it's not worth the speed impact. This is in contrast with enwik8 results.

This means that we should not assume run length to be constantly better compressed by Range0, requiring a more complex selection process.

Range0 : new version (v0.7)

Several learnings from the Huff0 new version were generic enough to become applicable to Range0. More specifically, the interleaved counter and the call to memcpy(), resulted in significant improvements, as displayed below :

                       Range0 v0.6      Range0 v0.7

                       R    C    D      R    C    D 

Not compressible 

enwik8.7z            1.000 870 1400   1.000 885 1930 

Hardly compressible 

audio1               1.071 174   83   1.071 174   83 

Distributed 

enwik8-lz4-lit       1.370 155   76   1.370 155   76 

Lightly ordered 

enwik8-lz4-offh      1.191 138   76   1.191 138   76 

Ordered 

enwik8-lz4-ml        2.946 155   83   2.946 160   83

Squeezed 

enwik8-lz4-run       4.577 163  116   4.577 180  116 

Ultra compressible

loong                1430. 362  427   1430. 555  427  

The memcpy() makes wonder at improving speed for incompressible segments.
More importantly, interleaved counter speed up squeezed distribution compression.

The ultra-compressible corner case is not so important, in spite of the huge performance benefit, but the squeezed distribution benefit is, since this is Range0 most likely use. At 180 MB/s, it makes it almost as fast as standard Huffman coders, which basically means extra compression performance for free.

The bad point is, and will remain, the decoding speed, which cannot beat Huffman, due to the presence of a division into the main loop. However, the decoding speed is not too bad for the specific "squeezed" situation we want Range0. Indeed, should the distribution become even more squeezed, decoding speed would become even better.

Evolving the benchmark corpus in order to consider LZ4HC output, instead of Fast LZ4, is likely to make this statement more relevant.

For the time being, Range0 can be downloaded here.

Huff0 : New version (v0.6)

Since working on the stats produced by huff0, some inefficiencies became apparent, and as a consequence got solved in a newer version, available on the new huff0 homepage.

To properly understand what was changed, here is a performance snapshot, comparing v0.5 (old) with v0.6 (new).

                       Huff0 v0,5       Huff0 v0,6 
                       R    C    D      R    C    D 
Not compressible 
enwik8.7z            1.000 740 1400   1.000 810 1930 
Hardly compressible 
audio1               1.070 285  280   1.070 285  280 
Distributed 
enwik8-lz4-lit       1.363 210  200   1.363 210  200 
Lightly ordered 
enwik8-lz4-offh      1.188 188  181   1.188 188  181 
Ordered 
enwik8-lz4-ml        2.915 200  197   2.915 210  197 
Squeezed 
enwik8-lz4-run       4.284 209  218   4.284 235  218 
Ultra compressible
loong                278.0 450 2930   278.0 785 2930  

Changes are underlined in bold characters.

To begin with, only speed is affected by the changes. Compression ratio remains strictly identical.

The first changed is in the way data is scanned. This is a nifty trick, related to cache behavior. When updating a data, such data should not be updated again immediately, otherwise there is a "cache" penalty : the previous change must be fully committed before the new one get accepted.
In order to avoid such penalty, we interleave data changes, so that the CPU get enough time to deal with repeated changes on the same value. It makes the code slightly more complex and data structure a bit bigger, but is definitely worth it : although it affect negatively situation such as "not compressible", on the other hand the more some data is present, the better the benefit.
We end up with a grand +70% improvement for "ultra compressible" corner case. Not only corner case benefit though, "ordered" distribution get a nice +5% boost, while squeezed one get a bit more than +10%.

The second change is on the way incompressible data is detected. While the end result is still slower than Range0, there is a pretty nice performance boost by betting earlier on the incompressible nature of data just scanned. It avoids later algorithm to be triggered, thus saving time and energy. This is a nice +10% boost.
While this gain is only visible on "not compressible" example, it still can achieve real situations benefits. It is not uncommon for some parts of large files to be incompressible. For example, an ISO file may contain a few pictures in compressed format. In this case, the better the detection, the faster the compression, since any attempt to compress it is likely to fail or end up with miserable gains.

The third change is really straighforward : i've removed my hand-made "copy" operation, and swapped it with the standard memcpy() call of C library.
Although only useful when some segments are incompressible, in this case, the gain is really noticeable, at about +30%. For just a simple function call, this is really worth it.

I still have to understand how come the call to memcpy() is faster than my own simple loop. There is probably some very interesting learnings behind.

Side comment, i tried the same trick on "ultra compressible" file, replacing my own simple loop with a memset(). It resulted in no speed difference. I tried then to improve the simple loop by making more complex parallel executions, but it resulted in a loss.
My only explanation so far is that the compiler probably translates my simple loop into a memset(), transparently.

Anyway, please feel free to test.
The binary can be downloaded at Huff0 homepage.

Quick look back at Huff0 : an entropy coder analysis

Since LZ4 is pretty much limited in testing match searches over long distances, i'm almost pushed into writing a new compression software to continue investigations.

Therefore, since such an effort is required, it is also a good time to have a fresh look at entropy coder.

Entropy is generally not used as a direct compression method. Its better use is *after* modeling.

For example, after an LZ77 compression pass, we end up with many match lengths, which distribution is not random : short lengths are much more common than longer ones.

Entropy coder will ensure that frequent symbol get coded using less bits than uncommon ones. That's the basis for better compression results.

The most renowned entropy coder is probably the Huffman one. It is no longer considered top of the line, but continue to be used in many mainstream applications, due to its simplicity and speed.
Huffman will guarantee that, given a symbol distribution, the best possible combination of bits per symbol will be created. That's a strong property.

Since Huffman proved that its method was the best possible, entropy coders received little attention before a few decades later, when Arithmetic coders started to be implemented.
This new beast is a lot more complex to explain, so i'll invite you to read the wikipedia entry to get more details. For the purpose of this post, it is enough to accept that arithmetic coders can attribute the equivalent of a fractional bit to a symbol. Yes, it becomes possible to encode a symbol using, for example, 0.38 bits.
This may sound strange, but it's all mathematics.

By breaking the "integer" boundary, arithmetic coders allow for much better precision, and therefore better compression. This is especially important when probability is higher than 50% : Huffman cannot do better than providing 1 bit per symbol, which is just right for 50%, but is much less optimal for 80%. In such instance, arithmetic coder will do much better.

A lesser version of arithmetic coder is called Range coder. It's pretty much the same, except that it works with integer numbers, and, more importantly, is free from patents, unlike arithmetic ones.

In order to test both method, i've created 2 programs, Huff0 and Range0.

Huff0 is a block based Huffman Entropy coder. Each data is divided into blocks of 16KB. The compressed output consists in a tree, followed by compressed entry.

Smaller blocks allow faster adaptation, but cost more in header, so a trade-off had to be chosen. 16KB was selected as being mostly optimal for distributed input, such as literals, or most files.

Range0 is a block based Range Entropy coder. Each data is divided into blocks of 128KB. The compressed output consists of a frequency count, followed by compressed entry.
Why 128KB ? Because the frequency count is much heavier than the Huffman tree. As a consequence, dividing data into smaller blocks results in a loss, in spite of better adaptation.

Such trade-off between adaptation speed and header costs deserve a full study in itself, and we'll keep that for another post.

In order to better understand the properties of each coder, i needed a benchmark corpus. I started by using files, but this is nonsense. As stated earlier, entropy coders are not used as direct compression tools, but rather as a "second stage" pass, applied to statistics or probabilities output from model.
So it sounded more reasonable to create files which would mimic the statistics produced by such models. Here is what i ended up with :

                       Huff0 v0,5       Range0 v0,6 
                       %    C    D      %    C    D 
Not compressible 
enwik8.7z           100,01 740 1400  100,00 870 1400 
Hardly compressible 
audio1               93,43 285  280   93,38 174   83 
Distributed 
enwik8-lz4-lit       73,35 210  200   73,00 155   76 
Lightly ordered 
enwik8-lz4-offh      84,18 188  181   83,95 138   76 
Ordered 
enwik8-lz4-ml        34,30 200  197   33,94 155   83 
Squeezed 
enwik8-lz4-run       23,34 209  218   21,85 163  116 
Ultra compressible
loong                 0,36 450 2930    0,07 362  427  

That's a lot of results for a single post. But there is a lot to learn from it.
enwik8-lz4-y are files created by using LZ4 on enwik8, extracting a specific field. This is the fastest LZ4 version, not the HC one, so this could change in the future.
% is the resulting size, as % of original file.
C is the compression speed, in MB/s.
D is the decoding speed, in MB/s.

Not compressible : as stated, this 7z entry is already compressed, so there is nothing left.
The basic idea here, is to detect this situation fast enough, and to switch to backup copy mode.
The catch, is that this mode should not be too triggered too easily, otherwise we may lose some compression.

What immediately look strange here is that Huff0 is slower than Range0. Probably there is still some room for improvement.

Hardly compressible : this is a good torture test for the compression detector. This entry is a wave file, 16 bits stereo. As a consequence, when dealt with directly by an entropy coder, half the data is purely random (lower bits), and the other half has a small tendency to lean towards an average threshold. All in all, the compression that can be achieved is less than stellar, but still measurable.

We are starting to witness a tendency that will only grow stronger : Range0 compress better, but slower. Especially, the decoding speed of Range0 is an issue when compared with Huff0.

I will skip directly to 

Squeezed : in this file, one of the symbol has a probability higher than 50%. And it pays off quite a lot for Range0. This is no longer about a .2% small benefit, but a more sensible 1.5% advantage. And this figure can only become better if using the HC version of LZ4, which will produced even more squeezed output.

Ultra Compressible : this is a test file, produced by Eugene Shelwien, to test limit conditions when compressing long streams of identical bytes. It is not a single byte, however, there are some changes from time to time, to make life harder to the coder.

What should immediately be visible, is that Huff0 succeeds in producing a file which is much better compressed than 1/8, the theoretical minimum. This is thanks to the relatively small size of blocks : when a block consists of only one repeated byte, it gets a specific shortcut sequence. The decoding speed shows this is highly effective.

This is in contrast with Range0, which decoding speed is *only* 427MB/s. This is due to larger block size, which means we more rarely have a full block with only one byte; as a consequence, it must be decoded, which is slower than the special escape sequence.

Note however, that, as could be expected, Range0 compression is much better than Huff0 on this example.

So, where does that lead us to ?

Well, that's just a start. It provides some interesting ground for future comparisons, allowing targeted improvements to become measurable. 

More of it in a future post...

MMC available as Source Code

 Finally, MMC can downloaded as a C source code, thanks to google code excellent publishing services.

Source is for programmers, obviously.
Interface has been made as simple as possible, with just a few calls  :

U32 MMC_InsertAndFindBestMatch (void* MMC_Data, BYTE* ip, BYTE** r);

U32 MMC_Insert1 (void* MMC_Data, BYTE* ip);

U32 MMC_InsertMany (void* MMC_Data, BYTE* ip, U32 length);

MMC_Data is handled transparently, so that program users do not need to care about it. It can be manipulated with the simple definitions below :

void* MMC_Create (BYTE* beginBuffer, BYTE* endBuffer);

U32 MMC_Init (void* MMC_Data, BYTE* beginBuffer, BYTE* endBuffer);

U32 MMC_Free (void** MMC_Data);

Although this is plain C, the logic seems pretty close from C++, with all data encapsulated into a void*.
This logic also ensures that MMC is multi-thread ready.


You can download it here :
http://code.google.com/p/mmc/

A new look at collisions

Quite some time ago,  i investigated Collisions effects, while working on the first version of MMC.

This was my second investigation, the first one being completed while working on simpler HC (Hash Chain), and which conclusion was : it's not worth increasing the Head Table beyond a certain level, since the improved dispatching ability is hampered by decreasing cache efficiency.

MMC made me have a second look, since its natural behavior is meant to reduce if not eliminate collisions. I ended up with the following diagram, which proved me wrong : MMC was simply decreasing collision effect, but not eliminating it.
I was also shocked by the very linear nature of the collision counter, adamant when using an exponential scale. In effect, it simply proved something simple : increasing hash size by 2 decrease collision by 2, which means that the hash formula is as good as it can be.

Nonetheless, this second study did not changed my conclusion, which was that beyond a certain level, cache effect is more important than reduced collision gains.

This was before working on large search window sizes. Indeed, since my earlier implementations were too slow, working on large search windows was simply out of reach. This has all changed with latest versions of MMC.

Invited by Piotr, i tried MMC with much larger window size, starting with 16MB.
The algorithm was slow as hell, but something struck me : the collision rate was extremely high, sometimes beyond 80% of all comparisons loop. This is way out of control, and can explain alone the bad performances.

Hence, a third look at this phenomena.

A "collision" happen when a hashed sequence, of length MINMATCH, get the same hash value as another different sequence. If the hash formula is relatively well distributed, it should happen once in every "hash-size" position. In fact, this is a worst case situation, since compressible data, by definition, have a non-random distribution pattern, meaning that many sequences are either extremely rare if not impossible.
On the other hand, worst case scenario do sometimes happen, typically when compressing an already compressed file, or part of file.

With collision representing sometimes up to 80% of comparisons, there was definitely quite a lot of effort wasted at this stage.

This is the result of keeping the hash table identical on all window size, in an effort to keep the numbers "comparable" (thus avoiding to attribute the merit of a better MMC method while it would in fact come from a larger hash distribution).

This however made me forget that Hash size is also part of the performance equation.
A quick solution to this problem is simply to enlarge the initial hash table, in charge of dispatching the sequences. With a good hash formula, enlarging hash by 2 should reduce collisions by 2. And it works as well as it should.

Hence, i came back to 4MB dictionary to make some tests and measure effects. Here are the results : the first figure is the % of comparisons which are collisions, and the second one is the speed.

Window Search 4M :

File	Calgary	Firefox	Enwik8	OpenOffice
Hash 128K	13% - 8.1 MB/s	60% - 2.7 MB/s	6% - 3.0 MB/s	66% - 2.8 MB/s
Hash 256K	7% - 8.0 MB/s	42% - 3.8 MB/s	3% - 2.9 MB/s	49% - 4.4 MB/s
Hash 512K	4% - 8.0 MB/s	27% - 4.9 MB/s	2% - 2.9 MB/s	33% - 6.2 MB/s
Hash 1M	2% - 8.0 MB/s	16% - 5.8 MB/s	1% - 2.9 MB/s	19% - 7.6 MB/s
Hash 2M	1% - 8.0 MB/s	9% - 6.3 MB/s	.5% - 2.9 MB/s	11% - 8.5 MB/s
Hash 4M	.5% - 7.9 MB/s	5% - 6.7 MB/s	.2% - 2.9 MB/s	6% - 9.2 MB/s
Hash 8M	.3% - 7.7 MB/s	2% - 6.7 MB/s	.1% - 2.9 MB/s	3% - 9.3 MB/s

Now this is pretty clear : this "fixed size" hash table was holding back MMC performance at larger search size. With an increased budget, it makes the final speed now relatively acceptable.

But there is more to it : as can be expected, files which were not advertising much collisions (Calgary, Enwik8) do not gain anything, and even lose some performance, most probably due to cache effects.

On the other hand, some files are suffering heavily from collisions (Firefox, OpenOffice), and as a consequence, increasing the hash size results in major speed gains, with OpenOffice showing impressive results.

This is in stark contrast with my earlier statement, which was probably biased due to :
1) using small search window, resulting in larger hash sizes having a notable bad performance impact
2) using Enwik8 and Calgary as my main test files. I though Firefox was an exception, but maybe it was the other way round.

Obviously, different files feature different distribution.

Which lead us to the question : which "Head" size is the best ?
I started with a fixed size of 17 bits, but now it seems a better rule should be to correlate this size with Window Size.
This, in effect, means that "Head Size" is no longer a "small additional table", and that it's budget is now correlated with dictionary size.

As far as i remember, 7zip uses 2x Dictionary size for Head table. Since each head element is 4 Bytes (32 bits pointer or index),  it means the number of elements is twice smaller as Dictionary Size (ex : 2M for a 4M window size).

Judging by the result in the above table, this looks just right.