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?

Solution 1

Modern JVM/JIT 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.

Solution 2

Approach

I wrote a benchmark program to evaluate different implementations:

1. instanceof implementation (as reference)
2. object-orientated via an abstract class and @Override a test method
3. using an own type implementation
4. getClass() == _.class implementation

I used jmh to run the benchmark with 100 warmup calls, 1000 iterations under measuring, and with 10 forks. So each option was measured with 10 000 times, which takes 12:18:57 to run the whole benchmark on my MacBook Pro with macOS 10.12.4 and Java 1.8. The benchmark measures the average time of each option. For more details see my implementation on GitHub.

For the sake of completeness: There is a previous version of this answer and my benchmark.

Results

| Operation  | Runtime in nanoseconds per operation | Relative to instanceof |
|------------|--------------------------------------|------------------------|
| INSTANCEOF | 39,598 ± 0,022 ns/op                 | 100,00 %               |
| GETCLASS   | 39,687 ± 0,021 ns/op                 | 100,22 %               |
| TYPE       | 46,295 ± 0,026 ns/op                 | 116,91 %               |
| OO         | 48,078 ± 0,026 ns/op                 | 121,42 %               |

tl;dr

In Java 1.8 instanceof is the fastest approach, although getClass() is very close.

Solution 3

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 

Solution 4

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.

Solution 5

I have got same question, but because i did not find 'performance metrics' for use case similar to mine, i've done some more sample code. On my hardware and Java 6 & 7, the difference between instanceof and switch on 10mln iterations is

for 10 child classes - instanceof: 1200ms vs switch: 470ms
for 5 child classes  - instanceof:  375ms vs switch: 204ms

So, instanceof is really slower, especially on huge number of if-else-if statements, however difference will be negligible within real application.

import java.util.Date;

public class InstanceOfVsEnum {

    public static int c1, c2, c3, c4, c5, c6, c7, c8, c9, cA;

    public static class Handler {
        public enum Type { Type1, Type2, Type3, Type4, Type5, Type6, Type7, Type8, Type9, TypeA }
        protected Handler(Type type) { this.type = type; }
        public final Type type;

        public static void addHandlerInstanceOf(Handler h) {
            if( h instanceof H1) { c1++; }
            else if( h instanceof H2) { c2++; }
            else if( h instanceof H3) { c3++; }
            else if( h instanceof H4) { c4++; }
            else if( h instanceof H5) { c5++; }
            else if( h instanceof H6) { c6++; }
            else if( h instanceof H7) { c7++; }
            else if( h instanceof H8) { c8++; }
            else if( h instanceof H9) { c9++; }
            else if( h instanceof HA) { cA++; }
        }

        public static void addHandlerSwitch(Handler h) {
            switch( h.type ) {
                case Type1: c1++; break;
                case Type2: c2++; break;
                case Type3: c3++; break;
                case Type4: c4++; break;
                case Type5: c5++; break;
                case Type6: c6++; break;
                case Type7: c7++; break;
                case Type8: c8++; break;
                case Type9: c9++; break;
                case TypeA: cA++; break;
            }
        }
    }

    public static class H1 extends Handler { public H1() { super(Type.Type1); } }
    public static class H2 extends Handler { public H2() { super(Type.Type2); } }
    public static class H3 extends Handler { public H3() { super(Type.Type3); } }
    public static class H4 extends Handler { public H4() { super(Type.Type4); } }
    public static class H5 extends Handler { public H5() { super(Type.Type5); } }
    public static class H6 extends Handler { public H6() { super(Type.Type6); } }
    public static class H7 extends Handler { public H7() { super(Type.Type7); } }
    public static class H8 extends Handler { public H8() { super(Type.Type8); } }
    public static class H9 extends Handler { public H9() { super(Type.Type9); } }
    public static class HA extends Handler { public HA() { super(Type.TypeA); } }

    final static int cCycles = 10000000;

