Thursday, 20 December 2012

Fixed point math to win performance on mobiles


Though fixed point calculations don't make sense as an optimization technique on x86 processors, where FPU became a standard years ago, on ARM machines it is still an approach to consider.

Although FPU (called VFP) on ARM processors was introduced in ARMv5TE, there is a lot of pitfalls with it. First, there are still a considerable number of devices without VFP. Second, VFP is an optional extension to ARM. There is no VFP unit in some newer phones, like in iPhone 4. (However, iPhone 4 has the NEON unit. NEON has single precision instructions set that can make short floating point calculation faster, but it is not a replacement for VFP.) So, if you are targeting just one platform you may know what you need - like use short floating point when targeting iPhone 4. But if you are looking for optimization on a variety of different ARM devices you may want to use fixed point calculations.

When such optimization makes sense? When your app does a lot of number crunching. For example, a 3D game may well be a candidate for such optimization if for every frame you need to push through the floating point transformation matrix, say, 10'000 vertexes.

Next I'm going to describe the how to replace floating point calculations with fixed point. The process is simple. You scale up float or double type and fit it into integral type. Then perform the calculations on the integral type, and after it is over, scale down integral type.

Suppose we need to multiply two floating point numbers.

long Scale = 20;
double a = .324, b = 3.34344;

//Scale up (a * 2^20 = a * 1048576)
signed long long aFixed = a * (1 << Scale);
 
//Scale up (b * 1048576)
signed long long bFixed = b * (1 << Scale); 

// ResultFixed = (a * b) * Scale = (a * Scale) * (b * Scale) / Scale = (aFixed * bFixed) / Scale
signed long long ResultFixed = (aFixed * bFixed) >> Scale;
 
//Scale down (ResultFixed / 1048576)
long Result = ResultFixed >> Scale;  


Why I have chosen to scale floating point numbers by the power of 2 (2^20)? That is because multiplications and divisions can be done with simple bit shifts.

I have had a story with one fixed point library that threw me off my rocker. It presented a nice fixed point class with overloaded math operators, very handy to replace double or float data types. Except when I done that I didn't get any performance increase! I looked inside and saw that the author chose 1000000 as a scale. So, while I gained speed on fixed point calculations I lost all of the performance gain while scaling back because division and multiplication by 1000000 can't be done by bit shift operations.

To look at fixed point math rules in detail visit http://www.gamedev.net/topic/214292-quick-explanationtutorial-on-fixed-point-math/.

Now for the benchmark. I took an iPhone 4 as a test machine. Suppose, I have 200'000 numbers and want to multiply each of them by some floating point coefficient. Lets do it in fixed and floating point manner and compare the performance. The test code:

#include <algorithm>
#include <vector>

double g_Coef = 0.0098942347923576;

signed long long g_CoefFixed;

int PutNumber() 
{ 
 static int Number = 1000;
 Number++;
 return Number;
}

int ModifyNumber(int i) 
{
 return (int)(i * g_Coef);
}

int ModifyNumberFixed(int i) 
{
 int result = (int) (((signed long long)i * g_CoefFixed) >> 20);
 return result;
}

void Test()
{
 std::vector<int> Numbers(200000);
 std::vector<int> Result1(200000);
 std::vector<int> Result2(200000);
 std::generate(Numbers.begin(), Numbers.end(), PutNumber);

 unsigned long Time1 = ::GetTickCount();
 std::transform(Numbers.begin(), Numbers.end(), Result1.begin(), ModifyNumber);
 unsigned long Time2 = ::GetTickCount() - Time1;
 
 g_CoefFixed = (signed long long)(g_Coef * (1 << 20));

 Time1 = ::GetTickCount();
 std::transform(Numbers.begin(), Numbers.end(), Result2.begin(), ModifyNumberFixed);
 Time2 = ::GetTickCount() - Time1;
}


Running this code for 11 times (why not 10? because butter never spoils the porridge!) produced the following results.



Clearly, fixed point version has left us with 6x performance increase.

No comments :

Post a Comment