- PVSM.RU - https://www.pvsm.ru -
Часто бывает, что мы соединяем 2 коллекции или группируем коллекцию при помощи LINQ to Objects [1]. При этом происходит сравнение ключей, выбранных для группировки или связывания.
К счастью, стоимость этих операций равна O(n). Но в случае больших коллекций нам важна эффективность самого сравнения. Если в качестве ключей выбраны строки, то какая из реализаций сравнения будет использована по умолчанию, подходит ли эта реализация для ваших строк и можно ли, указав IEqualityComparer<string> явно [2], сделать эту операцию быстрее?
clients.Join(orders,
c => c.Name,
o => o.ClientName,
(c, o) => CreateOrederDto(c, o));
Как же выбирается реализация компаратора, если пользователь не указал её явно?
В исходном коде метода Join [3] можно увидеть следующее поведение:
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 [4] нечасто можно встретить в явном виде. Этот класс представляет собой коллекцию с доступом к элементам по ключу, при этом для каждого ключа может храниться несколько элементов, а в случае попытки доступа по несуществующему ключу просто вернётся пустая коллекция [5].
Нас интересует метод CreateForJoin [6]:
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
}
Generic-интерфейс IEqualityComparer<T> [7] имеет базовую реализацию в виде абстрактного класса EqualityComparer<T> [8], который в свою очередь имеет статическое свойство Default [9] для выбора умолчательного компаратора конкретного класса T. То есть, для любого T, класса, структуры или простого типа, будет выбран актуальный компаратор объектов этого типа.
Полный код выбора [10] в зависимости от типа довольно витиеват, но интересен с точки зрения понимания работы наших Join и GroupBy.
Класс String [13] реализует интерфейс IEquatable<T> и потому при сравнении строк будет вызвана реализация этого интерфейса.
Для .NET Core реализация выбора компаратора по умолчанию другая [14] — в случае со строками будет выбран EqualityComparerForString [15], который использует при сравнении только оператор проверки равенства ==.
Метод String.Equals(string value) [16] проверяет равенство ссылок строк, равенство длины строк, и в случае, если вычислить равенство на основе этих свойств не получилось, вызывает (почти) побайтовое сравнение буферов строк [17]:
[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 даже размотали циклы [18].
Итак, по умолчанию, для сравнения строк используется побайтовое сравнение содержимого этих строк. Эффективно? Наверное. А как ещё можно сравнивать строки?
Для класса String в .net есть своя абстрактная реализация компаратора StringComparer [19] и ряд унаследованных от него классов, доступ к экземплярам которых можно получить через статические свойства этого класса. Есть 6 реализаций сравнения строк 3 видов с учётом и без учёта регистра символов каждый:
Так как StringComparer реализует IEqualityComparer<string>, то все его наследники можно указывать в качестве параметра там, где ожидается IEqualityComparer<string>.
Я неоднократно встречал описания этих методов сравнения, но ни разу по-настоящему не задумывался, что значит «сравнение по словам с учётом текущей культуры».
Будет ли побайтовое сравнение идентично таковому при выборе EqualityComparer<String>.Default или явному вызову метода Equals? За сравнение в этом случае отвечает класс OrdinalComparer [20]:
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 [21], поскольку эта операция зависит от культуры. Но результат всё-таки превзошёл ожидания. Для вызова String.Compare(x, y, StringComparison.OrdinalIgnoreCase) выполняется следующая ветвь кода [22]:
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 строк вызывается нативный код [23] на C++ и далее в зависимости от условий может вызываться метод сравнения строк из ядра Windows или (судя по комментариям, это возможно только для Windows XP) метод [24], который проводит такое же посимвольное сравнение, переводя каждый символ в верхний регистр на основе таблиц символов операционной системы.
Это действительно вызывает интерес к вопросу производительности, поскольку производительность одного и того же компаратора может отличаться в зависимости от входных данных, в вырожденном случае — от изменения одного символа в строке.
А что на счёт культур? Класс CultureAwareComparer [25] принимает на вход культуру, на основании которой будет сравнивать строки и флаг, сообщающий о том, будет ли игнорироваться регистр символов. Информация о культуре содержит свойство CompareInfo [26], объект которого содержит методы для сравнения строк с учётом данной культуры, которые и используются в CultureAwareComparer.
return (_compareInfo.Compare(x, y, _ignoreCase? CompareOptions.IgnoreCase : CompareOptions.None) == 0);
К сожалению, внутри нет ничего интересного, поскольку по факту вызывается нативный код [27], который снова лезет в ядро для вызова функции сортировки строк. Чтобы компенсировать отсутствие кода вот вам отрывок, который неоднократно встречается в функциях работы со строками в 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 [28]. Результаты немного плавали, но я решил, что 10.000 итераций по 1.000.000 будет достаточно и без доверительного интервала.
Сценарий | Миллисекунд/1.000.000 операций | Относительная разница |
---|---|---|
string.Equals | 25.8 | 1x |
EqualityComparer<string>.Default | 33.5 | 1.3x |
StringComparer.Ordinal | 29.8 | 1.16x |
StringComparer.OrdinalIgnoreCase | 50.3 | 1.95x |
StringComparer.OrdinalIgnoreCase non ASCII | 82.2 | 3.19x |
StringComparer.CurrentCulture | 136 | 5.27x |
StringComparer.CurrentCulture non ASCII | 174.3 | 6.76x |
StringComparer.CurrentCultureIgnoreCase | 134.5 | 5.21x |
StringComparer.CurrentCultureIgnoreCase non ASCII | 172.1 | 6.67x |
StringComparer.InvariantCulture | 132.2 | 5.12x |
StringComparer.InvariantCulture non ASCII | 189.5 | 7.34x |
StringComparer.InvariantCultureIgnoreCase | 134.1 | 5.2x |
StringComparer.InvariantCultureIgnoreCase non ASCII | 188 | 7.29x |
Результаты подтверждают код — явный вызов string.Equals быстрее всего, GenericEqualityComparer<string> медленнее за счёт дополнительных проверок входных параметров. В OrdinalComparer тоже есть дополнительные проверки. А далее вызываются либо не размотанные циклы, либо методы неуправляемого кода, которые, вообще говоря, ведут себя по-разному на разных платформах, но в случае работы с культурой вызывают методы из ядра операционной системы.
Казалось бы, по умолчанию используется самое быстрое и простое сравнение, программисту можно не беспокоиться. На самом деле всё не совсем так. Есть ещё ряд операций над строками. Например, определение того, начинается ли строка с определенной подстроки [29]:
public Boolean StartsWith(String value) {
return StartsWith(value, StringComparison.CurrentCulture);
}
В то же время проверка вхождения подстроки [30] (казалось бы, тоже самое) снова осуществляется побайтово:
public bool Contains( string value ) {
return ( IndexOf(value, StringComparison.Ordinal) >=0 );
}
А проверка вхождения подстроки, которая вернёт индекс начала этой подстроки [31] — снова с текущей культурой:
public int IndexOf(String value) {
return IndexOf(value, StringComparison.CurrentCulture);
}
LastIndexOf вообще вызывает нативный код. Что в нём происходит? Только Сатья знает.
Что же делать со всей этой информацией?
Автор: Vadimyan
Источник [32]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/c-2/111058
Ссылки в тексте:
[1] LINQ to Objects: https://msdn.microsoft.com/en-us/library/bb397919.aspx
[2] указав IEqualityComparer<string> явно: https://msdn.microsoft.com/en-us/library/bb549267(v=vs.110).aspx
[3] исходном коде метода Join: https://github.com/dotnet/corefx/blob/3d8569f7f2c8dd387366cbd2ef1b1cc4edab7038/src/System.Linq/src/System/Linq/Enumerable.cs#L938
[4] Lookup: https://msdn.microsoft.com/en-us/library/bb460184(v=vs.110).aspx
[5] вернётся пустая коллекция: https://msdn.microsoft.com/en-us/library/bb292716(v=vs.110).aspx
[6] CreateForJoin: https://github.com/dotnet/corefx/blob/3d8569f7f2c8dd387366cbd2ef1b1cc4edab7038/src/System.Linq/src/System/Linq/Enumerable.cs#L3250
[7] IEqualityComparer<T>: https://msdn.microsoft.com/en-us/library/ms132151(v=vs.110).aspx
[8] EqualityComparer<T>: https://github.com/dotnet/corefx/blob/3d8569f7f2c8dd387366cbd2ef1b1cc4edab7038/src/System.Collections/src/System/Collections/Generic/EqualityComparer.cs
[9] Default: https://msdn.microsoft.com/en-us/library/ms224763(v=vs.110).aspx
[10] Полный код выбора: https://github.com/dotnet/coreclr/blob/ef1e2ab328087c61a6878c1e84f4fc5d710aebce/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs#L43
[11] GenericEqualityComparer<T>: https://github.com/dotnet/coreclr/blob/ef1e2ab328087c61a6878c1e84f4fc5d710aebce/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs#L129
[12] Object.Equals: https://msdn.microsoft.com/en-us/library/bsc2ak47(v=vs.110).aspx
[13] String: https://msdn.microsoft.com/en-us/library/system.string(v=vs.110).aspx
[14] другая: https://github.com/dotnet/corefx/blob/3d8569f7f2c8dd387366cbd2ef1b1cc4edab7038/src/System.Collections/src/System/Collections/Generic/EqualityComparer.cs#L21
[15] EqualityComparerForString: https://github.com/dotnet/corefx/blob/3d8569f7f2c8dd387366cbd2ef1b1cc4edab7038/src/System.Collections/src/System/Collections/Generic/EqualityComparer.cs#L321
[16] String.Equals(string value): https://github.com/dotnet/coreclr/blob/ef1e2ab328087c61a6878c1e84f4fc5d710aebce/src/mscorlib/src/System/String.cs#L518
[17] побайтовое сравнение буферов строк: https://github.com/dotnet/coreclr/blob/ef1e2ab328087c61a6878c1e84f4fc5d710aebce/src/mscorlib/src/System/String.cs#L356
[18] размотали циклы: https://ru.wikipedia.org/wiki/Размотка_цикла
[19] StringComparer: https://msdn.microsoft.com/en-us/library/system.stringcomparer(v=vs.110).aspx
[20] OrdinalComparer: https://github.com/dotnet/coreclr/blob/bc146608854d1db9cdbcc0b08029a87754e12b49/src/mscorlib/src/System/StringComparer.cs#L275
[21] ToLower: https://msdn.microsoft.com/en-us/library/system.string.tolower(v=vs.110).aspx
[22] ветвь кода: https://github.com/dotnet/coreclr/blob/bc146608854d1db9cdbcc0b08029a87754e12b49/src/mscorlib/src/System/String.cs#L1798
[23] нативный код: https://github.com/dotnet/coreclr/blob/bc146608854d1db9cdbcc0b08029a87754e12b49/src/classlibnative/nls/nlsinfo.cpp#L2546
[24] метод: https://github.com/dotnet/coreclr/blob/bc146608854d1db9cdbcc0b08029a87754e12b49/src/utilcode/downlevel.cpp#L1593
[25] CultureAwareComparer: https://github.com/dotnet/coreclr/blob/bc146608854d1db9cdbcc0b08029a87754e12b49/src/mscorlib/src/System/StringComparer.cs#L129
[26] CompareInfo: https://msdn.microsoft.com/en-us/library/system.globalization.compareinfo(v=vs.110).aspx
[27] нативный код: https://github.com/dotnet/coreclr/blob/bc146608854d1db9cdbcc0b08029a87754e12b49/src/classlibnative/nls/nlsinfo.cpp#L1648
[28] GitHub: https://github.com/Vadimyan/StringComparationBenchmark
[29] начинается ли строка с определенной подстроки: https://github.com/dotnet/coreclr/blob/bc146608854d1db9cdbcc0b08029a87754e12b49/src/mscorlib/src/System/String.cs#L2516
[30] проверка вхождения подстроки: https://github.com/dotnet/coreclr/blob/bc146608854d1db9cdbcc0b08029a87754e12b49/src/mscorlib/src/System/String.cs#L2133
[31] которая вернёт индекс начала этой подстроки: https://github.com/dotnet/coreclr/blob/bc146608854d1db9cdbcc0b08029a87754e12b49/src/mscorlib/src/System/String.cs#L2269
[32] Источник: https://habrahabr.ru/post/274491/
Нажмите здесь для печати.