Заметки о C - TrueCat17/Ren-Engine GitHub Wiki

Эта статья не поможет вам в освоении Ren-Engine, здесь просто описан некоторый опыт, собранный при разработке на C++.

Её можно разделить на 3 части:

1. Учитывание архитектуры компьютера,
2. Программная часть,
3. Сборка.

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

Учитывание архитектуры компьютера

Между процессором и оперативной памятью лежит кэш для оперативной памяти. Этот кэш быстрее, чем оперативная память, но стОит дороже, поэтому имеет малый размер.
Обычно есть 2 (у ноутбуков) или 3 уровня.
В большинстве компьютеров сам процессор работает только с регистрами процессора, загружая и выгружая оттуда данные.
Есть несколько (для каждого процессорного ядра) кэшей первого уровня (L1), уровни 2 и 3 - общие для всех.
Но на самом деле это всё ещё упрощённая картина, конечно.

Зачем это всё вообще нужно знать? Вот примерное сравнение времени доступа (в наносекундах):

• к L1 - 1.2,
• к L2 - 3,
• к L3 - 12-23,
• к оперативной памяти - 60.

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

Когда я делал blur (размытие изображения), я заметил одну удивительную вещь.
Во-первых, стоит отметить, что в Ren-Engine есть размытие движением (motion blur, относительно какой-то "центральной" точки), а также горизонтальное и вертикальное размытия - речь здесь идёт о последних двух.
Горизонтальное размытие - это когда для каждого пикселя берётся диапазон соседей по-горизонтали, "суммируются" их цвета, делятся на кол-во этих пикселей, и в результате получается "средний" цвет, т. е. размытие. Надеюсь, это понятно, ведь здесь всё просто.

Для дальнейших объяснений нужно напомнить о хранении изображений в памяти.
Вот изображение 4x3 с пронумерованными пикселями:

00 01 02 03
04 05 06 07
08 09 10 11

В памяти эти строки располагаются подряд, т. е. (упрощённо) так:
00 01 02 03 04 05 06 07 08 09 10 11

(Учтите, что это очень маленькое изображение, и чаще каждая из сторон имеет длину в сотни или тысячи пикселей.)

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

Почему? Есть несколько причин:

• При чтении какого-либо байта процессор читает не только этот байт, но и целую "линию" из 64 байт. Условно говоря, при загрузке пикселя 00 мы автоматически получаем и 01, и 02.
  В результате происходит довольно большой прирост в производительности во время таких "горизонтальных" проходов.
  При "вертикальном" проходе всё это теряется. Пиксели, близкие в геометрическом смысле, находятся далеко физически.
• Кэш оперативной памяти здесь по факту не используется (загруженное однажды значение пикселя перезаписывается в кэше другими пикселями ещё до того, как оно понадобится в следующий раз).

Как была решена эта проблема? "Вертикальный" проход был заменён на следующий набор действий:

1. Повернуть изображение на 90 градусов,
2. Пройтись "горизонтально",
3. Повернуть изображение назад.

Казалось бы: операции поворота, мягко говоря, не бесплатны. Поэтому самым удивительным здесь для меня было то, что все эти действия в сумме выходили в 3 раза быстрее обычного "вертикального" прохода.

Длинная и интересная статья на эту тему на Хабре.

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

Впрочем, иногда это приводит к уязвимостям на уровне непосредственно процессора (см. Meltdown), но эта статья не про то.

Опять же, нагляднее всего это можно показать на примере попиксельной обработки изображений.
Вот основная часть кода от реализации im-функции recolor:

if (src[Ashift / 8]) {
	dst[Rshift / 8] = src[Rshift / 8] * r / 256;
	dst[Gshift / 8] = src[Gshift / 8] * g / 256;
	dst[Bshift / 8] = src[Bshift / 8] * b / 256;
	dst[Ashift / 8] = src[Ashift / 8] * a / 256;
}else {
	*(Uint32*)dst = 0;
}

Здесь сначала происходит проверка на непрозрачность, и если она не пройдена, то итоговым цветом просто ставится 0.

Может показаться, что т. к. в большинстве случаев пиксели не являются полностью прозрачными, и эта проверка скорее просто отнимает время, чем экономит его. Однако:

1. Самую большую часть времени происходит загрузка данных из оперативной памяти в регистры процессора. Т. е. в любом случае нам нужно долго получать значение src[Ashift / 8], а после этого проверка условия почти ничего не стоит.
2. Код в ветках условий начинает вычисляться ещё до того, как процессор определит, выполняется ли условие. После этого определения "ненужные" данные отбрасываются, а нужные продолжают вычисляться. Т. е. даже при обработке полностью непрозрачного изображения потери на условие будут около нуля.

Следующая оптимизация следует из предыдущей - параллельное выполнение инструкций.

Например, следующий код выполняется всего на 28% быстрее, чем тот же код с раскомментированными строками, хотя эти 3 строки являются, очевидно, бОльшей частью работы.

unsigned index = 0;
for (unsigned i = 0; i < 1e9; ++i) {
	res[0] += nums1[index];
//	res[1] += nums2[index];
//	res[2] += nums3[index];
//	res[3] += nums4[index];
	
	if (++index == N) {
		index = 0;
	}
}

Группировка нескольких мелких итераций цикла может значительно ускорить этот цикл.

Псевдокод:

повторить 100 раз:
	команда

Заменяется на:

# 12 = целая часть 100 / 8
повторить 12 раз:
	команда
	команда
	...итого 8 раз
# 4 = остаток от 100 / 8
повторить 4 раза:
	команда

Достигается это, конечно, не за счёт уменьшения операций со счётчиком цикла, а засчёт того, что процессор опять может выполнять несколько команд параллельно, в то время как в первоначальном варианте итерации идут одна за другой, потому что они зачастую зависят от счётчика цикла, который постоянно меняется.
Векторизация избавляет от этого. Штука эта нужная, поэтому в компиляторах есть автовекторизация (которая работает не всегда хорошо и надёжно), в gcc она включается на уровне оптимизаций -O3, в clang - на -O2.

Некоторые программы держат в памяти чуть ли не всё, до чего они могут дотянуться, и это плохо.
Замечали браузер, который может занять под 80% вашей оперативы? Или игру, которая для показа меню требует гигабайт-другой?
Вот это оно.

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

Дисковый кэш ОС - штука очень важная. Настолько, что ОС нередко выгружает неиспользуемую память приложений в swap-раздел, лишь бы увеличить размер этого кэша - вот на что тратится "пустая", "неиспользуемая никем" оперативка. И вот почему не стоит тратить её, даже если её ещё предостаточно.
Чтобы лично убедиться в этой важности, вы можете после запуска компьютера открыть браузер и засечь время, которое для этого понадобится (в моём случае это около 10 секунд). После закрыть и запустить снова (повторный запуск ~3 секунды). Разница - время, которое уходит не на запуск, а именно на чтение необходимых файлов с диска.
И чем меньше размер дискового кэша - тем меньше в нём хранится файлов, тем менее отзывчивой будет работа с компьютером.

Кстати, если чуть подробнее, то ОС кэширует "страницы" (части) файлов по 4 КБ, а не конкретные файлы.

Подробнее на всю эту тему.

Программная часть

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

Вот пример использования от всё той же реализации recolor:

if (smallImage(w, h)) {
	for (int y = 0; y < h; ++y) {
		processLine(y);
	}
}else {
#pragma omp parallel for
	for (int y = 0; y < h; ++y) {
		processLine(y);
	}
}

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

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

Раньше мне казалось, что непосредственно в процессоре операции с плавающими числами выполняются с типом double (или даже с long double), соответственно float просто экономит оперативную память (и её кэши), но не время.
Недавно я проверил эту идею, и оказалось, что операции с float на 35% быстрее, чем с double.
Во многих местах (координаты, прозрачность...) было бы достаточно и float (с приличным запасом точности), так что там был сделан переход double -> float.

Кстати, ещё одной причиной для этого перехода был баг компилятора g++, после какой-то версии которого работа с double в 32-разрядном Линуксе стали в ~1.5 раза медленнее, чем в версии для аналогичной винды (хотя я мало что могу сказать об обстоятельствах, в которых это начинает проявляться). С float такой проблемы не наблюдается.

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

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

Рекомендую просто абсолютно всегда и везде использовать utf-8.

Как с ней работать?

