В оптимизации процедуры развертки фазы для микроскопа ч дошел до предела, который позволяет c# без использования магии: проигрыш в 2.7 раз относительно чистого с.

Для достижения этого результата мне пришлось убрать из постоянно использующегося кода конструкторы примитивных объектов для хранения данных. Отказ от создания объектов для хранения промежуточной информации в пользу их обновления дал почти двукратный (!) прирост производительности, сократив разрыв отставание от чистого С с 5 раз.

С чем связано сохранение такого разброса затрудняюсь сказать, чисто в теории скорости должны быть намного ближе. Языки программирования можно разделить на компилируемые и интерпретируемые. Компилируемые при сборке выдают сразу файл, напрямую исполняемый в ОС. В интерпретируемых языках код компилируется в набор команд для виртуальной машины, которая берет на себя взаимодействие с железом. Именно таким языком является C#.

Первый запуск кода занимает относительно много времени, последующие - в теории - столько же, сколько занимал бы при запуске аналога на компилируемом языке. Но, видимо, дьявол оказался в мелочах.

С# в любом случае несет какие-то накладные расходы на функции, взятые из CLR (виртуальная машина платформы .Net). Кроме того, в C почти все манипуляции в коде осуществляются на уровне указателей.

Навигация по двумерному массиву с изображением также осуществляется с помощью арифметики указателей. Видимо сочетание этих факторов, а также более прямых рук авторов реализации алгоритма развертки фазы на C и дают такое преимущество.

У меня остается узкое место - сортировка здоровенного одномерного массива (примерно 4 млн элементов). Изначально, как в реализации на С, так и в методе, предлагаемым в для сортировки в С# используется алгоритм быстрой сортировки (quicksort), как один из наиболее шустрых. У меня на сортировку массива уходит до 40% всего времени.

Пришло время заменить его на хорошо распараллеливаемый алгоритм сортировки слиянием и начать распараллеливать вообще всё.

#csharp #диссер

Начал оптимизировать сортировку в своем диссертационном проекте, всплыла прекрасная иллюстрация такого понятия как вычислительная сложность алгоритма.

Тестовый массив - 4 миллиона элементов (классов, содержащих поле типа double, по которому и осуществляется сортировка).

Проверил четыре варианта сортировки массива:
1. Стандартный метод Array.Sort, предоставляемый c# из коробки (под капотом там quicksort O(n*log(n)), как писал выше). Результат - 2.2 секунды
2. Нагугленная реализация quicksort O(n*log(n)) для c#. Результат - 2.7 секунды
3. Нагугленная реализация сортировки вставками O(n^2) . Результат - бесконечность, за 45 минут не отсортировалась даже половина массива, я остановил тест.
4. Нагугленная реализация сортировки слиянием mergesort O(n*log(n)). Результат 4.08 секунды.

Уже из этих цифр видно различия в вычислительной сложности: n^2 по сравнению с n*log(n) начинает проигрывать просто феерически. И да, такой массив - это обыденность: по объему данных это примерно две картинки в full hd.

Выигрыш метода Array.Sort у простой реализации быстрой сортировки "в лоб" заслуживает отдельного внимания, обязательно залезу в исходный код .Net Core и расскажу чем он отличается.

#csharp #диссер

Продолжаю про оптимизацию сортировки массива в диссертационном проекте.

Более-менее успешно распараллелил сортировку: использовал нечто гибридное. Массив разделяется на несколько частей, каждая сортируется параллельно, после чего сливаются во едино функцией Merge из реализации сортировки слиянием из прошлого поста (п. 4).

Результаты меня несколько огорчили. Рост про производительности бесспорно есть. Время обработки сократилось с 2.2 секунд до 1.5 с использованием двух потоков. При этом, с ростом числа потоков, скорость растет на какие-то смешные значения, а то и падает за счёт того, что приходится ждать запаздывающие потоки.

