The Optimisation Tip Swap Thread

[technicalfool]

Just a little thread for amateurs and pros alike to swap hints and tips on how they make their projects go faster!

Now, I'm expecting that the Squad devs probably know every single one of these tricks. This thread will likely never result in an improvement in KSP's execution speed. However, this is for the people on the forums who are starting to learn to code, and might be wondering why the little demo they've made is running like treacle in Winter. Thing is, there are a number of things you can do to improve the speed at which a computer can crunch numbers. Quite a lot of them are somewhat "cheaty", but in the end, whether cheaty or not, it's the end result that matters!

And hey, if someone replies and puts in their own tricks that Squad haven't heard of, then that's just awesome all round.

And so I kick off with a couple of simple algorithm optimisations that anybody who's studied this stuff for a few years probably already knows. However, for the newbies, it could just save them some lost hair and fingernails.

Optimisation 1: Precalculating Sine Tables

So you're making a computer game. There's a lot of occasions where you might need to rotate something, or work with angles. In this case, you'll be doing a lot of playing around with the sine and cosine functions of your chosen programming language. Thing is, calculating a sine or cosine is an expensive operation. You don't want to be doing it a lot, and yet you might just need to do it a lot when you've got a boatload of stuff moving around in your game world. The answer to this? Well, you can swap memory for speed. See, you usually get, for instance, the sine value of an angle by punching in something like the following:

value = sin(angle_in_radians)

All well and good. That'll get you the sine of any angle, however tiny, right down to the limits of your system's accuracy. However, in many cases, you don't need to be that accurate. You can get away with the sine value only being accurate to say, 1/10_th or 1/100_th of a degree (or some fraction of a radian). In this case, try creating an array, and before the main part of your game or demo, you fill that array up with all the values from running sin(angle) from 0 to 360, going up in steps of 0.1, or 0.01, or however accurate you need to be. One big FOR loop, basically.

Later on in your project, when you need to calculate a sine value, rather than calling sin(value), you can convert the radians (or even better, degrees) value with a multiplication operation, and then look up the value in the array, with something like value = sine_array[angle]. Creating a function to do the lookup for you makes it even easier, so you can call value = sineFunc(radians), without having to write out the conversion steps for the angle each time.

As the cosine value for a given angle is basically the same as the sine value but 90 degrees out of phase, if you're clever, you can even use the same sine table to calculate cosines with. This saves a little bit of RAM. In the end, rather than having to run many sine or cosine operations, instead you're performing many lookups on an array, which in many programming languages, is a vastly quicker operation.

This approach can save a lot of time on any expensive operation. If you're working strictly with integers (whole numbers with no decimal point) for example, you could even precalculate square-root values. Why? Well, read on...

Optimisation 2: Working in the Square Domain

The what, I hear some people say?

Okay, there are many occasions when you need to calculate the distance between two points. The classic method for doing this is the Pythagorean equation. You know the bit about "the length of the hypotenuse is equal to the sum of the square of the other two sides" thing? Yeah, I wasn't paying attention in that lesson at school either. But, as a refresher, here's how you would normally do it:

Let's say you have two coordinates, [x1,y1] and [x2,y2]. You want to know how far apart they are. So, you do this:

d1 = x1 - x2

d2 = y1 - y2

This has now created an imaginary right angled triangle, which you can use to run the Pythagorean equation against.

distance = sqrt((d1 * d1) + (d2 * d2))

And herein lies the problem. That square root function. It's hugely expensive, more so than sine and cosine operations. In fact, a square root calculation is one of the most expensive operations you can ask a computer to perform. It takes quite an obscenely long amount of time to complete. And yet, sometimes you don't need to know the exact distance. Sometimes, you only need to know if distance A is greater or lesser than distance B. The answer?

Easy. Just skip the square root.

distanceA = (d1 * d1) + (d2 * d2)

And then some time later...

distanceB = (d1 * d1) + (d2 * d2)

Now you have two values, distanceA and distanceB, which, while they do not represent an exact distance value, can still tell you whether distanceA is greater or lesser than distanceB. While doing so, you've just saved on a square root operation. Well, go you! Give yourself a pat on the back.

Considering that converting a number to the square domain (by multiplying it by itself) is vastly cheaper than getting the square root of a number that's already in the square domain, you can use this approach in many parts of a program where you already have a distance value and want to compare it with a calculated distance. Take the distance you want to compare with, square it (multiply it by itself, or raise it by the power 2 if you like), then compare it against the value obtained by running (d1 * d1) + (d2 * d2), without the square root operation.

Just these two tricks alone could save a newbie coder a lot of headaches when it comes to making their program run faster. There's a lot of tricks out there and I've only scratched the surface with these two examples. If anybody out there has their own little tricks that they'd like to share, this is the thread to do it in!

(And please tell me if I'm just posting unreadable gobbledegook, I've only just had my first coffee!)