Alternatives for instanceof

[darkprophet]

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

[jbanes]

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.

[darkprophet]

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

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

[abies]

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

[blahblahblahh]

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 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 ), where full polymorphism can increase your readability, extensibility, maintainability by a huge leap (if you know what you're doing...).

[darkprophet]

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

[cknoll]

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

[darkprophet]

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

[princec]

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

[MGodehardt]

1   2   3   4

class Applet {    public void eat(); }

think OO   Question whats wrong with the Apple ?

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

[K.I.L.E.R]

1   2   3   4

class Applet {    public void eat(); }

think OO   Question whats wrong with the Apple ?

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

[Breadstick]

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?

[abies]

 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

[princec]

Use precisely the method I outlined in that code snippet.

Cas

[Jacko]

That the Visitor pattern isnt it?

[princec]

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

[Middy]

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

[princec]

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

Good grief.

Cas

[JeramieHicks]

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.

[abies]

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.

[blahblahblahh]

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

[princec]

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

[blahblahblahh]

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

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

[abies]

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