DEFLATE/zlib implementations

[GerryB]

Are there many accessable implementations of DEFLATE around? zlib is polished and liberally licensed and works very well, but what alternatives exist? I'm curious what optimizations people have tried, both for quality and speed tweaks, and maybe multithreaded implementations as well.

The wikipedia article above does list about 10 encoders, but mostly closed source or dead projects. It's unclear whether zlib has any real competitors.

[Fu Siyuan]

I'm not sure if gzip has the same implemention with zlib. Here is gzip

http://www.gzip.org/#sources

The main feature of such DEFALTEs is speed. I think their implementions are fast enough , but no multithreads. I also wonder why the forum talks little about multithread. Today most CPUs are dual-core or quad-core.

[joerg]

here is one interesting zip - implementation - but its more a demo

"The QuickLZ ZIP library will offer light but fast ZIP and deflate compression."

http://www.quicklz.com/zip.html
---
a complete zip is here (with a special paq extension)

"The best ratio compressor(paq8, using the lpaq8 version)
+ the most popular archive file format(zip)"

http://code.google.com/p/paqzip/
---

[Bulat Ziganshin]

joerg, second one is absolutely different thing

there is also open-source 7zip implementation, the rest i know are closed

[joerg]

@Bulat

what do you think about this:

http://compressionratings.com/d_archiver_template.html

a public domain solution for

supporting elementary archiver framework in

a compressor - program

"Public Domain Archiver Template"

"A c++ template that you can use for your programs."

sourcecode to make a archiver-program

---

@GerryB - multithreading in a compression program:

Parallel BZIP2 (full compatible with BZIP2)

http://compression.ca/pbzip2/

win32:

http://www.leszer.net/index.php/my-software.html

[Shelwien]

> Are there many accessable implementations of DEFLATE around?
> zlib is polished and liberally licensed and works very well,
> but what alternatives exist?

What for?
Anyway, for studying deflate algorithm I'd recommend puff.c
from zlib package - there's under 8k of standalone
C source with comments and ifdefs removed.

> I'm curious what optimizations people have tried, both for
> quality and speed tweaks,

Afaik the best zip compression is provided by http://advsys.net/ken/util/kzip.exe
But as to speed I dunno - there's not much reason to speed it up anymore imho,
as its speed is bound by i/o anyway.

> and maybe multithreaded implementations as well.

Well, 7-zip has that I think.
But anyway, multithreaded implementations are not easily portable.
Also there's an implementation in intel IPP library, but afaik its no good.

> The wikipedia article above does list about 10 encoders,
> but mostly closed source or dead projects.
> It's unclear whether zlib has any real competitors.

As to libraries for fast and low-quality compression,
there're lots I think - with their own formats.
And as to deflate specifically - who'd want to compete with
zlib in portability?

> I think their implementions are fast enough, but no
> multithreads.

Well, that might change when a large share of users
would have 1TB/s PCIe SSD cards installed or something like that.
For now there's not much gain in being much faster than i/o.

> I also wonder why the forum talks little about multithread.
> Today most CPUs are dual-core or quad-core.

BWT/CM won't be ever faster than LZ decoding, multi-threaded on not.
Just because LZ works with strings, while other methods work with
bytes or even bits, and its kinda unrealistic to expect a CPU
to store 8 bytes from 8 threads in 1 clock.
But then, there's some maximum speed after which nobody cares,
so lets hope that cpus would evolve fast enough for paq8 to
become practical soon, or something.

If anybody cares, I can also suggest a way for real (not blockwise)
deflate (and other similar LZ) decoding parallelizing.
thread 1: decoding matches/literals from huffman code
thread 2*N: constructing a sparse output with literals and copies
of known data (local matches etc) (there can be a few of such threads
and they can run in loops)
thread 3: filling the gaps and verification

[AiZ]

pigz, which stands for parallel implementation of gzip, is a fully functional replacement for gzip that exploits multiple processors and multiple cores to the hilt when compressing data. pigz was written by Mark Adler, and uses the zlib and pthread libraries. To compile and use pigz, please read the README file in the source code distribution.

