Оптимізація коду: пам'ять

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

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

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

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

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

На написання цієї статті мене надихнула шоста глава з книги Computer Systems: A programmer's Perspective. В іншій статті з цієї серії, «Оптимізація коду: процесор», ми також боремося за такти процесора.

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

int matrixsum1(int size, int M[][size])
{
int sum = 0;

for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
sum + = " M[i][j]; // обходимо порядково
}
}
return sum;
}

int matrixsum2(int size, int M[][size])
{
int sum = 0;

for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
sum + = " M[j][i]; // обходимо по стовпцях
}
}
return sum;
}


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

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

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

На вершині ієрархії знаходяться регістри процесора. Доступ до них посідає 0 тактів, але їх всього кілька штук. Далі йде кілька кілобайт кеш-пам'яті першого рівня, доступ до якої займає приблизно 4 такту. Потім йде пара сотень кілобайт більш повільної кеш-пам'яті другого рівня. Потім кілька мегабайт кеш-пам'яті третього рівня. Вона набагато повільніше, але все одно швидше оперативної пам'яті. Далі розташована відносно повільна оперативна пам'ять.

Оперативну пам'ять можна розглядати як кеш для локального диска. Диски це робочі конячки серед пристроїв зберігання. Вони великі, повільні і коштують дешево. Комп'ютер завантажує файли з диска в оперативну пам'ять, коли збирається над ними працювати. Розрив у часі доступу між оперативною пам'яттю та диском колосальний. Диск повільніше оперативної пам'яті в десятки тисяч разів, і повільніше кешу першого рівня в мільйони разів. Часто вигідніше звернутися кілька тисяч разів до оперативної пам'яті, ніж один раз до диска. На це знання спираються такі структури даних, як B-дерева, які намагаються розмістити більше інформації в оперативній пам'яті, намагаючись уникнути звернення до диска будь-яку ціну.

Локальний диск сам може розглядатися як кеш даних, розташованих на віддалених серверах. Коли ви відвідуєте веб-сайт, ваш браузер зберігає зображення з веб-сторінки на диску, щоб при повторному відвідуванні їх не треба було качати. Існують і більш низькі ієрархії пам'яті. Великі датацентри, типу Google, зберігають великі обсяги даних на стрічкових носіях, які зберігаються десь на складах, і коли знадобляться, повинні бути присоеденены вручну або роботом.

Сучасна система має приблизно такі характеристики:
Тип кешу Час доступу (тактів) Розмір кешу
Регістри 0 десятки штук
L1 кеш 4 32 KB
L2 кеш 10 256 KB
L3 кеш 50 8 MB
Оперативна пам'ять 200 8 ГБ
Буфер диска 100'000 64 MB
Локальний диск 10'000'000 1000 GB
Віддалені сервера 1'000'000'000
Швидка пам'ять коштує дуже дорого, а повільна дуже дешево. Це велика ідея архітекторів систем поєднати великі розміри повільною і дешевій пам'яті з маленькими розмірами швидкої і дорогий. Таким чином система може працювати на швидкості швидкої пам'яті і мати вартість повільної. Давайте розберемося, як це вдається.

Припустимо, ваш комп'ютер має 8 ГБ оперативної пам'яті і диск розміром 1000 ГБ. Але подумайте, що ви не працюєте з усіма даними на диску в один момент. Ви завантажуєте операційну систему, відкриваєте веб-браузер, текстовий редактор, пару-трійку інших додатків і працюєте з ними кілька годин. Всі ці програми поміщаються в оперативній пам'яті, тому вашій системі не потрібно звертатися до диска. Потім, звичайно, ви закриваєте додаток і відкриваєте інше, яке доводиться завантажити з диска в оперативну пам'ять. Але це займає пару секунд, після чого ви кілька годин працюєте з цим додатком, не звертаючись до диска. Ви не особливо помічаєте повільний диск, тому що в один момент ви працюєте тільки з невеликим бъемом даних, що зберігається в оперативній пам'яті. Вам немає сенсу витрачати величезні гроші на установку 1024 ГБ оперативної пам'яті, в яку можна було б завантажити вміст всього диска. Якби ви це зробили, ви б майже не помітили ніякої різниці в роботі, це було б «гроші на вітер».

