Fixed point numbers (Haxe3)

[Luca]

Had a go playing with abstracts for opaque fixed point number support in Haxe (Requires r6457)

https://gist.github.com/deltaluca/5413225

The Fixed16 type is a 16.16 fixed point number supporting signed floating point values from -32768 up to 32767.99998474121 with a resolution of 0.0000152587890625

This is directly replaceable (assuming no Dynamic usage) with the standard Float type, and in debug mode will check for overflow at runtime.

Division is implemented with floating point division, I am not entirely sure if this breaks its consistency across architectures, but doing a brute force test on my computer in C showed that a/b is always the same as int((double)a/(double)b) so I think it should be okay.

There is no implementation of sin/cos/tan/sqrt etc, though through implicit casting it still works, and if these functions are consistent then it would be fine too.

A speed test, with 30,000 circles moving around the screen, doing collision detection 100 times per overlapping pair from broadphase showed performance to really be very very slow to floats. I'm looking forward (when I have time!) to try replacing Float with Fixed16 in Nape :P

[Samuel Batista]

This is quite interesting, it does seem like this might cause a problem for the garbage collector since using Fixed16 for numeric operations involves allocating new instances of this object (which I imagine would happen often). Garbage collection is already an issue with Haxe, and I think we would need to devise a way for these values to be managed in a pool much like Vec2 are managed.

Please report back with performance statistics, it would be interesting to know how integer math fares versus double math. Also, have you tried defining <haxedef name="HXCPP_FLOAT32"/> on your project (so hxcpp uses floats instead of doubles) and checking out performance metrics with that setting on?

Thanks for your great work with Nape!

[Franco Ponticelli]

I think you are wrong. No objects are generated. The abstract only exists at compile time and all the operations are performed directly on the wrapped Int.

--
To post to this group haxe...@googlegroups.com
http://groups.google.com/group/haxelang?hl=en
---
You received this message because you are subscribed to the Google Groups "Haxe" group.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Samuel Batista]

I was just looking at the function RAW(x:Int), which returns a new Fixed16(x);

This function is used throughout the entire class.

[Franco Ponticelli]

but new Fixed16(x) maps directly to x in the generated code.

[Luca]

Yes, for instance:

var f:Fixed16 = 10.53;
f += Math.sqrt(f);
f /= 10 - (f/2);

generates for the JS target:

var f = 690094.08 | 0;
f = f + (Math.sqrt(f * 0.0000152587890625) * 65536.0 | 0);
f = f / (655360 - (f / 131072 * 65536.0 | 0)) * 65536.0 | 0;

[Cauê Waneck]

and that's the beauty of abstracts ;)

2013/4/18 Luca <delta...@hotmail.com>

[Malek]

This is pretty awesome, but I don't understand how it can be faster than just doing it with Float here ? I mean Luca's sample outputs 3 more * and 4 more | than it would if a real Float was used. Also more intermediary floats are used at runtime because there are more operations... So while I do get that it's convenient, why is it faster ?

[Luca]

When did i say it was faster than Float?

The point of fixed point numbers is that you get a subset of the Float type, that is 100% reproducible across all machines, guaranteed, and you get rid of many problems also like being able to always use == and != with fixed point unlike Floats where you have to choose a suitable epsilon etc.

[Malek]

I must have misread this.

A speed test, with 30,000 circles moving around the screen, doing collision detection 100 times per overlapping pair from broadphase showed performance to really be very very slow to floats. I'm looking forward (when I have time!) to try replacing Float with Fixed16 in Nape :P

Sounded like you said floats were utterly slow for what you were doing and you hoped Fixed16 would make it better. Well if it's not then okay, there's nothing else I don't understand :P
I might use your Fixed16 eventually, when it will be time to learn more about Haxe abstracts :)

[Luca]

Keyboard fart. I meant to say 'very very close' :P

[Nicolas Cannasse]

Le 20/04/2013 21:03, Luca a �crit :

The main advantage of fixed numbers in today VMs is that usually small
Ints are "unboxed" so does not require any GC allocation. But this can
also be optimized by the VM sometimes, so speed results might depend,
especially when using real float operations such converting from/to
Int/Float is a bit slow.

Best,
Nicolas

[Luca]

It'd be nice if Haxe exposed an integer divide ;)

Certainly most targets would still have to emulate it, but c++ at least could use a real integer division.

[Cauê Waneck]

On Java/C#, When the pattern Std.int(i1 / i2) is found, it's replaced by an integer divide

Le dimanche 21 avril 2013, Luca a écrit :

It'd be nice if Haxe exposed an integer divide ;)

Certainly most targets would still have to emulate it, but c++ at least could use a real integer division.

--

To post to this group haxe...@googlegroups.com
http://groups.google.com/group/haxelang?hl=en
---
You received this message because you are subscribed to the Google Groups "Haxe" group.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
Sent from Gmail Mobile

