[Zlib-devel] pigz 2.1.4 available

[Michael Han]

Several comments on optimization (not specifically related to parallel
computing..also I am interested to hear any suggestions on ideas to
optimize ZLIB, especially deflate, at algorithmetic level without
infringing any patents, to yield faster compression speed).

CRC calculation took a considerable amount of time. Current ZLIB/GZIP
is using a 4 way table look up while a more optimized version existing
in public domain, take a look at
http://sourceforge.net/projects/slicing-by-8
The paper can be found
http://download.intel.com/technology/comms/perfnet/download/slicing-by-8.pdf
Essentially the same with what ZLIB is using, just 8 way look up
instead of 4. In my tests the average speed increased approximately
25% to 30%. The slicing by 8, in turn, can be further optimized by
implementing "real" parallel look ups by distributing them into many
cores, etc..

As for ZLIB, take a look at Intel IPP
http://www.intel.com/cd/software/products/asmo-na/eng/302910.htm
It claims "provides functions for lossless compression methods, such
as those used in the popular "zlib" (inflate and deflate) and
"libbzip2" libraries". I took a brief look at the modified IPP ZLIB
version, there are three major "optimizations" (well, I didn't really
do any profiling yet..):
1. The crc calculation is replaced by a private implementation
2. The memory operations, like moving bytes (zmemcpy...)
3. A new huffman encoding implementation

However, the longest_match, which turns out a hot spot during
compression, is left intact.

Also take a look at the deflate implementation in 7z library. It
sacrifices speed to produce a little bit better compression ratio.

On Tue, Nov 11, 2008 at 2:16 PM, Nguyen Vu Hung <vuhung16plus at gmail.com> wrote:
> On Tue, Nov 11, 2008 at 2:56 PM, Mark Adler <madler at alumni.caltech.edu> wrote:
>> On Nov 10, 2008, at 8:36 PM, Nguyen Vu Hung wrote:
>>> [vuhung at aoclife src]$ time gzip jdk-6u10-linux-i586.rpm
>>>
>>> real    0m7.220s
>>> user    0m4.851s
>>> sys     0m0.379s
>>> [vuhung at aoclife src]$ time pigz jdk-6u10-linux-i586.rpm
>>>
>>> real    0m7.726s
>>> user    0m12.227s
>>> sys     0m0.598s
>>
>>
>> Nguyen,
>>
>> Since for pigz the user+sys time is greater than the real time, it appears
>> that in fact the hyper-threading was being used.  It looks like you're
>> getting about a 60% speedup from the hyperthreading.  To see how threading
>> and not threading compare in a controlled manner, use pigz and pigz -p 1.
> My bad.
>
>>
>> Looking at the user+sys time, gzip on your machine is very fast compared to
>> pigz.  On my machine, pigz is only a little slower than gzip on a single
>> processor.  I wonder if your gzip was compiled with assembler code for
>> longest match, or if the zlib library was not optimized.  Or maybe the
>> default compression level in your gzip was altered.
>
> I am using using CentOS 5.0 gzip-1.3.5-9.el5.centos.src.rpm  which is patched
> for a bigger window size( see below), as far as I can tell, no
> assembler code is there,
> and gzip uses default compression level.
>
> Computers( I mean PC) nowadays have more RAM and CPUs.
> lzma does a good job with very big window size. A good thing about it is that
> the compression takes a looong time but not compression, which is very
> practical in real life uses.
>
> zlib/gzip hogs less memory but the compression ratio is not that good and suits
> for computers with low specs.
>
> Is there any room for improvement? :)
>
> --- gzip-1.3.3/gzip.c.orig      Thu Jan 30 21:19:36 2003
> +++ gzip-1.3.3/gzip.c   Thu Jan 30 21:09:52 2003
> @@ -198,7 +198,7 @@
>  DECLARE(uch, inbuf,  INBUFSIZ +INBUF_EXTRA);
>  DECLARE(uch, outbuf, OUTBUFSIZ+OUTBUF_EXTRA);
>  DECLARE(ush, d_buf,  DIST_BUFSIZE);
> -DECLARE(uch, window, 2L*WSIZE);
> +DECLARE(uch, window, 2L*WSIZE + 4096);
>  #ifndef MAXSEG_64K
>     DECLARE(ush, tab_prefix, 1L<<BITS);
>  #else
>
> --
> Best Regards,
> Nguyen Hung Vu ( Nguyễn Vũ Hưng )
> vuhung16plus{remove}@gmail.dot.com , YIM: vuhung16 , Skype: vuhung16dg
> A brief profile: http://www.hn.is.uec.ac.jp/~vuhung/Nguyen.Vu.Hung.html
> _______________________________________________
> Zlib-devel mailing list
> Zlib-devel at madler.net
> http://mail.madler.net/mailman/listinfo/zlib-devel_madler.net
>



-- 
If first the idea is not absurd, then
there is no hope for it