Lua: Code optimization vector length calculation

I have a script in a game with a function that gets called every second. Distances between player objects and other gam开发者_如何学Goe objects are calculated every second there. The problem is that there can be thoretically 800 function calls in 1 second(max 40 players * 2 main objects(1 up to 10 sub-objects)). I have to optimize this function for less processing. this is my current function:

local square = math.sqrt;

local getDistance = function(a, b)
    local x, y, z = a.x-b.x, a.y-b.y, a.z-b.z;
    return square(x*x+y*y+z*z);
end;

-- for example followed by: for i = 800, 1 do getDistance(posA, posB); end

I found out, that the localization of the math.sqrt function through

local square = math.sqrt;

is a big optimization regarding to the speed, and the code

x*x+y*y+z*z

is faster than this code:

x^2+y^2+z^2

I don't know if the localization of x, y and z is better than using the class method "." twice, so maybe square(a.x*b.x+a.y*b.y+a.z*b.z) is better than the code local x, y, z = a.x-b.x, a.y-b.y, a.z-b.z; square(x*x+y*y+z*z);

Is there a better way in maths to calculate the vector length or are there more performance tips in Lua?

You should read Roberto Ierusalimschy's Lua Performance Tips (Roberto is the chief architect of Lua). It touches some of the small optimizations you're asking about (such as localizing library functions and replacing exponents with their mutiplicative equivalents). Most importantly, it conveys one of the most important and overlooked ideas in engineering: sometimes the best solution involves changing your problem. You're not going to fix a 30-million-calculation leak by reducing the number of CPU cycles the calculation takes.

In your specific case of distance calculation, you'll find it's best to make your primitive calculation return the intermediate sum representing squared distance and allow the use case to call the final Pythagorean step only if they need it, which they often don't (for instance, you don't need to perform the square root to compare which of two squared lengths is longer).

This really should come before any discussion of optimization, though: don't worry about problems that aren't the problem. Rather than scouring your code for any possible issues, jump directly to fixing the biggest one - and if performance is outpacing missing functionality, bugs and/or UX shortcomings for your most glaring issue, it's nigh-impossible for micro-inefficiencies to have piled up to the point of outpacing a single bottleneck statement.

Or, as the opening of the cited article states:

In Lua, as in any other programming language, we should always follow the two maxims of program optimization:

Rule #1: Don’t do it.

Rule #2: Don’t do it yet. (for experts only)

I honestly doubt these kinds of micro-optimizations really help any.

You should be focusing on your algorithms instead, like for example get rid of some distance calculations through pruning, stop calculating the square roots of values for comparison (tip: if a^2<b^2 and a>0 and b>0, then a<b), etc etc

Your "brute force" approach doesn't scale well.

What I mean by that is that every new object/player included in the system increases the number of operations significantly:

 +---------+--------------+
 | objects | calculations |
 +---------+--------------+ 
 |      40 |        1600  |
 |      45 |        2025  |
 |      50 |        2500  |
 |      55 |        3025  |
 |      60 |        3600  |
...       ...            ...
 |     100 |       10000  |
 +---------+--------------+

If you keep comparing "everything with everything", your algorithm will start taking more and more CPU cycles, in a cuadratic way.

The best option you have for optimizing your code isn't not in "fine tuning" the math operations or using local variables instead of references.

What will really boost your algorithm will be eliminating calculations that you don't need.

The most obvious example would be not calculating the distance between Player1 and Player2 if you already have calculated the distance between Player2 and Player1. This simple optimization should reduce your time by a half.

Another very common implementation consists in dividing the space into "zones". When two objects are on the same zone, you calculate the space between them normally. When they are in different zones, you use an approximation. The ideal way of dividing the space will depend on your context; an example would be dividing the space into a grid, and for players on different squares, use the distance between the centers of their squares, that you have computed in advance).

There's a whole branch in programming dealing with this issue; It's called Space Partitioning. Give this a look:

http://en.wikipedia.org/wiki/Space_partitioning

Seriously?

Running 800 of those calculations should not take more than 0.001 second - even in Lua on a phone.

Did you do some profiling to see if it's really slowing you down? Did you replace that function with "return (0)" to verify performance improves (yes, function will be lost).

Are you sure it's run every second and not every millisecond?

I haven't see an issue running 800 of anything simple in 1 second since like 1987.

If you want to calc sqrt for positive number a, take a recursive sequense

x_0 = a
x_n+1 = 1/2 * (x_n + a / x_n)

x_n goes to sqrt(a) with n -> infinity. first several iterations should be fast enough.

BTW! Maybe you'll try to use the following formula for length of vector instesd of standart.

local getDistance = function(a, b)
    local x, y, z = a.x-b.x, a.y-b.y, a.z-b.z;
    return x+y+z;
end;

It's much more easier to compute and in some cases (e.g. if distance is needed to know whether two object are close) it may act adequate.