Optimize switch for speed

[_eddie]

Is there a good way to code a switch/case-type construct for maximal
speed? The goal is to parse text key/value pairs.

IOW:
// key = "Text of some kind" // value = "Value Text"

string target1;
string target2;

switch (key) {
case "Text of some kind":
target1 = value;
break;
case "Text of some other kind":
target2 = value;
break;
// etc.

The list of possible cases is long, and I would like to avoid a linear
search through all possible cases. I can't just use a hash table
cause each case statement refers to a different target loc for storing
the 'value' part.

Any ideas?

[Jon Skeet [C# MVP]]

_eddie <_fakeemail@_no spam_.com> wrote:

Is there a good way to code a switch/case-type construct for maximal
speed? The goal is to parse text key/value pairs.

IOW:
// key = "Text of some kind" // value = "Value Text"

string target1;
string target2;

switch (key) {
case "Text of some kind":
target1 = value;
break;
case "Text of some other kind":
target2 = value;
break;
// etc.

The list of possible cases is long, and I would like to avoid a linear
search through all possible cases. I can't just use a hash table
cause each case statement refers to a different target loc for storing
the 'value' part.

It basically *is* going to be a linear search, but it won't need to
actually check every character in the text, as switches on strings make
cunning use of interning.

--
Jon Skeet - <sk***@pobox.co m>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

[_eddie]

On Fri, 23 Jan 2004 19:51:08 -0000, Jon Skeet [C# MVP]
<sk***@pobox.co m> wrote:

_eddie <_fakeemail@_no spam_.com> wrote:

// key = "Text of some kind" // value = "Value Text"

string target1;
string target2;

switch (key) {
case "Text of some kind":
target1 = value;
break;
case "Text of some other kind":
target2 = value;
break;
// etc.

It basically *is* going to be a linear search, but it won't need to
actually check every character in the text, as switches on strings make
cunning use of interning.

So it is already optimized about as much as it can be, or does the
order of the case statements have some bearing?

I was also considering reducing the number of case statements and just
not parsing some less valuable data, but if the cases are already
effectively hashed, then that wouldn't help much.

e

PS: Where did you find out about 'interning'?

[Jon Skeet [C# MVP]]

_eddie <_fakeemail@_no spam_.com> wrote:

It basically *is* going to be a linear search, but it won't need to
actually check every character in the text, as switches on strings make
cunning use of interning.
So it is already optimized about as much as it can be, or does the
order of the case statements have some bearing?

I very much doubt that it matters much, but if you *really* think it's
having a bearing on performance, you could always try different things
and measure the results.
I was also considering reducing the number of case statements and just
not parsing some less valuable data, but if the cases are already
effectively hashed, then that wouldn't help much.
Indeed.

How often are you actually executing this switch? Are you doing
*anything* significant within the cases themselves? I would be very
surprised if you found that the actual bottleneck in your application
is the switch.
PS: Where did you find out about 'interning'?

The C# language specification, the CLR specification, general
digging...

--
Jon Skeet - <sk***@pobox.co m>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

[Eric Gunnerson [MS]]

If you have enough entries, the compiler will switch over to a hashtable
rather than a linear search. IIRC, that switch occurs when the number of
cases is in the teens (16 comes to mind, but don't quote me on that).

You can tell by writing a big string switch and looking at the generated
code.

--
Eric Gunnerson

Visit the C# product team at http://www.csharp.net
Eric's blog is at http://weblogs.asp.net/ericgu/

This posting is provided "AS IS" with no warranties, and confers no rights.
"_eddie" <_fakeemail@_no spam_.com> wrote in message
news:th******** *************** *********@4ax.c om...

Is there a good way to code a switch/case-type construct for maximal
speed? The goal is to parse text key/value pairs.

IOW:
// key = "Text of some kind" // value = "Value Text"

string target1;
string target2;

switch (key) {
case "Text of some kind":
target1 = value;
break;
case "Text of some other kind":
target2 = value;
break;
// etc.

The list of possible cases is long, and I would like to avoid a linear
search through all possible cases. I can't just use a hash table
cause each case statement refers to a different target loc for storing
the 'value' part.

Any ideas?

[_eddie]

On Fri, 23 Jan 2004 22:43:40 -0000, Jon Skeet [C# MVP]
<sk***@pobox.co m> wrote:

_eddie <_fakeemail@_no spam_.com> wrote:

>It basically *is* going to be a linear search, but it won't need to
>actually check every character in the text, as switches on strings make
>cunning use of interning.
So it is already optimized about as much as it can be, or does the
order of the case statements have some bearing?

I very much doubt that it matters much, but if you *really* think it's
having a bearing on performance, you could always try different things
and measure the results.

Unfortunately, I can't think of anything else to try. <g> The target
locations change, so I can't just save refs to the target locs as
values in a hash table. The incoming data is text, so it would take
time to generate hash codes anyway.
How often are you actually executing this switch? Are you doing
*anything* significant within the cases themselves? I would be very
surprised if you found that the actual bottleneck in your application
is the switch.

That's pretty much all that the program is doing. It spins in a loop,
parsing incoming text with the switch, and storing the corresponding
values in various locations. The only thing I can eliminate is a few
of the case statements.

It seems slow--about 1-1/2 minutes to process a 125 meg text file, but
maybe that's all she'll do!

PS: Where did you find out about 'interning'?

The C# language specification, the CLR specification, general
digging...

Good insight into the switch function. Thanks.

[Jon Skeet [C# MVP]]

_eddie <_fakeemail@_no spam_.com> wrote:

How often are you actually executing this switch? Are you doing
*anything* significant within the cases themselves? I would be very
surprised if you found that the actual bottleneck in your application
is the switch.

That's pretty much all that the program is doing. It spins in a loop,
parsing incoming text with the switch, and storing the corresponding
values in various locations. The only thing I can eliminate is a few
of the case statements.

It seems slow--about 1-1/2 minutes to process a 125 meg text file, but
maybe that's all she'll do!

How complicated is your code? Could you post it? You may be doing
something else to cause the bottleneck. How fast it is at *just*
reading the file?

--
Jon Skeet - <sk***@pobox.co m>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

[Austin Ehlers]

On Fri, 23 Jan 2004 15:39:55 -0800, "Eric Gunnerson [MS]"
<er****@online. microsoft.com> wrote:

If you have enough entries, the compiler will switch over to a hashtable
rather than a linear search. IIRC, that switch occurs when the number of
cases is in the teens (16 comes to mind, but don't quote me on that).

You can tell by writing a big string switch and looking at the generated
code.

I did a test, and at 10 strings, it switches over to a hashtable.

Austin

[_eddie]

On Sat, 24 Jan 2004 00:12:08 -0000, Jon Skeet [C# MVP]
<sk***@pobox.co m> wrote:

_eddie <_fakeemail@_no spam_.com> wrote:

>How often are you actually executing this switch? Are you doing
>*anything* significant within the cases themselves? I would be very
>surprised if you found that the actual bottleneck in your application
>is the switch.

That's pretty much all that the program is doing. It spins in a loop,
parsing incoming text with the switch, and storing the corresponding
values in various locations. The only thing I can eliminate is a few
of the case statements.

It seems slow--about 1-1/2 minutes to process a 125 meg text file, but
maybe that's all she'll do!

How complicated is your code? Could you post it? You may be doing
something else to cause the bottleneck. How fast it is at *just*
reading the file?

This part of the code is relatively simple, but there are a lot of
case statements. Unfortunately, I can't post it, but I have tried
some tests, with inconsistent results. In general, NOT running the
switch cuts the run time in half.

From other replies, it looks like the switch is already hashed, so
I'll live with the current speed. I thought maybe there was a better
method for this type of thing, but apparently this is it.

I was also trying to avoid stalling the UI, so I'll have to create a
thread for that task (and I suppose have to marshal the data back to
the UI thread).

Thanks for your help, Jon.