Так само справа йде і з маленькими кэшами процесора. Припустимо вам потрібно виконати обчислення над масивом, що містить 1000 елементів типу int. Такий масив займає 4 КБ і повністю поміщається в кеші першого рівня розміром 32 КБ. Система розуміє, що ви почали роботу з певним шматком оперативної пам'яті. Вона копіює цей шматок в кеш-пам'ять, і процесор швидко виконує дії над цим масивом, насолоджуючись швидкістю кеша. Потім змінений масив з кешу копіюється тому в оперативну пам'ять. Збільшення швидкості оперативної пам'яті до швидкості кешу не дало відчутного приросту в продуктивності, але збільшило б вартість системи в сотні і тисячі разів. Але все це вірно тільки якщо програми мають хорошу локальність.

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

Розглянемо програму, яка обчислює суму елементів масиву:

int sum(int size, int A[])
{
int i, sum = 0;

for (i = 0; i < size; i++)
sum += A[i];
return sum;
}

У цій програмі звернення до змінних sum i відбувається на кожній ітерації циклу. Вони мають гарну тимчасову локальність і будуть розташовані в швидких регістрах процесора. Елементи масиву мають погану часову локальність, тому що до кожного елемента ми звертаємося лише по разу. Але зате вони мають хорошу просторову локальність — торкнувши один елемент, ми потім чіпаємо елементи поруч з ним. Всі дані в цій програмі мають або гарну тимчасову локальність або гарну просторову локальність, тому ми кажемо, що програма в загальному має хорошу локальність.

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

Переміщення даних між рівнями здійснюється блоками певного розміру. Наприклад, процесор Core i7 Haswell переміщує дані між своїми кэшами блоками розміром 64 байта. Розглянемо конкретний приклад. Ми виконуємо програму на машині з вищезазначеним процесором. У нас є масив v, що містить 8-байтові елементи типу long. І ми послідовно обходимо елементи цього масиву в циклі. Коли ми читаємо v[0], його немає в кеші, процесор зчитує його з оперативної пам'яті в кеш блоком розміром 64 байта. Тобто в кеш відправляються елементи v[0]v[7]. Далі ми обходимо елементи v[1], v[2], ..., v[7]. Всі вони будуть в кеші і доступ до них ми отримаємо швидко. Потім ми читаємо елемент v[8], якого в кеші немає. Процесор копіює елементи v[8]v[15] кеш. Ми швидко обходимо ці елементи не знаходимо в кеші елемента v[16]. І так далі.

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

Бажано обходити масиви послідовно, читаючи його елементи один за іншим. Якщо потрібно обійти елементи матриці, то краще їх обходити порядково, а не по стовпцях. Це дає хорошу просторову локальність. Тепер ви можете зрозуміти, чому функція matrixsum1 працювала повільніше функції matrixsum2. Двовимірний масив розташований в пам'яті порядково: спочатку розташована перша рядок, відразу за нею йде друга і так далі. Перша функція читала елементи матриці по рядках і рухалася по пам'яті послідовно, ніби обходила один великий одновимірний масив. Ця функція в основному читала дані з кеша. Друга функція переходила від рядка до рядка, читаючи по одному елементу. Вона як би стрибала по пам'яті зліва-направо, потім поверталася на початок і знову починала стрибати зліва-направо. В кінці кожної ітерації вона забивала кеш останніми рядками, так що на початку наступної ітерації перших рядків кеші не знаходила. Ця функція в основному читала дані з оперативної пам'яті.

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

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

void matrixmult1(int size, double A[][size], double B[][size], double C[][size])
{
double sum;

for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++) {
sum = 0.0;
for (int k = 0; k < size; k++)
sum += A[i][k]*B[k][j];
C[i][j] = sum;
}
}

Код дослівно повторює математичне визначення множення матриць. Ми обходимо всі елементи остаточної матриці по рядках, обчислюючи кожен з них один за іншим. У коді є одна неефективність, це вираз B[k][j] в самому внутрішньому циклі. Ми обходимо матрицю B стобцам. Здавалося б, нічого з цим не поробиш і доведеться змиритися. Але вихід є. Можна переписати той же обчислення по іншому:

void matrixmult2(int size, double A[][size], double B[][size], double C[][size])
{
double r;

for (int i = 0; i < size; i++)
for (int k = 0; k < size; k++) {
r = A[i][k];
for (int j = 0; j < size; j++)
C[i][j] += r*B[k][j];
}
} 

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

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

