Skip to main content

Упражнения: Компилаторни оптимизации, локалност, контейнери и масиви

Напредък

0%
✅ Завършени: 0 / 0📊 Напредък: 0%

💡 Напредъкът се записва локално в браузъра

ℹ️Информация за упражненията

Този набор от упражнения покрива:

  • Компилаторни оптимизации и техните ефекти
  • Локалност на данните (пространствена и временна)
  • C++ контейнери и техните производителни характеристики
  • Анализ с Compiler Explorer
  • Практически приложения на концепциите

Общо упражнения: 30 задачи в 5 нива на сложност

Лесни упражнения (EASY)​

Фундаментални концепции и базови разбирания

ЛЕСНО

Задача 1: Какво е показалец в C++?​

Напишете код, който декларира integer променлива x със стойност 42, създава показалец към x, и използва показалеца да промени стойността на 100.

Използвайте оператора & за вземане на адреса и * за dereference.

#include <iostream>

int main() {
    // Декларираме integer променлива
    int x = 42;

    // Създаваме показалец към x
    int* ptr = &x;  // & взема адреса на x

    // Използваме показалеца да променим стойността
    *ptr = 100;     // * дереференцира показалеца

    std::cout << "x = " << x << std::endl;  // Отпечатва: x = 100
    std::cout << "Адресът на x: " << &x << std::endl;
    std::cout << "ptr сочи към: " << ptr << std::endl;

    return 0;
}

Обяснение:

  • int* ptr - декларация на показалец към int
  • &x - взима адреса на променливата x
  • *ptr - дереференцира показалеца (достъпва стойността, която сочи)
  • Променяйки *ptr, променяме директно стойността на x
ЛЕСНО

Задача 2: Тест с многовариантни отговори​

Въпрос: Коя памет се използва за локални променливи във функция?

  • A) Heap
  • B) Stack
  • C) Data segment
  • D) Code segment

Локалните променливи се алокират автоматично при извикване на функция и се освобождават при завършването ѝ.

Отговор: B) Stack

Локалните променливи и параметрите на функциите се алокират на stack паметта, която е бърза и се управлява автоматично.

ЛЕСНО

Задача 3: Дефиниция на пространствена локалност​

Дефинирайте пространствена локалност с ваши думи и дайте прост пример за код, който демонстрира добра пространствена локалност.

Помислете за данни, които са близо една до друга в паметта и как те се достъпват.

Пространствена локалност (Spatial Locality) е принципът, че когато достъпим дадена памет, е вероятно да достъпим и съседни памети в близко бъдеще.

Обяснение:

  • Данните, които са физически близо в паметта, обикновено се достъпват в кратък период от време
  • CPU cache-овете използват този принцип, зареждайки цели "cache lines" (напр. 64 bytes) наведнъж

Пример за добра пространствена локалност:

int arr[1000];

// Отлична пространствена локалност
for (int i = 0; i < 1000; i++) {
    arr[i] = i * 2;  // Последователен достъп до съседни елементи
}

Обяснение на примера:

  • Масивът е съхранен в непрекъсната памет
  • Достъпваме arr[0], след това arr[1], arr[2]... (последователно)
  • Когато CPU-то зареди arr[0], cache line-ът ще съдържа и arr[1], arr[2], и т.н.
  • Следващите достъпи са много бързи (cache hits)

Пример за лоша пространствена локалност:

// Лоша пространствена локалност
for (int i = 0; i < 1000; i += 100) {
    arr[i] = i * 2;  // Скачаме на всеки 100 елемента
}

Този код скача през паметта, като пропуска много елементи, което води до по-малко ефективно използване на cache-а.

ЛЕСНО

Задача 4: Call-by-value vs Call-by-reference​

Каква е разликата между call-by-value и call-by-reference в C++? Кога бихте предпочели да използвате const& за параметри на функция?

Помислете за копиране на данни и производителност при предаване на големи обекти.

Call-by-value vs Call-by-reference:

void increment_value(int x) {
    x++;  // Променя само локалното копие
}

int main() {
    int num = 10;
    increment_value(num);
    std::cout << num << std::endl;  // Отпечатва: 10 (непроменено!)
}

Характеристики:

  • ✅ Функцията получава копие на стойността
  • ✅ Промените не афектират оригиналната променлива
  • ❌ Неефективно за големи обекти (копирането отнема време и памет)

Кога да използваме const&:

void process_large_vector(const std::vector<int>& vec) {
    // Функцията може да чете vec, но НЕ може да го променя
    for (int val : vec) {
        std::cout << val << " ";
    }
}

Предимства на const&:

  1. ✅ Ефективност: Без копиране на големи обекти
  2. ✅ Безопасност: const гарантира, че функцията няма да промени данните
  3. ✅ Ясна интенция: Показва, че функцията само чете данните
  4. ✅ Best practice: Стандартен подход за readonly параметри

Препоръки:

  • Използвай copy (value) за малки типове (int, char, double)
  • Използвай const& за големи обекти (std::vector, std::string, custom класове) когато само четеш
  • Използвай & (без const) когато искаш да модифицираш параметъра
ЛЕСНО

Задача 5: Декларация и инициализация на масив​

Декларирайте и инициализирайте C++ масив от 5 integers със стойности 50. Напишете код, който отпечатва третия елемент.

// Вашият код тук
#include <iostream>

int main() {
    int arr[5] = {10, 20, 30, 40, 50};
    std::cout << "Третият елемент е: " << arr[2] << std::endl;
    // Резултат: 30 (тъй като индексирането е 0-базирано)
    return 0;
}
ЛЕСНО

Задача 6: Компилатор флаг за debugging​

Въпрос: Кой флаг за оптимизация бихте използвали за debugging и защо?

  • A) -O0
  • B) -O1
  • C) -O2
  • D) -O3

За debugging е важно кодът да бъде компилиран точно както е написан, без оптимизации.

Отговор: A) -O0

