views:

11727

answers:

17

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 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?

A: 

Unless you're doing it in an inner loop, I wouldn't worry about it.

Michael Myers
+39  A: 

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.

Steve
+1  A: 

Generally the reason why the "instanceof" operator is frowned upon in a case like that (where the instanceof is checking for subclasses of this base class) is because what you should be doing is moving the operations into a method and overridding it for the appropriate subclasses. For instance, if you have:

if (o instanceof Class1)
   doThis();
else if (o instanceof Class2)
   doThat();
//...

You can replace that with

o.doEverything();

and then have the implementation of "doEverything()" in Class1 call "doThis()", and in Class2 call "doThat()", and so on.

Paul Tomblin
But sometimes you can't. If you're implementing an interface that has you taking in an Object, and you need to tell which type it is, then instanceof is really the only option. You could try casting, but instanceof is generally cleaner.
Herms
+1  A: 

'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.

Outlaw Programmer
A: 

Instanceof is very fast. It boils down to a bytecode that is used for class reference comparison. Try a few million instanceofs in a loop and see for yourself.

Apocalisp
A: 

You should measure/profile if it's really a performance issue in your project. If it is I'd recommend a redesign - if possible. I'm pretty sure you can't beat the platform's native implementation (written in C). You should also consider the multiple inheritance in this case.

You should tell more about the problem, maybe you could use an associative store, e.g. a Map<Class, Object> if you are only interested in the concrete types.

+8  A: 

Answering your very last question: Unless a profiler tells you, that you spend ridiculous amounts of time in an instanceof: Yes, you're nitpicking.

Before wondering about optimizing something that never needed to be optimized: Write your algorithm in the most readable way and run it. Run it, until the jit-compiler gets a chance to optimize it itself. If you then have problems with this piece of code, use a profiler to tell you, where to gain the most and optimize this.

In times of highly optimizing compilers, your guesses about bottlenecks will be likely to be completely wrong.

And in true spirit of this answer (which I wholeheartly believe): I absolutely don't know how instanceof and == relate once the jit-compiler got a chance to optimize it.

I forgot: Never measure the first run.

Olaf
do profilers profile built-in operators?
Seun Osewa
+1  A: 

You're focusing on the wrong thing. The difference between instanceof and any other method for checking the same thing would probably not even be measurable. If performance is critical then Java is probably the wrong language. The major reason being that you can't control when the VM decides it wants to go collect garbage, which can take the CPU to 100% for several seconds in a large program (MagicDraw 10 was great for that). Unless you are in control of every computer this program will run on you can't guarantee which version of JVM it will be on, and many of the older ones had major speed issues. If it's a small app you may be ok with Java, but if you are constantly reading and discarding data then you will notice when the GC kicks in.

tloach
That is much less true of the more modern java garbage collection algorithms than it ever used to be. Even the simplest algorithms don't care any more how much memory you discard just after you useit - they only care how much is retained across young-generation collections.
Bill Michell
Great, except I'm on the most recent JVM and my computer still crawls when the GC runs. On a dual-core, 3GB ram server. Java is not a language to use if performance actually matters.
tloach
+2  A: 

It's hard to say how a certain JVM implements instance of, but in most cases, Objects are comparable to structs and classes are as well and every object struct has a pointer to the the class struct it is an instance of. So actually instanceof for

if (o instanceof java.lang.String)

might be as fast as the following C code

if (objectStruct->iAmInstanceOf == &java_lang_String_class)

assuming a JIT compiler is in place and does a decent job.

Considering that this is only accessing a pointer, getting a pointer at a certain offset the pointer points to and comparing this to another pointer (which is basically the same as testing to 32 bit numbers being equal), I'd say the operation can actually be very fast.

It doesn't have to, though, it depends a lot on the JVM. However, if this would turn out to be the bottleneck operation in your code, I'd consider the JVM implementation rather poor. Even one that has no JIT compiler and only interprets code should be able to make an instanceof test in virtually no time.

Mecki
Doesn't it have to figure out if o inherits from java.lang.String?
WW
That's why I said it "might" be as fast. In reality it performs a loop, first checking iAmInstanceOf against the class in question, then it goes upwards the inheritance tree of o and repeating this check for every super-class of o (so it it might have to run this loop a couple of times for a match)
Mecki
+6  A: 

InstanceOf is a warning of poor Object Oriented design.

Current JVMs do mean the instanceOf is not much of a performance worry in itself. If you are finding yourself using it a lot, especially for core functionality, it is probably time to look at the design. The performance (and simplicity/maintainability) gains of refactoring to a better design will greatly outweigh any actual processor cycles spent on the actual instanceOf call.

To give a very small simplistic programming example.

if (SomeObject instanceOf Integer) {
  [do something]
}
if (SomeObject instanceOf Double) {
  [do something different]
}

Is a poor architecture a better choice would have been to have SomeObject be the parent class of two child classes where each child class overrides a method (doSomething) so the code would look as such:

