Ефективний код на C++: чому вирішує розташування даних у пам'яті

Сам лише вибір C++ не робить програму швидкою. У статті “Writing Efficient C++ Code” програміст Adam Sawicki пояснює, що визначає, наскільки добре код використовує апаратне забезпечення: як дані лежать у пам'яті та як часто процесор чекає на кеш. Текст уперше опублікували польською у журналі Programista 2013 року.

C++ сама по собі не дає швидкості

C++ достатньо високорівнева для об'єктно-орієнтованого дизайну й готових контейнерів, але достатньо низькорівнева, щоб між кодом і операційною системою не було ні віртуальної машини, ні збирача сміття: пам'ять звільняє сам програміст.

Дизайн, орієнтований на дані

Data-Oriented Design, популярний серед розробників ігор, починає з даних: їхнього розташування в пам'яті та структур, які їх зберігають, а алгоритми обирають пізніше. Підхід не забороняє класи, але застерігає проти безлічі дрібних об'єктів, розкиданих у пам'яті та з'єднаних вказівниками: такі схеми спричиняють часті промахи кешу і погано піддаються розпаралелюванню. Звичайний масив, навпаки, обробляється елемент за елементом, і його діапазон легко розділити між потоками.

Ієрархія пам'яті визначає ціну

На процесорі з частотою 3 ГГц одна арифметична операція триває близько 0,33 наносекунди, тобто один такт. Значення в кеші L1 коштує приблизно 1 наносекунду, у L2 близько 4,7, а в RAM близько 83 наносекунд, тобто 250 тактів. Дані передаються рядками по 64 байти, тому значення, які використовують разом, мають лежати поруч.

Тому неперервні структури, як звичайний масив або std::vector, виграють у зв'язаних списків і дерев. Стаття описує “піраміду продуктивності”: найшвидша арифметика, значно повільніші трансцендентні операції на кшталт синуса чи ділення, сотні тактів коштує звернення до RAM після промаху кешу, дороге динамічне виділення пам'яті, а найповільніше введення та виведення.

AOS, SOA і межі компілятора

Система частинок добре показує цей компроміс. Array of Structures зберігає позицію, швидкість і колір кожної частинки разом; Structure of Arrays тримає окремий масив для кожної властивості, тому потрібні в циклі значення лежать поруч, а невикористані поля не потрапляють у кеш.

Компілятор не виправить усе. Коли вказівник може вказувати на елементи масиву, значення доводиться перечитувати на кожній ітерації, і тут допомагає копіювання в локальну змінну або __restrict. Винесення std::string із циклу та очищення його щоразу скоротило тест із 0,36 до 0,27 секунди, тобто на 25%, бо рядок зберігає свій буфер.