Message question

Coordinator
Feb 16, 2008 at 7:10 PM
Edited Feb 16, 2008 at 7:12 PM
Is it the intent that everything listening for a message will have to check every message?

For example, if we have 100 things listening for messages, and the average object that is listening has 6 message types in the switch statement of things it is listening for, does that mean every message sent would go through 600 checks?

Basically with the input polling system I'm working on, I'll be listening of 9 different message types, all for input type events. It seems a waste that any other type of message would even get sent to the input polling system.

Although I'm not sure how we could register to only receive certain types.
Feb 16, 2008 at 7:27 PM
Yes you would invoke all 100 listeners and there simply bypass the method as the switch statement would simply fall through. I'm not too concerned about this, if it becomes a bottleneck we can certainly do some optimizaion here. But I think we will find other areas of the engine where we can improve considerably more.
Coordinator
Feb 16, 2008 at 7:31 PM
What I am worried about is when you have simple entities that each listen for 4-5 types of messages, and then you instanciate 700 of them in your level. You've now added 3500 checks each time a message is sent. If we truly don't see this as a problem then that is fine, it just seems like a waste. I agree we can use performance more in other areas, but it would suck to fix those and then have a message system that is far too integrated to fix later on.
Feb 16, 2008 at 7:44 PM
You only have 700 checks as it's switch bound on integer value (Unless .net did some bad optimization here as well, shaw any comments), you aren't doing
if (a)
else if(b)
else if(c)
etc

That would be a bad pattern.

We can certainlly do optimization wihout it having a huge effect on the OM.
Coordinator
Feb 16, 2008 at 7:51 PM
I believe even the if, else if, else if gets optimized somewhat like a switch. I do know that a switch if very fast, as it is simply offsets in memory addresses, and simply JMP commands in assembly when needed. I just want us to have thought about this at least once before moving on.
Feb 17, 2008 at 2:30 AM
Honestly, I haven't done much research on JITed x86 code generation for switch statements. Don't forget that jump tables aren't always possible/efficient. You need switch targets that are sequential and integer-based. If you have something like:

switch(myInteger)
{
    case 0: ...
    case 1: ...
    case 2: ...
}

then the compiler can easily generate a jump table using myInteger as the offset into the table. On the other hand, code like:

switch(myInteger)
{
    case 0: ...
    case 98: ...
    case -7975: ...
}

will not be able to efficiently make use of a jump table will need to fall back to the if/else-if/else model.

Switches are only fast if your switch targets sequential. Also, .NET throws another wrench into the works by allowing non-integer switches. For instance, you can switch on strings, floats, arbitrary classes that are comparable, etc. You need to fall back to the if/else-if/else model then.
Feb 17, 2008 at 6:04 AM
We are using interger based switching so I do believe that we are safe there.
Coordinator
Feb 17, 2008 at 6:44 AM
Yes, but I haven't even been checking the order of my case statements to keep them in order (numberically). And developers may not adhere to the order either. If we were basing performance on this fact we'd have to try and enforce this somehow, or let them know in the documentation.
Feb 17, 2008 at 7:20 AM
The order of the case statements is not up to you the language will change these as appropriate. So no need to document that.
Coordinator
Feb 17, 2008 at 5:11 PM


Sturm wrote:
The order of the case statements is not up to you the language will change these as appropriate.


Is that the case? I know with C++ is not, as you must be able to fall through your case statements into others if you choose not to break. Maybe this is why C# chose not to allow falling through. I always assumed they did it just because it was less prone to programmer symantic errors.
Feb 17, 2008 at 7:46 PM
The IL is potimized for this, so I would assume that the jitted code would be too, but then I haven't really actually looked into jitted code. But C# will produce potimized, or indexed jump statement which are bound to the value, so it's as optimum as it can be.
Feb 17, 2008 at 9:19 PM
Edited Feb 17, 2008 at 9:19 PM

Sturm wrote:
The IL is potimized for this, so I would assume that the jitted code would be too, but then I haven't really actually looked into jitted code. But C# will produce potimized, or indexed jump statement which are bound to the value, so it's as optimum as it can be.


