Ever worth using an array of length 2 instead of two variables for syntactical reasons?

Question

So I was implementing my own binary search tree and noticed that an ugly if statement appears all too often the way I'm doing it (which possibly isn't the best way, but that's not what we're discussing), based on whether a child of a node is the left or right child, e.g:

if (leftChild)
    parent.setLeft(child.getRight());
else
    parent.setRight(child.getRight());

Then I thought of this:

parent.setChild(childIndex, child.getRight());

Where childIndex is a byte that was determined earlier where leftChild would have been determined.

As you can see this much more concise, but to have it this way I would either have to have an if statement in the setChild method or represent the children as an array of length 2. If we pretend here that this BST requires maximized performance/space efficiency, what kind of trade-off would it be to switch the storage of child node references to a 2-element array, rather than a pair of variables (or even just hide the if statement inside the setChild method).

I know in a real-world situation this might not matter that much, but I'm still interested in which would be the best approach.

I'd opt for readability over a potential small performance gain. — Matthew Adams, Jul 18 '12 at 08:34

aioobe · Accepted Answer · 2012-07-30T10:12:10.057

10

As I understand it, you're asking, which of the following two is more efficient:

if (condition)
    x = value
else
    y = value

and

xyArray[index] = value

First of all any answer is compiler and/or JVM implementation dependent since the JLS doesn't mention any execution times for any types of statements.

That being said, I would suspect that the if-statement would be slightly faster since the JVM doesn't have to compute any array offset and check array bounds.

In any case, this smells like premature optimization to me. Choose approach based on which one is easiest to read and debug.

edited Jul 30 '12 at 10:12

answered Jul 18 '12 at 08:33

aioobe

413,195
112
811
826

I wonder if HotSpot would optimize access to a `private final Node[] children = new Node[2];` to eliminate range checks. All the info is there to ensure it's safe. – Marko Topolnik Jul 18 '12 at 08:46
Yeah. That's an interesting question. There's always the icky case where someone changes the value of `children` through reflection though. – aioobe Jul 18 '12 at 08:47
I've heard of mutating a `private` through reflection, but a `final`? Is that really possible? – Marko Topolnik Jul 18 '12 at 08:51
[Yep.](http://stackoverflow.com/questions/3301635/change-private-static-final-field-using-java-reflection). – aioobe Jul 18 '12 at 08:54
I'm just [reading this one](http://www.azulsystems.com/blog/cliff/2011-10-17-writing-to-final-fields-via-reflection). A very interesting discussion (Cliff Click's blog, Bill Pugh cited, Doug Lea writes in). In short, the JVM **does** aggressively optimize finals under the assumption that they are what they claim to be, and it **does** lead to problems sometimes :) – Marko Topolnik Jul 18 '12 at 08:57
Interesting read indeed. I support such design decision entirely :-) – aioobe Jul 18 '12 at 09:04

score 1 · Answer 2 · answered Jul 18 '12 at 08:41

I believe that if storing as two fields, you're not going to have just one if, your code is going to crawl with them. The if is in all probability more efficient and it is also more efficient memory-wise to have two fields instead of yet another heap-allocated object—a full object at that, with its usual overhead. If your tree is going to be really, really huge (millions of nodes), this is a concern. Also, if each node's payload is tiny compared to the overhead.

Ever worth using an array of length 2 instead of two variables for syntactical reasons?

2 Answers2