[TopHattedCoder]

Oh, I might just borrow that idea.

[Luca]

Ah nice Caue, I hadn't considered that possibility.

Checking C++, we end up with something like:

::Std_obj::_int((Float(f) / Float(g))

:(

[Simon Krajewski]

This seems to be a simple optimization, you could try filing an hxcpp issue.

Simon

[dlots]

What is the point of this if you are using fixed point? In the sense that I am curious as to why you would be interested in fixed point but okay with floating point calculations? I would think that one would use floating point to ensure determinism across CPU architectures.

It would be useful to have a fixed point implementation that perhaps does the following:

http://code.google.com/p/libfixmath/

Or some other stable c/cpp FP lib in the interest of saving time in getting this functioning and the fact that int64 doesn't exist in as3 but can be done with FlasCC.

For Flash, links to a swc generated with FlaCC
Native interface for neko/CPP

On Thursday, April 18, 2013 10:47:09 AM UTC-4, Luca wrote:

[Luca]

Having a library call (especcialy in the c++ case) for every single operation on a number would be really too slow!

My fixed16 abstract only uses floating point arithmetic to implement the division operator (Which on c#/java actually uses integer divide, and it could be made to use integer divide on c++ with use of untyped __cpp__ too). And I see no reason why Fixed16 should not be 100% equivalent across any architecture, whilst I have had many problems with floating point arithmetic not being 100% consistent across machines.

[dlots]

It's interesting you mention something about integer divide being used for floating point division.

1. Notation and fixed point operations on Fixed16 are equivalent across architectures. Are you sure using floating point division is safe?
2. For Flash (and Javascript, perhaps asm has an int64, I don't know) you probably wont be able to inline because an Int64, available with FlasCC. Perhaps haxe.Int64 is implemented a safe way. Everything in Javascript is a float. I haven't looked at asm though.

I haven't tested this and I don't know what goes on with regards to integer division for floating point arithmetic on the platforms you specified, I don't know that at least in theory that rounding floating points (into the fixed point point notation) is safe. This can probably be determined with math. If it is safe, then we need to check if the FPU calculations are in fact faster than the fixed point division implementation on Int64s.

Re: Implementing functions (including trig) that require Int64:
3. How is haxe.Int64 implemented for Javascript and Flash bytecode?
4. There is this article with regards to Int64 on Flash: http://marshgames.com/fixed-point-arithmetic-and-determinism-in-flash/
 - I think it would be possible to inline the implementations for platforms that support Int64 in a reasonable way
 - For Flash, I think it would be possible to do the function call

5. Trig functions are essential to any cross platform games with any rotation otherwise you're limited to doing grid pathfinding.

[dlots]

Okay I understand by reading the above comments what you mean by integer division in C#/Java. If that actually happens than I'm pretty sure with the current implementation you would just lose all of your fractional division when you multiply by 2^16

The division operation is:

(a<<16)/b

[Luca]

... have you actually tried my fixed16 implementation or looked at it?

I don't use Int64 at all, nor is it needed. All of the operations in my fixed16 use just 32bit integers, except for division which uses a float op as there is no integer divide in haxe (and doing the division algorithmically is much slower), and 64bit floats have enough precision to guarantee that (int)((double)a/(double)b) == a/b for valid input (b!=0).

[dlots]

The discussion about Int64 was in regards to the possibility that the int cast is unsafe. I'm far from an expert on the math of floating point so I just want to confirm the division is safe. Is the following not possible?

Lets say the result of your multiplication is some number that is close to the boundary of an integer and has an overflowing precision. Would it not be represented indeterminately across different architectures?

For int32 this would perhaps be values with a result that exceed precision of 2^-21(4.76837158e-7). So, essentially are you sure this is safe if you get a result that is something like:

2147483646.00000001

On Thursday, April 18, 2013 10:47:09 AM UTC-4, Luca wrote:

[dlots]

I think the relevant precision for 2147483646 is actually 2^-22.

[dlots]

I think it is safe:

The worse case of minimizing decimal float precision would be 2^15+2^-16. To then get an issue where it become indeterminant, you would have to divide by at least 2^7. However by that point, your integer portion has freed up additional precision. Should have just explained it for my slow brain :) Tldr, 52 is greater than 31/32.

I'm so sorry about my noob questions regarding this topic as now it appears to be really basic, it's just a little confusing if it's not specified to be 100% safe because you have to think through the conversions. In another thread your posts seemed to indicate you weren't entirely sure it was safe.

[dlots]

Might be nice to have utility from/to macro functions for from Int/Float expressions into a FixedPoint representation instead of multiplying at runtime? I'm not using this gist as I'm not using h3 but could be useful.

[Luca]

Haxe should already be optimising things like 10*1.21564+10-23123.0  into the result at compile time.