Порівняння рядків в 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 (i != null) {
for (int i = 0; i < g.count; i++) {
yield return resultSelector(item, g.elements[i]);
}
}
}
}

Добре, метод JoinIterator передається null, всередині не відбувається жодних перевірок і значення null передається як параметр при створенні Lookup в метод CreateForJoin.

Використання Пошук нечасто можна зустріти в явному вигляді. Цей клас являє собою колекцію з доступом до елементів по ключу, при цьому для кожного ключа може зберігатися кілька елементів, а в разі спроби доступу по неіснуючому ключу просто повернеться порожня колекція.

Нас цікавить метод 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

// Для рядків з непарної довжиною останнє порівняння буде включати \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<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. Це не дуже багато, хоча з точки зору HTML це пара десятків інструкцій:
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 буде достатньо і без довірчого інтервалу.
Сценарій Мілісекунд/1.000.000 операцій Відносна різниця
string.Equals 25.8 1x
EqualityComparer<string>.Default 33.5 1.3 x
StringComparer.Ordinal 29.8 1.16 x
StringComparer.OrdinalIgnoreCase 50.3 1.95 x
StringComparer.OrdinalIgnoreCase non ASCII 82.2 3.19 x
StringComparer.CurrentCulture 136 5.27 x
StringComparer.CurrentCulture non ASCII 174.3 6.76 x
StringComparer.CurrentCultureIgnoreCase 134.5 5.21 x
StringComparer.CurrentCultureIgnoreCase non ASCII 172.1 6.67 x
StringComparer.InvariantCulture 132.2 5.12 x
StringComparer.InvariantCulture non ASCII 189.5 7.34 x
StringComparer.InvariantCultureIgnoreCase 134.1 5.2 x
StringComparer.InvariantCultureIgnoreCase non ASCII 188 7.29 x
Результати підтверджують код — явний виклик 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.


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.