GIF dithering causes massive encoding slowdown

MaryMajesty commented 6 years ago

Prerequisites

[X] I have written a descriptive issue title
[X] I have verified that I am running the latest version of ImageSharp
[X] I have verified if the problem exist in both DEBUG and RELEASE mode
[X] I have searched open and closed issues to ensure it has not already been reported

Description

There are three main points of concern: Saving GIFs with dithering enabled massively slows down the encoding time. When dithering is disabled, decoding and reencoding GIFs is much slower than encoding them for the first time. This is not directly an issue but seems to be related: Setting every frame's DisposalMethod to RestoreToBackground has a positive impact on the time it takes to reencode the resulting image.

Steps to Reproduce

Save this image as "Spritesheet.png" and run the following code:

bool ditheringenabled = true; //Dithering causes a massive encoding slowdown.
bool restoretobackground = false; //This makes reencoding faster.

int spritecount = 10;

Image<Rgba32> img = SixLabors.ImageSharp.Image.Load("Spritesheet.png");
int w = img.Width / spritecount;
Image<Rgba32> gif = new Image<Rgba32>(w, img.Height);

for (int i = 0; i < spritecount; i++)
{
    gif.Frames.AddFrame(img.Clone(ctx => ctx.Crop(new SixLabors.Primitives.Rectangle(w * i, 0, w, img.Height))).Frames[0]);

    //RestoreToBackground causes the reencoding to be much faster.
    gif.Frames[i].MetaData.DisposalMethod = restoretobackground ? DisposalMethod.RestoreToBackground : DisposalMethod.NotDispose;
}

//Disabling the dithering gets completely rid of the initial encoding slowdown.
GifEncoder encoder = new GifEncoder() { Quantizer = new OctreeQuantizer(dither: ditheringenabled) };

DateTime start1 = DateTime.Now;
gif.Save("Result.gif", encoder);
TimeSpan time1 = (DateTime.Now - start1);

Image<Rgba32> reencode = SixLabors.ImageSharp.Image.Load("Result.gif");
DateTime start2 = DateTime.Now;
reencode.Save("Reencode.gif");
TimeSpan time2 = (DateTime.Now - start2);

throw new Exception(time1.TotalMilliseconds.ToString() + " vs " + time2.TotalMilliseconds.ToString());

Here are some benchmarks from my machine:

ditheringenabled = true;
restoretobackground = false;

First encode: 5432 ms Reencode: 4239 ms

ditheringenabled = true;
restoretobackground = true;

First encode: 5454 ms Reencode: 626 ms

ditheringenabled = false;
restoretobackground = false;

First encode: 96 ms Reencode: 3124 ms

ditheringenabled = false;
restoretobackground = true;

First encode: 83 ms Reencode: 530 ms

System Configuration

ImageSharp version:
Other ImageSharp packages and versions: beta 4
Environment (Operating system, version and so on): Windows 10
.NET Framework version: 4.6.1
Additional information:

tocsoft commented 6 years ago

You want to look at output file size too otherwise it's not a fair comparison.

JimBobSquarePants commented 6 years ago

@TodesBrot A couple of issues here with your tests.

You don't dispose of any of your images yet clone for each frame. This adds pressure to the GC.
You're using inaccurate time methods to determine the benchmark result.

That said, I am aware of some performance issues with the gif encoder (unrelated to dithering, we're allocating where we shouldn't and don't handle global color tables) which I have a PR coming for.

RestoreToBackground has no effect on encoding. What you are probably seeing is the consequence of that GC pressure as we do extra work on decoding.

I think it's best here if you understand quite how much extra work goes into dithering.

Dithering is traditionally a serial process with and error calculation passed to neighbouring pixels (bottom, right) that depends on the result of the previous pixel calculation. This dramatically improves the output quality of a palette encoded image We're arguably better than PngQuant at quantization + dithering.

The default dithering algorithm we use is the popular Floyd-Steinberg algorithm developed in 1975. This is represented by the following matrix:

{ 0, 0, 7 },
{ 3, 5, 1 }

For each pixel in the quantized image we have to perform 5 separate operations. 1 on the input pixel and 1 for each of the 4 neighbours. This, of course, adds a lot of processing overhead. Which is unavoidable if you want serious quality (Check out a System.Drawing gif sometime, you'll claw your eyes out.).

Now it may be possible for us to make that a parallel process. According to this document I found anyway but we'll have to see whether it's possible to implement this.

For some images, dithering is not the correct choice. If you have blocky edges, for example like in your sprite. I would turn off dithering. We've chosen to enable dithering by default as most gifs have softer edges and require much higher quality output than sprites.

So... It might be possible to speed up dithering (I'd really like to) but we're going to be no slower with our dithering approach currently than anyone else.

JimBobSquarePants commented 6 years ago

@TodesBrot with #637 I've managed to make gif encoding about 6x faster than it was previously. Output quality is improved also.

SixLabors / ImageSharp