Tiles data format

[Dmitry Kazakov]

>
>
>  > 2) I was considering swapping, and i wanted to use LZO compression
>
> > algorithm for this. According to some papers it is the fastest. (But
> those
>
> > papers didn't cover LZF). [0]
>
> Well my experimentation show that LZO and LZF are of the same speed order,
> but that LZO compress better. I was leaning toward LZF because LZO seems to
> have a very complex code.
>

I wanted to make abstract encoder to allow testing both =)


> > More than that, effect you were exploring in March can (not sure, again)
> be
>
> > a consequence of this. Original LZ77 algorithm does not depend on the
> size
>
> > of input and almost linear in time (when the size of the input is much
>
> > bigger than the size of the sliding window).
>
> Wikipedia pages on KZ77 [1] explain clearly the meaning of a sliding window
> : "The encoder and decoder must both keep track of some amount of the most
> recent data, such as the last 2 kB <http://en.wikipedia.org/wiki/Kilobyte>,
> 4 kB, or 32 kB. The structure in which this data is held is called a sliding
> window, which is why LZ77 is sometimes called sliding window compression.
> The encoder needs to keep this data to look for matches, and the decoder
> needs to keep this data to interpret the matches the encoder refers to. This
> is why the encoder can use a smaller size sliding window than the decoder,
> but not vice-versa."
>
> It just means that the compression algorithm won't look for similar pattern
> on more than 64kb, it explains why in my March exploration the result with
> LZ77 (zip/libz) is similar when we compress all the tiles at the same time,
> or only one.
>

Did libz show such a result? libz uses 'deflate' algorithm, that is
LZ77+Huffman. The latter part should have made some non-linearity to the
speed. So i find it quite strange.



>  So yes, in theory, it is more efficient to compress a set of tile than an
> individual tile, since we would be able to use data from different tile to
> find patterns.
>

In size - yes, but i'm not sure about the speed. Well, if you compress tiles
one-by-one, with a window bigger than the size of a tile, you may get a good
speed, but my guts say this speed will *not* be optimal.

I have an idea, that if we shrink the window (for example to half-size of a
tile), we will not loose much in compression rate, but we can gain much in
speed. That's an idea.

Grouping, tiles is not a good idea for swapping, you are right. But these
results for tile-by-tile compression are quite strange, maybe, you used
different compression algorithms for tile-by-tile vs entire compression,
e.g. lzf vs zlib?

Btw, it is possible to simply change the size of the sliding window in zlib.
It can change the results dramatically, in case lzf automatically adjusts
sliding window size for a single tile.

> 1) I don't see any reason of writing tile-save-compression system
>
> > separately and before the one that will be used in a swapper. We'll just
>
> > make many code-duplications.
>
> Apart from the compression method, I don't see many code-duplication (and
> if you want my opinion, tile-save-compression is way more important than
> swapper :) it is the last thing that truly annoys me in krita 2.2)
>

Well, first, there is an abstract compressor should be done first, to will
allow swapper to save data in the same format as kra. And life of both of us
will be much easier =)

And second, i'm not sure we interpreted the results of those tests right.
Sliding window size of zlib is configurable and it is big by default, so it
could cause the difference.

If we interpreted them wrong, then it's better to replace (configure)
compression of the KoStore, than to do this change.

PS:
Anyway, if you wish, i can hurry with this abstract compressor a bit. =)

-- 
Dmitry Kazakov
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.kde.org/pipermail/kimageshop/attachments/20100615/39ef41aa/attachment-0001.htm