Famous last words! These exists a special IL branch instruction for C# switch statements that are integer-based and sequential. So, the compiler will emit this instruction for case labels of 1, 2, 3, etc. or 41, 42, 43, etc., but not 1, 100, 1000, or 1, 3, 7, etc. If it's not strictly sequential like that, the compiler will fall back to the if/else-if/else model. Jump tables are very specialized in the cases they can handle, and the message IDs are not such a case (too many gaps and too large of a range). Also, just because a special IL instruction exists does not mean that the CLR will generate optimized machine code.
Feb 17, 2008 at 9:40 PM
DUH, you are right :S my bad.

So there might be a performance consideration if users have many messages they need to listen to. Then I guess we will need to add a way for users to define wich messages they want to listen to. I would opt for a List<int> providing the range of messages that an event listener would like to listen for. Comments?
Coordinator
Feb 17, 2008 at 10:10 PM
Each thing registers to receive messages right? Well if you were forced to register for specific message types when you did this, then the messaging system should know which ones to send to you.

So for MessageType 3004, it would know that 6 components have registered for that message, and send it down that list of components.

You could have a List of List of Ints ( Dictionary< int, List<int > > ). Each row in the Dictionary is a list of components to recieve messages of that type.

Row 1, Message 0001: Components #1, #7, #15, #32.
Row 2, Message 0002: Components #1, #9, #35

So the message system needs to route MessageType 0002. It uses the Dictionary, gives it the TKey of 0002, which returns to it a list of ints. Each of those ints is a specific component ID. Those IDs tell us where to route that message to.

We'd need a system of some kind so that every component that registered with the message system ended up with a unique ID identifier. I'm not sure if it would need to be completely unique across the network or not, unless we started registering for networked messages by component as well. If it only needs to be unique across a client, a 32-bit integer might suffice, and anytime something was made the server would give it a new ID. If it were unique across the network I'd say a 64-bit ID might be better.

Anyway, just throwing out ideas.
Feb 18, 2008 at 1:31 AM
So how does this help performance? You're introducing a dictionary lookup and list traversal to save a handful of branches.
Feb 18, 2008 at 1:36 AM
I had something a little simpler in mind, why not have a interface IMessageListener which every listener had to implement and it would simply look like this:
interface IMessageListener
{
    List<int> MessageList { get; }
}

And that's it from a dev perspective, we would handle the rest in the engine when a message listener is set up. This way you do not need the componenid entry, which is just a cause for possible id clashes, it potentially makes merging multiple custom modules a pain.
Feb 18, 2008 at 1:38 AM

shawmishrak wrote:
So how does this help performance? You're introducing a dictionary lookup and list traversal to save a handful of branches.


The dictionary lookup is made on int (and of cause use a custom lookup not the default generic lookup) and my suggestion invokes the list of event listeners directly instead of going to the components.
Coordinator
Feb 18, 2008 at 4:34 AM
Edited Feb 18, 2008 at 4:36 AM


shawmishrak wrote:
So how does this help performance? You're introducing a dictionary lookup and list traversal to save a handful of branches.


So what is faster, sending a message to possibly hundreds of entities, which must then traverse the switch of message types each of those entities listen for, or a dictionary lookup for each message type? Honest question, I'm not really sure. Isn't the dictionary sorted like a map, making it decent performance, in release mode at least.

For example:
I setup a test a little while back for work. Doing a search through a C++ STL map, using Int as the key, and filling it will 200 ints. I could search through the map for a random int 0-200, 10,000 times, in 0.89ms (on average, on my T7200 proc).

We should really do some performance tests. We could fake some stuff to get the test going fast. For example, rather than setup a message routing system for the test we could do something like this:

1.) Setup 500 entities, put 10 message types in their switch, and send out 30 messages per frame.
2.) Setup 500 entities, put 10 message type in their switch, and send out 3 messages per frame. But this time:
- We'd also do a Dictionary or List lookup that we'd have to do if we were using a routing system. For a dictionary you'd fill it with 10 ints as keys, and 10 lists. Each list could have 50 of the entities in them. We wouldn't have to send the actual messages through the dictionary but you would still need to traverse the list.

In #2 we'd be sending out 1/10th the messages, because in theory if different entities types listen for different messages, there will be less messages being sent as sending one type might exclude the other 9/10ths of the entities. We'd have less messages being passed, but we could see the cost of dictionary and list lookups.

I didn't put a huge amount of thought into this test, so it may not be entirely valid, again, just throwing out ideas.