как ускорить free pascal/lazarus программу в 2 раза

в free pascal/lazarus есть удивительная опция. называется она целевая платформа.
если выбрать ту платформу, под которой будет работать программа, или достаточно выбрать x86_64 и скомпилировать, то программа заработает в 2 раза быстрее.
в исходном коде не нужно для этого ничего менять
а вот 2 скриншота, показывающие результат

small mlt на free pascal

пришла мне идея проверить скорость работы free pascal compiler по сравнению с gcc на с++.
напишу pascal-версию small mlt для проверки на скорость.
для проверки раньше использовал другие рендеры на lazarus/free pascal и включение одной опции компилятора добавило 690 кб к размеру exe и невиданую доселе скорость работы получившейся программы - всего на 20% медленнее c++ версии алгоритма.
алгоритм был реализован неаккуратно и с точностью тех тестов согласиться не могу.
поэтому напишу своё. может пригодиться впоследствии.
заодно проверю перезагрузку операторов

hash maps

оказывается, ассоциативные массивы с ключом-строкой могут быть быстрее unordered_map <std::string, int>

unordered_map <std:string, int> map1;
 
    printf("std hash func... ");
 
    clock_t t0=clock();
 
    for(i=0;i < n;i++)
        str = ltoa(i);
        map1[str]=i;
    } 

если хранить индекс, как int со значением из хэш-функции, то можно достигать до 4х-кратного повышения скорости работы

unordered_map <uint32_t, int> map3_3;
 
    printf("X31_hash_string hash func... ");
 
    clock_t t20_3=clock();
 
    for(i=0;i < n ; i++)
        str = ltoa(i);
        map3_3[X31_hash_string((char*)str.c_str())]=i;
    }

и функция расчета хэша, которую я взял из проекта khash.h, выглядит просто и работает быстро и создаёт мало коллизий:

typedef uint32_t khint_t;
 
uint32_t X31_hash_string(const char *s)
{
 
    khint_t h = *s;
    if (h) for (++s ; *s; ++s) h = (h << 5) - h + *s;
    return h;
} 

xxhash оказался не очень быстрым, хоть и качественный, почти как и другие сравниваемые алгоритмы хеширования
sz означает количество элементов
если их меньше 5000000 - количество добавляемых элементов - то коллизии-наложения и ошибки
fletcher32 оказался не очень быстрым и к тому же создаёт много коллизий. не нужен!
X31_hash_string оказалась и быстрее, и хороша - мало коллизий(0)

скачать source code of tests on c++

сначала связать, затем оптимизировать

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

данный принцип похож на непрерывную интеграцию - одно из правил экстремального программирования

новый todo

• сделать akari variance based с blur и т.д. adaptive antialiasing
• IBL - tinyexr, hdr чтение оптимизировать из akari
• из akari взять целиком загрузчик vvv и интеграция с qbvh
• добавить загрузку изображений
• добавить texture mapping во всех видах
• добавить assimp, допилить его по максимуму
• добавить сцены

adaptive antialiasing + 3-pass preview

воплотил обе методики и заметил, что частое использование 3х-ступенчатого метода превью создаёт мерзкую квадратную структуру на изображении. отключаю эту методику для создания превью с 2й итерации. картинка получается быстрой и точной. раньше можно было получить первое изображение на тестовой сцене через 19-25 секунд.
сейчас же первая картинка - 4 секунды

SOIL - Simple OpenGL Image Library

хорошая библиотека, ремикс stb_image.
добавлен формат tga,
есть функции для загрузки текстур и отображения их с помощью OpenGL
https://github.com/kbranigan/Simple-OpenGL-Image-Library

курс держать учусь я снова

увлёкся отвлёкся привлёкся lazarus и библиотеками чтения, отображения 3d-форматов. автор искушает еще path tracer, с хорошей связью с читалкой файлов.
не смущало сильно и то, что тормозные достаточно читалки и дописывать тьму и то, что path tracer вникнуть, переписать, довнедрить из с++ версии...

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

отложил lazarus в сторону. ибо можно воплотить хорошо и быстро работающий вариант рендера, а переписывать, дописывать, шлифовать(а надо ли?) можно будет потом

важнее всего - быстро выпустить бету без потерь качества

не соблазняться и не отвлекаться
и фигачить!

переход снова к pascal/delphi -> lazarus

lazarus всё ж ближе. на крестах суетно писать бывает. и про то чтоб собрать везде спокойно не уверен что выйдет. сам намучился с присоединением к fox toolkit, fltk.

