В прошлое воскресенье на LeetCode в качестве челленджа была задачка Largest Local Values in a Matrix. Несмотря на уровень Easy, она демонстрирует важность последовательного доступа к данным.
Суть задачи
Дана матрица MxM. Нужно найти максимальные значения во всех матрицах 3x3, которые получаются из исходной матрицы. Решение от LeetCode реализовано так (рис. 1):
1. Берётся матрица 3x3.
2. Последовательно обходятся элементы матрицы в поисках максимума.
3. goto п.1.
Что не так с решением?
Например, что столбцы [9, 6, 2] и [8, 2, 6] относятся к матрицам 0 и 1, и будут обработаны несколько раз. Оптимальный алгоритм вернёт правильное решение, обработав каждый столбец и строку лишь 1 раз. Реализовать такой алгоритм можно 2 способами:
1. Обход по столбцам слева направо, сверху вниз (рис. 2).
2. Обход по строкам сверху вниз, слева направо.
Что быстрее? Кажется, что обход по столбцам. Да, но не всегда.
Причём тут последовательный доступ и кэш ЦПУ?
Реализация кэша ЦПУ основана на концепции локальности данных. При обращении к данным высока вероятность, что:
1. Вскоре к данным обратятся снова. Поэтому-то они и сохраняются в кэш.
2. Могут обратиться и к соседним данным. Поэтому кэширование происходит блоками определённого размера (cache line) и в кэш попадают не только запрашиваемые данные, но и соседние байты памяти.
В общем случае, если поведение программы не укладывается в концепцию выше, то производительность снижается. Например, для алгоритма с обходом по строкам, при размере матрицы 2000+ элементов, количество промахов кэша увеличивается многократно (рис. 3), что приводит к ухудшению производительности (рис. 4). Объясняется это непоследовательным доступом. В кэш попадают ненужные даные, ведь используется только 3 элемента из строки.
Но интересно то, что обход по строкам быстрее, если матрица небольшая (рис. 5). В таком случае, в кэш попадает практически вся матрица. А найти max значение 3-х элементов одной строки быстрее, чем 3-х элементов из разных строк.
Please open Telegram to view this post
VIEW IN TELEGRAM
⚡3❤🔥1
Недавно сербский портал N1 выпустил статью о самых высокооплачиваемых профессиях в Сербии. Как вы уже наверное догадались, больше всех зарабатывают в IT — средняя зарплата составляет 200 000 динар или 1707€. Диапазон колеблется от 587€ до 2143€, в зависимости от образования.
Вообще, в Сербии есть сайт HelloWorld, который похож на Хабр Карьеру. Там тоже вакансии, информация об IT-компаниях, отзывы и можно оставить данные о своей зарплате. Я сравнил доходы айтишников в Белграде и Москве на основе информации HelloWorld и Хабр Карьеры. На диаграммах значения после вычета налогов и без учёта премий.
Если смотреть по всем IT-специализациям, то зарплаты младших специалистов в Белграде выше или как минимум не хуже. А вот зарплаты опытных специалистов уступают на 13 – 20%.
Зарплаты разработчиков ПО тоже отличаются. В Белграде зарплаты интернов и джунов выше на 72% и 32% соответственно. Зарплаты мидлов и сеньоров ниже на 4% и 11%. Разница уже не такая большая.
Please open Telegram to view this post
VIEW IN TELEGRAM
Please open Telegram to view this post
VIEW IN TELEGRAM
👍3❤1
Очень короткий пост о том, как начать отслеживать покрытие кода тестами на примере MSTest.
1. Устанавливаем расширение Coverage Gutters для VS Code. Пользователи vim и neovim простите, сегодня пост не для вас.
2. Переходим в проект с тестами и добавляем библиотеку coverlet.msbuild.
dotnet add package coverlet.msbuild --version 6.0.2
3. Выполняем команду.
dotnet test /p:CollectCoverage=true /p:CoverletOutputFormat=cobertura
4. Смотрим отчёт.
Calculating coverage result...
Generating report '..\coverage.cobertura.xml'
+-------------+------+--------+--------+
| Module | Line | Branch | Method |
+-------------+------+--------+--------+
| SomeProject | 100% | 100% | 100% |
+-------------+------+--------+--------+
+---------+------+--------+--------+
| | Line | Branch | Method |
+---------+------+--------+--------+
| Total | 100% | 100% | 100% |
+---------+------+--------+--------+
| Average | 100% | 100% | 100% |
+---------+------+--------+--------+
5. Жмём кнопку Watch в тулбаре VS Code (рис. 1) и изучаем покрытые и непокрытые участки кода. Они подсвечиваются зелёным и красным соответственно (рис. 2).
Поздравляю, вы великолепны!
При необходимости, результаты отчёта можно прикрутить в CI/CD в GitLab и отслеживать насколько хорошо покрыт тестами новый код из мердж реквестов (рис. 3).
Please open Telegram to view this post
VIEW IN TELEGRAM
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥3
Прокаченные params в C# 13
На днях Microsoft анонсировала новую версию C#. В ней есть фича, касающаяся
Ключевое слово
Но в новой версии C# можно использовать
В итоге, в теле метода
Но также стоит учесть, что использование
На днях Microsoft анонсировала новую версию C#. В ней есть фича, касающаяся
params. Если вы не в курсе, что это такое, то вот простой пример:public void SomeMethod() {
ArrayParams(1);
ArrayParams(1, 2, 3);
}
public void ArrayParams(params int[] values) {
// some work
}Ключевое слово
params – это синтаксический сахар, позволяющий вызывать метод ArrayParams с любым количеством параметров. Но за сахар надо платить, в данном случае – ненужными аллокациями. После компиляции в методе SomeMethod на каждый вызов ArrayParams создаётся экземпляр массива int[].public void SomeMethod() {
int[] array = new int[1]; // аллокация 1
array[0] = 1;
ArrayParams(array);
int[] array2 = new int[3]; // аллокация 2
RuntimeHelpers.InitializeArray(array2, (RuntimeFieldHandle)/*OpCode not supported: LdMemberToken*/);
ArrayParams(array2);
}Но в новой версии C# можно использовать
Span<T> и ReadOnlySpan<T> вместо массива.public void SomeMethod() {
SpanParams(1);
SpanParams(1, 2, 3);
}
public void SpanParams(params ReadOnlySpan<int> values) {
// some work
}В итоге, в теле метода
SomeMethod аллокаций уже не будет. То есть, если вы любите писать высокопроизводительный код, то params вместе с ReadOnlySpan<T> — ваш бро.public void SomeMethod() {
SpanParams(RuntimeHelpers.CreateSpan<int>((RuntimeFieldHandle)/*OpCode not supported: LdMemberToken*/));
SpanParams(RuntimeHelpers.CreateSpan<int>((RuntimeFieldHandle)/*OpCode not supported: LdMemberToken*/));
}Но также стоит учесть, что использование
Span<T> накладывает ограничения – метод нельзя сделать асинхронным.// valid
public async Task ArrayParams(params int[] values) {
// some work
}
// error CS4012: Parameters or locals of type 'ReadOnlySpan<int>'
// cannot be declared in async methods or async lambda expressions.
public async Task SpanParams(params ReadOnlySpan<int> values) {
// some work
}
🆒6
Вопрос к C# разработчикам. В какой IDE вы больше всего пишете код на C#?
Final Results
48%
10%
42%
Пишет ли кто-нибудь, например, кастомные сниппеты кода, кроме меня? Я их создаю, когда замечаю, что пишу много boilerplate-кода. К примеру, для тестов у меня есть 4 сниппета:
- test-method (скрин 1);
- test-data-method;
- test-data;
- test-class.
Другой пример: часто добавляю required init-only свойства в классы кастомным сниппетом propreq (скрин 2). В самом популярном расширении для C# таких сниппетов нет (скрин 3).
Собственно, вопрос к тем, кто работает с Visual Studio и Rider: занимаетесь ли вы таким задротством или там уже всё «из коробки», и я зря страдаю?
P.S.
P.P.S.
Please open Telegram to view this post
VIEW IN TELEGRAM
Please open Telegram to view this post
VIEW IN TELEGRAM
🆒4
Начал готовить материал для новой статьи про производительность FrozenDictionary
Для тех, кто не в курсе, что такое FrozenDictionary, – это новая read-only generic-коллекция, которая появились в .NET 8. Его особенностью является улучшенная производительность на чтение, по сравнению с обычными коллекциями.
Что уже нашёл интересного:
1. FrozenDictionary – это абстрактный класс. Его конкретная реализация зависит от исходного словаря. Например, от типа ключа (значимый тип, string, int) или размера коллекции.
2. Некоторые реализации «замороженного» словаря вообще не содержат хэш-таблицы. Вместо этого для поиска значения используется линейный поиск через цикл for. Видимо, для некоторых случаев это быстрее, чем считать хэш.
3. Частое используется ключевое слово ref и агрессивный инлайн методов. Возвращение по ссылке позволяет избежать копирования значимых типов. А инлайн позволяет избежать оверхеда, связанного с вызовом методов.
В скором времени узнаем, насколько быстро всё это работает.
Для тех, кто не в курсе, что такое FrozenDictionary, – это новая read-only generic-коллекция, которая появились в .NET 8. Его особенностью является улучшенная производительность на чтение, по сравнению с обычными коллекциями.
Что уже нашёл интересного:
1. FrozenDictionary – это абстрактный класс. Его конкретная реализация зависит от исходного словаря. Например, от типа ключа (значимый тип, string, int) или размера коллекции.
2. Некоторые реализации «замороженного» словаря вообще не содержат хэш-таблицы. Вместо этого для поиска значения используется линейный поиск через цикл for. Видимо, для некоторых случаев это быстрее, чем считать хэш.
3. Частое используется ключевое слово ref и агрессивный инлайн методов. Возвращение по ссылке позволяет избежать копирования значимых типов. А инлайн позволяет избежать оверхеда, связанного с вызовом методов.
В скором времени узнаем, насколько быстро всё это работает.
🆒4
FrozenDictionary в C#: насколько он быстрее Dictionary. Часть 1. Значимые типы.
С релизом .NET 8 в арсенале C# разработчиков появился новый тип коллекций – FrozenDictionary. В серии статей рассмотрим, что представляет собой этот словарь и насколько он быстрее.
FrozenDictionary<TKey, TValue> – это абстрактный класс. У этого класса есть множество реализаций, зависящих от типа ключа, размера коллекции, компаратора. Создаются они при помощи extension-метода ToFrozenDictionary. Стратегия выбора подходящей реализации реализована в статическом классе FrozenDictionary, а именно в методе CreateFromDictionary.
В этой части рассмотрим реализации с ключом значимого типа и с компаратором по умолчанию. Для таких словарей предусмотрены 4 реализации FrozenDictionary:
1. Int32FrozenDictionary.
2. ValueTypeDefaultComparerFrozenDictionary.
3. SmallValueTypeComparableFrozenDictionary.
4. SmallValueTypeDefaultComparerFrozenDictionary.
Int32FrozenDictionary
Для словарей, с количеством элементов больше 10 и ключом типа Int32 используется класс Int32FrozenDictionary. Эта, как и большинство других реализаций
Особенность
Благодаря этому, чтение из
ValueTypeDefaultComparerFrozenDictionary
Для словарей, с количеством элементов больше 10 и ключом любого другого значимого типа, кроме Int32 используется
Чтение из ValueTypeDefaultComparerFrozenDictionary может быть до 80% быстрее (рис. 2).
Продолжение тут 👇
С релизом .NET 8 в арсенале C# разработчиков появился новый тип коллекций – FrozenDictionary. В серии статей рассмотрим, что представляет собой этот словарь и насколько он быстрее.
FrozenDictionary<TKey, TValue> – это абстрактный класс. У этого класса есть множество реализаций, зависящих от типа ключа, размера коллекции, компаратора. Создаются они при помощи extension-метода ToFrozenDictionary. Стратегия выбора подходящей реализации реализована в статическом классе FrozenDictionary, а именно в методе CreateFromDictionary.
В этой части рассмотрим реализации с ключом значимого типа и с компаратором по умолчанию. Для таких словарей предусмотрены 4 реализации FrozenDictionary:
1. Int32FrozenDictionary.
2. ValueTypeDefaultComparerFrozenDictionary.
3. SmallValueTypeComparableFrozenDictionary.
4. SmallValueTypeDefaultComparerFrozenDictionary.
Int32FrozenDictionary
Для словарей, с количеством элементов больше 10 и ключом типа Int32 используется класс Int32FrozenDictionary. Эта, как и большинство других реализаций
FrozenDictionary, основаны на структуре FrozenHashTable. Это основа «замороженных» словарей. Подробнее о ней я расскажу в последней статье о FrozenDictionary. Пока же достаточно знать, что эта структура содержит в себе множество оптимизаций, которые позволяют быстро производить чтение.Особенность
Int32FrozenDictionary в том, что когда тип ключа – целое число, то его хэш равен его значению и коллизии в таком словаре не возможны в принципе. Нельзя, например, добавить 2 элемента с ключом 123 – будет выброшено исключение. Значит при чтении можно пропустить расчёт хэша и использовать значение ключа напрямую. А при создании словаря, например, пропустить удаление дублирующихся хэшей.Благодаря этому, чтение из
Int32FrozenDictionary быстрее на 36% – 42% (рис. 1).ValueTypeDefaultComparerFrozenDictionary
Для словарей, с количеством элементов больше 10 и ключом любого другого значимого типа, кроме Int32 используется
ValueTypeDefaultComparerFrozenDictionary. В этом случае коллизии могут быть, поэтому при чтении необходим расчёт хэша ключа. Но реализация всё так же основана на FrozenHashTable.Чтение из ValueTypeDefaultComparerFrozenDictionary может быть до 80% быстрее (рис. 2).
Продолжение тут 👇
🆒3
Начало тут 👆
SmallValueTypeComparableFrozenDictionary и SmallValueTypeDefaultComparerFrozenDictionary
Строго говоря, два этих класса и не хэш-таблицы вовсе. Поиск значения в них осуществляется не через
При этом,
Такое разделение разработчики .NET объясняют тем, что у встроенных типов 100% реализован интерфейс
К примеру, если бы нам нужно было найти значение для ключа 10 в словаре как на рисунке 3, то без сортировки пришлось бы обойти весь массив
Кроме того, поскольку массив ключей
Реализация
Несмотря на все оптимизации в этих двух классах, результаты бенчмарка не выглядят впечатляющими (рис. 4). Даже то небольшое ускорение, которое может дать
На сегодня всё. Код и результаты бенчмарка лежит тут. В следующей части рассмотрим ссылочные типы. Самое интересное там связано со ключами типа
SmallValueTypeComparableFrozenDictionary и SmallValueTypeDefaultComparerFrozenDictionary
Строго говоря, два этих класса и не хэш-таблицы вовсе. Поиск значения в них осуществляется не через
FrozenHashTable, а простым сравнением элементов в цикле for. Поэтому эти реализации используются, когда в исходном словаре не более 10 элементов. При этом,
SmallValueTypeComparableFrozenDictionary применяется, если тип ключа – это встроенный примитивный значимый тип: int, long, double, enum и т.д. Если же тип ключа, к примеру, record struct, то будет использован тип SmallValueTypeDefaultComparerFrozenDictionary. Такое разделение разработчики .NET объясняют тем, что у встроенных типов 100% реализован интерфейс
IComparable и поэтому можно немного оптимизировать поиск, отсортировав массивы ключей и значений при инициализации словаря:// ctor
_keys = source.Keys.ToArray();
_values = source.Values.ToArray();
Array.Sort(_keys, _values);
_max = _keys[_keys.Length - 1];
К примеру, если бы нам нужно было найти значение для ключа 10 в словаре как на рисунке 3, то без сортировки пришлось бы обойти весь массив
_keys и убедиться, что такого значения в словаре нет. При наличии сортировки достаточно же сравнить с максимальным значением. В данном случае – 9.Кроме того, поскольку массив ключей
_keys отсортирован, можно осуществлять поиск пока искомое значение ключа больше текущего значения _keys[i].// GetValueRefOrNullRefCore method
if (Comparer<TKey>.Default
.Compare(key, _max) <= 0)
{
TKey[] keys = _keys;
for (int i = 0; i < keys.Length; i++)
{
int c = Comparer<TKey>
.Default.Compare(key, keys[i]);
if (c <= 0)
{
if (c == 0)
{
return ref _values[i];
}
break;
}
}
}
return ref Unsafe.NullRef<TValue>();
Реализация
SmallValueTypeDefaultComparerFrozenDictionary похожа на предыдущую, с тем лишь отличием, что в ней не используется сортировка. Соответственно, линейный поиск по массиву ключей _keys будет осуществлён всегда.Несмотря на все оптимизации в этих двух классах, результаты бенчмарка не выглядят впечатляющими (рис. 4). Даже то небольшое ускорение, которое может дать
SmallValueTypeDefaultComparerFrozenDictionary – это всего лишь несколько наносекунд.На сегодня всё. Код и результаты бенчмарка лежит тут. В следующей части рассмотрим ссылочные типы. Самое интересное там связано со ключами типа
string.🆒4
readonly, readonly everywhere
Сегодня с коллегой зашёл разговор про ключевое слово readonly. После разговора, решил вспомнить в C# всё, что содержит в себе readonly и написал такого монстра:
Этот код компилируется и работает. Естественно, в C# ещё много чего с readonly, но, наверно, и этого достаточно, чтобы запутать C# разработчика.
Кстати, сможете объяснить что значит readonly в каждом из случаев?
Сегодня с коллегой зашёл разговор про ключевое слово readonly. После разговора, решил вспомнить в C# всё, что содержит в себе readonly и написал такого монстра:
public readonly struct SomeStruct(int val)
{
public string SomeField { get; init; }
= "Hello, World!";
public readonly int SomeProperty = val;
public readonly IReadOnlyCollection<int> SomeCollection = [];
public readonly ReadOnlySpan<char> SomeMethod() => SomeField;
}
Этот код компилируется и работает. Естественно, в C# ещё много чего с readonly, но, наверно, и этого достаточно, чтобы запутать C# разработчика.
Кстати, сможете объяснить что значит readonly в каждом из случаев?
🆒4