-O0 означава без оптимизации. Кодът е компилиран точно както е написан, което прави debugging по-лесен, защото assembly кодът съответства на source кода.

ЛЕСНО

Задача 7: std::vector памет​

Вярно или невярно: std::vector съхранява елементите си в непрекъснати паметни локации, точно като чист C++ масив.

Отговор: Вярно

std::vector съхранява елементите си в непрекъсната памет на heap, което осигурява отлична пространствена локалност, подобно на чистите масиви.

ЛЕСНО

Задача 8: Constant Folding​

Какво е constant folding? Дайте пример за statement, където компилаторът може да приложи constant folding.

Помислете за изрази, които съдържат само константи и могат да бъдат изчислени по време на компилация.

Constant folding е компилаторна оптимизация, при която изрази съдържащи само константи се изчисляват по време на компилация вместо runtime.

Пример:

// Преди оптимизация
int x = 5 + 3;
int y = 10 * 2 + 5;

// След constant folding
int x = 8;
int y = 25;

Лесни-Средни упражнения (EASY-MEDIUM)​

Изграждане на разбиране и приложение на концепциите

ЛЕСНО-СРЕДНО

Задача 9: Временна vs Пространствена локалност​

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

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

Разлика между временна и пространствена локалност:

Temporal Locality: Ако достъпим дадена памет, е вероятно да я достъпим отново скоро.

Характеристики:

  • Многократна употреба на същите данни
  • Данните остават в cache между достъпите
  • Полезно за loop променливи, counters, често използвани променливи

Пример:

int sum = 0;  // 'sum' има отлична временна локалност
for (int i = 0; i < 1000000; i++) {
    sum += arr[i];  // 'sum' се достъпва 1,000,000 пъти!
}
// 'sum' остава в CPU registers/cache целия път

Комбиниран пример (и двете локалности):

void calculate_sum(int* arr, int size) {
    int sum = 0;           // Временна локалност (използва се много пъти)

    for (int i = 0; i < size; i++) {
        sum += arr[i];     // Пространствена локалност (последователен достъп)
    }

    return sum;
}

Визуално сравнение:

ЛокалностФокусПример
ВременнаКолко често достъпваме същите данниLoop counter, accumulator
ПространственаКолко близо са данните, които достъпвамеПоследователен array traversal
ЛЕСНО-СРЕДНО

Задача 10: std::array vs чисти масиви​

Сравнете std::array и чистите C++ масиви. Изброете две предимства на std::array пред чистите масиви.

Предимства на std::array:

  1. Bounds checking: std::array::at() проверява границите и хвърля изключение при out-of-bounds достъп
  2. STL съвместимост: Работи с STL алгоритми и има методи като .size(), .begin(), .end()
  3. По-безопасен: Не се разпада до указател толкова лесно
  4. Същата производителност: Няма overhead спрямо чистите масиви
ЛЕСНО-СРЕДНО

Задача 11: Out-of-bounds достъп​

Какво се случва когато достъпите елемент извън границите на чист C++ масив (напр. arr[100] когато масивът има само 10 елемента)? Защо е това опасно?

Помислете за undefined behavior и какви проблеми може да причини.

Undefined Behavior (UB)

Достъпът извън границите на масив води до undefined behavior:

  • Може да прочете/запише произволна памет
  • Може да причини segmentation fault (crash)
  • Може да презапише други променливи
  • Може да работи "правилно" понякога, но да се счупи в production
  • Security риск: Buffer overflow атаки използват този проблем

Защо е опасно:

  • Непредсказуемо поведение
  • Трудно за debugging (не винаги crash-ва веднага)
  • Security уязвимости
  • Може да корумпира данни
ЛЕСНО-СРЕДНО

Задача 12: Функция с const reference​

Напишете функция, която приема std::vector<int> по константна референция и връща сумата на всичките му елементи. Обяснете защо предаването по константна референция е предпочитано пред предаване по стойност за тази функция.

// Вашият код тук
int sum_vector(/* параметър тук */) {
    // ...
}
int sum_vector(const std::vector<int>& vec) {
    int sum = 0;
    for (int i = 0; i < vec.size(); ++i) {
        sum += vec[i];
    }
    return sum;
}

// Или с range-based for loop
int sum_vector(const std::vector<int>& vec) {
    int sum = 0;
    for (int val : vec) {
        sum += val;
    }
    return sum;
}

Защо const reference:

  • Без копиране: Не копира целия vector (може да е хиляди елементи!)
  • Performance: O(1) вместо O(n) за копирането
  • const: Гарантира, че функцията няма да модифицира vector-а
  • Ефективност: Предава само един указател (8 bytes) вместо целия vector
ЛЕСНО-СРЕДНО

Задача 13: Dead Code Elimination​

Какво е dead code elimination? Дайте код snippet, където компилаторът може да премахне dead code, и обяснете какво би било премахнато.

Dead code elimination премахва код, който:

  • Никога не се изпълнява (unreachable)
  • Резултатът му никога не се използва

Пример:

int calculate(int x) {
    int unused = 42;           // ❌ Никога не се използва
    int result = x * 10;
    int temp = x + 5;          // ❌ Резултатът не се използва
    return result;
    int y = 100;               // ❌ Unreachable (след return)
}

// След dead code elimination:
int calculate(int x) {
    int result = x * 10;
    return result;
}

// Или още по-оптимизирано:
int calculate(int x) {
    return x * 10;
}

Средни упражнения (MEDIUM)​

Приложение и анализ на концепциите

СРЕДНО

Задача 14: Сравнение на контейнери​

Сравнете паметната организация и cache характеристиките на std::vector, std::list, и std::map. За кои операции всеки контейнер би имал най-добра производителност?

Помислете за непрекъсната vs разпръсната памет и как това влияе на cache locality.

Сравнение на контейнери: Памет и Cache

Паметна организация:

  • ✅ Непрекъсната памет (всички елементи са един до друг)
  • ✅ Динамична памет на heap
  • ✅ Capacity overhead (обикновено 1.5x или 2x growth factor)

