2021-04-24 04:30:00 UTC

Введение

Изначально я не ставил своей целью исследовать работу строковых методов в .NET. Мне просто хотелось лучше разобраться с BenchmarkDotNet.

Исследование, я решил провести сравнивая работу наивного метода поиска нескольких подстрок в строке, с аналогичным, реализующим алгоритм Ахо-Корасик.

Процесс

Был написан следующий бенчмарк:

using System;
using System.Collections.Generic;
using System.Text;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Engines;
using project.library;

namespace bench
{
    [SimpleJob(
        RunStrategy.ColdStart,
        launchCount: 3,
        warmupCount: 2,
        targetCount: 5,
        invocationCount: 30000,
        "FindAll")]
    [RPlotExporter]
    public class KeywordsSearchBenchmark
    {
        private const string TestString =
            "Mozilla/5.0 (Windows NT 6.1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/41.0.2228.0 Safari/537.36";

        private string[] keywords;
        private AhoCorasickTree tree;

        [GlobalSetup]
        public void GlobalSetup()
        {
            this.keywords = new[] {"Safari", "Gecko", "Chrome"};
            this.tree = new AhoCorasickTree(this.keywords, StringComparer.CurrentCulture);
        }

        [Benchmark]
        [ArgumentsSource(nameof(Inputs))]
        public void AhoCorasick(string input)
        {
            this.tree.FindAll(input).Consume(new Consumer());
        }

        [Benchmark(Baseline = true)]
        [ArgumentsSource(nameof(Inputs))]
        public void Naive(string input)
        {
            FindAll(input, this.keywords).Consume(new Consumer());
        }
        
        public IEnumerable<object[]> Inputs()
        {
            yield return new object[] { CreateString(20) };
        }

        private static IEnumerable<string> FindAll(string str, string[] keywords)
        {
            for (var i = 0; i < keywords.Length; i++)
            {
                for (int index = 0;; index += keywords[i].Length)
                {
                    index = str.IndexOf(keywords[i], index, StringComparison.CurrentCulture);
                    if (index == -1)
                    {
                        break;
                    }

                    yield return keywords[i];
                }
            }
        }

        private static string CreateString(int repeatsCount)
        {
            var sb = new StringBuilder(repeatsCount * TestString.Length);
            for (var i = 0; i < repeatsCount; i++)
            {
                sb.Append(TestString);
            }

            return sb.ToString();
        }
    }
}

Код реализации алгоритма Ахо-Корасик я тут не привожу ибо это не особенно важно. Особо интересующиеся смотрите у меня на гитхабе.

Запустив этот бенчмарк на маке я увидел ожидаемый результат:

BenchmarkDotNet=v0.12.1, OS=macOS 11.2.3 (20D91) [Darwin 20.3.0]
Intel Core i5-1030NG7 CPU 1.10GHz, 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.101
  [Host]  : .NET Core 5.0.1 (CoreCLR 5.0.120.57516, CoreFX 5.0.120.57516), X64 RyuJIT
  FindAll : .NET Core 5.0.1 (CoreCLR 5.0.120.57516, CoreFX 5.0.120.57516), X64 RyuJIT

Job=FindAll  InvocationCount=30000  IterationCount=5  
LaunchCount=3  RunStrategy=ColdStart  WarmupCount=2  

Method	input	Mean	Error	StdDev	Ratio	RatioSD
AhoCorasick	Mozi(…)7.36 [2000]	25.39 μs	1.823 μs	1.705 μs	1.67	0.09
Naive	Mozi(…)7.36 [2000]	15.20 μs	0.610 μs	0.571 μs	1.00	0.00

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

Далее, просто для сравнения, запускаю ровно этот же код на компьютере под Windows:

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19042
Intel Core i9-9900K CPU 3.60GHz (Coffee Lake), 1 CPU, 16 logical and 8 physical cores
.NET Core SDK=5.0.202
  [Host]  : .NET Core 5.0.5 (CoreCLR 5.0.521.16609, CoreFX 5.0.521.16609), X64 RyuJIT
  FindAll : .NET Core 5.0.5 (CoreCLR 5.0.521.16609, CoreFX 5.0.521.16609), X64 RyuJIT