    public static void main(String[] args) {
        H1 h1 = new H1();
        H2 h2 = new H2();
        H3 h3 = new H3();
        H4 h4 = new H4();
        H5 h5 = new H5();
        H6 h6 = new H6();
        H7 h7 = new H7();
        H8 h8 = new H8();
        H9 h9 = new H9();
        HA hA = new HA();

        Date dtStart = new Date();
        for( int i = 0; i < cCycles; i++ ) {
            Handler.addHandlerInstanceOf(h1);
            Handler.addHandlerInstanceOf(h2);
            Handler.addHandlerInstanceOf(h3);
            Handler.addHandlerInstanceOf(h4);
            Handler.addHandlerInstanceOf(h5);
            Handler.addHandlerInstanceOf(h6);
            Handler.addHandlerInstanceOf(h7);
            Handler.addHandlerInstanceOf(h8);
            Handler.addHandlerInstanceOf(h9);
            Handler.addHandlerInstanceOf(hA);
        }
        System.out.println("Instance of - " + (new Date().getTime() - dtStart.getTime()));

        dtStart = new Date();
        for( int i = 0; i < cCycles; i++ ) {
            Handler.addHandlerSwitch(h1);
            Handler.addHandlerSwitch(h2);
            Handler.addHandlerSwitch(h3);
            Handler.addHandlerSwitch(h4);
            Handler.addHandlerSwitch(h5);
            Handler.addHandlerSwitch(h6);
            Handler.addHandlerSwitch(h7);
            Handler.addHandlerSwitch(h8);
            Handler.addHandlerSwitch(h9);
            Handler.addHandlerSwitch(hA);
        }
        System.out.println("Switch of - " + (new Date().getTime() - dtStart.getTime()));
    }
}

View more solutions

Comments

[MarioRicalde]

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.

[Bill Michell]

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.

[Josh]

I'm aware of that. That was not what I asked.

[tloach]

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.

[billy]

Unsure of whether to vote this up or not as it is a good point, but doesn't answer the question asked ...

[Lena Schimmel]

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.

[sk.]

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.

[E_the_Shy]

Doesn't it have to figure out if o inherits from java.lang.String?

[Mecki]

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)

[Ravisha]

Modern JVM/JIC ..COuld you please mention from which java version these optimiszation have been covered?

[Steve]

I don't have specific java versions, but any JVMs released by the major players (Sun/Oracle, IBM, Apple, etc) from the last 10 years or so could probably be considered "modern" in this regard.

[kgadek]

Always there's someone, who cites Knuth when performance is the topic... Forgetting, that Knuth also stated (in the same article) "In established engineering disciplines a 12 % improvement, easily obtained, is never considered marginal and I believe the same viewpoint should prevail in software engineering", nearly all his work was about efficiency of algorithms and he wrote algorithms in assembly to (inter alia) achieve better performance. Meh...

[tloach]

@David: You don't need require real-time to have issues when your app goes away for a period of time. A fun one I've encountered is a java app that connected to a TCP stream that died when the GC ran because it didn't close the stream first and couldn't handle the overload of network traffic when it came back - it would immediately go into a loop where GC runs, when app resumes it tries to churn through a bunch of data, which made it run out of memory, which triggered the GC, etc. Java is great for a lot of tasks, but not tasks where very strong performance is a requirement.

[prashant]

@tloach sounds to me like bad app design. you talk about "performance" as if it was one-dimensional. I've worked with (and on) plenty of java apps that were, for instance, performant in providing snappy interactive statistical analysis and visualization of very large data sets, or performant in processing very large transaction volumes very quickly. "performance" isn't just one thing, and the fact that someone can write an application that manages memory badly and lets GC get in its own way doesn't mean anything requiring "performance" should be written in something else.

[peterk]

An aside here but would try { ObjT o = (ObjT)object } catch (e) { no not one of these } would be any faster slower ??

[Steve]

If "object" is an instance of ObjT, casting it is a little faster than doing an instanceof, but the difference my quick test found was 10-20ms over 10,000,000 iterations. If "object" isn't an ObjT, though, catching the exception was over 3000x slower - over 31,000ms vs ~10ms for the instanceof.

[Pacerier]

Btw what do you mean by "don't need instanceof for final classes" ?

[Vishy]

