Сравнение string и Span: поиск символов и подстрок

Публикую первую часть результатов сравнения методов string и Span. Начнём с методов для поиска символов и подстрок. Замеры проводились на массиве из 100 000 строк. Я постарался скомпоновать данные в виде диаграмм, но поскольку я сравнивал перегрузки с различными значениями StringComparison, то данных получилось очень много. Сырые результаты и бенчмарки можно найти здесь. Основные выводы, которые можно сделать на основе полученных данных ниже.

Contains

🟢Методы string.Contains(char value), string.Contains(string value), ReadOnlySpan<char>(char value) работают одинаково быстро.

🟢Методы Contains(char value, StringComparison comparisonType) и Contains(string value, StringComparison comparisonType) работают быстро при использовании Ordinal, OrdinalIgnoreCase, InvariantCulture и InvariantCultureIgnoreCase.

🟠Использование CurrentCulture и CurrentCultureIgnoreCase медленее в 250 – 330 раз.

StartsWith

🟢Методы StartsWith(string value, StringComparison comparisonType) работают быстро при использовании Ordinal, OrdinalIgnoreCase, InvariantCulture и InvariantCultureIgnoreCase.

🟠Использование CurrentCulture и CurrentCultureIgnoreCase медленее примерно в 100 раз.

🟠Метод string.StartsWith(string value) под капотом использует перегрузку с параметром CurrentCulture.

EndsWith

🟢Методы EndsWith(string value, StringComparison comparisonType) работают быстро при использовании Ordinal, OrdinalIgnoreCase, InvariantCulture и InvariantCultureIgnoreCase.

🟠Использование CurrentCulture и CurrentCultureIgnoreCase медленее примерно в 100 раз.

🟠Метод string.EndsWith(string value) под капотом использует перегрузку с параметром CurrentCulture.

IndexOf

🟢Метод IndexOf(char value) работает одинаково быстро как в string, так и в Span.

🟢Метод IndexOf(string value) работает быстро только в ReadOnlySpan.

🟢Методы IndexOf(char value, StringComparison comparisonType) и IndexOf(string value, StringComparison comparisonType) работают быстро при использовании Ordinal, OrdinalIgnoreCase, InvariantCulture и InvariantCultureIgnoreCase.

🟠Использование CurrentCulture и CurrentCultureIgnoreCase медленее примерно в 260 раз.

🟠Метод string.IndexOf(string value) под капотом использует перегрузку с параметром CurrentCulture.

LastIndexOf

🟢Метод LastIndexOf(char value) работает одинаково быстро как в string, так и в Span.

🟢Методы LastIndexOf(char value, StringComparison comparisonType) и LastIndexOf(string value, StringComparison comparisonType) работают быстро при использовании Ordinal, OrdinalIgnoreCase, InvariantCulture и InvariantCultureIgnoreCase.

🟠Использование CurrentCulture и CurrentCultureIgnoreCase медленее примерно в 260-370 раз.

🟠string.LastIndexOf(string value) под капотом этот метод использует перегрузку с параметром CurrentCulture.

IndexOfAny и LastIndexOfAny

🟢Все методы работают одинаково быстро.

🖥 Сравнение string и Span. Часть 2. Trim, TrimStart, TrimEnd, CompareTo, Equals

English version is below.

Продолжаю сравнивать методы string и ReadOnlySpan<char>.

По результатам бенчмарка, методы Trim, TrimStart, TrimEnd в ReadOnlySpan<char> в среднем на 40% быстрее, чем в string. Ничего удивительного нет, т.к. использование этих же методов в string приводит к аллокациям памяти.

Метод string.CompareTo во всех случаях быстрее, правда незначительно. При использовании StringComparison.Ordinal эта разница достигает 88%.

Метод Equals в ReadOnlySpan<char> демонстрирует сопоставимую производительность с string при использовании CurrentCulture, InvariantCulture и других типах сравнения. Однако при использовании OrdinalIgnoreCase string быстрее ~25%.

👩‍💻 Код и результаты

String and Span comparison. Part 2. Trim, TrimStart, TrimEnd, CompareTo, Equals

I continue to compare the string and ReadOnlySpan<char> methods.

According to the benchmark results, Trim, TrimStart, and TrimEnd methods in ReadOnlySpan<char> are, on average, 40% faster than in string. This is not surprising, because using these methods in string causes memory allocations.

CompareTo is faster in string in all cases, although only slightly. But when using StringComparison.Ordinal, the difference reaches 88%.

Equals in ReadOnlySpan<char> shows comparable performance to string when using all comparison types except OrdinalIgnoreCase. In this case string is ~25% faster.

👩‍💻 Code and results

🖥 Сравнение string и Span. Часть 3. CopyTo, Split, Replace, ToLower, ToUpper

English version is below.

Продолжаю сравнивать методы string и ReadOnlySpan<char>.

Метод Split работает на 46% – 64% быстрее в ReadOnlySpan<char>. Использование метода MemoryExtensions.Split позволяет работать со структурой Range, массив которых можно создать в стеке:

Span<Range> ranges = stackalloc Range[str.Length];
str.AsSpan().Split(ranges, separator);

Методы ToLower и ToUpper также работают на 43% – 45% быстрее в ReadOnlySpan<char>. И опять же, это преимущество достигается за счёт отсутствия аллокаций в куче:

Span<char> destination = stackalloc char[str.Length];
str.AsSpan().ToLower(destination, CultureInfo.InvariantCulture);

Производительность метода CopyTo практически одинаковая — разница составляет всего 3% в пользу ReadOnlySpan. Однако важно учитывать, что массив, в который будет скопирована строка, должен быть заранее проинициализирован. Это можно сделать как в стеке с помощью stackalloc, так и в куче с помощью оператора new, что может влиять на производительность:

// Вариант 1
Span<char> destination = new char[str.Length];
str.CopyTo(destination);

// Вариант 2
Span<char> destination = stackalloc char[str.Length];
str.CopyTo(destination);

Метод Replace в ReadOnlySpan<char> работает на 75% быстрее, чем в string. Это очевидно связано с отсутствием аллокаций при использовании ReadOnlySpan — результат замены сохраняется в отдельный Span:

Span<char> destination = stackalloc char[str.Length];
str.AsSpan().Replace(destination, oldChar, newChar);

👩‍💻 Код и результаты

🖥 String and Span comparison. Part 3. CopyTo, Split, Replace, ToLower, ToUpper

I continue to compare the string and ReadOnlySpan<char> methods.

The Split method works 46% – 64% faster with ReadOnlySpan<char>. Using the MemoryExtensions.Split method allows to work with Range. An array of ranges can be created on the stack:

Span<Range> ranges = stackalloc Range[str.Length];
str.AsSpan().Split(ranges, separator);

The ToLower and ToUpper methods are also 43% – 45% faster with ReadOnlySpan<char>. Again, this comes from avoiding allocations on a heap:

Span<char> destination = stackalloc char[str.Length];
str.AsSpan().ToLower(destination, CultureInfo.InvariantCulture);

Method CopyTo has almost the same performance — ReadOnlySpan is only 3% faster. However, it's important to note that the destination array should be pre-initialized. This can be done either on the stack using stackalloc or on the heap using the new operator, which can affect performance:

// Option 1
Span<char> destination = new char[str.Length];
str.CopyTo(destination);

// Option 2
Span<char> destination = stackalloc char[str.Length];
str.CopyTo(destination);

Method Replace in ReadOnlySpan<char> is 75% faster than in string. Again, this is due to the absence of heap allocations when using ReadOnlySpan:

Span<char> destination = stackalloc char[str.Length];
str.AsSpan().Replace(destination, oldChar, newChar);

👩‍💻 Code and results

👩‍💻 Пишем производительный C# код при работе с коллекциями

Публикую следующую часть статьи про производительность коллекций. Сегодня про Enumerator.

---

Предположим, у нас есть массив _transactionsArray и список _transactionsList. Сама транзакция выглядит следующим образом:

public record class Transaction(
    Guid Id, 
    int Amount, 
    string Denoscription);

Существует множество способов пройтись по двум вышеупомянутым коллекциям:

// Индексатор массива
var sum = 0;
for (var i = 0; i < _transactionsArray.List; i++) {
    sum += _transactionsArray[i].Amount;
}

// Индексатор списка
var sum = 0;
for (var i = 0; i < _transactionsList.Count; i++) {
    sum += _transactionsList[i].Amount;
}

// Энумератор IEnumerable<T>
var sum = 0;
var collection = (IEnumerable<T>)_transactionsArray;
foreach (var item in collection) {
    sum += item.Amount;
}

var sum = 0;
var collection = (IEnumerable<T>)_transactionsList;
foreach (var item in collection) {
    sum += item.Amount;
}

// Энумератор List<T>
var sum = 0;
foreach (var item in _transactionsList) {
    sum += item.Amount;
}

Один из этих способов аллоцирует больше памяти, чем остальные – это приведение _transactionsList к IEnumerable<T>. Причина кроется в реализации энумератора для списков. У типа List<T> есть собственный энумератор-структура.

Если использовать foreach с типом List<T>, то проблем не возникает. Компилятор C# сгенерирует код, который будет использовать эту структуру напрямую.

// Исходный код
var nums= new List<int>();
var sum = 0;
foreach (n in nums) sum +=n;

// Код после компиляции
var nums = new List<int>();
var num = 0;
List<int>.Enumerator enumerator = 
    nums.GetEnumerator();
while (enumerator.MoveNext()) {
    num += enumerator.Current;
}

Но если привести List<T>, например, к IList<T> или IReadOnlyList<T>, т.е. к любому интерфейсу, реализующему IEnumerable<T>, то произойдёт неявная упаковка List<T>.Enumerator. Это происходит из-за того, что IEnumerable<T>.GetEnumerator() возвращает интерфейс IEnumerator<T>.

// Исходный код
var nums = new List<int>();
var collection = (IEnumerable<int>) nums;
var sum = 0;
foreach (n in collection) sum +=n;

// Код после компиляции
var nums = new List<int>();
var collection = ((IEnumerable<int>)nums);
var num = 0;
IEnumerator<int>.Enumerator enumerator = 
    // упаковка
    collection.GetEnumerator();
while (enumerator.MoveNext()) {
    num += enumerator.Current;
}

Аналогичный подход с энумераторами также встречается и других коллекциях: LinkedList<T>, Stack<T>, Queue<T> и т.д. Исключением являются, например, массивы.

Насколько упаковка влияет на производительность можно понять из графиков. Бенчмарк 100 раз прошёлся по каждой из коллекции. На первом графике ось Y отображает проценты от бенчмарка с массивом, а на втором — миллисекунды. Шкала оси X в обоих случаях логарифмическая.

Если говорить об абсолютных значениях, разница не так велика — десятки миллисекунд для коллекций размером 100 000 элементов и более. Наибольшее коварство такое поведение представляет, когда у вас много небольших коллекций. Я в своей практике встречал проблему, когда упаковка энумератора приводила к аллокациям десятков и сотен мегабайт. Это было большое дерево директорий, а доступ к дочерним директориям был только через IReadOnlyList<T>.