Speed Differences

Raknarg · **Posted:** Tue Mar 13, 2012 8:31 pm

I have these two algorithms for making bezier curves. If you test them both out, you'll notice that one is faster than the other:

Turing:

setscreen ("offscreenonly")

type points :
record
x, y : real
end record

var p : array 0 .. 9 of points
var newp : array 0 .. 100 of points
var mx, my, mb : int
var key : array char of boolean

for i : 0 .. upper (p)
loop
Mouse.Where (mx, my, mb)
var valid := false
if mb = 1 then
loop
Mouse.Where (mx, my, mb)
if mb = 0 then
valid := true
p (i).x := mx
p (i).y := my
Draw.FillOval (mx, my, 3, 3, black)
View.Update
exit
end if
end loop
end if
if valid = true then
exit
end if
end loop
end for

proc bezier_calc (pts : array 0 .. * of points, state, n : real)
var pt : array 0 .. upper (pts) - 1 of points
if upper (pts) > 1 then
for i : 0 .. upper (pt)
pt (i).x := (pts (i + 1).x - pts (i).x) * state + pts (i).x
pt (i).y := (pts (i + 1).y - pts (i).y) * state + pts (i).y
if i > 0 then
Draw.Line (round (pt (i - 1).x), round (pt (i - 1).y), round (pt (i).x), round (pt (i).y), RGB.AddColour (1 - n, 0, n))
end if
end for
bezier_calc (pt, state, n - 1 / upper (p))
elsif upper (pts) = 1 then
newp (round (state * 100)).x := (pts (1).x - pts (0).x) * state + pts (0).x
newp (round (state * 100)).y := (pts (1).y - pts (0).y) * state + pts (0).y
if state > 0.01 then
for i : 1 .. round (state * 100)
Draw.ThickLine (round (newp (i - 1).x), round (newp (i - 1).y), round (newp (i).x), round (newp (i).y), 3, brightred)
end for
end if
end if
end bezier_calc

var num : int := 0
loop
cls
Input.KeyDown (key)
if key (KEY_LEFT_ARROW) and num > 0 then
num -= 1
elsif key (KEY_RIGHT_ARROW) and num < 100 then
num += 1
end if
for j : 0 .. upper (p) - 1
Draw.Line (round (p (j).x), round (p (j).y), round (p (j + 1).x), round (p (j + 1).y), grey)
end for
bezier_calc (p, num / 100, 1)
View.Update
end loop

Turing:

%import Stuff
View.Set ("graphics:max;max, offscreenonly")

var X, Y : array 0 .. 100 of int
var mdx, mdy : array 0 .. 9 of real
var num : int := 0

fcn rv (a, b, r : real) : real
result (b - a) * r + a
end rv

proc DrawLines (x, y : array 0 .. * of real, thicknes : int, clr : int, intesity : real)
for a : 0 .. upper (x) - 1
Draw.ThickLine (x (a) div 1, y (a) div 1, x (a + 1) div 1, y (a + 1) div 1, thicknes, clr)
end for
end DrawLines

proc CalcCurveDot (x, y : array 0 .. * of real, r : real)
var lx, ly : flexible array 0 .. 0 of real
for a : 0 .. upper (x) - 1
new lx, a
new ly, a
lx (a) := rv (x (a), x (a + 1), r)
ly (a) := rv (y (a), y (a + 1), r)
end for
DrawLines (lx, ly, 1, 12, 1 - (upper (lx) / upper (mdx)))
if upper (lx) = 1 then
var dx, dy, id : int := round (r * 100)
dx := rv (lx (0), lx (1), r) div 1
dy := rv (ly (0), ly (1), r) div 1
X (id) := dx
Y (id) := dy
else
CalcCurveDot (lx, ly, r)
end if
end CalcCurveDot

