Как С# string.IndexOf выполняется так быстро, в 10 раз быстрее, чем обычная для поиска петли?

У меня очень длинная строка (60 МБ), в которой мне нужно найти, сколько пар '<' и ' > ' находятся там.

Я сначала попытался по-своему:

        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 = '<';
        }

Приведенный выше код работает на моей строке примерно на 1000 мс.

Затем я попытался использовать 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);

Вышеприведенный код работает только около 150 мс.

Мне интересно, что такое магия, которая заставляет string.IndexOf запускать так быстро?

Кто-нибудь может вдохновить меня?

Edit

Хорошо, в соответствии с ответом @BrokenGlass. Я изменил свой код так, чтобы они не проверяли сопряжение, вместо этого они проверяют, сколько '<' в строке.

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

приведенный выше код работает примерно 760 мс.

Используя IndexOf

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

Приведенный выше код работает примерно 132 мс. все еще очень быстро.

Изменить 2

После прочтения комментария @Jeffrey Sax, я понял, что я работал в VS с режимом Debug.

Затем я построил и запустил в режиме выпуска, ok, IndexOf все еще быстрее, но не так быстрее.

Вот результаты:

Для количества спаривания: 207ms VS 144ms

Для обычного char count: 141ms VS 111ms.

Эффективность моих собственных кодов была действительно улучшена.

Извлеченный урок: когда вы делаете тест, делайте это в режиме выпуска!

Ответ 1

Выполняете ли вы время в Visual Studio? Если это так, ваш код будет работать значительно медленнее по этой причине.

Помимо этого, вы в какой-то мере сравниваете яблоки и апельсины. Эти два алгоритма работают по-другому.

Версия IndexOf чередуется между поиском только открывающей скобы и только закрывающей скобой. Ваш код проходит через всю строку и сохраняет флаг состояния, который указывает, ищет ли он открытие или закрытие. Это требует больше работы и, как ожидается, будет медленнее.

Вот код, который выполняет сравнение так же, как ваш метод IndexOf.

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

В моих тестах это на самом деле примерно в 3 раза быстрее, чем метод IndexOf. Причина? Строки на самом деле не так просты, как последовательности отдельных символов. Есть маркеры, акценты и т.д. String.IndexOf правильно справляется со всей этой сложной сложностью, но это связано с затратами.

Ответ 2

Единственное, что приходит мне в голову, это фактическая реализация класса string IndexOf, вызывающего

callvirt    System.String.IndexOf

который, если мы используем мощность отражателя (насколько это возможно), попадает в

CompareInfo.IndexOf(..)

который вместо этого использует супер быструю встроенную функцию windows FindNLSString:

Ответ 3

Это немного ошибочно, чтобы напрямую сравнить управляемую реализацию и метод String.IndexOf. Реализация IndexOf в основном является внутренним кодом и, следовательно, имеет другой набор характеристик производительности, чем ваша управляемая реализация. В частности, собственный код избегает проверок безопасности типа и их соответствующих накладных расходов, которые вводятся CLR в управляемом алгоритме.

Одним из примеров является использование индекса массива

char c = html[j];

В управляемом коде этот оператор будет проверять, что j является допустимым индексом в массиве html, а затем возвращает значение. Собственный эквивалент кода просто возвращает смещение памяти без дополнительной проверки. Этот недостаток проверки дает встроенный код, присущее этому преимуществу, потому что он может избежать дополнительной команды перехода на каждой итерации цикла.

Обратите внимание, что это преимущество не является абсолютным. JIT может очень хорошо изучить этот цикл и решить, что j никогда не может быть недопустимым индексом и исключать проверки в сгенерированном собственном коде (и это делает это в некоторых случаях IIRC).

Ответ 4

Я бы ожидал, что string.IndexOf по сравнению с вашим первым образцом кода будет работать как минимум в два раза быстрее (помимо любых других оптимизаций, которые могут быть выполнены там), поскольку вы проверяете как начальный, так и конечный символ в каждой из ваших итераций. С другой стороны, ваша реализация с помощью string.IndexOf будет проверять конечный символ только после того, как он успешно нашел начальный символ. Это значительно сокращает количество операций на каждой итерации (меньшее сравнение).

Ответ 5

Использование оператора switch вместо теста if ускоряет работу. Этот код иногда превосходит индекс кода на моей машине.

        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;         
            }
        }