Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (577)
games submitted by our members
Games in WIP (498)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Alternatives for instanceof  (Read 6676 times)
0 Members and 1 Guest are viewing this topic.
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Posted 2004-07-26 21:51:56 »

Hi all,
It has come to my attention from some developers that instanceof is slow. And that seems to be the bottleneck to my AI routines. So I was wondering on an alternative to instanceof?

Thx a million, DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline jbanes

JGO Coder


Projects: 1


"Java Games? Incredible! Mr. Incredible, that is!"


« Reply #1 - Posted 2004-07-26 21:55:52 »

You can always use an interface like this:

1  
2  
3  
4  
5  
6  
7  
8  
public interface AIObject
{
    public int NEURON = 1;
    public int PULSE = 2;
    public int DECISION = 3;

    public int getObjectType();
}


Simply implement the above interface for each of your custom objects, then call "getObjectType()" to find out which object it is.

Java Game Console Project
Last Journal Entry: 12/17/04
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #2 - Posted 2004-07-26 22:11:53 »

Gotcha, plus/minus a few changes and im there. Thx jbanes

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 abies

Senior Member





« Reply #3 - Posted 2004-07-26 22:21:05 »

As for the speed of instanceof - it depends. It does not have to be slow - for classes, it is perfectly possible to be 2/3 assembler instructions. For interfaces it can be harder.

I suppose that what is killing you is not instanceof itself, but conditional branches (if/else tree). Mispredicted jump is very costly on most architectures. JBanes solution helps here, as you can use tableswitch then, which takes just a single jump (althrough costly).

Anyway, I have heard at some point in the past than casting and instanceof are signs of non-OO programming and I kind of believe it. Of course, it is just a general guide - same as goto can be useful in lexer/parser generation, sometimes instanceof/cast can be best solution. I do not count pre-1.5 collections here, or equals(Object) method - these are java language deficiencies. But if you see method like

1  
2  
3  
4  
5  
6  
7  
8  
9  
class Animal
{
    public void eat(Fruit f) {
        if ( f instanceof Apple ) {
        } else if ( f instanceof Orange) {
        } else if ( f instanceof Peach ) {
        } else ...        
    }
}


you know something is wrong...

Can you tell us more about a case where you need instanceof ? Maybe it can be solved other way ?

P.S.
Multimethods (runtime polymorphism depending on the argument type past 'this') would be cool...

Artur Biesiadowski
Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #4 - Posted 2004-07-26 23:11:11 »

Quote

Anyway, I have heard at some point in the past than casting and instanceof are signs of non-OO programming and I kind of believe it....
Multimethods (runtime polymorphism depending on the argument type past 'this') would be cool...


Yeah, *if* you have all the language-level support for doing full OOP, then you shouldn't see instanceof. Sadly, we're not yet there with full OOP support in java Sad particularly in it's various polymorphic deficiencies (pre-1.5 it only has basic polymorphism). This is a big problem with writing 3rd-party library code, especially user-extensible library code (where what you really want is probably C++ templates + some extras Wink), where full polymorphism can increase your readability, extensibility, maintainability by a huge leap (if you know what you're doing...).

malloc will be first against the wall when the revolution comes...
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #5 - Posted 2004-07-26 23:28:57 »

it is much like the animal eats fruit criteria. However, I know that there will only ever be 2 types of fruit the animal could eat. Either Apple or Orange.

Putting this in a more concrete example, I have:

-AbstractEntity
-Entity extends AbstractEntity
-EntityNode extends AbstractEntity

When I need to pass messages from one entity to another using MessageRouter, I need to know if im passing down to a node or an entity. If its a node, then pass the message down to all its children. If its an Entity then pass it the message.

There will only ever be Entity and EntityNode, so no complicated if else conditional statements.

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

As many wise men said: Premature optimisation is the root of all evil. And that is what I was doing, premature optimisation.

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline cknoll

Junior Member




Flame On!


« Reply #6 - Posted 2004-07-27 03:07:39 »

Quote

When I need to pass messages from one entity to another using MessageRouter, I need to know if im passing down to a node or an entity. If its a node, then pass the message down to all its children. If its an Entity then pass it the message.


Does the message router really need to know this? Or should there be a method  called 'receiveMessage()' on an Entity and a EntityNode such that for an Entity, the message will be handled by itself, while the EntityNode will forward the message to all of it's contained Entitys.  Seems to me that the OO aspect of implementation hiding would come very handy here.

-Chris
Offline darkprophet

Senior Member




Go Go Gadget Arms


« Reply #7 - Posted 2004-07-27 09:29:28 »

MessageRouter has the root EntityNode as an argument. You call the sendMessage on the Router and it will monitor when the message should be sent. Because the message could have a delay.

And yes, Entity does have recieveMessage(Message m) in it because that is what will be sent. The Router does exactly what says on the tin. It routes messages from one entity to another.

DP

Friends don't let friends make MMORPGs.

Blog | Volatile-Engine
Offline princec

JGO Kernel


Medals: 282
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #8 - Posted 2004-07-27 11:06:38 »

