Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (536)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Floating Point Determinism in Java  (Read 4359 times)
0 Members and 1 Guest are viewing this topic.
Offline ewjordan

Junior Member





« Posted 2010-10-11 11:45:03 »

So I just discovered yesterday that JBox2d turns out to be wildly non-deterministic, as in, if you run the same physics simulation 10 times in a row (whether or not you're re-starting the entire program or not), you can very easily end up with 10 completely different results, even though locally all the physics seems perfectly normal.  This seems to show up more often with very complex simulations, which is not terribly surprising, chaos and all that meaning that smaller changes are magnified more with more complex systems.

Now, this was surprising to me, to say the least, because every line of code in the engine seems like it should be deterministic, as long as you're on the same machine with the same setup - there's not a Math.random() call in the entire thing (apart from testing code, at least), and I've even tested with everything set so that all Math.* calls are instead handled through lookup tables instead of through the Math library.  Every other operation is straightforward pure Java, almost no library calls, and plain old arithmetic.  Every container iteration (to the extent that we use containers at all, which is very little, most things are arrays) is indexed, so there should be no question about iteration order changing.  Single threaded operation, of course.

I'm aware that you can never rely on floating point consistency across processors or OSes, but this was surprising to me.  Results seem to keep changing even after substantial warmup, once all function compilations have stopped.

Any ideas what might be going on?  Has anyone ever noticed any non-obvious non-deterministic actions in Java? I realize I could probably tag everything with strictfp and ensure floating point consistency, but it just seems like I must be missing something, if no methods are being recompiled and I'm initializing everything in the same way, then running the same simulation, how can I possibly be getting different floating point results?

Is it possible that the compiled code the JVM is producing actually leaves some operation orderings up to the CPU or something like that?  In C++, typically you can at least rely on the same program to produce the same output on the same computer, but maybe the JVM is being more clever in some way?
Offline cylab

JGO Ninja


Medals: 38



« Reply #1 - Posted 2010-10-11 11:58:43 »

I would suspect, that the "problem" lies in non-deterministic delta times in the simulation stepping. System.currentTimeMillis() "hops around" a bit...

Mathias - I Know What [you] Did Last Summer!
Offline Nate

JGO Kernel


Medals: 145
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #2 - Posted 2010-10-11 12:12:21 »

I don't use JBox2D, but there has to be some sort of mathematical integration. Eg, Euler integration. As cylab mentioned, fix the time step or record the deltas and use those to play back the second time if you want the same result.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #3 - Posted 2010-10-11 12:15:03 »

I've been bitten with unexpectedly-different results from what (I thought) should have been deterministic code before - it turned out to be down to iterating over the contents of a hashmap. I hadn't overridden hashCode(), so the order of iteration was determined by the object's location in memory, which obviously changes from run to run. Using a LinkedHashMap enforced the iteration order and everything was rosy.

It doesn't sound like this would apply to you though. If you're already using a fixed timestep then there's something very strange going on...
Online CommanderKeith
« Reply #4 - Posted 2010-10-11 12:37:12 »

Not really related to non-determinism, but I found that using look-up tables for Math operations eg sin cos tan can throw out the numbers by a huge amount even though the errors in the calcs start very small

Also, doesn't the engine use slop factors in some calculations? Maybe they're random?

Offline Roquen
« Reply #5 - Posted 2010-10-11 14:08:55 »

Table based methods are very very bad for many simulation techniques which frequently depend on the properties of the function(s) in question.  As an example, sinusoids are assumed to be continuous everywhere and a table based version is discontinuous at each grid position.  Also note that table based methods have huge relative error to begin with.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 744
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2010-10-11 15:01:24 »

See my old thread:

http://www.java-gaming.org/topics/difference-in-local-and-instance-variable-results/18278/view.html


Doing exactly the same a few times, can result in different values. (or my CPU is b0rked)

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline delt0r

JGO Knight


Medals: 26
Exp: 18 years


Computers can do that?


« Reply #7 - Posted 2010-10-11 15:50:29 »

Riven is it still like that? I didn't want to bump an old thread. But on all my systems I get exactly the same answer. Bit perfect. I am on 64 bit linux and i tried with jvms from 1.5 and up (including 1.7).

At first it didn't cus I didn't use a new instance of each Runnable for each thread... but that was it.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 744
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #8 - Posted 2010-10-11 16:16:10 »

Riven is it still like that?

Couldn't reproduce on my brand new work PC. Will try @ home later.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline ewjordan

Junior Member





« Reply #9 - Posted 2010-10-11 18:22:52 »

Nope, uses fixed time steps (always recommended for physics, FWIW).  Also not a hash map in sight, I've been bitten by that one before, but the one hash map we use is manually managed and completely deterministic.

The slop factors should always be deterministic, they don't randomize at all, what those do is allow for overlap tolerances.

Tried Riven's code, seems to do fine on my computer.

Table based methods are very very bad for many simulation techniques which frequently depend on the properties of the function(s) in question.  As an example, sinusoids are assumed to be continuous everywhere and a table based version is discontinuous at each grid position.  Also note that table based methods have huge relative error to begin with.

Yes, I actually usually don't like using lookups because the speed improvements are not great anyways; as it turns out, trig functions actually aren't that important in the physics engine, they're so infrequently used that it's kind of pointless to optimize over them.

Still, though, shouldn't be causing non-determinism (also, I've tried using Math.* instead, results are the same).

