Хабрахабр

Особенности вызова функций в С++

В результате возникла данная статья. Не так давно у меня произошёл очередной разговор с коллегой на извечную тему: "по ссылке, или по значению". Далее будут рассмотрены: В ней я хочу изложить результаты моего исследования по этой и смежным темам.

  • Регистры и их назначение при вызове функций.
  • Передача и возврат простых типов и структур.
  • Как передача по ссылке и по значению влияют на оптимизации тела функции компилятором.
  • Как используется место при многочисленных вызовах функций.
  • Механизм виртуальных вызовов.
  • Оптимизация хвостовых вызовов и рекурсии.
  • Инициализация структур, массивов и векторов.

Статья содержит большое количество кода на C++ и ассемблере (с комментариями), а также множество таблиц с оценками производительности. Осторожно!

Ассемблерные листинги получены для clang 5. Информация бралась из документа System V Application Binary Interface for x86-64. 0 x86-64 с флагами -O3 -std=c++1z -march=sandybridge (с помощью сайта https://godbolt.org). 0. 20GHz. Оценки производительности были сделаны для процессора Intel® Xeon® CPU E5-2660 2.

Table of contents

Registers in x86-64

Для ускорения работы с ней используются многоуровневые кэши. Все данные хранятся в оперативной памяти. Ниже дано очень краткое описание наиболее используемых регистров в архитектуре x86-64. Но для изменения данных, так или иначе, используются регистры (обсуждение в комментариях).

  • 16 регистров общего назначения: rax, rbx, rcx, rdx, rbp, rsi, rdi, rsp а также r8-r15. Размер каждого из них равен 64 битам (8 байтам). Для доступа к младшим 32 битам (4 байтам) используется префикс e вместо r (raxeax). Поддерживают только не векторные целочисленные операции.
  • rip (instruction pointer) указывает на инструкцию, которая будет исполнена следующей. Различные константные данные, лежащие в разделе памяти с инструкциями, могут считываться по смещению относительно rip.
  • rsp (stack pointer) указывает на последний элемент в стеке. Стек растёт в сторону меньших адресов. Запихивание чего-то в стек уменьшает значение rsp.
  • 16 SSE регистров размером 128 бит: xmm0 - xmm15. Если поддерживается режим AVX, то они ссылаются на младшие 128 бит регистров ymm0 - ymm15 каждый из которых имеет размер 256 бит. Для векторных, или не целочисленных операций, данные необходимо предварительно загрузить в эти регистры.

Parameter passing

Полное описание можно увидеть на странице 17 "System V ABI". В этом параграфе приведено несколько сокращённое и упрощённое описание алгоритма распределения аргументов по регистрам/стеку.

Введём несколько классов объектов:

  • INTEGER – интегральные типы, помещающиеся в регистры общего пользования. Это bool, char, int и так далее.
  • SSE – числа с плавающей точкой, вмещающиеся в векторный регистр. Это float и double.
  • MEMORY – объекты, передаваемые через стек.

Для унификации описания, типы __int128 и complex представляются как структуры из двух полей:

struct __int128 { int64 low, high;
};
struct complexT { T real, imag;
}; // Где T - float, или double.

В начале каждый аргумент функции классифицируется:

  1. Если тип больше 128 бит, или имеет не выровненные поля, то он MEMORY.
  2. Если есть нетривиальные деструктор, конструктор копирования, виртуальные методы, виртуальные базовые классы, то он передаётся через "прозрачную ссылку". Объект заменяется указателем, который имеет тип INTEGER.
  3. Агрегаты, а это структуры и массивы, анализируются кусками по 8 байт.
    1. Если в куске есть поле типа MEMORY, то весь кусок MEMORY.
    2. Если есть поле типа INTEGER, то весь кусок INTEGER.
    3. Иначе весь кусок SSE .
  4. Если есть кусок типа MEMORY, то весь аргумент MEMORY.
  5. Типы long double и complex long double используют специальный набор x87 FPU регистров и имеют тип MEMORY.
  6. Типы __m256, __m128 и __float128 имеют тип SSE .

После классификации, все 8 байтные куски (в одном куске может быть несколько полей структуры, или элементов массива) распределяются по регистрам:

  1. MEMORY передаются через стек.
  2. INTEGER передаются через следующий свободный регистр rdi, rsi, rdx, rcx, r8, r9 в именно таком порядке.
  3. SSE передаются через следующий свободный регистр xmm0 - xmm7.

Те аргументы, которым не хватило регистров, передаются через стек. Аргументы рассматриваются слева направо. Если какому-либо куску аргумента не хватило регистра, то весь аргумент передаётся через стек.

Возвращение значений производится следующим образом:

  1. MEMORY типы возвращаются через стек. Место на нём предоставляется вызывающей функцией и адрес его начала передаётся через rdi как будто бы это первый аргумент функции. При возврате это адрес должен быть возвращён через rax. Первый оригинальный аргумент будет передан, соответственно, как второй, и так далее.
  2. INTEGER кусок возвращается через следующий свободный регистр rax, rdx.
  3. SSE кусок возвращается через следующий свободный регистр xmm0, xmm1. Эти регистры используются как для приёма, так и для возврата значений.

Сводная таблица с регистрами и их назначением, очень полезна при чтении ассемблера:

Регистр

Назначение

rax

Временный регистр, возврат первого (ret 1) INTEGER результата.

rbx

Принадлежит вызывающие функции, не должен быть изменён на момент возврата.

rcx

Передача четвёртого (4) INTEGER аргумента.

rdx

Передача третьего (3) INTEGER аргумента, возврат второго (ret 2) INTEGER результата.

rsp

Указатель на стек.

rbp

Принадлежит вызывающие функции, не должен быть изменён на момент возврата.

rsi

Передача второго (2) INTEGER аргумента.

rdi

Передача первого (1) INTEGER аргумента.

r8

Передача пятого (5) INTEGER аргумента.

r9

Передача шестого (6) INTEGER аргумента.

r10-r11

Временные регистры.

r12-r15

Принадлежит вызывающие функции, не должны быть изменены на момент возврата.

xmm0-xmm1

Передача и возврат первого и второго SSE аргументов.

xmm2-xmm7

Передача с третьего по шестой SSE аргументов.

xmm8-xmm15

Временные регистры.

Регистры, принадлежащее вызывающей функции, или не должны использоваться, или их значения должны быть куда-то сохранены, к примеру, на стек, а потом восстановлены.

Simple examples

Делаем вид, что тело функции расположено в cpp файле, а LTO отключено. Если явно не указано обратное, то все используемые функции были помечены как NOINLINE. Также все результаты функций передаются в пустую NOINLINE функцию, чтобы предотвратить удаление всего кода оптимизатором.

#define NOINLINE __attribute__((noinline))
#define INLINE static __attribute__((always_inline))

Рассмотрим что-нибудь простое.

double foo(int8_t a, int16_t b, int32_t c, int64_t d, float x, double y) { return a + b + c + d + x + y;
}
...
auto result = foo(1, 2, 3, 4, 5, 6);

Параметры передаются так:

Имя

Регистр

Имя

Регистр

Результат

a

rdi

d

rcx

xmm0

b

rsi

x

xmm0

c

rdx

y

xmm1

Рассмотрим сгенерированный кода подробнее.

foo(signed char, short, int, long, float, double): add edi, esi # Складываем a и b. add edi, edx # Прибавляем c. movsxd rax, edi # Копируем результат в rax, расширяя его до 64 бит с сохранением знака. add rax, rcx # Прибавляем d. vcvtsi2ss xmm2, xmm2, rax # Конвертируем результат в float и сохраняем его в xmm2. vaddss xmm0, xmm2, xmm0 # Прибавляем x, суффикс 's' инструкции vaddss обозначает работу с single precision. vcvtss2sd xmm0, xmm0, xmm0 # Конвертируем результат в double. vaddsd xmm0, xmm0, xmm1 # Прибавляем y, суффикс 'd' команды vaddsd обозначает работу с double precision. ret # Выходим из функции и переходим по адресу, сохранённому на вершине стека, стек при этом уменьшается, то есть rsp увеличивается на 8.
.LCPI1_0: # Секция с константными данными. .long 1084227584 # float 5
.LCPI1_1: .quad 4618441417868443648 # double 6
main: # @main sub rsp, 24 # Распределяем аргументы по соответствующим регистрам. vmovss xmm0, dword ptr [rip + .LCPI1_0] # xmm0 = mem[0],zero,zero,zero vmovsd xmm1, qword ptr [rip + .LCPI1_1] # xmm1 = mem[0],zero mov edi, 1 mov esi, 2 mov edx, 3 mov ecx, 4 call foo(signed char, short, int, long, float, double) # call сохраняет адрес возврата на вершину стека, тем самым уменьшая rsp на 8, и переходит к месту начала функции. vmovsd qword ptr [rsp + 16], xmm0 # Копируем результат обратно на стек.

Если в функцию передавать параметры простых типов, то нужно сильно постараться, чтобы они были переданы не через регистры.

Массивы можно рассматривать как структуры с несколькими полями. Рассмотрим различные примеры агрегатов.

struct St { double a, b;
};
double foo(St s)
...
St s{1, 2};
auto result = foo(s);

Имя

Регистр

Имя

Регистр

Результат

s.a

xmm0

s.b

xmm1

xmm0

Но увы, алгоритм распределения оперирует только восьмибайтными кусками. Казалось бы, ничто не мешает запихнуть сразу два double в один xmm регистр.

foo(St): # @foo(St) vaddsd xmm0, xmm0, xmm1 # Прибавляем второй аргумент к первому, который уже находится в регистре с результатом. ret
.LCPI1_0: .quad 4607182418800017408 # double 1
.LCPI1_1: .quad 4611686018427387904 # double 2
main: # @main sub rsp, 24 # Заполняем входные регистры. vmovsd xmm0, qword ptr [rip + .LCPI1_0] # xmm0 = mem[0],zero vmovsd xmm1, qword ptr [rip + .LCPI1_1] # xmm1 = mem[0],zero call foo(St) vmovsd qword ptr [rsp + 16], xmm0 # Копируем double из регистра с результатом.

Если добавить ещё одно double поле, то вся структура будет передана через стек, так как её размер превысит 128 байт.

struct St { double a, b, c;
};
double foo(St s) { return s.a + s.b + s.c; }
...
St s{1, 2, 3};
auto result = foo(s);

foo(St): # @foo(St) # При вызове функции, стек увеличивается на 8 байт, в которых хранится адрес возврата. Так как стек растёт в сторону уменьшения адреса, то первый аргумент будет расположен со по адресу rsp+8. vmovsd xmm0, qword ptr [rsp + 8] # xmm0 = mem[0],zero vaddsd xmm0, xmm0, qword ptr [rsp + 16] vaddsd xmm0, xmm0, qword ptr [rsp + 24] ret
.L_ZZ4mainE1s: .quad 4607182418800017408 # double 1 .quad 4611686018427387904 # double 2 .quad 4613937818241073152 # double 3
main: # @main sub rsp, 40 # Выделяем на стеке 40 байт. # Константы хранятся в разделе памяти с кодом, перекидываем их на стек. Это приходится делать через промежуточный регистр, так как mov не может копировать из памяти в память. mov rax, qword ptr [rip + .L_ZZ4mainE1s+16] # Загружаем в регистр '3'. mov qword ptr [rsp + 16], rax # Копируем '3' на стек. vmovups xmm0, xmmword ptr [rip + .L_ZZ4mainE1s] # Загружаем в xmm0 сразу '1' и '2'. vmovups xmmword ptr [rsp], xmm0 # Копируем '1' и '2 на стек. Сейчас стек выглядит так: 1 = *rsp , 2 = *(rsp+8), 3 = *(rsp+16). call foo(St) vmovsd qword ptr [rsp + 32], xmm0 # Копируем на стек один double с результатом.

Посмотрим, что будет, если заменить double на uint64_t.

struct St { uint64_t a, b;
};
uint64_t foo(St s) { return s.a + s.b; }
...
St s{1, 2};
auto result = foo(s);

Имя

Регистр

Имя

Регистр

Результат

s.a

rdi

s.b

rsi

rax

foo(St): # @foo(St) lea rax, [rdi + rsi] ret
main: # @main sub rsp, 24 mov edi, 1 mov esi, 2 call foo(St) mov qword ptr [rsp + 16], rax

Подробнее про то, почему используется инструкция lea а не add, можно почитать, к примеру, тут: https://stackoverflow.com/a/6328441/1418863 Результат заметно компактнее.

Код, кстати, будет почти идентичен, даже загрузка на стек будет производиться через xmm регистры. Если добавить ещё одно поле, то, как и в примере с double, структура будет передана через стек.

Рассмотрим что-нибудь более интересное.

struct St { float a, b, c, d;
};
St foo(St s1, St s2) { return {s1.a + s2.a, s1.b + s2.b, s1.c + s2.c, s1.d + s2.d};
}
...
St s1{1, 2, 3, 4}, s2{5, 6, 7, 8}; auto result = foo(s1, s2);

Имя

Регистр

Имя

Регистр

Результат

s1.a

xmm0

s1.b

xmm0

xmm0, xmm1

s1.c

xmm1

s1.d

xmm1

s2.a

xmm2

s2.b

xmm2

s2.c

xmm3

s2.d

xmm3

В каждый xmm регистр запихиваются по два float поля.

foo(St, St): # @foo(St, St) # Одной инструкцией vaddps складываем сразу два float значения. vaddps xmm0, xmm0, xmm2 vaddps xmm1, xmm1, xmm3 ret
.LCPI1_0: .long 1065353216 # float 1 .long 1073741824 # float 2 .zero 4 .zero 4 # Аналогично определены LCPI1_1 - LCPI1_3.
...
main: # @main sub rsp, 24 # Заполняем регистры, копируя константные данные из области кода. vmovapd xmm0, xmmword ptr [rip + .LCPI1_0] # xmm0 = <1,2,u,u> vmovapd xmm1, xmmword ptr [rip + .LCPI1_1] # xmm1 = <3,4,u,u> vmovaps xmm2, xmmword ptr [rip + .LCPI1_2] # xmm2 = <5,6,u,u> vmovaps xmm3, xmmword ptr [rip + .LCPI1_3] # xmm3 = <7,8,u,u> call foo(St, St) # Так как тут нужно загрузить результат в стек, то предварительно два регистра с результатом смешиваются в один. xmm имеет размер 256 байт, поэтому в младшие 128 байт копируются поля a и b, в старшие - c и d. vunpcklpd xmm0, xmm0, xmm1 # xmm0 = xmm0[0],xmm1[0] vmovupd xmmword ptr [rsp + 8], xmm0

Если бы в структуре было не 4, а три поля, то код функции был бы аналогичен, за исключением замены второй инструкции vaddps на vaddss, которая складывает только первые 64 бита регистра.

struct St { int32_t a, b, c, d;
};
St foo(St s1, St s2) { return {s1.a + s2.a, s1.b + s2.b, s1.c + s2.c, s1.d + s2.d};
}
...
St s1{1, 2, 3, 4}, s2{5, 6, 7, 8}; auto result = foo(s1, s2);

Имя

Регистр

Имя

Регистр

Результат

s1.a

rdi

s1.b

rdi

rax, rdx

s1.c

rsi

s1.d

rsi

s2.a

rdx

s2.b

rdx

s2.c

rcx

s2.d

rcx

foo(St, St): # @foo(St, St) lea eax, [rdx + rdi] movabs r8, -4294967296 # 0xFFFFFFFF00000000 Битовая маска. and rdi, r8 add rdi, rdx and rdi, r8 or rax, rdi lea edx, [rcx + rsi] # То же, что и add. and rsi, r8 add rsi, rcx and rsi, r8 or rdx, rsi ret
main: # @main sub rsp, 24 movabs rdi, 8589934593 # Загружаем в регистры сразу по два числа. movabs rsi, 17179869187 movabs rdx, 25769803781 movabs rcx, 34359738375 call foo(St, St) mov qword ptr [rsp + 8], rax # Копируем результат на стек. mov qword ptr [rsp + 16], rdx

Каждая пара 32 битных чисел запаковывается в один 64 битный регистр. Внутри функции происходит битовая магия, но принцип примерно ясен. Возврат производится таким же образом.

Посмотрим, что будет, если начать смешивать типы полей, но так, чтобы в пределах 8 байтовых кусков они были одинакового класса.

struct St { int32_t a, b; float c, d;
};
St foo(St s1, St s2) { return {s1.a + s2.a, s1.b + s2.b, s1.c + s2.c, s1.d + s2.d};
}
...
St s1{1, 2, 3, 4}, s2{5, 6, 7, 8};
auto result = foo(s1, s2);

Имя

Регистр

Имя

Регистр

Результат

s1.a

rdi

s1.b

rdi

rax, xmm0

s1.c

xmm0

s1.d

xmm0

s2.a

rsi

s2.b

rsi

s2.c

xmm1

s2.d

xmm1

foo(St, St): # @foo(St, St) lea eax, [rsi + rdi] # Эта часть аналогична предыдущему примеру. movabs rcx, -4294967296 and rdi, rcx add rdi, rsi and rdi, rcx or rax, rdi vaddps xmm0, xmm0, xmm1 # Складываем сразу два поля. ret
.LCPI1_0: .long 1077936128 # float 3 .long 1082130432 # float 4 .zero 4 .zero 4
...
main: # @main sub rsp, 24 vmovaps xmm0, xmmword ptr [rip + .LCPI1_0] # xmm0 = <3,4,u,u> vmovaps xmm1, xmmword ptr [rip + .LCPI1_1] # xmm1 = <7,8,u,u> movabs rdi, 8589934593 movabs rsi, 25769803781 call foo(St, St) mov qword ptr [rsp + 8], rax # Копируем результат на стек. vmovlps qword ptr [rsp + 16], xmm0

Перемешаем поля. Но это не интересно, так как типы полей в каждом 8 байтном куске совпадают.

struct St { int32_t a; float b; int32_t c; float d;
};
St foo(St s1, St s2) { return {s1.a + s2.a, s1.b + s2.b, s1.c + s2.c, s1.d + s2.d};
}
...
St s1{1, 2, 3, 4}, s2{5, 6, 7, 8};
auto result = foo(s1, s2);

Имя

Регистр

Имя

Регистр

Результат

s1.a

rdi

s1.b

rdi

rax, rdx

s1.c

rsi

s1.d

rsi

s2.a

rdx

s2.b

rdx

s2.c

rcx

s2.d

rcx

2. Смотрим пункт 3. Так как в 8 байтном куске есть и float, и int, то весь кусок будет иметь тип INTEGER и будет передан в регистрах общего назначения.

foo(St, St): # @foo(St, St) mov rax, rdx add edx, edi shr rdi, 32 vmovd xmm0, edi mov rdi, rcx add ecx, esi shr rsi, 32 vmovd xmm1, esi shr rax, 32 vmovd xmm2, eax vaddss xmm0, xmm0, xmm2 shr rdi, 32 vmovd xmm2, edi vaddss xmm1, xmm1, xmm2 vmovd eax, xmm0 shl rax, 32 or rdx, rax vmovd eax, xmm1 shl rax, 32 or rcx, rax mov rax, rdx mov rdx, rcx ret
main: # @main sub rsp, 24 movabs rdi, 4611686018427387905 # 0x4000000000000001, в младших 32 битах хранится int, в старших - float. movabs rsi, 4647714815446351875 movabs rdx, 4665729213955833861 movabs rcx, 4683743612465315847 call foo(St, St) mov qword ptr [rsp + 8], rax # Возвращается результат тоже исключительно через 64 битные регистры. mov qword ptr [rsp + 16], rdx

А также отсутствие каких-либо векторных операций. Тут можно видеть 6 операций сдвига для извлечения float полей и их запихивания в регистр с результатом. В общем, лучше не мешать типы полей в пределах 8 байтовых кусков структуры.

References

Если объект не помещается в регистрах, то он передаётся и возвращается через стек. Передача параметров по константной ссылке аналогично передаче указателя на объект. Для реалистичности рассмотрим структуру для трёхмерной точки. Посмотрим, как это происходит.

struct Point3f { float x, y, z;
};
struct Point3d { double x, y, z;
};
Point3f scale(Point3f p) { return {p.x * 2, p.y * 2, p.z * 2}; }
Point3f scaleR(const Point3f& p) { return {p.x * 2, p.y * 2, p.z * 2}; }
Point3d scale(Point3d p) { return {p.x * 2, p.y * 2, p.z * 2}; }
Point3d scaleR(const Point3d& p) { return {p.x * 2, p.y * 2, p.z * 2}; }

Использоваться будут преимущественно новые xmm регистры, поэтому логика вполне понятна. Сравним код функций.

scale(Point3f): # @scale(Point3f) # Как и в прошлых примерах, x, y передаются в xmm0, z - xmm1, возвращается результат в них же. vaddps xmm0, xmm0, xmm0 vaddss xmm1, xmm1, xmm1 ret
scaleR(Point3f const&): # @scaleR(Point3f const&) # Указатель на аргумент находится в регистре rdi, служащего для передачи первого аргумента. Возврат так же через регистры xmm0, xmm1. vmovsd xmm0, qword ptr [rdi] # xmm0 = mem[0],zero vaddps xmm0, xmm0, xmm0 vmovss xmm1, dword ptr [rdi + 8] # xmm1 = mem[0],zero,zero,zero vaddss xmm1, xmm1, xmm1 ret
scale(Point3d): # @scale(Point3d) # В регистре rid передаётся адрес, по которому нужно записывать результат. Сам аргумент передаётся через стек и расположен по адресам [rsp+8, rsp+32). В [rsp, rsp+8) находится адрес возврата из функции. vmovapd xmm0, xmmword ptr [rsp + 8] vaddpd xmm0, xmm0, xmm0 vmovupd xmmword ptr [rdi], xmm0 vmovsd xmm0, qword ptr [rsp + 24] # xmm0 = mem[0],zero vaddsd xmm0, xmm0, xmm0 vmovsd qword ptr [rdi + 16], xmm0 mov rax, rdi # Возвращаем адрес, по которому записан результат. ret
scaleR(Point3d const&): # @scaleR(Point3d const&) # Код абсолютно идентичен, но аргумент начинается не в [rsp+8, rsp+32), а в [rsi, rsi+24). vmovupd xmm0, xmmword ptr [rsi] vaddpd xmm0, xmm0, xmm0 vmovupd xmmword ptr [rdi], xmm0 vmovsd xmm0, qword ptr [rsi + 16] # xmm0 = mem[0],zero vaddsd xmm0, xmm0, xmm0 vmovsd qword ptr [rdi + 16], xmm0 mov rax, rdi ret

Теперь посмотрим на место вызова этих функций.

# scale(Point3f)
main: # @main sub rsp, 24 # Копируем константы во входные регистры. vmovaps xmm0, xmmword ptr [rip + .LCPI4_0] # xmm0 = <1,2,u,u> vmovss xmm1, dword ptr [rip + .LCPI4_1] # xmm1 = <3,u,u,u> call scale(Point3f) # scaleR(const Point3f&)
main: # @main sub rsp, 24 # Просто записываем адрес участка с константами в регистр rdi, в котором передаётся первый аргумент. mov edi, .L_ZZ4mainE1p # <1,2,3,u> call scaleR(Point3f const&) # scale(Point3d)
main: # @main sub rsp, 64 # Копируем константы из раздела с данным на стек. mov rax, qword ptr [rip + .L_ZZ4mainE1p+16] mov qword ptr [rsp + 16], rax vmovups xmm0, xmmword ptr [rip + .L_ZZ4mainE1p] vmovups xmmword ptr [rsp], xmm0 lea rbx, [rsp + 40] mov rdi, rbx # Результат будет записан в [rsp+40, rsp+64). call scale(Point3d)
.L_ZZ4mainE1p: .quad 4607182418800017408 # double 1 .quad 4611686018427387904 # double 2 .quad 4613937818241073152 # double 3 # scaleR(const Point3d&)
main: # @main sub rsp, 64 # То же самое. mov rax, qword ptr [rip + .L_ZZ4mainE1p+16] mov qword ptr [rsp + 32], rax vmovups xmm0, xmmword ptr [rip + .L_ZZ4mainE1p] vmovaps xmmword ptr [rsp + 16], xmm0 lea rbx, [rsp + 40] lea rsi, [rsp + 16] # Аргумент будет по адресу [rsp+16, rsp+40). mov rdi, rbx # Результат будет записан в [rsp+40, rsp+64). call scaleR(Point3d const&)

Тут начинается самое интересное. Посмотрим, что если у нас много полей, но структура всё-таки влезает в регистры.

struct St { char d[16];
}; St foo(St s1, St s2) { // Просто суммируем s1 и s2. St res; for(int i{}; i < 16; ++i) res.d[i] = s1.d[i] + s2.d[i]; return res;
}

Код для функции, принимающей аргументы по значению.

Имя

Регистр

Имя

Регистр

Результат

s1.d[1:8]

rdi

s1.d[8:16]

rsi

rax, rdx

s2.d[1:8]

rdx

s2.d[8:16]

rcx

foo(St, St): # @foo(St, St) mov qword ptr [rsp - 16], rdi mov qword ptr [rsp - 8], rsi mov qword ptr [rsp - 32], rdx mov qword ptr [rsp - 24], rcx mov eax, edx add al, dil mov byte ptr [rsp - 48], al mov r8, rdi shr r8, 8 mov rax, rdx shr rax, 8 add al, r8b mov byte ptr [rsp - 47], al mov r8, rdi shr r8, 16 mov rax, rdx shr rax, 16 add al, r8b mov byte ptr [rsp - 46], al mov r8, rdi shr r8, 24 mov rax, rdx shr rax, 24 add al, r8b mov byte ptr [rsp - 45], al mov r8, rdi shr r8, 32 mov rax, rdx shr rax, 32 add al, r8b mov byte ptr [rsp - 44], al mov r8, rdi shr r8, 40 mov rax, rdx shr rax, 40 add al, r8b mov byte ptr [rsp - 43], al mov r8, rdi shr r8, 48 mov rax, rdx shr rax, 48 add al, r8b mov byte ptr [rsp - 42], al shr rdi, 56 shr rdx, 56 add dl, dil mov byte ptr [rsp - 41], dl mov eax, ecx add al, sil mov byte ptr [rsp - 40], al mov rax, rsi shr rax, 8 mov rdx, rcx shr rdx, 8 add dl, al mov byte ptr [rsp - 39], dl shr rsi, 16 shr rcx, 16 add cl, sil mov byte ptr [rsp - 38], cl mov al, byte ptr [rsp - 21] mov cl, byte ptr [rsp - 20] add al, byte ptr [rsp - 5] mov byte ptr [rsp - 37], al add cl, byte ptr [rsp - 4] mov byte ptr [rsp - 36], cl mov al, byte ptr [rsp - 19] mov cl, byte ptr [rsp - 18] add al, byte ptr [rsp - 3] mov byte ptr [rsp - 35], al add cl, byte ptr [rsp - 2] mov byte ptr [rsp - 34], cl mov al, byte ptr [rsp - 17] add al, byte ptr [rsp - 1] mov byte ptr [rsp - 33], al mov rax, qword ptr [rsp - 48] mov rdx, qword ptr [rsp - 40] ret

Как можно посчитать, в функции ровно 16 инструкций add. Да, тут все аргументы копируются на стек, после чего из него извлекается и складывается по одному байту за раз. Передадим структуру по ссылке. Может ли компилятор что-то с этим поделать?

St fooR(const St& s1, const St& s2) { /* Без изменений. */ }

Имя

Регистр

Имя

Регистр

Результат

s1

rdi

s2

rsi

rax, rdx

fooR(St const&, St const&): # @fooR(St const&, St const&) vmovdqu xmm0, xmmword ptr [rsi] vpaddb xmm0, xmm0, xmmword ptr [rdi] vmovdqa xmmword ptr [rsp - 24], xmm0 mov rax, qword ptr [rsp - 24] mov rdx, qword ptr [rsp - 16] ret

Это выглядит гораздо лучше. О да! После этого результат копируется в выходные регистры через стек. Мы можем загрузить сразу 16 однобайтовых элементов в xmm регистр и вызывать vpaddb которая их все сложит за одну операцию. Можно подумать, что от этой последней операции можно избавиться, заменив первый аргумент на не константную ссылку.

void fooR1(St &s1, const St& s2) { for(int i{}; i < 16; ++i) s1.d[i] += s2.d[i];
}

Имя

Регистр

Имя

Регистр

Результат

s1

rdi

s2

rsi

fooR1(St&, St const&): # @fooR1(St&, St const&) mov al, byte ptr [rsi] add byte ptr [rdi], al mov al, byte ptr [rsi + 1] add byte ptr [rdi + 1], al mov al, byte ptr [rsi + 2] add byte ptr [rdi + 2], al mov al, byte ptr [rsi + 3] add byte ptr [rdi + 3], al mov al, byte ptr [rsi + 4] add byte ptr [rdi + 4], al mov al, byte ptr [rsi + 5] add byte ptr [rdi + 5], al mov al, byte ptr [rsi + 6] add byte ptr [rdi + 6], al mov al, byte ptr [rsi + 7] add byte ptr [rdi + 7], al mov al, byte ptr [rsi + 8] add byte ptr [rdi + 8], al mov al, byte ptr [rsi + 9] add byte ptr [rdi + 9], al mov al, byte ptr [rsi + 10] add byte ptr [rdi + 10], al mov al, byte ptr [rsi + 11] add byte ptr [rdi + 11], al mov al, byte ptr [rsi + 12] add byte ptr [rdi + 12], al mov al, byte ptr [rsi + 13] add byte ptr [rdi + 13], al mov al, byte ptr [rsi + 14] add byte ptr [rdi + 14], al mov al, byte ptr [rsi + 15] add byte ptr [rdi + 15], al ret

Это получилось из-за того, что, по умолчанию, компилятор очень осторожен, и предполагает, что программист может быть не в духе и напишет что-то вроде такого: Кажется, что-то пошло не так.

char buff[17];
fooR1(*reinterpret_cast<St*>(buff+1), reinterpret_cast<const St*>(buff));

Для того, чтобы указать компилятору, что такого странного использования функции не предвидится, существует ключевое слово __restrict. В этом случае, на каждой итерации вычисляется buff[i+1] += buff[i], то есть имеется pointer aliasing.

void fooR2(St & __restrict s1, const St& s2) { /* Без изменений. */ }

Что и даёт желаемый результат.

fooR2(St&, St const&): # @fooR2(St&, St const&) vmovdqu xmm0, xmmword ptr [rdi] vpaddb xmm0, xmm0, xmmword ptr [rsi] vmovdqu xmmword ptr [rdi], xmm0 ret

Изменении сигнатуры на void fooR3(St &__restrict s1, St s2), тоже приведёт к раздутому код, похожему на первый пример с St foo(St, St).

Кстати, если размер массива заранее не известен, то void foo(char* __restrict s1, const char* s2, int size) генерирует примерно в полтора раза меньше строк кода, чем версия без __restrict.

Benchmark

Будем четыре раза прибавлять b к a, к примеру, для foo это будет выглядеть так:

St a, b; st(a, b); // st(St& a, St& b) { a = b = {}; } в другом файле.
a = foo(a, b);
a = foo(a, b);
a = foo(a, b);
a = foo(a, b);

Code

Cycles per iteration

St a, b; st(a, b);

7.6

4 x foo no reuse

121.9

4 x foo

117.7

4 x fooR no reuse

66.3

4 x fooR

64.6

4 x fooR1

84.5

4 x fooR2

20.6

4 x foo inline

51.9

4 x fooR inline

30.5

4 x fooR1 inline

8.8

4 x fooR2 inline

8.8

auto a2 = foo(a, b); auto a3 = foo(a2, b);. 'no reuse' указывает на то, что для хранения каждого результата используется новая переменная. 'inline' означает, что функции помечены как INLINE, а не NOINLINE.

Видимо, встраивание происходит после распределения всех полей по регистрам, после чего компилятор запутывается в происходящем и уже не может нормально упростить результат. Если посмотреть на листинг fooR1 inline / fooR2 inline, то в нём будет всего пара инструкций, но в случае, когда структура передаётся, или возвращается через регистры, foo inline / fooR inline, компилятор сходит с ума и выдаёт сотни строк кода.

Transparent pointers

Посмотрим, что будет, если добавить немного деструктора.

struct Point3f { float x, y, z; ~Point3f() {}
};
Point3f scale(Point3f p) { return {p.x * 2, p.y * 2, p.z * 2}; }

Вторым, в rsi, передаётся указатель на первый аргумент функции. Первым параметром в rdi передаётся адрес, по которому нужно записывать результат.

scale(Point3f): # @scale(Point3f) vmovss xmm0, dword ptr [rsi] # xmm0 = mem[0],zero,zero,zero vaddss xmm0, xmm0, xmm0 vmovss dword ptr [rdi], xmm0 vmovss xmm0, dword ptr [rsi + 4] # xmm0 = mem[0],zero,zero,zero vaddss xmm0, xmm0, xmm0 vmovss dword ptr [rdi + 4], xmm0 vmovss xmm0, dword ptr [rsi + 8] # xmm0 = mem[0],zero,zero,zero vaddss xmm0, xmm0, xmm0 vmovss dword ptr [rdi + 8], xmm0 mov rax, rdi ret

Компилятор не очень хочет оптимизировать не POD типы. Как видно, загрузка, умножение (через сложение) и сохранение производится по одному полю за раз. Посмотрим на место вызова. Версия функции с константной ссылкой Point3f scaleR(const Point3f&) даст идентичный код.

Point3f p{1, 2, 3};
auto result = scale(p);
sink(&result);

main: # @main push rbx sub rsp, 48 movabs rax, 4611686019492741120 # Копируем константы на стек. mov qword ptr [rsp + 16], rax mov dword ptr [rsp + 24], 1077936128 lea rbx, [rsp + 32] lea rsi, [rsp + 16] # Аргумент будет в [rsp+16, rsp+28) mov rdi, rbx # Результат будет в [rsp+32, rsp+44) call scale(Point3f) mov qword ptr [rsp + 8], rbx # В [rsp+8, rsp+16) будет указатель на результат. lea rdi, [rsp + 8] call void sink<Point3f*>(Point3f* const&) xor eax, eax add rsp, 48 pop rbx ret # Обработка исключений. mov rdi, rax call _Unwind_Resume

Если сделать деструктор NOINLINE, то всё будет гораздо запутаннее.

main: # @main push r14 push rbx sub rsp, 56 movabs rax, 4611686019492741120 # Константы будут в [rsp, rsp+12). Это переменная p. mov qword ptr [rsp], rax mov dword ptr [rsp + 8], 1077936128 # Копируем константы в [rsp+24, rsp+36), это временная переменная pTmp. mov eax, dword ptr [rsp + 8] mov dword ptr [rsp + 32], eax mov rax, qword ptr [rsp] mov qword ptr [rsp + 24], rax lea r14, [rsp + 40] lea rbx, [rsp + 24] mov rdi, r14 # Результат сохраняем в [rsp+40, rsp+52), это result. mov rsi, rbx # Первый аргумент - указатель на pTmp. call scale(Point3f) mov rdi, rbx # Вызываем деструктор у pTmp. Первый аргумент деструктора - указатель this. call Point3f::~Point3f() mov qword ptr [rsp + 16], r14 # В [rsp+16, rsp+24) будет храниться указатель на result. Он же первый аргумент sink. lea rdi, [rsp + 16] call void sink<Point3f*>(Point3f* const&) lea rdi, [rsp + 40] # Вызывает деструктор у result. call Point3f::~Point3f() mov rdi, rsp # Вызывает деструктор у p. call Point3f::~Point3f() xor eax, eax add rsp, 56 pop rbx pop r14 ret # Обработка исключений. Сюда может быть произведён переход в случае возникновения и перехвата исключения. mov rbx, rax lea rdi, [rsp + 40] # Вызывает деструктор у result. call Point3f::~Point3f() mov rdi, rsp # Вызывает деструктор у p. call Point3f::~Point3f() mov rdi, rbx call _Unwind_Resume

Если параметр p явно передавать по ссылке, то кода станет несколько меньше и будет произведено только два вызова деструктора.

Stack reuse

Будут использоваться функции из параграфа references. Посмотрим, как компилятор переиспользует регистры и стек между вызовами.

# Point3f result = scale(scale(Point3f{1, 2, 3})); sub rsp, 24 vmovaps xmm0, xmmword ptr [rip + .LCPI4_0] # xmm0 = <1,2,u,u> vmovss xmm1, dword ptr [rip + .LCPI4_1] # xmm1 = mem[0],zero,zero,zero # Так как регистры xmm0, xmm1 используются как для передачи, так и для возврата, то просто вызываем несколько раз нужную функцию! call scale(Point3f) call scale(Point3f) vmovlps qword ptr [rsp + 8], xmm0 vmovss dword ptr [rsp + 16], xmm1 # Point3f result = scaleR(scaleR(Point3f{1, 2, 3})); sub rsp, 56 # Копируем константы на стек в диапазоне [rsp+24, rsp+36). movabs rax, 4611686019492741120 # 0x400000003F800000 = [2.0f, 1.0f] mov qword ptr [rsp + 24], rax mov dword ptr [rsp + 32], 1077936128 # 0x40400000 = 3.0f lea rdi, [rsp + 24] # Аргумент с указателем на входные данные. call scaleR(Point3f const&) # Сохраняем результат в [rsp+8, rsp+20). vmovlps qword ptr [rsp + 8], xmm0 vmovss dword ptr [rsp + 16], xmm1 lea rdi, [rsp + 8] # Аргумент с указателем на результат первого вызова. call scaleR(Point3f const&) vmovlps qword ptr [rsp + 40], xmm0 vmovss dword ptr [rsp + 48], xmm1

Если аргумент не помещается в регистры, то всё точно наоборот. Видно, что в случае с передачей через регистры, кода значительно меньше.

# Point3d result = scale(scale(Point3d{1, 2, 3})); sub rsp, 112 # Загружаем константы в [rsp, rsp+24). vmovaps xmm0, xmmword ptr [rip + .LCPI4_0] # xmm0 = [1.000000e+00,2.000000e+00] vmovaps xmmword ptr [rsp + 32], xmm0 movabs rax, 4613937818241073152 # 0x4008000000000000 = 3.0 mov qword ptr [rsp + 48], rax mov rax, qword ptr [rsp + 48] mov qword ptr [rsp + 16], rax vmovaps xmm0, xmmword ptr [rsp + 32] vmovups xmmword ptr [rsp], xmm0 # Результат будет в [rsp+64, rsp+88). lea rdi, [rsp + 64] # В rdi передаём адрес стека для результата. call scale(Point3d) # Аргумент второй функции будет также по адресу [rsp, rsp+24). mov rax, qword ptr [rsp + 80] # Копируем z результата в z аргумента. mov qword ptr [rsp + 16], rax vmovups xmm0, xmmword ptr [rsp + 64] # Копируем [x, y] результата в [x, y] аргумента. vmovups xmmword ptr [rsp], xmm0 # Результат будет в [rsp+88, rsp+112). lea rbx, [rsp + 88] mov rdi, rbx call scale(Point3d) # Point3d result = scaleR(scaleR(Point3d{1, 2, 3})); sub rsp, 72 # Загружаем константы в [rsp, rsp+24), аналогично предыдущему коду. vmovaps xmm0, xmmword ptr [rip + .LCPI4_0] vmovaps xmmword ptr [rsp], xmm0 movabs rax, 4613937818241073152 mov qword ptr [rsp + 16], rax lea r14, [rsp + 24] mov rsi, rsp # Второй аргумент - указатель на стек с входными данными [rsp, rsp+24). mov rdi, r14 # Первый аргумент - указатель на стек для результата [rsp+24, rsp+48). call scaleR(Point3d const&) lea rbx, [rsp + 48] mov rdi, rbx # Указатель на стек для результата [rsp+48, rsp+72). mov rsi, r14 # Указатель на стек с входными данными [rsp+24, rsp+48). call scaleR(Point3d const&)

Если же они не помещаются – то лучше передавать по ссылке. Видно, что при передаче аргументов, помещающихся в регистры, код значительно короче, если передавать по значению. Причём он не может сделать так же, если параметр передаётся по значению через стек, и ему приходится выполнять лишние копирования. В этом случае компилятор может удалить лишние копирования и передавать сразу указатель на стек с результатом предыдущего вызова.

Benchmark

Функции для получения точек были объявлены в отдельном файле, чтобы предотвратить оптимизации для константных данных. Посмотрим, какое влияние всё это оказывает на быстродействие. Напомню, что при возврате из функции и передаче по значению, Point3f будет передаваться через регистры, а Point3d – через стек.

// В файле data.cpp. Предотвращаем встраивание.
Point3f pf() { return {1, 2, 3}; }
Point3d pd() { return {1, 2, 3}; }

Code

Cycles per iteration

auto r = pf();

6.7

auto r = scale(pf());

11.1

auto r = scaleR(pf());

12.6

auto r = scale(scale(pf()));

18.2

auto r = scaleR(scaleR(pf()));

18.3

auto r = scale(scale(scale(pf())));

16.8

auto r = scaleR(scaleR(scaleR(pf())));

20.2

auto r = pd();

7.3

auto r = scale(pd());

11.7

auto r = scaleR(pd());

11.0

auto r = scale(scale(pd()));

16.9

auto r = scaleR(scaleR(pd()));

14.1

auto r = scale(scale(scale(pd())));

21.2

auto r = scaleR(scaleR(scaleR(pd())));

17.2

Если функции пометить INLINE

8.1 — 8.9

Видимо, значительное время уходит на распаковку параметров из регистров, вспомним, что в один 64 битный регистры обычно запаковывается сразу два int, а векторные операции они не поддерживают. Если заменить Point3f на struct Point3i { int32_t x, y, z; }; и Point3d на struct Point3ll { int64_t x, y, z; };, то различия в производительности будет менее выраженными. С другой стороны, если заменить Point3f на struct Point2ll { int64_t x, y; }; и Point3d на struct Point4ll { int64_t x, y, z, a; };, то цифры будут примерно такие-же.

Что можно заметить:

  • Небольшие параметры лучше передавать по значению. Передача по ссылке только вредит.
  • Параметры, не влезающие в регистры, лучше передавать по ссылке.
  • Если есть возможность сделать функцию inline и поместить её в заголовочный файл, то это стоит сделать. При этом способ передачи параметров, по ссылке, или значению, не играет особой роли. По крайней мере для небольших простых типов.

About optional

Стандартный тип std::optional в данный момент имеет кривую реализацию (смотри http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0602r2.html), которая исправлена только в "x86-64 clang (experimental concepts)" и, вроде бы, MSVC последних версий, поэтому

struct Point { float x, y;
};
using OptPoint1 = optional<Point>;

будет совсем не эквивалентно

struct OptPoint2 { float x, y; union { char _; bool d; }; // Как в std::optional.
};

Несмотря на одинаковые размер и выравнивание, OptPoint1 будет передаваться через стек, а OptPoint2 – через регистры.

OptPoint1 foo(OptPoint1 s) { return Point{s->x + 1, s->y + 1}; }
OptPoint2 foo(OptPoint2 s) { return {s.x + 1, s.y + 1, true}; }
...
OptPoint1 s1{Point{1, 2}};
OptPoint2 s2{3, 4, true};
auto result1 = foo(s1);
auto result2 = foo(s2);

.LCPI0_0: .long 1065353216 # float 1
foo(std::optional<Point>): # @foo(std::optional<Point>) vmovss xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero # В rsi хранится адрес начала участка стека с аргументом. vaddss xmm1, xmm0, dword ptr [rsi] # Загружаем x со стека, прибавляя 1. vaddss xmm0, xmm0, dword ptr [rsi + 4] # Загружаем y со стека, прибавляя 1. vmovss dword ptr [rdi], xmm1 # Загружаем x на стек, rdi хранит адрес начала участка на стеке, в который нужно записывать результат. vmovss dword ptr [rdi + 4], xmm0 # Загружаем y на стек. mov byte ptr [rdi + 8], 1 # Флаг optional::has_value(). mov rax, rdi # Возвращаем адрес с результатом. ret
.LCPI1_0: .long 1065353216 # float 1 .long 1065353216 # float 1 .zero 4 .zero 4
foo(OptPoint2): # @foo(OptPoint2) vaddps xmm0, xmm0, xmmword ptr [rip + .LCPI1_0] # Складываем [x, y] c [1, 1]. В xmm0 хранится результат. mov al, 1 # Возвращаем d, al - это младшие 8 бит регистра rax. ret
.LCPI2_0: .long 1077936128 # float 3 .long 1082130432 # float 4 .zero 4 .zero 4
main: # @main push rbx sub rsp, 64 movabs rax, 4611686019492741120 # 0x400000003F800000 Поля x и y. mov qword ptr [rsp + 32], rax # Копируем x, y на стек. mov byte ptr [rsp + 40], 1 # Флаг optional::has_value(). lea rbx, [rsp + 48] lea rsi, [rsp + 32] # Участок стека с аргументом. mov rdi, rbx # Участок стека с результатом. call foo(std::optional<Point>) # Второй вызов осуществляется гораздо проще. vmovaps xmm0, xmmword ptr [rip + .LCPI2_0] # xmm0 = <3,4,u,u> mov edi, 1 # Флаг bool d. call foo(OptPoint2) vmovlps qword ptr [rsp + 16], xmm0 # Копируем результат на стек. mov byte ptr [rsp + 24], al # В al хранится самый младший байт регистра rax.

Впрочем, если пометить функции foo как inline, то генерируемый в месте использования код будет примерно одинаков.

# OptPoint1 foo(OptPoint1) или OptPoint1 foo(const OptPoint1&) vmovss xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero vaddss xmm1, xmm0, dword ptr [rsp + 32] vaddss xmm0, xmm0, dword ptr [rsp + 36] vmovss dword ptr [rsp + 8], xmm1 vmovss dword ptr [rsp + 12], xmm0 mov byte ptr [rsp + 16], 1 # OptPoint2 foo(OptPoint2) или OptPoint2 foo(const OptPoint2&) vmovsd xmm0, qword ptr [rsp + 48] # xmm0 = mem[0],zero vaddps xmm0, xmm0, xmmword ptr [rip + .LCPI0_1] vmovlps qword ptr [rsp + 8], xmm0 mov byte ptr [rsp + 16], 1

Видно, что в случае с простой структурой, компилятор смог соптимизировать код чуть лучше, но в остальном всё одинаково.

Вывод: если функция не inline, то лучше всегда передавать std::optional по ссылке.

Virtual functions

Для реалистичности придумаем следующий пример. Кратко рассмотрим, как у классов вызываются методы, в том числе виртуальные. Есть базовый класс функции, какие-то общие методы для работы с ним и наследники, реализующие, собственно, функции. Допустим, мы делаем математическую библиотеку. В начале рассмотрим реализацию через наследование и виртуальные методы.

struct Fn { virtual ~Fn() noexcept = default; virtual int call(int x) const = 0;
}; struct Add final : Fn { Add(int a) : a(a) {} int call(int x) const override { return a + x; } int a;
}; NOINLINE bool isFixedPoint(const Fn& fn, int x) { return fn.call(x) == x; } int main() { Add add{32}; bool result = isFixedPoint(add, 10);
}

В результат получим что-то вроде такого.

Add::call(int) const: # @Add::call(int) const # В rdi передаётся указатель this первым аргументом, по адресу [rdi, rdi+8) будет указатель на таблицу виртуальных функций, за ней уже идут поля с данными. add esi, dword ptr [rdi + 8] mov eax, esi # Возвращаем результат через rax, eax указывает на его младшие 32 бита. ret # Таблица виртуальных функций для класса Add. Загрузка должна всегда быть со смещением 16, чтобы информация RTTI находилась по отрицательному смещению.
vtable for Add: .quad 0 .quad typeinfo for Add # Информация для RTTI. Смещение -8. .quad Fn::~Fn() # Деструкторы, смещение 0 байт от начала таблицы. .quad Add::~Add() .quad Add::call(int) const # Методы, смещение 16 байт. isFixedPoint(Fn const&, int): # @isFixedPoint(Fn const&, int) push rbx # Так как вызываемая функция не должна менять значение rbx, сохраняем его на стеке, чтоб восстановить перед возвратом. mov ebx, esi # Младшие 32 бита второго аргумента. mov rax, qword ptr [rdi] # В rdi хранится первый аргумент - указатель на Fn, далее этот же регистр используется для передачи параметра this метода. call qword ptr [rax + 16] # Вызываем Add::call. cmp eax, ebx # Возвращённое методом call значение лежит в rax, сравниваем его с ebx, в котором лежит значение второго аргумента. sete al # Записываем результат в младшие 8 бит регистра eax. pop rbx # Восстанавливаем значение rbx. ret main: # @main sub rsp, 40 mov qword ptr [rsp + 24], vtable for Add+16 # Загружаем на стек адрес таблицы виртуальных функций для класса Add, прибавляем к нему 16 для того, чтобы он указывал на, собственно, виртуальные функции. Для доступа к RTTI необходимо использовать отрицательное смещение. mov dword ptr [rsp + 32], 32 # Значение add.a сразу за таблицей. lea rdi, [rsp + 24] # Первый параметр указывает прямо на таблицу. mov esi, 10 # Второй константный параметр. call isFixedPoint(Fn const&, int) mov byte ptr [rsp + 15], al # Копируем на стек результат. ... mov rdi, rax # Обработчик исключений. call _Unwind_Resume mov rdi, rax call _Unwind_Resume

Если же оставить деструктор виртуальным и убрать NOINLINE, то компилятор встроит все вызовы функций и методов и запишет на стек готовый результат (false в данном случае). Если сделать деструктор protected и не виртуальным, то весь код связанный с обработкой исключений исчезнет (строки 34-37). Для интереса переделаем пример с использованием шаблонов. Если пометить деструктор NOINLINE, то добавится просто куча кода с его вызовами.

struct Add final { Add(int a) : a(a) {} NOINLINE int call(int x) const { return a + x; } int a;
}; template<typename T>
NOINLINE bool isFixedPoint(const T& fn, int x) { return fn.call(x) == x; }

Add::call(int) const: # @Add::call(int) const add esi, dword ptr [rdi] # Тут ничего не изменилось, this передаётся в rdi первым аргументом, но так как уже нет таблицы виртуальных функций, то и дополнительное смещение не требуется. mov eax, esi ret bool isFixedPoint<Add>(Add const&, int): # @bool isFixedPoint<Add>(Add const&, int) push rbx mov ebx, esi # Add::call использует те же самые аргументы на тех же местах, что и isFixedPoint. call Add::call(int) const cmp eax, ebx sete al pop rbx ret main: # @main sub rsp, 24 mov dword ptr [rsp + 8], 32 # Инициализируем add.a. lea rdi, [rsp + 8] # Загружаем аргументы в регистры, в rdi хранится адрес поля add.a. mov esi, 10 call bool isFixedPoint<Add>(Add const&, int) mov byte ptr [rsp + 7], al ... ret

Как видно, код заметно компактнее даже с NOINLINE.

Benchmark

В данном случае была будет проводится итерация по вектору с 1000 элементов типа Add и вызова isFixedPoint для каждого из них.

Code

Cycles per iteration

Виртуальный call и деструктор, без вызова isFixedPoint и call

5267

Виртуальный call и деструктор, NOINLINE isFixedPoint

10721

Виртуальный call и деструктор, INLINE isFixedPoint

8291

Виртуальный только call, NOINLINE isFixedPoint

10571

Без виртуальных методов, NOINLINE call, шаблонный NOINLINE isFixedPoint

10536

Без виртуальных методов, без вызова isFixedPoint и call

4505

Без виртуальных методов, INLINE call, шаблонный INLINE isFixedPoint

4531

Что можно заметить:

  • Виртуальные функций вызываются очень быстро.
  • Указатель на таблицу виртуальных функций увеличивает размер класса, что может сказаться на производительности.
  • Даже функции, принимающие аргументы по указателю на базовый класс, лучше объявлять, как inline. Компилятор может их встроить и девиртуализировать.
  • Не inline шаблоны не дают особого выигрыша в производительности. Под не inline я имею ввиду что-то с определением в cpp файле и последующим явным инстанцированием, или явно помеченные как NOINLINE.
  • inline шаблоны дают нулевой оверхед при встраивании.

Tail call

Немного рассмотрим особенности вызова функции не через call, а через jmp без изменения размера стека.

Компилятор clang умеет оптимизировать хвостовую рекурсию. Немного оффтоп. К примеру, возьмём функцию быстрого возведения в степень:

double exp_by_squaring(double x, int n, double y = 1) { if (n < 0) return exp_by_squaring(1.0 / x, -n, y); if (n == 0) return y; if (n == 1) return x * y; if (n % 2 == 0) return exp_by_squaring(x * x, n / 2, y); return exp_by_squaring(x * x, (n - 1) / 2, x * y);
}

Получим:

.LCPI0_0: .quad 4607182418800017408 # double 1
exp_by_squaring(double, int, double): # @exp_by_squaring(double, int, double) vmovsd xmm2, qword ptr [rip + .LCPI0_0] # xmm2 = mem[0],zero vmovapd xmm3, xmm0 test edi, edi jns .LBB0_4 jmp .LBB0_3
.LBB0_9: # in Loop: Header=BB0_4 Depth=1 shr edi vmovapd xmm3, xmm0 test edi, edi jns .LBB0_4
.LBB0_3: # =>This Inner Loop Header: Depth=1 vdivsd xmm3, xmm2, xmm3 neg edi test edi, edi js .LBB0_3
.LBB0_4: # =>This Inner Loop Header: Depth=1 je .LBB0_7 cmp edi, 1 je .LBB0_6 vmulsd xmm0, xmm3, xmm3 test dil, 1 je .LBB0_9 lea eax, [rdi - 1] shr eax, 31 lea edi, [rdi + rax] add edi, -1 sar edi vmulsd xmm1, xmm3, xmm1 vmovapd xmm3, xmm0 test edi, edi jns .LBB0_4 jmp .LBB0_3
.LBB0_6: vmulsd xmm1, xmm3, xmm1
.LBB0_7: vmovapd xmm0, xmm1 ret

Код этой же функции, реализованной через цикл, будет примерно аналогичен. Как видно, нет ни одного рекурсивного вызова, лишь циклы. Причём рекурсивный даже будет на ~10% быстрее.

Сравним три версии одной и той же функции по прибавлению единицы к аргументу. Но я хотел рассмотреть особенности не рекурсивных вызовов функций непосредственно перед возвратом.

int64_t sum(int64_t x, int64_t y) { return x + y; }
int64_t add1(int64_t x) { return sum(x, 1); }
int64_t add2(int64_t x) { return sum(1, x); }
int64_t add3(int64_t x) { return sum(-1, x) + 2; }

sum(long, long): # @sum(long, long) lea rax, [rdi + rsi] ret
add1(long): # @add1(long) mov esi, 1 # Добавляем второй аргумент. jmp sum(long, long) # TAILCALL
add2(long): # @add2(long) mov rax, rdi # Переупорядочиваем значения регистров. mov edi, 1 mov rsi, rax jmp sum(long, long) # TAILCALL
add3(long): # @add3(long) push rax # Сохраняем rax между вызовами функции. mov rax, rdi # Так же, как и в add2, переупорядочиваем регистры. mov rdi, -1 mov rsi, rax call sum(long, long) add rax, 2 # Прибавляем 2 к регистру с результатом. pop rcx ret

Отличие в том, что адрес возврата не меняется, и после завершения функции sum, управление передаётся сразу в функцию, взывавшую add. Как видно, если функция вызывается перед выходом и её результат никак не изменяется, то компилятор использует не call, а более быстрый jmp.

Если пример немного усложнить и замерить производительность, то разница между скоростью выполнения функций будет в районе 10%.

Выводы:

  • Если из функции вызываются другие функции, то лучше всего их вызывать непосредственно перед выходом без манипуляций с результатом.
  • Аргументы лучше располагать везде в одном порядке.

Initialization

Рассмотрим классы для 2D точки с различными состояниями по умолчанию: В данном разделе я хочу рассмотреть особенности инициализации структур и массивов.

struct Point { double x, y;
}; struct ZeroPoint { double x{}, y{};
}; struct NanPoint { double x{quietNaN}, y{quietNaN};
};

ZeroPoint заполняется нулями. Структура Point не инициализируется. По стандарту IEEE 754-1985:

The number zero is represented specially: sign = 0 for positive zero, 1 for negative zero; biased exponent = 0; fraction = 0;

NanPoint заполняется значениями numeric_limits<double>::quiet_NaN(); Да, я сам видел реализацию с такими значения по умолчанию для точки. Так что их можно смело обнулять с помощью memset.

One point

Point data;

sub rsp, 24

Просто выделяем место на стеке без какой-либо инициализации.

ZeroPoint data;
Point data{};

Обе строки дают идентичный результат.

sub rsp, 40 vxorps xmm0, xmm0, xmm0 vmovaps xmmword ptr [rsp + 16], xmm0

Обнуляем регистр xmm0. Выделяем место на стеке. Копируем значение из регистра в память стека. Это делается через XOR так как vxorps работает быстрее записи нуля.

NanPoint data;

sub rsp, 40 vmovaps xmm0, xmmword ptr [rip + .LCPI0_0] # xmm0 = [nan,nan] vmovaps xmmword ptr [rsp + 16], xmm0

То же самое, но в регистр загружаем значение из раздела с константными данными.

Small array

Здесь и далее будут использоваться следующие константы:

static constexpr size_t smallSize = 8;
static constexpr size_t bigSize = 321;
extern size_t smallUnknownSize; // Also 8
extern size_t bigUnknownSize; // Also 321

Рассмотрим простой массив на стеке.

array<Point, smallSize> data;

Как и раньше – просто перемещение указателя на стек.

sub rsp, 136

Как и в случае с одной точкой, но размер стека пропорционально больше.

array<ZeroPoint, smallSize> data;
array<ZeroPoint, smallSize> data{};
array<Point, smallSize> data{};

Заметим явный вызов конструктора по умолчанию в третьей строке.

sub rsp, 192 vxorps ymm0, ymm0, ymm0 vmovaps ymmword ptr [rsp + 128], ymm0 vmovaps ymmword ptr [rsp + 96], ymm0 vmovaps ymmword ptr [rsp + 64], ymm0 vmovaps ymmword ptr [rsp + 32], ymm0

Память очищается кусками по 256 бит, или 2 точки.

array<NanPoint, smallSize> data;
array<NanPoint, smallSize> data{};

sub rsp, 136 vmovaps xmm0, xmmword ptr [rip + .LCPI0_0] # xmm0 = [nan,nan] vmovups xmmword ptr [rsp + 24], xmm0 vmovups xmmword ptr [rsp + 8], xmm0 vmovups xmmword ptr [rsp + 56], xmm0 vmovups xmmword ptr [rsp + 40], xmm0 vmovups xmmword ptr [rsp + 88], xmm0 vmovups xmmword ptr [rsp + 72], xmm0 vmovups xmmword ptr [rsp + 120], xmm0 vmovups xmmword ptr [rsp + 104], xmm0

Тут каждая точка инициализируется по отдельности.

Big array

array<Point, bigSize> data;

sub rsp, 5144

Это было предсказуемо.

array<ZeroPoint, bigSize> data;
array<ZeroPoint, bigSize> data{};
array<Point, bigSize> data{};

sub rsp, 5152 lea rbx, [rsp + 16] xor esi, esi mov edx, 5136 mov rdi, rbx call memset # Вызов memset(rsp+16, 0, 5136).

Указатель на начало, ноль в качестве заполнителся и размер, передаются через регистры rdi, esi, edx соответственно. После выделения места на стеке, вызывается memset. Префикс e вместо d используется для манипуляции младшими 32 битами 64-битного регистра.

array<NanPoint, bigSize> data;

sub rsp, 5144 lea rax, [rsp + 8] lea rcx, [rsp + 5144] vmovaps xmm0, xmmword ptr [rip + .LCPI0_0] # xmm0 = [nan,nan] # Цикл инициализации.
.LBB0_1: # =>This Inner Loop Header: Depth=1 vmovups xmmword ptr [rax], xmm0 vmovups xmmword ptr [rax + 16], xmm0 vmovups xmmword ptr [rax + 32], xmm0 add rax, 48 cmp rax, rcx jne .LBB0_1

В каждой итерации копируются сразу три элемента, так как число 321 делится на 3 без остатка. Тут уже используется цикл. В регистрах rax, rcx хранятся адреса начала и конца массива.

array<NanPoint, bigSize> data{};

sub rsp, 5152 lea rbx, [rsp + 16] xor esi, esi mov edx, 5136 mov rdi, rbx call memset # Вызов memset(rsp+16, 0, 5136). lea rax, [rsp + 5152] vmovaps xmm0, xmmword ptr [rip + .LCPI0_0] # xmm0 = [nan,nan] # Цикл инициализации.
.LBB0_1: # =>This Inner Loop Header: Depth=1 vmovups xmmword ptr [rbx], xmm0 vmovups xmmword ptr [rbx + 16], xmm0 vmovups xmmword ptr [rbx + 32], xmm0 add rbx, 48 cmp rbx, rax jne .LBB0_1

Присутствует как цикл, так и вызов memset. А вот тут результат довольно неожиданный. Но в данном случае это откровенно лишняя работа. Это логично, так как в общем случае, в структуре могут быть зазоры между элементами.

Vector

vector<Point> data(smallSize);

sub rsp, 40 vxorps xmm0, xmm0, xmm0 vmovaps xmmword ptr [rsp], xmm0 mov qword ptr [rsp + 16], 0 mov edi, 128 call operator new(unsigned long) # Вызов new(128). mov qword ptr [rsp], rax mov rcx, rax sub rcx, -128 mov qword ptr [rsp + 16], rcx vxorps xmm0, xmm0, xmm0 # Развёрнутый цикл с заполнением нулями. vmovups xmmword ptr [rax + 16], xmm0 vmovups xmmword ptr [rax], xmm0 vmovups xmmword ptr [rax + 32], xmm0 vmovups xmmword ptr [rax + 48], xmm0 vmovups xmmword ptr [rax + 64], xmm0 vmovups xmmword ptr [rax + 80], xmm0 vmovups xmmword ptr [rax + 96], xmm0 vmovups xmmword ptr [rax + 112], xmm0

По умолчанию, контейнеры инициализируют все элементы значением T{}, это поведение можно переопределить, предоставив собственный аллокатор. Вызываем new и обнуляем все элементы. Увлеичим количество элементов: Листинги для ZeroPoint и NanPoint практически аналогичны.

vector<Point> data(bigSize);

main: # @main push rbx sub rsp, 48 vxorps xmm0, xmm0, xmm0 vmovaps xmmword ptr [rsp], xmm0 mov qword ptr [rsp + 16], 0 mov edi, 5136 call operator new(unsigned long) # Вызов new(5136). mov qword ptr [rsp], rax mov qword ptr [rsp + 8], rax mov rcx, rax add rcx, 5136 mov qword ptr [rsp + 16], rcx vxorps xmm0, xmm0, xmm0 vmovaps xmmword ptr [rsp + 32], xmm0 xor edx, edx # Цикл с заполнением нулями.
.LBB0_2: # =>This Inner Loop Header: Depth=1 vmovaps xmm0, xmmword ptr [rsp + 32] vmovups xmmword ptr [rax + rdx], xmm0 vmovaps xmm0, xmmword ptr [rsp + 32] vmovups xmmword ptr [rax + rdx + 16], xmm0 vmovaps xmm0, xmmword ptr [rsp + 32] vmovups xmmword ptr [rax + rdx + 32], xmm0 add rdx, 48 cmp rdx, 5136 jne .LBB0_2 mov qword ptr [rsp + 8], rcx mov rax, rsp

В случае с NanPoint листинг примерно аналогичен. Как и в случае с массивом, инициализация происходит пачками через цикл.

vector<NanPoint> data(bigSize);

main: # @main push rbx sub rsp, 32 vxorps xmm0, xmm0, xmm0 vmovaps xmmword ptr [rsp], xmm0 mov qword ptr [rsp + 16], 0 mov edi, 5136 call operator new(unsigned long) # Вызов new(5136). mov qword ptr [rsp], rax mov qword ptr [rsp + 8], rax mov rcx, rax add rcx, 5136 mov qword ptr [rsp + 16], rcx xor edx, edx vmovaps xmm0, xmmword ptr [rip + .LCPI0_0] # xmm0 = [nan,nan] # Цикл с заполнением NAN.
.LBB0_2: # =>This Inner Loop Header: Depth=1 vmovups xmmword ptr [rax + rdx], xmm0 vmovups xmmword ptr [rax + rdx + 16], xmm0 vmovups xmmword ptr [rax + rdx + 32], xmm0 add rdx, 48 cmp rdx, 5136 jne .LBB0_2 mov qword ptr [rsp + 8], rcx mov rax, rsp

A вот при использовании ZeroPoint код заметно отличается.

vector<ZeroPoint> data(bigSize);

sub rsp, 32 vxorps xmm0, xmm0, xmm0 vmovaps xmmword ptr [rsp], xmm0 mov qword ptr [rsp + 16], 0 mov edi, 5136 call operator new(unsigned long) # Вызов new(5136). mov qword ptr [rsp], rax mov rbx, rax add rbx, 5136 mov qword ptr [rsp + 16], rbx xor esi, esi mov edx, 5136 mov rdi, rax call memset # Вызов memset(&data, 0, 5136).

Вспомним, что в случае с массивом, memset вызывался и при использовании Point. Только в этом случае вызывается memset. Посмотрим, что будет, если значение bigUnknownSize не известно на момент компиляции.

vector<NanPoint> data(bigUnknownSize);

sub rsp, 32 mov rbx, qword ptr [rip + bigUnknownSize] vxorps xmm0, xmm0, xmm0 vmovaps xmmword ptr [rsp], xmm0 mov qword ptr [rsp + 16], 0 test rbx, rbx # Если bigUnknownSize == 0, то пропускаем new. je .LBB0_1 mov rax, rbx shr rax, 60 jne .LBB0_3 mov rdi, rbx shl rdi, 4 # Умножение на 16 чере сдвиг на 4. call operator new(unsigned long) # Вызов new(bigUnknownSize*16). jmp .LBB0_6
.LBB0_1: xor eax, eax
.LBB0_6: mov rcx, rbx shl rcx, 4 add rcx, rax mov qword ptr [rsp], rax mov qword ptr [rsp + 8], rax mov qword ptr [rsp + 16], rcx test rbx, rbx # Если bigUnknownSize == 0, то пропускаем инициализацию. je .LBB0_14 lea rdx, [rbx - 1] mov rsi, rbx and rsi, 7 je .LBB0_10 neg rsi vmovaps xmm0, xmmword ptr [rip + .LCPI0_0] # xmm0 = [nan,nan] # Инициализируем первые 0-7 элементов.
.LBB0_9: # =>This Inner Loop Header: Depth=1 vmovups xmmword ptr [rax], xmm0 dec rbx add rax, 16 inc rsi jne .LBB0_9
.LBB0_10: cmp rdx, 7 jb .LBB0_13 vmovaps xmm0, xmmword ptr [rip + .LCPI0_0] # xmm0 = [nan,nan] # Инициализируем оставшиеся элементы пачками по 8.
.LBB0_12: # =>This Inner Loop Header: Depth=1 vmovups xmmword ptr [rax], xmm0 vmovups xmmword ptr [rax + 16], xmm0 vmovups xmmword ptr [rax + 32], xmm0 vmovups xmmword ptr [rax + 48], xmm0 vmovups xmmword ptr [rax + 64], xmm0 vmovups xmmword ptr [rax + 80], xmm0 vmovups xmmword ptr [rax + 96], xmm0 vmovups xmmword ptr [rax + 112], xmm0 sub rax, -128 add rbx, -8 jne .LBB0_12
.LBB0_13: mov rax, rcx
.LBB0_14: mov qword ptr [rsp + 8], rax mov rax, rsp

Первый, LBB0_9 заполняет по одной точке до тех пор, пока количество оставшихся элементов не станет кратно 8. Можно увидеть два цикла. После чего идёт заполнение сразу 8 точек за итерацию.

Как и в прошлый раз, листинг с Point примерно такой же, а при ZeroPoint опять используется memset:

vector<ZeroPoint> data(bigUnknownSize);

sub rsp, 40 mov rbx, qword ptr [rip + bigUnknownSize] vxorps xmm0, xmm0, xmm0 vmovaps xmmword ptr [rsp], xmm0 mov qword ptr [rsp + 16], 0 test rbx, rbx # Если bigUnknownSize == 0, то пропускаем new. je .LBB0_1 mov rax, rbx shr rax, 60 jne .LBB0_3 mov rdi, rbx shl rdi, 4 call operator new(unsigned long) # Вызов new(bigUnknownSize*16). jmp .LBB0_6
.LBB0_1: xor eax, eax
.LBB0_6: mov rdx, rbx shl rdx, 4 lea r14, [rax + rdx] mov qword ptr [rsp], rax mov qword ptr [rsp + 8], rax mov qword ptr [rsp + 16], r14 test rbx, rbx # Если bigUnknownSize == 0, то пропускаем memset. je .LBB0_8 xor esi, esi mov rdi, rax call memset # Вызов memset(&data, 0, bigUnknownSize*16). mov rax, r14
.LBB0_8: mov qword ptr [rsp + 8], rax mov rax, rsp

Кстати, компиляция

vector<NanPoint> data;
data.resize(bigUnknownSize);

Но operator new вызывается только один раз, так как при создании пустого вектора он не используется. произведёт больше 250 строк ассемблера, что заметно больше случая с передачей размера непосредственно в конструктор.

Benchmark

Теперь сравним скорость выполенения всех вышерассмотренных примеров.

Code

Cycles per iteration

Point p;

4.5

ZeroPoint p;

5.2

NanPoint p;

4.5

array<Point, smallSize> p;

4.5

array<ZeroPoint, smallSize> p;

6.7

array<NanPoint, smallSize> p;

6.7

array<Point, bigSize> p;

4.5

array<ZeroPoint, bigSize> p;

296.0

array<NanPoint, bigSize> p;

391.0

array<Point, bigSize> p{};

292.0

array<NanPoint, bigSize> p{};

657.0

vector<Point> p(smallSize);

32.3

vector<ZeroPoint> p(smallSize);

33.8

vector<NanPoint> p(smallSize);

33.8

vector<Point> p(bigSize);

323.0

vector<ZeroPoint> p(bigSize);

308.0

vector<NanPoint> p(bigSize);

281.0

vector<ZeroPoint> p(smallUnknownSize);

44.1

vector<NanPoint> p(smallUnknownSize);

37.6

vector<Point> p(bigUnknownSize);

311.0

vector<ZeroPoint> p(bigUnknownSize);

315.0

vector<NanPoint> p(bigUnknownSize);

290.0

vector<NanPoint> p; p.resize(bigUnknownSize);

315.0

Выводы:

  • Создание массива на стеке без инициализации ничего не стоит.
  • Инициализация небольших массивов на стеке очень быстра.
  • Инициализация массивов на стеке через memset работает ощутимо быстрее, чем через явный цикл с инициализацией каждого элемента.
  • Не вызывайте конструктор у массива с элементами со сложной инициализацией.
  • Для небольших векторов выделение памяти более затратно, чем инициализация. Различия становятся малозаметны при размерах уже в несколько десятков элементов.
  • Инициализация элементов вектора происходит даже при отсутствии конструктора. Для изменения подобного поведения можно использовать свой аллокатор.
  • У векторов с большим количеством элементов, значительное количество времени уходит на инициализацию. Причём знание размера на момент компиляции не так важно.
Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть