Dynamically choose method at runtime; alternatives to Visitor Pattern or Reflection

Question

I'm working on a small game template, with a world comprised of nodes like so:

World
|--Zone
|----Cell
|------Actor
|------Actor
|--------Item

Where a World can contain multiple Zone objects, a Zone can contain multiple Cell objects, and so on.

Each of these implements the Node interface, which has a few methods like getParent, getChildren, update, reset and so on.

I want to be able to execute a given Task on a single node or recursively down the tree from a node (as specified by the Task).

To compound this issue, I would like this to be a "pluggable" system, meaning I want players/developers to be able to add new types to the tree on the fly. I had also considered casting from the base types:

public void doTask(Actor node)
{
    if(!(node instanceof Goblin)) { return; }
    Goblin goblin = (Goblin) node;
}

Initially I was drawn to use the Visitor Pattern to take advantage of double dispatch, allowing each routine (Visitor) to act according to the type of Node being visited. However, this caused a few complications, specifically when I want to add a new Node type to the tree.

As an alternative, I wrote a utility class that uses reflection to find the most specific method applicable to the Node.

My concern now is performance; since there will be a fairly large number of reflective lookups and calls, I'm worried that the performance of my game (which could have hundreds or thousands of these calls per second) will suffer.

Which seems to solve the problem of both patterns, but makes the code for each new Task uglier.

The way I see it, I have three options for allowing this dynamic dispatch (unless I'm missing something obvious/obscure, which is why I'm here):

1. Visitor Pattern
   • Pros
     • Double Dispatch
     • Performance
     • Clean Code in tasks
   • Cons
     • Difficult to add new Node types (impossible without modifying original code)
     • Ugly code during invocation of tasks
2. Dynamic Invocation using Reflection
   • Pros
     • Can add new Node types with abandon
     • Very customizable tasks
     • Clean Code in tasks
   • Cons
     • Poor performance
     • Ugly code during invocation of tasks
3. Casting
   • Pros
     • More performant than reflection
     • Potentially more dynamic than Visitor
     • Clean code during invocation of tasks
   • Cons
     • Code smell
     • Less performant than Visitor (no double dispatch, casting in each invocation)
     • Ugly code in tasks

Have I missed something obvious here? I'm familiar with many of the Gang of Four patterns, as well as the ones in Game Programming Patterns. Any help would be appreciated here.

To be clear, I'm not asking which of these is the "best". I'm looking for an alternative to these approaches.

Emyle

What makes you think reflection isn't performant? – Rosa

What makes you think it is? Especially in something like the world system of a game that requires many updates per second, reflection can hit your performance really hard. – Polyclinic

Have you considered something like akka.io? – Perfumery

why doesn't a factory method work instead of reflection? – Odelet

@Odelet A factory for the Task? I hadn't thought of that, but I don't really see how it applies. – Emyle

@BrianKent Hadn't heard of akka.io but I'll look into it. At a cursory glance it doesn't look like what I need, but I'll dig in a bit more so that I really understand it before I jump to any conlusions – Emyle

Actually they all share a Node interface...why isn't doTask() or getTask() part of that interface? – Odelet

@Odelet there is a getTasks() method in the interface, and it's called with something like node.getTasks().forEach(t - > t.doTask(node)) but at runtime the type of the Node isn't known, which is why the doTask method to be called is chosen reflectively with the node's specific type. The Task interface can accept multiple types, but if a developer using the library adds a new Node type it won't be a part of the interface – Emyle

I don't see why the Node's type needs to be known at run time, so long as you act upon it polymorphically through interface methods, if it isnt part of the interface, use a wrapper or adapter pattern – Odelet

The issue with that is that I want others to be able to add new types to the tree; this can't be done without modifying the original source: gist.github.com/floralvikings/f31f3501ed9476bc8174 – Emyle

A static OOP structure is going to be at odds with your pluggability requirement. (Not to mention your hierarchy does not appear to abide the "is-a" requirement. An Item is really a World?). If you want this structure to be truly runtime dynamic, you are going to be forced to decouple your data model (the nodes) from the behavior (the tasks). Once the data and behavior is decoupled, you are essentially message passing (which is why I suggested akka). – Perfumery

I would like to see the code where these Nodes are actually inserted into the WorldNode tree – Odelet

