3 ms·
Does this imply zlib and gzip may be able to be patched to reduce memory usage and runtime?
by burntrelish1273 9y ago
Does this imply zlib and gzip may be able to be patched to reduce memory usage and runtime?
- faragon 9y agoRegarding reducing run time, zlib/gzip already use a O(n) algorithm (Rabin-Karp rolling hash search), despite being "slow" in comparison with other "pure-hashing" LZ77 implementations (e.g. LZO, LZ4, LZF). I don't have access to that paper, but "compressing indexes" is likely to be slow, no matter how is implemented: fastest LZ77 using hashing relies on doing few operations per input byte. So no matter if the hash table space could be reduced or not, the speed would not be likely to be faster (anyway, you can trade hash table size vs compression ratio, even without that new technique).
- wolf550e 9y agoIf you can, you should upgrade from DEFLATE (the compression format in zlib, gzip, zip files, png, office docs, etc) to something more modern like zstd. If you must preserve ability to decompress by zlib, there are different implementations of a DEFLATE compressor that are better than zlib (either faster or better compression ratio). A DEFLATE compressor needs to keep a data structure that is able to answer the query "where in the last 32,768 bytes of input there are occurrences of the exact 3 bytes I'm looking at? If possible, check whether the 4th byte matches too and find the longest match. Among matches equally long, prefer those which are closer". For a 32KB window, a data structure that always finds the best match is not large, unless you're on a microcontroller. The size of the data structure becomes a problem when the window is large.