Saturday, March 12, 2011

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

RatioCompress DecodingRatioCompressDecoding
Not compressible

enwik8.7z1.0001.42 GB/s1.91 GB/s1.0001.50 GB/s1.94 GB/s
Hardly compressible

win98-lz4hc-lit1.024850 MB/s995 MB/s1.024905 MB/s995 MB/s
audio11.070540 MB/s525 MB/s1.070560 MB/s530 MB/s

enwik8-lz4hc-lit1.290395 MB/s375 MB/s1.290400 MB/s380 MB/s
Lightly Ordered

enwik8-lz4hc-offh1.131375 MB/s350 MB/s1.131380 MB/s360 MB/s

enwik8-lz4hc-ml2.309375 MB/s380 MB/s2.309375 MB/s385 MB/s

office-lz4hc-run3.152330 MB/s310 MB/s3.152420 MB/s400 MB/s
enwik8-lz4hc-run4.959475 MB/s430 MB/s4.959480 MB/s430 MB/s
Ultra compressible

loong2781.49 GB/s3.22 GB/s2781.98 GB/s3.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.

No comments:

Post a Comment