CSharp/C# >> Speed of switch/case vs hash table for parsing XML

by _DS » Sat, 11 Feb 2006 08:34:11 GMT

I'm currently using a switch with about 50 case statements in a
stretch of code that's parsing XML attributes. Each case is a string.
I'm told that switch statements will actually use hash tables when
number of cases is around 10 or more, so I haven't changed the code.
Just wondering if anyone knows about how that's structured internally.
It does seem a bit slow.


CSharp/C# >> Speed of switch/case vs hash table for parsing XML

by Jon Skeet [C# MVP] » Sat, 11 Feb 2006 08:44:42 GMT



What exactly do you mean by the last sentence? Do you mean you've
implemented some code and it's working slowly, or that it sounds like a
slow way of doing things?

I suspect if you're really seeing something working slowly, it won't be
due to the switch statement. I very much doubt that that will be the
bottleneck.

--
Jon Skeet - < XXXX@XXXXX.COM >
http://www.pobox.com/ ~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

CSharp/C# >> Speed of switch/case vs hash table for parsing XML

by Brian Gideon » Sat, 11 Feb 2006 09:48:47 GMT

I'm almost certain that the C# compiler will not implement the select
construct with a Hashtable. You can easily check by running ildasm on
the assembly. Either way 50 case statements is an awful lot. If
nothing else I recommend refactoring the code to gain readability.

Brian

CSharp/C# >> Speed of switch/case vs hash table for parsing XML

by Jon Skeet [C# MVP] » Sat, 11 Feb 2006 10:02:58 GMT


It's easy to verify that at least in the case of strings, the C#
compiler does indeed use a hash table. Compile the following and then
disassemble it:

class Test
{
static void Main (string[] args)
{
int i=0;
switch (args[0])
{
case "1":
case "2":
case "3":
case "4":
case "5":
i=1;
break;
case "6":
case "7":
case "8":
case "9":
case "10":
i=2;
break;
}
i++;
}
}

--
Jon Skeet - < XXXX@XXXXX.COM >
http://www.pobox.com/ ~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

CSharp/C# >> Speed of switch/case vs hash table for parsing XML

by Brian Gideon » Sat, 11 Feb 2006 23:11:09 GMT

Jon,

That's actually pretty cool. I suppose if it does it for strings it
would do it for others as well. I never would have thought...

Brian

CSharp/C# >> Speed of switch/case vs hash table for parsing XML

by Jon Skeet [C# MVP] » Sun, 12 Feb 2006 15:39:45 GMT


It doesn't actually need to do it for other types. The thing is that
the IL switch instruction only supports integral types, so the C#
compiler needs to "fake it" for string.

--
Jon Skeet - < XXXX@XXXXX.COM >
http://www.pobox.com/ ~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

Similar Threads

1. XML parse - hash of hashes

2. switch vs Select Case - CSharp / C#

3. Unexpected result speed-testing switch vs if-else

Hi All,

I have been doing a quick performance test comparing the speed of execution 
of a switch statement against an if-else-if ladder of statements.  This was 
to confirm to myself that the switch statement would perform better when 
testing a discrete set of values.

However, I got an unexpected result finding that the switch statement was 
actually an order of magnitude _slower_ than if-else-if.  This was not 
expected but was recreatable on my two machines.

The test I used was to execute the two statements passing a variety of 
values to be matched using a long for loop.  On my Athlon64 3200 I used 
1,000,000,000 iterations.

I wondered if anybody else had come to the same conclusion?

-------------------------------------------------
The code for the if-else-if ladder was as follows:


Stopwatch timer = new Stopwatch();
long l;
timer.Start(); // Start the timer

for (long i = 1; i <= 10000000; i++)
{
    long compare = i % 20;
    if (compare == 0)
        l = 0;
    else if (compare == 1)
        l = 1;
    else if (compare == 2)
        l = 2;
    else if (compare == 3)
        l = 3;
    else if (compare == 4)
        l = 4;
    else if (compare == 5)
        l = 5;
    else if (compare == 6)
        l = 6;
    else if (compare == 7)
        l = 7;
    else if (compare == 8)
        l = 8;
    else if (compare == 9)
        l = 9;
    else if (compare == 10)
        l = 10;
    else if (compare == 11)
        l = 11;
    else if (compare == 12)
        l = 12;
    else if (compare == 13)
        l = 13;
    else if (compare == 14)
        l = 14;
    else if (compare == 15)
        l = 15;
    else if (compare == 16)
        l = 16;
    else if (compare == 17)
        l = 17;
    else if (compare == 18)
        l = 18;
    else
        l = 19;
}
timer.Stop(); // Stop the timer
decimal micro = (decimal)timer.Elapsed.Ticks / 10M;
Console.WriteLine("Execution time was {0:F1} microseconds.", micro);



-------------------------------------------------
The code for the switch statement was as follows:

Stopwatch timer = new Stopwatch();
long l;
timer.Start(); // Start the timer

for (long i = 1; i <= 10000000; i++)
{
    long compare = i % 20;
    switch (compare)
    {
        case 0:
            l = 0;
            break;
        case 1:
            l = 1;
            break;
        case 2:
            l = 2;
            break;
        case 3:
            l = 3;
            break;
        case 4:
            l = 4;
            break;
        case 5:
            l = 5;
            break;
        case 6:
            l = 6;
            break;
        case 7:
            l = 7;
            break;
        case 8:
            l = 8;
            break;
        case 9:
            l = 9;
            break;
        case 10:
            l = 10;
            break;
        case 11:
            l = 11;
            break;
        case 12:
            l = 12;
            break;
        case 13:
            l = 13;
            break;
        case 14:
            l = 14;
            break;
        case 15:
            l = 15;
            break;
        case 16:
            l = 16;
            break;
        case 17:
            l = 17;
            break;
        case 18:
            l = 18;
            break;
        default:
            l = 19;
            break;
        }
    }
timer.Stop(); // Stop the timer
decimal micro = (decimal)timer.Elapsed.Ticks / 10M;
Console.WriteLine("Execution time was {0:F1} microseconds.", micro);

-- 

BlackWasp
www.blackwasp.co.uk 


4. switch vs Select Case - CSharp/C#

5. C# switch vs. VB Select Case

I am a convert from VB to C# so bear with me on this "conversion" question

C# switch statement seems to be the closest relative to VB's Select Case.  I used VB's Select Case statement liberally.  Now I find myself wanting to use "Select Case" i.e., "switch" in C# regularly, but I always have to find another way b/c C#'s switch statement only allows static or integral variables.  For example, I often want to use a switch statement based on the value that is returned in a database field, but you can't do this - you get the 'ol C# error "A value of integral type expected

I am sure I am missing something here, but I just can't seem to find an easy, consistent "workaround" in C# for the way in am comfortable programming in VB.  I am sure this is something I am doing wrong in my "structure" and I guess my real question is what is the most efficient, and fast method in C# of testing for mutliple various results of a dynamic variable (like the value of a database field)?

6. switch vs Select Case

7. Comment on how to uniquely track your objects in C# / hash table / get hash code

raylopez99 wrote:
> A quick sanity check, and I think I am correct, but just to make
> sure:  if you have a bunch of objects that are very much like one
> another you can uniquely track them simply by using an ArrayList or
> Array, correct?  An example:  create the object, create an array, the
> stuff the object into the array.  Later on, assume the object is
> mutable, the object changes, but you can find it, if you have enough
> state information to uniquely identify it (which ideally is being
> stored on the object itself), delete it, etc using the state
> information for that object.  But to find the object in the array or
> array list, you must traverse the entire list, foreach, worse case,
> O(n) or something like that in big oh notation, right?
> 
> Now this method is foolproof but slow, no?  Especially if you're going
> to be sorting and doing lots of finding. So for this reason, we use
> hash tables to speed up searching and sorting of objects, and to
> "find" or "contains" objects, yes?

Yes.

> But, as pointed out in the links below, hash functions can be non-
> unique, or give collisions with two different objects having the same
> hash (rare, but happens), and further you have to write your own
> gethascode, such as if you overload the Equals implementation in a
> ArrayList for example.
> 
> I've seen examples on overriding GetHashCode and understand how it
> works (kind of, at least it made sense), but my question /comment is
> that if you're not concerned with performance, then a simple index
> based retrieval scheme is best.
> 
> Correct me if I'm wrong.

If you had to write your own Hashtable or Dictionary<> class, then
there would be a point.

But writing a GetHashCode method is not that difficult, so in case
you nee dto lookup by something, then I will recommend Dictionary<>
anyway.

Arne

8. Comment on how to uniquely track your objects in C# / hash table / get hash code - CSharp/C#