I'm going to try to dig into this deeper, see if I can track down the first place that things go wrong.  Maybe I'm wrong, and I actually do have some indeterminate code somewhere in there that I just don't remember...
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #10 - Posted 2010-10-11 19:04:00 »

Try running in interpreted mode.  It'll help eliminate a few possibilities if you still see the same bad behavior.  Mixed mode execution.  Also the lack of strictfp becomes very unlikely.
Offline thijs

Junior Member




Lava games rock!


« Reply #11 - Posted 2010-10-12 07:54:04 »

I remember this guy having setup a deterministic jbox2d simulation:
http://zetsgames.com/deterministic-physics/

Basically he added strictfp to all classes

<a href="http://www.dzzd.net">3DzzD!</a>
<a href="http://www.arcazoid.com">Arcazoid!</a>
Offline delt0r

JGO Knight


Medals: 26
Exp: 18 years


Computers can do that?


« Reply #12 - Posted 2010-10-12 10:04:20 »

strictfp *should* be required. But traditionally java has defaulted to strictfp despite the performance penalty. IIRC On x86 cpus the internal FP accumulator/register is quite a bit bigger than 64 bits (Or is it only for intermediate results in the FPU?). This changes rounding behavior from IEEE quite a bit, but most importantly, if the result is "pushed" back to ram and reloaded, it is now rounded like a 64bit IEEE number. Thus JIT could really change things here.

One thing i never did work out is what happens at a task switch?

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Roquen
« Reply #13 - Posted 2010-10-12 10:51:10 »

On newer processors you also have stuff like fused multiply add instructions (FMA). 

A context switch (re)stores the full register set state (SEE: FXSAVE & FXRSTOR).

I'm pretty sure that the JRE has always changed x87 to 64-bit mode, so you should never have the 80-bit problem and so doubles would always be strictfp (not so for floats).  This is pretty much moot with SSE processors (except for the noted FMA)
Offline ewjordan

Junior Member





« Reply #14 - Posted 2010-10-12 17:47:52 »

strictfp *should* be required. But traditionally java has defaulted to strictfp despite the performance penalty. IIRC On x86 cpus the internal FP accumulator/register is quite a bit bigger than 64 bits (Or is it only for intermediate results in the FPU?). This changes rounding behavior from IEEE quite a bit, but most importantly, if the result is "pushed" back to ram and reloaded, it is now rounded like a 64bit IEEE number. Thus JIT could really change things here.

I understand these points, but what I don't really understand is, can any of this behavior change without recompiling the code?  I would have thought that behavior like what's kept in registers and what goes to RAM is coming in at the assembly level, not lower, right?

As suspected, it sounds like strictfp probably is the answer, based on thijs's link it's actually worked with JBox2d before, which I didn't know anyone had actually tried - the interesting bit here is that if this works, it's actually a lot easier to get cross-platform consistency in Java than in any other language (including C++, where it's a whole lot of work, and AS3, where as far as I can tell it's absolutely impossible w/o fixed point math) thanks to that flag.  I may try that out just to see for sure that it works, the question comes up a lot (though not enough to use strictfp in the library by default).
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 744
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #15 - Posted 2010-10-12 18:10:29 »

You'd have to add this modifier to every field and method... you'll probably be better off with an ASM ClassAdapter to produce a new JAR.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #16 - Posted 2010-10-12 18:23:03 »

Yeah. That's why I'm suggesting running in interpreted mode first to verify that the problem 'might' be intermediate value related.
Offline delt0r

JGO Knight


Medals: 26
Exp: 18 years


Computers can do that?


« Reply #17 - Posted 2010-10-12 18:25:07 »

As i understand you should only have to add strictfp to the class. Not the fields or methods etc...  

I have no special talents. I am only passionately curious.--Albert Einstein
Offline thijs

Junior Member




Lava games rock!


« Reply #18 - Posted 2010-10-14 09:12:52 »

As i understand you should only have to add strictfp to the class. Not the fields or methods etc...  

Yes, I thought so too.

I may try that out just to see for sure that it works, the question comes up a lot (though not enough to use strictfp in the library by default).

It would be cool if jbox2d supported deterministic simulation as an option, fx like Riven suggest through an manipulation framework like ASM (http://asm.ow2.org/)
Please keep us updated on your findings.. Im particularly interested as I'll have a go on a p2p networked physics simulation in the near future.

<a href="http://www.dzzd.net">3DzzD!</a>
<a href="http://www.arcazoid.com">Arcazoid!</a>
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Riven (12 views)
2014-07-29 18:09:19

Riven (8 views)
2014-07-29 18:08:52

Dwinin (9 views)
2014-07-29 10:59:34

E.R. Fleming (25 views)
2014-07-29 03:07:13

E.R. Fleming (10 views)
2014-07-29 03:06:25

pw (39 views)
2014-07-24 01:59:36

Riven (39 views)
2014-07-23 21:16:32

Riven (27 views)
2014-07-23 21:07:15

Riven (28 views)
2014-07-23 20:56:16

ctomni231 (59 views)
2014-07-18 06:55:21
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!