A final class cannot have sub classes. In this case x.getClass() == Class.class is the same as x instanceof Class

[Pacerier]

Cool, assuming that x is not null, which would you prefer?

[Vishy]

Good point. It would depend on whether I expect x to be null I suppose. (Or whichever is clearer)

[Pacerier]

Hmm I just realised that we could use java.lang.class.isAssignableFrom as well, are you aware if instanceof keyword internally uses functions like these?

[Vishy]

I doubt instanceof calls a method, but they may use the same underlying code.

[marcorossi]

such a strong argument without any "reference", is completely useless because just opinionated.

[josiah]

@Steve: I agree with marcorossi. I would like to know which the specific performance characteristics are, rather than rely on a blanket statement like this. Otherwise, how would i justify using instanceof in a Code Review - because Steve on SO says so won't fly in the real world. Kudos to your above commend about exception handling vs instanceof, though. That at least gives me some idea of what you are talking about.

[Admin]

+0.(9) for science!

[Admin]

can be optimized or is optimized? source?

[mawia]

@peterk "casting vs instanceOf". Think like implementing your own virtual machine. In case of instanceOf you will refer to a class defination(object Class class) and checks for its parent reference. Compare the cost of this operation to operation involves in trying to assign the object to a variable of ObjT: VM tries to find out if object is of type ObjT(this should involves looking into ObjT Class class), if it is not, VM should raise an exception.Your code catches the exception. All these are extra instructions being executed. Hence casting will perform much worse than instanceOf.

[Tobias Reich]

+ the other 0.1 from me :D

[Pavel]

@TobiasReich So we got +1.0(9). :)

[Michael Dorner]

Ok, another bonus for you. There is enough +1 for everyone! :)

[xenoterracide]

should include _.class.isAssignableFrom, even though it's not asked for, imho.

[Lii]

I don't think this measures anything meaningful at all. The code measures using System.currentTimeMillis() on an operation that is not much more than a single method call, which should give much to low precision. Use a benchmark framework such as JMH instead!

[Michael Dorner]

You are right, I will update my question using JMH from OpenJDK or Caliper from Google as soon as possible

[LegendLength]

Or just do the timing of the whole billion calls rather than per call.

[LegendLength]

But the original poster mentioned performance was critical for this application, so it's not unreasonable to optimize early in that situation. In other words you wouldn't write a 3d game in GWBasic and then at the end say, ok let's start optimizing this, first step is to port it to c++.

[Olaf Kock]

GWBasic might be a great start for 3d games, if there are proper libraries available. But that aside (as it's an artificial argument): OP is not asking for a complete rewrite as optimization. It's about a single construct where we don't even know if the impact is significant (even if there's a better performing way to do the same in the current version of the compiler). I'm firmly standing behind c2.com/cgi/wiki?ProfileBeforeOptimizing and my answer. Preliminary Optimization is the root of all evil! It makes maintenance harder - and maintenance is the aspect that is worth optimizing

[RecursiveExceptionException]

@vaxquis can as its jvm impl specific

[Admin]

@itzJanuary sigh you missed the point of my question here: everybody knows that compiler can optimize foo - but is foo actually currently optimized by Oracle's javac/VM - or is it just possible that it'll do that in the future? Also, I asked the answerer does he have any backing source (be it docs, source code, dev blog) documenting that it indeed can be optimized or is optimized? Without it, this answer is just some random musing about what compiler can possibly do.

[RecursiveExceptionException]

@vaxquis You never mentioned the Hotspot VM but in that case I do not know if it is "optimized".

[Marko Topolnik]

The code also suffers from a clear opportunity to do Dead Code Elimination. The doX() method calls have no lasting effect.

[Michael Dorner]

It flips the sign?

[Holger]

@mawia: the costs of type casts and the instanceof operator are exactly the same in the successful case, as what the JVM does is the same, the only difference is the treatment of null references. In either case, modern JVMs don’t traverse the type hierarchy anymore. The subsequent assignment to the local variable is irrelevant, it has no effect.

[simon.watts]