I explained how to do this in a diary entry for XAP last year some time but more or less you can do this entirely by using the following pattern:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
public interface Eater {
      public void eat(Fruit fruit);
      public void eatApple(Apple apple);
      public void eatOrange(Orange orange);
      public void eatBanana(Banana banana);
}

public interface Fruit {
      public void eatenBy(Eater eater);
}

public abstract class Animal implements Eater {
      public final void eat(Fruit fruit) {
            fruit.eatenBy(this);
      }
     
      public void eatApple(Apple apple) {
            System.out.println("Burp");
      }
      public void eatOrange(Orange orange) {
            System.out.println("Yum");
      }
      public void eatBanana(Banana banana) {
            System.out.println("Yuk!");
      }
     
}

public class Monkey extends Animal {
      public void eatBanana(Banana banana) {
            System.out.println("Monkey likes bananas!");
      }
}

public class Apple implements Fruit {
      public void eatenBy(Eater eater) {
            eater.eatApple(this);
      }
}

public class Orange implements Fruit {
      public void eatenBy(Eater eater) {
            eater.eatOrange(this);
      }
}

public class Banana implements Fruit {
      public void eatenBy(Eater eater) {
            eater.eatBanana(this);
      }
}

and unless Java's JVM team have been telling us porkies that should optimize very nicely indeed, and it's very easy to extend and provide fine-grained behaviour.

Cas Smiley

Offline MGodehardt

Junior Member




why does the chicken cross the road?


« Reply #9 - Posted 2004-09-02 13:25:20 »

1  
2  
3  
4  
class Applet
{
   public void eat();
}


think OO  Cool Question whats wrong with the Apple ? Roll Eyes
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline K.I.L.E.R

Senior Member




Java games rock!


« Reply #10 - Posted 2004-09-09 14:44:03 »

Quote
1  
2  
3  
4  
class Applet
{
   public void eat();
}


think OO  Cool Question whats wrong with the Apple ? Roll Eyes



Apple does "eat". Though it does it through the tree. The tree's roots absorb moisture in the soil.

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline Breadstick

Senior Newbie




while(true) me.doAction(Act ions.PWN_ALL);


« Reply #11 - Posted 2004-09-11 21:15:12 »

Quote
1  
2  
3  
4  
class Applet
{
   public void eat();
}



Applet is supposed to be Apple, right?

Most of the multiplayer games I've written have used instanceof fairly heavily.  The network layer I wrote allows sending any Object over the network to the server.  When the server or a client receives an Object, I use instanceof to handle the object appropriatly.  For example:

1  
2  
3  
4  
5  
6  
7  
8  
9  
public void objectReceived(Object o)
{
   if(o instanceof Ping)
          handlePing(o);
   else if(o instanceof GameState)
          handleGameState(o);
   else
         .... ....
}


Is this poor practice? Should whoever's using the network layer only have one object that is sent around, so you always know what type it is?
Offline abies

Senior Member





« Reply #12 - Posted 2004-09-11 21:41:35 »

Quote

 The network layer I wrote allows sending any Object over the network to the server.  When the server or a client receives an Object, I use instanceof to handle the object appropriatly.


There are few other solutions.
a) Use packet type id in switch statement.
b) Add message-handling code to packet class itself - even if it is just calling handler.handle(this) to get static dispatch working (like Cas example)
c) use some kind of RMI instead of dispatching method to data manually

Artur Biesiadowski
Offline princec

JGO Kernel


Medals: 282
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #13 - Posted 2004-09-12 11:31:25 »

Use precisely the method I outlined in that code snippet.

Cas Smiley

Offline Jacko

Junior Member





« Reply #14 - Posted 2004-09-12 13:03:32 »

That the Visitor pattern isnt it?
Offline princec

JGO Kernel


Medals: 282
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #15 - Posted 2004-09-12 18:20:01 »

Might be. They started giving names to things we'd all been doing for years not so long ago. Us old farts can't keep up.

Cas Smiley

Offline Middy

Junior Member




Java games rock!


« Reply #16 - Posted 2004-10-07 11:53:46 »

It is the visitor pattern.... and the pattern has been around for like 20 years... so you must be reeealy old  Wink

When do I get my makeMyGameAsILike() extension?
Offline princec

JGO Kernel


Medals: 282
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #17 - Posted 2004-10-07 12:32:44 »

31 and a half Wink Been programming since 7 or so though.

Good grief.

Cas Smiley

Offline JeramieHicks

Senior Newbie




Java games rock!


« Reply #18 - Posted 2004-11-13 14:34:04 »

So what would you do if your Fruit types were dynamic? Suppose a run-time plugin added Grape, which the Monkey wasn't designed to receive. Grape would somehow have to determine that the target animal does/doesn't have an eatGrape() function. You'd end up with something like "is Monkey instanceof GrapeEater", and then each animal implements a set of xxEater interfaces.

It's a shame that polymorphism doesn't automatically do this for us... that is, if the object is of type Grape, then it could automatically call .eat(Grape g) instead of .eat(Fruit f). Just pick the most specific type and work your way up until you find a matching function.

Our system has both run-time dynamic plugin message generators and run-time dynamic plugin message receivers. We use a type combined with the source of the message; that is,

