Сравнение строк в C# (по умолчанию)02.02.2016 12:33

Класс String реализует интерфейс IEquatable и потому при сравнении строк будет вызвана реализация этого интерфейса.
Для .NET Core реализация выбора компаратора по умолчанию другая — в случае со строками будет выбран EqualityComparerForString, который использует при сравнении только оператор проверки равенства ==.

Сравнение строк

Метод String.Equals (string value) проверяет равенство ссылок строк, равенство длины строк, и в случае, если вычислить равенство на основе этих свойств не получилось, вызывает (почти) побайтовое сравнение буферов строк:

[System.Security.SecuritySafeCritical]  // auto-generated
[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
private unsafe static bool EqualsHelper(String strA, String strB)
{
    int length = strA.Length;
 
    fixed (char* ap = &strA.m_firstChar) 
    fixed (char* bp = &strB.m_firstChar)
    {
        char* a = ap;
        char* b = bp;
 
        // размотка цикла
#if AMD64
        // Для платформы AMD64 размотка по 12 байт и сравнение 3 qword за итерацию.  
        while (length >= 12)
        {
            if (*(long*)a     != *(long*)b) return false;
            if (*(long*)(a+4) != *(long*)(b+4)) return false;
            if (*(long*)(a+8) != *(long*)(b+8)) return false;
            a += 12; b += 12; length -= 12;
        }
#else
        while (length >= 10)
        {
            if (*(int*)a != *(int*)b) return false;
            if (*(int*)(a+2) != *(int*)(b+2)) return false;
            if (*(int*)(a+4) != *(int*)(b+4)) return false;
            if (*(int*)(a+6) != *(int*)(b+6)) return false;
            if (*(int*)(a+8) != *(int*)(b+8)) return false;
            a += 10; b += 10; length -= 10;
        }
#endif
 
        // Для строк с нечётной длиной последнее сравнение будет включать \0
        while (length > 0) 
        {
            if (*(int*)a != *(int*)b) break;
            a += 2; b += 2; length -= 2;
        }
 
        return (length <= 0);
    }
}

Для повышения производительности в Microsoft даже размотали циклы.
Итак, по умолчанию, для сравнения строк используется побайтовое сравнение содержимого этих строк. Эффективно? Наверное. А как ещё можно сравнивать строки?

StringComparer

Для класса String в .net есть своя абстрактная реализация компаратора StringComparer и ряд унаследованных от него классов, доступ к экземплярам которых можно получить через статические свойства этого класса. Есть 6 реализаций сравнения строк 3 видов с учётом и без учёта регистра символов каждый:

• CurrentCulture/CurrentCultureIgnoreCase — сравнение по словам с учётом правил текущей культуры и языка (культуры текущего Thread)
• InvariantCulture/InvariantCultureIgnoreCase — сравнение по словам без учёта правил языка и культуры и языка (используется CultureInfo.InvariantCulture)
• Ordinal/OrdinalIgnoreCase — побайтовое сравнение

Так как StringComparer реализует IEqualityComparer, то все его наследники можно указывать в качестве параметра там, где ожидается IEqualityComparer.
Я неоднократно встречал описания этих методов сравнения, но ни разу по-настоящему не задумывался, что значит «сравнение по словам с учётом текущей культуры».
Будет ли побайтовое сравнение идентично таковому при выборе EqualityComparer.Default или явному вызову метода Equals? За сравнение в этом случае отвечает класс OrdinalComparer:

public override bool Equals(string x, string y) {
    if (Object.ReferenceEquals(x ,y)) return true;
    if (x == null || y == null) return false;
 
    if( _ignoreCase) {
        if( x.Length != y.Length) {
            return false;
        }
        return (String.Compare(x, y, StringComparison.OrdinalIgnoreCase) == 0);                                            
    }
    return x.Equals(y);
}  

В случае учёта регистра символов отличие заключается в дублировании проверок равенства ссылок объектов и проверки на null. Это не очень много, хотя с точки зрения MSIL это пара десятков инструкций:

     IL_0000: nop
        IL_0001: ldarg.0
        IL_0002: ldarg.1
        IL_0003: call bool [mscorlib]System.Object::ReferenceEquals(object, object)
        IL_0008: ldc.i4.0
        IL_0009: ceq
        IL_000b: stloc.1
        IL_000c: ldloc.1
        IL_000d: brtrue.s IL_0013

        IL_000f: ldc.i4.1
        IL_0010: stloc.0
        IL_0011: br.s IL_003e

        IL_0013: ldarg.0
        IL_0014: brfalse.s IL_001f

        IL_0016: ldarg.1
        IL_0017: ldnull
        IL_0018: ceq
        IL_001a: ldc.i4.0
        IL_001b: ceq
        IL_001d: br.s IL_0020

        IL_001f: ldc.i4.0

        IL_0020: nop
        IL_0021: stloc.1
        IL_0022: ldloc.1
        IL_0023: brtrue.s IL_0029

        IL_0025: ldc.i4.0
        IL_0026: stloc.0
        IL_0027: br.s IL_003e

Как насчёт сохранения без учёта регистра? Признаться, я и не ожидал увидеть что-то вроде ToLower, поскольку эта операция зависит от культуры. Но результат всё-таки превзошёл ожидания. Для вызова String.Compare (x, y, StringComparison.OrdinalIgnoreCase) выполняется следующая ветвь кода:

case StringComparison.OrdinalIgnoreCase:
        if (this.Length != value.Length)
                return false;
 
        // Если обе строки содержат только ASCII символы, мы можем пойти по быстрому пути.
        if (this.IsAscii() && value.IsAscii()) {
                return (CompareOrdinalIgnoreCaseHelper(this, value) == 0);
        }
#if FEATURE_COREFX_GLOBALIZATION
        return CompareInfo.CompareOrdinalIgnoreCase(strA, 0, strA.Length, strB, 0, strB.Length);
#else
        // Медленное решение
        return TextInfo.CompareOrdinalIgnoreCase(strA, strB);
#endif

Интересно, на сколько хуже должно быть медленное решение чтобы проверка IsAscii была оправдана?
В случае с ASCII-строками проверка осуществляется действительно посимвольно, каждый символ проверяется на регистр и, при необходимости, переводится в верхний регистр простым вычитанием 0×20.

private unsafe static int CompareOrdinalIgnoreCaseHelper(String strA, String strB)
{
    int length = Math.Min(strA.Length, strB.Length);
    
    fixed (char* ap = &strA.m_firstChar) 
    fixed (char* bp = &strB.m_firstChar)
    {
        char* a = ap;
        char* b = bp;
 
        while (length != 0) 
        {
            int charA = *a;
            int charB = *b;
 
            Contract.Assert((charA | charB) <= 0x7F, "strings have to be ASCII");
 
            // Перевод обоих символов в верхний регистр чтобы получить результат одним сравнением
            if ((uint)(charA - 'a') <= (uint)('z' - 'a')) charA -= 0x20;
            if ((uint)(charB - 'a') <= (uint)('z' - 'a')) charB -= 0x20;
 
            if (charA != charB)
                return charA - charB;
 
            // Следующий символ
            a++; b++;
            length--;
        }
 
        return strA.Length - strB.Length;
    }
}

Для не ASCII строк вызывается нативный код на C++ и далее в зависимости от условий может вызываться метод сравнения строк из ядра Windows или (судя по комментариям, это возможно только для Windows XP) метод, который проводит такое же посимвольное сравнение, переводя каждый символ в верхний регистр на основе таблиц символов операционной системы.

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

А что на счёт культур? Класс CultureAwareComparer принимает на вход культуру, на основании которой будет сравнивать строки и флаг, сообщающий о том, будет ли игнорироваться регистр символов. Информация о культуре содержит свойство CompareInfo, объект которого содержит методы для сравнения строк с учётом данной культуры, которые и используются в CultureAwareComparer.

return (_compareInfo.Compare(x, y, _ignoreCase? CompareOptions.IgnoreCase :  CompareOptions.None) == 0);

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

// TODO: Remove this workaround after Vista SP2 &/or turkic CompareStringEx() gets fixed on Vista.
// If its Vista and we want a turkik sort, then call CompareStringW not CompareStringEx
LPCWSTR pLingLocaleName = AvoidVistaTurkishBug ? GetLingusticLocaleName((LPWSTR)lpLocaleName, dwCmpFlags) : lpLocaleName;
// TODO: End of workaround for turkish CompareStringEx() on Vista/Win2K8

То есть, сравнение строк .net с учётом культуры и языка всегда происходит на уровне ядра операционной системы.

Тесты производительности

После такого путешествия я не смог не заинтересоваться реальной разницей в производительности. Изначально моим сценарием было объединение последовательностей, поскольку в результате происходит большое количество сравнений. Для чистого теста я оставил только сравнение строк без дополнительных операций. Исходный код теста можно посмотреть или сграбить на GitHub. Результаты немного плавали, но я решил, что 10.000 итераций по 1.000.000 будет достаточно и без доверительного интервала.

Результаты подтверждают код — явный вызов string.Equals быстрее всего, GenericEqualityComparer медленнее за счёт дополнительных проверок входных параметров. В OrdinalComparer тоже есть дополнительные проверки. А далее вызываются либо не размотанные циклы, либо методы неуправляемого кода, которые, вообще говоря, ведут себя по-разному на разных платформах, но в случае работы с культурой вызывают методы из ядра операционной системы.

Сравнение в других операциях над строками

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

public Boolean StartsWith(String value) {
    return StartsWith(value, StringComparison.CurrentCulture);
}

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

public bool Contains( string value ) {
    return ( IndexOf(value, StringComparison.Ordinal) >=0 );
}

А проверка вхождения подстроки, которая вернёт индекс начала этой подстроки — снова с текущей культурой:

public int IndexOf(String value) {
    return IndexOf(value, StringComparison.CurrentCulture);
}

LastIndexOf вообще вызывает нативный код. Что в нём происходит? Только Сатья знает.

Выводы

Что же делать со всей этой информацией?

• Во-первых, при большом числе сравнений можно получить прирост производительности этих операций примерно на 10%, реализовав свой компаратор строк, который не будет дублировать проверки, которые уже есть в методе string.Equals.
• Во-вторых, если строки представляют собой ключи, то можно принять решение об использовании только Ascii-символов, что даст выигрыш около 20% для большинства сравнений.
• В-третьих, нужно хорошо понимать и ограничивать случае, когда применяется сравнение с учётом культуры. Часто в коде я встречал именно опцию StringComparer.InvariantCulture поскольку автор считал именно такое сравнение наиболее общим. Но чаще всего достаточно использовать StringComparer.Ordinal или, в особенных случаях, StringComparer.OrdinalIgnoreCase.
• Используя различные методы класса String лучше перепроверить их поведение в исходниках. Возможно, вас ждёт неожиданность после тестов с «TestString» и «AnotherTestString», когда код уйдёт в production.

© Habrahabr.ru