Cache характеристики:

  • ✅ Отлична пространствена локалност
  • ✅ Отличен cache hit rate при итерация
  • ✅ CPU prefetching работи перфектно

Най-добра производителност за:

  • ✅ Последователен достъп / итерация (O(n), много бързо)
  • ✅ Random access по индекс (O(1))
  • ✅ Push/pop на края (O(1) amortized)
  • ❌ Insert/delete в средата (O(n), бавно)

Memory overhead: ~8 bytes (pointer, size, capacity)

Performance Comparison (1 млн. елемента):

Операцияvectorlistmap
Sequential iteration0.5ms50ms100ms
Random access1ns-50ns
Insert at end10ns100ns100ns
Insert in middle50ms10ns100ns
Sorted order❌❌✅

Правило за избор:

  1. std::vector - Default choice! (90% от случаите)

    • Използвай когато: честа итерация, random access, push_back

  2. std::list - Рядко (5% от случаите)

    • Използвай когато: много чести insert/delete в средата И рядко итерираш

  3. std::map - Специализиран (5% от случаите)

    • Използвай когато: нуждаеш се от sorted order И logarithmic lookup

Важно: Поради cache locality, дори std::vector с O(n) insert може да е по-бързо от std::list с O(1) insert за малки N!

СРЕДНО

Задача 15: Последователен vs Strided достъп​

Напишете две версии на функция, която умножава всички елементи в integer масив по 2: една с последователен достъп и една със strided достъп (stride = 10). Обяснете коя версия ще има по-добра cache производителност и защо.

void multiply_sequential(int* arr, int size) {
    // Вашият код тук
}

void multiply_strided(int* arr, int size, int stride) {
    // Вашият код тук
}

Помислете за пространствена локалност и cache lines.

void multiply_sequential(int* arr, int size) {
    for (int i = 0; i < size; ++i) {
        arr[i] = arr[i] * 2;
    }
}

void multiply_strided(int* arr, int size, int stride) {
    for (int i = 0; i < size; i += stride) {
        arr[i] = arr[i] * 2;
    }
}

Анализ на производителността:

Sequential (по-бърза):

  • ✅ Отлична пространствена локалност
  • ✅ Всеки достъп зарежда следващите 15-20 елемента в cache line (64 bytes)
  • ✅ Cache hit rate ~95%+
  • ✅ CPU prefetching работи отлично

Strided с stride=10 (по-бавна):

  • ❌ Лоша пространствена локалност
  • ❌ Скача през 10 елемента (40 bytes), пропуска заредените в кеша
  • ❌ Cache hit rate по-нисък
  • ❌ CPU prefetching не работи добре

Очаквана разлика: Sequential може да е 2-10x по-бърза в зависимост от размера на данните и cache архитектурата.

СРЕДНО

Задача 16: Loop Unrolling​

Обяснете какво е loop unrolling и защо може да подобри производителността. Напишете прост цикъл, който сумира масив, после покажете как цикълът може да изглежда след като компилаторът го unroll-не с фактор 4.

Loop Unrolling е оптимизация, при която тялото на цикъла се реплицира няколко пъти, намалявайки броя итерации.

Предимства:

  • Намалява loop overhead (проверки, increments, branches)
  • Подобрява instruction-level parallelism
  • Позволява по-добро използване на registers
  • Намалява branch mispredictions

Пример:

// Оригинален цикъл
int sum = 0;
for (int i = 0; i < 100; ++i) {
    sum += arr[i];
}

// След unrolling с фактор 4
int sum = 0;
int i = 0;
for (; i < 100 - 3; i += 4) {
    sum += arr[i];
    sum += arr[i+1];
    sum += arr[i+2];
    sum += arr[i+3];
}
// Остатък (ако size не е делим на 4)
for (; i < 100; ++i) {
    sum += arr[i];
}

Резултат: Вместо 100 итерации с проверки, имаме 25 итерации + евентуален остатък.

СРЕДНО

Задача 17: Идентифициране на оптимизации​

При даден следния код, идентифицирайте поне три оптимизации, които компилаторът може да приложи на ниво -O3:

int calculate(int x) {
    const int multiplier = 10;
    int result = x * multiplier + 5 * 2;
    int unused = x + 100;
    return result;
}

Оптимизации, които компилаторът може да приложи:

  1. Constant Propagation: multiplier = 10 се замества с 10 директно
  2. Constant Folding: 5 * 2 се изчислява като 10 по време на компилация
  3. Dead Code Elimination: int unused = x + 100; се премахва (никога не се използва)
  4. Expression Simplification: x * 10 + 10 може да се оптимизира допълнително

Резултат:

int calculate(int x) {
    return x * 10 + 10;
}

// Или дори:
int calculate(int x) {
    return (x + 1) * 10;  // По-ефективно на някои архитектури
}

Компилаторът може да генерира само няколко assembly инструкции вместо оригиналните много!

СРЕДНО

Задача 18: Избор на контейнер​

Трябва да съхранявате 10,000 integers и често да итерирате през всички, за да правите изчисления. Бихте ли избрали std::vector или std::list? Обосновете отговора си базирайки се на локалност на данните и производителни характеристики.

Отговор: std::vector

Обосновка:

Предимства:

  • ✅ Отлична локалност: Непрекъсната памет → отлични cache hits
  • ✅ Бърза итерация: Може да е 10-100x по-бърза от list
  • ✅ CPU prefetching: Работи перфектно с последователен достъп
  • ✅ Векторизация: Компилаторът може да векторизира циклите
  • ✅ Memory overhead: Минимален (само capacity overhead)

Измервания: За 10,000 елемента, итерацията е ~0.01ms

Заключение: За честа итерация, std::vector е почти винаги по-добрият избор. Използвайте std::list само ако имате чести вмъквания/изтривания в средата И рядко итерирате.

СРЕДНО

Задача 19: Common Subexpression Elimination (CSE)​

Какво е Common Subexpression Elimination? При даден следния код, покажете как компилаторът може да го оптимизира използвайки CSE:

