Geeks With Blogs
Running with Code Like scissors, only more dangerous

Lately I've been doing some interesting work that I've alluded to elsewhere dealing with the binary communications protocol hosted Blizzard Entertainment's Battle.net game service.  It's kind of what brought me into C# development in the first place; I walked away from it for a few years, and now I've been digging into it again.  And I've learned a few things between then and now; I've been particularly interested in looking at the under-the-hood workings of the CLR, and so I'm starting a new series on "Speedy C#".  Let me be the first to point out that optimizations have a unique way of obfuscating code; particularly in this example, if you don't explain why you're doing what you're doing, and exactly what result you expect, you could run into trouble, or worse, your colleagues may run into trouble.  So while going through this series,

A little background: the binary protocol used for Battle.net has about 80 or so message IDs, which generally have a different structure for each.  The messages don't necessarily come as a result of sending a message first, and so the general pattern is that a receive loop is in place that receives the data, parses it, and then sends events back to the client.  In fact, there are no synchronous requests defined by the protocol.

When I first started programming, I had handlers for every message ID in a switch/case branching construct:

   1: switch (packetID)
   2: {
   3:     case BncsPacketId.Null:
   4:         break;
   5:     case BncsPacketId.EnterChat:
   6:         string ecUniqueName = pck.ReadNTString();
   7:         string ecStatstring = pck.ReadNTString();
   8:         string ecAcctName = pck.ReadNTString();
   9:         EnteredChatEventArgs ecArgs = new EnteredChatEventArgs(ecUniqueName, ecStatstring, ecAcctName);
  10:         OnEnteredChat(ecArgs);
  11:         break;
  12:     // ... ad nauseum
  13: }

When I looked at this in ildasm, I noticed that it declared a max stack size of something ridiculously large (sorry I don't have a specific number - it was about 6 years ago).  I also noticed that there were a LOT of branches, but not necessarily in the order in which I had written them.  The compiler had intrinsically optimized my code to perform a binary search.  Fairly interesting, optimal speed at O(log N), and something that most of us wouldn't have thought of naturally!

When I last revisited this type of development, I broke all of my handlers out of the branching conditional, calling a separate method to handle each message.  This had a nice effect of making me not have to worry about variable name collisions like I had to in the above example, and it made the code slightly more maintainable.  It's difficult to gauge on paper whether that would have been better or worse performance; there was certainly far less stack allocation, but there was an additional (potentially virtual) method call.

The latest code incorporated into my library takes a different approach: I declare a Dictionary<BncsPacketId, ParseCallback>, populate it with default handlers, and allow existing handlers to be replaced and new ones to be added provided certain conditions are met.  This has had several benefits:

  • According to MSDN, Dictionary<TKey, TValue> approaches O(1), which is (obviously) the fastest lookup we could hope for. 
  • Adding support for new or changed messages does not require change to the code, only that a handler be updated via a method call.
  • Handlers can be switched at runtime.

In this code, a ParseCallback is a delegate that accepts information provided by the message header and the message contents themselves.  This has modified the entire parsing thread to be:

   1: private void Parse()
   2: {
   3:     try
   4:     {
   5:         while (IsConnected)
   6:         {
   7:             m_parseWait.Reset();
   8:  
   9:             while (m_packetQueue.Count == 0)
  10:             {
  11:                 m_parseWait.WaitOne();
  12:             }
  13:  
  14:             ParseData data = m_packetQueue.Dequeue();
  15:             if (m_packetToParserMap.ContainsKey(data.PacketID))
  16:             {
  17:                 m_packetToParserMap[data.PacketID](data);
  18:             }
  19:             else
  20:             {
  21:                 switch (data.PacketID)
  22:                 {
  23:                     #region SID_NULL
  24:                     case BncsPacketId.Null:
  25:                         break;
  26:                     #endregion
  27:                     default:
  28:                         Trace.WriteLine(data.PacketID, "Unhandled packet");
  29:                         if (!BattleNetClientResources.IncomingBufferPool.FreeBuffer(data.Data))
  30:                         {
  31:                             Debug.WriteLine(data.PacketID, "Incoming buffer was not freed for packet");
  32:                         }
  33:                         break;
  34:                 }
  35:             }
  36:         }
  37:     }
  38:     catch (ThreadAbortException)
  39:     {
  40:         // exit the thread gracefully.
  41:     }
  42: }

Now, obviously, this is a very domain-specific optimization that I wouldn't make unless it makes sense in the problem domain.  For mine, it does; I am writing the library so that others are able to integrate functionality without having to worry about modifying code that they maybe are not familiar with or are worried about breaking.  If you absolutely need to use this method, be sure to document why.

The "Speedy C#" Series:

Posted on Tuesday, August 5, 2008 10:05 PM | Back to top


Comments on this post: Speedy C#, Part 1: Optimizing Long if-else or switch Branches

# re: Speedy C#, Part 1: Optimizing Long if-else or switch Branches
Requesting Gravatar...
Hi,

Nice article, sounds like you have just implemented the command pattern. I am looking forward to the rest of you posts.

Cheers, Paul.
Left by Paul Kinlan on Aug 06, 2008 1:09 AM

# re: Speedy C#, Part 1: Optimizing Long if-else or switch Branches
Requesting Gravatar...
Thanks! I'm not quite sure that this qualifies as the command pattern; I'm not treating the callbacks specifically like objects. Still, you raise an interesting point, and it might be appropriate to change this up in the future.
Left by Rob on Aug 06, 2008 9:02 AM

# re: Speedy C#, Part 1: Optimizing Long if-else or switch Branches
Requesting Gravatar...
Interesting read, seems to have shortened your code immensely.
Left by Chriso on Aug 06, 2008 6:30 PM

# re: Speedy C#, Part 1: Optimizing Long if-else or switch Branches
Requesting Gravatar...
Nice :)

