The performance impact of using instanceof in Java

Question

I am working on an application and one design approach involves extremely heavy use of the instanceof operator. While I know that OO design generally tries to avoid using instanceof, that is a different story and this question is purely related to performance. I was wondering if there is any performance impact? Is is just as fast as ==?

For example, I have a base class with 10 subclasses. In a single function that takes the base class, I do checks for if the class is an instance of the subclass and carry out some routine.

One of the other ways I thought of solving it was to use a "type id" integer primitive instead, and use a bitmask to represent categories of the subclasses, and then just do a bit mask comparison of the subclasses "type id" to a constant mask representing the category.

Is instanceof somehow optimized by the JVM to be faster than that? I want to stick to Java but the performance of the app is critical. It would be cool if someone that has been down this road before could offer some advice. Am I nitpicking too much or focusing on the wrong thing to optimize?

Answer 1

I thought it might be worth submitting a counter-example to the general consensus on this page that "instanceof" is not expensive enough to worry about. I found I had some code in an inner loop that (in some historic attempt at optimization) did

if (!(seq instanceof SingleItem)) {
  seq = seq.head();
}

where calling head() on a SingleItem returns the value unchanged. Replacing the code by

seq = seq.head();

gives me a speed-up from 269ms to 169ms, despite the fact that there are some quite heavy things happening in the loop, like string-to-double conversion. It's possible of course that the speed-up is more due to eliminating the conditional branch than to eliminating the instanceof operator itself; but I thought it worth mentioning.

Answer 2

Modern JVM/JIC compilers have removed the performance hit of most of the traditionally "slow" operations, including instanceof, exception handling, reflection, etc.

As Donald Knuth wrote, "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." The performance of instanceof probably won't be an issue, so don't waste your time coming up with exotic workarounds until you're sure that's the problem.

Answer 3

If speed is your sole aim then using int constants to identify sub classes seems to shave a milliseconds of the time

static final int ID_A = 0;
static final int ID_B = 1;
abstract class Base {
  final int id;
  Base(int i) { id = i; }
}
class A extends Base {
 A() { super(ID_A); }
}
class B extends Base {
 B() { super(ID_B); }
}
...
Base obj = ...
switch(obj.id) {
case  ID_A: .... break;
case  ID_B: .... break;
}

terrible OO design, but if your performance analysis indicates this is where you bottleneck is then maybe. In my code the dispatch code takes 10% of total execution time and this maybe contributed to a 1% total speed improvement.

Answer 4

instanceof is probably going to be more costly than a simple equals in most real world implementations (that is, the ones where instanceof is really needed, and you can't just solve it by overriding a common method, like every beginner textbook as well as Demian above suggest).

Why is that? Because what is probably going to happen is that you have several interfaces, that provide some functionality (let's say, interfaces x, y and z), and some objects to manipulate that may (or not) implement one of those interfaces... but not directly. Say, for instance, I have:

w extends x

A implements w

B extends A

C extends B, implements y

D extends C, implements z

Suppose I am processing an instance of D, the object d. Computing (d instanceof x) requires to take d.getClass(), loop through the interfaces it implements to know whether one is == to x, and if not do so again recursively for all of their ancestors... In our case, if you do a breadth first exploration of that tree, yields at least 8 comparisons, supposing y and z don't extend anything...

The complexity of a real-world derivation tree is likely to be higher. In some cases, the JIT can optimize most of it away, if it is able to resolve in advance d as being, in all possible cases, an instance of something that extends x. Realistically, however, you are going to go through that tree traversal most of the time.

If that becomes an issue, I would suggest using a handler map instead, linking the concrete class of the object to a closure that does the handling. It removes the tree traversal phase in favor of a direct mapping. However, beware that if you have set a handler for C.class, my object d above will not be recognized.

here are my 2 cents, I hope they help...

Answer 5

'instanceof' is actually an operator, like + or -, and I believe that it has its own JVM bytecode instruction. It should be plenty fast.

I should not that if you have a switch where you are testing if an object is an instance of some subsclass, then your design might need to be reworked. Consider pushing the subclass-specific behavior down into the subclasses themselves.

Answer 6

I also prefer an enum approach, but I would use a abstract base class to force the subclasses to implement the getType() method.

public abstract class Base
{
  protected enum TYPE
  {
    DERIVED_A, DERIVED_B
  }

  public abstract TYPE getType();

  class DerivedA extends Base
  {
    @Override
    public TYPE getType()
    {
      return TYPE.DERIVED_A;
    }
  }

  class DerivedB extends Base
  {
    @Override
    public TYPE getType()
    {
      return TYPE.DERIVED_B;
    }
  }
}