int a = x * y + z;
int b = x * y + w;
int c = x * y + 5;

Common Subexpression Elimination (CSE) идентифицира изрази, които се изчисляват многократно, и ги изчислява веднъж, запазвайки резултата.

Оригинален код:

int a = x * y + z;
int b = x * y + w;  // x * y се изчислява отново
int c = x * y + 5;  // x * y се изчислява трети път

След CSE оптимизация:

int temp = x * y;   // Изчисли веднъж
int a = temp + z;
int b = temp + w;
int c = temp + 5;

Ползи:

  • Намалява броя изчисления от 3 умножения до 1
  • По-малко CPU инструкции
  • По-бързо изпълнение

Важно: CSE работи само ако x и y не се променят между изразите!

СРЕДНО

Задача 20: Cache lines и cache misses​

Обяснете концепцията за cache lines и cache misses. Защо strided достъп с голяма stride стойност води до лоша производителност?

Помислете за размера на cache line (типично 64 bytes) и как данните се зареждат в кеша.

Cache Line:

  • CPU-то зарежда данни в кеша не byte по byte, а в цели cache lines
  • Типичен размер: 64 bytes
  • Когато достъпите 1 byte, цялата cache line (64 bytes) се зарежда

Cache Hit vs Miss:

  • Cache Hit: Данните са в кеша → бързо (~4 цикъла)
  • Cache Miss: Данните не са в кеша → бавно (~200 цикъла)

Защо strided достъп е лош:

for (int i = 0; i < 1000; ++i) {
    sum += arr[i];  // i = 0, 1, 2, 3...
}

Cache behavior:

  • Достъп до arr[0] → зарежда cache line (64 bytes = 16 integers)
  • arr[1], arr[2], ..., arr[15] са вече в кеша → cache hits!
  • Hit rate: ~94% (1 miss на 16 достъпа)

Performance impact: Strided достъп може да е 10-100x по-бавен поради постоянните cache misses!

Средни-Трудни упражнения (MEDIUM-HARD)​

Напреднало приложение и експериментиране

СРЕДНО-ТРУДНО

Задача 21: Compiler Explorer анализ​

Използвайки Compiler Explorer (godbolt.org), напишете проста функция, която събира два масива element-wise. Компилирайте с -O0 и -O3. Опишете поне три разлики, които наблюдавате в генерирания assembly код.

void add_arrays(int* a, int* b, int* result, int n) {
    for (int i = 0; i < n; i++) {
        result[i] = a[i] + b[i];
    }
}

Търсете loop unrolling, векторизация (SIMD инструкции), и оптимизация на registers.

Compiler Explorer анализ:

Отидете на godbolt.org и въведете кода. Ето какво да търсите:

С -O0 (без оптимизации):

add_arrays(int*, int*, int*, int):
    push    rbp
    mov     rbp, rsp
    mov     QWORD PTR [rbp-24], rdi
    mov     QWORD PTR [rbp-32], rsi
    mov     QWORD PTR [rbp-40], rdx
    mov     DWORD PTR [rbp-44], ecx
    mov     DWORD PTR [rbp-4], 0          ; i = 0
.L3:
    mov     eax, DWORD PTR [rbp-4]
    cmp     eax, DWORD PTR [rbp-44]       ; i < n проверка
    jge     .L2                            ; branch
    mov     eax, DWORD PTR [rbp-4]
    cdqe
    lea     rdx, [0+rax*4]
    mov     rax, QWORD PTR [rbp-24]
    add     rax, rdx
    mov     ecx, DWORD PTR [rax]          ; зареди a[i]
    mov     eax, DWORD PTR [rbp-4]
    cdqe
    lea     rdx, [0+rax*4]
    mov     rax, QWORD PTR [rbp-32]
    add     rax, rdx
    mov     edx, DWORD PTR [rax]          ; зареди b[i]
    add     edx, ecx                       ; a[i] + b[i]
    ; ... още много инструкции за запис
    add     DWORD PTR [rbp-4], 1          ; i++
    jmp     .L3
.L2:
    pop     rbp
    ret

Характеристики на -O0:

  • ❌ Много stack операции (push/pop)
  • ❌ Всяка променлива се пази в stack memory
  • ❌ Loop counter (i) се чете/пише от памет всяка итерация
  • ❌ Много load/store операции
  • ❌ Прост, неоптимизиран loop
  • ✅ Лесно за debugging (1-to-1 mapping с source кода)

С -O3 (агресивни оптимизации):

add_arrays(int*, int*, int*, int):
    test    ecx, ecx
    jle     .L1                            ; ранен exit ако n <= 0
    lea     eax, [rcx-1]
    cmp     eax, 2
    jbe     .L7                            ; малко n -> scalar loop

    ; SIMD векторизация!
    movdqu  xmm0, XMMWORD PTR [rdi]        ; зареди 4 ints от a[]
    movdqu  xmm1, XMMWORD PTR [rsi]        ; зареди 4 ints от b[]
    paddd   xmm0, xmm1                     ; добави 4 ints наведнъж!
    movups  XMMWORD PTR [rdx], xmm0        ; запиши 4 ints

    ; Loop е unroll-нат и обработва 4+ елемента/итерация
    add     rdi, 16                        ; advance указателя с 4*4 bytes
    add     rsi, 16
    add     rdx, 16
    sub     r8d, 4                         ; counter -= 4
    jne     .L3                            ; повтори
.L1:
    ret

Характеристики на -O3:

  • ✅ SIMD векторизация: paddd xmm0, xmm1 добавя 4 integers наведнъж!
  • ✅ Loop unrolling: обработва 4+ елемента/итерация вместо 1
  • ✅ Register optimization: променливите са в registers (rdi, rsi, rdx)
  • ✅ Елиминирани проверки: интелигентна branch оптимизация
  • ✅ Малко инструкции: 5-10x по-малко assembly код
  • ✅ Pointer arithmetic: вместо array indexing

Ключови разлики:

Аспект-O0-O3
Инструкции/итерация~20-30~5-8 (4x по-малко)
SIMD❌ Скаларни операции✅ 4 елемента наведнъж
Loop unrolling❌ Няма✅ Фактор 4+
Registers❌ Stack memory✅ CPU registers
PerformanceBaseline5-10x по-бързо

Експеримент: Копирайте кода в Compiler Explorer и сравнете!

СРЕДНО-ТРУДНО

Задача 22: __restrict keyword​

Обяснете какво прави ключовата дума __restrict и защо позволява по-агресивни компилаторни оптимизации. Дайте пример, където използването на __restrict би направило значителна разлика в производителността.

__restrict keyword:

__restrict е обещание към компилатора, че даденият указател е единственият начин за достъп до паметта, която сочи (в този scope). Това означава, че не се припокрива с други указатели.

Защо е важно:

Без __restrict, компилаторът трябва да предполага pointer aliasing - че указателите могат да се припокриват, което инхибира оптимизациите.

Пример:

// Без __restrict - компилаторът е консервативен
void add_arrays_no_restrict(int* a, int* b, int* c, int n) {
    for (int i = 0; i < n; i++) {
        a[i] = b[i] + c[i];
    }
}

// С __restrict - позволява агресивни оптимизации
void add_arrays_with_restrict(int* __restrict a,
                               int* __restrict b,
                               int* __restrict c, int n) {
    for (int i = 0; i < n; i++) {
        a[i] = b[i] + c[i];
    }
}

Performance разлика:

На Compiler Explorer с -O3:

Без __restrict:

  • Компилаторът генерира скаларен код
  • Трябва да чете b[i] и c[i] преди да запише a[i]
  • Не може да векторизира безопасно

С __restrict:

  • SIMD векторизация: Обработва 4-8 елемента наведнъж
  • Използва vmovdqu, vpaddd инструкции (AVX)
  • 2-4x speedup за прости loops!
⚠️Внимание

Ако нарушите обещанието (предадете припокриващи се указатели), поведението е undefined!

СРЕДНО-ТРУДНО

Задача 23: Benchmark: vector vs list​

Проектирайте малък benchmark за измерване на разликата в производителността между итериране през std::vector<int> последователно versus итериране през std::list<int>. Обяснете очакваните резултати базирани на принципите за локалност на данните.

Използвайте std::chrono за измерване на времето. Тествайте с голям брой елементи (напр. 1 милион).

Benchmark: vector vs list итерация

#include <iostream>
#include <vector>
#include <list>
#include <chrono>

// Benchmark за std::vector
void benchmark_vector(int size) {
    std::vector<int> vec(size);

    // Инициализация
    for (int i = 0; i < size; i++) {
        vec[i] = i;
    }

    // Измерване на итерация
    auto start = std::chrono::high_resolution_clock::now();

    long long sum = 0;
    for (int i = 0; i < size; i++) {
        sum += vec[i];
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    std::cout << "vector iteration: " << duration.count() << " μs" << std::endl;
    std::cout << "Sum: " << sum << " (to prevent optimization)" << std::endl;
}

// Benchmark за std::list
void benchmark_list(int size) {
    std::list<int> lst;

    // Инициализация
    for (int i = 0; i < size; i++) {
        lst.push_back(i);
    }

    // Измерване на итерация
    auto start = std::chrono::high_resolution_clock::now();

    long long sum = 0;
    for (int val : lst) {
        sum += val;
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    std::cout << "list iteration: " << duration.count() << " μs" << std::endl;
    std::cout << "Sum: " << sum << " (to prevent optimization)" << std::endl;
}

int main() {
    const int SIZE = 1000000;  // 1 милион елемента

    std::cout << "Benchmarking with " << SIZE << " elements:" << std::endl;
    std::cout << "===========================================" << std::endl;

    benchmark_vector(SIZE);
    std::cout << std::endl;
    benchmark_list(SIZE);

    return 0;
}

Компилация и изпълнение:

# Компилирай с оптимизации
g++ -O3 -std=c++17 benchmark.cpp -o benchmark

# Изпълни
./benchmark

Очаквани резултати (типична x86-64 машина):

Benchmarking with 1000000 elements:
===========================================
vector iteration: 450 μs
Sum: 499999500000

list iteration: 25000 μs
Sum: 499999500000

Анализ на резултатите:

Метрикаstd::vectorstd::listРазлика
Време~450 μs~25,000 μs50-60x по-бавно!
Cache missesМалко (~6%)Много (~95%)-
Memory access patternПоследователенPointer chasing-
CPU prefetchingРаботи отличноНе работи-

Обяснение на резултатите:

std::vector (бързо):

  • ✅ Непрекъсната памет: Всички елементи са един до друг
  • ✅ Cache hits: При достъп до елемент, следващите 15-20 също са в кеша
  • ✅ CPU prefetching: CPU-то автоматично зарежда следващите данни
  • ✅ SIMD потенциал: Компилаторът може да векторизира (с -O3)

std::list (бавно):

  • ❌ Разпръсната памет: Всеки node е произволно място в heap-а
  • ❌ Cache misses: Всеки node достъп е вероятно cache miss
  • ❌ Pointer chasing: Трябва да следваме 1,000,000 указателя
  • ❌ No prefetching: CPU не може да предвиди къде е следващият node
  • ❌ No SIMD: Невъзможна векторизация

Практически извод:

За операции, които изискват честа итерация, std::vector е почти винаги по-добрият избор, дори ако има O(n) complexity за някои операции като insert в средата.

Изключения когато list може да е по-добър:

  • Много чести insert/delete операции в средата
  • Рядко итерираш през всички елементи
  • Нуждаеш се от stable iterators
СРЕДНО-ТРУДНО

Задача 24: Проблеми с локалността при матрично умножение​

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

void matrix_multiply(int** A, int** B, int** C, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

Помислете за достъпа до матрица B - той е column-wise, което е лошо за row-major съхранение.

Проблем с локалността:

Матриците в C++ са съхранени в row-major order (по редове):

  • A[i][k] - row-wise достъп → ✅ добра локалност
  • B[k][j] - column-wise достъп → ❌ лоша локалност!
  • C[i][j] - еднократна референция → OK

Защо е лошо:

  • B[0][0], B[1][0], B[2][0] са далеч един от друг в паметта
  • Всеки достъп до B е вероятно cache miss
  • За матрица 1024x1024, това е огромен performance удар!

Решение 1: Транспониране на B

void matrix_multiply_optimized(int** A, int** B, int** C, int n) {
    // Транспонирай B
    int** B_T = new int*[n];
    for (int i = 0; i < n; i++) {
        B_T[i] = new int[n];
        for (int j = 0; j < n; j++) {
            B_T[j][i] = B[i][j];
        }
    }

    // Умножение с транспонирана B
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                C[i][j] += A[i][k] * B_T[j][k];  // Сега и двата са row-wise!
            }
        }
    }
}

