In a search for something else entirely, I found myself reading an article on performance in Lua. I decided to test an alternate representation for the Bezier.
We store the Bezier’s four control points in four member variables, and access them accordingly, like this, in the method that computes the tangent at a position t, which is the long part of computing the actual position:
Bezier = class()
function Bezier:init(p0, p1, p2, p3)
self.p0 = p0
self.p1 = p1
self.p2 = p2
self.p3 = p3
self:final()
end
function Bezier:tangent_at(t)
-- de casteljau algorithm
-- returns two points defining the tangent line
-- generally speaking, that's what most movers want.
local mt = 1 - t
local q0 = self.p1*t + self.p0*mt
local q1 = self.p2*t + self.p1*mt
local q2 = self.p3*t + self.p2*mt
local r0 = q1*t + q0*mt
local r1 = q2*t + q1*mt
return r1, r0
end
For timing purposes, I added a member containing the points as an array, and a new method using the array:
Bezier = class()
function Bezier:init(p0, p1, p2, p3)
self.p0 = p0
self.p1 = p1
self.p2 = p2
self.p3 = p3
self.array = {p0,p1,p2,p3}
self:final()
end
function Bezier:array_tangent_at(t)
local mt = 1 - t
local a = self.array
local q0 = a[2]*t + a[1]*mt
local q1 = a[3]*t + a[2]*mt
local q2 = a[4]*t + a[3]*mt
local r0 = q1*t + q0*mt
local r1 = q2*t + q1*mt
return r1, r0
end
Note that the array_tangent_at fetches the array just once, into a, so that is the only hashed access to the object. All other accesses are indexed by integer into that array.
Then I timed three things: an empty loop from 1 to 100,000, a loop calling tanget_at, and a loop calling array_tangent_at. Differencing the times, and removing the nearly zero empty loop, I get this result:
nothing 0.001 sec,
hashed 0.391 sec,
array 0.305 sec,
ratio 0.780
The cost of the array version is less than 80% of the version using member variables. Or, looking at tit the other way around, the hashed version is 25% more costly than the array.
So what, you might well ask. Well, in the current SLRR_capable movers, we compute a lot of bezier values every tenth of a second. While my Mac can calculate over 30,000 bezier values every tenth of a second, an SL script migh not be so capable. In any case it’s certainly an interesting result.
That said, my current thinking is that it is worth linearizing a Bezier when we first create it, which takes very little (but unmeasured) time and produces a very fast (but also unmeasured) form that can be accessed quickly (unmeasured) and calculates the point with just two vector operations instead of ten or twelve. So it is likely that we won’t be computing so many Beziers every tenth of a second. On the other hand, there will be a burst of calculations for creating the linearized data, and that needs to be as fast as possible.
Note that all this is on my Mac: we would want to check the figures in SL when things get further along.
_:test("array vs hash", function()
local data_h = {a=1,b=2,c=3,d=4}
local data_a = {1,2,3,4}
local n = 100_000_000
local t0 = os.clock()
for i = 1,n do
end
local t_nothing = os.clock()
for i = 1,n do
local t
t = data_h.a
t = data_h.b
t = data_h.c
t = data_h.d
end
local t_hash = os.clock()
for i = 1,n do
local t
t = data_a[1]
t = data_a[2]
t = data_a[3]
t = data_a[4]
end
local t_array = os.clock()
local nothing = t_nothing - t0
local hashed = t_hash-t_nothing - nothing
local array = t_array-t_hash - nothing
local better = hashed / array
local r = string.format('nothing %0.3f sec, hashed %0.3f sec, array %0.3f sec, ratio %0.3f',
nothing, hashed, array, better)
print(r)
end)
nothing 0.367 sec,
hashed 0.577 sec,
array 0.604 sec,
ratio 0.956
None, really, other than the recognition that the cost of array access is probably possibly sometimes around 80% the cost of hashed access, which is vague enough aht it should inform, but not overwhelm, how we create our code.
And, of course, we relearn the lesson we have learned a million times: optimize code only when tests have shown that the optimization is needed, and that the new code is a substantial improvement over the old.
Quite commonly, by which I mean almost always, where we think the problem is is not where it is, and the code we think will make things better does not. Test, test, test again.
Safe paths!