Фантастический сюрприз поджидал меня далее. Я сортирую массив объектов по одному из полей с типом double. При этом используется стандартный инструмент для сравнения пользовательских типов данных внутри метода Array.Sort - реализация интерфейса IComparer. По сути, в сортировку передается функция, с помощью которой можно сравнивать экземпляры сортируемых классов.

Я решил посмотреть, сколько будет сортироваться массив моего размера (4млн) double. 0.08 секунды, почти в 25(!) раз быстрее. Теперь думаю, как по-ловчее перевести алгоритм на такую сортировку.

#csharp

Небольшое уточнение к прошлому посту. В мои замеры прокралась ошибка, на самом деле среднее время сортировки массива из double-ов составляет 0.37 секунды.

Несмотря на это, шестикратная разница в скорости - это тоже неплохо.

Кроме того, у метода Array.Sort есть перегрузка, которая предлагает сортировать один массив относительно другого. Замерял её производительность, вынеся поле, по которому сортирую в отдельный массив. Результат - 1.1 секунды. Т.е. простой вынос поля, по которому осуществляется сортировка в отдельный массив и отказ от использования реализации IComparer там, где это не нужно, уже дает двукратный рост производительности.

Интересно, получится ли выдавить бОльший рост какими-либо другими манипуляциями?

#csharp

Итого подошла к концу эпопея с оптимизацией реализации алгоритма развертки фазы, написанного на с#. В качестве эталона используется реализация на чистом С, скопированная из репозитория библиотеки sklearn-image.

Итог оптимизации: производительность на С и С# практически сравнялась, теперь я отстаю примерно на
20% вместо 400% в начале пути.

Произведенные манипуляции:
1. Обновление классов вместо их пересоздания. Подробнее - тут

2. Использование встраиваемых функций. Встраивание - процедура, обратная разбиению кода на отдельные функции для повышения читаемости. Такие функции я пометил как встраиваемые (inline), чтобы компилятор вставил их содержимое в байт-код вместо простого вызова. Подробнее - тут, 7й раздел.

3. Правильное использование сортировки. Узким местом в алгоритме являлась сортировка массива, размером равного удвоенному числу пикселей.

После долгих экспериментов с сортировкой, я сделал две вещи:
А) вынес поле сортируемых классов в отдельных массив и использовал сорировку "по ключу" - т.е. сортировал один массив по данным из другого.
Б) Раскопав код коробочного метода сортировки я обнаружил, что он отлично работает на массивах с повторяющимися значениями. Потому я округлил используемый мной параметр до третьего знака (задача позволяет), в результате чего выгадал ещё процентов 30 скорости сортировки. Про эту реализацию Быстрой сортировки напишу отдельно.

Итого, я разогнал FPS своего приложения до 8 на 2 мега пикселях. Немного поколдовать над интеграцией с Arduino и им можно пользоваться. SIMD и другие оптимизационные шаманства оказались неприменимы, единственное, откуда я могу получить рост производительности - распараллеливание.

Я уже получил levelup и кучу экспиренса, но задача - преобразование картинки в реальном времени - не решена. Я алгоритм конечно распараллелю, но появилась новая вводная - 5 мегапикселей, потому следующий большой пункт назначения - CUDA.

#csharp #диссер

Обещанный пост о вариации быстрой сортировки, использующейся в c# в коробочном методе Array.Sort.

Суть алгоритма заключается в следующем: Берется опорный элемент, примерно по середине массива. Элементы, большие него помещаются справа от него, меньшие - слева.

Над половинками рекурсивно проводится та же операция, до тех пор, пока массив не отсортируется.

Нашел реализацию в репозитории Майкрософт с прошлой версией .Net. Ниже прикладываю вырванный оттуда рабочий кусок кода.

На первый взгляд он выглядит диковато: каскад из двух операторов do... while и двух простых while являются антитезой понятия "читаемый и понятный код".

При этом, вырванный кусок обходит все другие найденные и написанные мной реализации сортировок в несколько раз, уступая только коробочному решению (на 40%), в основе которого и лежит (видимо обвешан какими-то оптимизациями на этапе компиляции).

