current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 7 down vote favorite

I spent the past hour trying to optimize a block of code I wrote that renders a simple coloured line directly to a backbuffer.

I've compared it with one of the DrawLine method implementations of the WriteableBitmapEx project, and found that my algorithm isn't quite as fast (unless I use Parallel).

public static unsafe void DrawLineVector(this IntPtr target, Line2D line, int colour, int width, int height)
{
    var buf = (int*) target;
    var start = line.Start;
    var lineVector = line.Stop - start;
    var steps = (int)lineVector.Magnitude();
    var uX = lineVector.X / steps;
    var uY = lineVector.Y / steps;
    var col = colour;
    Parallel.For(0, steps, i =>
    //for (var i = 0; i != steps; ++i)
    {
        var x = start.X + uX * i;
        var y = start.Y + uY * i;
        if (x > -1 && y > -1 && x < width && y < height)
            buf[(int)y * width + (int)x] = col;
        //x += uX;
        //y += uY;
    }
    );
}

Note, the Line2D object is basically just a container for two VectorD objects (which are my own implementation of vectors).

Running this as it is currently, will get me, on my machine, roughly 300MPixels per second, while the "default" DrawLine method fromWriteableBitmapEx gets me around 170MPixels per second. If I use the 'serial' version of this (i.e. not useParallel`), I get around 100MPixels per second.

Is there any way I can optimize this further?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

Because you're comparing your performance with that of the WriteableBitmapEx project, you might like to compare your algorithm with theirs, which is here on github: WriteableBitmapShapeExtensions.cs

You say your performance isn't much slower than theirs (100 versus 170 MPixels/second).

A difference between yours and there's might be that yours is using float or double arithmetic, whereas theirs is using int arithmetic.

Their code is much longer (more lines of code) than yours, but their inner loop is something like this:

        for (int x = x1; x <= x2; ++x)
        {
           pixels[index] = color;
           ys += incy;
           y = ys >> PRECISION_SHIFT;
           if (y != previousY)
           {
              previousY = y;
              index += k;
           }
           else
           {
              ++index;
           }
        }

Note:

  • Only int (not double)
  • Few branches
  • Every write is to a significant pixels (in your algorithm if you write a line at 45 degrees then you do 1.414 writes per pixels).
share|improve this answer
    
Yeah, I did think about that. I'm not sure if there's any 'smart' way of avoiding the overdraw of my algorithm, at least not right now. - Thanks again for your time, and your analysis :) –  t0yk4t Mar 16 '14 at 9:40
1  
Instead of var steps = (int)lineVector.Magnitude(); would it work to do var steps = (int)Math.Max(lineVector.X,lineVector.Y;? That would be fewer steps (if it's a slanted line) but still every pixel. –  ChrisW Mar 16 '14 at 10:50
    
The line wouldn't be long enough if it is angled. If we assume we have a line from 0,0 to 5,5 then the actual length would need to be about 7.07 pixels to cover the distance (Hypothenuse), while the "Max" approach would only draw 5 pixels. –  t0yk4t Mar 16 '14 at 11:15
    
@MelanieSchmidt But IMO you should only want to draw 5 pixels, i.e. [0,0], [1,1], etc., through [5,5] –  ChrisW Mar 16 '14 at 11:26
    
Right, didn't realize that. One modification though. (int)Math.Max(Math.Abs(lineVector.X), Math.Abs(lineVector.Y)) - Since x and y can be negative. –  t0yk4t Mar 16 '14 at 11:40
up vote 1 down vote

I'm curious about why the code starts with if (x > -1

Doesn't that mean you need to scan values of i which end up doing nothing?

Perhaps you could skip those stages; something like:

var initial_i = 0;
if (start.X < 0)
    // need a bigger i to make it visible
    initial_i = -start.X / uX;

The above needs to be changed in uX can be negative, and beware floating point and divide by zero.

Do something similar (i.e. increase initial_i) to ensure that y is visible.

Then do something similar to ensure that i is not too large.

Then you ought to be able to have code like,

Parallel.For(initial_i, ending_i, i =>
//for (var i = 0; i != steps; ++i)
{
    var x = start.X + uX * i;
    var y = start.Y + uY * i;
    // if (x > -1 && y > -1 && x < width && y < height)
    buf[(int)y * width + (int)x] = col;
}
share|improve this answer
    
The problem with that would be to take in to account all the four 'sides' of the backbuffer, meaning I'd have to check both negative x, negative y, and positive x and positive y. Since a line can be both from -x to +x, and from +x to -x (And the same for y). But thanks for the suggestion! –  t0yk4t Mar 15 '14 at 22:53
    
A 'branch' i.e. a conditional jump is slow because of CPU branch prediction, so I was hoping that removing all those if expressions would make it faster. –  ChrisW Mar 15 '14 at 22:58
    
Yeah, I figured - I'll try tinkering with it a bit, see if I can't get that "iffy" branch out of the loop. Would require more complexity before the loop though, I think... Unless I can figure out a way to do the 'offsetting' correctly, with a bit of maths. The other thing I'd have to take in to consideration in that case, would be lines that don't ever intersect with the backbuffer at all. I'd initially done some nasty intersection checking in a method that uses this one, but decided not to do that here, yet. –  t0yk4t Mar 15 '14 at 23:04
    
Minor update: I've tried just removing the branch from the loop, and the improvement is marginal at best. It would of course be great to not step through the points outside the backbuffer, but the branch itself doesn't appear to be very expensive. –  t0yk4t Mar 15 '14 at 23:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.