Про мову З і продуктивності



Якщо програміст добре знайомий тільки з високорівневими мовами, наприклад PHP, то йому не так просто освоїти деякі ідеї, властиві низькорівневим мов і критичні для розуміння можливостей інформаційно-обчислювальних процесів. Здебільшого причина в тому, що у низько — та високорівневих мовах ми вирішуємо різні проблеми.

Але як можна вважати себе професіоналом у якому-небудь (высокоуровневом) мовою, якщо навіть не знаєш, як саме працює процесор, як він виконує обчислення, ефективним спосіб? Сьогодні автоматичне керування пам'яттю стає головною проблемою в більшості високорівневих мов, і багато програмісти підходять до її вирішення без достатньої теоретичної бази. Я впевнений, що знання основних процесів сильно допомагає в розробці ефективних високорівневих програм.

Програми багатьох шкільних курсів з програмування досі починаються з освоєння азів асемблера і С. Це вкрай важливо для майбутніх програмістів, яким подібні знання знадобляться у майбутній кар'єрі. Високорівневі мови постійно і сильно змінюються, а інтенсивність і частота змін в низькорівневі мови на порядок нижче.

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

Ви дійсно думаєте, що інтернет речей буде розроблятися на високорівневих мовах? А майбутні відеокодеки? VR-програми? Мережі? Операційні системи? Ігри? Автомобільні системи, наприклад автопілоти, системи попередження про зіткнення? Все це, як і багато інші продукти, пишеться на низькорівневих мовами начебто З або відразу на асемблері.

Ви можете спостерігати розвиток нових архітектур, наприклад дуже цікавих ARM-процесорів, які стоять у 98 % смартфонів. Якщо сьогодні ви використовуєте Java для створення Android-додатків, то лише тому, що сам Android написаний на Java і С++. А мова Java — як і 80 % сучасних високорівневих мов — написаний на С (або С++).

Мова З перетинається з деякими спорідненими мовами. Але вони використовують імперативну парадигму, а тому мало поширені або не настільки розвинені. Наприклад, Fortran, що відноситься до тієї ж «віковій групі», що і З, в деяких специфічних завданнях більш продуктивний. Ряд спеціалізованих мов можуть бути швидше при вирішенні суто математичних задач. Але все ж залишається одним з найбільш популярних, універсальних та ефективних низькорівневих мов у світі.

Приступимо
Для цієї статті я скористаюся машиною з процесором X86_64, працює під управлінням Linux. Ми розглянемо дуже просту програму, яка підсумовує 1 мільярд байт з файлу менш ніж за 0,5 секунди. Спробуйте зробити це на будь-якому з високорівневих мов — ви і не наблизитеся по продуктивності до С. Навіть на Java з допомогою JIT, з паралельними обчисленнями і хорошою моделлю використання пам'яті в просторі користувача. Якщо мови програмування не звертаються безпосередньо до машинним інструкцій, а є проміжною формою (визначення високорівневих мов), то вони не зрівняються по продуктивності з (навіть з допомогою JIT). У деяких областях розрив можна зменшити, але в цілому За залишає суперників далеко позаду.

Спочатку ми докладно розберемо завдання з допомогою С, потім розглянемо інструкції X86_64 та оптимізуємо програму з допомогою SIMD — різновиди інструкцій у сучасних процесорах, що дозволяє обробляти великі обсяги даних однією інструкцією в кілька циклів (кілька наносекунд).

Проста програма на С
Щоб продемонструвати можливості мови, я наведу простий приклад: відкриваємо файл, зчитуємо з нього всі байти, підсумовуємо їх, а отриману суму стискаємо в один байт без знака (unsigned byte) (тобто кілька разів буде переповнення). І все. Ах так, і все це ми постараємося виконати якомога ефективніше — швидше.

Поїхали:

#include < stdio.h>
#include <stdint.h>
#include < string.h>
#include <fcntl.h>
#include <unistd.h>

#define BUF_SIZE 1024

int main(int argc, char **argv)
{
int f, i;
ssize_t readed;

unsigned char result = 0;
unsigned char buf[BUF_SIZE] = {0};

if (argc != 2) {
fprintf(stderr, "Використання: %s \n", argv[0]);
exit(-1);
}

f = open(argv[1], O_RDONLY);

if (f == -1) {
perror("Не можу відкрити файл");
}

while ((readed = read(f, buf, sizeof(buf))) > 0) {
for (i=0; i < readed; i++) {
result += buf[i];
}
}

close(f);

printf("Читання завершено, сума дорівнює %u \n", result);

return 0;
}

Для нашого прикладу візьмемо файл на 1 Гб. Щоб створити такий файл з випадковими даними, просто скористаємося
dd
:

> dd if=/dev/urandom of=/tmp/test count=1 bs=1G iflag=fullblock

Тепер передамо файл в нашу програму (назвемо її file_sum) в якості аргументу:

> file_sum /tmp/file
Read out, sum is 186

Можна підсумувати байти самими різними способами. Але для ефективності потрібно розуміти:

  • Як працює CPU і що він вміє (які обчислення може виробляти).
  • Як працює ядро ОС (kernel).
Коротко: необхідні деякі знання по електроніці та низькому рівню ОС, на яких виконується наша програма.

Пам'ятайте про ядрі
Тут ми не будемо заглиблюватися в роботу ядра. Але пам'ятайте, що ми не станемо просити процесор взаємодіяти з диском, на якому зберігається наш файл. Справа в тому, що на дворі 2016 рік, і ми створюємо так звані програми користувача простору (ППП). Одне з визначень свідчить, що такі програми НЕ МОЖУТЬ безпосередньо звертатися до обладнання. Коли виникає необхідність скористатися обладнанням (звернутися до пам'яті, диска, мережі, картрідеру і так далі), програма за допомогою системних викликів просить операційну систему зробити це для неї. Системні виклики — це функції ОС, доступні для ППП. Ми не будемо питати диск, чи готовий він обробити наш запит, просити його перемістити голівку, вважати сектор, перенести дані з кеша в основну пам'ять і так далі. Все це робить ядро ОС разом з драйверами. Якби нам потрібно було зайнятися такими низькорівневими речами, то ми писали програму «простору ядра» — по суті, модуль ядра.

Чому так? Почитайте мою статтю про розподіл пам'яті. Там пояснюється, що ядро керує одночасним виконанням декількох програм, не дозволяючи їм зруйнувати систему, або перейти в необоротне стан. При будь-яких інструкціях. Для цього ядро переводить процесор в режим третього кільця захисту. А в третьому кільці програма не може звертатися до апаратно відображуваної пам'яті (hardware memory mapped). Будь-які подібні інструкції будуть генерувати в процесорі виключення, як і всі спроби доступу до пам'яті за межами абсолютно конкретних меж. На виняток у процесорі ядро відповідає запуском коду виключення (Exception code). Він повертає процесор в стабільний стан і завершує нашу програму з допомогою якогось сигналу (можливо, SIGBUS).

Третє кільце захисту — режим з найнижчими привілеями. Всі ППП виконуються в цьому режимі. Можете його випробувати, прочитавши перші два біти CS-регістра в своєму X86-процесор:

gdb my_file
(gdb) p /t $cs
$1 = 110011

