Advanced Multithreading algorithm (Huff0 v0.9)

 Not being entirely satisfied by latest results from Huff0 v0.8, i've been investigating the threading performance issue mentioned in the last post. It seems that the suspect was guilty : creating threads is a really costly operation.

This was not too sensible with LZ4, thanks to its naturally large chunk size, but this is not an all-around solution. Large chunks also means granularity is impacted. For example, if a test file is divided into 3 approximately equivalent chunks, on double core systems, one core will get twice more work to do, and will become the bottleneck of the system.

In order to solve such issue, jobs must be divided into smaller tasks, so that the potentially less efficient "tail job" remain small in comparison with the rest of the job, when all cores are working full steam.

In order to work on small thread tasks, the right thing to do : keep your threads alive, and feed them regularly.

There are obviously several ways to achieve this, including "do it yourself" ones. Right now, i've been experimenting 2 well documented ones for Windows : Thread Pools, and I/O completion port.

On first look, Thread Pools seems the obvious way to go. This windows API was meant for such task : just pile up jobs, and they will get dealt with as fast as system can complete them, dispatching them over available cores.
There is just a little problem, this API is relatively recent, and unavailable to Windows XP and prior systems. Quite a deal breaker.
Or is it ? Its little cousin, QueueUserWorkItem() was created in 2000, and does exactly the same.
And its usage is damn simple. The structure is the same as CreateThread(). Just use it as a kind of "fire and forget" job queue.
It's extremely efficient. Using this API, I was able to decrease chunk size by a factor 100 with no performance degradation. Quite an achievement.

There are just 2 little problems :

1) There is no API to check when all jobs are completed. Quite a dumb (or faulty?) design. This was apparently later corrected for other languages (C#, C++, even VB), but never for C. In order to know when all segments are compressed, it is necessary to create one's own method. And things are becoming quite nasty at this stage. Since this problem is pretty frequent, many methods can be found on searching Internet, several being questionably stable hackish-styled.
The most interesting one, in my opinion, is Interlocked counter, in conjunction with event wait. Well, now the whole system is a lot more complex than it was supposed to be.

2) You get no control on system resource. No way to tell for example "use just 2 cores please". This simple API uses whatever CPU resource is available.

OK, this starts to make a lot of issues. So i investigated the second method, I/O completion port.
It sounds scary, and ... it looks scary too. On using this old API's method (available since Windows NT4!), it's obvious it was never meant to become a general-purpose job scheduler. But that's one thing it does, and very well.
Initialization is significantly more complex than Thread Pools, but once this is correctly understood, you get all the advantage without the problems. Speed is excellent, number of concurrent thread is finely tuned, and job completion check is much more natural and secure.

So here it is. This new version of Huff0 (v0.9) is using I/O completion port to divide data into much smaller chunks, resulting in more stable and faster results. A little scanning improvement was also added, for the benefit of faster compression.

Detailed performance assessment :

		Huff0 v0.8	-t2		Huff0 v0.9	-t2
	Ratio	Compress	Decoding	Ratio	Compress	Decoding
Not compressible
enwik8.7z	1.000	1.42 GB/s	1.91 GB/s	1.000	1.50 GB/s	1.94 GB/s
Hardly compressible
win98-lz4hc-lit	1.024	850 MB/s	995 MB/s	1.024	905 MB/s	995 MB/s
audio1	1.070	540 MB/s	525 MB/s	1.070	560 MB/s	530 MB/s
Distributed
enwik8-lz4hc-lit	1.290	395 MB/s	375 MB/s	1.290	400 MB/s	380 MB/s
Lightly Ordered
enwik8-lz4hc-offh	1.131	375 MB/s	350 MB/s	1.131	380 MB/s	360 MB/s
Ordered
enwik8-lz4hc-ml	2.309	375 MB/s	380 MB/s	2.309	375 MB/s	385 MB/s
Squeezed
office-lz4hc-run	3.152	330 MB/s	310 MB/s	3.152	420 MB/s	400 MB/s
enwik8-lz4hc-run	4.959	475 MB/s	430 MB/s	4.959	480 MB/s	430 MB/s
Ultra compressible
loong	278	1.49 GB/s	3.22 GB/s	278	1.98 GB/s	3.50 GB/s

