How would you make this switch statement as fast as possible?

Question

2009-12-04 UPDATE: For profiling results on a number of the suggestions posted here, see below!

---

The Question

Consider the following very harmless, very straightforward method, which uses a switch statement to return a defined enum value:

public static MarketDataExchange GetMarketDataExchange(string ActivCode) {
    if (ActivCode == null) return MarketDataExchange.NONE;

    switch (ActivCode) {
        case "": return MarketDataExchange.NBBO;
        case "A": return MarketDataExchange.AMEX;
        case "B": return MarketDataExchange.BSE;
        case "BT": return MarketDataExchange.BATS;
        case "C": return MarketDataExchange.NSE;
        case "MW": return MarketDataExchange.CHX;
        case "N": return MarketDataExchange.NYSE;
        case "PA": return MarketDataExchange.ARCA;
        case "Q": return MarketDataExchange.NASDAQ;
        case "QD": return MarketDataExchange.NASDAQ_ADF;
        case "W": return MarketDataExchange.CBOE;
        case "X": return MarketDataExchange.PHLX;
        case "Y": return MarketDataExchange.DIRECTEDGE;
    }

    return MarketDataExchange.NONE;
}

My colleague and I batted around a few ideas today about how to actually make this method faster, and we came up with some interesting modifications that did in fact improve its performance rather significantly (proportionally speaking, of course). I'd be interested to know what sorts of optimizations anyone else out there can think up that might not have occurred to us.

Right off the bat, let me just offer a quick disclaimer: this is for fun, and not to fuel the whole "to optimize or not to optimize" debate. That said, if you count yourself among those who dogmatically believe "premature optimization is the root of all evil," just be aware that I work for a high-frequency trading firm, where everything needs to run absolutely as fast as possible--bottleneck or not. So, even though I'm posting this on SO for fun, it isn't just a huge waste of time, either.

One more quick note: I'm interested in two kinds of answers--those that assume every input will be a valid ActivCode (one of the strings in the switch statement above), and those that do not. I am almost certain that making the first assumption allows for further speed improvements; anyway, it did for us. But I know that improvements are possible either way.

---

The Results