Перші два біти (молодші) позначають поточний рівень кільця захисту. В даному випадку — третій.

Користувальницькі процеси працюють в строго обмеженою ізольованому середовищі, що настроюється ядром, яке само виконується в нульовому кільці (повні привілеї). Тому після знищення користувацького процесу витік пам'яті неможлива. Всі структури даних, що мають до цього відношення, недоступні для користувацького коду безпосередньо. Ядро саме піклується про них при завершенні користувацького процесу.

Повернемося до нашого коду. Ми не можемо управляти продуктивністю читання з диска, оскільки за це відповідають ядро, низькорівнева файлова система і апаратні драйвери. Ми скористаємося викликами
open()/read()
та
close()
. Я не став брати функції з libC (
fopen()
,
fread()
,
fclose()
), в основному тому, що вони є обгортками для системних викликів. Ці обгортки можуть як покращувати, так і погіршувати загальну продуктивність: все залежить від того, який код ховається за цими інструкціями і як вони використовуються самою програмою. LibC — це прекрасно спроектована і високопродуктивна бібліотека (ряд її ключових функцій написана на асемблері), але всім цим функціям «вводу-виводу» потрібен буфер, яким ви не керуєте, і вони на свій розсуд викликають read(). А нам треба повністю контролювати програму, тож звернемося безпосередньо до системних викликів.

На системний виклик ядро найчастіше відповідає викликом
read()
файлової системи, даючи апаратного драйверу команду вводу/виводу. Всі ці виклики можна відстежити за допомогою Linux-трасувальників, наприклад perf. Для програм системні виклики витратні, тому що призводять до перемикання контексту — переходу з простору в простір ядра. Варто уникати цього, оскільки переходи вимагають від ядра значного обсягу робіт. Але нам потрібні системні виклики! Найповільніший з них —
read()
. Коли він робиться, процес напевно буде виведений з черги виконання в CPU і переведений в режим очікування введення/виводу. Коли операція завершиться, ядро поверне процес в чергу виконання. Цю процедуру можна контролювати за допомогою прапорів, переданих викликом open().

Як ви можете знати, ядро реалізує буферний кеш, в якому зберігаються нещодавно лічені з диска чанкі даних з файлів. Це означає, що якщо ви кілька разів запустіть одну програму, то в перший раз вона може працювати повільніше всього, особливо якщо мається на увазі активне виконання операцій введення/виведення, як у нашому прикладі. Так що для вимірювання витраченого часу ми будемо брати дані, наприклад, починаючи з третього або четвертого запуску. Або можна усереднити результати декількох запусків.

Краще дізнайтеся своє залізо і компілятор
Отже, ми знаємо, що не в змозі цілком керувати продуктивністю трьох системних викликів:
open()
,
read()
та
close()
. Але давайте тут довіримося розробникам простору ядра. Крім того, сьогодні багато використовують SSD-накопичувачі, так що можна з певною часткою впевненості припустити, що наш одногигабайтный файл вважається досить швидко.

Що ще уповільнює код?

Спосіб складання байтів. Може здатися, що для цього досить простого циклу підсумовування. Але хочу відповісти: дізнайтеся краще, як працюють ваш компілятор і процесор.
Давайте скомпилируем код в лоб, без оптимізацій, і запустимо його:

> gcc -Wall -g -O0 -o file_sum file_sum.c


Потім отпрофилируем допомогою команди
time
:

> time ./file_sum /tmp/big_1Gb_file
Read out, sum is 186 

real 0m3.191s
user 0m2.924s
sys 0m0.264s

Не забудьте запустити кілька разів, щоб прогріти кеш сторінки ядра. У мене після кількох прогонів підсумовування одного гігабайта з SSD зайняло 3,1 секунди. Процесор ноутбука — Intel Core i5-3337U @ 1,80 ГГц, ОС — Linux 3.16.0-4-amd64. Як бачите, сама звичайна X86_64-архітектура. Для компілювання я використовував GCC 4.9.2.

Згідно з даними
time
, більшу частину часу (90 %) ми провели в користувацькому просторі. Час, коли ядро щось робить від нашого імені, — це час виконання системних викликів. У нашому прикладі: відкривання файлу, читання і закривання. Досить швидко, вірно?

Зверніть увагу: розмір буфера читання дорівнює одному килобайту. Це означає, що для одногигабайтного файлу доводиться викликати
read()
1024*1024 = 1 048 576 разів. А якщо збільшити буфер, щоб зменшити кількість викликів? Візьмемо 1 Мб, тоді у нас залишиться тільки 1024 виклику. Внесемо зміни, перекомпилируем, запустимо кілька разів, отпрофилируем:

#define BUF_SIZE 1024*1024
.
> gcc -Wall -g -O0 -o file_sum file_sum.c
> time ./file_sum /tmp/big_1Gb_file
Read out, sum is 186 

real 0m3.340s
user 0m3.156s
sys 0m0.180s

Відмінно, вдалося знизити з 264 до 180 мс. Але не захоплюйтеся збільшенням кеша: у швидкості
read()
є певна межа, а буфер знаходиться в стеку. Не забувайте, що максимальний розмір стека в сучасних Linux-системах за замовчуванням 8 Мб (можна змінювати).

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

Швидше, сильніше (і не настільки вже важче)
Чому складання байтів виконується так довго? Проблема в тому, що ми просимо процесор виконувати його дуже неефективним способом. Давайте дизассемблируем програму і подивимося, як це робить процесор.

Мова — ніщо без компілятора. Це лише прийнятний для людини мова програмування комп'ютера. А щоб перетворити З-код в низькорівневі машинні інструкції, потрібно компілятор. Сьогодні ми здебільшого використовуємо для створення систем та вирішення основних завдань, тому що хочемо мати можливість без переписування портувати код з однієї процесорної архітектури на іншу. Саме тому в 1972 році був розроблений С.

Так от, без компілятора мову З — порожнє місце. Поганий компілятор або його неправильне використання може призвести до низької продуктивності. Те ж саме справедливо і для інших мов, компилируемых в машинний код, наприклад для Fortran'а.

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

Асемблер нескладно освоїти. Все залежить від архітектури, і тут ми розглянемо тільки найбільш поширений варіант з X86 (для 2016 року — X86_64).

В архітектурі X86_64 також немає нічого складного. Просто в ній ВЕЛИЧЕЗНУ кількість інструкцій. Коли я робив перші кроки в асемблері (під Freescale 68HC11), то використав кілька десятків інструкцій. А в X86_64 їх вже тисячі. Мануали у той час були такими ж, як сьогодні: незрозумілими і багатослівними. А оскільки PDF тоді не було, то доводилось тягати з собою величезні книги.

Ось, наприклад, мануали Intel X86_64. Тисячі сторінок. Це первинне джерело знань для розробників ядра і низькорівневих розробників. А ви думали, що можна було б поліпшити ваші онлайн-мануали по PHP?

На щастя, для нашої маленької програми немає потреби читати всі ці цифрові фоліанти. Тут застосовується правило 80/20 — 80 % програми буде зроблено за допомогою 20 % загальної кількості інструкцій.