1. utf-8 (кодировка) кодирует символы Юникода (таблицы),
2. Каждый символ занимает от 1 до 4 байт,
3. Т. е. нельзя напрямую переместиться к символу по его номеру,
4. Каждый байт содержит в себе информацию о своём номере в символе,
5. Можно легко определить, является ли данный байт первым,
6. Следовательно, можно пройтись по байтам как по цепочке, отсчитывая номера символов,
7. Так можно дойти до нужного символа или посчитать кол-во символов в массиве байтов.

Как быть с входными данными?
Легко - принимать только utf-8 и точка.
Никаких "угадываний", никакой конвертации, никаких дополнительных указаний.
Только полная унификация всего.
Аналогично с выходными данными.

Почему не utf-16 или utf-32, ведь они тоже кодируют символы Юникода?

• utf-32 слишком "жирный" (в 4 раза), хоть и имеет приемущество в скорости отсчёта (что вряд ли нужно где-то кроме текстовых редакторов),
• utf-16 - не одна кодировка, а две (BE и LE, с разным порядком байтов), имеет как недостатки utf-32 ("жирность" x2), так и недостатки utf-8 (переменное число байт на символ), а также свои собственные (их 2 разных штуки). Блин, да это нечто используется в винде - какие ещё аргументы нужны? Определённо худший из всех возможных выборов.

Вот статья с дополнительными разъяснениями на эту тему. Хотя призыв использовать "широкие" символы я не одобряю.

А, и стоит помнить, что здесь не учитывается работа с теми символами, что являются не отдельными символами, а дополнениями к предыдущим (вроде знака ударения, см. "Комбинированные символы" и "Блоки Юникода", выделенные под них).

Нет, shared_ptr не потокобезопасен, потому что не является атомарным в общем смысле этого слова. Может смутить то, что внутри используются атомарные примитивы, но они обеспечивают корректную работу лишь для многопоточного "чтения" (и только!), "запись" же время от времени будет приводить к неприятностям вроде двойного освобождения памяти.

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

Хотя в C++20 вроде планировали с этим что-то сделать, с этим нужно разбираться отдельно, но в любом случае голый shared_ptr (скорее всего) будет иметь прежнее поведение.

Опять же вот хорошая статья.

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

• debug/app
• release/app
• resources/...

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

• Латиницей (причём только маленькими буквами, a-z),
• Цифрами (0-9),
• А также подчёркиванием (_) и точкой (.).

Даже тире (все виды) и уж тем более пробелы, а также все остальные символы и не-латиница - нежелательны.

Этот класс используется в SDL для изображений. Но у него есть одна проблема. При создании такого объекта SDL инициализирует его, обнуляя все пиксели, чтобы в нём не было мусора. Проблема заключается в том, что если после создания вы сразу начинаете заполнять его нужными вам значениями, то вам не важно, что именно там было до этого, но просто сказать "не нужно обнулять все пиксели" нельзя.

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

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

vector<bool> - это не совсем обычный вектор, это специализация, она заметно отличается от, к примеру, vector<int>. Отличие в том, что bool, как логический тип, занимает 1 бит, но компьютер напрямую позволяет обращаться лишь к отдельным байтам, а не битам. Хранение же 1 значения на байт равносильно трате в никуда 7/8 занимаемой контейнером памяти, что очень расточительно. И vector<bool> как раз и занимается "упаковкой", в которой место не тратится напрасно.

Я часто слышал призывы использовать вместо него обычный vector<char> (который, по сути, можно использовать как аналог vector<bool> без этой оптимизации), т. к. он якобы очень медленный. Однако, разница в моём случае была меньше 3%, так что экономия памяти и, что важнее, кэша памяти, того стоит. Хотя, возможно, некоторые операции вроде вставки элемента в начало, и будут медленнее (в чём я не уверен), но "обычная" работа идёт вполне быстро.

Сборка

С самого начала написания проекта на C++ нужно иметь хоть какую-то систему скачивания и сборки зависимостей.
В других языках программирования есть официальные менеджеры зависимостей вроде npm, pip, composer, cargo и т. д.
Но C++ был создан задолго до этого, и так уж случилось, что ничего подобного в нём нет. Есть, конечно, некоторые аналоги, но у них есть свои проблемы.
Так что для более-менее большого проекта важно с самого начала либо выбрать один из аналогов для C++, либо написать его самостоятельно (как у Ren-Engine).

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

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

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