My diagram isn't the clearest; the Item class doesn't inherit from World, it's contained in it; all the classes just implement Node. Decoupling the behavior of the nodes is actually the whole point so I'm going to definitely look into akka some more – Emyle

@CalebBrinkman, akka has builtin support for hierarchies which would naturally translate from your desired cascading task behavior. And as your amount of nodes grows, asynchronicity and parallelism are very likely going to be far more important performance concerns than fretting over a little reflection overhead. – Perfumery

Answer 1

So after some research into Java 8 Lambdas and how they can be constructed reflectively, I came up with the idea of creating a BiConsumer from the Method object I had obtained reflectively, with the first argument being the instance on which the method should be invoked and the second argument being the actual argument of the method:

private static <T, U> BiConsumer<T, U> createConsumer(Method method) throws Throwable {
    BiConsumer<T, U> consumer = null;
    final MethodHandles.Lookup caller = MethodHandles.lookup();
    final MethodType biConsumerType = MethodType.methodType(BiConsumer.class);
    final MethodHandle handle = caller.unreflect(method);
    final MethodType type = handle.type();

    CallSite callSite = LambdaMetafactory.metafactory(
          caller,
          "accept",
          biConsumerType,
          type.changeParameterType(0, Object.class).changeParameterType(1, Object.class),
          handle,
          type
    );
    MethodHandle factory = callSite.getTarget();
    try {
        //noinspection unchecked // This is manually checked with exception handling.
        consumer = (BiConsumer<T,U>) factory.invoke();
    }catch (ClassCastException e) {
        LOGGER.log(Level.WARNING, "Unable to cast to BiConsumer<T,U>", e);
    }
    return consumer;
}

Once this BiConsumer has been created, it is cached in a HashMap using the parameter type and method name as a key. It can then be invoked like so:

consumer.accept(nodeTask, node);

This method of invocation almost entirely eliminates the invocation overhead incurred by reflection, but it does have a couple of issues/constraints:

• Because of the use of BiConsumer, only one parameter may be passed into the method (the first argument to the accept method must be the instance that should have the method invoked on it).
  • This is fine for my purposes, I only want to pass one argument anyway.