Ось З-код і дизассемблированная частина, яка нас цікавить (починаючи з циклу while()), скомпільована без оптимізацій з допомогою GCC 4.9.2:

#define BUF_SIZE 1024

int main(int argc, char **argv)
{
int f, i;
ssize_t readed;

unsigned char result = 0;
unsigned char buf[BUF_SIZE] = {0};

if (argc != 2) {
fprintf(stderr, "Використання: %s \n", argv[0]);
exit(-1);
}

f = open(argv[1], O_RDONLY);

if (f == -1) {
perror("Не можу відкрити файл");
}

while ((readed = read(f, buf, sizeof(buf))) > 0) {
for (i=0; i < readed; i++) {
result += buf[i];
}
}

close(f);

printf("Читання закінчено, сума дорівнює %u \n", result);

return 0;
}

00400afc: jmp 0x400b26 < main+198>
00400afe: movl $0x0-0x4(%rbp)
00400b05: jmp 0x400b1b < main+187>
00400b07: mov -0x4(%rbp),%eax
00400b0a: cltq 
00400b0c: movzbl -0x420(%rbp,%rax,1),%eax
00400b14: add %al,-0x5(%rbp)
00400b17: addl $0x1,-0x4(%rbp)
00400b1b: mov -0x4(%rbp),%eax
00400b1e: cltq 
00400b20: cmp -0x18(%rbp),%rax
00400b24: jl 0x400b07 < main+167>
00400b26: lea -0x420(%rbp),%rcx
00400b2d: mov -0xc(%rbp),%eax
00400b30: mov $0x400,%edx
00400b35: mov %rcx,%rsi
00400b38: mov %eax,%edi
00400b3a: callq 0x4005d0 < read@plt>
00400b3f: mov %rax,-0x18(%rbp)
00400b43: cmpq $0x0-0x18(%rbp)
00400b48: jg 0x400afe < main+158>
00400b4a: mov -0xc(%rbp),%eax
00400b4d: mov %eax,%edi
00400b4f: callq 0x4005c0 < close@plt>

Бачите, наскільки неефективний код? Якщо ні, то дозвольте мені коротко розповісти вам про асемблері під X86_64 з коментарями до вищенаведеного дампу.

Основи асемблера під X86_64
Тут ми пробіжимося по верхах, а за подробицями зверніться до матеріалів , два і три.

Ми будемо оперувати байтами і ступенями 2 і 16.

  • Кожна інструкція зберігається в пам'яті за адресою, вказаною в лівій колонці.
  • Кожна інструкція унікальна і має ім'я (мнемонічне): LEA — MOV — JMP і так далі. У сучасній архітектурі X86_64 існує кілька тисяч інструкцій.
  • X86_64 — це CISC-архітектура. Одна інструкція може перетворюватися в конвеєрі в кілька більш низькорівневих інструкцій, виконання кожного з яких іноді потрібно кілька процесорних циклів (clock cycles) (1 інструкція != 1 цикл).
  • Кожна інструкція може приймати максимум 0, 1, 2 або 3 операнда. Частіше всього 1 або 2.
  • Існує дві основні моделі асемблера: AT&T (також називається GAS) і Intel.
    • AT&T ви читаєте INSTR SRC DEST.
    • Intel ви читаєте INSTR DEST SRC.

    • Є й ряд інших відмінностей. Якщо ваш мозок натренований, то можна без особливих зусиль переключатися з однієї моделі на іншу. Це всього лише синтаксис, нічого більше.
    • Частіше використовується AT&T, хто віддає перевагу Intel. Стосовно X86 в моделі AT&T за замовчуванням використовується GDB. Детальніше про моделі AT&T.
  • X86_64 застосовується порядок проходження байтів від молодшого до старшого (little-endian), так що готуйтеся перетворювати адреси по мірі читання. Завжди групуйте побайтно.
  • X86_64 не дозволені операції «пам'ять-пам'ять». Для обробки даних потрібно використовувати який-небудь регістр.
  • $ означає статичне безпосереднє значення (наприклад, $1 — це значення '1').
  • % означає доступ до регістру (%eax — доступ до регістра EAX).
  • Круглі дужки — доступ до пам'яті, зірочка З разыменовывает покажчик (запис (%eax) означає доступ до області пам'яті, адреса якої зберігається в регістрі EAX).
Регістри
Регістри — це області пам'яті фіксованого розміру в чіпі процесора. Це не оперативна пам'ять! Регістри працюють набагато швидше RAM. Якщо доступ до оперативці виконується приблизно за 100 нс (в обхід усіх рівнів кеша), то доступ до регістру — за 0 нс. Найголовніше в програмуванні процесора — це розуміти сценарій, який повторюється раз за разом:

  • З оперативної пам'яті в регістр вантажаться дані: тепер процесор «володіє» значенням.
  • З регістром виконується що-небудь (наприклад, його значення множиться на 3).
  • Вміст регістра відправляється назад в оперативну пам'ять.
  • Якщо хочете, то можна переміщувати дані з регістра в інший регістр того ж розміру.
Нагадую, що в X86_64 не можна виконувати звернення «пам'ять-пам'ять»: спочатку потрібно передати дані в регістр.

Існують десятки регістрів. Найчастіше використовуються регістри загального призначення» — для обчислень. В архітектурі X86_64 доступні наступні універсальні регістри: a, b, c, d, di, si, 8, 9, 10, 11, 12, 13, 14 і 15 (32-бітної X86 набір інший).

Всі вони 64-бітні (8 байтів), АЛЕ до них можна звертатися в чотирьох режимах: 64-, 32-, 16 — і 8-бітному. Все залежить від ваших потреб.

Регістр A — 64-бітний доступ. RAX — 32-бітний. EAX — 16-бітовий. AX — 8-бітний. Молодша частина: AL, старша частина: AH.



Все дуже просто. Процесор — це дурний шматок кремнію, він виконує лише найпростіші операції з крихітними порціями байтів. В регістрах загального призначення можна звертатися мінімум до байту, а не біту. Короткий словник:

  • Один байт = 8 біт це найменший доступне кількість інформації. Позначається як BYTE.
  • Подвійний байт = 16 бітів, позначається як WORD.
  • подвійний Подвійний байт = 32 біта, позначається як DWORD (подвійний WORD).
  • 8 суміжних байт = 64 біта, позначається як QWORD (четверний WORD).
  • 16 суміжних байт = 128 бітів, позначається як DQWORD (подвійний четверний WORD).
Більше інформації про архітектуру X86 можна знайти на http://sandpile.org/ і сайтах Intel/AMD/Microsoft. Нагадую: X86_64 працює дещо інакше, ніж X86 (32-бітний режим). Також почитайте вибіркові матеріали з манулов Intel.

Аналіз коду X86_64
00400afc: jmp 0x400b26 

JMP — це безумовний перехід (unconditional jump). Перейдемо за адресою 0x400b26:

00400b26: lea -0x420(%rbp),%rcx
00400b2d: mov -0xc(%rbp),%eax
00400b30: mov $0x400,%edx
00400b35: mov %rcx,%rsi
00400b38: mov %eax,%edi
00400b3a: callq 0x4005d0 < read@plt>

