Коротко — что происходит в исходном фрагменте и как улучшить.
Исходник:
std::vector v;
for (int i = 0; i < $1000000$; ++i) v.push_back(i);
Проблемы и улучшения (алгоритм/инженерия):
1) Устранить перералокации
- Причина: по умолчанию vector увеличивает capacity геометрически; при первых вставках происходят копирование/реалокации.
- Решение: заранее выделить память:
v.reserve($1000000$);
for (int i = 0; i < $1000000$; ++i) v.push_back(i);
Результат: одна аллокация вместо множества, меньше копирований, лучше время.
2) emplace_back vs push_back
- Для типов-тривиалов (int) emplace_back ничего не даёт по сравнению с push_back (для сложных типов emplace_back может избежать лишнего копирования/перемещения).
- Вывод: для int используйте удобный push_back; для сложных типов — emplace_back.
3) Альтернативы заполнения
- Если известно n, можно делать:
v.reserve(n); for (...) v.push_back(...);
или
v.resize(n); std::iota(v.begin(), v.end(), 0); // семантически удобно
- Замечание: resize для простой типизации value-initializes элементы (запись), затем iota снова пишет — может получиться лишняя запись. Поэтому reserve+push_back часто эффективнее, если вы создаёте значения один раз.
4) Аллокаторы
- Для одного vector аллокатор влияет мало (одна большая аллокация). Значение кастомного аллокатора проявится при большом количестве мелких аллокаций или при специфических требованиям: pool/arena, alignment, huge pages.
- Системные улучшения: использовать быстрые аллокаторы (tcmalloc/jemalloc) или включить huge pages, если память и нагрузка оправдывают.
- Если у вас много контейнеров с частыми аллокациями — рассмотрите monotonic/arena allocator.
5) Кеширование и локальность
- vector хранит элементы подряд — отличная кеш-локальность. Последовательная запись/чтение хорошо использует кеш-линии (prefetcher CPU).
- Избегайте случайных вставок в середину, частых аллокаций, указателей/контейнеров со слабой локальностью (list, map) — они приводят к кэш-промахам.
- Для больших объёмов можно экспериментировать с предзатравкой (touch pages) или с выравниванием/huge pages, но это редко нужно.
6) Компилятор и сборка
- Собирать в релизе: -O2/-O3, -march=native, LTO, PGO — это часто даёт больше, чем микрооптимизации в коде.
- Проверять инлайнинг и оптимизацию циклов.
7) Профилирование — обязательно перед оптимизацией
- Инструменты: Linux perf, perf record/report, FlameGraphs, callgrind/valgrind, Intel VTune, Xcode Instruments.
- Правила: профиль в релизной сборке, с реальной нагрузкой; сначала найти «горячие точки», затем оптимизировать.
- Измеряйте время аллокаций, копирований, кеш-промаxов, branch-mispredicts.
8) Когда микрооптимизации бессмысленны
- Если алгоритмическая сложность доминирует: переход от $O(n^2)$ к $O(n\log n)$ или $O(n)$ даст куда больший выигрыш, чем оптимизация вставок или мелких ветвей.
- Пример: сортировка million элементов — оптимизация push_back не сопоставима с выбором лучшего алгоритма/структуры.
- Иерархия приоритета: алгоритм > структура данных > аллокации/локальность > микрооптимизации.
9) Практические рекомендации (сводка)
- Если n известно: v.reserve(n) + push_back; или если удобнее — v.resize(n) + заполнение (учитывайте возможную дополнительную инициализацию).
- Для int emplace_back не нужен.
- Профилируйте в релизной сборке перед оптимизацией.
- Рассмотрите системный аллокатор (tcmalloc/jemalloc) или кастомный allocator только если аллокации — явный узкий профиль.
- Ставьте оптимизацию в области алгоритмов/локальности прежде чем заниматься micro-tuning.
Если нужно — могу привести конкретные измерения (микробенчмарки) для разных вариантов кода на вашей машине и показать профили.