проще всего связать рендер с fox toolkit, дописав в проекте visual c++ вместо примера по fox toolkit вызов своего кода и компилировать intel c++.

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

lazarus радует наличием библиотек и компонентов для загрузки и отображения 3d-форматов.
glscene и Castle Game Engine - достойные библиотеки. возьму одну из них и допишу из другой, недостающее возьму из assimp.

Castle Game Engine порадовали наличием поддержки hdr, но exr сделан через экспорт из imagemagick. надо код связи с imagemagick изгнать и сделать на основе tinyexr, stb_image

AdaptiveDistributedRenderScene, vcm и разные семплинги

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

smallVCM sampling		шумный семплинг из других рендеров
path_noisyness 0.15		path_noisyness 0.075

все рендеры - 10 минут +-10 секунд

интересная работа - Глобальное освещение с помощью октантных текстур

Глобальное освещение с помощью октантных текстур

two-stage mlt

рассматривал mitsuba render в действии и заметил, что есть в kalemen-style mlt(в mitsuba этот метод называется primary sample space mlt) галочка two-stage mlt.
все попытки понять что это такое отсылали меня к чтению документации.
оказывается, сначала генерируется картинка 1/16 размера и высчитывается variance начальных путей для mlt, далее с использованием variance выбирается путь, что даёт более точную картинку.
direct samples не делает картинку лучше. поэтому они и не нужны



на что обратить внимание

обзор nox render

nox renderer - render от evermotion.com, ныне - opensource. исходный код можно загрузить с сайта. из интересного для меня:

• path tracing, bidirectional path tracing
  
  
• прогрессивное обновление изображения
• render passes, здесь называемые LAYERS
  
• разные алгоритмы заполнения изображения семплами
• аккуратное управление камерой - фокусное расстояние, пресеты обьективов
  
  
• очень хороший редактор материалов
  
• присутствуют пост-эффекты bloom, glare, fog
  
• коррекция изображения с помощью кривых
  
• настройки антиалиазинга и пресеты фотоплёнок
  
• хорошие настройки солнца, неба, атмосферы
  
• оптимизация геометрии при загрузке - находятся дубли вершин и сохраняются только неповторяющиеся. экономит память
• удобный интерфейс

внимательный читатель заметит, что я обошел стороной вкладку FAKE DOF. я там ничего не понял и слово fake меня отогнало

в комплекте с исходниками идёт и nox bench

загружается и рендерится достаточно увесистая сцена с помощью nox render
сцену можно загрузить в nox render

из минусов
странно на этапе загрузки сцены видеть, что вычисляются uv-координаты и дисплейсмент
я бы рассчитал потом, когда это действительно понадобится
процесс загрузки сцены

о 3х-проходном методе рендеринга. продолжение

в прошлой заметке я показывал вот такую схему проходов рендеринга

если внимательно посчитать и подумать, то:
1й проход это 1/16
2й проход это 4/16
3й проход это 16/16 - 4/16 - 1/16 = 11/16

многовато на 3й проход... подумалось мне и придумал я другую схему

в новом варианте на 2м проходе немного странноватая схема - не 2х2 блок, а 2 на 3 строки
итого:
1й проход 1/16
2й проход 6/16
3й проход 16/16 - 1/16 - 6/16 = 9/16
так вроде бы лучше ;-)

хотел заметить, что фотонов выпускать нужно 1/16, 6/16 и 9/16. размер изображения 1/4, 1/2, 1/1

manifoldis next event estimate

в ближайшее время возьму реализацию PTMNEE из nanogi.cpp и внедрю в свой PEPELAC RENDERING BANDURA отдельным рендером на основе pathtracer.hxx, в работе которого и всего комплекса основного рендеринга я насилу разобрался

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

render dev roadmap

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

