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

Часто бывает, что мы соединяем 2 коллекции или группируем коллекцию при помощи LINQ to Objects. При этом происходит сравнение ключей, выбранных для группировки или связывания.
К счастью, стоимость этих операций равна O(n). Но в случае больших коллекций нам важна эффективность самого сравнения. Если в качестве ключей выбраны строки, то какая из реализаций сравнения будет использована по умолчанию, подходит ли эта реализация для ваших строк и можно ли, указав IEqualityComparer<string> явно, сделать эту операцию быстрее?

clients.Join(orders, 
                   c => c.Name, 
                   o => o.ClientName, 
                   (c, o) => CreateOrederDto(c, o));

Как же выбирается реализация компаратора, если пользователь не указал её явно?

В исходном коде метода Join можно увидеть следующее поведение:

public static IEnumerable<TResult> Join<TOuter, TInner, TKey, TResult>(this IEnumerable<TOuter> outer, IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector) {
    if (outer == null) throw Error.ArgumentNull("outer");
    if (inner == null) throw Error.ArgumentNull("inner");
    if (outerKeySelector == null) throw Error.ArgumentNull("outerKeySelector");
    if (innerKeySelector == null) throw Error.ArgumentNull("innerKeySelector");
    if (resultSelector == null) throw Error.ArgumentNull("resultSelector");
    return JoinIterator<TOuter, TInner, TKey, TResult>(outer, inner, outerKeySelector, innerKeySelector, resultSelector, null);
}

static IEnumerable<TResult> JoinIterator<TOuter, TInner, TKey, TResult>(IEnumerable<TOuter> outer, IEnumerable<TInner> inner, Func<TOuter, TKey> outerKeySelector, Func<TInner, TKey> innerKeySelector, Func<TOuter, TInner, TResult> resultSelector, IEqualityComparer<TKey> comparer) {
    Lookup<TKey, TInner> lookup = Lookup<TKey, TInner>.CreateForJoin(inner, innerKeySelector, comparer);
    foreach (TOuter item in outer) {
        Lookup<TKey, TInner>.Grouping g = lookup.GetGrouping(outerKeySelector(item), false);
        if (g != null) {
            for (int i = 0; i < g.count; i++) {
                yield return resultSelector(item, g.elements[i]);
            }
        }
    }
}

Хорошо, в метод JoinIterator передаётся null, внутри не происходит никаких проверок и значение null передаётся в качестве параметра при создании Lookup в метод CreateForJoin.

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

Нас интересует метод CreateForJoin:

internal static Lookup<TKey, TElement> CreateForJoin(IEnumerable<TElement> source, Func<TElement, TKey> keySelector, IEqualityComparer<TKey> comparer) {
    Lookup<TKey, TElement> lookup = new Lookup<TKey, TElement>(comparer);
    ...
}

Lookup(IEqualityComparer<TKey> comparer) {
    if (comparer == null) comparer = EqualityComparer<TKey>.Default;
    this.comparer = comparer;
    groupings = new Grouping[7]; // 7 - хорошее число, пусть здесь будет 7
}

EqualityComparer

Generic-интерфейс IEqualityComparer<T> имеет базовую реализацию в виде абстрактного класса EqualityComparer<T>, который в свою очередь имеет статическое свойство Default для выбора умолчательного компаратора конкретного класса T. То есть, для любого T, класса, структуры или простого типа, будет выбран актуальный компаратор объектов этого типа.
Полный код выбора в зависимости от типа довольно витиеват, но интересен с точки зрения понимания работы наших Join и GroupBy.

1. Для byte будет выбран свой особенный ByteEqualityComparer. Этот класс создан с целью повышения производительности при сравнении массивов байт, поскольку содержит реализацию IndexOf для байтового массива.
2. Если T реализует интерфейс IEquatable<T>, то будет выбран GenericEqualityComparer<T>, который сравнивает объекты на основе вызова их реализаций метода IEquatable<T>.Equals(T). Кроме того, перед вызовом оба параметра будут проверены на неравенство null.
3. Если T представляет собой Nullable<U>, значение которого реализует IEquatable<U>, будет использован класс NullableEqualityComparer<T>, аналогичный предыдущему и содержащий дополнительные проверки HasValue.
4. Для перечислений в зависимости от базового типа будет выбрана одна из реализаций EnumEqualityComparer<T> (для типа long есть своя особенная реализация), которые отличаются только JIT-оптимизациями того, как значение перечисления будет приведено к числовому значению.
5. Во всех остальных случаях используется ObjectEqualityComparer<T>, который сравнивает объекты на основе Object.Equals. Здесь всё как обычно — для ссылочных типов проверяется равенство ссылок, для значимых — совпадение типов объектов (в случае с ObjectEqualityComparer<T> всегда true) и совпадение значений всех полей объектов.

Класс String реализует интерфейс IEquatable<T> и потому при сравнении строк будет вызвана реализация этого интерфейса.
Для .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
 
        // Для строк с нечётной длиной последнее сравнение будет включать 
        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<string>, то все его наследники можно указывать в качестве параметра там, где ожидается IEqualityComparer<string>.
Я неоднократно встречал описания этих методов сравнения, но ни разу по-настоящему не задумывался, что значит «сравнение по словам с учётом текущей культуры».
Будет ли побайтовое сравнение идентично таковому при выборе EqualityComparer<String>.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-строками проверка осуществляется действительно посимвольно, каждый символ проверяется на регистр и, при необходимости, переводится в верхний регистр простым вычитанием 0x20.

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<string> медленнее за счёт дополнительных проверок входных параметров. В 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.

Автор: Vadimyan

Источник