Решение 2: Loop Reordering (ikj order)

void matrix_multiply_ikj(int** A, int** B, int** C, int n) {
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            int temp = A[i][k];
            for (int j = 0; j < n; j++) {
                C[i][j] += temp * B[k][j];  // B е row-wise сега!
            }
        }
    }
}

Performance подобрение: 3-10x speedup за големи матрици!

СРЕДНО-ТРУДНО

Задача 25: Loop Invariant Code Motion​

Какво е loop invariant code motion? При дадения следния цикъл, идентифицирайте loop-invariant изчислението и покажете как компилаторът би го оптимизирал:

for (int i = 0; i < n; i++) {
    arr[i] = arr[i] * (x + y + z);
}

Loop Invariant Code Motion (LICM) премества изчисления, които не зависят от loop променливата, извън цикъла.

Оригинален код:

for (int i = 0; i < n; i++) {
    arr[i] = arr[i] * (x + y + z);  // x+y+z се изчислява n пъти!
}

Loop invariant изчисление: x + y + z - резултатът не зависи от i

След LICM оптимизация:

int temp = x + y + z;  // Изчисли веднъж преди цикъла
for (int i = 0; i < n; i++) {
    arr[i] = arr[i] * temp;
}

Ползи:

  • Намалява n-1 събирания
  • По-малко инструкции в loop body
  • По-добра performance (особено за големи n)

Важно: Работи само ако x, y, z не се променят в цикъла!

Трудни упражнения (HARD)​

Комплексен анализ и решаване на проблеми

ТРУДНО

Задача 26: Performance comparison: Arrays vs Containers​

Имплементирайте performance-critical функция, която обработва голям dataset (1 милион integers). Сравнете три имплементации: използвайки чисти масиви, std::vector, и std::list. Измерете и обяснете разликите в производителността, като вземете предвид компилаторни оптимизации, паметна организация, и cache поведение.

Компилирайте с -O3, използвайте std::chrono за timing, разгледайте assembly в Compiler Explorer.

Performance Comparison: Arrays vs Containers

#include <iostream>
#include <vector>
#include <list>
#include <array>
#include <chrono>
#include <numeric>

const int SIZE = 1000000;  // 1 милион integers