У цьому коді робиться системний виклик
read()
. Якщо ви почитаєте конвенцію викликів в X86_64, то побачите, що більшість параметрів передаються не стеком, а регістрами. Це підвищує продуктивність виклику кожної функції в X86_64 Linux в порівнянні з 32-бітним режимом, коли для кожного виклику використовується стек.

Згідно таблиці системних викликів ядра,
read(int fd, char *buf, size_t buf_size)
перший параметр (дескриптор файлу) повинен бути переданий в RDI, другий (буфер для заповнення) — RSI, а третій (розмір буфера для заповнення) — у RDX.

Розглянемо вищенаведений код. Тут використовується RPB (Register Base Pointer, покажчик базового регістра). RBP запам'ятовує саме початку простору поточного стека, в той час як RSP (Stack Pointer Register, покажчик стека регістра) запам'ятовує вершину поточного стека, на випадок, якщо нам знадобиться з цим стеком щось зробити. Стек — це просто великий шматок пам'яті, виділений для нас. Він містить локальні змінні функції, змінні
alloca()
, адреса повернення, може містити аргументи функцій, якщо їх кілька штук.

В стеці зберігаються локальні змінні функції
main()
, в якій ми зараз знаходимося:

00400b26: lea -0x420(%rbp),%rcx


LEA (Load Effective Address) зберігається в RBP мінус 0x420, аж до RCX. Це наша мінлива буфера —
buf
. Зверніть увагу, що LEA не зчитує значення після адреси, тільки сама адреса. Під GDB ви можете надрукувати будь-яке значення і виконати обчислення:

> (gdb) p $rbp - 0x420
$2 = (void *) 0x7fffffffddc0

За допомогою
info registers
можна відобразити будь-який регістр:

> (gdb) info registers
rax 0x400a60 4196960
rbx 0x0 0
rcx 0x0 0
rdx 0x7fffffffe2e0 140737488347872
rsi 0x7fffffffe2c8 140737488347848
... ...

Продовжуємо:

00400b2d: mov -0xc(%rbp),%eax

Помістимо значення за адресою, вказаною в RBP мінус 0xc — в EAX. Швидше за все, це наша мінлива
f 
. Це можна легко підтвердити:

> (gdb) p $rbp - 0xc
$1 = (void *) 0x7fffffffe854
> (gdb) p &f
$3 = (int *) 0x7fffffffe854

Йдемо далі:

00400b30: mov $0x400,%edx

Помістимо в EDX значення 0x400 (1024 в десятковому вираженні). Це
sizeof(buf)
: 1024, третій параметр
read()
.

00400b35: mov %rcx,%rsi
00400b38: mov %eax,%edi
00400b3a: callq 0x4005d0 < read@plt>

Запишемо вміст RCX в RSI, другий параметр
read()
. Запишемо вміст EAX в EDI, третій параметр
read()
. Потім викличемо функцію
read()
.

При кожному системному виклику його значення повертається в регістр A (іноді ще й в D).
read()
повертає значення
ssize_t
, яка важить 64 біта. Отже, для читання повертається нам потрібно проаналізувати весь регістр A. Для цього скористаємося RAX (64-бітове читання регістра A):

00400b3f: mov %rax,-0x18(%rbp)
00400b43: cmpq $0x0-0x18(%rbp)
00400b48: jg 0x400afe < main+158>

Запишемо повертає значення
read()
з RAX за адресою, вказаною в RBP мінус 0x18. Швидка перевірка підтверджує, що це наша мінлива
readed
З-коду.

CMPQ (Compare Quad-Word, порівняння четверного WORD). Порівнюємо значення
readed
зі значенням 0.

JG (Jump if greater, перехід за умовою «більше»). Переходимо за адресою 0x400AFE. Це всього лише порівняння в циклі
while()
з нашого З-коду.

Продовжуємо читати буфер і переходимо за адресою 0x400AFE, це має бути початок циклу
for()
.

00400afe: movl $0x0-0x4(%rbp)
00400b05: jmp 0x400b1b < main+187>

MOVL (Move a Long, копіювання довгого цілого). Записуємо LONG (32 біта) значення 0 за адресою, вказаною в RBP мінус 4. Це
i
— цілочисельна змінна C-коді, 32 біта, тобто 4 байти. Потім вона буде збережена як найперша змінна в стековому фреймі
main()
(представленому RBP).

Переходимо за адресою 0x400B1B, тут має бути продовження циклу
for()
.

00400b1b: mov -0x4(%rbp),%eax
00400b1e: cltq 
00400b20: cmp -0x18(%rbp),%rax
00400b24: jl 0x400b07 

Записуємо в EAX значення, вказане в RBP мінус 4 (ймовірно, ціле число).

CLTQ (Convert Long To Quad). CLTQ працює з регістром A. Він розширює EAX до 64-бітного цілочисельного значення, одержуваного RAX.

CMP (Compare value, порівняння значення). Порівнюємо значення в RAX зі значенням, на яке вказується за адресою в RBP мінус 0x18. Тобто порівнюємо змінну
i
з циклу
for()
з змінної
readed
.

JL (Jump if Lower, перехід за умовою «менше»). Переходимо за адресою 0x400B07. Ми на першому етапі циклу
for()
, так що так, переходимо.

00400b07: mov -0x4(%rbp),%eax
00400b0a: cltq 
00400b0c: movzbl -0x420(%rbp,%rax,1),%eax
00400b14: add %al,-0x5(%rbp)
00400b17: addl $0x1,-0x4(%rbp)
00400b1b: mov -0x4(%rbp),%eax
00400b1e: cltq 
00400b20: cmp -0x18(%rbp),%rax
00400b24: jl 0x400b07 < main+167>

А тепер найцікавіше.

Записуємо (MOV)
i
в EAX (як говорилося вище,
i
— це –0x4(%rbp)). Потім робимо CLTQ: розширюємо до 64 біт.

MOVZBL (MOV Zero-extend Byte to Long). Додаємо нульовий байт до довгого цілого, що зберігається за адресою (1*RAX+RBP) мінус 0x420, і записуємо в EAX. Звучить складно, але це просто математика ;-) Виходить обчислення
buf[i]
з допомогою однієї інструкції. Так ми проілюстрували можливості покажчиків у мові C:
buf[i] — це buf + i*sizeof(buf[0])
байтів. Одержаний адреса легко обчислюється на асемблері, а компілятори виконують купу математичних обчислень, щоб згенерувати таку інструкцію.

Завантаживши значення EAX, ми додаємо його в
result
:

00400b14: add %al,-0x5(%rbp)

Пам'ятайте: AL — молодший байт 8-байтного RAX (RAX і AL являють собою регістр A) — це
buf[i]
, оскільки
buf
відноситься до типу char і важить один байт.
result
знаходиться за адресою –0x5(%rbp): один байт після
i
, розташованого на відстані 0x4 від RBP. Це підтверджує, що
result
— це char, що важить один байт.

00400b17: addl $0x1,-0x4(%rbp)


ADDL (Add a long, додавання довгого цілого — 32 біта). Додаємо 1 до
i


І знову повертаємося до інструкції 00400b1b: цикл
for()
.

