> Here I should note that Python is not the best choice for CPU-bound software. I want to take the opportunity to learn Zig.
For optimizing CPU-bound operations in Python, there’s some low hanging fruit with numba. I would recommend this as a 5-minute solution to you limiting your algorithm because regular Python is too slow. I regularly tell people that if their Python program is slow enough to take several minutes, you could probably learn numba before it finishes.
For exhaustive searches, a library like or-tools or clingo can speed things up a lot. But first you have to figure out how to express your problem declaratively.
I used cursor to port it to rust as well, and it got the conversion time down to 20s. Still likely not worth it as even with the rust port it's a 400x increase in processing time (that scales exponentially) for a ~2% decrease in size.
> We need to be careful here, because finding the actual best compression for an arbitrary format can be equivalent to solving the halting problem.
I don't see why that would be relevant here. The goal is to find the best compression of a given source among all possible DEFLATE streams, not to find the best compression of a given source among all possible ways to compress data. There are only so many DEFLATE streams shorter than the original source, you "simply" try them all, and then you've halted. That said:
> Now, Zopfli is the software that performs an exhaustive search across all possible syntactically valid streams
Maybe I don't understand LZ77 as well as I thought, but surely the search space is way too big to exhaust?
Love the goal of supporting ancient browsers. What I’m missing in the article about images is images. For example the achieved results and some table of the amount of space saved using the compression methods described. Nonetheless interesting read.
I agree, it would be way more interesting to see a table of original GIF sizes versus the improved size. I'm left wondering how bad the plain greedy version is on a typical image.
Cool effort! I appreciated the background into the why, as initially I thought this would have to do with optimizing animated GIFs and didn't realize there was a usecase for single frame GIFs anymore.
> Here I should note that Python is not the best choice for CPU-bound software. I want to take the opportunity to learn Zig.
For optimizing CPU-bound operations in Python, there’s some low hanging fruit with numba. I would recommend this as a 5-minute solution to you limiting your algorithm because regular Python is too slow. I regularly tell people that if their Python program is slow enough to take several minutes, you could probably learn numba before it finishes.
For exhaustive searches, a library like or-tools or clingo can speed things up a lot. But first you have to figure out how to express your problem declaratively.
PyPy is an option too.
Nice advice
Neat. I tested it and here were my results:
ffmpeg conversion: 1,515 bytes, 0.05s
zgif conversion: 1,479 bytes, 90.1s
I used cursor to port it to rust as well, and it got the conversion time down to 20s. Still likely not worth it as even with the rust port it's a 400x increase in processing time (that scales exponentially) for a ~2% decrease in size.
> We need to be careful here, because finding the actual best compression for an arbitrary format can be equivalent to solving the halting problem.
I don't see why that would be relevant here. The goal is to find the best compression of a given source among all possible DEFLATE streams, not to find the best compression of a given source among all possible ways to compress data. There are only so many DEFLATE streams shorter than the original source, you "simply" try them all, and then you've halted. That said:
> Now, Zopfli is the software that performs an exhaustive search across all possible syntactically valid streams
Maybe I don't understand LZ77 as well as I thought, but surely the search space is way too big to exhaust?
> We need to be careful here, because finding the actual best compression for an arbitrary format can be equivalent to solving the halting problem.
That sentence was pasted unmodified from the LLM output.
Too big to exhaust... the concluding sentences of the article contain the details. "Hybrid search with pruning" is the current state of the codebase.
That's where OP ended up, I was disputing the description of zopfli.
Love the goal of supporting ancient browsers. What I’m missing in the article about images is images. For example the achieved results and some table of the amount of space saved using the compression methods described. Nonetheless interesting read.
I agree, it would be way more interesting to see a table of original GIF sizes versus the improved size. I'm left wondering how bad the plain greedy version is on a typical image.
Cool effort! I appreciated the background into the why, as initially I thought this would have to do with optimizing animated GIFs and didn't realize there was a usecase for single frame GIFs anymore.
> didn't realize there was a usecase for single frame GIFs anymore
If the purpose is supporting NCSA Mosaic… I’m content to say that there isn’t. Definitely not “anymore”.
For PNG, there’s ”pngcrush”: <https://pmt.sourceforge.io/pngcrush/>
pngcrush is pretty old. A newer, more effective option is oxipng: https://github.com/oxipng/oxipng