Pandora Rethinking Floating Point On Pandora.

[TrevorBradley]

EDIT: Read down, I disprove that this is useful further down the page, but thought I'd share this anyways.

I know that integer math is pretty fast on Pandora, and floating point math is fairly slow on the pandora, and I know that NEON there to help get around the problem.

I'm trying to wrap my head around why this might be an issue. Float and int are both 32-bit. The only thing that makes logical sense is that float have floating decimal places, and that mathematics like exp(10,10)*exp(10,-10) are significantly more complicated than 2+2.

After some hard thought, it might be possible to convert my game from float to int. It would take a bit of work, but the mathematics I'm doing with these floats is somewhere between 0.1 to 200000. Perhaps 0.001 to 200000 to be safe if I'm thinking of radians. Which scaled up by 1000 works out to 1 to 2*10^8, within integer's range.

Now, rather than going to convert everything throughout the program, the thought occurred that I might be able to create a new data class (let's call it "flint") and overload the math operators. Data would be stored as an int, but really be a float, like so:

CODE
flint | float value
0 | 0
1 | 0.001
1000 | 1.0
-1000 | -1.0
100000000 | 100000.0
123456789 | 123456.789


Overloading +, - and == would be a snap. * and / slightly harder, but doable. Things get much harder with sin, cos, atan and log (each of which I need) but might be within my grasp.

... pauses ...

Y'know... I was hoping typing this up after thinking about it would bring some clarity, and I'm afraid it has. Multiplication is going to be pretty expensive. I was going to ask if I was attempting to reinvent the wheel and I believe I was about to.

123456.0 * 2.222 is a non trivial calculation for the floating point core. For integer math and my proposed flints, there would be overflow issues for almost every calculation.

I could nuke this but I've typed it up and might as well share the thought process, even if it is incorrect.

Back to thinking about NEON then..

 

[senquack]

Why not just go with an already-bug-tested existing C++ fixed-point library?

Our own Trenki has one:
http://www.trenki.net/content/view/17/1/

 

[Butterman]

QUOTE
I'm doing with these floats is somewhere between 0.1 to 200000


What an earth, are you doing that requires what range of values?

I thought this was a simple 2d space game? Are you using one single set of absolute co-ordinates that every object in space is linked to?

 

[bzar]

You're talking about fixed-point arithmetics. It's a very good solution, if you need fixed fraction accuracy. The point of floating point numbers is that the accuracy is changeable, so floats can represent either really large or really small numbers.

On topic though, it could make things clearer to have a dedicated data type for fixed-point numbers. Most database systems do (to handle currency correctly, never do moneystuff with floats).

Three decimal places should be enough for everyone

 

[TrevorBradley]

QUOTE
I'm doing with these floats is somewhere between 0.1 to 200000

What an earth, are you doing that requires what range of values?

I thought this was a simple 2d space game? Are you using one single set of absolute co-ordinates that every object in space is linked to?


It's a 2d space game with 40 million+ stars placed in fixed positions. It's critical that each player share the same data: star placement needs to be exact.

In theory each game will start in a different galaxy, but galaxy #12345 has the same for all players and calculated on the fly.

I'm not sure that's defined as simple or not.

 

[Butterman]

It's a 2d space game with 40 million+ stars placed in fixed positions. It's critical that each player share the same data: star placement needs to be exact.

In theory each game will start in a different galaxy, but galaxy #12345 has the same for all players and calculated on the fly.

I'm not sure that's defined as simple or not.

But, you can't say that galaxy #12345 has a center X/Y of 100,300. Then find the difference between each star in that galaxy and the galaxy itself and multiply that by a big enough number so it's precise? Relativity is very useful in game development.

 

[TrevorBradley]

You're talking about fixed-point arithmetics. It's a very good solution, if you need fixed fraction accuracy. The point of floating point numbers is that the accuracy is changeable, so floats can represent either really large or really small numbers.

On topic though, it could make things clearer to have a dedicated data type for fixed-point numbers. Most database systems do (to handle currency correctly, never do moneystuff with floats).

Three decimal places should be enough for everyone



Well, that starts getting dicey for trigonometric functions where you're using radians (in the range from 0 to 2PI). Really dicey when you start thinking of the natural log function ln.

Fixed point arithmetic is still on the menu as a possibility. But I am presently doing a lot of multiplication of the form x*y (0<x000.0, 0.0<y<1.0), so I'm not sure how much savings I'm going to get.

 

[PokeParadox]

Why not just go with an already-bug-tested existing C++ fixed-point library?

Our own Trenki has one:
http://www.trenki.net/content/view/17/1/



Yup very good it is too!
I make good use of it!

 

[hessiess]

You're talking about fixed-point arithmetics. It's a very good solution, if you need fixed fraction accuracy. The point of floating point numbers is that the accuracy is changeable, so floats can represent either really large or really small numbers.

On topic though, it could make things clearer to have a dedicated data type for fixed-point numbers. Most database systems do (to handle currency correctly, never do moneystuff with floats).

Three decimal places should be enough for everyone



Well, that starts getting dicey for trigonometric functions where you're using radians (in the range from 0 to 2PI). Really dicey when you start thinking of the natural log function ln.

Fixed point arithmetic is still on the menu as a possibility. But I am presently doing a lot of multiplication of the form x*y (0<x000.0, 0.0<y<1.0), so I'm not sure how much savings I'm going to get.


Can't you divide up the galaxy into a number of tiles, have each tile as an independent entity, with its own precalculated stars, then cull all of the non viable tiles, which should reduce the range of numbers required. When you zoom out, down sample the individual tiles(you don't need any more than one star per pixel), to create bigger tiles, with a reduced accuracy coordinate system.

 

