implementation of "instanceof"

[emzic]

hello,

does anyone know how instanceof is implemented in the JVM?

and what are its issues performancewise? is it fast? is it slow?

is it ok to use it in the gameloop, for example to decide between different renderingmodes for different classes?

thanks!

[Markus_Persson]

It's fairly slow and generally considered bad object oritented design. However, if you just use it in a few places for large branches, you're never going to notice it.

[emzic]

thanks.

just out of curiosity, does anyone know how is it implemented? native code?

Games published by our own members! Check 'em out!

[Abuse]

I'd suggest having a look in the virtual machine specification.

In particular :-

http://java.sun.com/docs/books/jvms/second_edition/html/Instructions2.doc6.html#instanceof

To my naive understanding, it sounds like instanceof involves a simple iterative search through the objects parent types.
No doubt some kind of caching mechanism might be employed to reduce the cost of this operation to a high O(1), rather than a low O(n).

[princec]

I seem to recall that the last instanceof check for a hierarchy of classes is cached somewhere so that it's generally much faster in the case where objects are mostly of one type.

Cas

[cylab]

It's fairly slow and generally considered bad object oritented design. However, if you just use it in a few places for large branches, you're never going to notice it.

Can you back this? We exchanged <object> instanceof <class> calls with <object>.getType() == <INTEGER_TYPE_CONSTANT> in xith3d and were quite surprised by the lack of performance boost :/

[EgonOlsen]

I've never noticed instanceof as being a performance problem. I usually try to avoid it, but there are situations, where doing it in another way isn't appropriate. Replacing it by getType()==<YOUR_CONSTANT> is the poor man's solution to get rid of it. I did that myself in the past but i'm not doing it anymore. If i'm too lazy to do it right, i'm simply using instanceof now instead of using that half-baked-pseudo-OO-getType()-solution.

[darkprophet]

I created a thread about this ages ago titled 'alternatives to instanceof' to look at this issue. In the end after some more benchmarking, i concluded:

On a side note, instanceof seemed not to be my bottleneck, infact, it was faster than calling the getType() method !

If I remember correctly, it was an order of magnitude faster too!

DP

[erikd]

But if you read the thread referenced above, also notice that Cas offered the correct solution without instanceof or getObjectType() kind of uglyness. 
TBH, I can't think of a situation where instanceof is the appropriate way?

[darkprophet]

When you have an open structure that can be extended through "child" implementations, but each of the children have a "type" that gets addressed differently to differet listeners maybe?

DP

Games published by our own members! Check 'em out!

[Riven]

But if you read the thread referenced above, also notice that Cas offered the correct solution without instanceof or getObjectType() kind of uglyness. 
TBH, I can't think of a situation where instanceof is the appropriate way?

Do you remember when we were trying to squeeze out the last drip of performance out of Jemu2?

Doing:

1   2   3   4

int[] instructionSequence = ...; Runnable[] instructionExecutors = ...; for( ... i ... )    instructionExecutors[instructionSequence[i]].run();

was slower than a massive switch-table.



So while the 'visitor pattern' hinted by princec is very neat, the JIT turns it into a big jump-table anyway, which probably has similar performance as the dirty way. Going OO certainly won't make it faster.

[cylab]

I used instanceof a lot in the past in conjunction with "tagging interfaces", but nowadays annotations are used for this, though. But I still can think of many different scenarios where I don't want to clutter my API with a visitor pattern, just to do something in an OO way, when I could centralize control flow with a bunch of if/then statements. To follow the example with the Fruits and the Eater from the linked thread: with common sense, I would never apply a visitor pattern here. In a real world, an Eater would try to identify what is on the plate and then decides what action to take to get the served thing eaten. Regardless of good OO principles

TBH I think the "instanceof==bad" attitude is artificial and using instanceof has practically no downside, if not overused.

[cylab]

Replacing it by getType()==<YOUR_CONSTANT> is the poor man's solution to get rid of it. I did that myself in the past but i'm not doing it anymore. If i'm too lazy to do it right, i'm simply using instanceof now instead of using that half-baked-pseudo-OO-getType()-solution.

Actually I think the getType() approach is worse than instanceof. We just tried to squeeze a better performance out of the scenegraph analysis, but this can be considered a failure, so there is even less reason to consider getType() as a solution for anything... either use a visitor pattern or instanceof.

[erikd]

Do you remember when we were trying to squeeze out the last drip of performance out of Jemu2?

Doing:

1   2   3   4

int[] instructionSequence = ...; Runnable[] instructionExecutors = ...; for( ... i ... )    instructionExecutors[instructionSequence[i]].run();

was slower than a massive switch-table.

It was, but somehow isn't anymore.
The M68k emulator now doesn't use switch-tables anymore because nowadays that's the faster way afaik.
Don't know exactly which version of the JRE changed that, but it's something later than 1.4.

So while the 'visitor pattern' hinted by princec is very neat, the JIT turns it into a big jump-table anyway, which probably has similar performance as the dirty way. Going OO certainly won't make it faster.

Not faster maybe, but better maintainable and less depending

[aldacron]