The interesting bit is here : this new threading method is generic, and can be applied to any other program. So this is good news for further improvements.

Multi-threaded entropy experiment : Huff0 v0.8

 As a logical step following LZ4, i've been porting multi-threading capabilities to Huff0. For the time being, it is only available in benchmark mode. But since Huff0 is not really a compressor, rather a component for compressors, i do not plan to move it to the file interface for now.

However, there were some useful learnings during this implementation.

First, on multi-threading cost.
LZ4 has a very simple design, it was only natural to keep the large block structure and adapt it to parallel compression. With Huff0, doing the same directly results in a dramatic performance slowdown.
The reason for it : creating new threads costs some performance overhead.
In order to limit this cost, a simple solution is to limit the number of times a new thread is created; a very simple way to achieve this is to deal with larger blocks of data.
Huff0 therefore features a double-segmentation layer, with larger blocks defined at thread level, while smaller ones are dispatched for entropy adaptation purpose (i.e. compression rate is better if blocks are smaller, because the statistics are more adapted to the block).

Thinking aloud, i'm wondering if performance would be better by changing threading strategy : instead of creating a new thread for each block, what about "sleeping it", filling its tables and resume it ?
I'm not sure if it would change performance conclusion, but it's probably worth a try.
[Edit] and indeed, it is, see follow-up : http://fastcompression.blogspot.com/2011/03/advanced-multithreading-analysis-huff0.html

Second, on memory access behavior.
This part is a bit more tricky.
Making a code "multi-thread compatible" requires little more than getting rid of all form of global variables, keeping only local ones (ie dynamically allocated into the stack) or, when necessary, allocating memory in a kind of "context structure" which will be provided as part of the function parameters. This second point makes the code very much "object-oriented".
Now on the findings : i've been witnessing some performance hit on highly accessed memory slots. When, for example, a statistics or counter structure is declared, and due to its nature is updated very often, performance is better when the structure is declared as global variable, rather than local ones. (Note that declaring "static local" variables has the same effect).
I'm not sure to fully understand that one, but i've found a lead : this comment :

"Global variables are accessed via a single known address, whereas local variables are typically accessed by indexing off an address register." 

In calculating the memory address, local variables require one more fast addition operation than global ones. It sounds very little, but precise benchmarks do feel a difference.
I still have to find a way around this performance hit though, if that's possible...

You can download the new version of Huff0 here.

Reaching system speed limits

Although results from CompressionRatings benchmark were good, i was nonetheless surprised to notice that decoding speed would not improve on increasing the number of threads.

The only explanation i could come up with is that LZ4 decoder is decompressing data faster than the RAM Drive can deliver. Which is likely a correct statement, considering the in-memory benchmark results (LZ4 can decompress at an average 800MB/s per core, while RAM Drive can only deliver between 400 and 500 MB/s).

However, it would not explain why compressing with 4 threads was faster than decoding...

Here also, there is a plausible explanation : writing to RAM Drive may be slower than reading. In this case, compression has an advantage, since it writes less data.

Now, let's put that hypothesis to the test. I built a quick benchmark to measure read and write speed from a RAM Drive installed into a Windows XP box. I'm using Gavotte's Ramdisk for this test. Using another ramdisk might result in different speed, but is unlikely to dramatically change the conclusions. A different OS may also change results, but since CompressionRatings run with Windows XP, i'm mostly interested in mimicking the same conditions.

On running the benchmark, i witnessed a very stable 1190 MB/s for read operations.
On the other hand, write operations were limited at "only" 770 MB/s.
So now, that's confirmed : writing is slower than reading.

It's consistent with CompressionRatings results. Extrapolating from these figures :
if compressing at a ratio of 2:1, then the ramdrive r+w speed is limited to 525 MB/s.
On decoding the same data 1:2, the speed limit is now down to 455MB/s.
Hey, that's about the same ratio as LZ4 compression/decompression speed difference  ...

