Artifacts when using multi-threaded option

[thierrylamarre]

Hello,

there appears to be a bug when resizing gifs using the multi-threaded option (-j).

Here is an example original image:

And the result where you can see some lines/a square around the moving eyebrow:

The following command was used:
gifsicle -i input.gif -j8 --resize-method catrom --resize-colors 64 -O2 --resize-fit "250x400" -o output.gif

Another example is this image:

which then looks like this:

This second image was resized using also the -U option. It is too complex to resize in a multi-threaded fashion without unoptimizing first:
gifsicle -U -i input.gif -j8 --resize-method catrom --resize-colors 64 -O2 --resize-fit "250x400" -o output.gif

@wilkesybear

[thierrylamarre]

Alright, I think I found the issue in the first example:
the condition here: https://github.com/kohler/gifsicle/blob/master/src/xform.c#L1276-L1281
does not check the position of the last frame.
I'll submit a PR for this tomorrow.

[thierrylamarre]

I believe #62 should fix the first example.
The second one seems to be a separate issue. I can open a different ticket for it if you'd like.

[thierrylamarre]

Note that the second issue definitely seems caused by the threaded code since the image looks fine without the -j option and we can see that the resulting image is non-deterministic when using the -j option: different calls to gifsicle to resize this same image yields different output images.

[thierrylamarre]

Hi there,
I've started digging into the second issue and from my very incomplete understanding of the code so far i'm wondering if there isn't an issue with the global colormap:

• at the end of each frame scaling, the colormap is updated via scale_image_complete() => scale_image_add_colors() => Gif_AddColor()
• it is accessed in other places. Notably at the beginning of each frame scaling to build the kd3_tree via scale_image_prepare() => kd3_init_build() as well as in scale_image_prepare() => ksscreen_init() and kcscreen_init() for example.

I believe this is not thread-safe.
And even more importantly, I'm wondering if this logic works properly when done in parallel for each frame? I can't quite say with my limited understanding but I'm guessing the code in kd3_init_build() assumes previous frames colors were already added to the colormap which is typically not the case with threaded resizing.
Additionally, the colors in the colormap may change from the time kd3_init_build() is called in scale_image_prepare() to the time scale_image_complete() is called due to other frames scaling completing in-between, which would render the kd3_tree data "stale". Isn't this a logical issue?

[thierrylamarre]

I made a couple experimental branches to try to dig into this colormap thing.

Colormap thread-safe access + rebuilding kd3_tree on complete:
master...thierrylamarre:threaded_colormap_experiment
It adds mutexes around what I believe are the non-thread-safe global colormap accesses.
It also adds a step the re-build the global kd3_tree at the beginning of each scale_image_complete(). Of course this is a hack and not quite correct logically I think. It does produce good-looking images though maybe hinting at this really being the source of the issue.

Global to local colormap:
master...thierrylamarre:threaded_global_colormap_to_local
To avoid non-thread-safe global colormap accesses, I wondered if copying the global colormap to be a local colormap on each frame that doesn't already have one would work.
Unfortunately, the results look off to me and the resulting images produced are much heavier (byte-size) than normal which is a problem for our web use.

Here's an example image:

No threading (gifsicle -i input.gif --resize-method catrom --resize-colors 64 -O2 --resize-fit "250x400" -o output.gif):

With threading and mutexes + kd3_tree rebuilding (gifsicle -U -i input.gif -j8 --resize-method catrom --resize-colors 64 -O2 --resize-fit "250x400" -o output.gif):

With threading and global-to-local colormap copy (gifsicle -U -i input.gif -j8 --resize-method catrom --resize-colors 64 -O2 --resize-fit "250x400" -o output.gif):

We can see on the bright red parts of the gif that the darker pixels are "blinking" which is not the case for the other ones.

The original is:

edit: here's how it looks with the current code using gifsicle -U -i input.gif -j8 --resize-method catrom --resize-colors 64 -O2 --resize-fit "250x400" -o output.gif:

[wilkesybear]

@thierrylamarre what is the performance cost of using the mtuxes + kd3_tree rebuilding? From visual inspection of the above, it definitely looks very close (or identical?) to the non-threaded resize, and there is no flickering as you mention.

[thierrylamarre]

@wilkesybear performance, in terms of the time it takes to resize an image regardless of cpu usage which is what the multi-threading is meant to improve, is almost the same as using single-threaded 😞. What's killing it is adding these rather large critical sections, making it near-single-threaded in practice.

[kohler]

I'm not sure this problem is as big as you imply. Every thread has its own global kd3_tree. There certainly is a multithreading problem with access to the global colormap in scale_image_add_colors.

[kohler]

Please see 2e136b4, which is like your threaded_colormap_experiment but with much smaller critical sections: Only the actual accesses to the global colormap are protected with a mutex. Since each thread has its own kd3_global tree, there is no need to protect access to that tree. Since the global colormap is only extended (never shrunk), there is no need to rebuild the tree each time. But we do need to retry the resize if the global colormap changes. This can cause some wasted work, but it's only likely to happen at the beginning of the resize.

Your GIF resized with this commit:

(I'm still not sure whether I think threaded resize is a good idea overall. Multithreading is hard, the required unoptimization step is expensive, there might still be bugs, etc., etc.)

But thanks for finding the issue! Let me know if this commit does or doesn't work for you.

[thierrylamarre]

Thanks a lot!
It works like a charm and performance remains good with this fix.

I can't blame you if you decide not to support multi-threading going forward. It's very useful to us but it's a very niche use-case and I understand you may not want to continue having to maintain it.

Thanks again!
I'm closing this issue since it is fixed.

[kohler]

Thank you for finding the issue and your debugging work!