Сегодня хочу рассказать о двух оптимизациях (они не связаны между собой, просто так совпало):
Начнем с чего попроще:
У вас есть такой код:
std::vector<Data> storage;
for (int i = 0; i < some_n; ++i) {
storage.push_back(some_data);
}
Что с ним не так?Верно, log(some_n) аллокаций.
Как это исправить?
Верно, вызвать
storage.reserve(some_n).Любопытно, что такую оптимизацию умеет в простых кейсах распознавать даже clang-tidy: https://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-vector-operation.html
Продолжим, что если мы не знаем сколько push_back будет?
Мы можем сделать reserve на максимум/минимум/среднее/етс, если его знаем, а что если при этом нам важно потребление памяти?
32 битные системы, большие объемы данных, выделения для gpu, для них все становится несколько хуже, и начинаются, например, вызовы shrink_to_fit:
https://github.com/mapbox/vector-tile/blob/master/include/mapbox/vector_tile.hpp#L284
Который может быть пустой заглушкой,
На самом деле в таких случаях, хорошим подходом может быть выполнить часть вычислений без сохранения результата, посчитать количество необходимых байт.
В итоге мы получим одну аллокацию под размер данных.
Отлично, но вроде мы замедлили код 2 раза?
На самом деле, как правило нет.
1) Обычно нужно сделать предварительных вычислений в несколько раз меньше, так как нужно узнать только количество вызовов push_back/аналога, то есть замедление не в 2 раза, а в 1 + 1/k, где k это то насколько меньше мы можем считать.
2) Большие аллокации это дорого (как правило работа с деревьями поиска внутри аллокатора), мы избавились от всех кроме одной.
3) Часто наш код многопоточный, а большие аллокации это глобальная синхронизация внутри аллокатора (для мелких < 4-65 КБ, обычно есть тредлокал/етс пулы, для остальных же глобальный спинлок/мьютекс етс)
4) Возможно мы смогли получить более плоскую и cache friendly структуру на данных.
Я несколько раз применял эту идею и получал значительно более компактную и простую структуру данных, ещё и работало быстрее.
Почему я вообще вспомнил об этом?
Недавно на лекции по GPGPU про sparse matrix рассказали о таком же подходе для перемножения матриц, и том что он там также оказался хорош.
Пара примеров из open source проектов (оказалось я совершенно без понятия как такое искать, ведь в большинстве таких мест, скорее всего будет использоваться не vector::reserve, а какая-то ручная аллокация), поэтому закину тривиальный пример, join строк: https://github.com/abseil/abseil-cpp/blob/master/absl/strings/internal/str_join_internal.h#L233
Про вторую оптимизацию более кратко:
Допустим есть некоторая операция, которая в начале увеличивает атомарный счётчик, а в конце уменьшает.
При достижении нуля происходит что то тяжёлое.
Собственно происходит добавление кучи таких параллельных операций.
Как добиться того чтобы тяжёлая операция происходила не более одного раза?
Предлагается до всех добавлений увеличить счётчик, так чтобы достижение нуля было невозможно, и уменьшить на соответствующую величину после добавлений.
Пример: https://github.com/YACLib/YACLib/blob/main/include/yaclib/algo/detail/wait_impl.hpp#L17
Пример из ядра линукса: TODO