Программисты Microsoft таки едят хлеб недаром.

#csharp

Хотел бы внести корректировку к ранее опубликованными цифрам по FPS в моем приложении. У меня была ошибка в счётчике кадров в секунду.

Реальные значения FPS сейчас что с использованием С, что с использованием новонаписанного кода на С# колеблется в диапазоне от 1.05 до 1.25 кадров в секунду.

Сортировка на массиве случайных чисел выполняется около секунды + выполняется несколько других операций. То есть FPS 1 и выше кажется невозможным в теории. В реальности массив у меня частично отсортированный, потому сортировка занимает 0.2-0.3с, что и делает возможным обрабатывать один кадр в секунду.

Кроме того, целевое значение FPS у меня не 25, а 6-8, т.к. одно изображение у меня получается из 3 или 4 кадров с камеры.

Перепроверил и остальные цифры, публикуемые мной в канале, там все четко.

#csharp #диссер

Наткнулся сегодня на интересную особенность работы .Net на разных процессорах.

Один из самых простых способов параллелизовать операцию над последовательностью - использовать библиотеку Parallel, метод For. Операция будет выполнена, как и в обычном for, но параллельно, в разных потоках. Балансировкой нагрузки занимается сама CLR.

У меня было:
1. Операция над массивом из 4млн элементов, с глубоким путешествием по полям классов, составляющих массив. То есть что-то типа elements[i].inner_field.field.value. Выпоняю сложение и округление.

2. Три процессора:
Core i3 (3.6 гГц, 4 ядра)
AMD Ryzen (3.6 гГц, 6 ядер)
Core i9 (8 ядер, 3.6 гГц)

Результаты при параллельном запуске:
i3: 0.08с
AMD: 0.4с
i9: 0.03с

При запуске в один поток, на всех процессорах время примерно одинаковое - около 0.35 с.

Что за чертовщина, с чего AMD проигрывает i3 в 5 раз - не понятно. Буду искать объяснение или решение (отличное от "забить"), если найду - поделюсь.

#csharp

По микроскопу появилась новая вводная: дополнительно реализовать метод вычисления фазового изображения по одной картинке с помощью фильтрации его двумерного Фурье-образа - методом Гильберта.

В поисках готовой реализации двумерного фурье преобразования, я нашел проект AForge - реализации различного матана на c#. Проект, хоть и написан по какую-то допотопную версию .Net крут: вырванный копипастой кусок, относящийся с Фурье преобразованию, просто взял и заработал. Время отработки на картинке 1024х2048 - около 1 секунды. Вырванная реализация работает только на картинках с размером, кратным степени двойки.

Теперь мне предстоит переварить копипасту: разобраться в принципе работы алгоритма, выкинуть лишнее, оптимизировать оставшееся. Появилась идея со временем выкинуть весь матан, как на c#, так и на CUDA в отдельный проект и в NuGet пакет (стандартное средство распространения готовых модулей и библиотек для c#) в свободный доступ, глядишь кому пригодится.

Понятного для дебилов описания принципа работы Быстрого Фурье преобразования я с ходу не нагуглил (но код готовой реализации несколько прояснил ситуацию). Нашел фундаментальную переводную книгу 1989 год - Быстрые алгоритмы цифровой обработки сигналов, автор Блейхут Р., начинаю читать. В посте ниже выложу саму книгу.

Из уже прочитанного в коде и книге понятно: либо я использую картинку размерности степени двойки (возможно какими-то костылями подгоняя ее по размеру), либо погружаюсь в мир боли и страданий, делая свои реализации, пытаясь выйти на приемлимую производительность.

Использование массива с размерами, кратными степени двойки - один из основных читов, которые используются, чтобы получить результат максимально быстро. Что интересно - в одной из научных статей, посвященных фазовой микроскопии, все тесты алгоритмов, основанных на FFT2 проводились на картинках размером 1024x2048.

#диссер #csharp

Палантир. Часть 18. Оптимизация базы данных.
#палантир@eshu_coding