var mx, my, bnum, freeze : int := 0
loop
Mouse.Where (mx, my, bnum)
freeze -= 1
if bnum > 0 and freeze <= 0 then
mdx (num) := mx
mdy (num) := my
Draw.FillOval (mdx (num) div 1, mdy (num) div 1, 3, 3, 255)
View.Update
num += 1
if num > upper (mdx) then
exit
else
freeze := 5
end if
end if
delay (20)
end loop
/*
for a : 0 .. upper (mdx)
mdx (a) := Rand.Int (0, maxx)
mdy (a) := Rand.Int (0, maxy)
end for
*/

var seq : int := 2
var keys : array char of boolean
CalcCurveDot (mdx, mdy, 0.00)
CalcCurveDot (mdx, mdy, 0.01)
CalcCurveDot (mdx, mdy, 0.02)
loop
Input.KeyDown (keys)
if keys (KEY_RIGHT_ARROW) or keys ('d') then
seq += 1
if seq > 100 then
seq := 100
end if
elsif keys (KEY_LEFT_ARROW) or keys ('a') then
seq -= 1
if seq < 0 then
seq := 0
end if
end if
CalcCurveDot (mdx, mdy, seq / 100)
DrawLines (mdx, mdy, 1, grey, 0.8)
if seq > 0 then
DrawLines (mdx, mdy, 1, grey, 0.8)
end if
if seq >= 1 then
for b : 0 .. seq - 1
Draw.ThickLine (X (b), Y (b), X (b + 1), Y (b + 1), 3, 48)
end for
end if
Draw.FillOval (X (seq), Y (seq), 2, 2, 255)
View.Update
delay (20)
cls
end loop

I was wondering if someone could explain why that is. My guess would be because of the flexible arrays in the second one, lx and ly.

Dreadnought · **Posted:** Tue Mar 13, 2012 9:02 pm

Which one is supposed to be fastest? After I added a delay of 20 ms to the first program to match that of the second program I didn't see a noticeable difference.

chrisbrown · **Posted:** Tue Mar 13, 2012 9:53 pm

Resizing an array can be very costly. If the next location in memory after the end of the array is in use, it becomes necessary to copy the entire array somewhere else.

As far as I can tell, there's no need for a flexible array at all. Why not just allocate from 0 .. upper (x) - 1? In general though, you want to minimize the number of enlargements you make.

When memory consumption isn't a factor (as is usually the case), a large inflexible array with a size variable is usually a better choice. The only caveat is that it should be passed to functions with the var keyword in the parameter list to pass be reference instead of copying the whole thing.

DemonWasp · **Posted:** Tue Mar 13, 2012 10:19 pm

chrisbrown @ Tue Mar 13, 2012 9:53 pm wrote:

...If the next location in memory after the end of the array is in use, it becomes necessary to copy the entire array somewhere else.

While that's technically correct, it would be more accurate to say "it is always necessary to allocate the new, larger array, copy all the elements over, and delete the old array".

The reason has to do with how the OS allocates memory. There's (usually) no way to ask whether you can grow that particular segment, or allocate the next one over.

If you DO have to write something that resizes arrays, try to make it so that it doubles the size of the array every time it needs to grow it. Then you'll have log(N) "resize" operations rather than N, which makes it a lot faster.

chrisbrown · **Posted:** Tue Mar 13, 2012 10:46 pm

Cool, good to know re: allocation.

And no argument on doubling, but I'll just add that still necessitates a size variable, which might be overkill for small N.

Raknarg · **Posted:** Wed Mar 14, 2012 3:57 pm

The first one is supposed to be faster, I've tested it on two separate computers. It was a significant difference, too.

Dreadnought · **Posted:** Wed Mar 14, 2012 4:49 pm

Well the second program has a 20 ms delay in its loop, if I remove it the two programs seem to run at approximately the same speed.

Raknarg · **Posted:** Wed Mar 14, 2012 9:48 pm

oooh, i didnt see that -.-' thanks, I thought I had looked through it :/
Good thing for me, I dont think of such simple things as ctrl+f XD

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members