LZ4 : New version (0.9HC)

 Well, just when i though that there was nothing else to do to improve the decompression speed of LZ4...

Then i find a corner case where LZ4 does not work so well. Having a sanity check on loong, a file created by Eugene Shelwien, initially to torture range coders with limit conditions, i discovered to my surprise that the decoding speed was not good enough, "only" 500MB/s; unexpected, as i was looking for something much closer to a few Gigabytes.

Looking back into the source, my understanding was that the code in charge of overlapping sequences was too cautious. With just a little more complexity, it could be made much faster.
Overlapping sequences are not too often, but they happen here and there, in each and every file. As a consequence, it resulted in a generic speed boost to all files for decoding.

Logical follow-up, here comes the release of a new LZ4 version, breaking some new decompression speed records. You can download them on LZ4 Homepage.

	version	Compression Ratio	Speed	Decoding
LZ4 "Ultra Fast"	0.6	2.062	232 MB/s	805 MB/s
LZ4HC "High Compression"	0.9	2.345	38.2 MB/s	880 MB/s

Talking about bragging around the world...

BST : First experimental results

Still on my quest for better search algorithms, i tried a simple BST (Binary Search Tree) code, in order to compare it with MMC. As stated in an earlier post, BST should be faster than MMC, at least in its current format.
Reality is a bit more complex.

My current BST implementations uses a Hash Table acceleration, using same size and calculation as MMC. For a fair comparison, i've disabled Segment detection from MMC.

The results are somewhat mixed and require some explanations.
First, i tried BST with partial updates. It means that positions inside matches are not taken in consideration. This reduces compression rate, but also considerably improve speed, since repetitions are unlikely to be found very often in the dictionary.

Here are the results. As usual, i'm counting the number of comparisons necessary to complete the file.

Partial Update Test
File        BST      MMC
Calgary    0.98M    1.73M 
Firefox    7.71M    13.1M
Enwik8     33.4M    62.4M

The results are pretty clear : in partial update mode BST wins. With much less comparisons to do, BST is much faster, between 20% and 50% depending on file types. Speeds in the range of 80MB/s to 110MB/s are accessible.

Now, partial update is not really my objective. I want a full search, over the entire search window. This is much more difficult, with a lot more elements to integrate, longer searches, and repetitions putting an heavy toll on any search structure.
Here are the results i started with :

Full Update Test

File        BST      MMC

Calgary    1.46M    5.81M 

Firefox    11.3M    41.1M

Enwik8     47.0M    167.M

Looks like a clear win for BST ? Alas, there is more to it.

From a speed perspective, observations do not match these results. Indeed, MMC is much faster than BST, sometimes just 2x, sometimes up to 10x; there is a massive difference, and it is clearly in favor of MMC.

So where does it comes from ? Code complexity ?

No, remember one of the fundamental properties of MMC : data is sorted only if necessary, and during search. In contrast, BST data is sorted on insertion, which means that all bytes added to the tree produce comparisons. These comparisons must be added to total. And here are the surprising results :

Full Update Test

File       BST.Search BST.Update MMC.Search MMC.Update

Calgary    1.46M      382.M      5.81M      0

Firefox    11.3M      518.M      41.1M      0

Enwik8     47.0M      312.M      167.M      0

Ouch, this hurts. Indeed, many more comparisons are generated while adding positions into the tree than while searching a match. The difference is really huge, and clearly play in favor of MMC.

One can see the pretty large impact of repetitions on Calgary and Firefox, which makes MMC stand very far ahead (even though repetition detection is disabled !).

But even if we just look at Enwik8, where repetitions are nearly non-existent, the update cost is still too large compared with MMC.

Speed results are directly affected : MMC is 2.5x faster for Enwik8, 5x faster for Firefox, and 7x faster for Calgary. Quite a large lead.

Obviously, adding some optimizations for repetitions should help BST. However, as the results with Enwik8 prove, it will not be enough to beat MMC.

Maybe MMC is much more a contender than i initially thought...

Note that these results are using Greedy parsing strategy. The conclusions are likely to be very different if going for Optimal parsing strategy.

Cache-friendly search algorithms

In an earlier post, i've presented some obvious statements about cache properties. In a nutshell, cache make tremendous difference in data access, but the fastest the cache, the smallest.

Now we are going to look more closely to its behavior.

The first important concept to keep in mind is the cache line. A memory cache does not keep in mind the last randomly accessed bytes. Data is considered structured into lines, which size depends on the CPU.
The most standard line size is 64 Bytes, that you'll find in all recent PC.
It means that whenever you are accessing a single byte in memory, you are not just loading one byte into cache, but a full line of 64 Bytes.

