Искам да ви покажа някои неща, свързани с low level оптимизации, които не се срещат често. Те са доста интересни при задачи за обработка на данни и скорост. Това не означава, че не са приложими за друг вид задачи и е хубаво да мислим за оптимизации, независимо от конкретната задача.

След като искаме да сме бързи и да ползваме low level оптимизации, следва да използваме C/C++. Той е подходящ, защото е по-бърз от езици като Go, Java и др. подобни, и имаме по-голям контрол върху това, което се случва. Същевременно, той позволява да компилираме кода си в Асемблер и да видим какво ще се изпълни на машината (Асемблер кодът е 1-1 с машинния код). [1]

Data Oriented Design

Какво е това? Отговорът на този въпрос е: как да обработим данните като използваме CPU-то и кеш паметта по оптимален начин. Първоначално избягваме да навлизаме в ОО design patterns. Големият фокус върху изграждането на абстракции и репрезентации на обектите от самото начало може да ни ограничи при намирането на оптималното решение на задачата. Според Christer Ericson (Director of Tools and Technology for internal development at Sony Computer Entertainment America in Santa Monica), „Thinking in patterns is exactly the wrong thing to do! It makes you think in terms of the solution instead of in terms of the problem! Pattern thinking makes you try to fit a round, square, or oval hole (your choice of patterns) to the triangular peg (your problem). When all you have is a hammer. [2]

Сега ще видим пример как може да преминем от OOP -> DOD и какви са ползите от това. Задачата е следната: Имаме програма, която следи в реално време всички акции. При всяко действие, има риск, който трябва да пресмятаме периодично.

OOP Design

Имаме Stock обект, който има следните полета: в дясно имаме функция, която прави някакво изчисление, а малко по-долу е генерираният Асемблер код.

Асемблер кодът изпълнява следните функции:

  1. Чете от RAM паметта двете променливи;
  2. Извършва умножение и деление;
  3. Записва резултата обратно в RAM паметта.
    *променливата f се намира в xmm0

Най-бавното нещо в кода ще бъде достъпът до RAM паметта. Това като цяло е от 10 – 15 пъти по-бавно от това да четем от L2 кеша (размерът на кеш линиите зависи от хардуера, да предположим че е 64 bytes за тези примери). Малко по-долу виждаме колко по-бавно работим, ако трябва да достъпваме RAM паметта вместо кеш паметта.[3]

DOD Design

Нека променим дизайна. Сега имаме 2 обекта. Единият има 2 properties (magicNumber & ratingFactor), които използваме за самото изчисление.
Един обект RiskFactor е с едно property – riskNumber, където записваме резултатите (с тази промяна, ще трябва в главния обект Stock да пазим указатели към тези обекти).

Това е генерираният Асемблер код (една част от него). В него има доста оптимизации и сега ще ги погледнем.

Асемблер кодът изпълнява следните функции:

  1. Чете двата MagicNumber обекта в xmm2 и следващите два MagicNumber обекта в xmm3;
  2. Подрежда xmm регистрите така, че единият да съдържа само magicNumber на четирите обекта, а във втория xmm register да се съдържат ratingFactor променливите;
  3. Извършва умножение и деление на MagicNumber обектите едновременно;
  4. Записва четири резултата едновременно;
  5. Следващите стъпки извършват същото (стъпка 1- 4) повторно. След това се връщаме в началото на цикъла.

Така за един цикъл записваме осем резултата от тип RiskFactor.

Нека сега видим всички оптимизации (при един модерен процесор). Броят такти за всяка операция ще вземем от тази  за Асемблер инструкции:[4]

1. Функцията получава масив от тип MagicNumbers. Ние четем тази памет последователно. Модерните процесори имат streaming prefetcher. Идеята е, че когато четем последователна памет, процесорът започва да чете напред и кешира паметта в L2 или L3 кеша. Това означава, че в първата стъпка очакваме да имаме L3 или L2 кеш хит, което е около 14 цикъла.
2. Пренареждане (shuffle) на данните в регистрите и местене на xmm2 в xmm4 – около 8 цикъла.
3. Умножение и деление – около 35 цикъла.
4. Записване на резултата – 167 цикъла

Сега имаме същите инструкции, които се изпълняват повторно.

  1. Тъй като сме прочели предишните 32 байта следващите ще са в L2 кеша – около 11 цикъла.
  2. Пренареждане (shuffle) – около 8 цикъла;
  3. Умножение и деление – около 35 цикъла;
  4. Записване на резултата – 167 цикъла

Сборът на числата е: 14 + 8 + 35 + 167* + 11 + 8 + 35 + 167* = 445

Тук ще получим още една оптимизация. При първия запис към RAM паметта, процесорът ще попадне в stall. Това означава, че той чака IO операцията да приключи.

За да няма загубени цикли, CPU-то ще продължи да изпълнява следващите инструкции, които са независими и за които имаме необходимата информация.

Така получаваме: 14 + 8 + 35 + 167 + 55 = 279 цикъла за 8 резултата.
За един резултат са ни необходими 35 цикъла.

Да се върнем на 1-вия пример, където имахме:

  1. Четене от RAM – 167* цикъла;
  2. Умножение и деление – 35 цикъла;
  3. Записване на резултата – 167 цикъла.

*Забележете, че между ratingFactor и magicNumber имаме данни, които изместват двете променливи в отделни кеш линии. Тук CPU-то може да направи оптимизация и да ги прочете заедно. Затова сме сложили само 167 (което е един достъп до RAM паметта).
*За тези два достъпа до RAM паметта ще се ползват две отделни кеш линии (общо 128 bytes). От този кеш ние използваме само 8 bytes, което е голяма загуба. Дори да сложим двете променливи заедно в паметта (което трябва да направим), пак имаме лошо оползотворяване на кеш паметта. В по-горния дизайн използваме кеш линиите на 100%.

ОО дизайна получаваме 167 + 35 + 167 = 369 цикъла
Да предположим, че имаме 100% кеш попадения при първото четене (което може да се случи в зависимост от начина, по който се обхождат обектите) – 11 + 35 + 167 = 213 цикъла.

Сравнете 219 – 369 цикъла с 35.


За автора:

Александър Пенев
Работя като developer в развойния център на SAP в България. Завършил съм Computer Science в UVIC (University of Victoria), Бритиш Колумбия, Канада. Работил съм в Business Objects и Microsoft.

 

 


[1] За проучване на скоростта на езиците вижте тази статия от Google: Hundt, Robert, Loop Recognition in C++/Java/Go/Scala, https://days2011.scala-lang.org/sites/days2011/files/ws3-1-Hundt.pdf, посетен на 03.05.2019 г. Според статията:“We find that in regards to performance, C++ wins out by a large margin. However, it also required the most extensive tuning efforts, many of which were done at a level of sophistication that would not be available to the average programmer.“
[2] Ericson, Christer, Design patters are from hell, 01.05.2018, http://realtimecollisiondetection.net/blog/?p=44посетен на 03.05.2019 г.
[3] https://cenalulu.github.io/images/linux/cache_line/latency.png, посетен на 03.05.2019 г.
[4] Fog, Agner, Istruction Tables, Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs, Technical University of Denmark, https://www.agner.org/optimize/instruction_tables.pdf, посетен на 03.05.2019 г.

Share This