Подключения к базе данных устанавливаются относительно продолжительное время, потому принято пользоваться ими длительное время. Мои боты, которых я писал летом 2020 висят на постоянных подключениях иногда по нескольку месяцев и проблем не было.

Но как через подключения потекли значительные объемы данных, проблемы резко возникли. А с учётом того, что в поисковике ожидается много пользователей, подключений используется тоже много (в среднем 200-300, с максимальным лимитом в 1500).

Проблему утечки памяти из прошлого поста я решил переработкой менеджера подключений. Некоторое время назад я написал класс, который ведёт учёт всех подключений к базе (чтобы не выйти за установленное максимальное число), держит несколько готовых подключений в горячем резерве и закрывает те, которые больше не нужны. Добавил к нему функцию закрытия подключений, которые живут и используются слишком долго и в которых мог накопиться мусор.

В принципе, в ConnectionString, строке, которой описывается подключение к PostgreSQL, есть группа параметров, отвечающих за тот самый пул подключений, который я сам наколхозил. И время жизни соединения там тоже можно задать. Но соединение там рвется только при неактивности в течение N секунд, а мне нужен костыль, ограничивающий время жизни вне зависимости от активности использования.

По хорошему, хранением соединений должна заниматься библиотека, с помощью которой я цепляюсь к базе данных - Npgsql. Но вот функции горячего резерва N подключений и безболезненного ограничения максимального числа в ней нет: мой менеджер подключений ждёт пока освободится слот, а Npgsql кидает исключение, что мне в этом проекте неудобно.

В итоге я пришел к следующим настройкам пула: 200 подключений в резерве, время жизни подключения 30 секунд, проверка и обслуживание пула раз в 3 секунды.

#csharp

Познакомился с работой с координатами на карте. Широта и долгота, x и y, логично ведь? Север на карте - сверху, вертикаль - это y. А горизонталь - x.

А вот стандартная шарповая библиотека для работы с пространством считает иначе, придется с этим жить.

#csharp

Совершил третий подход к библиотеке Quartz - инструменту для управления фоновыми задачами в шарповом сервисе. И таки познал его дзен. Первый раз я смотрел его джуном. У меня закипели мозги и я в ужасе закрыл его. Второй раз я уже был мидддом. Подумал: прикольно, но избыточно. И вот третий подход.

Предположим у нас есть сервис. Раз в секунду он совершает какой-то запрос. Повесили вечный цикл/таймер и живём дальше.

Спустя какое-то время нам потребовалось делать серию запросов куда-то раз в 5 минут. Мы все ещё живём на таймерах.

Добавилась необходимость содержать пару локальных кешей, обновляя/чистя их по расписанию. У нас таймеры, нам ок.

Потом добавилась ещё пара серий запросов с разной периодичностью. На таймерах/бесконечных циклах ещё живётся приемлимо, но уже хочется конфигурировать наш зверинец с помощью Cron.

А потом добавилась длинная и тяжёлая задача задач, которая должна запускаться в 13:13 по пятницам 13 го. Длится она около 30 минут. Мы уже очень хотим красивое управление периодами с помощью Cron, но наваяли костылей и поехали дальше.

И тут выясняется, что одновременное выполнение задачи задач и второй из серий запросов рушит внешний сервис. Разрулить можно, но добро пожаловать в ад из семафоров! В тот момент, когда мы закоммитили этот ужас, наш проект превращается в махровое легаси, место которому на помойке в очереди на переписывание.

Чтобы не скатываться в такое есть специализированный инструмент, упомянутый выше. Периодичность выполнения можно конфигурировать как передавая Cron - выражение, так и единицы времени/интервалы. Можно настроить приоритеты задач, общее число доступных потоков и много чего ещё.

Но больше всего мне понравилась возможность сгруппировать задачи. Задача задач помечается как относящаяся к одной группе с теми, с кем совместно она кладет внешний сервис. И вот, в час Х она просто говорит одной строкой своей группе: поспите, пока я работаю. И они просто спят. А когда она оканчивает свою работу ещё одной строкой говорит: проснитесь!

