Какво значи заглавието?
- CPU-Friendly code?
- С какви работи хардуерът се справя добре
- Неща извън О-нотацията
- Неща, за които не всеки се замисля
- 101?
- Фундаментални работи
- ... които са лесни за прилагане
- ...и които вероятно вече знаете :)
- ...и които могат да се покрият за 15 минути
1. Алокации на памет
Те са бавни
А защо са бавни?
- Явна цена
- Операционната система трябва да извърши една камара неща.
- Физическата памет: Commit Size, страници
- Свободно парче поредни страници
- Синхронизация между различни процеси и нишки
- Скрита цена
- Нулиране на памет
- Фрагментация
- Garbage collection
Какво да направим?
- Билярди и басейни (сиреч pools)
- Преизползване на обекти
- Code it like it's 1969. Масиви с фиксиран размер
- Reserve (например
std::vector::reserve)
- Примери от игрите:
- Projectile/Particle pools
- Per-frame pools
- Целта ни е нула алокации за обекти, които живеят само един фрейм.
Какво ни коства това?
- Повече памет
- По-сложен и труден за четене код
- По-дълго време за зареждане
- В краен случай malloc-lite: Да решаваме проблемите, които операционната система решава
- За щастие в 90% от ситуациите можем да минем с 10% от усилията
2. Cache-locality
То е бързо
Какво е това?
- Процесорът има кеш (но не пари в брой, а cache)
- Това е памет, която е близко до него
- Той обича да работи с нея
- Cache is so cash (levels, TLB)
- Щом барнем парче памет, то отива в кеша
- Cache-hit vs Cache-miss
- Кешът е космически бърз
Какво да направим?
- Value types
- Линейни структури от данни
- Не всеки език ни дава такива
- ... но някои езици ни дават такива неявно
- Ха! Отново memory pools
- Примери от игрите:
Demo
...или как O(n) може да е по-бързо от O(log(n))
Какво ни коства това?
- Без полиморфизъм
- Потенциално копиране на данни
- Неудобни за ползване структури
- Не всеки език за програмиране може да ни помогне
3. Branch prediction
То е... хм...
Какво е това?
- Инструкции, register aliasing и CPU pipeline
- CPU branch predictor
- Pipeline stall
- На човешки език: ако нещо се случва много често по един и същи начин, това е добре за процесора
И какво от това?
- Ми... нищо?...
if не бива да е толкова страшен- Dense is better than sparse
- Conficius say, order is better than chaos
- Експериментирайте
