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

Тестовый массив - 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