GP2X Fixed Vs. Float

[A_SN]

I just did some benchmarks on my early implementation of something I don't wanna mention*, with both fixed-point and floating-point arithmetic, and floats win hands down, and I didn't really expect that I must say.

I always heard that it was faster to use fixed-point arithmetic on the GP2X rather than floating-point due to the lack of a FPU, but after all it's not that simple to perform fixed-point operations, and we got a pretty optimized software handling of floats.

So here's what I'm wondering, isn't float-point arithmetic faster than fixed-point arithmetic on the GP2X in spite of the lack of a FPU, or can fixed-point arithmetic be faster that floating-point no matter what and I should implement better fixed-point functions?

*so that the discussion doesn't drift away from the fixed vs. float performance debate

 

[Blah]

You are using Jack Bresenham's Run-Slice Algorithm, right?

 

[A_SN]

You are using Jack Bresenham's Run-Slice Algorithm, right?

No, I said anti-aliased, and don't get me started with line drawing algorithms because I don't wanna hear about it, I only want to hear about fixed vs float in terms of performance.

 

[Blah]

You can optimize a bad algorithm all you want and it will still be slow. As for the fixed vs float thing, I'm positive that fixed is faster, and you're just not doing it right.

 

[marmakoide]

Well, I think you don't use correctly fixed point. Doing software floating point operation is MUCH slower. Just compare the assembler code needed by an addition, a multiplication, or a square root ! And the difference is even greater when the fixed point usage is implicit like in the Bresenham algorithm. Here it is a tiny list of algorithms that are fast because of a *clever* use of fixed point :
* Bresenham line and circle
* Wu antiliased line and circle
* DDA trick for linear interpolation (for linear texture mapping or Gouraud shading as instance)
* Intersection over a regular grid (for raycasting as instance)

Using floating point for those algorithms, at least on a processor without floating point unit, is much much slower. Don't imagine a second that you can beat those ones with fixed point. When I implement some algorithms, I first go with a floating point version, then I make a fixed point version, that always rocks the house. I think that is a problem from your implementation. Show it to us, and you will see the light

 

[rixed]

You forget to mention the fabulous quake3's InvSqrt().

Anyway, perhaps the OP found such another gem ?
Could we see the code sample that performed better on float than fixed ?

 

[Dr_Ian]

You forget to mention the fabulous quake3's InvSqrt().

This specifically only runs on IEEE type 32 bit floating point numbers. It wouldn't work with fixed point.
It is VERY clever though.

 

[Squidge]

Floats can be pretty quick if you use the correct tool chain with the optimized assembler floating point routines, but it'll be no where near as quick as a decent fixed point implementation, which can be tailored (and optimized) to your exact needs.

Point us towards your comparison code & tool chain used so we may investigate further.

 

[Mudi]

Well I would hope that floats would be decently fast, since I used floats in emulation mode on an old 8088 and it was 'fast enough'. But yeah, on the GP2X fixed will always be faster than float when properly implemented, and in the same algorithm fixed should _always_ be faster than float.

 

[telecoda]

Are you using variable float values or constants?

I remember reading somewhere that the compiler optimises float constants to integer mult/divides.

(Or did I eat too much cheese before bed that night?)

 

[marmakoide]

The cheese as nothing to do with confusion, that's a French frog that said that to you ! Indeed, yes, you right, at least recent GCC versions (4.x.x) are able to generate optimized code for the operations implying float constants.

 

[A_SN]

Well thanks everybody for your input. I have tried different fixed algorithms, so here they all are

Firstly, the 24.8 * 24.8 -> 24.8 multiplication

int32_t qmul(int32_t a, int32_t b)
{
	int32_t af=a&0xFF, bf=b&0xFF, r;
 
	a >>= 8;
	b >>= 8;
	r = (a*bf + b*af + (af*bf>>8));
	r += a*b<<8;
	return r;
}

//or alternatively (but not any faster)
int32_t qmul(int32_t a, int32_t b)
{
	return (int32_t) (((int64_t) a*b) >> 8);
}

Now, the 8.24 * 24.8 -> 24.8 multiplication

int32_t qmul2(int32_t a, int32_t b)
{
	int32_t af=a&0xFFFFFF, bf=b&0xFF, r;
 
	a >>= 24;
	b >>= 8;
	r = (a*bf + (((int64_t) b*af)>>16) + ((af>>1)*bf>>23));
	r += a*b<<8;
	return r;
}

