Какие знаешь способы ускорения работы программы?

Способы ускорения работы программы

Оптимизация — это систематический процесс. Вот все методы, которые использую:

Уровень 1: Профилирование и анализ

Перед оптимизацией нужно понять где находится bottleneck:

# CPU профилирование
perf record -F 99 ./program
perf report

# Flamegraph визуализация
perf record -g ./program
perf script | stackcollapse-perf.pl | flamegraph.pl > graph.svg

# Memory профилирование
valgrind --tool=massif ./program
ms_print massif.out.123

Уровень 2: Алгоритмическая оптимизация

Самое важное — правильный алгоритм:

// Плохо: O(n²)
int find_duplicate_naive(const std::vector<int>& v) {
    for (int i = 0; i < v.size(); ++i) {
        for (int j = i + 1; j < v.size(); ++j) {
            if (v[i] == v[j]) return v[i];
        }
    }
    return -1;
}

// Хорошо: O(n)
int find_duplicate_fast(const std::vector<int>& v) {
    std::unordered_set<int> seen;
    for (int x : v) {
        if (seen.count(x)) return x;
        seen.insert(x);
    }
    return -1;
}

Сложность алгоритма — критична для больших данных.

Уровень 3: Структуры данных

Выбор правильной структуры влияет на производительность:

// Плохо: O(n) поиск в vector
std::vector<Record> records;
auto it = std::find_if(records.begin(), records.end(), 
                       [id](const Record& r) { return r.id == id; });

// Хорошо: O(1) поиск в map
std::unordered_map<int, Record> records;
auto record = records[id];

Выбор между vector, list, map, unordered_map влияет на 10-100x.

Уровень 4: Cache-friendly код

Cache misses — это 100-200x замедление:

// Плохо: случайный доступ к памяти
struct Entity {
    int id;
    int value;
    std::string name;
    std::vector<int> data;
};

// Хорошо: cache-aware layout
std::vector<int> ids, values;
for (int i = 0; i < entities.size(); ++i) {
    sum += values[i];  // Sequential access, cache-friendly
}

Уровень 5: SIMD и параллелизм

Использование возможностей процессора:

// Хорошо: SIMD версия (AVX)
void add_arrays_simd(const float* a, const float* b, float* c, int n) {
    for (int i = 0; i < n; i += 8) {
        __m256 va = _mm256_loadu_ps(&a[i]);
        __m256 vb = _mm256_loadu_ps(&b[i]);
        __m256 vc = _mm256_add_ps(va, vb);
        _mm256_storeu_ps(&c[i], vc);
    }
}

// Или OpenMP
#pragma omp simd
for (int i = 0; i < n; ++i) {
    c[i] = a[i] + b[i];
}

Уровень 6: Многопоточность

Распараллеливание для многоядерных систем:

// OpenMP
#pragma omp parallel for
for (int i = 0; i < n; ++i) {
    result[i] = expensive_operation(data[i]);
}

Уровень 7: Memory allocation

Выделение памяти — дорогая операция:

// Плохо: много аллокаций
for (int i = 0; i < 1000000; ++i) {
    std::vector<int> tmp(100);
    // ...
}

// Хорошо: переиспользование
std::vector<int> tmp;
tmp.reserve(100);
for (int i = 0; i < 1000000; ++i) {
    tmp.clear();
    // ...
}

Уровень 8: Компилятор оптимизации

# Включить оптимизации
g++ -O3 -march=native -flto program.cpp
clang++ -O3 -march=native -flto program.cpp

Уровень 9: I/O оптимизация

// Хорошо: буферизация
std::cout.rdbuf()->pubsetbuf(buffer, buffer_size);
for (int i = 0; i < 1000000; ++i) {
    std::cout << i << "\n";
}

Практический процесс оптимизации

1. Измерить — профилирование показывает реальные bottleneck'и
2. Найти горячие линии — 80% времени в 20% кода
3. Оптимизировать алгоритм — дает 10-100x улучшение
4. Выбрать структуры данных — может дать 10x
5. Cache-aware дизайн — 2-5x улучшение
6. SIMD — 4-8x для числовых вычислений
7. Многопоточность — линейное масштабирование с ядрами
8. Компилятор оптимизации — "free" улучшение 10-20%
9. Профилировать снова — убедиться что оптимизации помогли

Вывод: Самое эффективное ускорение — это правильный алгоритм и структуры данных. Cache-aware программирование дает больший прирост, чем микро-оптимизации. Всегда профилируй перед оптимизацией!