http://www.zlib.net/pigz/

[m^2]

Afaik the best zip compression is provided by http://advsys.net/ken/util/kzip.exe
But as to speed I dunno - there's not much reason to speed it up anymore imho,
as its speed is bound by i/o anyway.

In kzip? It definitely isn't and there's a lot of room for improvement.

> and maybe multithreaded implementations as well.

Well, 7-zip has that I think.
But anyway, multithreaded implementations are not easily portable.
Also there's an implementation in intel IPP library, but afaik its no good.

OpenMP is pretty portable.

BWT/CM won't be ever faster than LZ decoding, multi-threaded on not.

Didn't you say the opposite recently? That one could make CM with LZMA decoding speed and better compression?

[Shelwien]

I guess it was provocative enough to get an answer

> > as its speed is bound by i/o anyway.
>
> In kzip? It definitely isn't and there's a lot of room for improvement.

Decoding speed is the same for kzip-generated archivers and any others.

And here's a quick test with a directory containing sources and executables
of some random program (its a slow cpu, i know):

4161950  unpacked
1570036   0.563s  // infozip 2.3
1565043   0.844s  // infozip 2.3 -9
1533995   1.188s  // 7z 4.64 a -tzip
1509658   7.937s  // 7z 4.64 a -tzip -mx9
1509789  48.203s  // kzip

And now, who would care about 4% if its a zip archive anyway?
And reaching hdd speed shouldn't be a problem even with some
simple match sequence optimization.
Anyway, deflate is not the kind of algorithm where tweaking
would bring a lot of compression improvement.

> > > and maybe multithreaded implementations as well.
> > Well, 7-zip has that I think.
> > But anyway, multithreaded implementations are not easily portable.
> OpenMP is pretty portable.

Well, I'd really like it if somebody just gave me a working gcc 4.2+ for iphone.

But I actually talked about a somewhat different kind of portability.
Not about whether a multi-threaded compression library would work at all,
but about _how_ it would work.
Most applications are still not that thread-aware, and ones that are
mostly have some dirty hacks - so quirks after attaching a multi-threaded
compression library are kinda guaranteed.
Though actual problem is still something else - thing is, any speed gain
from multi-threaded implementations is only possible in certain circumstances,
basically when you can process a lot of data at once. And for something
like decoding a 20k web page it would be probably twice slower than
simple single-threaded version (and that's not considering other things).

> > BWT/CM won't be ever faster than LZ decoding, multi-threaded on not.
> Didn't you say the opposite recently?

Its not really a contradiction

> That one could make CM with LZMA decoding speed and better compression?

I said that I think it should be possible to make a _new_ CM with
faster decoding than _current_ LZMA, and somewhat better compression.
And here we're talking about deflate, based on static bitcode, which
I specifically mentioned.

[joerg]

PBZIP2 = Parallel BZIP2

URL: http://compression.ca/pbzip2/

Release: 1.0.5 (Jan. 08, 2009) by Jeff Gilchrist

- full compatible with BZIP2
- "anything compressed with pbzip2 can be decompressed with bzip2"
- uses pthreads
- achieves near-linear speedup on SMP machines

PBZIP2 should work on any system
that has a pthreads compatible C++ compiler (such as gcc).
It has been tested on: Linux, Windows (cygwin & MinGW),
Solaris, Tru64/OSF1, HP-UX, OS/2, and Irix.

win32:

http://www.leszer.net/index.php/my-software.html

--- --- ---

pigz = Parallel Implementation of GZip

URL: http://www.zlib.net/pigz/

Release: pigz 2.1.4 (9 Nov 200 by Mark Adler

- is a fully functional replacement for gzip
that exploits multiple processors and multiple cores

- uses the zlib and pthread libraries

This version of pigz is written to be portable across Unix-style
operating systems.

win32: ... currently no win32-binary


Will it be possible for someone here
to make a port/compile for win32 for testing ?

[SolVanDyck]

How to use zlib becuase all i can get i :? :? :?