This is of fundamental importance. What it means is that if you ask for data at position 1, CPU will load the first line. Then, when position 2 will be needed, this data will already be in the cache, so will be position 3, and so on, up to position 63.
Given the very large difference in access time between L1 cache (3-7 cycles) and memory (100-200 cycles), it makes access to already loaded data almost free.

This is a property that any performance-oriented algorithm should keep in consideration. It requires adapted data structure.

Let's have a look at MMC and BST. They both store 2 pointers per position. These 2 pointers are stored next to each other, which means that when i will ask one, i will be able to access the other one "almost" for free.
Now, what about the data it is pointing to ?
Well, here it is very likely to fall outside of line cache, since only 8 positions are part of the same line : the next jump is almost certainly way outside of this range.

Taking advantage of cache line requires a completely different data structure. We should try to get as much hit as possible into the already loaded line, for example by keeping all level positions next to each other.

As said, this is a very different data architecture, and therefore would require a complete rewrite of search algorithm. But then, i'm here to learn...

MMC last boost : Secondary sorting

Credit is due here to Piotr Tarsa, which made an abandoned idea for improving MMC achievable.

This idea is called "secondary sorting", and can be explained as follows :
When searching into a given level, MMC is currently merely interested by the character being looked for. Sometimes we find it immediately, and sometimes not. We may keep finding wrong characters many times, until we get to our goal.

What happens then to all these wrong characters we have discovered all along ?
Quite simply, nothing. They just stay there at their position in the chain, waiting for their turn to be looked for, if it ever happen.
It sounds like a pity, as, eventually, we could have used this information to sort all these positions to higher level, making future searches for these characters faster, but also "cleaning" the current level much faster.

However, this is a much more complex algorithm to implement. And not just complex, it's also an expensive one, requiring more structures, memory and tests. As a consequence, i was pretty much convinced that it would no reach the point of becoming worthwhile.

After a rich discussion at encode.ru forum, all problems gradually found their solution thanks to Piotr involvement and smart advises. We are now in a position where the algorithm looks reasonably efficient, and could therefore bring some benefits.

I started with a few statistics extraction, as usual, to better understand the situation.
To my great surprise, i discovered that, in many circumstances, some level can take a very long walk before finding the character being looked for. In worst circumstances, i've reach values in the thousands (probably a symptom of long repetitions).  Even in more common situations, we can reach several tens attempts, with some "wrong" characters repeated many times.
It's therefore obvious that secondary sorting will provide a real boost at sorting this data, reducing the number of comparisons required for future searches.

Following this short study, i quickly implemented a limited version of "secondary sorting", just able to handle the last position of wrong characters, resulting in their anticipated promotion. It immediately resulted in a 12% improvement in number of comparisons.
Quite a large benefit for such a minor sorting improvement. Better secondary sorting can only improve this figure.

All looks for the better, except that, at this stage, the benefits do not offset code complexity.

At least not yet ...

BST : Binary Search Tree

As stated when MMC algorithm was first published on encode.ru board, there are alternative methods to search sequences in a dictionary, and one of the most efficient, to date, is BST.

BST stands for Binary Search Tree. There is a nice entry at wikipedia on this concept.

BST key idea is pretty simple : given an element, 2 pointers are associated to it. On the "left" pointers, we'll find others elements which are strictly smaller than current one. On the "right" one, all elements will be larger.
This requires elements to be "comparable", a rule we can easily create in this numeric world.

The concept is applicable to positions within a text, or to generalize, within any file.

Now, maybe some of you played at the "guess my number" game as a kid. The idea is simply to find a hidden number, using a minimum number of questions, which answer can only be yes or no.
And the best strategy is always the same : if the "hidden number" is between 0-100, we start at 50, the middle number. Is it larger ? If yes, we continue at 75, if not at 25, and so on, dividing remaining space by 2 at each step.
This method will statistically provide the best result over several games.

The same can be applied here, using BST, over millions of value. In theory, it means we'll get to the result in approximately log2(N) attempts.

Except that, we can't be sure that remaining space is divided into 2 equal parts like in the game. Indeed, the tree could be "degenerated", for example when all elements are inserted in sorted order at root node, resulting in a tree which looks like a chain.
To avoid this situation, some complex mechanisms can be applied, to "balance" the tree, to ensure that all searches get approximately the same (and best) number of attempts before finding the solution. Unfortunately, such mechanisms tend to cost so much overhead as to kill performances for compression algorithms, since the dictionary constantly changes.

So, the question of this post : would BST be any superior to MMC ?

According to Bulat, yes, it should. Because its "compare" relation between parent and child nodes is more powerful than the "is next byte equal" question asked by MMC. In the end, it means that we extract more information from the BST question, and therefore we should converge faster.