Бонус: почему нужно возиться с перекомпилированием библиотек, почему бы просто не брать готовое?
Зачастую при конфигурации можно отключить многие ненужные лично вашему проекту вещи. К примеру, "стандартная" версия одного из компонентов ffmpeg весит 30 МБ, в то время как без всего лишнего - 2. Учтите, что это - не единственная библиотека, а также не забывайте, что бинарники будут под несколько платформ.
Большой вес приложения снижает удобство распространения, замедляет запуск, тратит оперативную память и трафик.
По возможности старайтесь бороться за каждый мегабайт. Кстати, статическая линковка в этом тоже помогает, хоть она и не всегда бывает желательна по самым разным причинам. Но libc лучше не линковать статически (как минимум, потому что OpenGL на системе пользователя всё равно будет пытаться загрузить её динамически, и тогда будет конфликт 2-х libc).

Итак, как было сказано выше, Ren-Engine использует свою систему сборки. Вот как это устроено:

1. Есть сам проект (со своими параметрами сборки),
2. Есть зависимые библиотеки,
3. У некоторых зависимых библиотек есть свои зависимые библиотеки (png для SDL2_image, к примеру),
4. У каждой библиотеки есть свои параметры и компоненты, которыми нужно управлять,
5. Сборка библиотеки делится на конфигурацию (настройку, configure) и саму сборку (make),
6. Для каждого из этих 2 этапов у каждой библиотеки есть свой скрипт (bash),
7. Эти скрипты копируются в директории исходников (где и запускаются), во время копирования они подправляются,
8. Поправки указываются в самой этой самописной системе сборки (компилятор, разрядность, оптимизации, потоки и т. д.),
9. Когда все зависимости собраны, собирается основной проект.

В результате получается мешанина из кода на C++, C, bash и python, которые запускают, копируют, изменяют, генерируют, конфигурируют и собирают друг друга.
Мозги при написании такого кода иногда просто закипали.

А самое веселье начиналось при поиске ошибок, игра "угадай, кто и на каком этапе накосячил":

• Проблема в указании параметров?
• В копировании и внесении правок?
• В моём скрипте сборки?
• В скрипте конфигурации данной библиотеки?
• В скрипте, который генерирует предыдущий скрипт? (привет, autogen.sh)
• В неустановленных зависимоятсях, о которых забыли написать?
• Где-то ещё?

Иногда даже выходило, что косячил Гитхаб, отдавая при скачивании zip-архива репозитория с сайта не все файлы, из-за чего пришлось для этого использовать git и требовать его установки для сборки проекта.

Ужас, в общем. Мне нравится сам язык C++, но его инфраструктура просто убивает...

И ещё выяснилось, что Python нельзя собрать с помощью gcc на винде - только с помощью компилятора от MS. Ну и где эта хвалёная кроссплатформенность питона? Можно сказать, что кроссплатформенность - это не про то, но это не совсем так. Лично меня это в нём сильно разочаровало.

В прошлых версиях я использовал Boost (Python и Filesystem; и system - общий код компонентов буста).
Но после некоторого времени я был рад от него отказаться и удалить всё с ним связанное.

Boost::Python был медленным, но что ещё важнее - он медленно собирался и сильно замедлял разбор файла со стороны IDE. Как пример - каждый файл с #include <boost/python.hpp> компилировался на 10 секунд дольше.
Файлов таких было больше десятка, в результате даже самое минимальное изменение приводило к долгим ожиданиям, не смотря на то, что компиляция была инкрементальной (перекомпиляция лишь изменённых файлов).
Да и Python C API оказался не таким страшным, как казался в начале. Хотя вызов C++-функций из Python с проверкой кол-ва, типов и значений аргументов оказался той ещё головоломкой, моё решение которой лежит в соответствующем репозитории.

Boost::Filesystem после этого остался, по сути, единственным компонентом буста, который использовался в моём проекте. Отдельно его компилировать, вникать в его тонкости и тащить его собственную систему сборки было весьма неудобно.
Выходом стала подоспевшая поддержка компиляторами стандарта C++17, в котором операции с файловой системой были перенесены из буста в стандартную библиотеку.

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

Вероятно, время от времени сюда будет что-то добавляться в будущем...