Yaz compression horrendously slow

[narahiero]

While testing SZS creation (U8 archive compressed with Yaz0), I was taken aback by how slow the compression was. I tested some other programs and they all took much less time to compress the same data.

Here is a table of the stats of some tools when compressing the same data (6,034 KB).

Tool name	Time taken	Compression quality
CTools (MrBean35000vr & Chadderz)	< 1 sec	3,875 KB (36 %)
Wexos's Toolbox (Wexos)	~2 sec	3,463 KB (43 %)
Wiimms SZS Tools (Wiimms)	~3 sec	3,190 KB (47 %)
CT Lib	38 sec!!!	3,190 KB (47 %)

As you can see, Wiimms SZS Tools compresses as well as CT Lib, but is 10 times faster.

So the algorithm definitely needs some improvements. One enhancement I can think of right off the bat is to use raw pointers instead of a buffer, as it does bounds checking on every put/get operation.

[narahiero]

I just modified the compression code to only use raw pointers (to get rid of the Buffer class), but the compression time is unfortunately the exact same.

Looks like the problem is the algorithm itself... *sigh*

[narahiero]

Guess this issue will stay opened for a while. I can't think of a single way to improve the algorithm at the moment.

I might add some compression level in the near future as a temporary 'fix', but I know the algorithm can greatly be improved (Wiimms SZS Tools shows this).

[narahiero]

Alright! The commit I just made drastically improves performance, while retaining the same high compression quality.

Here is the updated tools' stats table as shown in the original post (6,034 KB).

Tool name	Time taken	Compression quality
CTools (MrBean35000vr & Chadderz)	< 1 sec	3,875 KB (36 %)
Wexos's Toolbox (Wexos)	~2 sec	3,463 KB (43 %)
Wiimms SZS Tools (Wiimms)	~3 sec	3,190 KB (47 %)
CT Lib	6 sec	3,190 KB (47 %)

6 seconds! Yes! Thats 6 times faster than the old algorithm (38 seconds). Obviously, Wiimms SZS Tools is still the better one, but at least the speed of CT Lib is acceptable.

The only drawback of this new algorithm is that 4 MB of additional memory is allocated, which is used to make a table with the offsets to the occurrences of all possible byte values.

So, there's obviously still room for improvement, but I'd say it's good enough for now.

And I was saying that I had no idea on how to improve the algorithm 6 hours ago. LOL