LZ4 : confirmed as world's fastest compressor

 After Stephan's SqueezeChart statement on LZ4 being the fastest compressor seen on his public benchmark, LZ4 was once again put to the test, this time by Sami Runsas 's Compression Ratings.

This benchmark is very interesting, since its policy is very clear, its benchmark corpus is intentionally heterogeneous and carefully selected (so much that i use it regularly for calibration), and its emphasis on speed and precision makes it a reliable comparison tool, especially for fast compressors.

It is also heavily multi-thread oriented. Therefore, in order to sustain the comparison, LZ4 needed to be upgraded with multi-threading capabilities, since it would stand no chance when running on a single core against the best-of-breed multi-threaded. That's where enters version 0.9....

And it fares pretty well on its first try.
LZ4 gets top position on both compression and decompression speed, while also providing better ratio than previous king of the hill, the excellent 4x4 from Bulat Ziganshin.
And the difference is pretty large : +50% for compression speed, +25% for decompression speed using less than a full thread to max out, and +9% compression ratio.

As a complement, it's interesting to observe that the decoding speed of LZ4 does not vary by increasing the number of threads. That's because decoding speed is so fast that half a CPU usage is enough to exhaust RAMdisk steam.

With such a speed available, compressing/decompressing data costs about the same time as just copying it ... from a main memory RAM Drive. It opens the way to almost free compression for, well, any usage, even on-the-fly compression of temporary data for instance.

LZ4 is available on its homepage.

Multi-threading compression available : LZ4 v0.9

 Previous versions of LZ4 were displaying promising results using multi-threading, but only in benchmark mode. Now this feature is made fully accessible, with real "file i/o" interface.

You will need a very fast disk drive to experiment with it. In effect, only a RAM Drive can expect to keep fast enough steam to feed LZ4, especially when using multi-threading modes.

Block subdivision method was selected, due to its design simplicity and scalability. Compared with previous versions, even single thread mode greatly benefits, since multi-threading requires asynchronous data loading, which means that reading and writing to the disk is done in parallel with compression. 

I can't really test beyond 2 threads, since i only have dual-core systems within reach, but the code should prove pretty scalable with quad-core systems and more (up to 32 threads).

You can download and test this new version on the LZ4 homepage.

LZ4 on steroids : version 0.8

Back to playground. It's always nice to work with LZ4, since its layout is very easy to test new ideas.

In this case, i wanted to check the principle of selective sampling, but this time purely in order to improve speed. This is a bit different from Zhuff, which used this idea to improve compression.

As stated in an earlier post, increasing speed is achieved by decreasing the number of samples. However, since LZ4 is a pure LZ77 compressor (using offset to identify repeated patterns), it also means that reducing samples can only decrease compression. Therefore, this is a matter of trade-off.

The end result achieved with LZ4 version 0.8 seems really interesting. On average, we end up with a 0,05% compression loss, and achieve a more than 10% speed boost. This is almost an unfair trade-off.

Don't be fooled by this "10%" average value, since it hides some very vast differences. Effectively, some files will gain a lot, while others will not get any benefit. For instance, an almost incompressible file can get a speed improvement of more than 500%, while another file with no possibility to "discard" elements, such as enwik8, will not see any performance improvement. But this is still an interesting bet "on average".

While at it, i also modified the multi-threading code branch. The new behavior is now much closer to an I/O algorithm, which makes it more representative of real usage. It also results in a slightly faster operation.

And finally, there is a new checksum algorithm, which ensures compression results are correct.

The resulting binary is rightly available here, and can be tested on your system.

	version	Compression Ratio	Speed	Decoding
LZ4 "Ultra Fast"	0.7	2.062	232 MB/s	805 MB/s
LZ4 "Ultra Fast"	0.8	2.061	260 MB/s	810 MB/s
LZ4 "Ultra Fast" - 2 threads	0.7	2.062	430 MB/s	1510 MB/s
LZ4 "Ultra Fast" - 2 threads	0.8	2.061	500 MB/s	1510 MB/s

