Коли «Про» велику підводить


"" велика — це відмінний інструмент. Він дозволяє швидко вибрати відповідну структуру даних або алгоритм. Але іноді простий аналіз "" великого може обдурити нас, якщо не подумати гарненько про вплив константных множників. Приклад, який часто зустрічається при програмуванні на сучасних процесорах, пов'язаний з вибором структури даних: масив, список або дерево.
Пам'ять, повільна-повільна пам'ять
На початку 1980-х час, необхідне для отримання даних з ОЗП і час, необхідний для виконання обчислень з цими даними, були приблизно однаковим. Можна було використовувати алгоритм, який випадково рухався по динамічної пам'яті, збираючи і обробляючи дані. З тих пір процесори стали виробляти обчислення в рази швидше, від 100 до 1000 раз, ніж отримувати дані з ОЗУ. Це значить, що поки процесор чекає даних з пам'яті, він простоює сотні циклів, нічого не роблячи. Звичайно, це було б зовсім нерозумно, тому сучасні процесори містять кілька рівнів вбудованої кеша. Кожен раз, коли ви запитуєте один фрагмент даних з пам'яті, додаткові прилеглі фрагменти пам'яті будуть записані в кеш процесора. В результаті, при послідовному проході по пам'яті можна отримувати до неї доступ майже настільки ж швидко, наскільки процесор може обробляти інформацію, тому що шматки пам'яті будуть постійно записуватися в кеш L1. Якщо ж рухатися по випадковим адресами пам'яті, то найчастіше кеш використовувати не вийде, і продуктивність може сильно постраждати. Якщо хочете дізнатися більше, то доповідь Майка Актона на CppCon — це відмінна відправна точка (і відмінно проведений час).
В результаті цього масиви стали кращою структурою даних, коли важлива продуктивність, навіть якщо згідно з аналізом "" великого масив повинен працювати повільніше. Там, де ви хотіли використовувати дерево, відсортований масив з двійковим пошуком може підійти краще. Там, де ви хотіли використовувати чергу, зростаючий масив може підійти краще, і так далі.
Зв'язний список і динамічний масив
Коли ви зрозуміли важливість доступу до послідовної пам'яті, для вас не буде сюрпризом той факт, що якщо потрібно швидко пройти колекції, то масив буде швидше зв'язного списку. Оточення з розумним управлінням пам'яттю і збирачами сміття, можливо, будуть зберігати вузли зв'язного списку більш послідовно, але вони не можуть гарантувати це. Використання сирого масиву зазвичай вимагає більш складного коду, особливо коли потрібно вставляти або додавати нові елементи, так як доведеться обробляти зростання масиву, переміщення елементів, і так далі. В більшості мов є рідні бібліотеки, що містять ту чи іншу реалізацію динамічних масивів. В C++ єvector, в C# є List (в F# використовується під ім'ям ResizeArray), а в Java є ArrayList. Зазвичай ці структури надають такий самий або схожий інтерфейс, як і зв'язний список. В цій статті я буду називати такі структури динамічними масивами (Array List), але майте на увазі, що в прикладах на C# використовується клас List, а не старий ArrayList.
Що, якщо потрібна структура даних, в яку можна швидко вставляти елементи і швидко проходити за ним? Уявімо, для прикладу, що у нас такий випадок: ми будемо вставляти в початок колекції приблизно в 5 разів частіше, ніж проходити по ній. Давайте також уявімо, що і у зв'язного списку, і в динамічного масиву в нашому середовищі є однаково приємні для роботи інтерфейси. Залишається тільки вирішити, що буде більш ефективним рішенням. Ми можемо звернутися до аналізу "" большго для оптимізації нашого цінного часу. Звернемося до корисної підказкою про "" великий, відповідні складності для цих структур даних:





Прохід Вставити Динамічний масив O(n) O(n) Зв'язний список O(n) O(1)
Проблема динамічних масивів полягає в ставці, як мінімум потрібно буде копіювати і рухати кожен елемент на одиницю після точки вставки щоб звільнити місце для нового елемента. Звідси O(n). Іноді потрібно створити новий масив, більший за розміром щоб з'явилося місце для вставки. У нашому випадку вставка відбувається в 5 разів частіше, ніж прохід, так що, здається, висновок очевидний. Поки n досить великий, зв'язний список повинен бути ефективніше.
Експеримент
Але щоб упевнитися, краще порахувати. Давайте проведемо експеримент з C#, використовуючи BenchMarkDotNet. В C# є колекція LinkedList, яка є класичним зв'язковим списком, і List, який є динамічним масивом. Інтерфейси в обох схожі, і обидва можна з легкістю застосувати в нашому випадку. Розглянемо найгірший випадок для динамічного масиву — вставка завжди відбувається на початок, так що доводиться копіювати весь масив при вставлення. Конфігурація оточення тестування така:
Host Process Environment Information:
BenchmarkDotNet.Core=v0.9.9.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel® Core(TM) i7-4712HQ CPU 2.30 GHz, ProcessorCount=8
Frequency=2240910 ticks, Resolution=446.2473 ns, Timer=TSC
CLR=MS.NET 4.0.30319.42000, Arch=64-bit RELEASE [RyuJIT]
GC=Concurrent Workstation
JitModules=clrjit-v4.6.1590.0