Короткий підсумок
Втомилися? Це тому, що у вас немає досвіду в асемблері. Як ви могли переконатися, розшифровка асемблера — це всього лише арифметика на рівні початкової школи: скласти, витягти, помножити, поділити. Так, асемблер простий, але дуже багатослівний. Відчуваєте різницю між «важкий» і «багатослівний»?

Якщо ви хочете, щоб ваша дитина стала хорошим програмістом, то не робіть помилки і не обмежуйте його вивченням математики тільки з основою 10. Тренуйте його переключатися з однієї підстави на інше. Фундаментальну алгебру можна повністю зрозуміти тільки тоді, коли ви можете представити будь-які величини з будь-якою підставою, особливо 2, 8 і 16. Для навчання дітей рекомендую використовувати соробан.

Якщо ви відчуваєте себе в математиці не надто впевнено, то лише тому, що ваш мозок завжди натаскували тільки на операції з основою 10. Перемикатися з 10 на 2 важко, тому що ці міри не кратні. А перемикатися між 2 і 16 або 8 легко. Потренувавшись, ви зможете обчислювати більшість адрес в розумі.

Отже, нашому цикл
for()
потрібно шість адрес пам'яті. Він був перетворений як є з вихідного C-коду: цикл виконується для кожного байта з побайтным підсумовуванням. Для одногигабайтного файлу цикл доводиться виконувати 0x40000000 разів, тобто 1 073 741 824.

Навіть на 2 ГГц (CISC одна інструкція != один цикл) прогін циклу 1 073 741 824 рази забирає досить часу. У результаті код виконується близько 3 секунд, тому що побайтное підсумовування в ліченому файлі вкрай неефективно.

Давайте всі векторизуем з допомогою SIMD
SIMD — Single Instruction Multiple Data, одна інструкція, множинний потік даних. Цим все сказано. SIMD являє собою спеціальні інструкції, що дозволяють процесору працювати не з одним байтом, одним WORD, одним DWORD, а з декількома з них в рамках однієї інструкції.

Зустрічайте SSE — Streaming SIMD Extensions, потокове SIMD-розширення. Вам напевно знайомі такі абревіатури, як SSE, SSE2, SSE4, SSE4.2, MMX або 3DNow. Так от, SSE — це SIMD-інструкції. Якщо процесор може одночасно працювати з численними даними, то це істотно зменшує загальну тривалість обчислень.



При купівлі процесора звертайте увагу не тільки на кількість ядер, розмір кешей і тактову частоту. Важливий ще набір підтримуваних інструкцій. Що ви оберете: складати кожну наносекунду один байт за іншим або додавати 8 байтів до 8 кожні дві наносекунди?

SIMD-інструкції дозволяють дуже сильно прискорювати обчислення в процесорі. Вони використовуються скрізь, де допускається паралельна обробка інформації. Деякі з сфер застосування:

  • Матричні обчислення, що лежать в основі графіки (але GPU робить це на порядок швидше).
  • Стиснення даних, коли за раз обробляється за кілька байтів (формати LZ, GZ, MP3, Divx, H264/5, JPEG FFT і багато інших).
  • Криптографія.
  • Розпізнавання мови і музики.
Візьмемо, приміром, оцінку параметрів руху (Motion Estimation) з допомогою Intel SSE 4. Це критично важливий алгоритм використовується в кожному сучасному видеокодеке. Він дозволяє на основі векторів руху, обчислених за базовим кадру F, передбачити кадр F+1. Завдяки цьому можна програмувати тільки переміщення пікселів від одного зображення до іншого, а не кодувати картинки цілком. Яскравий приклад — чудові кодеки H264 і H265, у них відкритий вихідний код, можете його вивчити (тільки спочатку прочитайте про MPEG).

Проведемо тест:

> cat /proc/cpuinfo
processor : 2
vendor_id : GenuineIntel
cpu family : 6
model : 58
model name : Intel® Core(TM) i5-3337U CPU @ 1.80 GHz
(...)
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm ida arat epb xsaveopt pln pts dtherm tpr_shadow vnmi flexpriority ept vpid fsgsbase smep erms

Всі ці прапори — здебільшого підтримувані моїм процесором інструкції та набори інструкцій.

Тут можна побачити sse, sse2, sse4_1, sse4_2, aes, avx.

AES лежить в основі AES-шифрування! Прямо в CPU, за допомогою купи спеціалізованих інструкцій.

SSE4.2 дозволяє однією інструкцією обчислити контрольну суму CRC32, а за допомогою декількох інструкцій — порівнювати рядкові значення. Найсвіжіші функції
str()
в бібліотеці libC засновані на SSE4.2, тому ви можете так швидко грепать слово з гігантського тексту.

SIMD нам допоможе
Настав час поліпшити нашу З-програму за допомогою SIMD і подивитися, чи стане вона швидше.

Все почалося з технологією MMX, яка додавала 8 нових 64-бітних регістрів, від MM0 до MM7. MMX з'явилася в кінці 1990-х, почасти через неї Pentium 2 і Pentium 3 коштували дуже дорого. Тепер ця технологія абсолютно неактуальна.

Різні версії SSE, аж до останньої SSE4.2 з'являлися в процесорах приблизно з 2000-го по 2010-й. Кожна наступна версія сумісна з попередніми.



Сьогодні найбільш поширена версія — SSE4.2. У ній додано 16 нових 128-бітних регістрів (X86_64): з XMM0 за XMM15. 128 бітів = 16 байтів. Тобто, заповнивши SSE-регістр і виконавши з ним якийсь обчислення, ви обробите відразу 16 байтів.



А якщо обробити два SSE-регістра, то це вже 32 байта. Стає цікаво.

З 16 байтами на регістр ми можемо зберігати (розміри LP64):

  • 16 байтів: шістнадцять C-символів.
  • Два 8-байтних значення: два довгих значення З або два числа з подвійною точністю (double precision float).
  • Чотири 4-байтних значення: чотири цілих або чотири числа з одинарною точністю (single precision float).
  • Вісім 2-байтних значення: вісім коротких значень C.
Наприклад:



SIMD також називають «векторними» інструкціями, тому що вони працюють з «вектором» — областю, заповненої різними дрібними об'єктами. Векторна інструкція одночасно опрацьовує різні дані, в той час як скалярна інструкція — тільки одну порцію даних.

У нашій програмі можна реалізувати SIMD двома способами:

  • Написати на асемблері код, який працює з цими регістрами.
  • Використовувати Intel Intrinsics — API, що дозволяє писати C-код, що при компіляції перетворюється в SSE-інструкції.
Я покажу вам другий варіант, а перший зробите самі в якості вправи.

Пропатчим наш код:

#include < stdio.h>
#include <stdint.h>
#include < string.h>
#include <fcntl.h>
#include <unistd.h>
#include <tmmintrin.h>

#define BUF_SIZE 1024