Multi-threaded compression experiment : LZ4 version 0.7

Putting into practice conclusions from an earlier post on multi-threading, I finally created a code branch using multi-threading for LZ4.
This is an opportunity to present version 0.7, which for now limit multi-threading to the "benchmark mode" only.

Results are interesting : speed improvement is very noticeable.
However, using 2 threads does not translate into exactly X2 performance (we are more into the +80-90% range).

There are at least 2 reasons for this (that i have identified).
First, not all segments compress as fast as others. This is expected : compression speed is partly dependent on file type being compressed. On a large file, some segments are easier and faster to compress than others. This is exactly what's happening here : i'm effectively impacted by the "slowest segment" which decides the final speed of algorithm.
As an interesting side-effect, using more threads than cores can sometimes lead to increased performance, which is counter-intuitive, but is simply a proof that by "distributing the load", we avoid having one thread with an "easy part" to compress, then waiting for the second one with a "worse part" to handle.

As a consequence, a more clever way to "segment" input data would help to improve the issue.

Second, there are some limits which cannot be improved, in this case, the bus speed between CPU and main memory. On reaching 2GB/s, there is a kind of "wall speed" which cannot be crossed. This effect is not too large with "only" 2 threads, but on quad-core systems is likely to have an impact, especially for decoding speed. There is nothing which can be done to improve upon this. But hopefully, this is not that much of an issue, since working at "memory bus speed" is quite fast enough.

Anyway, here are the results for the current version :

	version	Compression Ratio	Speed	Decoding
LZ4 "Ultra Fast"	0.7	2.062	232 MB/s	805 MB/s
LZ4 "Ultra Fast" - 2 threads	0.7	2.062	430 MB/s	1510 MB/s

Since i only own a 2-cores system, i can't really test for more threads. But the code allows for up to 32 threads. So feel free to test on your own rig.

You can download the new version here.

Huff0 : Early detection offers better speed (v0.7)

 In my earlier release, i skipped the integration of a simple to understand but more difficult to execute feature : early detection of border-cases segments.

This definition regroups both "not compressible segments" and "single character segments". The previous algorithm was correctly detecting these cases, but during the construction of the Huffman tree.

The new algorithm ensures these situations are detected before any operation is done to build the tree. It does so by counting differently, in a new structure created for this purpose. The net result is a speed improvement for files which feature such situations :

Detailed performance assessment :

		Huff0 v0.6			Huff0 v0.7
	Ratio	Compress	Decoding	Ratio	Compress	Decoding
Not compressible
enwik8.7z	1.000	810 MB/s	1.93 GB/s	1.000	870 MB/s	1.93 GB/s
Hardly compressible
win98-lz4hc-lit	1.024	465 MB/s	600 MB/s	1.024	485 MB/s	600 MB/s
audio1	1.070	285 MB/s	280 MB/s	1.070	285 MB/s	280 MB/s
Distributed
enwik8-lz4hc-lit	1.290	204 MB/s	194 MB/s	1.290	204 MB/s	194 MB/s
Lightly Ordered
enwik8-lz4hc-offh	1.131	197 MB/s	184 MB/s	1.131	197 MB/s	184 MB/s
Ordered
enwik8-lz4hc-ml	2.309	214 MB/s	195 MB/s	2.309	214 MB/s	195 MB/s
Squeezed
office-lz4hc-run	3.152	218 MB/s	202 MB/s	3.152	218 MB/s	202 MB/s
enwik8-lz4hc-run	4.959	245 MB/s	224 MB/s	4.959	245 MB/s	224 MB/s
Ultra compressible
loong	275	785 MB/s	2.93 GB/s	275	860 MB/s	2.93 GB/s

This (mostly) closes the gap with Range0 regarding the detection speed of not compressible segments, which is the main case to consider for real-life situations.

You can download and test the new version here :
http://fastcompression.blogspot.com/p/huff0-range0-entropy-coders.html