[Tutorial] Benchmarking Draw.ThickLine with Turing

[Tony]

Benchmarking with Turing

wikipedia.org wrote:

In computing, a benchmark is the result of running a computer program, or a set of programs, in order to assess the relative performance of an object, by running a number of standard tests and trials against it.

What is the best way of performing a certain action? On an introductory level it doesn't matter - whatever works will suffice. "Premature Optimization... Don't!" - wtd.

Though when we do get to that end.. when everything works, but we want to make it faster.. how do we judge the performance?

It is assumed that you know your BigO()s, your algorythms are efficient and we are concerned with picking one function over another on the same order of complexity.

A question has been brought up in [Turing Help] on the execution time of Draw.ThickLine.

Mazer wrote:

But also, making your own Draw.ThickLine() probably won't give you results as good as the one Turing already has, speed-wise.

Windsurfer wrote:

Why not? I read somewhere that a lot of turing is made using turing code, so why can't i just tweak it a bit and have it just as fast? Like, sure, maaaybe they coded Draw.ThickLine() in assembly or C, but I ighly doubt it, especially considering how it's a fairly new addition.

I wanted to find out.

The Set Up
{

Turing:

var x1,x2,y1,y2:int var t_start, t_end:int %test out original t_start := Time.Elapsed for i:1..100     x1 := Rand.Int(0,300)     x2 := Rand.Int(0,300)     y1 := Rand.Int(0,300)     y2 := Rand.Int(0,300)     Draw.ThickLine(x1,y1,x2,y2,5,black)     Draw.ThickLine(x1,y1,x2,y2,3,grey) end for t_end := Time.Elapsed - t_start locate(1,1) put t_end

The set up usually takes the following form:

code:

variable declarations and other overhead start timer loop end timer display results

The larger the test loop - the better average result. We are trying to average out whatever noise and spikes that might have occured during the testing. It is also important to isolate the timing as close to the function we're measuring as possible.

If using Rand.Int, it is essential to have a large enough sample set to normalize the outcome. 100 samples is a fairly poor choice for the above test, you would normally want something that runs for at least a second or more, but the next comparison test is considerably slower and 100 samples is sufficient to demonstrate the difference.
}
Alternate Function
{

Turing:

proc MyLine(x1,y1,x2,y2,w,c:int)     var a:real     var width:int := w div 2     %calculate angle of the line     if (x2-x1) = 0 then         if y2>y1 then             a:=PI/2         else             a:=PI*1.5         end if     else         a:=arctan((y2-y1)/(x2-x1))         if x2 < x1 then             a += PI         end if     end if     %for each point on the line     for i:1..round(Math.Distance(x1,y1,x2,y2))         Draw.FillOval(round(x1+i*cos(a)),round(y1+i*sin(a)), width, width, c)     end for end MyLine

This is my attempt at drawing a ThickLine, by constructing it out of circles. A faster approach would have been to draw a number of lines and just round off the corners, but some pixels were being skipped at certain angles, so the function didn't behave the same.

The benchmark test should be performed right after the original, hoping that the system is in a relativly same state of load.

Turing:

t_start := Time.Elapsed for i:1..100     x1 := Rand.Int(300,600)     x2 := Rand.Int(300,600)     y1 := Rand.Int(0,300)     y2 := Rand.Int(0,300)     MyLine(x1,y1,x2,y2,5,black)     MyLine(x1,y1,x2,y2,3,grey) end for t_end := Time.Elapsed - t_start locate(1,10) put t_end

}
Some Conclusions

61 against 1620 - it's not even a contest. Turing's native Draw.ThickLine is much faster to draw. On the other hand I notice that my function results in a more vivid black outline

[Cervantes]

Nice, Tony.

Though I think it would be a good idea to remove the Rand.Int's from the for loop. Just hardcode the coordinates so the line draws over itself every time. This doesn't affect the drawing speed, so we can safely factor out those Rand.Int's that are common to both tests.

[Windsurfer]

I must say, drawing circles? That's no way to draw a line!

Okay, so i made another procedure. It's a little less than half of turing's speed (though it can be sped up to faster than turing at the loss of accuracy!)
I'm still working on it. Maybe I can improve it some more.

code:

procedure DrawFillPoly_Int (x1 : array 1 .. * of int, y1 : array 1 .. * of int, clr : int)     if upper (x1) > upper (y1) then %what is the upper bound         Draw.FillPolygon (x1, y1, upper (y1), clr)     else         Draw.FillPolygon (x1, y1, upper (x1), clr)     end if end DrawFillPoly_Int procedure DrawThickLine (x1, y1, x2, y2, width : real, clr : int)     %find angle     const delta_y := (y2 - y1)     var angle : real     if x1 <= x2 then         angle := arcsind (delta_y / sqrt ((x2 - x1) ** 2 + delta_y ** 2)) + 90     else         angle := 180 - arcsind (delta_y / sqrt ((x2 - x1) ** 2 + delta_y ** 2)) + 90     end if     var xp : array 1 .. 20 of int     var yp : array 1 .. 20 of int     %set points     for lp : 0 .. 9         xp (lp + 1) := round (x1 + cosd (angle + lp * 20) * width)         yp (lp + 1) := round (y1 + sind (angle + lp * 20) * width)     end for     for lp : 9 .. 18         xp (lp + 2) := round (x2 + cosd (angle + lp * 20) * width)         yp (lp + 2) := round (y2 + sind (angle + lp * 20) * width)     end for     DrawFillPoly_Int (xp, yp, clr) end DrawThickLine var last_time : real var test1, test2 : string put "Running... time is in miliseconds..." %These values are completly arbitrary var mouse_x, mouse_y, button : int loop     Mouse.Where (mouse_x, mouse_y, button)     DrawThickLine (120, 120, mouse_x, mouse_y, 30, black)     delay (40)     cls     exit when button = 1 end loop loop     last_time := Time.Elapsed     for lp : 1 .. 10000         Draw.ThickLine (20, 20, 200, 200, 60, black)     end for     test1 := "using turing's built-in: " + realstr (Time.Elapsed - last_time, 5)     last_time := Time.Elapsed     for lp : 1 .. 10000         DrawThickLine (120, 20, 300, 200, 30, black)     end for     test2 := "using my procedure:      " + realstr (Time.Elapsed - last_time, 5)     cls     put test1     put test2 end loop