Job=FindAll  InvocationCount=30000  IterationCount=5  
LaunchCount=3  RunStrategy=ColdStart  WarmupCount=2  

Method	input	Mean	Error	StdDev	Ratio
AhoCorasick	Mozi(…)7.36 [2000]	18.19 μs	0.691 μs	0.647 μs	0.04
Naive	Mozi(…)7.36 [2000]	470.17 μs	6.156 μs	5.758 μs	1.00

Хмм … версия в лоб медленнее в 20 раз Карл!

Начинаем разбираться

И разбираться мы будем с наивным методом, а точнее со строковым методом IndexOf.

Благо теперь исходники .NET открыты, поэтому идем в репозиторий dotnet/runtime и ищем реализацию нужного нам метода. Интересующая нас реализация находится в файле String.Searching.cs

Интересующая нас реализация (на момент написания этого текста) начинается со строчки 333 и выглядит так:

        public int IndexOf(string value, int startIndex, int count, StringComparison comparisonType)
        {
            // Parameter checking will be done by CompareInfo.IndexOf.

            switch (comparisonType)
            {
                case StringComparison.CurrentCulture:
                case StringComparison.CurrentCultureIgnoreCase:
                    return CultureInfo.CurrentCulture.CompareInfo.IndexOf(this, value, startIndex, count, GetCaseCompareOfComparisonCulture(comparisonType));

                case StringComparison.InvariantCulture:
                case StringComparison.InvariantCultureIgnoreCase:
                    return CompareInfo.Invariant.IndexOf(this, value, startIndex, count, GetCaseCompareOfComparisonCulture(comparisonType));

                case StringComparison.Ordinal:
                case StringComparison.OrdinalIgnoreCase:
                    return Ordinal.IndexOf(this, value, startIndex, count, comparisonType == StringComparison.OrdinalIgnoreCase);

                default:
                    throw (value is null)
                        ? new ArgumentNullException(nameof(value))
                        : new ArgumentException(SR.NotSupported_StringComparison, nameof(comparisonType));
            }
        }

Поскольку у нас сравнение учитывает текущую культуру, нам надо искать как реализована CultureInfo.CurrentCulture.CompareInfo.IndexOf. Для начала, нам надо найти класс CultureInfo.CurrentCulture.CompareInfo — и тут начинается самое интересное.

Класс это немаленький и находится в runtime/src/libraries/System.Private.CoreLib/src/System/Globalization/. Раз он немаленький, — он partial, и разбит на несколько файлов.

Для начала пойдем в CompareInfo.cs. В конечном итоге, все перегрузки IndexOf приводят сюда (строчка 949):

        private unsafe int IndexOf(ReadOnlySpan<char> source, ReadOnlySpan<char> value, int* matchLengthPtr, CompareOptions options, bool fromBeginning)
        {
            Debug.Assert(matchLengthPtr != null);
            *matchLengthPtr = 0;

            int retVal = 0;

            if ((options & ValidIndexMaskOffFlags) == 0)
            {
                // Common case: caller is attempting to perform a linguistic search.
                // Pass the flags down to NLS or ICU unless we're running in invariant
                // mode, at which point we normalize the flags to Ordinal[IgnoreCase].

                if (!GlobalizationMode.Invariant)
                {
                    if (value.IsEmpty)
                    {
                        // empty target substring trivially occurs at beginning / end of search space
                        return (fromBeginning) ? 0 : source.Length;
                    }
                    else
                    {
                        return IndexOfCore(source, value, options, matchLengthPtr, fromBeginning);
                    }
                }

                if ((options & CompareOptions.IgnoreCase) == 0)
                {
                    retVal = (fromBeginning) ? source.IndexOf(value) : source.LastIndexOf(value);
                }
                else
                {
                    retVal = fromBeginning ? Ordinal.IndexOfOrdinalIgnoreCase(source, value) : Ordinal.LastIndexOfOrdinalIgnoreCase(source, value);
                }
            }
            else
            {
                // Less common case: caller is attempting to perform non-linguistic comparison,
                // or an invalid combination of flags was supplied.

                if (options == CompareOptions.Ordinal)
                {
                    retVal = (fromBeginning) ? source.IndexOf(value) : source.LastIndexOf(value);
                }
                else if (options == CompareOptions.OrdinalIgnoreCase)
                {
                    retVal = fromBeginning ? Ordinal.IndexOfOrdinalIgnoreCase(source, value) : Ordinal.LastIndexOfOrdinalIgnoreCase(source, value);
                }
                else
                {
                    ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidFlag, ExceptionArgument.options);
                }
            }

            // Both Ordinal and OrdinalIgnoreCase match by individual code points in a non-linguistic manner.
            // Non-BMP code points will never match BMP code points, so given UTF-16 inputs the match length
            // will always be equivalent to the target string length.

            if (retVal >= 0)
            {
                *matchLengthPtr = value.Length;
            }
            return retVal;
        }

