Почему С# скомпилированы регулярные выражения быстрее, чем эквивалентные строковые методы?

Каждый раз, когда мне приходится выполнять простые операции сдерживания или замены строк, где термин, который я ищу, является фиксированным значением, я считаю, что если я возьму свой пример ввода и сделаю некоторое его профилирование, используя скомпилированный регулярное выражение почти всегда всегда быстрее, чем использование эквивалентного метода из класса String.

Я пытался сравнить различные методы (hs - это "стог сена" для поиска, ndl - это "игла" для поиска, repl - это значение замены. regex всегда создается с опцией RegexOptions.Compiled):

hs.Replace( ndl, repl ) vs regex.Replace( hs, repl )
hs.Contains( ndl ) vs regex.IsMatch( hs )

Я нашел немало дискуссий, посвященных тому, какой из этих двух методов быстрее (1, 2, 3 и множество других), но эти дискуссии всегда, кажется, сосредоточены на:

Используйте строковую версию для простых операций и регулярное выражение для сложных операций (что, с точки зрения необработанной производительности, даже не кажется хорошей идеей), или
Запустите тест и сравните два (и для эквивалентных тестов версия регулярных выражений всегда работает лучше).

Я не понимаю, как это может быть так: как движок regex сравнивает любые две строки для подстрочных совпадений быстрее, чем эквивалентная строка? Это, по-видимому, справедливо для поисковых пространств, которые очень малы или очень велики, или поисковые термины, которые являются малыми или большими, или термин поиска встречается рано или поздно в пространстве поиска.

Итак, почему являются регулярными выражениями быстрее?

* На самом деле, в случае только мне удалось показать, что строковая версия быстрее, чем скомпилированное регулярное выражение при поиске пустой строки! Любой другой случай, от одиночных символов до очень длинных строк, обрабатывается быстрее скомпилированным регулярным выражением, чем эквивалентный строковый метод.

Обновление: Добавлен раздел, поясняющий, что я рассматриваю случаи, когда термин поиска известен во время компиляции. Для динамических или одноразовых операций накладные расходы на компиляцию регулярного выражения будут искажать результаты в пользу строковых методов.

Ответ 1

Я не понимаю, как это может быть так: как движок regex сравнивает любые две строки для подстрочных совпадений быстрее, чем эквивалентная строка?

Я могу думать о двух причинах:

В регулярном выражении используется некоторый интеллектуальный алгоритм, например Boyer Moore (O (M/N)), в то время как простая операция строки просто сравнивает иглу с каждая позиция в стоге сена (O (N * M)).
Они не делают то же самое. Например, можно было бы сопоставить культурно-инвариантное соответствие, в то время как другое совместимо с культурой, что может иметь разницу в производительности.

Ответ 2

В качестве команды библиотеки базового класса написал:

В [случае RegexOptions.Compiled] мы сначала выполняем работу по анализу в опкоды. Затем мы также делаем больше работы, чтобы превратить эти коды операций в фактический IL с использованием Reflection.Emit. Как вы можете себе представить, этот режим торгует увеличенное время запуска для более быстрого выполнения: на практике компиляция занимает примерно на порядок больше времени для запуска, но дает 30% более высокая производительность исполнения.

Но вы накладываете одну важную вещь: Шаблон исправлен. Имейте в виду, что это не всегда так. Вы не можете изменить его во время выполнения! Будут случаи, когда гибкость снизится более чем на 30% от производительности.

Ответ 3

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

Но из любопытства я написал небольшой тест, чтобы узнать, действительно ли то, что вы говорите, истинно в простейшем из примеров.

Здесь мой тест...

    private static Regex RegexSearch = new Regex("Audi A4", RegexOptions.Compiled);

    static void Main(string[] args)
    {            
        // warm up the JIT compiler
        FoundWithRegexIsMatch();
        FoundWithStringContains();
        FoundWithStringIndexOf();
        // done warming up

        int iterations = 100;
        var sw = new Stopwatch();

        sw.Restart();
        for (int i = 0; i < iterations; i++)
        {
            FoundWithRegexIsMatch();
        }
        sw.Stop();
        Console.WriteLine("Regex.IsMatch: " + sw.ElapsedMilliseconds + " ms");


        sw.Restart();
        for (int i = 0; i < iterations; i++)
        {
            FoundWithStringIndexOf();
        }
        sw.Stop();
        Console.WriteLine("String.IndexOf: " + sw.ElapsedMilliseconds + " ms");


        sw.Restart();
        for (int i = 0; i < iterations; i++)
        {
            FoundWithStringContains();
        }
        sw.Stop();
        Console.WriteLine("String.Contains: " + sw.ElapsedMilliseconds + " ms");
    }

    private static bool FoundWithStringContains()
    {
        return Resource2.csv.Contains("Audi A4");
    }

    private static bool FoundWithStringIndexOf()
    {
        return Resource2.csv.IndexOf("Audi A4") >= 0;
    }

    private static bool FoundWithRegexIsMatch()
    {
        return RegexSearch.IsMatch(Resource2.csv);
    }

Я тестирую файл CSV, который составляет около 1,2 МБ. И вот результаты:

Regex.IsMatch: 172 мс
String.IndexOf: 172 мс
String.Contains: 185 мс

Действительно, вы правы. Когда вы не делаете ничего необычного в регулярном выражении, регулярное выражение немного быстрее, чем операция String.Contains. Тем не менее, я обнаружил, что там крошечный бит накладных расходов в String.Contains и вызов String.IndexOf выполняется быстрее и фактически соответствует времени Regex.IsMatch для миллисекунды.

Эти идентичные тайминги являются подозрительными. Интересно, во время компиляции выяснилось, что на самом деле это не нужно переходить с помощью механизма Regex (так как в шаблоне, который я использовал выше) не существует специальных инструкций, которые используются в regex. Вместо этого он может быть упрощен, так что Regex.IsMatch делает тот же вызов FindNLSString из kernel32.dll, что и IndexOf. Это просто предположение.