if (obj.Source == FruitTree && obj.type == FruitTree.APPLE)
  eatApple((Apple)obj);

mostly because we didn't want to try to define a unique ID to each type of message (ie, didn't want to create a global message ID namespace). So our message types are only unique within their own source, and we check both.

However, this is little more than a fancy instanceof, and I'm curious what the "proper" solution is supposed to be.
Offline abies

Senior Member





« Reply #19 - Posted 2004-11-13 15:46:20 »

Solution is to use object with real support for OO instead of java...

Jokes aside, I don't think that this problem can be solved in generic case. If you have truly dynamic system, with two independent libraries extending base objects, there is no place to put definition of what should happen when these two subclasses will meet. You need to provide some kind of methods which will describe an object in a way which could be changes by just overriding base object methods.

When I think about multimethods, standard method call notation stops to make sense. What is needed is just a possibility to write
method(ClassA a, ClassB b)
and have it to work on dynamic type of arguments (so you will call method(a,b) instead of a.method(b));
Second thing needed is ability to define such methods out of scope of any class - and I end up with Nice (http://nice.sourceforge.net/index.html). Anything short of that is just a hack.


Artur Biesiadowski
Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #20 - Posted 2004-11-14 08:05:18 »

Quote
It's a shame that polymorphism doesn't automatically do this for us... that is, if the object is of type Grape, then it could automatically call .eat(Grape g) instead of .eat(Fruit f). Just pick the most specific type and work your way up until you find a matching function.


Yes, I've been complaining about this for years - java is not (was not) truly polymorphic under the non-language-specific definitions I was given as an undergrad, and it's a huge problem for library developers. But as I understand it the co-variant types of java 5 fix this "oversight".

The ONLY reason I've ever heard for java not doing this originally was that performance would suffer considerably - each function lookup would have a lot of extra overhead (at least one more indirection, more in cases where otherwise it could have been optimized, and potentially many lookups if there are many "possible" matching functions).

malloc will be first against the wall when the revolution comes...
Offline princec

JGO Kernel


Medals: 282
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #21 - Posted 2004-11-14 08:22:35 »

They did right when they chose this optimization. 99.99% of use cases are closed systems where mostly every interaction between 2 classes is well-defined. Pluggable architectures may be all the rage these days but they're inherently slower, more complicated, and as I say, probably not required for 99.99% of the programs that think they need them.

Cas Smiley

Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #22 - Posted 2004-11-14 12:07:00 »

Quote
They did right when they chose this optimization. 99.99% of use cases are closed systems where mostly every interaction between 2 classes is well-defined. Pluggable architectures may be all the rage these days but they're inherently slower, more complicated, and as I say, probably not required for 99.99% of the programs that think they need them.

Cas Smiley


Indeed. Ultimately, I think the use of explicit syntax to activate this aspect of polymorphism is a good compromise. I was always bothered more by the fact that it was practically impossible in java, short of making a proprietary pre-processing language and pre-compiling all classes Sad; if there had been any way around it I would have been happy (e.g. in C++ you can override it, if you really really want to).

malloc will be first against the wall when the revolution comes...
Offline abies

Senior Member





« Reply #23 - Posted 2004-11-14 16:31:41 »

With Hotspot-class technologies, there is no reason for multiple argument polymorphism to be inherently slower. In same way Hotspot can inline dynamic method calls in optimistic way today and deoptimize it on conflicting class load, multiple argument dispatch could be done by checking only needed combinations of parameters.

SmallEiffel has done similar thing for multiple inheritance (there are no overloaded methods in eiffel, but there is multiple inheritance with explicit overriding of methods). It performed global analysis of entire program and was able to determine what subclasses are possible at which place of program. It was then just a problem of creating dispatch table or binary 'if tree' for correct dispatch - with full possibility of inlining the call. As it turns out, majority of calls are known exactly at compile time - so there is no need for dynamic dispatch at all.
Similar thing could be in theory done during runtime, by optimizing/deoptimizing jit like Hotspot. Of course, in patological cases like plus(A,B) defined for hundreds of various parameters and always called on Object,Object as seen in static context, it would be slow - but probably a lot faster than any hand-made solutions.

As far as the need is concerned... I suppose that 95% of current 'enterprise' application don't need objects at all (value objects are just structures with no logic, transactions are managed in SLSB which are plain functions, view/persistence is decoupled from objects in form of disconnected methods, which are put into object just to call it 'DAO' or 'View'...).

Artur Biesiadowski
Pages: [1]
  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.

xsi3rr4x (22 views)
2014-04-15 18:08:23

BurntPizza (17 views)
2014-04-15 03:46:01

UprightPath (31 views)
2014-04-14 17:39:50

UprightPath (15 views)
2014-04-14 17:35:47

Porlus (31 views)
2014-04-14 15:48:38

tom_mai78101 (57 views)
2014-04-10 04:04:31

BurntPizza (115 views)
2014-04-08 23:06:04

tom_mai78101 (214 views)
2014-04-05 13:34:39

trollwarrior1 (182 views)
2014-04-04 12:06:45

CJLetsGame (189 views)
2014-04-01 02:16:10
List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:05:20
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!