Java Array Updating

Question

The following is the code for a method of an object that maintains a list of types (IType[] types) in an array as well as a field that stores the number of non-null types in the array (int typeCount). What the method should do is to resolve all types in the list (resolve either returns the type it was called at or another IType). I am now wondering which of the following implementations is better:

for (int i = 0; i < this.typeCount; i++)
{
    this.types[i] = this.types[i].resolve(markers, context);
    // vs
    IType t1 = this.types[i];
    IType t2 = t1.resolve(markers, context);
    if (t1 != t2)
    {
        this.types[i] = t2;
    }
}

Note that this pattern occurs in many places throughout the project, of which many can be considered boilerplate.

I understand from the text that some elements of the array may be `null`. It means you should check for `null` before calling `resolve`. And the `i < this.typeCount` doesn't smell good. I would prefer a `i < this.types.length`. The code above _may_work if all nulls are effectively grouped at the end of the array. — T.Gounelle, Mar 04 '15 at 17:32
As long as `i < this.typeCount` is true, `this.types[i]` will be true. The `typeCount` and `types` fields are basically inlined from the `ArrayList` implementation. `typeCount` exists so I can initially create `types` as `new IType[3]` without actually stating that it contains 3 types. There is also an `addType` method in the class that increases `typeCount` and 'resizes' the array at wish. — Clashsoft, Mar 04 '15 at 17:38

score 1 · Accepted Answer · answered Mar 04 '15 at 17:48

1

The other answers are not really technically correct.

The correct answer is most likely the are the same, but it depends on the JVM and also arguments passed to the java command.

JVM will inline and optimize code heavily, so even if you use local variables, it does not mean the code will be executed as it is written. At the end of the day JVM will do stack operations according to bytecode instructions. Also JVM can perform speculative execution so that the if condition can be computed before reaching and have almost 0 performance effect.

Performance optimization is root of all evil. You should use the more readable code.

And if you really need it, you have to use microbenchmarking.

answered Mar 04 '15 at 17:48

Crazyjavahacking

9,343
2
31
40

Branching can be expensive - I just ran a test on the second method, with an array of 100 ints. If the branch is always true (t1 == t2) it runs in 45ns, if it is true 75% of the time it runs in 230ns, if it is true 50% of the time (worst case scenario) it runs in 310ns. So saying that the if condition has no performance effect is inaccurate. – assylias Mar 04 '15 at 17:52
Unless you will provide exact details on how did you test it, what you said might and might not be true. – Crazyjavahacking Mar 04 '15 at 17:54
I used jmh but the result is expected - see for example: http://stackoverflow.com/a/11227902/829571 – assylias Mar 04 '15 at 17:56
That result does not mean anything :). Unless you have a program that does exactly the part of code you micro-benchmarked. Most likely the application is much more complicated and much more things then come into consideration. He needs to micro-benchmark his app to be sure. – Crazyjavahacking Mar 04 '15 at 18:33
The application is a compiler and I replaced the well-known List pattern with this in about a dozen places now, and that alone gave me a performance boost of ~40%. But generally, I am now going for the direct assignment version for readability's sake (Also the project *already* has more than 50000 LoC). – Clashsoft Mar 04 '15 at 20:38

score 0 · Answer 2 · answered Mar 04 '15 at 17:19

When in doubt, measure!

But my guess is that the first version is probably more efficient because you remove a branch and replace it by an assignment. Assigning is cheap, branching can be expensive, unless you know that 99% of the time the condition will be the same, in which case it may become more efficient.

When in doubt, measure!

score 0 · Answer 3 · answered Mar 04 '15 at 17:21

With regards to performance we can look at the code and judge that the first one line solution does all the work in one line which makes it repeat the pattern n times. Depending on the amount of items in the array the loop will run O(n) times. Now with regards to the second solution the instruction follows: Load, Assign(Request storage), Assign, Compare, Assign if. So the amount of atom statements is increased by a fair amount. If a lot of objects are present I would go with the first solution. Also, when you compare objects, I would use .equals() to compare which is also another method to take into account.

I'm not using equals here because I am just checking if the array needs to be updated, but otherwise, I see that the first method should be a slightly bit faster (Unless I need the `t1` for something else). — Clashsoft, Mar 04 '15 at 17:23

score 0 · Answer 4 · answered Mar 04 '15 at 20:19

The correct answer is: it depends.

The example like yours is discussed in a cool presentation by Sergey Kuksenko on Hardware Performance Counters (slides 45-49). This example shows that the answer is oppositely different depending on the length of the array.

There are too many factors even on the hardware level (branch misprediction, L1 cache misses etc.), so you can't know beforehand until you measure using the real data set.

Java Array Updating

4 Answers4