The performance of 'DrawLines' degrades the thinner the lines are

[pmcxs]

Prerequisites

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

Description

Drawing thinner lines takes much more time to process than broader lines.

The following tests were done on a 500x500 image (sorted by processing time):

• 100 lines with 10px: 448 ms
• 1000 lines with 10 px: 640 ms
• 100 lines with 1px: 1530 ms
• 1000 lines with 1px: 44680 ms

1000 10px lines render faster than 100 1px lines, which seems strange.

Steps to Reproduce

Option 1

Create a simple project, referencing the latest ImageSharp library and include the code below:

var numberOfLines = 100;  // Update accordingly
var imageSize = 500; // Update accordingly
var lineWidth = 5; // Update accordingly

var lines = new List<int[]>();
var rnd = new Random(1);

for (int i = 0; i < numberOfLines; i++)
{
    int pixelX = rnd.Next(imageSize);
    int pixelY = rnd.Next(imageSize);
    lines.Add(new int[] { pixelX, pixelY });
}

SixLabors.Primitives.PointF[] imageSharpLines = lines
    .Select(r => new SixLabors.Primitives.PointF(r[0], r[1]))
    .ToArray();

PointF[] systemDrawingLines = lines.Select(r => new PointF(r[0], r[1])).ToArray();

var w = new Stopwatch();

w.Start();
using (var image = new Image<Rgba32>(imageSize, imageSize))
{
    image.Mutate(x => x

        .DrawLines(
            Rgba32.Red,
            lineWidth,
            imageSharpLines));

    using (var stream = File.Create($"test-imageSharp-{imageSize}-{numberOfLines}-{lineWidth}.png"))
    {
        image.SaveAsPng(stream);
    }
}
w.Stop();

Console.WriteLine($"Took {w.ElapsedMilliseconds} ms with ImageSharp");

Option 2

This was detected on a comparison between ImageSharp, System.Drawing and a custom simplified implementation. That benchmark is available at: https://github.com/pmcxs/core-linedrawing-benchmark/. It can be executed to replicate the issue:

• Clone the aforementioned repo
• Run it in Release. By default it will do various comparisons, including the ones specified above.

System Configuration

• ImageSharp version: 1.0.0-dev002737
• Environment (Operating system, version and so on): Windows 10 Pro
• .NET Framework version: .NET Core 2.1

[JimBobSquarePants]

Thanks @pmcxs for all the detail.

We're planning on separating ImagSharp.Drawing into a separate repository as we really haven't begun to do the same performance work on that library as we have the main library and we don't want to delay the main libraries RC1 release .

It would be brilliant if you have any advice to give once we do that migration.

[implemental]

Wouldn't a simple explanation behind why larger lines are faster is because the stopwatch includes the PNG saving to disk and larger lines produce a less-complex PNG and therefore improves performance during serialization.

[JimBobSquarePants]

@implemental Yep, that’s definitely a factor. I hadn’t actually looked at the benchmarking code.... it’s not great.

System.Drawing saves png’s at zlib compression level 1 with no filter where we use level 6 with paeth filtering. The encoding speed alone with be 2-3x slower.

[antonfirsov]

There are two factors explaining this:

1. The thinner the lines, the more points will the final tessellated polygon contain (after extending the multiline with the polygon thickness). In my experiment I've seen ~200x more points in the tessellation with the provided repro code with thickness 1px vs 10px EDIT: 200x degenerate, see The performance of 'DrawLines' degrades the thinner the lines are #18 (comment)
2. The performance of the scanning code on current master is very bad, and degrades with the number of (tessellated polygon) points in a non-linear manner.

I don't think we can do anything with (1) since it's just the math behind extending a multi-line to a polygon. (2) will be fixed with #96.

@pmcxs if still interested, check out our nightly builds after we merge that PR (ETA: couple of days).

[antonfirsov]

Actually, (numberOfLines=1000, lineWidth=10) is a degenerate case, where the 500x500 canvas will be filled with mess so I it's not a useful baseline. In normal cases the multiplier between 1px and 10px is much smaller.

I consider this issue to be fixed by #96.