Поскольку мы не задаем опций, мы попадаем в первую ветку if. Далее, поскольку у нас сравнение с учетом культуры (т.е. не Invariant) и строка не пустая, вызывается IndexOfCore.

Смотрим как он сделан:

        private unsafe int IndexOfCore(ReadOnlySpan<char> source, ReadOnlySpan<char> target, CompareOptions options, int* matchLengthPtr, bool fromBeginning) =>
            GlobalizationMode.UseNls ?
                NlsIndexOfCore(source, target, options, matchLengthPtr, fromBeginning) :
                IcuIndexOfCore(source, target, options, matchLengthPtr, fromBeginning);

Ничего особенного — проверяем флаг и вызываем нужный метод. Флаг этот находится в классе GlobalizationMode.cs (лежит в той же папке). Он тоже partial и разбит на несколько файлов. И они уже имеют суффиксы соответствующие той или иной платформе.

Смотрим что у нас под Windows

        internal static bool UseNls { get; } = !Invariant &&
            (AppContextConfigHelper.GetBooleanConfig("System.Globalization.UseNls", "DOTNET_SYSTEM_GLOBALIZATION_USENLS") ||
                !LoadIcu());

И под Unix:

internal static bool UseNls => false;

Под Unix у нас без вариантов — только ICU (International Components for Unicode), под Windows возможно и то и другое, — и это весьма интересный факт. Поиск по ключевому слову DOTNET_SYSTEM_GLOBALIZATION_USENLS приводит нас к документации Microsoft о глобализации и ICU. Я не буду пересказывать все что написано в этой статье, скажу лишь что изначально, до .NET 5.0, на Windows, для глобализации, исторически использовался только NLS (National Language Support). Теперь же может использоваться и ICU.

В статье описаны и условия при которых в Windows будет использоваться ICU — это Windows 10 May 2019 Update и новее, включающая в себя icu.dll ну и разумеется использование .NET 5.0. В Случае если эта библиотека не будет найдена, будет использован старый механизм NLS.

В статье приведен и способ проверки того, используются ли у вас ICU. Для этого надо выполнить следующий код:

string s = "Hello\r\nworld!";
int idx = s.IndexOf("\n");
Console.WriteLine(idx);

Если задействованы ICU вернется -1 если NLS вернется 6. Ожидаемо под MacOSX вернулось -1. Под Windows, если не крутить никакие настройки, у меня (поскольку стоит Windows 10 2004 H2 и запуск под .NET 5) возвращается также -1. Если принудительно включить использование NLS (я делал через добавление RuntimeHostConfigurationOption в ItemGroup в файле проекта), возвращается 6, как и написано в документации. Теперь сделаем замеры с включенной опцией NLS под Windows:

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19042
Intel Core i9-9900K CPU 3.60GHz (Coffee Lake), 1 CPU, 16 logical and 8 physical cores
.NET Core SDK=5.0.202
  [Host]  : .NET Core 5.0.5 (CoreCLR 5.0.521.16609, CoreFX 5.0.521.16609), X64 RyuJIT
  FindAll : .NET Core 5.0.5 (CoreCLR 5.0.521.16609, CoreFX 5.0.521.16609), X64 RyuJIT

Job=FindAll  InvocationCount=30000  IterationCount=5  
LaunchCount=3  RunStrategy=ColdStart  WarmupCount=2  

Method	input	Mean	Error	StdDev	Ratio
AhoCorasick	Mozi(…)7.36 [2000]	18.16 μs	0.629 μs	0.589 μs	0.04
Naive	Mozi(…)7.36 [2000]	464.42 μs	7.434 μs	6.953 μs	1.00

