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

в 10:46, , рубрики: abi, c++, clang, optional, system v, xeon, виртуальные функции, вызов функции, инициализация, массивы, ненормальное программирование, оптимизация, Программирование, производительность, хвостовая рекурсия

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

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

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

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

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

Если явно не указано обратное, то все используемые функции были помечены как NOINLINE. Делаем вид, что тело функции расположено в cpp файле, а LTO отключено. Также все результаты функций передаются в пустую 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) { return s.a + s.b; }
...
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

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

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

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

Смотрим пункт 3.2. Так как в 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));

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

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

'no reuse' указывает на то, что для хранения каждого результата используется новая переменная. auto a2 = foo(a, b); auto a3 = foo(a2, b);. '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}; }

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

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

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

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

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

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

Выводы:

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

Initialization

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

struct Point {
    double x, y;
};

struct ZeroPoint {
    double x{}, y{};
};

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

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

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

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

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).

После выделения места на стеке, вызывается memset. Указатель на начало, ноль в качестве заполнителся и размер, передаются через регистры rdi, esi, edx соответственно. Префикс 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

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

vector<NanPoint> data(bigSize);

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

Как и в случае с массивом, инициализация происходит пачками через цикл. В случае с Point листинг примерно аналогичен, а вот при использовании 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. Вспомним, что в случае с массивом, memset вызывался и при использовании Point.

vector<NanPoint> data(bigUnknownSize);

Тут значение 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);

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

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 работает значительно, чем через цикл с копированием.
  • Не вызывайте конструктор у массива с элементами со сложной инициализацией.
  • Для небольших векторов выделение памяти более затратно, чем инициализация. Различия становятся малозаметны при размерах уже в несколько десятков элементов.
  • Инициализация элементов вектора происходит даже при отсутствии конструктора. Для изменения подобного поведения можно использовать свой аллокатор.
  • Для больших векторов большая времени работы уходит на инициализацию. Причём знание размера на момент компиляции не так важно.

Автор: Unrul

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js