More efficient way to determine if a string starts with a token from a set of tokens?

Question

I'm currently doing something like this in some code I'm working on right now:

public CommandType GetCommandTypeFromCommandString(String command)
{
   if(command.StartsWith(CommandConstants.Acknowledge))
      return CommandType.Acknowledge;
   else if (command.StartsWith(CommandConstants.Status))
      return CommandType.Status;
   else if (command.StartsWith(CommandConstants.Echo))
      return CommandType.Echo;
   else if (command.StartsWith(CommandConstants.Warning))
     return CommandType.Warning;
     // and so on

   return CommandType.None;
}

I'd like to know if there is a more efficient way of doing this in C#. This code needs to execute many, many times a second, and I'm not too happy with the time it takes to do all of those string comparisons. Any suggestions? :)

Answer 1

One optimization would be to use the StringComparison enum to specify that you only want ordinal comparison. Like this:

if(command.StartsWith(CommandConstants.Acknowledge, StringComparison.Ordinal))
    return CommandType.Acknowledge;

If you don't specify a string comparison method the current culture will be used for comparison and that slows things down a bit.

I did some (really really naive) benchmarking:

var a = "foo bar foo";
var b = "foo";

int numTimes = 1000000;

Benchmark.Time(() => a.StartsWith(b, StringComparison.Ordinal), "ordinal", numTimes);
Benchmark.Time(() => a.StartsWith(b), "culture sensitive", numTimes);

Which produced the following results:

ordinal ran 1000000 times in 35.6033 ms
culture sensitive ran 1000000 times in 175.5859 ms

You should also order your comparisons so that the most likely tokens are being compared first (happy path).

Theese optimizations are a simple way of making your current implementation perform better but if performance really is critical (and I mean really critical) you should be looking towards implementing some sort of state machine.

Answer 2

Similar in concept to the FSM answer by Vojislav, you could try putting the constants into a trie. You can then replace your sequence of comparisons with a single traversal of the trie.

There is a C# trie implementation described here.