// Benchmark за чист масив
void benchmark_raw_array() {
    int* arr = new int[SIZE];

    // Инициализация
    for (int i = 0; i < SIZE; i++) {
        arr[i] = i;
    }

    auto start = std::chrono::high_resolution_clock::now();

    // Processing
    long long sum = 0;
    for (int i = 0; i < SIZE; i++) {
        sum += arr[i] * 2;
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    std::cout << "Raw array: " << duration.count() << " μs (sum: " << sum << ")" << std::endl;

    delete[] arr;
}

// Benchmark за std::vector
void benchmark_vector() {
    std::vector<int> vec(SIZE);

    // Инициализация
    for (int i = 0; i < SIZE; i++) {
        vec[i] = i;
    }

    auto start = std::chrono::high_resolution_clock::now();

    // Processing
    long long sum = 0;
    for (int i = 0; i < SIZE; i++) {
        sum += vec[i] * 2;
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    std::cout << "std::vector: " << duration.count() << " μs (sum: " << sum << ")" << std::endl;
}

// Benchmark за std::list
void benchmark_list() {
    std::list<int> lst;

    // Инициализация
    for (int i = 0; i < SIZE; i++) {
        lst.push_back(i);
    }

    auto start = std::chrono::high_resolution_clock::now();

    // Processing
    long long sum = 0;
    for (int val : lst) {
        sum += val * 2;
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    std::cout << "std::list: " << duration.count() << " μs (sum: " << sum << ")" << std::endl;
}

int main() {
    std::cout << "Performance Comparison (1M integers):" << std::endl;
    std::cout << "======================================" << std::endl;

    benchmark_raw_array();
    benchmark_vector();
    benchmark_list();

    return 0;
}

Компилация и измервания:

# С оптимизации
g++ -O3 -march=native -std=c++17 perf_test.cpp -o perf_test
./perf_test

Типични резултати:

Performance Comparison (1M integers):
======================================
Raw array: 420 μs (sum: 999999000000)
std::vector: 425 μs (sum: 999999000000)
std::list: 28500 μs (sum: 999999000000)

Анализ:

Performance: ⭐⭐⭐⭐⭐ (най-бърз)

Предимства:

  • ✅ Директен memory access (без overhead)
  • ✅ Отлична compiler оптимизация
  • ✅ SIMD векторизация (с -O3)
  • ✅ Минимален overhead

Недостатъци:

  • ❌ Ръчно memory management (new/delete)
  • ❌ Няма bounds checking
  • ❌ Unsafe (buffer overflow риск)
  • ❌ Няма size информация

Assembly анализ (Compiler Explorer):

Raw array / std::vector с -O3:

; SIMD векторизация (обработва 4 integers наведнъж)
.L3:
    movdqu  xmm0, XMMWORD PTR [rax]     ; зареди 4 ints
    paddd   xmm0, xmm0                   ; умножи по 2 (чрез добавяне)
    paddq   xmm1, xmm0                   ; добави към sum
    add     rax, 16                      ; следващи 4 елемента
    cmp     rax, rdx
    jne     .L3

std::list:

; Pointer chasing (скаларен код, no SIMD)
.L3:
    mov     eax, DWORD PTR [rbx]        ; зареди val
    add     rbx, QWORD PTR [rbx+8]      ; следвай next указател
    add     eax, eax                     ; умножи по 2
    add     rcx, rax                     ; добави към sum
    cmp     rbx, rbp
    jne     .L3

Практически извод:

Use CaseПрепоръка
Performance-critical кодstd::vector или raw array
General purposestd::vector (best balance)
Safety важнаstd::vector с .at()
Чести insert/deleteВсе пак std::vector! (освен ако наистина е bottleneck)
Stable iterators нужниstd::list (рядко)
ТРУДНО

Задача 27: Векторизация (SIMD)​

Обяснете концепцията за векторизация (SIMD). Напишете функция, която събира два масива от floats, компилирайте с -O3 -march=native, и анализирайте assembly output в Compiler Explorer. Можете ли да идентифицирате SIMD инструкции? Какви условия трябва да бъдат изпълнени за да може компилаторът да векторизира цикъл?

SIMD (Single Instruction, Multiple Data):

  • Процесорна архитектура, която позволява паралелна обработка на множество данни с една инструкция
  • Модерните процесори поддържат SSE, AVX, AVX2, AVX-512

Пример:

void add_arrays(float* a, float* b, float* result, int n) {
    for (int i = 0; i < n; i++) {
        result[i] = a[i] + b[i];
    }
}

С -O3 -march=native, компилаторът може да генерира:

  • AVX инструкции: vaddps (добавя 8 floats наведнъж)
  • Loading: vmovups (зарежда 8 floats)
  • 8x паралелизъм → 8x по-бързо!

Условия за векторизация:

  1. ✅ Прост loop с известен брой итерации
  2. ✅ Независими операции (data independence)
  3. ✅ Непрекъснат паметен достъп
  4. ✅ Поддържан тип данни (int, float, double)
  5. ❌ Няма pointer aliasing (или използвайте __restrict)
  6. ❌ Няма conditionals в loop body (или използвайте predication)
ТРУДНО

Задача 28: Проектиране на структура от данни за игра​

Проектирайте структура от данни за игра, която трябва да:

  • Съхранява 100,000 game entities
  • Често итерира през всички entities за обновяване на позициите им
  • Понякога вмъква/премахва entities от произволни позиции

Обосновете избора на контейнер базирайки се на локалност, memory overhead, и производителност на операциите. Обсъдете trade-offs.

Помислете за комбиниран подход или специализирани структури като entity-component systems.

Дизайн на структура от данни за игра

Изисквания анализ:

  1. 100,000 entities (голям брой)
  2. Честа операция: итерация за update на позиции
  3. Рядка операция: insert/delete на произволни позиции

Решение: std::vector с "Tombstone" pattern (или Entity-Component System)

struct Entity {
    int id;
    float x, y, z;      // Позиция
    bool active;        // За "soft delete"

    void update(float deltaTime) {
        x += deltaTime;
        y += deltaTime * 0.5f;
    }
};

class EntityManager {
private:
    std::vector<Entity> entities;

public:
    // Добавяне на entity (O(1) amortized)
    void add_entity(int id, float x, float y, float z) {
        entities.push_back({id, x, y, z, true});
    }

    // Update на всички entities (отлична cache locality!)
    void update_all(float deltaTime) {
        for (Entity& e : entities) {
            if (e.active) {
                e.update(deltaTime);
            }
        }
    }

    // Delete с swap-and-pop (O(1), но променя реда)
    void remove_entity_fast(int id) {
        for (size_t i = 0; i < entities.size(); i++) {
            if (entities[i].id == id) {
                // Swap със последния елемент
                std::swap(entities[i], entities.back());
                entities.pop_back();
                return;
            }
        }
    }

    // Delete със запазване на реда (O(n), рядко)
    void remove_entity_ordered(int id) {
        entities.erase(
            std::remove_if(entities.begin(), entities.end(),
                [id](const Entity& e) { return e.id == id; }),
            entities.end()
        );
    }

    // Soft delete (O(1), не премахва веднага)
    void deactivate_entity(int id) {
        for (Entity& e : entities) {
            if (e.id == id) {
                e.active = false;
                return;
            }
        }
    }

    // Periodic cleanup (извиква се рядко)
    void cleanup_inactive() {
        entities.erase(
            std::remove_if(entities.begin(), entities.end(),
                [](const Entity& e) { return !e.active; }),
            entities.end()
        );
    }
};

Предимства:

  • ✅ Отлична итерация: Непрекъсната памет → cache-friendly
  • ✅ SIMD потенциал: Компилаторът може да векторизира update loop
  • ✅ Бърз insert: push_back е O(1) amortized
  • ✅ Гъвкавост: swap-and-pop за бързо изтриване, или ordered delete ако трябва

Недостатъци:

  • ⚠️ Delete може да променя реда (swap-and-pop)
  • ⚠️ Soft delete изисква проверка на active (малък overhead)

Trade-offs таблица:

Критерийstd::vectorstd::vector + SoA (ECS)std::list
Iteration speed⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐
Cache localityОтличнаПерфектнаКатастрофална
SIMD potentialДобърПерфектенНяма
Insert speedO(1) amortizedO(1) amortizedO(1)
Delete speedO(n) или O(1)*O(n) или O(1)*O(1)**
Memory overheadМинималенМинимален16 bytes/entity
Code complexityПростСреднаПрост

*O(1) със swap-and-pop, O(n) със запазване на ред **Само ако имаш iterator

Препоръка:

Използвай std::vector с swap-and-pop като начален дизайн. Ако update loop-ът стане bottleneck, мигрирай към SoA/ECS.

Практически измервания (100,000 entities update):

  • std::vector: ~0.5ms ⭐⭐⭐⭐⭐
  • ECS (SoA): ~0.3ms ⭐⭐⭐⭐⭐
  • std::list: ~30ms ❌❌❌
ТРУДНО

Задача 29: Cache performance анализ​

Анализирайте следния код за cache производителност. Изчислете (приблизително) колко cache lines биха били достъпени ако cache line size е 64 bytes и int е 4 bytes:

// Matrix е 1024x1024, съхранена в row-major order
void process_matrix_columns(int matrix[1024][1024]) {
    for (int col = 0; col < 1024; col++) {
        for (int row = 0; row < 1024; row++) {
            matrix[row][col] *= 2;
        }
    }
}

Как бихте преструктурирали кода за подобряване на cache производителността?

Анализ на cache performance:

Row-major order означава:

  • Елементите на един ред са съседни в паметта
  • matrix[0][0], matrix[0][1], matrix[0][2]... са последователни

Проблемът с този код:

  • Достъпва column-wise: matrix[0][0], matrix[1][0], matrix[2][0]...
  • Всеки елемент е на 4096 bytes разстояние (1024 * 4)
  • Cache line е само 64 bytes (16 integers)

Cache line изчисления:

  • Cache line съдържа 16 integers
  • Всеки достъп зарежда 16 елемента от СЪЩИЯ ред
  • Но ние искаме елементи от различни редове!
  • Cache misses: почти 100% (1024 * 1024 = 1,048,576 misses)

Оптимизирано решение - row-wise достъп:

void process_matrix_rows(int matrix[1024][1024]) {
    for (int row = 0; row < 1024; row++) {      // Обръщаме циклите!
        for (int col = 0; col < 1024; col++) {
            matrix[row][col] *= 2;
        }
    }
}

Cache line изчисления (оптимизиран):

  • Един cache miss на 16 integers
  • Cache misses: ~65,536 (1024 * 1024 / 16)
  • 16x по-малко cache misses!

Performance подобрение: 10-50x speedup!

ТРУДНО

Задача 30: Cache-oblivious matrix transpose​

Имплементирайте и анализирайте cache-oblivious matrix transpose алгоритъм. Сравнете производителните характеристики с naive имплементация, обяснявайки как cache blocking подобрява локалността. Използвайте Compiler Explorer за да разгледате как различните нива на оптимизация влияят на двете имплементации.

Разгледайте recursive divide-and-conquer подход и blocked matrix operations.

Cache-Oblivious Matrix Transpose

Проблем: Naive matrix transpose има лоша cache locality при едната от операциите (или read или write е column-wise).

void transpose_naive(int** src, int** dst, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dst[j][i] = src[i][j];
            // src[i][j] - row-wise access ✅ добра locality
            // dst[j][i] - column-wise access ❌ лоша locality
        }
    }
}

Проблем:

  • src се чете row-wise → добра locality
  • dst се пише column-wise → лоша locality
  • За матрица 1024x1024: ~50% cache miss rate
  • Performance: ~10ms за 1024x1024 матрица

Пълен benchmark код:

#include <iostream>
#include <chrono>
#include <algorithm>

const int N = 1024;

// Helper: алокирай 2D масив
int** allocate_matrix(int n) {
    int** mat = new int*[n];
    for (int i = 0; i < n; i++) {
        mat[i] = new int[n];
    }
    return mat;
}

// Helper: инициализирай матрица
void initialize_matrix(int** mat, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            mat[i][j] = i * n + j;
        }
    }
}