Кроме Quartz есть ещё библиотека Hangfire, но мне она пока кажется избыточной, как Quartz когда-то:)

#кодинг
#csharp

Наткнулся на очень интересный инструмент для махинаций с кодом на c# на стадии пост-компиляции: fody.

Инструмент по определенным правилам в скомпилированный код может подсунуть дополнительного функционала, например, во все отмеченные методы влепить логирование. Выглядит очень интересно, хоть пока и кажется близким к бесполезному.

#кодинг
#csharp

#dotnext, день 2, доклад 1.

Экономия памяти в .Net.

Известно, что приложения на java/c# съедают память столько, сколько им дадут. Но если заморочиться - можно сократить потребление.

В докладе занимались загрузкой файлов со средним размером ~123 Мб. В среднем на загрузку такого файла уходило ~280 Мб памяти.

Путем разных непристойных действий с байтами автор ужал потребление памяти до ~2.7 Мб, т.е. в 100 раз. И даже не особо потерял в читаемости кода.

Во основном использовалось два подхода:
1. Пулинг объектов
2. Выделение памяти на стеке вместо кучи

В c# есть встроенный пул массивов, которые можно использовать как буферные объекты, не создавая новые и не забивая память новосоздаваемыми одноразовыми массивами.

А если таки надо создавать буферные короткоживущие объекты - можно попробовать разместить их на стеке. Использовать структуру. Или вообще аллоцировать кусочек стека и использовать его по своему усмотрению (главное не переусердствовать и не завалить все приложение со Stack Overflow Exception).