Можна продемонструвати це на прикладі. Припустимо у вас є орієнтований граф, представлений у вигляді матриці суміжності. Це така квадратна матриця з нулів і одиниць, так що якщо елемент матриці з індексом (i, j) дорівнює одиниці, то існує межа від вершини графа i до вершини j. Ви хочете перетворити цей орієнтований граф в неорієнтованим. Тобто, якщо є межа (i, j), то повинна з'явитися протилежна грань (j, i). Зверніть увагу, що якщо представити матрицю візуально, то елементи (i, j) і (j, i) є симетричними відносно діагоналі. Цю трансформацію неважко здійснити в коді:

void convert1(int size, int G[][size])
{
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
G[i][j] = G[i][j] | G[j][i];
}

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

void convert2(int size, int G[][size])
{
int block_size = size / 12; // розбити на 12*12 блоків
// уявімо, що ділиться без залишку
for (int ii = 0; ii < size; ii += block_size) {
for (int jj = 0; jj < size; jj += block_size) {
int i_start = ii; // індекс i для блоку приймає значення [ii, ii + block_size)
int i_end = ii + block_size;
int j_start = jj; // індекс j для блоку приймає значення [jj, jj + block_size)
int j_end = jj + block_size;

// обходимо блок
for (int i = i_start; i < i_end; i++)
for (int j = j_start; j < j_end; j++)
G[i][j] = G[i][j] | G[j][i];
}
}
}

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

На машині з процесором Core i7 Haswell друга функція не виконується швидше. На машині з більш простим процесором Pentium 2117U друга функція виконується в 2 рази швидше. На машинах, які не виконують предвыборку, продуктивність покращилася б ще сильніше.

Які алгоритми швидше
Всі знають з курсів за алгоритмами, що потрібно вибирати хороші алгоритми з найменшою складністю і уникати поганих алгоритмів з високою складністю. Але ці складнощі оцінюють виконання алгоритму на теоретичній машині, створеної нашою думкою. На реальних машинах теоретично поганий алгоритм може виконуватися швидше теоретично хорошого. Згадайте, що отримати дані з оперативної пам'яті займає 200 тактів, а з кешу першого рівня 4 такту — це в 50 разів швидше. Якщо хороший алгоритм часто зачіпає пам'ять, а поганий алгоритм розміщує свої дані в кеші, гарний може виконуватися повільніше поганого. Також хороший алгоритм може гірше виконуватися на процесорі, ніж поганий. Наприклад, хороший алгоритм вносить залежність даних і не може завантажити конвеєр, а поганий позбавлений цієї проблеми і на кожному такті відправляє в конвеєр нову інструкцію. Іншими словами, складність алгоритму це ще не все. Те, як алгоритм будемо виконуватися на конкретній машині з конкретними даними, має значення.

Уявімо, що вам потрібно реалізувати чергу цілих чисел, і нові елементи можуть додаватися в будь-яку позицію черги. Ви вибираєте між двома реалізаціями: масив і зв'язний список. Щоб додати елемент в середину масиву, потрібно зрушити вправо половину масиву, що займає лінійний час. Щоб додати елемент в середину списку, потрібно дійти за списком до середини, що також займає лінійний час. Ви думаєте, що раз складності у них однакові, то краще вибрати список. Тим більше у списку є одна хороша властивість. Список може рости без обмеження, а масив доведеться розширювати, коли він заповниться. Давайте уявимо що довжина черги 1000 елементів і нам потрібно вставити елемент в середину черги. Елементи списку хаотично розкидані по пам'яті, а отримати дані з пам'яті займає 200 тактів. Тому щоб обійти 500 елементів, нам знадобиться 500*200=100'000 тактів. Масив розташований в пам'яті послідовно, що дозволить нам насолоджуватися швидкістю кешу першого рівня з часом відгуку 4 такту. Використовуючи декілька оптимізацій, ми можемо рухати елементи, витрачаючи 1-4 такти на елемент. Ми зрушимо половину масиву максимум за 500*4=2000 тактів. Це швидше в 50 разів.

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

Висновок
Система пам'яті організована у вигляді ієрархії пристроїв зберігання з маленькими і швидкими пристроями вгорі ієрархії і великими і повільними пристроями внизу. Програми з хорошою локальністю працюють з даними з кешу процесора. Програми з поганою локальністю працюють із даними щодо повільної оперативної пам'яті.

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

Зокрема, рекомендуються наступні техніки:

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

0 коментарів

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