But there is another big difference with BST : elements need to be sorted on insertion; while for MMC, they will be sorted during the search. It results in useless comparison operations for BST, since some elements will never be searched during their lifetime.
In a "greedy match" search strategy, this should play a role in favor of MMC, making it a faster alternative.

BST is also vulnerable to long streams of identical characters, since comparison requires more character to decide which one is smaller.

All things considered, BST is a very strong competitor to MMC, and potentially a better one.

So, save any new idea to further improve on MMC, i should spend some time on BST now, to better understand its behavior.

[Edit] I finally made a comparison between MMC and BST, and results are not so favorable to BST :
http://fastcompression.blogspot.com/2010/12/bst-first-experimental-results.html
Maybe MMC is a much better competitor than anticipated...

LZ4 : New version

Following yesterday's improvements on MMC search algorithm, here comes logically a new version of LZ4 "HC", for High Compression, which serves as a living demo to MMC.

It's noticeably faster, about 20% more than earlier "Fusion" version, which makes it close to 40MB/s. Not too bad considering it is a full search. The new version 0.8 can be downloaded on LZ4 Homepage.

While working on the multi-level promotion improvement, i made a small mistake in the length counter loop, which made me discover a new trick about buffer management. Thanks to this trick, less verifications are necessary, and therefore speed is a little bit increased. This trick can be re-used in many other context, and as a consequence, can be speed up LZ4 Ultra-Fast too, which make it even faster. So you'll find a new version of LZ4 too. Funny how new ideas are sometimes discovered ...

	version	Compression Ratio	Speed	Decoding
LZ4 "Ultra Fast"	0.5	2.062	232 MB/s	780 MB/s
LZ4HC "High Compression"	0.8	2.345	38.2 MB/s	835 MB/s

Multiple level promotions : Experimental Results

At last !
God this was difficult, but finally i've completed a working version of MMC with multiple level promotions, and can now extract some useful statistics from it.
If you remember this earlier post, multiple levels promotions is about sorting the currently tested position immediately at its best level, while the previous version was limited to promoting by only one level per pass.
Being at "level L" ensure that all positions chained from the current one have at least L bytes in common. This is a pretty strong property, which greatly reduces remaining positions to test.

By promoting a position, the algorithm makes the next search for a similar pattern faster. In the end, it means less comparisons are necessary to make a full search across a file.

As usual, in order to properly test improvements, i've measured the number of comparisons required for different window size (search depth) and file types. And here are the results :

                       Fusion  Multiple Improvement 
Calgary 64K Searches   5.54M    4.86M      14%
Firefox 64K Searches   41.9M    35.2M      19%
Enwik8  64K Searches    187M     166M      13%

Calgary 512K Searches  10.9M    9.31M      17%
Firefox 512K Searches  92.1M    78.2M      18%
Enwik8  512K Searches   434M     370M      17%

Calgary 4M Searches    14.2M    12.0M      18%
Firefox 4M Searches     182M     160M      14%
Enwik8  4M Searches     751M     619M      21%


As can be seen, improvement is sensible, but not outstanding. There is a slow ramp-up with window search size, although it seems to decrease for Firefox : this is entirely due to collision hashes, which accounts for approximately 40% of all comparisons, which seems a symptom of a long enough compressed segment within the tar file.
Improvement is also relatively well distributed across all file types, and as a consequence, even enwik8 witness some solid gains for a change.

All in all, it translates into an incrementally faster search algorithm. It does not make it super-fast, but an appreciable improvement nonetheless.
Reaching higher speeds now is likely to require a completely new search methodology.

Early end optimization

In the course of what finally is a major effort at rewriting MMC for multiple promotions, i found a small optimization left for current MMC version.
It is simple to explain : when i know that there is no more better element in the chain, i should stop searching.
I always wanted to implement it but failed up to now, producing some missed opportunities in the pack. This is now correctly solved, with a trick called "early end".
Here are some results :

                       Fusion  Early-end 
Calgary 64K Searches   5.54M    5.52M 
Firefox 64K Searches   41.9M    41.8M  
Enwik8  64K Searches    187M     186M  

Calgary 512K Searches  10.9M    10.9M  
Firefox 512K Searches  92.1M    91.7M 
Enwik8  512K Searches   434M     432M 

Calgary 4M Searches    14.2M    14.2M 
Firefox 4M Searches     182M     181M 
Enwik8  4M Searches     751M     749M 


Benefits are disappointingly low.
There must be an explanation though. If there is no possible better opportunity, we are quite likely near the end of the chain anyway, if not already at its end. With these results, it seems this was already the case most of the time.
The only good news is that this small benefit comes at no cost at all.