<div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div style="font-family: 'DejaVu Sans'; font-size: 9pt; font-weight: 400; font-style: normal;">
<br><div class="im">
<p style="margin: 0px; text-indent: 0px;"></p>
<p style="margin: 0px; text-indent: 0px;">> 2) I was considering swapping, and i wanted to use LZO compression</p>
<p style="margin: 0px; text-indent: 0px;">> algorithm for this. According to some papers it is the fastest. (But those</p>
<p style="margin: 0px; text-indent: 0px;">> papers didn't cover LZF). [0]</p>
</div><p style="margin: 0px; text-indent: 0px;">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.</p>
</div></blockquote><div><br>I wanted to make abstract encoder to allow testing both =)<br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div style="font-family: 'DejaVu Sans'; font-size: 9pt; font-weight: 400; font-style: normal;"><div class="im">
<p style="margin: 0px; text-indent: 0px;"></p><p style="margin: 0px; text-indent: 0px;">> More than that, effect you were exploring in March can (not sure, again) be</p>
<p style="margin: 0px; text-indent: 0px;">> a consequence of this. Original LZ77 algorithm does not depend on the size</p>
<p style="margin: 0px; text-indent: 0px;">> of input and almost linear in time (when the size of the input is much</p>
<p style="margin: 0px; text-indent: 0px;">> bigger than the size of the sliding window).</p>
<p style="margin: 0px; text-indent: 0px;"></p>
</div><p style="margin: 0px; text-indent: 0px;">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 <a href="http://en.wikipedia.org/wiki/Kilobyte" target="_blank"><span style="text-decoration: underline; color: rgb(0, 87, 174);">kB</span></a>, 4 kB, or 32 kB. The structure in which this data is held is called a <span style="font-style: italic;">sliding window</span>, which is why LZ77 is sometimes called <span style="font-weight: 600;">sliding window compression</span>. 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."</p>
<p style="margin: 0px; text-indent: 0px;"></p>
<p style="margin: 0px; text-indent: 0px;">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.</p>
</div></blockquote><div><br>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.<br><br> </div>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div style="font-family: 'DejaVu Sans'; font-size: 9pt; font-weight: 400; font-style: normal;">
<p style="margin: 0px; text-indent: 0px;"></p>
<p style="margin: 0px; text-indent: 0px;">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.</p></div></blockquote>
<div><br>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.<br>
<br>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.<br><br>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?<br>
<br>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.<br><br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div style="font-family: 'DejaVu Sans'; font-size: 9pt; font-weight: 400; font-style: normal;"><div class="im"><p style="margin: 0px; text-indent: 0px;">> 1) I don't see any reason of writing tile-save-compression system</p>
<p style="margin: 0px; text-indent: 0px;">> separately and before the one that will be used in a swapper. We'll just</p>
<p style="margin: 0px; text-indent: 0px;">> make many code-duplications.</p>
</div><p style="margin: 0px; text-indent: 0px;">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)</p>
</div></blockquote><div><br>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 =)<br><br>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.<br>
<br>If we interpreted them wrong, then it's better to replace (configure) compression of the KoStore, than to do this change.<br><br>PS:<br>Anyway, if you wish, i can hurry with this abstract compressor a bit. =)<br><br>
</div></div>-- <br>Dmitry Kazakov<br>