How can C#'s string.IndexOf perform so fast, 10 times faster than ordinary for loop find?

Question

I have a very long string (60MB in size) in which I need to find how many pairs of '<' and '>' are in there.

---

I have first tried my own way:

        char pre = '!';
        int match1 = 0;
        for (int j = 0; j < html.Length; j++)
        {
            char c = html[j];
            if (pre == '<' && c == '>') //find a match
            {
                pre = '!';
                match1++;
            }
            else if (pre == '!' && c == '<')
                pre = '<';
        }

The above code runs on my string for roughly 1000 ms.

---

Then I tried using string.IndexOf

        int match2 = 0;
        int index = -1;
        do
        {
            index = html.IndexOf('<', index + 1);
            if (index != -1) // find a match
            {
                index = html.IndexOf('>', index + 1);
                if (index != -1)
                   match2++;
            }
        } while (index != -1);

The above code runs for only around 150 ms.

---

I am wondering what is the magic that makes string.IndexOf runs so fast?

Anyone can inspire me?

---

Edit

Ok, according to @BrokenGlass's answer. I modified my code in the way that they don't check the pairing, instead, they check how many '<' in the string.

---

        for (int j = 0; j < html.Length; j++)
        {
            char c = html[j];
            if (c == '>')
            {
                match1++;
            }
        }

the above code runs for around 760 ms.

---

Using IndexOf

        int index = -1;
        do
        {
            index = html.IndexOf('<', index + 1);
            if (index != -1)
            {
                match2++;
            }
        } while (index != -1);

The above code runs for about 132 ms. still very very fast.

---

Edit 2

After read @Jeffrey Sax comment, I realised that I was running in VS with Debug mode.

Then I built and ran in release mode, ok, IndexOf is still faster, but not that faster any more.

Here is the results:

For the pairing count: 207ms VS 144ms

For the normal one char count: 141ms VS 111ms.

My own codes' performance was really improved.

---

Lesson learned: when you do the benchmark stuff, do it in release mode!

Intrastate

Did you enable optimizations while testing? – Leavitt

Have you taken a look at what string.IndexOf is doing behind the scenes? – Gametocyte

@MartinLiversage How to enable optimizations? – Intrastate

@Gametocyte No, that's what I am asking actually – Intrastate

@MartinLiversage Yes, I checked and it is enabled always – Intrastate

Try implementing your own version of the IndexOf function that behaves the same way as the string.IndexOf, then the comparison will be more "fair" and it will be possible to argue if IndexOf does "something magical". – Cripple

Try not to use html.length, try int len =html.length; and then use len in the for loop. – Polliwog

@HaLaBi string.Length is static, only changes or sum when string is modified. It is not a on-fly counting. – Intrastate

@Jack: Now you search through the full string in your implementation while you stop the search once you have found a < > pair in the IndexOf version. – Grim

@Intrastate good investigation, and yes, release mode makes a massive difference to performance! Mainly due to bounds checking, code optimization and dropping of debug tracing – Genteel

Answer 1

Are you running your timings from within Visual Studio? If so, your code would run significantly slower for that reason alone.

Aside from that, you are, to some degree, comparing apples and oranges. The two algorithms work in a different way.

The IndexOf version alternates between looking for an opening bracket only and a closing bracket only. Your code goes through the whole string and keeps a status flag that indicates whether it is looking for an opening or a closing bracket. This takes more work and is expected to be slower.

Here's some code that does the comparison the same way as your IndexOf method.

int match3 = 0;
for (int j = 0; j < html.Length; j++) {
    if (html[j] == '<') {
        for (; j < html.Length; j++)
            if (html[j] == '>')
                match3++;
    }
}

In my tests this is actually about 3 times faster than the IndexOf method. The reason? Strings are actually not quite as simple as sequences of individual characters. There are markers, accents, etc. String.IndexOf handles all that extra complexity properly, but it comes at a cost.

Leolaleoline

credit goes to you because you mentioned Are you running your timings from within Visual Studio? – Intrastate

Answer 2

The only thing that comes to my mind is actual implementation of IndexOf iniside string class, that call

callvirt    System.String.IndexOf

which, if we use a power of reflector (as much as it possible) ends up into the

CompareInfo.IndexOf(..)

call, which instead use super fast windows native function FindNLSString:

Furuncle

Answer 3

It's a bit of a fallacy to directly compare your managed implementation and the String.IndexOf method. The implementation of IndexOf is largely native code and hence has a different set of performance characteristics than your managed implementation. In particular native code avoid the type safety checks, and their corresponding overhead, which injected by the CLR in the managed algorithm.

One example is the use of the array index

char c = html[j];

In managed code this statement will both verify that j is a valid index into the array html and then return the value. The native code equivalent simply returns a memory offset with no additional checking necessary. This lack of a check gives native code an inherent advantage here because it can avoid an additional branch instruction on every iteration of the loop.

Note that this advantage is not absolute. The JIT could very well examine this loop and decide that j could never be an invalid index and elide the checks in the generated native code (and it does do this in some cases IIRC).

Barnet

Answer 4

I would expect string.IndexOf compared to your first code sample to run at least twice as fast (besides any other optimizations that might be done there) since you check for both start and end character in each of your iterations. Your implementation with string.IndexOf on the other hand will check for the end character only after it has successfully found a start character. This cuts the number of operations on each iteration down significantly (one less comparison).

Grim

Actually the IndexOf also check twice. – Intrastate

@Jack: No it doesn't: you pass the index of the found start character < to string.IndexOf - so you are looking for the first occurrence of the end character only after that index within your input string – Grim

You mean if I find < is at 10, then my searching for > will start from 10, right? I think it is the same in my first implementation, which is also running for one go. – Intrastate

Ok, I know what you mean. you mean the if parts. I will modify my code and run again now. – Intrastate

for your last paragraph, I don't think IndexOf can quit earlier, as the last string in the whole string is </html>, i.e., IndexOf still need to finish scanning all the chars – Intrastate

@Jack: you are correct, didn't take your outer while loop into account – Grim

Please have a look at my edit. Now I even don't scan for pairs. Just to count how many < in the string. – Intrastate

Answer 5

Using a switch statement instead of an if test speeds things up a little also. This code occasionally beats the indexof code on my machine.

        int count = 0;
        bool open = false;
        for (int j = 0; j < testStr.Length; j++)
        {  
            switch (testStr[j])
            {
                case '<':
                    open = true;
                    break;
                case '>':
                    if (open)
                       count++;

                    open = false;
                    break;         
            }
        }

Geopolitics

If you have a lot of comparisons building a hash table will speed things up – Quotidian