Program seems to find new compressions to make after multiple runs (?)

[EnderNon]

See my commits here https://github.com/EnderNon/Wynntils-jpegnoise-fix

So basically what happened was:

• Ran these for initial commit:
  • oxipng -o max --strip all --alpha **/*.png in common/src/main/resources/assets/wynntils/textures,
  • then ran oxipng -o max --strip all --alpha logo.png in common/src/main/resources/assets/wynntils
  • creating the commit refactor: compress every image lossless
• Realised logo.png became slightly dimmer,
  • so I regenerated file from before I touched it, with oxipng -o max --strip safe --alpha **/*.png
  • creating the commit fix: use '--strip safe' on logo.png instead. Full command: 'oxipng -o max --strip safe --alpha logo.png'
• Then a contributor to upstream Wynntils asked to see what happens if you were to run the first command from the first commit again.
  • It modified some files here, creating this commit run oxipng again
• Running it again afterwards showed in the output that there was no new differences.
  So for some reason, running the command once wasn't enough to achieve max savings - running it twice was necessary. Seems like a bug.

[andrews05]

Hi @EnderNon, thanks for the report.

Analysis of map_icon.png: The palette sorting evaluations are all tied for best result. When this happens it chooses the one that was performed first.
In the first run, the luma sort is performed first and this is what is selected for the output. In the second run, the luma sort is skipped because it is the same as the input, so the battiato sort is selected instead. The input "baseline" is always evaluated last, so it is never preferred in the case of a tie and is why a second run may give a different result. A third run would end up the same as the first and can therefore never produce further improvement.

I'll have to consider if there's anything we can improve here but my initial thought is to just keep it as-is. If we were to change it to, e.g., prefer the input baseline in the case of a tie, then you would be stuck with the first result and never achieve the smaller size of the second run.

[AlexTMjugador]

A somewhat naive initial idea I'm thinking is that choosing one of the tied sorts at random, or from some tuned probability distribution, could be an improvement overall if the expected final size is less than just always sticking with the first, but doing that comes with its own set of gotchas related to reproducibility... Perhaps there is something better than that though.

[TPS]

Maybe, if running multi-threaded anyway, run all of these tied (& close-to-tied) palette sorts in parallel? Kinda like CPUs do predictive branching?

[andrews05]

A somewhat naive initial idea I'm thinking is that choosing one of the tied sorts at random, or from some tuned probability distribution, could be an improvement overall if the expected final size is less than just always sticking with the first, but doing that comes with its own set of gotchas related to reproducibility... Perhaps there is something better than that though.

Yeah, determinism is important. Perhaps we could just adjust the order so that, e.g. mzeng is preferred if we know it's usually the best one.

Maybe, if running multi-threaded anyway, run all of these tied (& close-to-tied) palette sorts in parallel? Kinda like CPUs do predictive branching?

Indeed, I still plan to get around to #523 someday...

[ace-dent]

@andrews05 -

Yeah, determinism is important.

Yes, it seems Users value this; personally I just want smallest file size and can accept multiple runs when using a batch script and brute force.

Perhaps we could just adjust the order so that, e.g. mzeng is preferred

I'm always using oxipng in combination with multiple other compression engines. Sometimes it's preferable to retain a previously optimised palette when tied (e.g. I have hand-crafted it). Sometimes we might want to expose a newly sorted palette to other engines when tied... perhaps this should be configurable as a parameter...? 🤔

[andrews05]

Yes, it seems Users value this; personally I just want smallest file size and can accept multiple runs when using a batch script and brute force.

So with all the combined tweaks here, we're actually coming out better off in a single run than we were with multiple runs before. See results in #674.

I'm always using oxipng in combination with multiple other compression engines. Sometimes it's preferable to retain a previously optimised palette when tied (e.g. I have hand-crafted it). Sometimes we might want to expose a newly sorted palette to other engines when tied... perhaps this should be configurable as a parameter...? 🤔

This will become moot if/when #523 happens. A "tie" usually only occurs within the reduction evaluations which use fast compression. If we were to run full compression trials on all tied candidates it would (most likely) resolve the tie with one being clearly smaller.