int main(int argc, char **argv)
{
int f, i;
ssize_t readed;
__m128i r = _mm_set1_epi8(0);

unsigned char result = 0;
unsigned char buf[BUF_SIZE] __attribute__ ((aligned (16))) = {0};

if (argc != 2) {
fprintf(stderr, "Використання: %s \n", argv[0]);
exit(-1);
}

f = open(argv[1], O_RDONLY);

if (f == -1) {
perror("Не можу відкрити файл");
}

while ((readed = read(f, buf, sizeof(buf))) > 0) {
for (i=0; i < readed; i+=16) {
__m128i a = _mm_load_si128((const __m128i *)(buf+i));
r = _mm_add_epi8(a, r);
}
memset(buf, 0, sizeof(buf));
}

for (i=0; i<16; i++) {
result += ((unsigned char *)&r)[i];
}

close(f);

printf("Читання завершено, сума дорівнює %u \n", result);

return 0;
}

Бачите новий заголовок tmmintrin.h? Це інтеловський API. Для нього є прекрасна документація.

Для зберігання результату підсумовування (накопичувального) я вирішив використовувати тільки один SSE-регістр і заповнювати його рядком з пам'яті. Ви можете вчинити інакше. Наприклад, взяти відразу 4 регістра (або взагалі все), і тоді ви будете підсумувати 256 байтів у 16 операціях :D
Пам'ятайте розміри SSE-регістрів? Наша мета — підсумувати байти. Це означає, що ми будемо використовувати в регістрі 16 окремих байтів. Якщо почитаєте документацію, то дізнаєтеся, що існує багато функцій для «упаковки» та «розпакування» значень в регістрах. Нам вони не знадобляться. У нашому прикладі не потрібно перетворювати 16 байтів до 8 WORD або 4 БАЙТИ. Нам потрібно просто порахувати суму. І в цілому SIMD дає набагато більше можливостей, ніж описано в цій статті.

Отже, тепер замість побайтового складання ми будемо складати по 16 байт.

В одній інструкції ми опрацюємо набагато більше даних.

__m128i r = _mm_set1_epi8(0);


Попередній вираз готує XMM-регитр (16 байтів) і заповнює його нулями.

for (i=0; i < readed; i+=16) {
__m128i a = _mm_load_si128((const __m128i *)(buf+i));
r = _mm_add_epi8(a, r);
}

Кожен цикл
for()
тепер повинен збільшувати буфер не на 1 байт, а на 16. Тобто
i+=16
.

Тепер звертаємося до буфера пам'яті
buf+i
і наводимо його на покажчик
__m128i*
. Таким чином ми беремо з пам'яті порції по 16 байтів. За допомогою
_mm_load_si128()
записуємо ці 16 байтів в змінну
a
. Байти записуються в XMM-регістр як «16*один байт».

Тепер з допомогою
_mm_add_epi8()
додаємо 16-байтний вектор до нашого акумулятору
r
. І починаємо проганяти в циклах з 16 байтів.

В кінці циклу останні байти залишаються в регістрі. На жаль, немає простого способу додати їх горизонтально. Це можна робити для WORD, DWORD і так далі, але не для байтів! Наприклад, погляньте на
_mm_hadd_epi16()
.

Так що будемо працювати вручну:

for (i=0; i<16; i++) {
result += ((unsigned char *)&r)[i];
}

Готове.

Компілюємо і профілюємо:

> gcc -Wall -g -O0 -o file_sum file_sum.c
> time ./file_sum /tmp/test 
Read out, sum is 186 

real 0m0.693s
user 0m0.360s
sys 0m0.328s

Близько 700 мс. C 3000 мс при класичному побайтовом підсумовуванні ми впали до 700 при підсумовуванні по 16 байт.

Давайте дизассемблируем код циклу
while()
, адже решті код не змінився:

00400957: mov -0x34(%rbp),%eax
0040095a: cltq 
0040095c: lea -0x4d0(%rbp),%rdx
00400963: add %rdx,%rax
00400966: mov %rax,-0x98(%rbp)
0040096d: mov -0x98(%rbp),%rax
00400974: movdqa (%rax),%xmm0
00400978: movaps %xmm0,-0x60(%rbp)
0040097c: movdqa -0xd0(%rbp),%xmm0
00400984: movdqa -0x60(%rbp),%xmm1
00400989: movaps %xmm1,-0xb0(%rbp)
00400990: movaps %xmm0,-0xc0(%rbp)
00400997: movdqa -0xc0(%rbp),%xmm0
0040099f: movdqa -0xb0(%rbp),%xmm1
004009a7: paddb %xmm1,%xmm0
004009ab: movaps %xmm0,-0xd0(%rbp)
004009b2: addl $0x10,-0x34(%rbp)
004009b6: mov -0x34(%rbp),%eax
004009b9: cltq 
004009bb: cmp -0x48(%rbp),%rax
004009bf: jl 0x400957

Треба пояснювати? Помітили
%xmm0
та
%xmm1
? Це використовувані SSE-регістри. Як ми з ними зробимо?

Ми виконуємо MOVDQA (MOV Double Quad-word Aligned) і MOVAPS (MOV Aligned Packed Single-Precision). Ці інструкції роблять одне і те ж: переміщують 128 біт (16 байтів). А навіщо тоді дві інструкції? Я не можу цього пояснити без докладного розгляду архітектури CISC, суперскалярного движка і внутрішнього конвеєра.

Далі ми виконуємо PADDB (Packed Add Bytes): складаємо один з одним два 128-бітових регістра в одній інструкції!

Мета досягнута.

Про AVX
AVX (Advanced Vector extensions) — це майбутнє SSE. Можна вважати AVX чимось на зразок SSE++, начебто SSE5 або SSE6.

Технологія з'явилася в 2011-му разом з архітектурою Intel Sandy Bridge. І як SSE витіснила MMX, так тепер AVX витісняє SSE, яка перетворюється в «стару» технологію, притаманну процесорам, з десятиліття 2000-2010.

AVX збільшує можливості SIMD, розширюючи XMM-регістри до 256 біт, тобто 32 байтів. Наприклад, до регістру XMM0 можна звертатися як до YMM0. Тобто регістри залишилися ті ж, просто були розширені.



AVX-інструкції можна використовувати з XMM-регістрами з SSE, але тоді будуть працювати тільки молодші 128 бітів відповідних YMM-регістрів. Це дозволяє комфортно переносити код з SSE в AVX.

Також в AVX з'явився новий синтаксис: для одного місця призначення опкоды можуть брати до трьох вихідних аргументів. Місце призначення може відрізнятися від джерела, у той час як в SSE воно було одним з джерел, що призводило до «деструктивним» обчислень (якщо регістр пізніше повинен був стати місцем призначення для опкода, то доводилося зберігати вміст регістра, перш ніж виконувати над ними обчислення). Наприклад:

VADDPD %ymm0 %ymm1 %ymm2 : Додає числа з плаваючою комою з подвійною точністю з ymm1 в ymm2 і кладе результат в ymm0


Також AVX дозволяє у формулі MNEMONIC DST SRC1 SRC2 SRC3 мати в якості адреси пам'яті один SRC або DST (але не більше). Отже, багато AVX-інструкції (не всі) можуть працювати прямо з пам'яті, без проміжної завантаження даних в регістр, а багато здатні працювати з трьома джерелами, не тільки з двома.

Нарешті, в AVX є чудові FMA-інструкції. FMA (Fused Multiply Add) дозволяє однією інструкцією виконувати такі обчислення: A = (B * C) + D.

