Open Source Streaming API for Compression

[harry]

Hi all,

This is my first post so be gentle if I'm talking nonsense, Note... when I say
nonsense I don't mean I'm about to tell you I can compress random data, that's
something else entirely.

I've been messing around with compression for a while and started with a PPM0
model and a 64 bit arithmetic encoder. This has sort of snowballed into a
threaded streaming API that could be used by most compressors. I expect that
someone has already written something in this area, if so I'd love some
pointers at previous work. I'm aware that zlib has a streaming api, the library
I'm working on (libdach) would be generalizing this for anyone to use.

I've started a web page on it here that lists some of the ideas for the
library.

http://libdach.com/

I'd like to know if this is an exercise in folly ie it's not needed, it's
done already, or unlikely to be used by anyone due to [insert reason here].

[Piotr Tarsa]

There's ZPAQ which has lots of features, is well tested and reliable. What about extending ZPAQ/ libZPAQ instead of creating (some sort of) alternative from scratch?

I remember Guillaume Voirin put a lot of effort into streaming API and it seems he abandoned his project ( https://github.com/centaurean ).

Probably before you start doing your own API, look at existing ones, try to extend them and ascertain whether they can be restructured for your need in reasonable amount of time. Armed with knowledge of shortcomings of existing APIs and issues the authors had to overcome you can start your own API and it will make more sense then.

[harry]

The intention is not to create an alternative to zpaq or any compressor, besides zpaq has most of what I'm talking about anyway ie it's got a streaming API using blocks and decompresses each block in parallel. I'm suggesting a library/container that a compressor writer can use to get a Streaming API with threads etc without having to write all the plumbing. I think xz is the closest one I've seen out there to being general enough for anyone to use, it's also public domain and that makes things a bit simpler. I suppose the elevator pitch is along the lines of the Apache Portable Runtime ie the Compression Portable Runtime (CPR is an unfortunate TLA and might be suggestive of what any such project might need to get started, Encoding Portable Runtime might be more fitting)

I had a look at Density. It looks like a well written library, it took about a 1/4 sec to get enwik8 to ~53Mb and I'm not sure it used threads to do it.

[Piotr Tarsa]

I think implementing basic multithreading is not a problem nowadays. Newest iterations of C/ C++ have lots of concurrency facilities built in. Java has had easy threading for a long time. So I don't think yet another multithreading framework would be interesting to experimenter.

Streaming API is needed for someone who already has completed making, tuning and testing his compression algorithm. But the algorithm would have to be relatively very good to give sense to implementing a streaming API.

What is missing in compression scene is a good parameter optimizer. Christopher Mattern (http://encode.su/members/15-toffer) made a genetic algorithm based optimizer, but it was rather simple thing without much features. There are lots of opportunities here. I think that e.g. optimizing parameters in PAQ could be done much faster than simply spawning one PAQ process for every (logical) CPU core. Even a GPGPU could be used here as optimizing parameters often means running the same computations but with different variables contents.

When optimizing parameters you have to run actual computations, but the actual computation can be split to two parts: one that does not depend on the tuned constants and the rest. Computations that don't depend on the tuned constants can be cached and the rest can be parallelized.

Eg:
- optimizing PAQ parameters,
- optimize only mixer coefficients,
- outputs from models could be easily cached as they don't depend on mixer coefficients,
- mixing is very computationally expensive but also rather low on memory pressure except a small area, so, when run in multiple instances at once, is ideal for GPGPU implementation,

[nburns]

I'd like to know if this is an exercise in folly ie it's not needed, it's
done already, or unlikely to be used by anyone due to [insert reason here].

If you want to work in general-purpose compression, you have to get over worrying that no one will use your stuff.

Probably before you start doing your own API, look at existing ones, try to extend them and ascertain whether they can be restructured for your need in reasonable amount of time. Armed with knowledge of shortcomings of existing APIs and issues the authors had to overcome you can start your own API and it will make more sense then.

zlib's API feels just plain clunky and inelegant. It does seem to work, and that's an underrated feature. But it can't be the final word.

I think implementing basic multithreading is not a problem nowadays. Newest iterations of C/ C++ have lots of concurrency facilities built in. Java has had easy threading for a long time. So I don't think yet another multithreading framework would be interesting to experimenter.

Streaming API is needed for someone who already has completed making, tuning and testing his compression algorithm. But the algorithm would have to be relatively very good to give sense to implementing a streaming API.

I think it could be worth it to create some kind of plugin-API type of thing for compression. It would introduce consistency and make compression code easier to run and benchmark.

[harry]

If you want to work in general-purpose compression, you have to get over worrying that no one will use your stuff.

Other than educational value to me no one using it would make it a mostly pointless exercise.

[Jarek]

If you want it to be used, it needs to be somehow exceptional among alternatives.
For example offering compression+encryption at great speed, what can be now easily achieved with tANS.

[nburns]

Other than educational value to me no one using it would make it a mostly pointless exercise.

The problem is that there's already a huge amount of software for compression out there.