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

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