Про AVX2
У 2013 році разом з архітектурою Haswell з'явилася технологія AVX2. Вона дозволяє додавати байти в 256-бітні регістри. Як раз те, що потрібно для нашої програми. На жаль, в AVX1 цього немає. При роботі з 256-бітними регістрами AVX може виконувати операції тільки з числами з плаваючою комою (з половинною, одинарною або подвійною точністю) і з цілочисельними. Але не з поодинокими байтами!

Пропатчим нашу програму, щоб використовувати AVX2 і нову інструкцію VPADDB, добавляющую байти з YMM-регістрів (щоб складати по 32 байти). Зробіть це самостійно, тому що мій процесор занадто старий і не підтримує AVX2.
Мануали по AVX і AVX2 можна скачати тут.

Про AVX-512
За станом на кінець 2016 року технологія AVX-512 призначена для «професійних» процесорів Xeon-Phi. Є ймовірність, що до 2018 року вона потрапить і на споживчий ринок.

AVX-512 знову розширює AVX-регістри, з 256 до 512 бітів, тобто 64 байтів. Також додається 15 нових SIMD-регістрів, так що стає доступно в сумі 32 512-бітових регістра. Звертатися до старших 256 біт можна через нові ZMM-регістри, половина обсягу яких доступна YMM-регістрів з AVX, а половина обсягу YMM-регістрів доступна XMM-регістрів з SSE.

Інформація від Intel.

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

SIMD скрізь?
У SIMD є недоліки:

  • Необхідно ідеально вирівнювати дані в області пам'яті.
  • Не кожен код допускає таке розпаралелювання.
Спочатку про вирівнювання. Процесор може звертатися до області пам'яті для завантаження 16 байтів, якщо адреса не ділиться на 16? Та ніяк (в одній інструкції зразок MOV).

Конструктор Lego дозволяє добре проілюструвати концепцію вирівнювання даних в пам'яті комп'ютера.



Бачите проблему? Тому я використовую в З-коді:

unsigned char buf[BUF_SIZE] __attribute__ ((aligned (16))) = {0};

щоб комп'ютер зберігав
buf
в стек за адресою, який ділиться на 16.

SIMD можна використовувати і з невыравненными даними, але за це доведеться розплачуватися так дорого, що краще взагалі не вдаватися до SIMD. Ви просите процесор завантажити дані за адресою Х, потім за адресою Y, потім видалити байти з Х, потім з Y, потім вставити поруч дві області пам'яті. Ні в які ворота не лізе.

Детальніше про вирівнювання:

Зверніть увагу, що вирівнювати дані в пам'яті рекомендується при роботі з «класичним» С. Цю методику ми використовуємо і в PHP. Будь автор серйозної З-програми звертає увагу на вирівнювання і допомагає компілятору генерувати більш якісний код. Іноді компілятор може «припускати» і вирівнювати буфери, але при цьому часто використовується динамічна пам'ять (купа), і потім доводиться наводити порядок, якщо вас хвилює падіння продуктивності при кожному зверненні до пам'яті. Це особливо характерно для розробки структур.

Інша проблема, пов'язана з SIMD, ваші дані повинні бути придатні для розпаралелювання. Додаток повинен передавати дані в процесор в паралельних потоках. В іншому випадку компілятор згенерує класичні регістри та інструкції, без використання SIMD. Однак не кожен алгоритм можна розпаралелити.

Загалом, за SIMD доведеться заплатити певну ціну, але вона не надто велика.

Боремося з компілятором: включаємо оптимізацію та автовекторизацию
На початку статті я говорив про половину секунди на підсумовування байтів. Але у нас зараз 700 мс, це ніяк не 500!

Є один трюк.

Згадайте, як ми компілювали наш З-код. Ми відключили оптимізації. Не буду вдаватися в подробиці про них, але має відношення до PHP статті я розповідав, як розширення OPCache може чіплятися до PHP-компілятор і виконувати оптимізаційні проходи у створеному коді.

Тут все те ж саме, але пояснювати занадто складно. Оптимізувати код непросто, це величезна тема. Погуглите деякі терміни і отримаєте приблизне уявлення.
Спрощено: якщо наказати компілятору згенерувати оптимізований код, то він напевно оптимізує його краще за вас. Тому ми використовуємо більш високорівнева мова (в даному випадку — З) і компілятор.

З-існують компілятори з 1970-х років. Їх відточували близько 50 років. У якихось дуже рідкісних і специфічних випадках ви зможете оптимізувати краще, але і тільки. При цьому вам доведеться ідеально розбиратися в асемблері.

Однак потрібно знати, як компілятор працює, щоб розуміти, чи можна оптимізувати ваш код. Є багато рекомендацій, які допомагають компілятору генерувати більш якісний код. Почніть вивчати питання звідси.

Скомпилируем першу версію нашої програми — побайтное складання без використання Intrinsics — з повною оптимізацією:

> gcc -Wall -g -O3 -o file_sum file_sum.c
> time ./file_sum /tmp/test 
Read out, sum is 186 

real 0m0.416s
user 0m0.084s
sys 0m0.316s

Загальний час всього 416 мс, а підсумовування байтів зайняло лише 84 мс, тоді як на системні виклики та доступ до диска витрачено аж 316 мс.

Мда.

Дизассемблируем. Повний код можна подивитися тут.

Цікавий шматок:

00400688: mov %rcx,%rdi
0040068b: add $0x1,%rcx
0040068f: shl $0x4,%rdi
00400693: cmp %rcx,%rdx
00400696: paddb 0x0(%rbp,%rdi,1),%xmm0
0040069c: ja 0x400688 
0040069e: movdqa %xmm0,%xmm1
004006a2: psrldq $0x8,%xmm1
004006a7: paddb %xmm1,%xmm0
004006ab: movdqa %xmm0,%xmm1
004006af: psrldq $0x4,%xmm1
004006b4: paddb %xmm1,%xmm0
004006b8: movdqa %xmm0,%xmm1
004006bc: psrldq $0x2,%xmm1
004006c1: paddb %xmm1,%xmm0
004006c5: movdqa %xmm0,%xmm1
004006c9: psrldq $0x1,%xmm1
004006ce: paddb %xmm1,%xmm0
004006d2: movaps %xmm0,(%rsp)
004006d6: movzbl (%rsp),%edx
(...) (...) (...) (...)

Проаналізуйте його самі. Тут компілятор використовує багато трюків, щоб підвищити ефективність програми. Наприклад, розвертає назад (unroll) цикли, певним чином розподіляє байти по регістрах, передаючи побайтно одні і зрушуючи інші.
Але тут точно згенеровані SIMD-інструкції, оскільки наш цикл можна «векторизовать» — перетворити в векторні інструкції SIMD.

Спробуйте проаналізувати весь код цілком, і ви побачите, наскільки розумно компілятор підійшов до вирішення завдання. Він знає ціну кожній інструкції. Він може організувати їх так, щоб вийшов найкращий код. Тут можна почитати про кожній оптимізації, виконуваної GCC на кожному рівні.

Найважчий рівень — O3, він включає «векторизацію дерево — цикл», «векторизацію дерево — slp», а також розмикає цикли.