Type=Bench Mode=Throughput 

Тест-кейси:
[Benchmark(Baseline=true)]
public int ArrayTest()
{ 
//In C#, List<T> is an array backed list.
List<int> local = arrayList;
int localInserts = inserts;
int sum = 0;
for (int i = 0; i < localInserts; i++)
{
local.Insert(0, 1); //Insert the number 1 at the front
}

// Loops For iterate over List<T> much faster than foreach
for (int i = 0; i < local.Count; i++)
{
sum += local[i]; //do some work here so the JIT doesn't elide the loop entirely
}
return sum;
}

[Benchmark]
public int ListTest()
{
LinkedList<int> local = linkedList;
int localInserts = inserts;
int sum = 0;
for (int i = 0; i < localInserts; i++)
{
local.AddFirst(1); //Insert the number 1 at the front
}

// Again, iterating the fastest possible way over this collection
var node = local.First;
for (int i = 0; i < local.Count; i++)
{
sum += node.Value;
node = node.Next;
}

return sum;
}

Результати:





Метод Розмір Вставити Медіана ArrayTest 100 5 38.9983 us ListTest 100 5 51.7538 us
Динамічний масив виграє з непоганим відривом. Але це маленький список, "" велика описує продуктивність лише зростаючого до великих розмірів
n
, тому що результати тесту повинні в підсумку перевернутися навпаки при збільшенні
n
. Давайте спробуємо:













Метод Розмір Вставити Медіана ArrayTest 100 5 38.9983 us ListTest 100 5 51.7538 us ArrayTest 1000 5 42.1585 us ListTest 1000 5 49.5561 us ArrayTest 100000 5 208.9662 us ListTest 100000 5 312.2153 us ArrayTest 1000000 5 2,179.2469 us ListTest 1000000 5 4,913.3430 us ArrayTest 10000000 5 36,103.8456 us ListTest 10000000 5 49,395.0839 us

Несподівані для багатьох результати. Яким би великим не був
n
, динамічний масив все одно виявляється краще. Щоб продуктивність стала гірше, відношення вставок до проходах повинне змінитися, а не тільки розмір колекції. Зауважте, що це не помилка аналізу "" великого, це просто людська помилка — ми неправильно використовуємо метод. Якщо заглибитися в математику, то "" велика покаже, що обидві структури даних будуть рости з однією швидкістю поки відношення вставок до проходах не змінюється.
Де знаходиться переломний момент, залежить від безлічі факторів, але гарне наближене правило запропоновано Чандлером Каррутом з Google: динамічний масив буде ефективніше зв'язного списку поки вставок на порядок більше, ніж проходів. У нашому випадку правило працює добре, тому що при відношенні 10:1 можна побачити зрушення в бік зв'язного списку:





Метод Розмір Вставити Медіана ArrayTest 100000 10 328,147.7954 ns ListTest 100000 10 324,349.0560 ns
Диявол у деталях
Динамічний масив перемагає тому, що числа, за яким відбувається прохід, знаходяться в пам'яті послідовно. Кожен раз, коли відбувається запит з пам'яті, цілий набір чисел додається в кеш L1, так що наступні 64 байта даних вже готові до обробки. При роботі зі зв'язковим списком кожен виклик
node.Next
перенаправляє покажчик на наступний вузол, і немає гарантій, що цей сайт буде знаходиться в пам'яті відразу за попереднім. Тому іноді ми будемо потрапляти повз кеша. Але нам не завжди доводиться працювати з типами, що зберігають безпосередньо значення, особливо в об'єктно-орієнтованих мовах, де прохід найчастіше відбувається за посилальних типів. В такому випадку, не дивлячись на те, що в динамічному масиві самі вказівники знаходяться в пам'яті послідовно, об'єкти, на які вони вказують — ні. Ситуація все ще краще, ніж зі зв'язковим списком, де вам доведеться двічі розв'язати покажчики для кожного елемента, але як це впливає на загальну продуктивність?
Продуктивність значно погіршується, в залежності від розміру об'єктів і особливостей заліза і софта. Якщо замінити у прикладі вище числа на маленькі об'єкти (12 байт), то точка "перелому" опускається до 4 вставок до одного проходу:









Метод Розмір Вставити Медіана ArrayTestObject 100000 0 674.1864 us ListTestObject 100000 0 1,140.9044 us ArrayTestObject 100000 2 959.0482 us ListTestObject 100000 2 1,121.5423 us ArrayTestObject 100000 4 1,230.6550 us ListTestObject 100000 4 1,142.6658 us
Керований код на C# сильно страждає в цьому випадку, тому що прохід по динамічного масиву створює зайві перевірки меж масиву. Вектор в С++, швидше за все, буде працювати ефективніше. Якщо бути зовсім агресивним у вирішенні цієї задачі, то можна написати більш швидкий клас для динамічного масиву з використанням небезпечного коду C# щоб уникнути перевірки меж масиву. Відносна різниця також буде сильно залежати від того, як розподільник пам'яті і збирач сміття керують динамічної пам'яттю, наскільки великі об'єкти і від інших факторів. Більш великі об'єкти зазвичай покращують продуктивність динамічних масивів у моєму середовищі. Коли мова йде про цілих додатках, відносна продуктивність динамічних масивів може поліпшуватися з збільшенням фрагментації динамічної пам'яті, але щоб упевнитися, потрібно проводити тестування.
Ще один момент. Якщо об'єкти досить маленькі (від 16 до 32 байтів або менше в різних ситуаціях), то варто розглянути варіант зберігання їх за значенням (
struct
.NET), а не в об'єкті. Це не тільки сильно поліпшить продуктивність завдяки послідовному розподілу пам'яті, але також теоретично зменшить додаткове навантаження за збирання сміття, залежно від сценарію використання цих даних:







Метод Розмір Вставити Медіана ArrayTestObject 100000 10 2,094.8273 us ListTestObject 100000 10 1,154.3014 us ArrayTestStruct 100000 10 792.0004 us ListTestStruct 100000 10 1,206.0713 us
Java тут може показати кращі результати, тому що вона автоматично робить розумні зміни маленьких об'єктів, або можна просто використовувати окремі масиви примітивних типів. І хоча таке писати дуже нудно, це може виявитися швидше, ніж масив структур. Все залежить від особливостей звернення до даних у вашому коді. Майте це на увазі, коли продуктивність особливо важлива.
Переконайтеся, що абстракція себе виправдовує
Часто люди не згодні з такими висновками, і їх аргументи— це чистота коду, коректність і поддерживаемость. Звичайно, у кожній галузі є свої пріоритети, але я вважаю, що коли абстракція лише ненабагато покращує чистоту коли, а продуктивність сильно страждає, потрібно взяти за правило вибирати продуктивність. Якщо не шкодувати часу на вивчення середовища, то можна дізнатися про випадках, коли існує більш швидке і не менш чисте рішення, як це часто буває у випадку з динамічними масивами замість списків.
Інформація для роздумів: ось сім різних способів знайти суму списку чисел в C#, з часом виконання і використанням пам'яті. Скрізь використовується арифметика з перевіркою переповнення, щоб порівняння з Linq, де метод Sum використовує саме таку арифметику, було коректним. Зауважте, наскільки кращий метод швидше за інших. Зауважте, наскільки витратний найпопулярніший спосіб. Зауважте, що абстракція
foreach
добре працює з масивами, але не з динамічними масивами або зв'язковими списками. Яким би не був ваш язик і оточення, важливо розуміти ці деталі щоб приймати правильні рішення за замовчуванням.











Method Length Median Bytes Allocated/Op LinkedListLinq 100000 990.7718 us 23,192.49 RawArrayLinq 100000 643.8204 us 11,856.39 LinkedListForEach 100000 489.7294 us 11,909.99 LinkedListFor 100000 299.9746 us 6,033.70 ArrayListForEach 100000 270.3873 us 6,035.88 ArrayListFor 100000 97.0850 us 1,574.32 RawArrayForEach 100000 53.0535 us 1,574.84 RawArrayFor 100000 53.1745 us 1,577.77
[Benchmark(Baseline = true)]
public int LinkedListLinq()
{
var local = linkedList;
return local.Sum();
}

[Benchmark]
public int LinkedListForEach()
{
var local = linkedList;
int sum = 0;
checked
{
foreach (var node in local)
{
sum += node;
}
}
return sum;
}

[Benchmark]
public int LinkedListFor()
{
var local = linkedList;
int sum = 0;
var node = local.First;
for (int i = 0; i < local.Count; i++)
{
checked
{
sum += node.Value;
node = node.Next;
}
}

return sum;
}

[Benchmark]
public int ArrayListFor()
{
//In C#, List<T> is an array backed list
List<int> local = arrayList;
int sum = 0;

for (int i = 0; i < local.Count; i++)
{
checked
{
sum += local[i];
}
}

return sum;
}

[Benchmark]
public int ArrayListForEach()
{ 
//In C#, List<T> is an array backed list
List<int> local = arrayList;
int sum = 0;
checked
{
foreach (var x in local)
{
sum += x;
}
}
return sum;
}

[Benchmark]
public int RawArrayLinq()
{
int[] local = rawArray;
return local.Sum();
}

[Benchmark]
public int RawArrayForEach()
{
int[] local = rawArray;
int sum = 0;
checked
{
foreach (var x in local)
{
sum += x;
}
}
return sum;
}

[Benchmark]
public int RawArrayFor()
{
int[] local = rawArray;
int sum = 0;

for (int i = 0; i < local.Length; i++)
{
checked
{
sum += local[i];
}
}

return sum;
}

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

0 коментарів

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