Optimizing multiple dispatch notification algorithm in C#?

Question

Sorry about the title, I couldn't think of a better way to describe the problem. Basically, I'm trying to implement a collision system in a game. I want to be able to register a "collision handler" that handles any collision of two objects (given in either order) that can be cast to particular types. So if Player : Ship : Entity and Laser : Particle : Entity, and handlers for (Ship, Particle) and (Laser, Entity) are registered than for a collision of (Laser, Player), both handlers should be notified, with the arguments in the correct order, and a collision of (Laser, Laser) should notify only the second handler.

A code snippet says a thousand words, so here's what I'm doing right now (naieve method):

    public IObservable<Collision<T1, T2>> onCollisionsOf<T1, T2>()
        where T1 : Entity
        where T2 : Entity
    {
        Type t1 = typeof(T1);
        Type t2 = typeof(T2);
        Subject<Collision<T1, T2>> obs = new Subject<Collision<T1, T2>>();
        _onCollisionInternal += delegate(Entity obj1, Entity obj2)
        {
            if (t1.IsAssignableFrom(obj1.GetType()) && t2.IsAssignableFrom(obj2.GetType()))
                obs.OnNext(new Collision<T1, T2>((T1) obj1, (T2) obj2));
            else if (t1.IsAssignableFrom(obj2.GetType()) && t2.IsAssignableFrom(obj1.GetType()))
                obs.OnNext(new Collision<T1, T2>((T1) obj2, (T2) obj1));
        };
        return obs;
    }

However, this method is quite slow (measurable; I lost ~2 FPS after implementing this), so I'm looking for a way to shave a couple cycles/allocation off this.

I thought about (as in, spent an hour implementing then slammed my head against a wall for being such an idiot) a method that put the types in an order based on their hash code, then put them into a dictionary, with each entry being a linked list of handlers for pairs of that type with a boolean indication whether the handler wanted the order of arguments reversed. Unfortunately, this doesn't work for derived types, since if a derived type is passed in, it won't notify a subscriber for the base type. Can anyone think of a way better than checking every type pair (twice) to see if it matches?

Thanks, Robert

Answer 1

If each Entity had a property that identified its entity type, and you just fetched the value of that property, wouldn't that be faster?

Then if you had a convention for the order of the entities in your handler, so that Laser would always be before player, etc.

Your entity type could be and enum, and the enum order could be your handler object order.

public IObservable<Collision<T1, T2>> onCollisionsOf<T1, T2>()
    where T1 : Entity
    where T2 : Entity
{
    EntityTypeEnum t1 = T1.EntityType;
    EntityTypeEnum t2 = T2.EntityType;

    Subject<Collision<T1, T2>> obs = new Subject<Collision<T1, T2>>();
    _onCollisionInternal += delegate(Entity obj1, Entity obj2)
    {
       if (t1 < t2)
           obs.OnNext(new Collision<T1, T2>((T1) obj1, (T2) obj2));
       else
           obs.OnNext(new Collision<T1, T2>((T1) obj2, (T2) obj1));
    };
    return obs;
}

Answer 2

All that reflection is not going to be fast. Notice how the reflection happens on every collision. That's the problem.

Some thoughts.

Thought number one: visitor pattern.

The standard way to implement reasonably fast double-virtual dispatch in OO languages is via building an implementation of the visitor pattern.

Can you implement a visitor pattern whereby each acceptor in the vistior maintains a list of "things to do in this situation"? Then your adder method consists of identifying the right place to write the new "thing to do", and then add the delegate to that thing. When the collision happens, you start the visitor to do double dispatch, find the delegate of things to do, and invoke it.

Do you need more than double-dispatch ever? Efficient multiple-virtual dispatch is doable but it's not exactly straightforward.

Thought number two: dynamic dispatch

C# 4 has dynamic dispatch. The way it works is we use reflection the first time the call site is encountered to analyze the call site. We then generate fresh new IL dynamically to execute the call, and cache the IL. On the second call, we reflect upon the arguments to see whether they are the exact same types as before. If they are, we re-use the existing IL and just call it. If not, we do the analysis again. If the arguments are typically of only a few types then the cache very quickly starts being only hits and no misses, and performance is actually quite good all things considered. Certainly faster than lots of reflection every single time. The only reflection we do every time is the analysis of the runtime type of the arguments.

Thought number three: implement your own dynamic dispatch

There's nothing magical about what the DLR is doing. It does some analysis once, spits some IL and caches the result. I suspect your pain is happening because you're re-doing the analysis every time.

Answer 3

I am assuming that there are 2 sets of collisions you are after: laser / player and laser / laser. If you were willing to make IObservable< Collision< T1, T2 > > just match those two cases, then you would be able to reduce the delegate to just one check and have everything strong typed for the comparison.

_onCollisionInternal += delegate(T1 obj1, T2 obj2) {
  obs.OnNext(new Collision<T1, T2>( obj1, obj2));
};


public IObservable<Collision<T1, T2>> onCollisionsOf<T1, T2>()
        where T1 : Entity
        where T2 : Entity
    {
        Subject<Collision<T1, T2>> obs = new Subject<Collision<T1, T2>>();
        _onCollisionInternal += delegate(T1 obj1, T2 obj2) {
           obs.OnNext(new Collision<T1, T2>( obj1, obj2));
        };
        return obs;
    }

Observable<Collision<Laser, Player>> lp = onCollisionsOf<Laser, Player>();
Observable<Collision<Laser, Laser>> ll = onCollisionsOf<Laser, Laser>();