//or alternatively but not obviously faster
int32_t qmul2(int32_t a, int32_t b)
{
	return (int32_t) (((int64_t) a*b) >> 24);
}

And finally, the most time consuming of all, the 24.8 / 24.8 -> 8.24 division

__inline int32_t qdiv(int32_t a, int32_t b)
{
	int64_t al, bl, rl;

	al = (int64_t) a << 32;

	rl = al/b;

	return (int32_t) (rl >> 8);
}

//or otherwise, but faster this time
__inline int32_t qdiv(int32_t a, int32_t b)
{
	int32_t r = 0, s = 24;
	int32_t as = unsign(&a), bs = unsign(&b), rs = as ^ bs;		//needed for sign support only
 
	//if (b == 0) return 0;
 
	while (b < a)
	{
		b <<= 1;
		s++;
	}

	while (!(b & 0x400000))
	{
		a <<= 1;
		b <<= 1;
	}

 
	while (a!=0 && s>=0)
	{
		if (a >= b)
		{
			a -= b;
			r += (1 << s);
		}
		else
		{
			b >>= 1;
			s--;
		}
	}
 
	if (rs==0)
		return r;
	else
		return -r;
}

I'm not sure to know if the code that calls them is relevant, mainly that it's not a definitive algorithm anyways, more like a proof-of-concept algorithm to show how to do the job in a simple and unefficient manner.

 

[rixed]

So, which one is slower than it's floating point counterpart ?

 

[A_SN]

So, which one is slower than it's floating point counterpart ?

Everything is. Well as a whole, as used by my function that calls them, I haven't tested individually the performance of each.

 

[Lint]

you're doing it all wrong, I say (imho)

what you're doing is comparing floating point math by hand versus floating point math by the compiler
neither one of these are fixed point math

in fixed point math you must deal with temporary precision numbers, like 24.8 can be 248, so multiply 248 * 248 and the result will be 61504, which is the correct value << 2d (decimal shift! means 1<<1d is 10), so 248 * 248 >> 1d will give you the result in the same notation of the parameters and 248 * 248 >> 2d will give you the result in the pure decimal/binary notation (i.e. 248 * 248 / 100 = 615)

That's just a very simple sample, best is if you can manage your precision to be powered-by-2-compatible, then you can use binary shift instead of division and your code will be fastest, like this:

24.8 is 248 shifted right by 1d, but let's take a simpler example: 11.5 * 11.5
11.5 is 23 >> 1b (now binary shifts, for speed!), so we should write a function that takes x and y as temporary precision numbers (I don't know if is that the real name, I knew this for a long time just by researching) and returns it in the decimal notation so:

int dothatmultiply(char x, char y) {
return (x * y) >> 2;
}

// or to return in the same notation as the parameters:

char dothatmultiply(char x, char y) {
return(x * y) >> 1;
}

// or in other temporary precision number to keep maximum precision:

char dothatmultiply(char x, char y) {
return (x * y);
}

when you call the first one with 23 as both parameters, the result will be 23 * 23 >> 2 the result would be 132, discarding some precision if you shift, but you can keep as much as precision you want if you manage to return other temporary math precision number, the precision is directly related to how many bits you offer to the calculation so ALWAYS try to best fit your numbers to deal with speed and precision altogether...

your code will be definitely faster and smaller than any floating point precision you'll ever know (as long as it's softare based), but it can render you crazy as well if you try to use one specific temporary precision number for each calculation you done! so beware of how much precision you'll need h34r:

 

[Lint]

you're doing it all wrong, I say (imho)

what you're doing is comparing floating point math by hand versus floating point math by the compiler
neither one of these are fixed point math

in fixed point math you must deal with temporary precision numbers, like 24.8 can be 248, so multiply 248 * 248 and the result will be 61504, which is the correct value << 2d (decimal shift! means 1<<1d is 10), so 248 * 248 >> 1d will give you the result in the same notation of the parameters and 248 * 248 >> 2d will give you the result in the pure decimal/binary notation (i.e. 248 * 248 / 100 = 615)

That's just a very simple sample, best is if you can manage your precision to be powered-by-2-compatible, then you can use binary shift instead of division and your code will be fastest, like this:

24.8 is 248 shifted right by 1d, but let's take a simpler example: 11.5 * 11.5
11.5 is 23 >> 1b (now binary shifts, for speed!), so we should write a function that takes x and y as temporary precision numbers (I don't know if is that the real name, I knew this for a long time just by researching) and returns it in the decimal notation so:

int dothatmultiply(char x, char y) {
return (x * y) >> 2;
}

// or to return in the same notation as the parameters:

char dothatmultiply(char x, char y) {
return(x * y) >> 1;
}

// or in other temporary precision number to keep maximum precision:

char dothatmultiply(char x, char y) {
return (x * y);
}

when you call the first one with 23 as both parameters, the result will be 23 * 23 >> 2 the result would be 132, discarding some precision if you shift, but you can keep as much as precision you want if you manage to return other temporary math precision number, the precision is directly related to how many bits you offer to the calculation so ALWAYS try to best fit your numbers to deal with speed and precision altogether...

your code will be definitely faster and smaller than any floating point precision you'll ever know (as long as it's softare based), but it can render you crazy as well if you try to use one specific temporary precision number for each calculation you done! so beware of how much precision you'll need h34r:

that's one of the things I like to be a low level programmer, that's much more fun and challenge!
and remember that our numerical system is 10-based just because we've got 10 fingers in our hands, if we've got 13 fingers would be 13 based and so on... at least we didn't got just 2! :lol:

I'm sorry, my internet is quite not working so I've got it double-posted, could somebody delete the first answer please?

 

[Lint]

can somebody delete the first answer please?
my internet is quite not much working today....

 

[gmiller1018]

I think the example notation might be confusing you. His 24.8 is 24 bits integer and 8 fractional bits. The multiply of the two 24.8 integer can produce a number that is 48.16 wide so overflow is possible. The simplistic solution is to just do ((x * y) >> 8) for multiply , but this could have hight order bits drop off. or the complete approach (int) (((long long)x * (long long) y) >> 8).

 

[A_SN]

you're doing it all wrong, I say (imho)

what you're doing is comparing floating point math by hand versus floating point math by the compiler
neither one of these are fixed point math

in fixed point math you must deal with temporary precision numbers, like 24.8 can be 248, so multiply 248 * 248 and the result will be 61504, which is the correct value << 2d (decimal shift! means 1<<1d is 10), so 248 * 248 >> 1d will give you the result in the same notation of the parameters and 248 * 248 >> 2d will give you the result in the pure decimal/binary notation (i.e. 248 * 248 / 100 = 615)

That's just a very simple sample, best is if you can manage your precision to be powered-by-2-compatible, then you can use binary shift instead of division and your code will be fastest, like this:

24.8 is 248 shifted right by 1d, but let's take a simpler example: 11.5 * 11.5
11.5 is 23 >> 1b (now binary shifts, for speed!), so we should write a function that takes x and y as temporary precision numbers (I don't know if is that the real name, I knew this for a long time just by researching) and returns it in the decimal notation so:

int dothatmultiply(char x, char y) {
return (x * y) >> 2;
}

// or to return in the same notation as the parameters:

char dothatmultiply(char x, char y) {
return(x * y) >> 1;
}

// or in other temporary precision number to keep maximum precision:

char dothatmultiply(char x, char y) {
return (x * y);
}

when you call the first one with 23 as both parameters, the result will be 23 * 23 >> 2 the result would be 132, discarding some precision if you shift, but you can keep as much as precision you want if you manage to return other temporary math precision number, the precision is directly related to how many bits you offer to the calculation so ALWAYS try to best fit your numbers to deal with speed and precision altogether...

your code will be definitely faster and smaller than any floating point precision you'll ever know (as long as it's softare based), but it can render you crazy as well if you try to use one specific temporary precision number for each calculation you done! so beware of how much precision you'll need h34r:

dude, I already do that.. That's already what I do when I do stuff like

return (int32_t) (((int64_t) a*b) >> 24);

, isn't it?

And yeah like Gary Miller says, you got my notation wrong it seems. Anyways, maybe the multiplication is already faster the way I do it in fixed than in float, I'd have to test that, but I'm pretty sure it's not the case for the division.

PS : Did you even look at my code or only my comments? ;-)

 

[rixed]

So, which one is slower than it's floating point counterpart ?

Everything is. Well as a whole, as used by my function that calls them, I haven't tested individually the performance of each.

I can't believe it.

You pretend that :

int32_t a = 12<<8;
int32_t b = 5<<8;
int32_t c = qmul(a,b);

is slower than :

float a = 12;
float b = 5;
float c = a*b;

??

Please have a look at the assembly for both versions, this should give us a good hint.