То, о чем я собираюсь рассказать в статье настолько тривиально, что любой, даже начинающий, разработчик уже это знает - я правда очень на это надеюсь. Тем не менее, приходящий на ревью код, показывает, что люди как делали, так и продолжают делать что-то подобное:
bool LoadAnimation(str::string filename);
void DrawLines(std::vector<Points> path);
Matrix RotateObject(Matrix m, Angle angle);
int DrawSprite(Sprite sprite);
Что общего у этих функций? Аргумент по значению. И каждый раз, когда вызывается подобный функционал в коде, создается копия входных данных в своем временном контексте и передается внутрь функции. И можно еще простить редко вызываемый код, вроде загрузки анимаций или понадеяться на компилятор, что сработают оптимизации и он уничтожит копирование данных, но как назло, чаще всего такой подход к разработке уничтожает только перформанс и фпсы.
К любым оптимизациям надо подходить только! после анализа их в профайлере, копии как оказалось могут и не быть дорогой операцией. Это например зависит от размера объекта, так компилятор отлично справляется с передачей по значению объектов до 32 байт, расходы конечно есть, но они очень незначительные и не ловятся на бенчмарках. Вендор может накрутить "чего-то такого в платформу и компилятор", что копирование 32кб из специальных областей памяти будет быстрее, чем сложение пары чисел. А в самой игре оптимизация "горячего кода", будем говорить честно, часто является не самой большой проблемой общей производительности. Но вот динамическое выделении памяти может преподнести немало сюрпризов, особенно при бездумном применении.
Но даже если накладные расходы небольшие, есть ли смысл тратить процессорные циклы, когда можно этого избежать? Вот эти "потерянные 2-3%" размазанного перфа, которые даже в профайлере не светятся, очень трудно потом ловить, и еще труднее чинить.
Скрытая алокация на строках
#include <string>
#include <numeric>
size_t PassStringByValueImpl(std::string str) {
return std::accumulate(str.begin(), str.end(), 0, [] (size_t v, char a) {
return (v += (a == ' ') ? 1 : 0);
});
}
size_t PassStringByRefImpl(const std::string& str) {
return std::accumulate(str.begin(), str.end(), 0, [] (size_t v, char a) {
return (v += (a == ' ') ? 1 : 0);
});
}
const std::string LONG_STR("a long string that can't use Small String Optimization");
void PassStringByValue(benchmark::State& state) {
for (auto _ : state) {
size_t n = PassStringByValueImpl(LONG_STR);
benchmark::DoNotOptimize(n);
}
}
BENCHMARK(PassStringByValue);
void PassStringByRef(benchmark::State& state) {
for (auto _ : state) {
size_t n = PassStringByRefImpl(LONG_STR);
benchmark::DoNotOptimize(n);
}
}
BENCHMARK(PassStringByRef);
void PassStringByNone(benchmark::State& state) {
for (auto _ : state) {
size_t n = 0;
benchmark::DoNotOptimize(n);
}
}
BENCHMARK(PassStringByNone);
QuickBench: https://quick-bench.com/q/f6sBUE7FdwLdsU47G26yPOnnViY
Скрытая алокация на массивах
size_t SumValueImpl(std::vector<unsigned> vect)
{
size_t sum = 0;
for(unsigned val: vect) { sum += val; }
return sum;
}
size_t SumRefImpl(const std::vector<unsigned>& vect)
{
size_t sum = 0;
for(unsigned val: vect) { sum += val; }
return sum;
}
const std::vector<unsigned> vect_in = { 1, 2, 3, 4, 5 };
void PassVectorByValue(benchmark::State& state) {
for (auto _ : state) {
size_t n = SumValueImpl(vect_in);
benchmark::DoNotOptimize(n);
}
}
BENCHMARK(PassVectorByValue);
void PassVectorByRef(benchmark::State& state) {
for (auto _ : state) {
size_t n = SumRefImpl(vect_in);
benchmark::DoNotOptimize(n);
}
}
BENCHMARK(PassVectorByRef);
void PassVectorByNone(benchmark::State& state) {
for (auto _ : state) {
size_t n = 0;
benchmark::DoNotOptimize(n);
}
}
BENCHMARK(PassVectorByNone);
QuickBench: https://quick-bench.com/q/GU68xgT0r97eYaCKxMzm9bXJei4
Компилятор все равно умнее
В случаях, если копируемый объект занимает размер меньше пары тройки десятков байт мы вообще не заметим никакой разницы от передачи его по ссылке, вплоть до того, что сгенерированный ассемблерный код будет "почти одинаковым".
Копирование есть, но не влияет
struct Vector{
double x;
double y;
double z;
};
double DotProductObjectImpl(Vector a, Vector p){
return (a.x*p.x + a.y*p.y + a.z*p.z);
}
double DotProductRefImpl(const Vector& a, const Vector& p){
return (a.x*p.x + a.y*p.y + a.z*p.z);
}
void DotProductObject(benchmark::State& state) {
Vector in = {1,2,3};
for (auto _ : state) {
double dp = DotProductObjectImpl(in, in);
benchmark::DoNotOptimize(dp);
}
}
BENCHMARK(DotProductObject);
void DotProductRef(benchmark::State& state) {
Vector in = {1,2,3};
for (auto _ : state) {
double dp = DotProductObjectImpl(in, in);
benchmark::DoNotOptimize(dp);
}
}
BENCHMARK(DotProductRef);
void DotProductNone(benchmark::State& state) {
for (auto _ : state) {
size_t n = 0;
benchmark::DoNotOptimize(n);
}
}
BENCHMARK(DotProductNone);
QuickBench: https://quick-bench.com/q/drlH-a9o4ejvWP87neq7KAyyA8o
В этом примере нам конечно известен размер структуры, да и пример очень простой. С другой стороны, если передача по ссылке явно работает не медленнее таковой по значению, использование const&
будет "such best as we can". А передача примитивных типов по const&
и вообще ни на что не влияет при компиляции с флагом /Ox
А раз нет никаких преимуществ, писать что-то подобное const int &i
лишено смысла, но некоторые всеже пишут.
Reserve my vector
Массивы имеют огромное преимущество по сравнению с другими структурами данных, которое зачастую перекрывает любые удобства других контейнеров: их элементы следуют в памяти один за другим. Можно долго обсуждать влияние применяемого алгоритма на время работы и как это может повлиять на производительность, но ничего быстрее кешлиний процессора у нас нет, и чем больше элементов лежит в кеше, тем быстрее будет работать самый банальный перебор. Любое обращение за пределы L1 кеша сразу кратно увеличивает время работы.
Но работая с векторами (динамическими массивами) многие забывают, или не помнят, что там под капотом. А там если закончилось выделенное место, а оно было например выделено для 1 (одного) элемента, то:
Выделяется новый блок памяти, который больше.
Копируются все элементы, которые были сохранены в новый блок.
Удаляется старый блок памяти
Все эти операции затратные, очень быстрые, но все равно затратные. И происходят они под капотом и не видны:
- если не лазить смотреть код стандартной библиотеки
- не смотреть профайлером алокации
- доверять коду, который написан вендором (хотя тут придется принять вещи как они есть)
Use reserve, Luke
static void NoReserve(benchmark::State& state)
{
for (auto _ : state) {
// create a vector and add 100 elements
std::vector<size_t> v;
for(size_t i=0; i<100; i++){ v.push_back(i); }
benchmark::DoNotOptimize(v);
}
}
BENCHMARK(NoReserve);
static void WithReserve(benchmark::State& state)
{
for (auto _ : state) {
// create a vector and add 100 elements, but reserve first
std::vector<size_t> v;
v.reserve(100);
for(size_t i=0; i<100; i++){ v.push_back(i); }
benchmark::DoNotOptimize(v);
}
}
BENCHMARK(WithReserve);
static void CycleNone(benchmark::State& state) {
// create the vector only once
std::vector<size_t> v;
for (auto _ : state) {
benchmark::DoNotOptimize(v);
}
}
BENCHMARK(CycleNone);
QuickBench: https://quick-bench.com/q/OuiFp3VOZKNKaAZgM_0DkJxRock
Ну и напоследок пример того, как можно убить перф и получить просадку до 10 FPS на ровном месте, просто при движении мышкой по игровому полю. Движок называть не буду, баг уже пофиксили. Найдете ошибку, пишите в коменты :)
bool findPath(Vector2 start, Vector2 finish) {
...
while (toVisit.empty() == false)
{
...
if (result == OBSTACLE_OBJECT_IN_WAY)
{
...
const std::vector<Vector2> directions{ {1.f, 0.f}, {-1.f, 0.f}, {0.f, 1.f}, {0.f, -1.f} };
for (const auto& dir : directions)
{
auto nextPos = currentPosition + dir;
if (visited.find(nextPos) == visited.end())
{
toVisit.push({ nextPos, Vector2::DistanceSq(center, nextPos) });
}
}
}
}
}
Комментарии (31)
TheDestr
30.09.2024 19:48По поводу ошибки в последнем примере:
Скрытый текст
Из очевидного. Не хватает словечка static перед const я полагаю. Но не верится что это могло дать такую просадку.
Хотелось бы прочитать больше о таких же тривиальных советах к обозначенным проблемам. По типу, создать вектор под заранее известный или ожидаемый размер ячеек. Или в каких случаях стоит использовать врапперы по типу std::array.
Если такие ошибки делаются, то конечно нужно обсуждать.
Спасибо за статью.
dalerank Автор
30.09.2024 19:48Вы правы насчет ошибки, оно и есть, но даже так оно будет афектить пусть и не так сильно. Подскажу немного, карта размером 300х300 тайлов, не самая большая скажем, попробуйте пройти условно от одного угла до другого, обойти препятствия и т.д.
TheDestr
30.09.2024 19:48Вы намекаете на расширение
toVisit
?Но мне показалось тут ошибка в том, что нужно применять эвристику и нормальный алгоритм поиска. А тут как будто почти брутфорс. Но это уже багой не назвать. Хотя может быть это все есть под многоточием...
Revertis
30.09.2024 19:48+1Как раз модель владения в Расте заставляет передавать переменные по ссылке, либо явно копировать с помощью
clone()
.KanuTaH
30.09.2024 19:48Неа. В расте его типичная фейковая мув-семантика - это как раз большой любитель делать
memcpy()
"под капотом". Пример:struct S { i: i32 } fn foo(s: S) { println!("{:p}", &s); } fn main() { let s = S{ i: 100 }; println!("{:p}", &s); foo(s); }
Запускаем и видим, что напечатались разные адреса, а это означает, что где-то произошел
memcpy()
. Так что никто никого не "заставляет", если об этом специально не заботиться, то будут все те же грабли.goglom
30.09.2024 19:48+1Как будто вы тут в заблуждение вводите. Очевидно что move для структур с тривиальными типами в полях ничем не будет отличаться от copy. Но это обычно и не создаёт проблем (но опять же, если дурак будет по значению жирные структуры подавать, то ни rust, ни c++ тут не спасут).
Если бы в примере использовалась бы структура владеющая дин. памятью, то тут бы implicit move дал бы выйгрыш по числу аллокаций по сравнению с C++, где для того же эффекта надо было бы звать для аргумента std::move явно
KanuTaH
30.09.2024 19:48+1Как будто вы тут в заблуждение вводите.
Да неужели.
Очевидно что move для структур с тривиальными типами в полях ничем не будет отличаться от copy.
А вот оратору выше это явно не очевидно, он утверждает, что "модель владения раста чего-то там заставляет". Модель владения раста ни разу не "заставляет" передавать жирные структуры или, скажем, массивы со стека по ссылке, ей на это по-фи-гу, погромист должен следить за этим сам.
mayorovp
30.09.2024 19:48Вы так пишете, как будто в каком-нибудь С++ аналогичный код сделает меньше копирований памяти:
struct S { int i; } void foo(S s) { std::cout << &s << std::endl; } fn main() { S s = ...; std::cout << &s << std::endl; foo(std::move(s)); }
KanuTaH
30.09.2024 19:48Вы так пишете, как будто в каком-нибудь С++ аналогичный код сделает меньше копирований памяти
Нет, я как раз так не пишу. Спор с выдуманным утверждением оппонента - это типичный случай подмены тезиса :) И в C++ и в расте погромист должен думать над механизмом передачи параметров, если хочет производительности.
feelamee
30.09.2024 19:48а есть какие-нибудь советы как это подружить с расширением классов?
Я обычно полагаюсь на размер при передаче в функцию, но если в будущем класс будет расширен.. То уже не уверен стоит ли принимать даже 8 байтовый тип по значению
Abstraction
30.09.2024 19:48Написать в функции
static_assert(sizeof(DataCollection) <= 16, "redesign to reference if DataCollection grows");
, как простейшая соломка?
Cheater
30.09.2024 19:48Кто такой toVisit? В строке с push() похоже на вызов конструктора копирования вместо perfect forwarding.
Ещё предположу, что распухает visited (если это некое множество посещённых точек, в которое только кладут данные, но не удаляют) и постоянный поиск в нём ухудшает производительность. Я вижу, что на каждом шаге происходит попытка добавления в toVisit 4 точек вокруг данной, не знаю что с ними за кадром потом делается, надеюсь многие выкидываются, но если не делается ничего и просто для каждой точки в toVisit в свою очередь рекурсивно исследуются 4 точки вокруг и т.д., то в результате может получиться весьма дорогой алгоритм.
dalerank Автор
30.09.2024 19:48+3Спойлер
А темповая алокация/деалокация в вектор этих четырёх точек на каждой итерации вас не смутила?
mayorovp
30.09.2024 19:48Оно там исследуется конечно же, только не рекурсивно, а итеративно. Обратите внимание на внешний цикл.
simplepersonru
30.09.2024 19:48+4Такая сигнатура с передачей по значению позволяет мувать в функцию, но при этом остается вариант с копией. Например:
void setSomeSh(std::shared_ptr<Resource> ptr) {
m_some = std::move(ptr);
}
Вызывающий код может передать туда lvalue, или rvalue
std::shared_ptr<Resource> myPtr;
setSomeSh(myPtr)
setSomeSh(std::move(myPtr));
В случае конст ссылки всегда будет лишний инкремент шареда, даже если его можно было избежать, сигнатура со значением дает выбор.
Сори что без кодэблоков, пишу с телефона
mentin
30.09.2024 19:48А когда не надо мувать - то лучше передать view-тип, опять же по значению.
Получаем один из двух вариантов
foo(std::string arg) // если внутри m_arg_ = std::move(arg) foo(std::string_view arg) // eсли сохранять не надо
Вариант с
const std::string&
хуже последнего - чтобы передать простую С-строчку придется конструировать std::string. В общем, в современном С++ чаще всего аргументы по ссылкам передавать не надо.
LaRN
30.09.2024 19:48Тут не рассмотрен момент, когда нужно обеспечить иммутабельность переданных данных. Передача по ссылке имеет кучу побочки, которую трудно отследить. Это почти как глобальные переменные. В одном месте случайно поменял, а выстрелило в другом. У нас был кейс, когда в одной функции переданный по ссылке объект удалили, сделали ему free. А потом чуть ниже из-за этого все палало с AV за пределами этой функции.
8street
30.09.2024 19:48+1const ссылка не спасает?
LaRN
30.09.2024 19:48Спасает. Только об этом не сказано в статье. Там как-то однобоко. Минусы описаны, а плюсы нет.
AbuMohammed
30.09.2024 19:48+1У меня при ревью есть несколько звоночков, которые прямо в регекспы оформил.
Неконстантная ссылка. В 4 из 5 случаев это сопровождается косяками.
Указатель вместо ссылки. То же самое, плюс еще явные проблемы с дезайном.
A(A&&)=default; как ни странно но очень часто тащит сложно вылавливаемые проблемы.
Ну и вишенка на торте - auto вместо auto&. Помню в продакшене долго ловил чужой баг, связанный с этим).
dalerank Автор
30.09.2024 19:48Я не уверен насчет pvs, cppxheck точно не ловит такое, может @Andrey2008подскажет умеет ли pvs ловить такие потенциально ошибки
orefkov
30.09.2024 19:48+4Если вызываемый собирается завладеть переданным, то передача по значению позволяет передавать универсально - копией или перемещением. Понятно, что у себя вызываемый всегда будет мувать переданное. Ну и при многопоточке - локальное значение гарантированно только твое и не нуждается в синхронизации. И компилятор знает, что никто снаружи к этому объекту не имеет ссылок.
redfox0
30.09.2024 19:48писать что-то подобное const int &i лишено смысла
Линтер раста на подобное ругается:
warning: this argument (4 byte) is passed by reference, but would be more efficient if passed by value (limit: 8 byte) --> src/main.rs:4:16 | 4 | fn func(value: &i32) { | ^^^^ help: consider passing by value instead: `i32` | = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#trivially_copy_pass_by_ref note: the lint level is defined here --> src/main.rs:3:8 | 3 | #[warn(clippy::trivially_copy_pass_by_ref)] | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
vesper-bot
30.09.2024 19:48С интом понятное дело, но претензии в статье на string или более весомые типы данных. Плюс современный int короче современного void*
Vladime
30.09.2024 19:48+1Here are a few potential performance issues in the provided C++ code:
-
Reallocation of
directions
vector:
Thestd::vector directions
is being initialized inside the loop on each iteration. This causes memory allocation and deallocation, which can be avoided by moving the initialization outside the loop:const std::vector directions{ {1.f, 0.f}, {-1.f, 0.f}, {0.f, 1.f}, {0.f, -1.f} }; while (!toVisit.empty()) { ... }
Costly
visited.find(nextPos)
calls:
Checking fornextPos
invisited
every time within the loop can be expensive depending on the size ofvisited
. Ifvisited
is an unordered set, this is average O(1) but can degrade to O(n) in worst cases. If it is an ordered set, the lookup is O(log n). Consider if optimizing this lookup or howvisited
is structured can help improve performance (e.g., hashingVector2
more efficiently).Possible excessive dynamic memory allocation:
ThetoVisit.push({nextPos, Vector2::DistanceSq(center, nextPos)})
creates a temporary object fornextPos
and the calculated distance. Depending on the structure oftoVisit
, this might result in frequent memory allocations if it's dynamically growing.Vector2::DistanceSq
recalculations:
You’re calculating the squared distance betweencenter
andnextPos
in each iteration. If this calculation is redundant or repeated for the same points, you could store the result ofVector2::DistanceSq
in a cache if the computation is expensive.Inefficient
toVisit
container:
IftoVisit
is a priority queue (like in A* or Dijkstra algorithms), using an inefficient data structure for this can slow down the overall algorithm. A heap-based priority queue might be more efficient for pushing and popping elements in such a pathfinding context.
Addressing these points should help reduce unnecessary overhead and improve the overall performance of your pathfinding code.
-
Sazonov
Про копирование 32кб памяти которые до этого не были в кэше и которое быстрее суммы двух чисел можете поподробнее, с примерами? А то заучит как-то волшебно.
И почему вы в бенчмарках используете копирование вместо обращения по ссылке в range for?
dalerank Автор
могу рассказать конкретно про nintendo switch, через API SDK (это поддержка со стороны железа всегда) можно выделить область памяти которую следует скопировать, работало как для gpu так и для cpu. Происходит это в обход cpu и это не шареная память gpu-cpu, происходило именно копирование данных. Так например было сделано сохранение предыдущего фрейма для разных пост эффектов. Еще навскидку nontemporal memcopy в обход кеша, который конечно не сложение двух чисел, но тоже сильно быстрее обычного. Про бенчи, там стейт небольшой смысла его через реф делать нет, но если очень хочется то почему бы и не сделать.
unreal_undead2
И такое копирование работало при передаче обычного плюсового вектора по значению?
Deosis
Я могу предположить два способа сделать "копию" данных сильно быстрее честного копирования:
Отображение разных страниц виртуальной памяти на одну физическую (например, fork). Работает очень быстро пока не понадобится записать в скопированную или оригинальную память.
DMA, процессор отдает команду на копирование данных, которую периферия будет выполнять асинхронно.
Sazonov
И обе этих вещи не являются частью стандарта и соответственно, не кросс-платформенны.
PrinceKorwin
это же другими словами copy-on-write, не? Нормальный подход.