Before the coming of NIO, there was a non-blocking networking architecture someone developed with a bit of JNI. I'm beating myself up trying to remember the name of it and Google isn't helping me. It certainly wasn't an obscure project. Anyway, I remember it was a very performant bit of code. The native part was minimal and most of the work, dispatching Network events and such, was handled on the Java side. I was shocked when I first looked at the source and saw that the dispatcher used instanceof to route the events. My naive assumption had been that instanceof would have been a bottleneck for something like that. From then on I wasn't afraid to use it.

[princec]

instanceof is as fast as you could possibly get for a plugin architecture when you think about it - all the "workarounds" with getType() are probably just naive unoptimised versions of what the JVM is doing under the hood to implement instanceof. But probably without the clever cacheing.

Brain exercise: imagine you're making a plugin architecture for somesuch thing and you want to implement what amounts to a visitor pattern but at the class level. What might that look like? (Invent new syntax if necessary)

Cas

[Markus_Persson]

Wow, I ran some tests, and instanceof really is lightning fast.
I made new Test[10000000] containing 50% Test1 and 50% Test2 objects, then iterated over all of them, calling getValue() on each. This took about 1350 ms.
I made another loop, doing instanceof on each object, testing against both Test1 and Test2, setting the value to what the object call would return. This ran in about 700 ms
Out of curiosity, I also made a loop that did getType() and compared it against a static final int (basically a manual version of instanceof), and this ran in 1350 ms.

instanceof is still bad, imo, as in order to add new code, you have to find all the places you use instanceof and insert code there, instead of having it all encapsulated in one place.. but if you have a tight inner loop that you want to get rid of a costly method call in, instanceof actually seems like a good idea, as it's almost twice as fast (in my very naive test).

[Eli Delventhal]

I think it works very well in simple cases.

For example, I'm working on a simple game where you're a character that runs through a maze and fights monsters and bosses and gets items. Every Room in the maze has a single Entity, which can be null. If an Entity is trying to move and has another Entity in its way, it will only attack the other Entity if its an enemy. There are two extensions of Entity: PlayerEntity and EnemyEntity. Each only wants to attack in the case where (enemy instanceof EnemyEntity) or vise versa.

Because my bottleneck is most certainly in my pathfinding algorithm (A* in a maze), I don't even begin to care about instanceof. It works. Later I might give each Entity a faction or something, and then allow more than just two "teams," but the way it is now, instanceof is fast and works great.

[Abuse]

Wow, I ran some tests, and instanceof really is lightning fast.
I made new Test[10000000] containing 50% Test1 and 50% Test2 objects, then iterated over all of them, calling getValue() on each.

Out of interest, how were the Test1 & Test2 objects arranged in the array? sequentially?

[Markus_Persson]

1   2   3   4

for (int i = 0; i < NUM_OBJECTS; i++)    objects[i] = i % 2 == 0 ? new Test1() : new Test2(); shuffle(objects);

I used a normal Knuth shuffle

[princec]

Try using instanceof to test alternately for one interface and then another (on the same object).

Cas

[Markus_Persson]

How do you mean?

My test was

1   2   3

if (obj instanceof Test1) value = VALUE_1; else if (obj instanceof Test2) value = VALUE_2; else value = VALUE_DEFAULT;

And that was almost twice as fast as both

1	value = obj.getValue();

and

1   2   3   4   5   6

int type = obj.getType(); switch (type) {    case TYPE_1: value = VALUE_1; break;    case TYPE_2: value = VALUE_2; break;    default: value = VALUE_DEFAULT; }

(Those two ran at almost exactly the same speed)

Hmm, I wonder what the speed would be if Test contained a public int type instead of getting it through an accessor..


edit:

Obviously, if you've got many classes, the cost of the if ladder would slowly eat up the speed benefit. Not to mention it's still Bad Code.

[Addictman]

Can you run your test with a more hierarchical approach? For instance, Test1 extends Test2 which extends Test3 or Test4 etc. The "homemade" versions shouldnt see a huge performance hit from this, but I wonder if instanceof does. Interesting nevertheless though!

[Orangy Tang]

Can you run your test with a more hierarchical approach? For instance, Test1 extends Test2 which extends Test3 or Test4 etc. The "homemade" versions shouldnt see a huge performance hit from this, but I wonder if instanceof does. Interesting nevertheless though!

Surely you're getting into an apples<->oranges comparison there? instanceof means it's castable to that type, numeric ids just establish that it's an exact match. A more appropriate comparison would be replacing instanceof with .getClass() == Type.class surely? (which I'd expect to perform the same as the numeric id approach - they're both going to be an accessor and a comparison).

[Addictman]

Yes, it might be apples and oranges, - but if the orange is always tastier, why consider the apple at all?

[Orangy Tang]

Yes, it might be apples and oranges, - but if the orange is always tastier, why consider the apple at all?

[Addictman]

 

[Eli Delventhal]

 

[xinaesthetic]

I've used instanceof in the past while recursively processing nested hierarchies.

interface Item{}
class CollectionItem implements Item{
  List<Item> items;
}

void processItem(Item item){
  if (item instanceof CollectionItem) for (Item i : (CollectionItem) item.items) processItem(i);
  else { ... }
}

Anything fundamentally wrong with that from a performance point of view? Obviously one needs to be aware of the risk of circular references; that's a design concern, not a performance one.

[Jackal von ÖRF]

That sounds like a good place to use http://en.wikipedia.org/wiki/Composite_pattern

I don't think that there is any performance difference. Profile your application before thinking about optimizing performance.