[TrevorBradley]

But, you can't say that galaxy #12345 has a center X/Y of 100,300. Then find the difference between each star in that galaxy and the galaxy itself and multiply that by a big enough number so it's precise? Relativity is very useful in game development.

Integer placement isn't an issue. Rather than saying my galaxy center is at (0.0,0.0), I could say it's at (50000000,50000000), and as I scale in geometrically I should still have enough breathing room. Stars need to be at least 0.05ly apart in a 100000ly diameter galaxy.

Scaling, which is relatively tricky, should be possible that way too, though I need to look at that 100000.0 ly galaxy from any arbitrary scale or position.

I also need to know the exact distance between two stars tens of thousands of light years apart.

The tricky bit is the star seeding:

Star location vector = old star location vector + "random" scalar * "random" normal vector

where scalar is some value between 0.0 and say 1000.0, and the normal vector is an x,y with a radius of 1.0. Doesn't seem like much math, but I occasionally have to do 12000+ of them.

There are ways of doing this with integer math, and I'm still considering them. There's a lot of math in my program and I'd need to look at it all to make sure I'm not doing anything that couldn't be replaced. I was just hoping there was some way to construct some other data type that would allow me not to throw my existing units out the window. An interim step that would take a day's work instead of a week's work.

All of this is up to Pandora's speed. It's pointless for me to attempt to convert from float to int, or use NEON unless I know how poor the performance is on Pandora and know what needs optimizing.

It's possible I'll be releasing my source later this week. I'm sure all kinds of inefficiencies in my code will be found once I have my pants down and bare all to the world.

Can't you divide up the galaxy into a number of tiles, have each tile as an independent entity, with its own precalculated stars, then cull all of the non viable tiles, which should reduce the range of numbers required. When you zoom out, down sample the individual tiles(you don't need any more than one star per pixel), to create bigger tiles, with a reduced accuracy coordinate system.

I've already considered this. It's possible, but it's more work than an interim "float replacement".

One problem is to determine distance between two arbitrary stars anywhere in the galaxy.

Another will be to work out integer equivalents to sin, cos, and atan (I'm going to have to give up radians for angular measurement... *cries*)

I need to look through all 12,500 lines of code to see if this is feasible. Something's nagging me that it's not as simple as flipping everything over. I've been thinking about this at night and just before I go to sleep I remember "What about X?" and think "Right, that's going to be a problem..." and go to sleep and forget the next morning.

It's probably the right answer to flip everything over and deal with the consequences. It's just going to take me a week at least to repair the damage...

 

[Exophase]

I agree that you shouldn't worry about the float performance being subpar, since I doubt your game is heavily float demanding to begin with (not software rendering using float texel coordinates or anything like that). The Cortex-A8's VFP performance will probably be enough.

Having said that, it sounds like fixed would be more than sufficient for your game, and they would probably be much faster than floats. One adjustment to your original design: instead of multiplying by a number like 1000, you should multiply by a power of two. Then the decimal point adjustments become shifts instead of multiplies and divides, meaning that your fixed multiplies won't be really slow - on ARM it should be a 64bit multiply and two single cycle instructions to do the adjustment afterwards (unless you're doing a multiplication * a 0.32 number, which you sound like you are.. then you can just do the mul).