Ничего вообще не поменялось в плане скорости. Возвращаемся к CompareInfo.cs. Под Windows, поскольку он поддерживает NLS, используется CompareInfo.Nls.cs

Под Unix используется CompareInfo.Icu.cs

Сначала Windows:

private unsafe int NlsIndexOfCore(ReadOnlySpan<char> source, ReadOnlySpan<char> target, CompareOptions options, int* matchLengthPtr, bool fromBeginning)
{
    Debug.Assert(!GlobalizationMode.Invariant);
    Debug.Assert(GlobalizationMode.UseNls);

    Debug.Assert(target.Length != 0);

    uint positionFlag = fromBeginning ? (uint)FIND_FROMSTART : FIND_FROMEND;
    return FindString(positionFlag | (uint)GetNativeCompareFlags(options), source, target, matchLengthPtr);
}

Все сводится к вызову FindString который имеет следующую реализацию:

        private unsafe int FindString(
                    uint dwFindNLSStringFlags,
                    ReadOnlySpan<char> lpStringSource,
                    ReadOnlySpan<char> lpStringValue,
                    int* pcchFound)
        {
            Debug.Assert(!GlobalizationMode.Invariant);
            Debug.Assert(!lpStringValue.IsEmpty);

            string? localeName = _sortHandle != IntPtr.Zero ? null : _sortName;

            // FindNLSStringEx disallows passing an explicit 0 for cchSource or cchValue.
            // The caller should've already checked that 'lpStringValue' isn't empty,
            // but it's possible for 'lpStringSource' to be empty. In this case we'll
            // substitute an empty null-terminated string and pass -1 so that the NLS
            // function uses the implicit string length.

            int lpStringSourceLength = lpStringSource.Length;
            if (lpStringSourceLength == 0)
            {
                lpStringSource = string.Empty;
                lpStringSourceLength = -1;
            }

            fixed (char* pLocaleName = localeName)
            fixed (char* pSource = &MemoryMarshal.GetReference(lpStringSource))
            fixed (char* pValue = &MemoryMarshal.GetReference(lpStringValue))
            {
                Debug.Assert(pSource != null && pValue != null);

                int result = Interop.Kernel32.FindNLSStringEx(
                                    pLocaleName,
                                    dwFindNLSStringFlags,
                                    pSource,
                                    lpStringSourceLength,
                                    pValue,
                                    lpStringValue.Length,
                                    pcchFound,
                                    null,
                                    null,
                                    _sortHandle);

                Debug.Assert(result >= -1 && result <= lpStringSource.Length);

                // SetLastError is only performed under debug builds.
                Debug.Assert(result >= 0 || Marshal.GetLastWin32Error() == Interop.Errors.ERROR_SUCCESS);

                return result;
            }
        }

В конечном итоге — все сводится к вызову функции FindNLSStringEx из kernel32.dll

Далее смотрим что у нас под Unix:

        private unsafe int IcuIndexOfCore(ReadOnlySpan<char> source, ReadOnlySpan<char> target, CompareOptions options, int* matchLengthPtr, bool fromBeginning)
        {
            Debug.Assert(!GlobalizationMode.Invariant);
            Debug.Assert(!GlobalizationMode.UseNls);
            Debug.Assert(target.Length != 0);

            if (_isAsciiEqualityOrdinal && CanUseAsciiOrdinalForOptions(options))
            {
                if ((options & CompareOptions.IgnoreCase) != 0)
                    return IndexOfOrdinalIgnoreCaseHelper(source, target, options, matchLengthPtr, fromBeginning);
                else
                    return IndexOfOrdinalHelper(source, target, options, matchLengthPtr, fromBeginning);
            }
            else
            {
                // GetReference may return nullptr if the input span is defaulted. The native layer handles
                // this appropriately; no workaround is needed on the managed side.

                fixed (char* pSource = &MemoryMarshal.GetReference(source))
                fixed (char* pTarget = &MemoryMarshal.GetReference(target))
                {
                    if (fromBeginning)
                        return Interop.Globalization.IndexOf(_sortHandle, pTarget, target.Length, pSource, source.Length, options, matchLengthPtr);
                    else
                        return Interop.Globalization.LastIndexOf(_sortHandle, pTarget, target.Length, pSource, source.Length, options, matchLengthPtr);
                }
            }
        }

