Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (115)
games submitted by our members
Games in WIP (562)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  implementation of "instanceof"  (Read 14032 times)
0 Members and 1 Guest are viewing this topic.
Offline emzic

Senior Member





« Posted 2008-06-05 14:18:01 »

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!

www.embege.com - personal website
webstart blendinspect - OpenGL BlendingModes visualization.
Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #1 - Posted 2008-06-05 14:50:46 »

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.

Play Minecraft!
Offline emzic

Senior Member





« Reply #2 - Posted 2008-06-05 15:53:05 »

thanks.

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

www.embege.com - personal website
webstart blendinspect - OpenGL BlendingModes visualization.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Abuse

JGO Knight


Medals: 12


falling into the abyss of reality


« Reply #3 - Posted 2008-06-05 18:45:19 »

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

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline princec

JGO Kernel


Medals: 379
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #4 - Posted 2008-06-06 08:18:49 »

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 Smiley

Offline cylab

JGO Ninja


Medals: 49



« Reply #5 - Posted 2008-06-06 14:41:27 »

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 :/

Mathias - I Know What [you] Did Last Summer!
Offline EgonOlsen
« Reply #6 - Posted 2008-06-06 15:46:14 »

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.

Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #7 - Posted 2008-06-06 18:20:59 »

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:

Quote
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 Smiley

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #8 - Posted 2008-06-06 18:27:18 »

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

Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #9 - Posted 2008-06-06 18:55:19 »

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 Smiley

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 799
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #10 - Posted 2008-06-06 19:04:45 »

But if you read the thread referenced above, also notice that Cas offered the correct solution without instanceof or getObjectType() kind of uglyness.  Smiley
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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline cylab

JGO Ninja


Medals: 49



« Reply #11 - Posted 2008-06-06 19:15:41 »

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 Wink

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


Mathias - I Know What [you] Did Last Summer!
Offline cylab

JGO Ninja


Medals: 49



« Reply #12 - Posted 2008-06-06 19:19:35 »

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.

Mathias - I Know What [you] Did Last Summer!
Offline erikd

JGO Ninja


Medals: 16
Projects: 4
Exp: 14 years


Maximumisness


« Reply #13 - Posted 2008-06-07 12:18:55 »

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.

Quote
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

Offline aldacron

Senior Member


Medals: 9
Exp: 16 years


Java games rock!


« Reply #14 - Posted 2008-06-07 12:20:04 »

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

JGO Kernel


Medals: 379
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #15 - Posted 2008-06-07 16:35:43 »

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 Smiley

Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #16 - Posted 2008-06-08 09:20:26 »

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

Play Minecraft!
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #17 - Posted 2008-06-08 17:09:54 »

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.

See my work:
OTC Software
Offline Abuse

JGO Knight


Medals: 12


falling into the abyss of reality


« Reply #18 - Posted 2008-06-08 18:45:18 »

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?

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #19 - Posted 2008-06-08 19:35:57 »

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

Play Minecraft!
Offline princec

JGO Kernel


Medals: 379
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #20 - Posted 2008-06-09 12:12:59 »

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

Cas Smiley

Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #21 - Posted 2008-06-09 13:20:16 »

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.

Play Minecraft!
Offline Addictman

Senior Member


Medals: 3
Projects: 1


Java games rock!


« Reply #22 - Posted 2008-06-09 13:29:00 »

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!
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #23 - Posted 2008-06-09 13:39:45 »

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

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Addictman

Senior Member


Medals: 3
Projects: 1


Java games rock!


« Reply #24 - Posted 2008-06-09 15:56:52 »

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

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #25 - Posted 2008-06-09 16:15:17 »

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

Click to Play

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Addictman

Senior Member


Medals: 3
Projects: 1


Java games rock!


« Reply #26 - Posted 2008-06-09 16:24:02 »

 Grin
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #27 - Posted 2008-06-09 21:04:21 »

 Undecided

See my work:
OTC Software
Offline xinaesthetic

Senior Member


Medals: 1



« Reply #28 - Posted 2008-09-15 12:12:23 »

I've used instanceof in the past while recursively processing nested hierarchies.
Quote
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.
Offline Jackal von ÖRF

Junior Member





« Reply #29 - Posted 2008-09-15 14:27:53 »

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.

Pages: [1] 2
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

BurntPizza (25 views)
2014-09-21 02:42:18

BurntPizza (17 views)
2014-09-21 01:30:30

moogie (19 views)
2014-09-21 00:26:15

UprightPath (26 views)
2014-09-20 20:14:06

BurntPizza (29 views)
2014-09-19 03:14:18

Dwinin (44 views)
2014-09-12 09:08:26

Norakomi (74 views)
2014-09-10 13:57:51

TehJavaDev (100 views)
2014-09-10 06:39:09

Tekkerue (50 views)
2014-09-09 02:24:56

mitcheeb (71 views)
2014-09-08 06:06:29
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!