Integer division?

[Steven Richey]

Is it possible to do integer division without using Std.int() or cast? These are rather slow, I'm trying to optimize a random number generator.

[Juraj Kirchheim]

The backends actually should optimize `Std.int(x / y)` to use integer
division if available on that platform. If there's a backend that
doesn't do it, you should open an issue on github.

> --
> 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/d/optout.

[David Elahee]

If you need really fast rand there should be a random number generator that operate without division ... What is you target and intended use ?

Le 2 juin 2014 19:03, "Steven Richey" <stevenpat...@gmail.com> a écrit :

Is it possible to do integer division without using Std.int() or cast? These are rather slow, I'm trying to optimize a random number generator.

[Steven Richey]

This is for HaxeFlixel's internal RNG, which is providing different results in AS3 and JS due to a difference in the way Haxe's AS3 and JS targets handle integer overflows. The current solution does not use division, but the new method may.

[Steven Richey]

Right now `Std.int(x/y)` is proving to be much slower than `x/y`, which suggests that it's doing the float division and then a cast, rather than optimizing to integer division.

[David Elahee]

Casting double to int is very expensive. Can you bench with Math.floor.round please ?

[David Elahee]

If I were you :

Rng are a big problem so I would make something mathematically portable and hint in the docs about potential speed issue and why not hint to faster strategies (rand maps, faster algorithm) 

:)

[Steven Richey]

Sure, I'm doing 10 million PRNG calls each time, generating integers:

• Flash
• Previous method: ~236ms
• Math.floor: ~1651ms
• Math.round: ~1809ms
• Cast: ~2112ms
• Std.int: ~1991ms
• C++, Windows
• Previous method: ~118ms
• Math.floor: ~1154ms
• Math.round: ~1421ms
• Cast: (crashes)
• Std.int: ~934ms

[David Elahee]

Well nobody should try to do 10 mega random with a general lib random but that is my opinion ;)

[Mike Welsh]

Hi Steven,

As you noted, some platforms don't support integer division/mod, so I think you'll find the floor/cast to be unavoidable and slow on some platforms. Modern JS VMs might be smart enough to JIT this to int ops with proper code output ( | 0 the result). Flash doesn't have an integer divide, so you will always eat the cast there. Cpp should optimize the cast since it can support integer division natively -- you might want to open an issue if that is not the case.

Personally, if I need cross-platform determinism, I would use an RNG that does not rely on division to preserve my sanity. How about Xorshift? It only uses simple shift and bitwise ops, so it would be quite fast, portable, and suitable for games.

http://en.wikipedia.org/wiki/Xorshift

[Daniel Uranga]

I think this might be useful https://groups.google.com/forum/#!topic/haxelang/-I7zQDu7sT8

Look at Hughs solution for Hxcpp

[Hugh]

Yes, I think that "Std.int(  /  )" has become pseudo standard longhand for integer division at compile time.  Currently this this not supported by the hxcpp backend.

I campaigned for Math.idiv, which would work on runtime/dynamic as well, but this has been rejected.  :(

Hugh

[David Elahee]

@hughsando I deeply but humbly think you should start cpp.Math  which would provide an entry point for such native math functions and intrinsics, this would give you leverage to add vectorised cross platform primitives and I am sure flixel or the future flambe would use it at some point.

Yours

--

[Steven Richey]

Thank you all for your input. I think I'll find another method, as clearly integer division is not viable in the manner I had hoped. Previously I had been using a Lehman PRNG, which worked very well, so I'll probably just find a way to use that with special behavior for the JS target that prevents the overflow error.

[Nicolas Cannasse]

Le 02/06/2014 19:18, Steven Richey a écrit :
> This is for HaxeFlixel's internal RNG, which is providing different

> results in AS3 and JS <https://github.com/HaxeFlixel/flixel/issues/1146>

> due to a difference in the way Haxe's AS3 and JS targets handle integer

> overflows <https://github.com/HaxeFoundation/haxe/issues/2971>. The

> current solution does not use division, but the new method may.

I think the one here is pretty cross platform:
https://github.com/ncannasse/h3d/blob/master/hxd/Rand.hx

Best,
Nicolas

[Hugh]

I think cpp.NativeMath is probably the way to go - did you have some specific syntax in mind?

Hugh

[David Elahee]

Hi Huge !

Did my homework and explored the different intrinsic provider, remembered their syntax was horrible but with years it got worse.

Methink we should start small with a cpp.NativeMath with all the regular Carmack tricks.

Then we should stick to haxe naming convention maybe flavored with opengl for typing ( ex saturatedAdd_f32_f32, divide_i32_i32).

We want this code to be readable rather than concise because haxe already provide mechanics to shorten these names for math freaks.

Since auto vectorisation works well these days, we can delay the intrinsic access api.

Second stage (intrinsics) would be to have the equivalent of http://www.agner.org/optimize/ ' s vectorclass. Which is not the most efficient implementation but I think it perfectly matches haxe constraints and leaves room for vectorisation. Alas its licence impeached us to add it to haxe so we ll have to rewrite something similar.

We can delay this until someone really needs it since the 3d community is still young and might probably turn to webgl.

Direct intrinsic access can be done via cpp.Function so i think we can leave it behind for now.

What do you think ?

[Steven Richey]

Nicolas, I will be sure to check out your PRNG method, it looks very interesting!

While this isn't directly related to the topic at hand, does anyone know why Neko would be experiencing float math errors? For example:

trace((20000000 * 48271)% 0x7FFFFFFF);

Returns `1199842497` on CPP and Flash (the correct value) but `-947641600` in Neko. In fact, it doesn't seem that the modulo operator `%` works at all on Neko. However, if I use `Int64` instead of `Float`, I'm able to arrive at the correct solution. Does Neko not have 32-bit `Float` values?

[Nicolas Cannasse]

Are you using neko 2.0 ?

Best,
Nicolas

[Steven Richey]

Yes, just checked and I'm on Neko 2.0.0

[Mike Welsh]

Hi Steven,

-947641600 is in fact the correct answer. 20000000 * 48271 has a type of Int. It's 32-bit integer multiplication, so the full result (96542000000) gets clamped to -947641600. This is a negative value, modulus is signed, and -947641600 is less than 0x7FFFFFFF, so -947641600 % 0x7FFFFFFF returns the same result.

I confirmed that this is the same result with the SWF compilation and CPP... Can you post the code where you are getting 1199842497? The results might change if you are storing intermediate values as Float. For example, if you do 20000000.0 * 48271, the type is Float instaed of Int.

AS3 compilation will indeed probably give 1199842497 because AS3 always promotes a * b to Float. You can alleviate this by truncating the result with Std.int( a * b ), but you might still run into some overflow error with 32-bit * 32-bit multiplication not fitting in the 52-bit precision of a double. That's why you need to use Int32 to guarantee cross-platform 32-bit behavior for some ops.

Hope this helps,

Mike

[Steven Richey]

I see what you mean! I was able to fix my problem by storing the first two values as floats, and ensuring the second number has a decimal component (it's 48271.0 now) to force Neko to do float math. Thank you!