Java not deterministic?

Question

I've written a little predator-prey simulation in Java. Even if the rules are quite complicated and end up in a chaotic system the techniques used are simple:

• arithmetics and decisions on basic data types
• no external libraries
• no external systems are included
• no concurrency occurs
• no use of current time or date

So I thought when initializing the system with identical parameters it should output identical results, but it doesn't and I wonder why.

Some thoughts on that: My application uses Randoms, but for that test I initialize them all with a given value, so in my understanding they should create for every run the same outputs in the same order.

I'm iterating through Sets, and I know that the order a Set is iterated isn't defined. But I don't see any reason why a Set that is filled in the same order with the same values should behave different in several runs. Does it?

I'm using a lot of floats. Datatypes where 1 + 1 = 1.9999999999725 are always suspect to me, but I even if their behavior is strange to me, it should be always the same strange. Isn't it?

Garbage Collection isn't deterministic, but as long as I don't rely on destructors I should be safe.

As said above, there is no concurrency and no datatypes depending on the actual time in use.

I can't reproduce that behavior in a simple example. But going through my code, I can't see anything that could be unpredictable. So are any of my assumptions above wrong? Any ideas what I could be missing?

Here's a test to verify my assumptions:

public static void main(String[] args) {
    Random r = new Random(1);
    Set<Float> s = new HashSet<Float>();
    for (int i = 0; i < 1000000; i++) {
        s.add(r.nextFloat());
    }

    float ret = 1;
    int cnt = 0;
    for (Float f : s) {
        float multiply = 0.3f;
        if (cnt++ % 2 == 0) {
            multiply = 0.7f;
        }
        float f2 = (f * multiply);
        ret += f2;
    }

    System.out.println(ret);
}

It results always in 242455.25 for me.

Answer 1

I'm iterating throu Sets, and I know that the order a Set is iterated isn't definied. But I don't see any reason why a Set that is filled in the same order with the same values should behave differnet in several runs. Does it?

It can. The implementation is free to use, for example, the object's location in memory as the key into the underlying hash table. That can vary depending on when garbage collection runs.

Answer 2

You can write a deterministic program in Java. You just need to eliminate the possible sources of non-determinism.

It's hard to know what could be causing non-determinism without seeing your actual code, and concrete evidence of that determinism.

There are any number of library methods that could potentially be sources of non-deterministic behaviour ... depending on how you use them.

For example, the value returned by Object.hashcode() (the first time it is called on an instance) is non-deterministic. And that percolates through to any library that uses hashing. It can definitely affecting the order in which elements of a HashSet or HashMap are returned when you iterate them ... if the element class doesn't override hashcode().

Random number generators may or may not be deterministic. If they are pseudo-random and they are initialized with fixed seeds, then the sequence of numbers produced by each one will be deterministic.

Floating point arithmetic should be deterministic. For any (fixed) set of inputs to an arithmetic expression, the result should always be the same. (I'm not sure that determinism of floating point arithmetic is guaranteed by the JLS, but it would be mighty strange if it happened in practice. As in ... you are running on broken hardware.)

---

FOLLOWUP ... on strictfp and non-determinism.

According to the JLS 15.4:

"Within an expression that is not FP-strict, some leeway is granted for an implementation to use an extended exponent range to represent intermediate results; the net effect, roughly speaking, is that a calculation might produce "the correct answer" in situations where exclusive use of the float value set or double value set might result in overflow or underflow."

This doesn't exactly say how much "leeway" the implementation has in a non-FP-strict expressions. However, I'd have thought that that leeway would not extend to allowing non-deterministic behaviour. I'd have thought that a JIT compiler on a particular platform would always generate equivalent native code for the same expression, and that code would be deterministic. (I can't see any reason for non-determinism ... unless the hardware itself has non-deterministic floating point.) The other possible source of non-determinism might be that behaviour of JIT compiled and interpreted code might be different. But frankly, I think that it would be "nuts" to allow that to happen ... and I think we'd have heard of it.

So while non-FP-strict expression evaluation could be non-deterministic in theory, I think we should discount this ... unless there is clear evidence that it happens in practice.

(Note that I'm talking about real non-determinism, not platform differences.)