За замовчуванням використовується тільки O2, тому що з-за занадто агресивної оптимізації O3 програми можуть демонструвати несподіване поведінку. Також в компіляторах бувають баги, як і в процессорах. Це може призвести до багам в генерованому коді або до несподіваного поведінки, навіть у 2016 році. Я з таким не стикався, але нещодавно знайшов баг в GCC 4.9.2, що впливає на PHP з -O2. Також згадується баг в управлінні FPU.

Візьмемо в якості прикладу PHP. Скомпилируем його без оптимізації (-O0) і запустимо бенчмарк. Потім порівняємо з -O2 і -O3. Бенчмарк повинен просто перегрітися через агресивних оптимізацій.

Однак -O2 не активує автовекторизацию. Теоретично при використанні -O2 GCC не повинен генерувати SIMD. Дратує факт, що кожна програма у вигляді Linux-пакета за замовчуванням скомпільована з -O2. Це як мати дуже потужне обладнання, але не використовувати його можливості цілком. Але ми ж професіонали. Ви знаєте, що комерційні Linux-дистрибутиви можуть поширюватися з програмами, які при компіляції сильно оптимізуються під обладнання, з яким поширюються? Так роблять багато компаній, у тому числі IBM і Oracle.

Ви теж можете самостійно компілювати їх з вихідних кодів, використовуючи -O3 або -O2 з потрібними прапорами. Я використовую -march=native для створення ще більш спеціалізованого коду, більш продуктивного, але менш портируемого. Але він іноді працює нестабільно, так що ретельно тестуйте і готуйтеся до сюрпризів.

Крім GCC, є й інші компілятори, наприклад LLVM або ICC (від Intel). gcc.godbolt.org можна в онлайні протестувати всі три. Компілятор Intel генерує кращий код для процесорів Intel. Але GCC і LLVM швидко наздоганяють, до того ж у вас можуть бути свої ідеї щодо методики тестування компіляторів, різних сценаріїв і кодових баз.

Працюючи з вільним ПЗ, ви вільні. Не забувайте: вас ніхто не буде підбадьорювати.

Ви ж не купуєте комерційну суперпрограмму, яка невідомо як скомпільована, і якщо її розбирати, то можна потрапити у в'язницю, оскільки це заборонено в багатьох країнах. Або ви все це зробили? Ой.

PHP?
А при чому тут взагалі PHP? Ми не кодим PHP на асемблері. При генеруванні коду ми повністю покладаємося на компілятор, тому що хочемо, щоб код був портуємо на різні архітектури та ОС, як і будь-яка З-програма.

Однак ми намагаємося використовувати добре перевірені хитрощі, щоб компілятор генерував більш ефективний код:

  • Багато структури даних в PHP вирівняні. Диспетчер пам'яті, виконує розміщення куп, завжди виправить на ваше прохання буфер. Подробиці.
  • Ми використовуємо alloca() тільки там, де вона працює краще купи. Для старих систем, які не підтримують alloca(), у нас є власний емулятор.
  • Ми використовуємо вбудовані команди GCC. Наприклад, __builtin_alloca(), __builtin_expect() і __builtin_clz().
  • Ми підказуємо компілятору, як використовувати регістри для основних обробників віртуальної машини Zend Virtual. Подробиці.
В PHP ми не використовуємо JIT (ще не розробили). Хоча плануємо. JIT — це спосіб генерування асемблерного коду «на льоту», по мірі виконання деяких машинних інструкцій. JIT покращує продуктивність віртуальних машин, таких як PHP (Zend), але при цьому поліпшення стосуються тільки повторюваних обчислювальних патернів. Чим більше ви повторюєте низькорівневі патерни, тим корисніше JIT. Оскільки сьогодні PHP-програми складаються з великої кількості різноманітних PHP-інструкцій, JIT оптимізує тільки важкі процеси, які обробляють великі обсяги даних в секунду протягом довгого часу. Але для PHP така поведінка нехарактерно, тому що він намагається обробляти запити як можна швидше і делегувати «важкі» завдання іншим процесам (асинхронним). Так що PHP може виграти від впровадження JIT, але не настільки, як та ж Java. Принаймні, не як веб-технологія, а при використанні в якості CLI. CLI-скрипти сильно покращаться, на відміну від Web PHP.

При розробці PHP ми рідко звертаємо увагу на згенерований асемблерний код. Але іноді ми це робимо, особливо зіткнувшись з несподіваною поведінкою», не належать до С. Це може говорити про ба компілятора.

Трохи не забув про SIMD-розширення Джо для PHP. Не поспішайте засуджувати: це перевірка концепції, але зате хороша перевірка.

У мене є багато ідей щодо PHP-розширень, пов'язаних з SIMD. Наприклад, я хочу перенести на частину проекту math-php і впровадити SIMD. Можна зробити розширення з публічними структурами, що дозволяють PHP-користувачам застосовувати SIMD для лінійних алгебраїчних обчислень. Можливо, це допоможе комусь створити повноцінну відеогру на PHP.

Висновок
Отже, ми почали зі створення простенької програми на С. Побачили, що компілювання без оптимізацій призвело до генерування дуже зрозумілого і дружнього до GDB асемблерного коду, при цьому вкрай неефективне. Другий рівень оптимізації за замовчуванням в GCC не передбачає включення автовекторизации, а отже, не генерує SIMD-інструкції. З використанням -O3 GCC по продуктивності перевершив результати від реалізації нашої SIMD.

Також ми побачили, що наша реалізація SIMD — всього лише перевірка концепції. Для подальшого поліпшення продуктивності ми могли б вдатися до AVX і ряду інших регістрів. Також при доступі до файлу можна було б використовувати mmap(), але в сучасних ядрах це не дало ефекту.

Створюючи код, ви покладаєте роботу на компілятор, тому що він її зробить краще за вас. Змиріться з цим. В яких випадках ви можете взяти кермо влади в свої руки і написати асемблерний код безпосередньо або з допомогою API Intel Intrinsics. Також кожен компілятор приймає «розширення» з мови, які допомагають створити бажаний код. Список GCC-розширень.

Хтось віддає перевагу використовувати Intel Intrinsics, хто сам пише асемблерний код і вважає, що так простіше. Дійсно нескладно вставляти асемблерні інструкції З-програму, це дозволяє робити кожен компілятор. Або можна написати один файл проекту на асемблері, інші на С.

Взагалі З — дійсно класний мову. Він старий і мало змінився за 45 років, що доводить його стійкість, а значить, наше залізо працює на твердому фундаменті. У З є конкуренти, але він справедливо займає левову частку ринку. На ньому написані всі галузеві системи, які ми сьогодні використовуємо. Так, тепер у нас більше потоків, кілька ядер і ряд інших проблем начебто NUMA. Але процесори раніше обробляють так само, як і раніше, і тільки неймовірно талановиті інженери Intel і AMD примудряються слідувати закону Мура: тепер ми можемо використовувати дуже спеціалізовані інструкції, одночасно обробляючи багато даних.

Я написав цю статтю, тому що нещодавно зустрів талановитих фахівців, які повністю ігнорують все, що тут написано. Я подумав, що вони багато втрачають і навіть не розуміють цього. Ось і вирішив поділитися своїми знаннями про те, як виконуються низькорівневі обчислення.

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

Корисні посилання:

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.