• There is a non-trivial performance overhead when invoking a method with parameter types that haven't been seen before, as it must first be searched for reflectively.
  • Again, for my purposes this is OK; the number of acceptable node types will not be very large and will be quickly cached as they are seen. After this first "discovery" of the appropriate method for combinations of parameter types, the overhead is very small (constant, I believe, as it's a simple HashMap lookup).
• Requires Java 8 (which I was using already anyway)

I could clarify this code a bit by using a custom functional interface (something like an Invoker class instead of Java's BiConsumer) but as of right now it does exactly what I want with the performance I want.

Emyle

Why return null in the case of a ClassCastException? – Motivate

This was just a proof-of-concept to make sure this worked and performed as expected, there wasn't a lot of thought put into error handling :-) – Emyle

Answer 2

I think that if you cannot have a static factory class then it is a tough problem. If a static factory is allowed, then perhaps this short example might provide some ideas.

This sort of approach allows for run-time insertion of INode instances into the tree (WorldNode), however, it doesn't answer how these concrete INodes are created. I would hope you would have some kind of factory pattern.

    import java.util.Vector;

    public class World {

      public static void main(String[] args) {
        INode worldNode = new WorldNode();
        INode zoneNode = new ZoneNode();

        zoneNode.addNode(new GoblinNode());
        zoneNode.addNode(new GoblinNode());
        zoneNode.addNode(new GoblinNode());
        zoneNode.addNode(new GoblinNode());
        worldNode.addNode(zoneNode);

        worldNode.addNode(new ZoneNode());
        worldNode.addNode(new ZoneNode());
        worldNode.addNode(new ZoneNode());

        worldNode.runTasks(null);
      }
    }

    interface INode {
      public void addNode(INode node);
      public void addTask(ITask node);
      public Vector<ITask> getTasks();
      public void runTasks(INode parent);
      public Vector<INode> getNodes();
    }

    interface ITask {
      public void execute();
    }

    abstract class Node implements INode {
      private Vector<INode> nodes = new Vector<INode>();
      private Vector<ITask> tasks = new Vector<ITask>();

      public void addNode(INode node) {
        nodes.add(node);
      }

      public void addTask(ITask task) {
        tasks.add(task);
      }

      public Vector<ITask> getTasks() {
        return tasks;
      }

      public Vector<INode> getNodes() {
        return nodes;
      }

      public void runTasks(INode parent) {
        for(ITask task : tasks) {
          task.execute();
        }
        for(INode node : nodes){
          node.runTasks(this);
        }
      }
    }

    class WorldNode extends Node {
      public WorldNode() {
        addTask(new WorldTask());
      }
    }

    class WorldTask implements ITask {
      @Override
      public void execute() {
        System.out.println("World Task");
      }
    }

    class ZoneNode extends Node {
      public ZoneNode() {
        addTask(new ZoneTask());
      }
    }

    class ZoneTask implements ITask {

      @Override
      public void execute() {
        System.out.println("Zone Task");
      }
    }

    class GoblinNode extends Node {
      public GoblinNode() {
        addTask(new GoblinTask());
      }
    }

    class GoblinTask implements ITask {

      @Override
      public void execute() {
        System.out.println("Goblin Task");
      }
    }

Output:

World Task
    Zone Task
        Goblin Task
        Goblin Task
        Goblin Task
        Goblin Task
Zone Task
Zone Task
Zone Task

Odelet

Answer 3

The reflection idea is fine - you'll just need to cache the lookup result based on argument types.

The visitor pattern can be expanded by user program. For example, given the classic Node and Visitor definitions in visitor pattern, user can define MyNode, MyVisitor

interface MyVisitor extends Visitor
{
    void visit(MyNode m);
    void visit(MyNodeX x);
    ...
}

interface MyNode extends Node
{
    @Override default void accept(Visitor visitor)
    {
        if(visitor instanceof MyVisitor)
            acceptNew((MyVisitor) visitor);
        else
            acceptOld(visitor);
    }

    void acceptNew(MyVisitor visitor);
    void acceptOld(Visitor visitor);
}

class MyNodeX implements MyNode
{
    @Override public void acceptNew(MyVisitor visitor)
    {
        visitor.visit(this);
    }
    @Override public void acceptOld(Visitor visitor)
    {
        visitor.visit(this);
    }
}
// problematic if MyNodeX extends NodeX; requires more thinking

In general, I don't like visitor pattern; it is quite ugly, rigid, and intrusive.

---

Basically, the problem is that given a node type and a task type, lookup a handler. We can solve this by a simple map of (node,task)->handler. We can invent some APIs for bind/lookup handlers

register(NodeX.class, TaskY.class, (x,y)->
{ 
    ...  
});

or with anonymous class

new Handler<NodeX, TaskY>()  // the constructor registers `this`
{
    @Override public void handle(NodeX x, TaskY y)
    ...

To invoke a task on a node,

invoke(node, task);
// lookup a handler based on (node.class, task.class)
// if not found, lookup a handler on supertype(s). cache it by (node.class, task.class)

Danielldaniella

Caching the method does not resolve the performance problem. The reflection overhead arises at invocation time, not at lookup time. Java 8 MethodHandles claim that the overhead arises at lookup time. So this could be an alternative. – Aftertime

in OP's code sample that does reflection, it is a little complicated and expensive to find the proper method to invoke; and the lookup process is repeated for each invocation; I suggest to cache the lookup result. – Danielldaniella

Answer 4

If you are looking for performance - the visitor pattern is the way to go. I personally would't even have come up with reflection as a solution to this, as it seems unreal and overcomplicated. Casting works, but in an OO environment it is usually considered code smell and should be avoided (for example with the visitor pattern).

Another important aspect is readability vs writability: The visitor pattern might be a bit more work and requires more maintenance when adding nodes, but it is definitely easier to read and usually easier to understand as well. Reflection is in both aspects a no-go, and casts are, again, code smell.

Polyclinic

If performance was my only concern, I'd be 100% with you; unfortunately it's very important to be able to add new types to the tree, which is very hard using the Visitor Pattern (actually impossible for someone using this code without modifying the original library) so I'd really rather avoid using it if possible. The reflection itself is "hidden" in the framework; someone using it would never actually have to see/work with the reflection code, so that's not as much an issue. – Emyle

I'm really looking for an alternative to the three approaches I mentioned, rather than a comparison of the three; I'll edit the question to reflect that – Emyle