There's also not much gain in trying to do trigonometric or exponential/logarithmic functions in floating point since the overhead will largely be in the algorithms computing the values rather than the data representation (I could be wrong though). If you're using fixed you should convert float to fixed for these, and if you're using them constantly then you might want to rethink how your program is written (although you can use LUTs to improve things there, in which case doing them straight to fixed would make sense).

 

[multiplex]

Fixed point arithmetic is usually done in binary, so for 4 bit fractions, 2 would become 0x20, 1.5 would be 0x18, and 0.1 would be not quite 0x02.
That means the divide after multiplication can be done as a shift, and an integer multiplication and a shift can still be an improvement from going through the VFP.

For the trigonometry, it depends on how accurate you need it. For games you can often use a lookup table (and maybe represent angles as something else than radians, depending on what math you're doing.)

I'd definitely use both fixed point arithmetics and lookup tables if I were making some fast-paced, number heavy game for a console with limited power. It's a fair amount of trouble compared to just sticking with floats and just doing the obvious, though.

 

[TrevorBradley]

I agree that you shouldn't worry about the float performance being subpar, since I doubt your game is heavily float demanding to begin with (not software rendering using float texel coordinates or anything like that). The Cortex-A8's VFP performance will probably be enough.

Having said that, it sounds like fixed would be more than sufficient for your game, and they would probably be much faster than floats. One adjustment to your original design: instead of multiplying by a number like 1000, you should multiply by a power of two. Then the decimal point adjustments become shifts instead of multiplies and divides, meaning that your fixed multiplies won't be really slow - on ARM it should be a 64bit multiply and two single cycle instructions to do the adjustment afterwards (unless you're doing a multiplication * a 0.32 number, which you sound like you are.. then you can just do the mul).

There's also not much gain in trying to do trigonometric or exponential/logarithmic functions in floating point since the overhead will largely be in the algorithms computing the values rather than the data representation (I could be wrong though). If you're using fixed you should convert float to fixed for these, and if you're using them constantly then you might want to rethink how your program is written (although you can use LUTs to improve things there, in which case doing them straight to fixed would make sense).

I'm biased against int. The last program I wrote for the GP2x failed because I didn't have enough accuracy in the floating point mathematics. That was using the Fenix interpreter where doubles weren't allowed. (I may still re-write that in SDL.. it shouldn't be too evil as there were only about a dozen calculations per frame.)

I'm certain to be embarrassed if I release my source for my new game.. probably all kinds of cruft in there that experienced programmers will see and say "Why the heck did you do that?!?". I'm not looking forward to it (though getting the actual performance increase from any hints I get may be worth it)

There's so much up in the air about system performance I'm just going to hold off worrying about this problem until I have a pandora in hand. The floating point damage has already been done, it will take the same about to work to fix now or later, and I have no clue where I should be spending my time optimizing.. Guessing at the moment is kind of pointless.

 

[darkblu]

There's so much up in the air about system performance I'm just going to hold off worrying about this problem until I have a pandora in hand. The floating point damage has already been done, it will take the same about to work to fix now or later, and I have no clue where I should be spending my time optimizing.. Guessing at the moment is kind of pointless.

a wise man once said:

'premature optimisation is the root of all evil.'

which, in retrospect, is nothing more than the IT-age equivalent of what a caveman once thought (but could not put into words, partially due to the non-yet-developed speech ability, and partially - due to him screaming off the top of his lungs), while being chewed upon by a carnivorous raspberry bush:

'assumtion is the mother of all fuck-ups.'

 

[Exophase]

There's so much up in the air about system performance I'm just going to hold off worrying about this problem until I have a pandora in hand. The floating point damage has already been done, it will take the same about to work to fix now or later, and I have no clue where I should be spending my time optimizing.. Guessing at the moment is kind of pointless.

a wise man once said:

'premature optimisation is the root of all evil.'

which, in retrospect, is nothing more than the IT-age equivalent of what a caveman once thought (but could not put into words, partially due to the non-yet-developed speech ability, and partially - due to him screaming off the top of his lungs), while being chewed upon by a carnivorous raspberry bush:

'assumtion is the mother of all fuck-ups.'