Someobject.doSomething();
Demian Krige
I'm aware of that. That was not what I asked.
Josh
Unsure of whether to vote this up or not as it is a good point, but doesn't answer the question asked ...
jklp
I think the code example is actually a very bad one: You cannot extend the class Double, and also you cannot derive Double from some other class. If you had used other classes for the example, it would have been ok.
Brian Schimmel
Also if the child classes of SomeObject are value objects, then you don't want to put the logic in them. E.g. Pie and Roast might not be the correct place for putInOven() and putInMouth() logic.
sk
+1  A: 

In modern Java version the instanceof operator is faster as a simple method call. This means:

if(a instanceof AnyObject){
}

is faster as:

if(a.getType() == XYZ){
}

Another thing is if you need to cascade many instanceof. Then a switch that only call once getType() is faster.

Horcrux7
A: 

Demian and Paul mention a good point; however, the placement of the code to execute really depends on how you want to use the data...

I'm a big fan of small data objects that can be used in many ways. If you follow the override (polymorphic) approach, your objects can only be used "one way".

This is where patterns come in...

You can use double-dispatch (as in the visitor pattern) to ask each object to "call you" passing itself -- this will resolve the type of the object. However (again) you'll need a class that can "do stuff" with all of the possible subtypes.

I prefer to use a strategy pattern, where you can register strategies for each subtype you want to handle. Something like the following. Note that this only helps for exact type matches, but has the advantage that it's extensible - third-party contributors can add their own types and handlers. (This is good for dynamic frameworks like OSGi, where new bundles can be added)

Hopefully this will inspire some other ideas...

package com.javadude.sample;

import java.util.HashMap;
import java.util.Map;

public class StrategyExample {
    static class SomeCommonSuperType {}
    static class SubType1 extends SomeCommonSuperType {}
    static class SubType2 extends SomeCommonSuperType {}
    static class SubType3 extends SomeCommonSuperType {}

    static interface Handler<T extends SomeCommonSuperType> {
        Object handle(T object);
    }

    static class HandlerMap {
        private Map<Class<? extends SomeCommonSuperType>, Handler<? extends SomeCommonSuperType>> handlers_ =
            new HashMap<Class<? extends SomeCommonSuperType>, Handler<? extends SomeCommonSuperType>>();
        public <T extends SomeCommonSuperType> void add(Class<T> c, Handler<T> handler) {
            handlers_.put(c, handler);
        }
        @SuppressWarnings("unchecked")
        public <T extends SomeCommonSuperType> Object handle(T o) {
            return ((Handler<T>) handlers_.get(o.getClass())).handle(o);
        }
    }

    public static void main(String[] args) {
        HandlerMap handlerMap = new HandlerMap();

        handlerMap.add(SubType1.class, new Handler<SubType1>() {
            @Override public Object handle(SubType1 object) {
                System.out.println("Handling SubType1");
                return null;
            } });
        handlerMap.add(SubType2.class, new Handler<SubType2>() {
            @Override public Object handle(SubType2 object) {
                System.out.println("Handling SubType2");
                return null;
            } });
        handlerMap.add(SubType3.class, new Handler<SubType3>() {
            @Override public Object handle(SubType3 object) {
                System.out.println("Handling SubType3");
                return null;
            } });

        SubType1 subType1 = new SubType1();
        handlerMap.handle(subType1);
        SubType2 subType2 = new SubType2();
        handlerMap.handle(subType2);
        SubType3 subType3 = new SubType3();
        handlerMap.handle(subType3);
    }
}
Scott Stanchfield
+3  A: 

I just made a simple test to see how instanceOf performance is comparing to a simple s.equals() call to a string object with only one letter.

in a 10.000.000 loop the instanceOf gave me 63-96ms, and the string equals gave me 106-230ms

I used java jvm 6.

So in my simple test is faster to do a instanceOf instead of a one character string comparison.

using Integer's .equals() instead of string's gave me the same result, only when I used the == i was faster than instanceOf by 20ms (in a 10.000.000 loop)

+1  A: 

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...

A: 

instanceof is very efficient, so your performance is unlikely to suffer. However, using lots of instanceof suggests a design issue.

If you can use xClass == String.class, this is faster. Note: you don't need instanceof for final classes.

Peter Lawrey
A: 

With regard to Peter Lawrey's note that you don't need instanceof for final classes and can just use a reference equality, be careful! Even though the final classes cannot be extended, they are not guaranteed to be loaded by the same classloader. Only use x.getClass() == SomeFinal.class or its ilk if you are absolutely positive that there is only one classloader in play for that section of code.

If a class is loaded by a different classloader, I don't think instanceof will match either.
Peter Lawrey
+1  A: 

The items which will determine the performance impact are:

  1. The number of possible classes for which the instanceof operator could return true
  2. The distribution of your data - are most of the instanceof operations resolved in the first or second attempt? You'll want to put your most likely to return true operations first.
  3. The deployment environment. Running on a Sun Solaris VM is significantly different than Sun's Windows JVM. Solaris will run in 'server' mode by default, while Windows will run in client mode. The JIT optimizations on Solaris, will make all method access able the same.

I created a microbenchmark for four different methods of dispatch. The results from Solaris are as follows, with the smaller number being faster:

InstanceOf 3156
class== 2925 
OO 3083 
Id 3067
brianegge