Using this level of accuracy:
Turing : 1068
Me : 1996

I'm catching up!

[zylum]

the whole point of this tutorial was how to bench mark, not how to draw a thick line efficiently. besides, here's one that draws thick lines more like Turings built in procedure as well as does it faster than yous

code:

proc DrawThickLine (x1, y1, x2, y2, w, c : int)     var x : array 1 .. 4 of int     var y : array 1 .. 4 of int     var m := sqrt ((x2 - x1) ** 2 + (y2 - y1) ** 2)     var i := (y2 - y1) / m     var j := (x2 - x1) / m     var width := w / 2     x (1) := round (x1 + i * width)     x (2) := round (x1 - i * width)     x (3) := round (x2 - i * width)     x (4) := round (x2 + i * width)     y (1) := round (y1 - j * width)     y (2) := round (y1 + j * width)     y (3) := round (y2 + j * width)     y (4) := round (y2 - j * width)     Draw.FillPolygon (x, y, 4, c)     Draw.FillOval (x1, y1, round (width - 1), round (width - 1), c)     Draw.FillOval (x2, y2, round (width - 1), round (width - 1), c) end DrawThickLine

[Windsurfer]

zylum wrote:

the whole point of this tutorial was how to bench mark, not how to draw a thick line efficiently. besides, here's one that draws thick lines more like Turings built in procedure as well as does it faster than yous

I know it's a tutorial, but it is an offshoot of a question i asked earlier. Since this topic is more relevant, I decided to post here.
On your claim that yours is faster:
Not true! I benchmarked using my program, and the timing results are :
Yours : 2860
Mine : 1906

These numbers don't vary by any more than 100 in either direction, btw.

[[Gandalf]]

Before you get into a fight about whose function is faster, may I refer you a previous post of mine showing how inaccurate benchmarking in Turing can be: here.

Now, that may not be the sole reason for the difference in your results, but it's good to keep in mind.

[Windsurfer]

Gandalf, I completly agree with you, which is why i stated about how much the variance that i observed was.

I would also like to say that after further testing, I have discovered that zylum's procedure can be faster when the thickness of the line is 20 or less, but mine wins at larger numbers. I believe that may be due to the differences in time that Draw.FillOval has when dealing with different sizes (as opposed to polygons, which seem to have a more uniform resource use).
I suppose if i wanted to make my procedure better, i would have some sort of equation that relates the size of the thick line to the number of sides on my polygon. (right now it's 20 sides, but if i reduce it to 4 sides, it beats even turings built-in)

[[Gandalf]]

Windsurfer wrote:

Gandalf, I completly agree with you, which is why i stated about how much the variance that i observed was.

Indeed, only there is another factor that you hadn't considered. In my linked post it became obvious that whichever test was started first would run longer or equally as long as the other test. Did you try switching the order in which you tested the procedures?

Of course, I digress. The differences in how the two lines are drawn and the conditions which they are drawn in have a much larger effect on the results of the benchmark than these random deviations.

[Windsurfer]

AHAHAHA!!

OKAY! I was messing with that timing program you made, and i was thinking "this can't be right... wow turing sucks" so i flip the order of the tests, unconviced that order should have anything to do with it. "What the hell???" I get the same results. timeB wins 40 to 60 even. 0 to timeB. I then also make this whole new part of code (thinking maybe there's something else about the code that i'm missing) that randomises the order. SAME RESULTS! 40 to 60 about, plus 0 for timeB. It made NO sense. I was thinking Gandalf was really a wizard.

SO! I keep looking at your code, very conviced that there's something wrong with it... like, HOW can timeB NEVER beat timeA?! i couldn't understand.
Then I found it

code:

put "Test finished..."     var timeALonger, timeBLonger, timesEqual : int := 0     for i : 1 .. upper (timeA)         if timeA (i) > timeB (i) then             timeALonger += 1 % -------   Right here --------         elsif timeB (i) > timeB (i) then             timeBLonger += 1         else             timesEqual += 1         end if     end for     put "Time A longer: ", timeALonger / upper (timeA) * 100, "%"     put "Time B longer: ", timeBLonger / upper (timeB) * 100, "%"     put "Times equal: ", timesEqual / upper (timeA) * 100, "%"

Well THERE you go! Comparing timeB to timeB! Of course it can never be greater!

I fixed it, and what do you know? i get the predicted and theoretical results.

(sorry for bursting your bubble Gandalf)

[Windsurfer]

Sorry that last post was really off topic, but i felt I had to share it, and the old forum that had the original code was locked.

[[Gandalf]]

It's not off topic on a Tutorial about benchmarking. A double post, on the other hand is something to be shamed.

Anyway, dang that was a stupid mistake on my part. Everyone makes mistakes though, especially as simple as mistyping A as B heh. You can never be sure with Turing either.

And who says I'm not a wizard?