The problem is that people have a pretty bad idea of what constitutes as "premature." Optimization can't always merely be a pass you add to your programming to tighten it later. Sometimes you have to make performance considerations part of your higher level design or you'll prevent yourself from ever being able to improve beyond a certain point. This happens all the time when someone tries to port an non-efficient-enought program to an not-fast-enough platform - they then approach the problem fully expecting to be able to optimize it into compliance and eventually come off rather disappointed (see VBA on PSP)

I'd say that saying was originally directed to people who think they know what they're doing but don't - unfortunately, a lot of pretty silly ideas have come up since then and the phrase is thrown around really casually. Like the belief that you can't ever have even the smallest clue where the performance in a program is going without using a standard profiler (read: writing your own profiling code is not sufficient). Or that any C compiler for any platform will almost always beat any assembly programmer. Or the belief that all things are being ran on high end desktops and not the 25MHz embedded CPUs that are still widely used.

But yes, in this case, if you don't know that performance won't be good enough then there's no point trying to improve it.

But sometimes you can know, even before you run it.

 

[bzar]

There's so much up in the air about system performance I'm just going to hold off worrying about this problem until I have a pandora in hand. The floating point damage has already been done, it will take the same about to work to fix now or later, and I have no clue where I should be spending my time optimizing.. Guessing at the moment is kind of pointless.

a wise man once said:

'premature optimisation is the root of all evil.'

which, in retrospect, is nothing more than the IT-age equivalent of what a caveman once thought (but could not put into words, partially due to the non-yet-developed speech ability, and partially - due to him screaming off the top of his lungs), while being chewed upon by a carnivorous raspberry bush:

'assumtion is the mother of all fuck-ups.'

I agree. Don't fix what isn't broken. Use the time you would spend optimizing by cleaning up your code (not to imply it's messy, but one can always improve comments, function structure, etc.). If it will be run decent on a pandora, you'll have a working program with a source you're not ashamed to show. If it runs slow, you'll have a nice, clean code to optimize.

 

[maciek_urbanski]

It's a 2d space game with 40 million+ stars placed in fixed positions. It's critical that each player share the same data: star placement needs to be exact.

In theory each game will start in a different galaxy, but galaxy #12345 has the same for all players and calculated on the fly.

I'm not sure that's defined as simple or not.

I had similar problem but with 3D. I ended with doing (yet another) custom exact floating point class. Idea is to store data in float-like fashion (I've used arbitrary long mantissa and fixed size exponent) and never perform rounding. When overflow would to occur mantissa grows to accommodate new bits.
You have to carefully design algorithms using this class (no divisions and not too many multiplies), but result is always exact.

And for those wondering why I didn't use existing class - all libs I've evaluated used sign+mantissa+exponent format. I needed fastest possible bit extraction for both signed and unsigned U2 values... and I like coding those low-level stuff.

Ahh - and use reference counting, and LOTS of unit level tests. You don't want to have lib with faulty addition code...

If you want a sketch - I can share my class - it's well tested but nowhere near completion. PM me for details. B)

But I'd advise to use something more ready and used in other projects (read: bug-free).

 

[Exophase]

It's a 2d space game with 40 million+ stars placed in fixed positions. It's critical that each player share the same data: star placement needs to be exact.

In theory each game will start in a different galaxy, but galaxy #12345 has the same for all players and calculated on the fly.

I'm not sure that's defined as simple or not.

I had similar problem but with 3D. I ended with doing (yet another) custom exact floating point class. Idea is to store data in float-like fashion (I've used arbitrary long mantissa and fixed size exponent) and never perform rounding. When overflow would to occur mantissa grows to accommodate new bits.
You have to carefully design algorithms using this class (no divisions and not too many multiplies), but result is always exact.

Ahh - and use reference counting, and LOTS of unit level tests. You don't want to have lib with faulty addition code...

If you want a sketch - I can share my class - it's well tested but nowhere near completion. PM me for details. B)


Floats are giving him enough precision, performance is his concern. I don't think he'd want to move to a library that makes his operations much slower.

 

[maciek_urbanski]

Floats are giving him enough precision, performance is his concern. I don't think he'd want to move to a library that makes his operations much slower.

In this case he should of course stick to floats (using NEON ).

 

[Exophase]

Floats are giving him enough precision, performance is his concern. I don't think he'd want to move to a library that makes his operations much slower.

In this case he should of course stick to floats (using NEON ).


Given the option, yes.. I just don't know if Pandora will launch such that there's a compiler flag that uses NEON for scalar floats, or if auto-vectorization will work sufficiently (or if his code is a candidate for it).