Well, it turns out that the fastest solution so far (that I've tested) came from João Angelo, whose suggestion was actually very simple, yet extremely clever. The solution that my coworker and I had devised (after trying out several approaches, many of which were thought up here as well) came in second place; I was going to post it, but it turns out that Mark Ransom came up with the exact same idea, so just check out his answer!

Since I ran these tests, some other users have posted even newer ideas... I will test them in due time, when I have a few more minutes to spare.

I ran these tests on two different machines: my personal computer at home (a dual-core Athlon with 4 Gb RAM running Windows 7 64-bit) and my development machine at work (a dual-core Athlon with 2 Gb RAM running Windows XP SP3). Obviously, the times were different; however, the relative times, meaning, how each method compared to every other method, were the same. That is to say, the fastest was the fastest on both machines, etc.

Now for the results. (The times I'm posting below are from my home computer.)

But first, for reference--the original switch statement:
1000000 runs: 98.88 ms
Average: 0.09888 microsecond

Fastest optimizations so far:

1. João Angelo's idea of assigning values to the enums based on the hash codes of the ActivCode strings and then directly casing ActivCode.GetHashCode() to MarketDataExchange:
   1000000 runs: 23.64 ms
   Average: 0.02364 microsecond
   Speed increase: 329.90%

2. My colleague's and my idea of casting ActivCode[0] to an int and retrieving the appropriate MarketDataExchange from an array initialized on startup (this exact same idea was suggested by Mark Ransom):
   1000000 runs: 28.76 ms
   Average: 0.02876 microsecond
   Speed increase: 253.13%

3. tster's idea of switching on the output of ActivCode.GetHashCode() instead of ActivCode:
   1000000 runs: 34.69 ms
   Average: 0.03469 microsecond
   Speed increase: 185.04%

4. The idea, suggested by several users including Auraseer, tster, and kyoryu, of switching on ActivCode[0] instead of ActivCode:
   1000000 runs: 36.57 ms
   Average: 0.03657 microsecond
   Speed increase: 174.66%

5. Loadmaster's idea of using the fast hash, ActivCode[0] + ActivCode[1]*0x100:
   1000000 runs: 39.53 ms
   Average: 0.03953 microsecond
   Speed increase: 153.53%

6. Using a hashtable (Dictionary<string, MarketDataExchange>), as suggested by many:
   1000000 runs: 88.32 ms
   Average: 0.08832 microsecond
   Speed increase: 12.36%

7. Using a binary search:
   1000000 runs: 1031 ms
   Average: 1.031 microseconds
   Speed increase: none (performance worsened)

Let me just say that it has been really cool to see how many different ideas people had on this simple problem. This was very interesting to me, and I'm quite thankful to everyone who has contributed and made a suggestion so far.

Answer 1

I would put it in dictionary instead of using a switch statement. That being said, it may not make a difference. Or it might. See C# switch statement limitations - why?.

Answer 2

I'd use a dictionary for the key value pairs and take advantage of the O(1) lookup time.

Answer 3

Put the cases in a sorted structure with non linear access (like a hash table). The switch that you have will have a linear time.

Answer 4

Do you have any statistics on which strings are more common? So that those could be checked first?

Answer 5

I would do nothing, since its a switch the compiler already optimizes it.

Answer 6

You can get a mild speed-up by ordering the codes according to which ones are most used.

But I agree with Cletus: the best speed-up I can think of would be to use a hash map with plenty of room (so that there are no collisions.)

Answer 7

+1 for using a dictionary. Not necessarily for optimization, but it'd be cleaner.

I would probably use constants for the strings as well, though i doubt that'd buy you anything performance wise.

Answer 8

A couple of random thoughts, that may not all be applicable together:

Switch on the first character in the string, rather than the string itself, and do a sub-switch for strings which can contain more than one letter?

A hashtable would certainly guarantee O(1) retrieval, though it might not be faster for smaller numbers of comparisons.

Don't use strings, use enums or something like a flyweight instead. Using strings in this case seems a bit fragile anyway...

And if you really need it to be as fast as possible, why aren't you writing it in assembly? :)

Answer 9

If you know how often the various codes show up, the more common ones should go at the top of the list, so fewer comparisons are done. But let's assume you don't have that.

Assuming the ActivCode is always valid will of course speed things up. You don't need to test for null or the empty string, and you can leave off one test from the end of the switch. That is, test for everything except Y, and then return DIRECTEDGE if no match is found.

Instead of switching on the whole string, switch on its first letter. For the codes that have more letters, put a second test inside the switch case. Something like this:

switch(ActivCode[0])
{
   //etc.
   case 'B':
      if ( ActivCode.Length == 1 ) return MarketDataExchange.BSE; 
      else return MarketDataExchange.BATS;
      // etc.
}

It would be better if you could go back and change the codes so they are all single characters, because you would then never need more than one test. Better yet would be using the numerical value of the enum, so you can simply cast instead of having to switch/translate in the first place.

Answer 10

Can we cast the ActivCode to int and then use int in our case statements?

Answer 11

With a valid input could use

if (ActivCode.Length == 0)
    return MarketDataExchange.NBBO;

if (ActivCode.Length == 1)
    return (MarketDataExchange) (ActivCode[0]);

return (MarketDataExchange) (ActivCode[0] | ActivCode[1] << 8);

Answer 12

Change the switch to switch on the HashCode() of the strings.

Answer 13

Messy but using a combination of nested ifs and hard coding might just beat the optimiser:-

   if (ActivCode < "N") {
         // "" to "MW"
         if (ActiveCode < "BT") {
            // "" to "B"
            if (ActiveCode < "B") {
                // "" or "A"
                if (ActiveCode < "A") {
                      // must be ""
                     retrun MarketDataExchange.NBBO;
                } else {
                     // must be "A"
                    return MarketDataExchange.AMEX;
                }
            } else {
                // must be "B"
                return MarketDataExchange.BSE;
            }
         } else {
            // "BT" to "MW"
            if (ActiveCode < "MW") {
                // "BT" or "C"
                if (ActiveCode < "C") {
                      // must be "BT"
                     retrun MarketDataExchange.NBBO;
                } else {
                     // must be "C"
                    return MarketDataExchange.NSE;
                }
            } else {
            // must be "MV"
                return MarketDataExchange.CHX;
            }
         }
    } else {
        // "N" TO "Y"
         if (ActiveCode < "QD") {
            // "N" to "Q"
            if (ActiveCode < "Q") {
                // "N" or "PA"
                if (ActiveCode < "PA") {
                      // must be "N"
                     retrun MarketDataExchange.NYSE;
                } else {
                     // must be "PA"
                    return MarketDataExchange.ARCA;
                }
            } else {
                // must be "Q"
                return MarketDataExchange.NASDAQ;
            }
         } else {
            // "QD" to "Y"
            if (ActiveCode < "X") {
                // "QD" or "W"
                if (ActiveCode < "W") {
                      // must be "QD"
                     retrun MarketDataExchange.NASDAQ_ADF;
                } else {
                     // must be "W"
                    return MarketDataExchange.CBOE;
                }
            } else {
            // "X" or "Y"
                if (ActiveCode < "Y") {
                      // must be "X"
                     retrun MarketDataExchange.PHLX;
                } else {
                     // must be "Y"
                    return MarketDataExchange.DIRECTEDGE;
                }
            }
         }
    }

This gets the right function with three or four compares. I wouldnt even think of doing this for real unless your piece of code is expected to run several times a second!

You further otimise it so that only single character compares occurred. e.g. replace '< "BT" ' with '>= "B" ' -- ever so slightly faster and even less readable!

Answer 14

1. Avoid all string comparisons.
2. Avoid looking at more than a single character (ever)
3. Avoid if-else since I want the compiler to be able optimize the best it can
4. Try to get the result in a single switch jump

code:

public static MarketDataExchange GetMarketDataExchange(string ActivCode) {
    if (ActivCode == null) return MarketDataExchange.NONE;
    int length = ActivCode.Length;
    if (length == 0) return MarketDataExchange.NBBO;

    switch (ActivCode[0]) {
        case 'A': return MarketDataExchange.AMEX;
        case 'B': return (length == 2) ? MarketDataExchange.BATS : MarketDataExchange.BSE;
        case 'C': return MarketDataExchange.NSE;
        case 'M': return MarketDataExchange.CHX;
        case 'N': return MarketDataExchange.NYSE;
        case 'P': return MarketDataExchange.ARCA;
        case 'Q': return (length == 2) ? MarketDataExchange.NASDAQ_ADF : MarketDataExchange.NASDAQ;
        case 'W': return MarketDataExchange.CBOE;
        case 'X': return MarketDataExchange.PHLX;
        case 'Y': return MarketDataExchange.DIRECTEDGE;
        default:  return MarketDataExchange.NONE;
    }
}

Answer 15

I'd extrapolate tster's reply to "switch over a custom hash function", assuming that the code generator creates a lookup table, or - failing that - building the lookup table myself.

The custom hash function should be simple, e.g.:

(int)ActivCode[0]*2 + ActivCode.Length-1

This would require a table of 51 elements, easily kept in L1 cache, under the following assumptions:

• Input data must already be validated
• empty string must be handled sepsarately
• no two-character-codes start with the same character
• adding new cases is hard

the empty string case could be incorporated if you could use an unsafe access to ActivCode[0] yielding the '\0' terminator.

Answer 16

I'd roll my own fast hash function and use an integer switch statement to avoid string comparisons:

int  h = 0;  

// Compute fast hash: A[0] + A[1]*0x100
if (ActivCode.Length > 0)
    h += (int) ActivCode[0];
if (ActivCode.Length > 1)
    h += (int) ActivCode[1] << 8;  

// Find a match
switch (h)
{
    case 0x0000:  return MarketDataExchange.NBBO;        // ""
    case 0x0041:  return MarketDataExchange.AMEX;        // "A"
    case 0x0042:  return MarketDataExchange.BSE;         // "B"
    case 0x5442:  return MarketDataExchange.BATS;        // "BT"
    case 0x0043:  return MarketDataExchange.NSE;         // "C"
    case 0x574D:  return MarketDataExchange.CHX;         // "MW"
    case 0x004E:  return MarketDataExchange.NYSE;        // "N"
    case 0x4150:  return MarketDataExchange.ARCA;        // "PA"
    case 0x0051:  return MarketDataExchange.NASDAQ;      // "Q"
    case 0x4451:  return MarketDataExchange.NASDAQ_ADF;  // "QD"
    case 0x0057:  return MarketDataExchange.CBOE;        // "W"
    case 0x0058:  return MarketDataExchange.PHLX;        // "X"
    case 0x0059:  return MarketDataExchange.DIRECTEDGE;  // "Y"
    default:      return MarketDataExchange.NONE;
}

My tests show that this is about 4.5 times faster than the original code.

If C# had a preprocessor, I'd use a macro to form the case constants.

This technique is faster than using a hash table and certainly faster than using string comparisons. It works for up to four-character strings with 32-bit ints, and up to 8 characters using 64-bit longs.

Answer 17

Assuming every input will be a valid ActivCode, that you can change the enumeration values and highly coupled to the GetHashCode implementation:

enum MarketDataExchange
{
    NONE,
    NBBO = 371857150,
    AMEX = 372029405,
    BSE = 372029408,
    BATS = -1850320644,
    NSE = 372029407,
    CHX = -284236702,
    NYSE = 372029412,
    ARCA = -734575383,
    NASDAQ = 372029421,
    NASDAQ_ADF = -1137859911,
    CBOE = 372029419,
    PHLX = 372029430,
    DIRECTEDGE = 372029429
}

public static MarketDataExchange GetMarketDataExchange(string ActivCode)
{
    if (ActivCode == null) return MarketDataExchange.NONE;

    return (MarketDataExchange)ActivCode.GetHashCode();
}

Answer 18

If the enumeration values are arbitrary you could do this...

public static MarketDataExchange GetValue(string input)
{
    switch (input.Length)
    {
        case 0: return MarketDataExchange.NBBO;
        case 1: return (MarketDataExchange)input[0];
        case 2: return (MarketDataExchange)(input[0] << 8 | input[1]);
        default: return MarketDataExchange.None;
    }
}

... if you want to go totally nuts you can also use an unsafe call with pointers as noted by Pavel Minaev ... The pure cast version above is faster than this unsafe version.

unsafe static MarketDataExchange GetValue(string input)
{
    if (input.Length == 1)
        return (MarketDataExchange)(input[0]);
    fixed (char* buffer = input)
        return (MarketDataExchange)(buffer[0] << 8 | buffer[1]);
}

---

public enum MarketDataExchange
{
    NBBO = 0x00, //
    AMEX = 0x41, //A
    BSE = 0x42, //B
    BATS = 0x4254, //BT
    NSE = 0x43, //C
    CHX = 0x4D57, //MW
    NYSE = 0x4E, //N
    ARCA = 0x5041, //PA
    NASDAQ = 0x51, //Q
    NASDAQ_ADF = 0x5144, //QD
    CBOE = 0x57, //W
    PHLX = 0x58, //X
    DIRECTEDGE = 0x59, //Y

    None = -1
}

Answer 19

All your strings are at most 2 chars long, and ASCII, so we can use 1 byte per char. Furthermore, more likely than not, they also never can have \0 appear in them (.NET string allows for embedded null characters, but many other things don't). With that assumption, we can null-pad all your strings to be exactly 2 bytes each, or an ushort:

""   -> (byte) 0 , (byte) 0   -> (ushort)0x0000
"A"  -> (byte)'A', (byte) 0   -> (ushort)0x0041
"B"  -> (byte)'B', (byte) 0   -> (ushort)0x0042
"BT" -> (byte)'B', (byte)'T'  -> (ushort)0x5442

Now that we have a single integer in a relatively (64K) short range, we can use a lookup table:

MarketDataExchange[] lookup = {
    MarketDataExchange.NBBO, 
    MarketDataExchange.NONE, 
    MarketDataExchange.NONE, 
    ...
    /* at index 0x041 */
    MarketDataExchange.AMEX,
    MarketDataExchange.BSE,
    MarketDataExchange.NSE,
    ...
};

Now, obtaining the value given a string is:

public static unsafe MarketDataExchange GetMarketDataExchange(string s)
{
   // Assume valid input
   if (s.Length == 0) return MarketDataExchange.NBBO;

   // .NET strings always have '\0' after end of data - abuse that
   // to avoid extra checks for 1-char strings. Skip index checks as well.
   ushort hash;
   fixed (char* data = s)
   {
       hash = (ushort)data[0] | ((ushort)data[1] << 8);
   }

   return lookup[hash];
}

Answer 20

Forgive me if I get something wrong here, I'm extrapolating from my knowledge of C++. For example, if you take ActivCode[0] of an empty string, in C++ you get a character whose value is zero.

Create a two dimensional array which you initialize once; the first dimension is the length of the code, the second is a character value. Populate with the enumeration value you'd like to return. Now your entire function becomes:

public static MarketDataExchange GetMarketDataExchange(string ActivCode) {
    return LookupTable[ActivCode.Length][ActivCode[0]];
}

Lucky for you all the two-character codes are unique in the first letter compared to the other two-character codes.

Answer 21

Trade memory for speed by pre-populating an index table to leverage simple pointer arithmetic.

public class Service 
{
    public static MarketDataExchange GetMarketDataExchange(string ActivCode) {
    {
        int x = 65, y = 65;
        switch(ActivCode.Length)
        {
            case 1:
                x = ActivCode[0];
                break;
            case 2:
                x = ActivCode[0];
                y = ActivCode[1];
                break;
        }
        return _table[x, y];
    }

    static Service()
    {
        InitTable();
    }

    public static MarketDataExchange[,] _table = 
        new MarketDataExchange['Z','Z'];

    public static void InitTable()
    {
        for (int x = 0; x < 'Z'; x++)
            for (int y = 0; y < 'Z'; y++)
                _table[x, y] = MarketDataExchange.NONE;

        SetCell("", MarketDataExchange.NBBO);
        SetCell("A", MarketDataExchange.AMEX);
        SetCell("B", MarketDataExchange.BSE);
        SetCell("BT", MarketDataExchange.BATS);
        SetCell("C", MarketDataExchange.NSE);
        SetCell("MW", MarketDataExchange.CHX);
        SetCell("N", MarketDataExchange.NYSE);
        SetCell("PA", MarketDataExchange.ARCA);
        SetCell("Q", MarketDataExchange.NASDAQ);
        SetCell("QD", MarketDataExchange.NASDAQ_ADF);
        SetCell("W", MarketDataExchange.CBOE);
        SetCell("X", MarketDataExchange.PHLX);
        SetCell("Y", MarketDataExchange.DIRECTEDGE);
    }

    private static void SetCell(string s, MarketDataExchange exchange)
    {
        char x = 'A', y = 'A';
        switch(s.Length)
        {
            case 1:
                x = s[0];
                break;
            case 2:
                x = s[0];
                y = s[1];
                break;
        }
        _table[x, y] = exchange;
    }
}

Make the enum byte-based to save a little space.

public enum MarketDataExchange : byte
{
    NBBO, AMEX, BSE, BATS, NSE, CHX, NYSE, ARCA, 
    NASDAQ, NASDAQ_ADF, CBOE, PHLIX, DIRECTEDGE, NONE
}