Recently read that JIT (JVM 8) will optimize a call site for 1 or 2 types by direct calls, but reverts to the vtable if more than two actual types are encountered. So only having two concrete types passing through a call site at runtime represents a performance advantage.

[Azeroth2b]

Which result was java 6 and which was java 7? Have you revisited this under Java 8? More significantly here, you're comparing a length if of instanceofs to what is essential a case statement on ints. I think we would expect an int switch to be lightening fast.

[Xtra Coder]

I can't remember exactly what was happening 5 years ago - I think both Java 6 and Java 7 had similar result, that's why there is only one result provided (provided 2 lines are for different depth of class hierarchy)... and no, i did not try comparing with Java 8. The whole code of test is provided - you may copy/paste it and check in the environments you need (note - nowadays I would use JMH test for this).

[Lodovik]

I saw in your test that for every instanceof X that you do X has no sub-types. This could (theoretically) be optimized by the JVM (similar to how it replaces invokevirtual with direct method call in such cases). Using deeper hierarchies and including interfaces could provide a more accurate result. But I would not expect a significantly different outcome.

[Kimi Chiu]

You should always answer a question. Not just tell them don't do it.

[binboavetonik]

self cooking pie and roast would be awesome though

[Miss Chanandler Bong]

This is the type of answers I like to see.

[rghome]

This should be the accepted answer. The actual accepted answer doesn't answer the question.

[Garret Wilson]

OK, what about string table lookup with switch()? That is, let's say I have to say if(x instanceof Integer || x instanceof Long || x instanceof Short) and I have a long list of things to check. Would it be more efficient to do a switch(x.getClass().getName) and have a lot of case "java.lang.Integer":, etc.? Would the string switch be more efficient than having a lot of instanceof comparisons?

[Darrell Teague]

Check out empirical observations in other answers and in this other question. In general, anything involving a stack trace is going to be much slower. stackoverflow.com/questions/299068/how-slow-are-java-excepti‌​ons

[Dmytro]

This might be because of the if itself. If the distribution of trues and falses is close to even, speculative execution becomes useless, which leads to significant lags.

[JeanValjean]

The JMH test is not well done. You are measuring a cast operation, using no Blackholes. I think your test is reporting a false truth. Especially with regards of measureGETCLASS that is indeed faster than

[Michael Dorner]

I wouldn't agree on that: As far as In understood, Blackholes in JMH prevent dead code elimination. But there is no potential dead code as the sign flip is stored in the object. So it must be evaluated. Or have I misunderstood your comment?

[Alexander Terp]

If I was to speculate, what instanceof does is arguably more complex. A getClass() == check will do a precise 1:1 check, where instanceof checks a hierarchy i.e. myHashSet instanceof Collection would pass, but myHashSet.getClass() == Collection.class would not. Essentially, they are not equivalent operations, so I am not too surprised that the performance is different as well.

[Coder Guy]

Due diligence is important. The more emphasis upon making computers do all the work for us, the more we take advantage of Moore's law as a crutch rather than a gift. While splitting hairs over use of instanceof might be fruitless, I have found in my own organization that the general stigma against thinking about high performance code while you write it has resulted in, not just a few inefficient instructions, but several hundred. We need to load balance better between the carbon-based units and the silicon-based units.

[Coder Guy]

I should add that due diligence includes making time for performance profiling for issues like these that are not certain. I was convinced that using Scala's Either.fold method would be faster than performing a pattern match on it. The latter approach did result in more bytecode as expected, but using Either.fold was actually slower. This was very unexpected.

[blurryrunner]

This code doesn't properly warm up the VM, which will balloon the first loop. That seems to have skewed the results.

[Luke Hutchison]

While I'm a big fan of that Don Knuth quote, there's nothing inherent about instanceof that would lend itself to a particularly fast implementation (you still have to walk up the class hierarchy and compare class pointers). And you can't just apply the Knuth quote to any language feature that is not efficient. Have you ever tried single-stepping through the Java libraries as a method is being invoked reflectively, i.e. through all the security check code etc.? There's no way that will ever be sped up with a smart JIT. Java 8 lambdas are similar, if you've ever looked at a debug trace: bleuch!