Список колдунств, применённых автором, просто чтобы не забыть:
1. stackalloc
2. ArrayPool
3. readonly ref struct
4. ValueStringBuilder (вытащенный внутренний класс из недр рантайма c#, базирующийся на стеке билдер строк).
5. TryFormat

Ещё была важная мысль - использовать бенчмарки в докере, чтобы сравнивать как работает код в целевой ОС, а не на Винде, где идёт разработка.

#csharp
#conf

Как обычно ставят нугет пакеты? Зашёл в менеджер, выбрал версию, поставил, побежал дальше писать код.

Предположим, наша инфраструктура растет, у нас появляются собственные нугет пакеты, мы их активно используем, чтобы не копипастить код и не впадать в микросервисное безумие.

Мы продолжаем расти и развиваться. Часть наших пакетов начинает ссылаться на другие наши пакеты. Которые ссылаются на другие наши пакеты. Которые ссылаются на другие наши пакеты. Ой, рекурсия. На самом деле, циклическую зависимость создать никто не даст, но деревья зависимостей могут быть очень развесистыми.

И в какой-то момент ссылки начинают пересекаться. И если мы работаем обычным образом - как описано в начале поста - рано или поздно два установленных пакета начнут ссылаться на разные версии одного и того же пакета. И тут мы попадаем в ад конфликтующих зависимостей, из которого выход только один: в окно. Впрочем, в ад можно попасть даже если два проекта в решении ссылаются на разные версии одного и того же пакета, без всяких страшных древ зависимостей.

Лучше подобные проблемы не решать, а предотвращать, не допуская даже саму возможность появления.

Во-первых, продумать структуру решения. В идеале - нарисовать схему взаимных зависимостей проектов и установленных в них пакетов. И идеале, один пакет в решении должен устанавливаться один раз. Если мы ставим пакет 1 и пакет 2, зависящий от пакета 1, прямую установку пакета 1 мы тоже можем удалить.

Во-вторых, можно указать не конкретную версию пакета, а диапазон, например [1.0.0,3.0.0). В этот интервал попадут все пакеты, имеющие версию 1 или 2. Если у другого пакета будет [1.2.0,2.5.0) - при сборке будет подобрана версия, удовлетворяющая обоим интервалам условий.

В-третьих, версии пакетов можно выносить в константы и подтягивать из .props файлов. Предположим, часть функционала у нас вынесена в пакеты, имеющие в названии "Common", например Common.Math, Common.StringParsing, Common.HttpHelper. Мы можем ввести внутреннее правило - двигать версии этих пакетов только вместе (как на уровне регламента, так и в CI/CD). В .props мы можем определить параметр ${CommonPackageVersion}, после чего в проекте согласованно выставлять все версии Common пакетов через .props файл, указывая в .csproj файлах вместо привычных численных версий пакетов значение ${CommonPackageVersion}

P.S. больше информации по нугет пакетам можно посмотреть в официальной документации.

#csharp

Вышло очень хорошее описание потокобезопасных коллекций в c#.

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

#csharp

Познал дзен написания автотестов в c#. Тесты я пишу уже довольно давно и помногу, но во основном функциональные/интеграционные, закрывающие функционал проекта в целом. При этом зависел я обычно только от объектов инфраструктуры: баз данных, брокеров сообщений и т.д. Модульные тесты тоже писал, но только на места с неочевидной сложной логикой, которая не помещается в голове.

Перенесемся в мир кровавого энтерпрайза. Представим ситуацию, когда наш сервис ходит по сети более чем в 10 других микросервисов. Куда ходят эти 10 микросервисов чтобы собрать информацию - представить страшно.

Поднимать все это добро каждый раз, когда приспичит проверить бизнес логику - не очень удобно даже в светлую эпоху контейнеризации. Тут на помощь нам приходят моки: обносим источник данных интерфейсом, а дальше в тестах в тестируемый класс с бизнес логикой подсовываем фейковую реализацию интерфейса.

До недавнего времени я пилил эту реализацию сам, но тут проникся двумя инструментами - NSubstitute и Autofixture. Первый позволяет создавать фейковые реализации, второй - инициализировать инстансы классов для возвратов с заполненными полями.

У NSubstitute понравилась возможность легко задавать конкретные кейсы из пар запрос - ответ, очень удобно и никакой логики внутри фейка самому писать (и потом поддерживать) не надо.

Autofixture мне не казалось чем-то нужным, до тех пор, пока мне не пришлось тестировать проброс информации из глубинных слоев наверх, с возвращаемой моделью (в сумме с вложенными классами) в пару тысяч строк. Говоришь: мне нужен объект, поля id, name, userid должны иметь заданные значения. Остальные - заполнятся по усмотрению библиотеки чем-то не-дефолтным. Раз - и объект для теста готов, без бесконечной лапши с инициализацией полей руками.

#csharp
#tests

Продолжая тему модульных тестов в c#. Вляпался в занятную ситуацию с Autofixture. Строки и числа Autofixture заполняет случайными значениями, меняющимися от запуска тестов к запуску. А вот тот момент, что значения булевых полей меняются по другим законам я как-то упустил.

Удаляю я неиспользуемое поле в одном из классов, экземпляры которых я создаю с помощью Autofixture - и тут у меня перестает проходить несколько тестов, при том покрывающих вообще случайные места в проекте. А переименование поля (неиспользуемого) такого эффекта не оказывает.

Первое на что я подумал - что-то где-то закешировалось у меня на компе и тесты заглючили, так иногда бывает. Следующий час прошел в попытках провести экзорцизм над проектом. Не помогло, зато я выяснил что проблема воспроизводится и в пайплайне CI/CD на серверах. Приплыли.

В итоге, оказалось, что генерируемые с помощью Autofixture значения булевых полей не меняются от запуска к запуску тестов, но являются функцией от набора полей в классе. Убрали или добавили поле - значения поехали.

А ошибки полезли из-за того, что я их допустил при написании тестов. Сочетание сгенерированных булевых флагов делало их незаметными, но минус на минус перестал давать плюс и тайное стало явным.

#csharp
#tests
#Autofixture

Вообще, для пишущих хранимые процедуры на не-SQL, есть отдельный котел в аду.

Но новость очень приятная.

#postgresql
#csharp