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.

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.

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?