// ... (paste transpose functions from above)

int main() {
    int** src = allocate_matrix(N);
    int** dst_naive = allocate_matrix(N);
    int** dst_blocked = allocate_matrix(N);
    int** dst_oblivious = allocate_matrix(N);

    initialize_matrix(src, N);

    // Benchmark Naive
    auto start = std::chrono::high_resolution_clock::now();
    transpose_naive(src, dst_naive, N);
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Naive: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
              << " ms" << std::endl;

    // Benchmark Blocked
    start = std::chrono::high_resolution_clock::now();
    transpose_blocked(src, dst_blocked, N);
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Blocked: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
              << " ms" << std::endl;

    // Benchmark Cache-Oblivious
    start = std::chrono::high_resolution_clock::now();
    transpose_cache_oblivious(src, dst_oblivious, N);
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Cache-Oblivious: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
              << " ms" << std::endl;

    return 0;
}

Очаквани резултати (1024x1024 матрица):

Naive: 12 ms
Blocked: 4 ms
Cache-Oblivious: 3 ms

Cache анализ:

МетодCache MissesSpeedup
Naive~1M missesBaseline
Blocked (32x32)~300K misses3x
Cache-Oblivious~250K misses4x

Compiler Explorer анализ:

Тествайте на godbolt.org с -O3 -march=native:

  • Naive: Генерира прост nested loop
  • Blocked: Loop tiling с известен block size
  • Recursive: Tail-call оптимизация + loop fusion

Ключов извод:

Cache-oblivious алгоритмите използват divide-and-conquer за да постигнат оптимална locality на всяко cache ниво без да знаят cache sizes!

Допълнителни ресурси​

ℹ️Полезни ресурси за практика

Инструменти:

Практически съвети:

  • Експериментирайте с различни optimization levels: -O0, -O1, -O2, -O3
  • Сравнявайте assembly output за различни имплементации
  • Измервайте производителността с реални данни
  • Профилирайте кода с tools като perf, valgrind --tool=cachegrind
✅Ключови точки за запомняне
  • Локалността е критична: Оптимизирайте за пространствена и временна локалност
  • Compiler Explorer е вашият най-добър приятел: Използвайте го често!
  • Измервайте, не гадайте: Винаги профилирайте преди и след оптимизации
  • Предпочитайте std::vector: За повечето случаи е най-добрият избор
  • Разбирането е сила: Знаейки как компилаторът работи, пишете по-добър код