Also i am certain the Dictionary<TKey, TValue> is fast i use it often. But if i am correct the DictionaryBase class (abstract) uses a HashTable internally, so wouldn't HashTable be a little bit better performance wise?

Sorry to go off topic, good work though!
Left by Paul on Aug 07, 2008 12:57 AM

# re: Speedy C#, Part 1: Optimizing Long if-else or switch Branches
Requesting Gravatar...
A Dictionary is generic Hashtable
Left by Jay on Dec 01, 2008 2:50 PM

# re: Speedy C#, Part 1: Optimizing Long if-else or switch Branches
Requesting Gravatar...
When the IDs are tightly packed, you could use a List instead of a Dictionary, and check for boundaries and nulls (Wrap the list into a Dictionary-Like class for easier usage).

This should be cheaper than a dictionary lookup which involves Hashing.

Also, the "tryGetValue"-Method on the dictionary could help you save one of the two lookups (ContainsKey and []) you currently have.


HTH,
markus
Left by Markus Schaber on Mar 20, 2009 9:47 AM

# re: Speedy C#, Part 1: Optimizing Long if-else or switch Branches
Requesting Gravatar...
I have some networking code that looks almost exactly like your "before" scenario. I'm definitely going to try this. I'm curious though - I've heard that invoking delegates is costly (at least in the context of events), as compared to calling methods directly. Does that factor into the speed considerations here at all?
Left by Kai on Apr 06, 2010 12:33 PM

# re: Speedy C#, Part 1: Optimizing Long if-else or switch Branches
Requesting Gravatar...
Be careful with using objects that are reference types instead of value types with a Dictionary unless you have created your own GetHashValue() function that properly handles it for you. The compiler defaults to the first member variable in your class or struct as the only value to use for hashing otherwise, which can greatly affect your desire to "approach O(1)" for look-up. I would suggest reading the section on overriding hash code generation in the "Effective C#" book by Bill Wagner.
Left by Matt Kerr on Mar 28, 2011 9:06 AM

# re: Speedy C#, Part 1: Optimizing Long if-else or switch Branches
Requesting Gravatar...
@Matt Kerr: I don't know for certain, but I'm pretty sure that the compiler does not "default to the first member variable in your class ... for hashing." First of all, classes are reference types (unlike structs), so they are represented most simply as memory address locations. Hash codes need only be unique, and I'm sure I've read that the default hash code for any reference type is simply its memory address.

As for value types (structs, primitives, etc), I don't know how they are hashed by default. They are stored on the stack, so they wouldn't have a memory location in the heap.
Left by Pat on Jun 09, 2011 10:54 AM

# re: Speedy C#, Part 1: Optimizing Long if-else or switch Branches
Requesting Gravatar...
Objects are locatable in .NET due to the use of a compacting garbage collector. Thus, the memory location cannot participate in the hash calculation.

Rather, objects are assigned a hash code on creation. This is sufficient to ensure reference semantics. The value remains unchanged for the lifetime of the object. (The point of overriding GetHashCode is to give you the option of value semantics.)
Left by Tom on Jul 23, 2012 9:02 PM

Your comment:
 (will show your gravatar)


Copyright © Robert Paveza | Powered by: GeeksWithBlogs.net