• запоминать render passes, в том числе по технологиям, как в UPBP
• variance adaptive importance sampling for cam paths, как в akari
• AdaptiveDistributedRenderScene() готово
• далее - воплотить 3х-ступенчатый метод рендеринга готово
• добавить texture mapping, bump mapping, displacement, процедурные текстуры
• добавить tinyexr для чтения и записи exr
• добавить assimp кучи форматов 3d-сцен и обьектов, оптимизировать assimp в плане поиска в строках и любимую мной буферизацию добавить
• на основе примера из fox toolkit сделать загрузчик и просмотрщик всех форматов 3d, поддерживаемых assimp
• добавить загрузчики и сохранение изображений из stb_image, lodepng для png, jpeg compressor для jpg
• добавить uniform grid scene accelerator - для вокселизации всей сцены и сделать мою реализацию, без хранения большого массива массивов с обьектами. линейный массив и бинарные поиски!
• добавить qbvh из akari. создавать qbvh в каждой ячейке grid, к которой происходит обращение. можно кешировать и выбрасывать из кэша, если память нужнее
• попробовать переписать vector.push_back на emplace_back и проверить насколько мой arr_list быстр и уместен
• hdri освещение с importance sampling из akari
• сохранение hdr с rle-упаковкой из akari, код записи которого я недавно ускорил с 17 секунд на файл до 0,6 секунд. это всё чудеса буферизации и выбрасывать нужно по-тупому используемые функции, которые дико там не к месту. код не лучше, чем у меня, и потому внедрять его не стану
  

akari MinGW build !!!

minGW port of akari
я наконец-то собрал akari с помощью MinGW компилятора gcc.
теперь заживу!
меня останавливало от продолжения работы над рендером отсутствие вменяемого примера, когда qbvh собирается с MinGW без ошибок


преимуществом факта сборки с помощью MinGW akari стало то, что можно будет собирать мой рендер на любой платформе без потери скорости

мне радость!!!!!!!!!!
потому что из akari можно взять работу с апертурой-изображением, variance-based importance sampling path tracing, importance sampled IBL, qbvh и еще парочку штук

vcm в 3 прохода с импортансами в придачу

пока в виде идеи, но на днях воплощу такое:
отрываю фотошо и рисую простую картинку с линиями и циферками, которую рисовал в блокноте сегодня

1. первый проход
   
   • выпускается 1/4 лучей из ламп от размера изображения
   • просчитывается картинка 1/4 от размера кадра
   • если итерация алгоритма первая, то зарисовать все остальные пикселы полученным цветом. маленькие цифры покажут что я зарисую тем же цветом пиксела
   • шаг к следующей комбинации 4
   • ^{у меня исполняется за часть секунды (0.1 - 0.3), у людей компы посильнее и будет очень быстро}
2. второй проход
   
   • выпускается 1/2 лучей из ламп от размера кадра
     *просчитануя на предыдущем проходе хэшмап фотонов можно использовать в качестве импортонов - для улучшенного попадания лучей в действительно важные области изображения
   • просчитывается картинка с на размер изображения 1/2 от размера изображения с учетом variance от картинки с прошлого шага. адаптивный самплинг тут сделаю
   • если итерация алгоритма первая, то зарисовать все пикселы справа и снизу квадратами 2х2
   • шаг к следующей комбинации 2
   • ^{у меня исполняется за 3 секунды}
3. третий проход
   
   • всё также, как и в 2м
     
   • ^{у меня исполняется за 3 секунды}

итерация - это один полный цикл трейсинга для получения полного кадра
проход - в каждой итерации 3 прохода
комбинация - это цикл прохода по пикселам изображения - сначала обработаются все 1, затем все 2, затем все 3

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

1/4 размера кадра у меня исполняется за часть секунды (0.1 - 0.3), у людей компы посильнее и будет очень быстро
1/2 размера кадра - за 3.5 секунды
полный кадр просчитывается за 17 секунд

Volumetric Vertex connection and merging и другие новшества из проекта UPBP

при внимательном изучении кода UPBP обнаружил:
upbp_bpt это vbpt(volumetric bidirectional path tracing)
upbp_surf - vertex merging фотоны на поверхности
upbp_vcm = upbp_bpt + upbp_surf, volumetric vcm
upbp_pp3d - point to point merging - соединяет фотоны volume - дымы, туманы и прочее такое, немного совсем замедляет рендеринг
upbp_pb2d - point to beam - связывает фотоны с photon beam(световые трубы), замедляет ощутимо, до 2х раз время рендеринга
upbp_bb1d - beam to beam - связывает световые трубы, капец как сильно замедляет рендеринг

upbp_bpt, upbp_surf, upbp_pp3d работают с фотонами-точками,
upbp_pb2d, upbp_bb1d - с photon beams - световые трубы, снопы света

*помимо упомянутых здесь photon beams, облегчающих задачу визуализации volumetric-эффектов есть еще Progressive Expectation–Maximization for Hierarchical Volumetric Photon Mapping, который ускоряет рендеринг по сравнению с photon beams.
изображение из pdf


все эти алгоритмы нашёл как пустить через importance sampling дабы избежать долгого рендеринга.
спасибо авторам UPBP за внятный код и реализованные там алгоритмы сохранения DebugImages - сохраняются изображения покрытия семплами для каждого алгоритма и даже по проходам картинки сохраняются