Пути ведут в Interop.Globalization.IndexOf(_sortHandle, pTarget, target.Length, pSource, source.Length, options, matchLengthPtr); Это уже код из runtime/src/libraries/Common/src/Interop/

В итоге, все будет зависеть от конкретной системы, так как данная функция определена как:

        [DllImport(Libraries.GlobalizationNative, CharSet = CharSet.Unicode, EntryPoint = "GlobalizationNative_IndexOf")]
        internal static extern unsafe int IndexOf(IntPtr sortHandle, char* target, int cwTargetLength, char* pSource, int cwSourceLength, CompareOptions options, int* matchLengthPtr);

Очевидно под MacOSX (в моем случае) реализация эта сильно эффективнее нежели чем функция Windows.

Ну и сделаем сравнение без учета культуры (т.е. Invariant). Сначала MacOSX

BenchmarkDotNet=v0.12.1, OS=macOS 11.2.3 (20D91) [Darwin 20.3.0]
Intel Core i5-1030NG7 CPU 1.10GHz, 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.101
  [Host]  : .NET Core 5.0.1 (CoreCLR 5.0.120.57516, CoreFX 5.0.120.57516), X64 RyuJIT
  FindAll : .NET Core 5.0.1 (CoreCLR 5.0.120.57516, CoreFX 5.0.120.57516), X64 RyuJIT

Job=FindAll  InvocationCount=30000  IterationCount=5  
LaunchCount=3  RunStrategy=ColdStart  WarmupCount=2  

Method	input	Mean	Error	StdDev	Ratio	RatioSD
AhoCorasick	Mozi(…)7.36 [2000]	27.10 μs	1.122 μs	1.050 μs	1.71	0.05
Naive	Mozi(…)7.36 [2000]	15.86 μs	0.808 μs	0.756 μs	1.00	0.00

Ничего принципиально не меняется. Теперь Windows:

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19042
Intel Core i9-9900K CPU 3.60GHz (Coffee Lake), 1 CPU, 16 logical and 8 physical cores
.NET Core SDK=5.0.202
  [Host]  : .NET Core 5.0.5 (CoreCLR 5.0.521.16609, CoreFX 5.0.521.16609), X64 RyuJIT
  FindAll : .NET Core 5.0.5 (CoreCLR 5.0.521.16609, CoreFX 5.0.521.16609), X64 RyuJIT

Job=FindAll  InvocationCount=30000  IterationCount=5  
LaunchCount=3  RunStrategy=ColdStart  WarmupCount=2  

Method	input	Mean	Error	StdDev	Ratio	RatioSD
AhoCorasick	Mozi(…)7.36 [2000]	18.16 μs	0.637 μs	0.596 μs	1.50	0.04
Naive	Mozi(…)7.36 [2000]	12.13 μs	0.773 μs	0.723 μs	1.00	0.00

Ага! Ускорение более чем в 30 раз! В относительных величинах ускорение огромное, но не такое впечатляющее, учитывая разницу в мощи используемых машин — мак это MacBook Air, а Windows — это мощная рабочая станция, которая раз пять мощнее чем легкий ультрабук.

Выводы

Я конечно не могу 100% утверждать, но все выглядит так, как будто под MacOS делается некая оптимизация и сравнение идет без учета культуры, даже если указано иное, возможно определятся что строка не требует сравнения с учетом культуры и идет простое сравнение байтов. Иначе, мне сложно объяснить одинаковую производительность, как при использовании NLS, так и при использовании ICU под Windows и при этом Unix вариант (где всегда ICU) быстрее почти в 30 раз. Хотя, я сначала подумал, что Windows всегда работает с использованием NLS, и вышеупомянутая FindNLSStringEx из kernel32.dll просто сильно медленнее. Но нет, она по скорости работы ничем не отличается от варианта по умолчанию в .NET 5 (ICU).

Кроме отличий в работе функции IndexOf — есть и другие различия в работе функций касающихся культурных особенностей (глобализации), и обо всем об этом читайте в документации Microsoft.