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

Я пишу программу для записи изображений с микроскопа. Цель - иметь возможность писать поток в 2 мегапикселя в реальном времени (захват изображения камерой, несложные математические преобразования ™, вывод на экран).

Пока потолок - около 2-4 FPS на приличном компьютере. Цель - 25.

Упёрся в узкое место: скопипащенный кусок на С отрабатывает за 0.5 секунды минимум, а применять его нужно к каждой картинке.

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

Соответственно, в следующем сообщении выложу статью с описанием алгоритма.

#диссер
#csharp

Herráez, M. A., Burton, D. R., Lalor, M. J., & Gdeisat, M. A. (2002). Fast two-dimensional phase-unwrapping algorithm based on sorting by reliability following a noncontinuous path. Applied Optics, 41(35), 7437. doi:10.1364/ao.41.007437

Нас ждёт увлекательное путешествие в мир векторных инструкций (SIMD, возможно - вставок ассемблера в С#, или, как крайняя мера - знакомство с CUDA или OpenGL).

Будет весело и страшно больно и познавательно, не переключайтесь.

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

P.S. Адские звуки на фоне - это кот, а не кристаллизация воды в бутылке.

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

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

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

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

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

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

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

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

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

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

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

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

#csharp #диссер

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

Опишу в двух словах, как работает финансирование российской науки. Деньги могут прийти или от организации, в которой работают ученые, или от отраслевого министерства (Минсельхоз, Минобрауки, Минздрав) или от федерального фонда — РНФ или РФФИ. Деньгами на науку могут распоряжаться и другие организации, но на фоне вышеназванных это мелочи.

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

РНФ — только крутые команды, ценз на набор публикаций, необходимых для подачи заявки и отчетность, там совершенно конский. И только РФФИ занимается сбросом небольших "вертолетных" денег на российскую науку. Гранты у РФФИ небольшие, их не хватает на полноценное содержание научного коллектива и проведение исследований. Но получить их относительно просто, чтобы отчитаться достаточно просто что-то делать, прорывных успехов они не требуют.

Именно РФФИ позволяет не разбежаться коллективам, которые по каким-то причинам остались без постоянного источника денег. При слиянии обещают сохранить всё лучшее из того, что было, но зачем трогать то, что прекрасно работает и выполняет свою роль, сложившуюся исторически? Да и сомнительно, чтобы сброс "вертолетных денег" на науку относился к лучшим практикам по мнению министерства.

Eshu Marabo

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

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

Как определить, что проект, в базе которого ты копаешься - русский по происхождению?

А если серьезно - создатели Libgen очень круты. И их полная открытость (код приложения, код сервера, все бэкапы и весь контент в свободном доступе) - это мега круто.