на State of the Art in Photon Density Estimation SIGGRAPH 2012 Course также есть интересная техника Photon Relaxation

из исходников вытер всякое упоминание методов рендеринга, которые дублируются в upbp.hxx - exe уменьшился на 100 кб. небольшое, но всё ж уменьшение ;-)

что такое Vertex Merging в алгоритме Vertex Connection and Merging (vcm)

читая исходный код UPBP, наткнулся на неплохую реализацию Volumetric Bidirectioanl Path Tracing.
и многое мне напоминало код vcm.
сравнил код VolBidirPT.hxx и VertexCM.hxx увидел, что отличие, кроме volumetric-кода, в коде Vertex Merging.
в vcm, upbp он есть, а в vbpt - нет.

bpt		vcm
33s		56s
39s		73s
37s		71s
29s		44s

в обоих случаях - 5 проходов

между Generate light paths и Generate camera paths
вписан следующий код

создаётся на основе запомненных попадений луча в обьекты и цвета этих "фотонов" хэш-таблица для progressive photon mapping, который дописывается после vertex connection, который в свою очередь собирает лучи из камеры для каждого пиксела


vertex merging - очень хороший пример path reuse, использования уже просчитаной информации еще одним путём для нахождения дополнительной информации об освещении сцены.
и пофиг, что vcm в 1.5-2 раза медленнее bpt. у многих современных рендеров и такое редкость, не говоря о качестве изображения.

Volumetric Bidirectional Path Tracing мне приглянулся больше, чем UPBP-технологии - быстрее, не уступает в качестве - более равномерное покрытие семплами изображения

восторг при чтении кода

эвристика для ускорения поиска фотонов, попадающих в радиус

фотоны, которые попадают в квадрат, автоматически попадают в нужную мне окружность и не надо считать расстояние до фотона

smallUPBP - сцена 27

время просчета - 4 минуты 28 секунд. 10 проходов
алгоритм upbp_vcm
о волюметриках и алгоритмах группы upbp_ могу сказать, что память жрёт очень и очень

smallUPBP

Сделал еще попытку собрать upbp и обнаружил, что программа падает при попытке исполнить sse4 - инструкции. Кое-где заменил на обычный алгебраический подход, без sse.
В тестовых сценах много источников света и им очень-преочень нужно умное importance-based семплирование, коим я сейчас и занимаюсь.
На upbp еще навешаю importance sampling везде где только можно - hdri-освещение, как в предыдущем посте - для direct light и importons для глобального освещения и прочих каустиков


10 проходов. каждые 2 прохода сохранял изображение. 261 секунда(4 минуты 20 секунд)

как видно, семплинг галимейший. ибо столько шума и ярких точек спустя столько времени просчета...

importance light sampling. tungsten

взято из Tungsten. со слов Handling multiple lights

идея для быстрого и экономного акселлератора пересечений луча с обьектами сцены grid. обновлено - пересечение

данный алгоритм писался с учетом особенностей GLSL и программирования GPU-рендера - простота и быстродействие выбраных технологий

1. по формуле из SunFlow расчитать количества ячеек в grid на основе ограничивающего бокса сцены и количества обьектов
2. пройтись по сцене и вместо добавления обьектов увеличивать счетчик необходимых ячеек
3. выделить память под массив
4. расчитать коэфициент ближайшего большего десятка по количеству обьектов
5. хранить одну запись в формате float.
   элемент массива = индекс обьекта*коэфициент + номер ячейки
6. пройтись по сцене и сохранить в массив данные
7. отсортировать сортировкой Шелла массив по номеру ячейки. она на 2-3 месте от quicksort и лучше там, что проста в воплощении и нерекурсивна
8. доступ к элементам в ячейке - быстрый поиск в массиве по номеру ячейки

пересечение. проход ячейки grid.

1. выбираются все обьекты у которых mailbox!=rayID, складываются в массив сортированых ид обьектов. если такой ид уже есть(бинарный поиск мне поможет), то не вставлять. если нет - смотреть и сдвигать элементы массива
2. полученный массив обьектов сортируется по дальности центров BBox относительно ray.org (сортировка шелла, sqrt не вызываю)
   vec3 delta = vec3(bbx.bbmax-bbx.bbmin)*0.5-r.org;
   float dist = dot(delta,delta);
3. отсортированный массив проходится и устанавливается обьектам mailbox=rayID