Оценка числа инструкций при выполнении типовой задачи

Кафедра кибернетики и вычислительной техники.

Отчёт по лабораторной работе №5 по дисциплине: «Вычислительные системы» на тему: » РАСЧЁТ БЫСТРОДЕЙСТВИЯ ПРОЦЕССОРА И ПАРАМЕТРОВ ТИПОВОГО ЗАДАНИЯ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ «

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

Вариант 27

Интенсивность li поступления заданий, с-1.

Среднее число qi процессорных операций (десятки миллионов) и средние числа Nij обращений к файлам.

Ход работы:

1. Определение параметров типового задания

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

— интенсивность l потока заданий:

— число процессорных операций при выполнении типового задания:

;

(оп.)

— число Dj обращений к файлу Fj для типового задания:

, j = 1, … , N;

(с-1) и т. д.

— число D обращений к файлам для типового задания:

(с-1)

— вероятность pj использования файла Fj:

pj = Dj /D, j = 1, … , N

p1 = 5.26/30.8=0.17 и т. д.

— средняя трудоемкость qо этапа счета:

qо = q / (D + 1),

(оп)

2. Расчет минимального быстродействия процессора

Чтобы получить оценку быстродействия процессора его можно представить как систему массового обслуживания. В этом случае существование стационарного режима (режим с конечной очередью)определяется условием:

r < 1 ,

где:

r — загрузка процессора потоком заданий,

r = r1 + … + rм, и ri = li qi / B, i = 1, … , M.

Отсюда получаем В >В* , где

Нижнюю оценку необходимого быстродействия В*, можно также вычислить так: В* = l q,

(оп/с)

При быстродействии В*, время w пребывания задания в системе может принять очень большие значения (хоть и конечные). В случае если время w ограничено, возникает необходимость вычислять другое B, обеспечивающее заданное время пребывания, т. е. В>В(w*), где

,

Для быстрой оценки В воспользуемся графиком функции В(w*).

Рисунок 1. График зависимости B от w*

Выводы: по проделанным расчётам можно сказать, что минимальное допустимое быстродействие процессора, выполняющего типовое задание с заданными характеристиками, должно быть не менее 8,3 млн. оп./cек. Нарушение заданного порога приведёт к выходу процессора из стационарного режима, что не допустимо( время пребывания задания в процессоре → ∞).

Если же ограничить время пребывания задания w (например до 1сек) то, как видно из рисунка 1, быстродуйствие приходится резко увеличить до 35,7 млн. оп./сек. Дальнейшее уменьшение w приводит к очень резкому росту производительности, что затрудняет удовлетворение заданного быстродействия на практике.

Linux perf_event_open system call with config = PERF_COUNT_HW_INSTRUCTIONS

This Linux system call appears to be a cross architecture wrapper for performance events, including both hardware performance counters from the CPU and software events from the kernel.

Here’s an example adapted from the man perf_event_open page:

perf_event_open.c

#define _GNU_SOURCE
#include <asm/unistd.h>
#include <linux/perf_event.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/ioctl.h>
#include <unistd.h>

#include <inttypes.h>
#include <sys/types.h>

static long
perf_event_open(struct perf_event_attr *hw_event, pid_t pid,
                int cpu, int group_fd, unsigned long flags)
{
    int ret;

    ret = syscall(__NR_perf_event_open, hw_event, pid, cpu,
                    group_fd, flags);
    return ret;
}

int
main(int argc, char **argv)
{
    struct perf_event_attr pe;
    long long count;
    int fd;

    uint64_t n;
    if (argc > 1) {
        n = strtoll(argv[1], NULL, 0);
    } else {
        n = 10000;
    }

    memset(&pe, 0, sizeof(struct perf_event_attr));
    pe.type = PERF_TYPE_HARDWARE;
    pe.size = sizeof(struct perf_event_attr);
    pe.config = PERF_COUNT_HW_INSTRUCTIONS;
    pe.disabled = 1;
    pe.exclude_kernel = 1;
    // Don't count hypervisor events.
    pe.exclude_hv = 1;

    fd = perf_event_open(&pe, 0, -1, -1, 0);
    if (fd == -1) {
        fprintf(stderr, "Error opening leader %llx\n", pe.config);
        exit(EXIT_FAILURE);
    }

    ioctl(fd, PERF_EVENT_IOC_RESET, 0);
    ioctl(fd, PERF_EVENT_IOC_ENABLE, 0);

    /* Loop n times, should be good enough for -O0. */
    __asm__ (
        "1:;\n"
        "sub $1, %[n];\n"
        "jne 1b;\n"
        : [n] "+r" (n)
        :
        :
    );

    ioctl(fd, PERF_EVENT_IOC_DISABLE, 0);
    read(fd, &count, sizeof(long long));

    printf("Used %lld instructions\n", count);

    close(fd);
}

Compile and run:

g++ -ggdb3 -O0 -std=c++11 -Wall -Wextra -pedantic -o perf_event_open.out perf_event_open.c
./perf_event_open.out

Output:

Used 20016 instructions

So we see that the result is pretty close to the expected value of 20000: 10k * two instructions per loop in the __asm__ block (sub, jne).

If I vary the argument, even to low values such as 100:

./perf_event_open.out 100

it gives:

Used 216 instructions

maintaining that constant + 16 instructions, so it seems that accuracy is pretty high, those 16 must be just the ioctl setup instructions after our little loop.

Now you might also be interested in:

• prevent reordering of the syscalls: Enforcing statement order in C++
• prevent the test loop from being optimized out: How to prevent GCC from optimizing out a busy wait loop?

Other events of interest that can be measured by this system call:

• cycle counts: How to get the CPU cycle count in x86_64 from C++?

Tested on Ubuntu 20.04 amd64, GCC 9.3.0, Linux kernel 5.4.0, Intel Core i7-7820HQ CPU.

perf stat CLI utility

The perf CLI utility can print an instruction estimate. Ubuntu 22.04 setup:

sudo apt install linux-tools-common linux-tools-generic
echo -1 | sudo tee /proc/sys/kernel/perf_event_paranoid

Usage:

perf stat <mycmd>

Let’s test with the following Linux x86 program which loops 1 million times. Each loop has 2 instructions: inc and loop, so we expect about 2 million instruction.

main.S

.text
.global _start
_start:
    mov $0, %rax
    mov $1000000, %rcx
.Lloop_label:
    inc %rax
    loop .Lloop_label

    /* exit */
    mov $60, %rax   /* syscall number */
    mov $0, %rdi    /* exit status */
    syscall

Assemble and run:

as -o main.o main.S
ld -o main.out main.o
perf stat ./main.out

Sample output:

 Performance counter stats for './main.out':

              1.51 msec task-clock                #    0.802 CPUs utilized          
                 0      context-switches          #    0.000 /sec                   
                 0      cpu-migrations            #    0.000 /sec                   
                 2      page-faults               #    1.328 K/sec                  
         5,287,702      cycles                    #    3.511 GHz                    
         2,092,040      instructions              #    0.40  insn per cycle         
         1,017,489      branches                  #  675.654 M/sec                  
             1,156      branch-misses             #    0.11% of all branches        

       0.001878269 seconds time elapsed

       0.001922000 seconds user
       0.000000000 seconds sys

So it says about 2 million instructions. Only about 92k off. So it is not absolutely precise, but good enough for many applications. And we also get some other fun statistics like branch misses and page faults.

The extra instructions presumably come from imprecise sampling barriers that ended up including kernel/other processes’ instructions.

perf can also do a bunch more advanced things, e.g. here I show how to use it to profile code: How do I profile C++ code running on Linux?

Рассматривая
различные алгоритмы решения одной и
той же задачи, по­лезно проанализировать,
сколько вычислительных ресурсов они
требуют (время работы, память), и выбрать
наиболее эффективный. Конечно, надо
договориться о том, какая модель
вычислений используется. В данном
учебном пособии в качестве модели по
большей части используется обычная
однопроцессорная машина
с произвольным доступом
(random—access
machine,
RAM),
не предусматривающая параллельного
выполнения операций.

Под
временем
работы
(running
time)
алгоритма будем подразумевать число
элементар­ных шагов, которые он
выполняет. Положим, что одна строка
псевдокода требует не более чем
фиксированного числа операций (если
только это не словесное описание каких-то
сложных действий – типа «отсортировать
все точки по x-координате»).
Следует также различать вызов
(call)
процедуры (на который уходит фиксированное
число операций) и её исполнение
(execution),
которое может быть долгим.

Сложность
алгоритма – это величина, отражающая
порядок величины требуемого ресурса
(времени или дополнительной памяти) в
зависимости от размерности задачи.

Таким
образом, будем различать временную T(n)
и пространственную V(n)
сложности алгоритма. При рассмотрении
оценок сложности, будем использовать
только временную сложность. Пространственная
сложность оценивается аналогично. Самый
простой способ оценки – экспериментальный,
то есть запрограммировать алгоритм и
выполнить полученную программу на
нескольких задачах, оценивая время
выполнения программ. Однако, этот способ
имеет ряд недостатков. Во-первых,
экспериментальное программирование –
это, возможно, дорогостоящий процесс.
Во-вторых, необходимо учитывать, что на
время выполнения программ влияют
следующие факторы:

1. Временная
   сложность алгоритма программы;

2. Качество
   скомпилированного кода исполняемой
   программы;

3. Машинные
   инструкции, используемые для выполнения
   программы.

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

Часто,
временная сложность алгоритма зависит
от количества входных данных. Обычно
говорят, что временная сложность
алгоритма имеет порядок T(n)
от входных данных размера n.
Точно определить величину T(n)
на практике представляется довольно
трудно. Поэтому прибегают к асимптотическим
отношениям с использованием

O-символики.

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

Листинг
1.3 – Псевдокод алгоритма сортировки
вставками с оценками времени выполнения

Для
вычисления суммарного времени выполнения
процедуры Insertion-Sort
отметим
около каждой стро­ки её стоимость
(число операций) и число раз, которое
эта строка исполняется. Для каждого j
от
2 до п
(здесь
п
=
length[A]
–
размер массива) требуется подсчитать,
сколько раз будет исполнена строка 5,
обозначим это число через t_j.
Строки
внутри цикла выполняются на один раз
меньше, чем проверка, поскольку последняя
проверка выводит из цикла. Строка
стоимостью c,
повторённая т
раз,
даёт вклад c
m
в
общее число операций (однако, это
выражение нельзя использовать для
оценки количества использованной
памяти). Сложив вклады всех строк, получим

Время
работы процедуры зависит не только от
п
но
и от того, какой именно массив размера
п
подан
ей на вход. Для процедуры Insertion-Sort
наиболее
благоприятен случай, когда массив уже
отсортиро­ван. Тогда цикл в строке 5
завершается после первой же проверки
(поскольку A[i]
≤
key
при
i
=
j
–
1), так что все t_j
равны
1, и общее время есть

Таким
образом, в наиболее благоприятном случае
время T(n),
необходимое для сортировки массива
размера п,
является
линейной функцией (linear
function)
от n,
т.е. имеет вид Т(п)
=
a  n + b
для некоторых констант a
и
b.
Эти константы определяются выбранными
значениями с₁,…,
с₈.

Если же массив
расположен в обратном (убывающем)
порядке, время работы

процедуры
будет максимальным: каждый элемент A[j]
придётся
сравнить со всеми элементами А[1],…,
A[j
–
1]. При этом t_j
= j.
Поскольку

получаем, что в
худшем случае время работы процедуры
равно

В
данном
случае
T(n)
– квадратичная
(quadratic
function),
т.е.
имеет
вид
Т(п) = an²
+ bn
+ с.
Константы
a, b и
с здесь
также определяются значениями с₁,…,с₈.

Обычно
говорят, что временная сложность
алгоритма имеет порядок T(n)
от входных данных размера n.
Точно определить величину T(n)
на практике представляется довольно
трудно. Поэтому прибегают к асимптотическим
отношениям с использованием O-символики.

Например,
если число тактов (действий), необходимое
для работы алгоритма, выражается как
16n² + 12n log n + 2n + 3,
то это алгоритм, для которого T(n)
имеет порядок O(n²).
При формировании асимптотической
O-оценки
из всех слагаемых исходного выражения
оставляется одно, вносящее наибольший
вклад при больших n
(остальными слагаемыми можно пренебречь)
и игнорируется коэффициент перед ним
(так как все асимптотические оценки
даются с точностью до константы).

Когда
используют обозначение O(),
имеют в виду не точное время исполнения,
а только его предел сверху, причем с
точностью до постоянного множителя.
Когда говорят, например, что алгоритму
требуется время порядка O(n²),
имеют в виду, что время исполнения задачи
растет не быстрее, чем квадрат количества
элементов.

Таблица 1.2
– Сравнительный анализ скорости роста
функций

Рисунок
1.1 – Примеры различных функциональных
зависимостей

Если
считать, что числа, приведенные в
таблице 1.2,
соответствуют микросекундам, то для
задачи с 1048476 элементами алгоритму со
временем работы T(log n)
потребуется 20 микросекунд, а алгоритму
со временем работы T(n²)
– более 12 дней.

Если
операция выполняется за фиксированное
число шагов, не зависящее от количества
данных, то принято писать O(1).

Следует
обратить внимание, что основание
логарифма в асимптотических оценках
не пишется. Причина этого весьма проста.
Пусть есть O(log₂ n).
Но log₂ n = log₃ n / log₃ 2,
а log₃ 2,
как и любую константу, символ О()
не учитывает. Таким образом, O(log₂ n)
= O(log₃ n).
К любому основанию можно перейти
аналогично, а, значит, и писать его не
имеет смысла.

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

• максимальную
  сложность T_max(n),
  или сложность наиболее неблагоприятного
  случая, когда алгоритм работает дольше
  всего;

• среднюю
  сложность T_mid(n)
  – сложность алгоритма в среднем;

• минимальную
  сложность T_min(n)
  – сложность в наиболее благоприятном
  случае, когда алгоритм справляется
  быстрее всего.

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

1. Время
   выполнения операций присваивания,
   чтения, записи обычно имеют порядок
   O(1).
   Исключением являются операторы
   присваивания, в которых операнды
   представляют собой массивы или вызовы
   функций;

2. Время
   выполнения последовательности операций
   совпадает с наибольшим временем
   выполнения операции в данной
   последовательности (правило сумм: если
   T₁(n)
   имеет порядок O(f(n)),
   а T₂(n)
   – порядок O(g(n)),
   то T₁(n)
   + T₂(n)
   имеет порядок O(max(f(n),
   g(n)));

3. Время
   выполнения конструкции ветвления
   (if-then-else)
   состоит из времени вычисления логического
   выражения (обычно имеет порядок O(1))
   и наибольшего из времени, необходимого
   для выполнения операций, исполняемых
   при истинном значении логического
   выражения и при ложном значении
   логического выражения;

4. Время
   выполнения цикла состоит из времени
   вычисления условия прекращения цикла
   (обычно имеет порядок O(1) )
   и произведения количества выполненных
   итераций цикла на наибольшее возможное
   время выполнения операций тела цикла.

5. Время
   выполнения операции вызова процедур
   определяется как время выполнения
   вызываемой процедуры;

6. При
   наличии в алгоритме операции безусловного
   перехода, необходимо учитывать изменения
   последовательности операций,
   осуществляемых с использованием этих
   операции безусловного перехода.

Итак,
время работы в худшем случае и в лучшем
случае могут
сильно
различаться. При анализе алгоритмов
наиболее часто используется время
работы в худшем случае
(worst—case
running
time),
которое определяется как максимальное
время работы для входов данного размера.
Почему? Вот несколько причин.

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

2. На
   практике «плохие» входы (для которых
   время работы близко к максимуму)
   встречаются наиболее часто. Например,
   для базы данных плохим запросом может
   быть поиск отсутствующего элемента
   (очень распространенная ситуация);

3. Время
   работы в среднем может быть до­вольно
   близко к времени работы в худшем случае.
   Пусть, например, сортируется массив
   из п
   случайных
   чисел
   с помощью процедуры Insertion-Sort.Сколько
   раз придётся выполнить цикл в строках
   5-8 (листинг 1.3)? В среднем около половины
   элементов массива A[1..j
   – 1]
   больше A[j],
   так
   что t_j
   в
   среднем можно считать равным j/2,
   и
   время Т(п)
   квадратично
   зависит от n.

В
некоторых случаях требуется также
среднее время
работы
(average—case
running
time,
expected
running
time)
алгоритма на входах данной длины.
Конечно, эта величина зависит от
выбранного распределения вероятно­стей,
и на практике реальное распределение
входов может отличаться от пред­полагаемого,
которое обычно считают равномерным.
Иногда можно добиться равномерности
распределения, используя датчик случайных
чисел.

Как оценить реальную производительность своего кода

Код, который мы пишем, и который будет исполнен процессором, — две разные вещи. На уровне ассемблера существует миллион вариантов, в каком виде интерпретировать и запустить высокоуровневые команды. Более того, современные компиляторы сильно оптимизируют код, а результат этой оптимизации похож на магию.

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

Для такой оптимизации хочется в реальном времени наблюдать, к каким изменениям в машинном коде приводит редактирование исходника. Есть специальные инструменты, которые выполняют такую трансляцию на лету, в том числе Compiler Explorer (многие называют этот инструмент Godbolt по доменному имени и фамилии автора), uiCA, Quick C++ Benchmark, а также Sharplab.io, который специализируется на быстрой компиляции C#.

Compiler Explorer

Известный ресурс Compiler Explorer (godbolt.org) от Мэтта Годбольта демонстрирует результат трансляции в машинный код для 46 языков программирования:

  Id             | Name
  csharp         | C#
  fsharp         | F#
  vb             | Visual Basic
  go             | Go
  c              | C
  c++            | C++
  fortran        | Fortran
  assembly       | Assembly
  circle         | C++ (Circle)
  circt          | CIRCT
  hlsl           | HLSL
  cppx           | Cppx
  crystal        | Crystal
  dart           | Dart
  erlang         | Erlang
  carbon         | Carbon
  hook           | Hook
  cppx_blue      | Cppx-Blue
  cppx_gold      | Cppx-Gold
  mlir           | MLIR
  cuda           | CUDA C++
  analysis       | Analysis
  python         | Python
  racket         | Racket
  ruby           | Ruby
  typescript     | TypeScript Native
  d              | D
  ada            | Ada
  cpp_for_opencl | C++ for OpenCL
  openclc        | OpenCL C
  llvm           | LLVM IR
  cpp2_cppfront  | Cpp2-cppfront
  rust           | Rust
  ispc           | ispc
  java           | Java
  kotlin         | Kotlin
  nim            | Nim
  pony           | Pony
  scala          | Scala
  solidity       | Solidity
  clean          | Clean
  pascal         | Pascal
  haskell        | Haskell
  ocaml          | OCaml
  swift          | Swift
  zig            | Zig

На интересующий язык можно перейти сразу по прямой ссылке, указав его в поддомене, например, erlang.godbolt.org, rust.godbolt.org и т. д.

Интерфейс простой: в окошке слева вводим исходный код, в окошке справа появляется результат компиляции. Сверху выпадающее меню с выбором версии компилятора и аппаратной платформы, под которую генерируется машинный код. Там же можно указать настройки компилятора (включить разные оптимизации) и посмотреть, как это отразится на результате. По умолчанию код компилируется без каких-либо оптимизаций.

Интерфейс меняется по желанию пользователя: можно сравнить справа два компилятора, а можно добавить окошки для сравнения двух вариантов исходного кода:

Отобразить промежуточный язык LLVM:

Или препроцессор:

Удобно, что каждый пример кода можно расшарить с коллегами по прямой ссылке (кнопка Share):

Автор запустил проект в далёком 2012 году как маленький экспериментальный сайтик под названием GCC Explorer (тогда он поддерживал только один компилятор GCC), а сейчас он вырос в большой и полезный ресурс для изучения компиляторов C++ и других языков программирования, а также оптимизации кода. По статистике проекта, сейчас он выполняет более 200 000 компиляций в сутки, примерно по 3 компиляции в секунду. В основном на C++ и C.

Любопытно, что на третье место по популярности среди языков программирования вышел Rust, хотя C++ и C остаются вне конкуренции.

Оптимизация кода

▍ Количество инструкций

По машинному коду в Godbolt можно примерно прикинуть производительность своего кода. Самая наивная метрика — количество инструкций. Чем их меньше, тем лучше. Хотя это не всегда так, потому что некоторые инструкции в современном ассемблере могут выполняться за сотни вычислительных циклов на CPU. Кажется, что если есть возможность изменить оригинальный исходник и количество инструкций в машинном коде уменьшится, это может быть полезно. Но по большому счёту это довольно бесполезная микрооптимизация, поскольку скорость выполнения разных инструкций отличается в разы. А сами вычислительные инструкции можно считать практически бесплатными по сравнению с обращениями в память.

▍ Обращения к памяти

Обращения к памяти, в том числе к кешу L3 — на несколько порядков более медленная операция, чем любое вычисление в CPU. По идее, минимизация обращений к памяти (в том числе через исключения) — первая и главная цель оптимизации, а не простое количество вычислительных инструкций.

▍ Бенчмарк ассемблера

Для более наглядной оценки есть специальные инструменты визуализации и бенчмарки, которые помогают примерно оценить производительность машинного кода, такие как анализатор uiCA (The uops.info Code Analyzer). Копируем сюда фрагмент ассемблерного кода из предыдущего окна Godbolt и запускаем эмулятор.

Например, возьмём для анализа такой цикл:

loop:
add rax, [rsi]
adc rax, [rsi+rbx]
shld rcx, rcx, 1
shld rcx, rdx, 2
dec r15
jnz loop

Выдача uiCA:

Throughput (in cycles per iteration): 4.00
Bottleneck: Dependencies

M - Macro-fused with previous instruction

┌───────────────────────┬────────┬───────┬───────────────────────────────────────────────────────────────────────┬───────┐
│ MITE   MS   DSB   LSD │ Issued │ Exec. │ Port 0   Port 1   Port 2   Port 3   Port 4   Port 5   Port 6   Port 7 │ Notes │
├───────────────────────┼────────┼───────┼───────────────────────────────────────────────────────────────────────┼───────┤
│              1        │   1    │   2   │                     1                          1                      │       │ add rax, qword ptr [rsi]
│              1        │   2    │   2   │  0.66                        1                         0.34           │       │ adc rax, qword ptr [rsi+rbx*1]
│              1        │   1    │   1   │  0.48                                                  0.52           │       │ shld rcx, rcx, 0x1
│              1        │   1    │   1   │            1                                                          │       │ shld rcx, rdx, 0x2
│              1        │   1    │   1   │                                                         1             │       │ dec r15
│                       │        │       │                                                                       │   M   │ jnz 0xffffffffffffffec
├───────────────────────┼────────┼───────┼───────────────────────────────────────────────────────────────────────┼───────┤
│              5        │   6    │   7   │  1.13      1        1        1                 1       1.87           │       │ Total
└───────────────────────┴────────┴───────┴───────────────────────────────────────────────────────────────────────┴───────┘

Анализатор оценивает пропускную способность этого цикла на архитектуре Skylake в четыре цикла на итерацию (процессорную инструкцию), а бутылочным горлышком производительности называет зависимости.

Вот как выглядит трассировка исполнения для 25 первых итераций цикла:

Кроме Skylake, можно посмотреть трассировку выполнения на всех последних микроархитектурах Intel: Sandy Bridge, Ivy Bridge, Haswell, Broadwell, Skylake-X, Kaby Lake, Coffee Lake, Cascade Lake, Ice Lake, Tiger Lake и Rocket Lake.

Выдача стандартного objdump:

0000000000000000 <loop>:
   0:	48 03 06             	add    rax,QWORD PTR [rsi]
   3:	48 13 04 1e          	adc    rax,QWORD PTR [rsi+rbx*1]
   7:	48 0f a4 c9 01       	shld   rcx,rcx,0x1
   c:	48 0f a4 d1 02       	shld   rcx,rdx,0x2
  11:	49 ff cf             	dec    r15
  14:	75 ea                	jne    0 <loop>

Другой полезный инструмент — Quick C++ Benchmark — быстрый бенчмарк кода С++. Сюда копируем фрагмент исходного кода на C++, выбираем компилятор и параметры и смотрим, что получается на разных опциях. Тут можно убедиться, что самые медленные фрагменты в программе — операции с памятью.

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

В научной статье от 2019 года Мэтт Годбольт приводит примеры базовых оптимизаций, которые выполняет компилятор.

По его словам, многие оптимизации относятся к разряду упрощения выражений, когда мы берём более дорогие операции и преобразуем их в менее дорогие. Простейший пример — цикл с умножением и счётчиком:

for (int i = 0; i < 100; ++i)
{
    func(i * 1234);
}

Даже на современных CPU умножение гораздо медленнее, чем сложение, поэтому компилятор переписывает этот код следующим образом:

for (int iTimes1234 = 0; iTimes1234 < 100 * 1234; i += 1234)
{
    func(iTimes1234);
}

Самая дорогая арифметическая операция — деление, которое обычно в 20–50 раз дороже сложения и 5–10 раз дороже умножения. Поэтому компилятор старается по возможности убрать деление. Например, заменить его сдвигом с умножением.

Пример:

unsigned divideByThree(unsigned x)
{
    return x / 3;
}

Результат оптимизации:

divideByThree(unsigned int):
  mov eax, edi          ; eax = edi
  mov edi, 2863311531   ; edi = 0xaaaaaaab
  imul rax, rdi         ; rax = rax * 0xaaaaaaab
  shr rax, 33           ; rax >>= 33
  ret

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

Другие ключевые оптимизации:

Инлайнинг. Компилятор заменяет вызов функции её телом. Это устраняет накладные расходы на вызов и часто открывает возможности для дальнейшей оптимизации, поскольку компилятор может оптимизировать объединённый код как единое целое.

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

Распространение констант. Компилятор отслеживает происхождение значений и устанавливает, что определённые значения остаются постоянными для всех возможных исполнений.

Устранение общих подвыражений. Дублирующие вычисления переписываются так, чтобы вычисление выполнялось один раз, а результат дублировался.

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

Выбор инструкций. Это не оптимизация как таковая, но поскольку компилятор использует внутреннее представление программы и генерирует инструкции процессора, у него есть выбор эквивалентных последовательностей инструкций для конкретной архитектуры CPU.

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

Оптимизация по принципу peephole. Компилятор берёт короткие последовательности инструкций и ищет локальные оптимизации между ними.

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

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

Научная статья Мэтта Годбольта с примерами базовых оптимизаций опубликована 12 ноября 2019 года в журнале ACM Queue (doi: 10.1145/3371595.3372264). Большинство примеров в статье на C или C++, но актуальны для многих других компилируемых языков, а в эпоху популярности LLVM большинство этих оптимизаций работают аналогичным образом даже для таких языков, как Rust, Swift и D.

Весь код проекта Compiler Explorer открыт в репозитории на GitHub, также как конфигурация AWS-инфраструктуры для работы публичных инстансов и сборки более 400 компиляторов. Всего поддерживается 1500 комбинаций компиляторов/языков программирования и сотни дополнительных библиотек общим весом около 2 ТБ, так что облачная установка сайта довольно тяжеловесная.

Автор всегда рад пул-реквестам и спонсорам, обсуждение проекта ведётся в группе в Дискорде.

Sharplab.io

Некоторые разработчики предпочитают альтернативный инструмент Sharplab.io, который специализируется на C# и конкретно для него работает более шустро, чем Compiler Explorer.

Кроме C#, он поддерживает ещё три языка: Visual Basic, F# и IL (Intermediate Language), так называемый «высокоуровневый ассемблер» или «промежуточный язык» виртуальной машины .NET. Все компиляторы на платформе .NET должны транслировать код с языков высокого уровня на IL.

Дефолтный пример.

Код на C#:

using System;
public class C {
    public void M() {
    }
}

Трансляция этого кода в JIT Asm:

; Core CLR 6.0.922.41905 on x86

C..ctor()
    L0000: push ebp
    L0001: mov ebp, esp
    L0003: push eax
    L0004: mov [ebp-4], ecx
    L0007: cmp dword ptr [0x1a51c190], 0
    L000e: je short L0015
    L0010: call 0x71cc5060
    L0015: mov ecx, [ebp-4]
    L0018: call System.Object..ctor()
    L001d: nop
    L001e: nop
    L001f: mov esp, ebp
    L0021: pop ebp
    L0022: ret

C.M()
    L0000: push ebp
    L0001: mov ebp, esp
    L0003: push eax
    L0004: mov [ebp-4], ecx
    L0007: cmp dword ptr [0x1a51c190], 0
    L000e: je short L0015
    L0010: call 0x71cc5060
    L0015: nop
    L0016: nop
    L0017: mov esp, ebp
    L0019: pop ebp
    L001a: ret

Трансляция в IL:

.assembly _
{
    .custom instance void [System.Runtime]System.Runtime.CompilerServices.CompilationRelaxationsAttribute::.ctor(int32) = (
        01 00 08 00 00 00 00 00
    )
    .custom instance void [System.Runtime]System.Runtime.CompilerServices.RuntimeCompatibilityAttribute::.ctor() = (
        01 00 01 00 54 02 16 57 72 61 70 4e 6f 6e 45 78
        63 65 70 74 69 6f 6e 54 68 72 6f 77 73 01
    )
    .custom instance void [System.Runtime]System.Diagnostics.DebuggableAttribute::.ctor(valuetype [System.Runtime]System.Diagnostics.DebuggableAttribute/DebuggingModes) = (
        01 00 07 01 00 00 00 00
    )
    .permissionset reqmin = (
        2e 01 80 8a 53 79 73 74 65 6d 2e 53 65 63 75 72
        69 74 79 2e 50 65 72 6d 69 73 73 69 6f 6e 73 2e
        53 65 63 75 72 69 74 79 50 65 72 6d 69 73 73 69
        6f 6e 41 74 74 72 69 62 75 74 65 2c 20 53 79 73
        74 65 6d 2e 52 75 6e 74 69 6d 65 2c 20 56 65 72
        73 69 6f 6e 3d 36 2e 30 2e 30 2e 30 2c 20 43 75
        6c 74 75 72 65 3d 6e 65 75 74 72 61 6c 2c 20 50
        75 62 6c 69 63 4b 65 79 54 6f 6b 65 6e 3d 62 30
        33 66 35 66 37 66 31 31 64 35 30 61 33 61 15 01
        54 02 10 53 6b 69 70 56 65 72 69 66 69 63 61 74
        69 6f 6e 01
    )
    .hash algorithm 0x00008004 // SHA1
    .ver 0:0:0:0
}

.class private auto ansi '<Module>'
{
} // end of class <Module>

.class public auto ansi beforefieldinit C
    extends [System.Runtime]System.Object
{
    // Methods
    .method public hidebysig 
        instance void M () cil managed 
    {
        // Method begins at RVA 0x2050
        // Code size 2 (0x2)
        .maxstack 8

        IL_0000: nop
        IL_0001: ret
    } // end of method C::M

    .method public hidebysig specialname rtspecialname 
        instance void .ctor () cil managed 
    {
        // Method begins at RVA 0x2053
        // Code size 8 (0x8)
        .maxstack 8

        IL_0000: ldarg.0
        IL_0001: call instance void [System.Runtime]System.Object::.ctor()
        IL_0006: nop
        IL_0007: ret
    } // end of method C::.ctor

} // end of class C

В целом, для C++ самым полезным бенчмарком оценки производительности кода кажется Quick C++ Benchmark, в то время как классический Compiler Explorer (godbolt.org) — это более универсальный и академический инструмент, поддерживающий десятки языков. Он позволяет сравнить, как разные компиляторы по-своему интерпретируют один и тот же код.

Современные компиляторы — сложные интеллектуальные машины, которые становятся всё сложнее и умнее. Они делают огромную работу по оптимизации. Для межпроцедурной оптимизации (WPO и LTO) крайне важно предоставить компилятору максимум информации, включая максимальный объём кода, все модули приложения. Конечно, включение интеллектуальных режимов ведёт к замедлению компиляции. Зато на выходе мы получаем маленькие и быстрые бинарники.

Telegram-канал с полезностями и уютный чат

Всем доброго! Вот мы и добрались до тематики С++ на наших курсах и по нашей старой доброй традиции делимся тем, что мы нашли достаточно интересным при подготовке программы и то, что будем затрагивать во время обучения.

Инфографика:

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

Итак, вот она — инфографика, которая должна помочь оценить стоимость конкретных операций в тактах ЦП — и ответить на такие вопросы, как “эй, сколько обычно стоит операция чтения L2?”. Хотя ответы на все эти вопросы более или менее известны, я не знаю ни одного места, где все они перечислены и представлены в перспективе. Также отметим, что, хотя перечисленные стоимости, строго говоря, применяются только к современным процессорам x86/x64, ожидается, что аналогичное отношение стоимостей будут наблюдаться на других современных процессорах с большими многоуровневыми кэшами (такими как ARM Cortex A или SPARC); с другой стороны, MCU (включая ARM Cortex M) достаточно отличны, чтобы некоторые из закономерностей могли быть к ним не применимы.

И последнее, но не менее важное, предостережение: все оценки здесь лишь указывают на порядок; однако, учитывая масштаб различий между различными операциями, эти показания могут по-прежнему использоваться (по крайней мере, следует помнить, что нужно избегать «преждевременной пессимизации»).

С другой стороны, я все еще уверен, что такая диаграмма полезна, чтобы не говорить «эй, вызовы виртуальных функций ничего не стоят» — что может быть или не быть истинным в зависимости от того, как часто вы их вызываете. Вместо этого, используя инфографику выше, вы сможете увидеть, что если вы вызовете свою виртуальную функцию 100K раз в секунду на процессоре с частотой 3 ГГц — это, вероятно, не будет стоить вам более 0,2% от общего объема вашего процессора; однако, если вы вызываете одну и ту же виртуальную функцию 10M раз в секунду, это легко может означать, что виртуализация поглощает двузначные проценты ядра вашего процессора.

Другой способ приблизиться к тому же вопросу — сказать «эй, я вызываю виртуальную функцию один раз за кусок кода, который составляет 10000 тактов, поэтому виртуализация не будет потреблять более 1% от времени программы», — но вам все равно нужен какой-то способ увидеть порядок величины связанных затрат — и приведенная выше диаграмма по-прежнему будет полезна.

Теперь давайте более подробно рассмотрим пункты в нашей инфографике выше.

Операции ALU и FPU

Для наших целей, говоря об операциях ALU, мы будем рассматривать только операции типа регистр-регистр. Если задействована память, затраты могут быть ОЧЕНЬ разными — это будет зависеть от того, “насколько велик был промах кэша” при доступе к памяти, как описано ниже.

“Простые” операции

В наши дни (и на современных процессорах), «простые» операции, такие как ADD/MOV/OR/…, могут легко выполняться быстрее одного такта ЦП. Это не означает, что операция будет выполняться буквально в течение половины такта. Напротив — в то время, как все операции все еще выполняются за целое число тактов, некоторые из них могут выполняться параллельно.

В [Agner4] (который, кстати, ИМХО является лучшим справочным руководством по оценке операций процессора) эта особенность отражается в наличии двух величин характеризующих каждую операцию: одна — это задержка (которая всегда представлена целым числом тактов), а другая — производительность. Следует отметить, однако, что в реальном мире, когда выходят за рамки оценок порядка, точное время будет сильно зависеть от характера вашей программы и от порядка, в котором компилятор поставил, казалось бы, несвязанные инструкции; вкратце — если вам нужно что-то лучше, чем порядок ожидания, вам нужно профилировать свою конкретную программу, скомпилированную вашим конкретным компилятором (и в идеале — на конкретном целевом процессоре тоже).

Дальнейшее обсуждение таких методов (известных как «внеочередное исполнение»), будучи Действительно Интересным, будет слишком аппаратно-ориентированным (как насчет «именования регистра», которое происходит под капотом процессора, чтобы уменьшить количество зависимостей, которые снижают эффективность работы внеочередного порядка?), и явно не входит в область нашего внимания в настоящий момент.

Целочисленное умножение/деление

Целочисленное умножение/деление достаточно дорогое по сравнению с «простыми» операциями выше. [Agner4] оценивает стоимость 32/64-битного умножения (MUL/IMUL в мире x86/x64) в 1-7 тактов (на практике я наблюдал более узкий диапазон значений, например 3-6 тактов), и стоимость 32/64-разрядного деления (известного как DIV/IDIV на x86/64) — около 12-44 тактов.

Операции с плавающей запятой

Стоимость операций с плавающей запятой взята из [Agner4] и варьируется от 1-3 тактов ЦП для сложения (FADD/FSUB) и 2-5 тактов для умножения (FMUL) до 37-39 тактов для деления (FDIV).

Если использовать скалярные SSE-операции (которыми, по-видимому, пользуется “каждая собака” в наши дни), показатели уменьшаться до 0,5-5 тактов для умножения (MULSS/MULSD) и до 1-40 тактов для деления (DIVSS/DIVSD); на практике, однако, вы должны ожидать скорее 10-40 тактов для деления (1 такт — это «взаимная пропускная способность», что на практике редко реализуется).

128-битные векторные операции

В течении уже нескольких лет ЦП поддерживают «векторные» операции (точнее — операции множественных данных Single Instruction Multiple Data или SIMD); в мире Intel они известны как SSE и AVX и в мире ARM — как ARM Neon. Забавно, что они работают с «векторами» данных, причем данные имеют одинаковый размер (128 бит для SSE2-SSE4, 256 бит для AVX и AVX2 и 512 бит для предстоящего AVX-512), но интерпретировать их можно по-разному. Например, 128-битный регистр SSE2 может быть интерпретирован как (a) два double, (b) четыре float, © два 64-битных integer, (d) четыре 32-битных integer, (e) восемь 16-битных integer, (f) шестнадцать 8-битных integer.

[Agner4] оценивает целочисленное сложение над 128-битным вектором в < 1 такт, если вектор интерпретируется как 4 × 32-битных целых числа и в 4 такта, если это 2 × 64-битных целых числа; умножение (4 × 32 бита) оценивается в 1-5 тактов — и в последний раз, когда я проверял, не было операций целочисленного векторного деления в наборе команд x86/x64. Операций с плавающей запятой над 128-битными векторами оцениваются от 1-3 тактов ЦП для сложения и 1-7 тактов ЦП для умножения, для деления до 17-69 тактов.

Задержки перехода

Не такая очевидная вещь, связанная с затратами на вычисления, заключается в том, что переключение между целыми и плавающими инструкциями не бесплатно. [Agner3] оценивает эту стоимость (известную как «задержка перехода») в 0-3 такта в зависимости от процессора. На самом деле проблема более общая, и (в зависимости от ЦП) также могут быть штрафы за переключение между векторными (SSE) целочисленными инструкциями и обычными (скалярными) целочисленными инструкциями.

Совет по оптимизации: в коде, для которого критична производительность, избегайте комбинирования вычислений с плавающей запятой и целыми числами.

Ветвление

Следующее, что мы будем обсуждать, — это ветвление кода. Переход (if внутри вашей программы), по сути, является сравнением и изменением в счетчике команд. В то время как обе эти вещи просты, ветвление может быть достаточно затратным. Обсуждение, почему это так, опять получится слишком аппаратно-ориентированным (в частности, это затрагивает конвейерную обработку и спекулятивное исполнение), но с точки зрения разработчика программного обеспечения это выглядит так:

• если процессор правильно угадывает, куда будет направлено выполнение (это до фактического вычисления условия if), тогда стоимость перехода составляет около 1-2 тактов ЦП
• однако, если процессор делает неправильное предположение — это приводит к тому, что ЦП «глохнет»

Продолжительность этой задержки оценивается в 10-20 тактов процессора, для последних процессоров Intel — около 15-20 тактов [Agner3].

Отметим, что в то время как макрос GCC __builtin_expect(), как полагают, влияет на предсказание ветвления — и он работал таким образом всего 15 лет назад, он больше не актуален, по крайней мере, для процессоров Intel (начиная с Core 2 или около того).
Как описано в [Agner3], на современных Intel-процессорах предсказание перехода всегда динамично (или, по крайней мере, доминируют динамические решения); это, в свою очередь, подразумевает, что ожидаемые отклонения от кода __builtin_expect() не будут влиять на предсказание переходов (на современных процессорах Intel). Однако __builtin_expect() все еще влияет на способ генерации кода, как описано в разделе «Доступ к памяти» ниже.

Доступ к памяти

В 80-е годы скорость процессора была сопоставима с задержкой памяти (например, процессор Z80, работающий на частоте 4 МГц, тратил 4 такта на команду типа регистр-регистр и 6 тактов на команду типа регистр-память). В то время можно было вычислить скорость программы, просто посмотрев на сборку.

С тех пор скорости процессоров выросли на 3 порядка, а задержки памяти улучшились только в 10-30 раз или около того. Чтобы справиться с оставшимся более чем тридцати кратным несоответствием, были введены все эти виды кэшей. Современный процессор обычно имеет 3 уровня кэшей. В результате скорость доступа к памяти очень сильно зависит от ответа на вопрос «где хранятся данные, которые мы пытаемся прочитать?». Чем ниже уровень кэша, где был найден ваш запрос, тем быстрее вы можете его получить.

Время доступа к кэшу L1 и L2 можно найти в официальных документациях, таких как [Intel.Skylake]; он оценивает время доступа к L1 / L2 / L3 в 4/12/44 такта процессора соответственно (обратите внимание: эти цифры немного варьируются от одной модели процессора к другой). Вообще, как упоминается в [Levinthal], время доступа к L3 может достигать 75 тактов, если кэш совместно используется с другим ядром.

Однако, что сложнее найти, так это информацию о времени доступа к основной ОЗУ. [Levinthal] оценивает его в 60нс (~ 180 тактов, если процессор работает на частоте 3ГГц).

Совет по оптимизации: улучшайте локальность данных. Подробнее об этом см., например, [NoBugs].

Помимо чтения из памяти, есть также запись. В то время как запись интуитивно воспринимается как более дорогая, чем чтение, чаще всего это не так; причина для этого проста: процессору не нужно ждать завершения записи перед тем, как идти вперед (вместо этого он только начинает писать — и сразу переходит к другим делам). Это означает, что большую часть времени процессор может выполнять запись в 1 такт; это согласуется с моим опытом и, по-видимому, достаточно хорошо коррелирует с [Agner4]. С другой стороны, если ваша система завязана на пропускной способности памяти, цифры могут получиться ЧРЕЗВЫЧАЙНО высокие; все же, из того, что я видел, перегрузка шины операциями записи является очень редким явлением, поэтому я не отразил его на диаграмме.

Еще помимо данных, есть и код.

Еще один совет по оптимизации: постарайтесь улучшить также и локальность кода. Это менее очевидно (и, как правило, оказывает меньшее влияние на производительность, чем плохая локализация данных). Обсуждение способов улучшения локальности кода можно найти в [Drepper]; эти способы включают такие вещи, как inlining, и __builtin_expect().

Следует отметить, что хотя __builtin_expect(), как упоминалось выше, больше не влияет на предсказание переходов на процессорах Intel, она все равно влияет на разметку кода, что, в свою очередь, влияет на пространственную локальность кода. В результате __builtin_expect() не имеет эффектов, которые слишком выражены на современных процессорах Intel (на ARM — понятия не имею, если быть честным), но все равно может повлиять на производительность в той или иной степени. Также сообщалось, что под MSVC замена if и else переходов условного оператора имеет эффекты, сходные с __builtin_expect() (если предполагаемый переход является if-переходом условного оператора с двумя переходами), но к этому следует относится с сомнением.

NUMA (Архитектура с неравномерной памятью)

Еще одна вещь, связанная с доступом к памяти и производительностью, редко наблюдается на настольных компьютерах (так как для этого требуются многопроцессорные машины — не следует путать с многоядерными). Таким образом, это, в основном, серверная парафия; однако это существенно влияет на время доступа к памяти.

Когда задействованы несколько сокетов, современные процессоры имеют тенденцию реализовывать так называемую архитектуру NUMA, причем каждый процессор (где «процессор» = «эта штука, вставленная в сокет») имеет свою собственную ОЗУ (в отличие от архитектуры FSB более раннего возраста с общей FSB aka Front-Side Bus и общая оперативная память). Несмотря на то, что каждый процессор имеет собственную ОЗУ, ЦП совместно используют адресное пространство ОЗУ — и всякий раз, когда требуется доступ к ОЗУ, физически находящемуся в другом, это делается путем отправки запроса на другой сокет через сверхбыстрый протокол, такой как QPI или Hypertransport.

Удивительно, но это не так долго, как вы могли бы ожидать — [Levinthal] дает 100-300 тактов ЦП, если данные были в кэше L3 удаленного процессора и 100нс (~ = 300 тактов), если данные были не там, и удаленный процессор должен был перейти в свою основную ОЗУ для этих данных.

CAS (сравнение с обменом)

Иногда (в частности, в неблокирующих алгоритмах и при реализации мьютексов) мы хотим использовать так называемые атомарные операции. Академически обычно рассматривается только одна атомарная операция, известная как CAS (Compare-And-Swap — сравнение с обменом) (на том основании, что все остальное может быть реализовано через CAS); в реальном мире их обычно больше (см., например, std::atomic в C++ 11, Interlocked*() в Windows или __sync _*_ и _*() в GCC/Linux). Эти операции — довольно странные звери: в частности, им нужна специальная поддержка ЦП для правильной работы. В x86 / x64 соответствующие инструкции ASM характеризуются наличием префикса LOCK, поэтому CAS на x86 / x64 обычно записывается как LOCK CMPXCHG.

С нашей нынешней точки зрения важно то, что эти операции, подобные CAS, будут выполняться значительно дольше обычного доступа к памяти (чтобы гарантировать атомарность, процессор должен синхронизировать процессы, по крайней мере, между разными ядрами, или в случае мультисокетных конфигураций, также между различными сокетами).

[AlBahra] оценивает стоимость операций CAS примерно в 15-30 тактов (с небольшой разницей между семействами x86 и IBM Power). Стоит отметить, что это число обоснованно только при выполнении двух допущений: (а) мы работаем с одноядерной конфигурацией и (б), что сравниваемая память уже находится в L1.

Касательно затрат CAS в мультисокетных NUMA-конфигурациях, я не смог найти данные о CAS, поэтому мне пока не обойтись без спекуляций. С одной стороны, ИМХО будет почти невозможным иметь задержки работы CAS на «удаленной» памяти меньше, чем кругооборот HyperTransport между сокетами, что в свою очередь сопоставимо со стоимостью чтения NUMA кэша L3.

С другой стороны, я действительно не вижу причин, чтобы превысить эти показатели :-). В результате я оцениваю стоимость NUMA раздельных CAS (и CAS-подобных) операций в 100-300 тактов ЦП.

TLB (Буфер ассоциативной трансляции)

Всякий раз, когда мы работаем с современными процессорами и современными ОС, на уровне приложений мы обычно имеем дело с «виртуальным» адресным пространством; другими словами, если мы запускаем 10 процессов, каждый из этих процессов может (и, вероятно, будет) иметь свой собственный адрес 0x00000000. Для поддержки такой изоляции процессоры реализуют так называемую «виртуальную память». В мире x86 она была впервые реализована через «защищенный режим», введенный еще в 1982 году на 80286.

Обычно «виртуальная память» работает постранично (для x86 каждая страница имеет размер либо 4K, либо 2M или, по крайней мере, теоретически, даже 1G (!)), когда ЦП знает какой процесс выполняется (!), и переразмечает виртуальные адреса на физические адреса при каждом доступе к памяти. Обратите внимание, что эта повторная разметка происходит полностью за кулисами, в том смысле, что все регистры процессора (кроме тех, которые имеют дело с разметкой) содержат все указатели в формате «виртуальной памяти».

И раз уж мы заговорили о «разметке» — ну, информация об этой разметке должна быть где-то сохранена. Более того, поскольку эта разметка (из виртуальных адресов в физические) происходит при каждом доступе к памяти, это должно быть Чертовски Быстро. Для этого обычно используется специальный вид кэша, называемый Буфер ассоциативной трансляции (TLB).
Так же как и для любого типа кэша, существует стоимость промаха TLB; для x64 она колеблется между 7-21 тактами ЦП [7cpu]. В целом, на TLB довольно сложно повлиять; однако здесь еще можно дать несколько рекомендаций:

• еще раз — улучшение общей локальности памяти помогает уменьшить промахи TLB; чем локальнее ваши данные, тем меньше шансов выйти из TLB.
• рассмотрите возможность использования «больших страниц» (те 2 MБ страницы на x64). Чем больше страницы, тем меньше записей в TLB вам понадобится; с другой стороны, использовать «больший страницы» нужно с осторожностью, это палка о двух концах. Это означает, что вам нужно протестировать его для своего конкретного приложения.
• рассмотрите возможность отключения ASLR (=«рандомизация размещения адресного пространства»). Как обсуждалось в [Drepper], в то время как включение ASLR хорошо для безопасности, оно убивает производительность, и в том числе именно из-за промахов TLB .

Примитивы программного обеспечения

Теперь мы закончили с теми вещами, которые напрямую связаны с “железом”, и будем говорить о некоторых вещах, связанных с программным обеспечением; они действительно все еще повсюду встречаются, поэтому давайте посмотрим, сколько мы тратим каждый раз, когда используем их.

Вызовы функций в С/С++

Сначала давайте рассмотрим стоимость вызова функций в C/C++. На самом деле, то, что вызывает функции в C/C++ делает чертовски много дел перед вызовом, и вызываемое тоже не сидит сложа руки.

[Efficient C++] оценивает затраты ЦП для вызова функции в 25-250 тактов в зависимости от количества параметров; однако, это довольно старая книга, а у меня нет лучшей ссылки того же калибра. С другой стороны, по моему опыту, для функции с достаточно небольшим числом параметров это скорее будет 15-30 тактов; это также, по-видимому, относится к процессорам, отличным от Intel, как выяснил [eruskin].

Совет по оптимизации: используйте inline-функции, где это применимо. Однако имейте в виду, что в наши дни компиляторы чаще всего игнорируют встраиваемые спецификации. Поэтому для действительно критически важных фрагментов кода вы можете использовать __attribute __ ((always_inline)) для GCC и __forceinline для MSVC, чтобы заставить их делать то, что вам нужно. Тем не менее, НЕ используйте эти принудительные inline для не очень критических фрагментов кода, это может сделать намного хуже.

Кстати, во многих случаях выигрыш от встраивания может превышать стоимость простого удаления вызова. Это происходит из-за того, что встраивание обеспечивает довольно много дополнительных оптимизаций (в том числе связанных с переупорядочением для обеспечения правильного использования аппаратного конвейера). Также давайте не будем забывать, что встраивание улучшает пространственную локальность для кода, что также немного помогает (см., например, [Drepper]).

Косвенные и виртуальные вызовы

Дискуссия выше была связана с обычными («прямыми») вызовами функций. Стоимость косвенных и виртуальных вызовов, как известно, выше, и многие согласны с тем, что косвенный вызов вызывает ветвление (однако, как отмечает [Agner1], до тех пор, пока вы вызываете одну и ту же функцию из одной и той же точки кода, механизмы предсказания переходов современных процессоров могут предсказать это довольно хорошо, в противном случае, вы получите штраф за ложное предсказание в 10-30 тактов). Что касается виртуальных вызовов — это одно дополнительное чтение (чтение указателя VMT), поэтому, если в этот момент все кэшируется (как обычно и есть), мы говорим о дополнительных 4 тактах процессора или около того.

С другой стороны, практические измерения [eruskin] показывают, что стоимость виртуальных функций примерно вдвое меньше стоимости прямых вызовов для небольших функций; в пределах нашей погрешности (которая является «порядком») это вполне согласуется с вышеприведенным анализом.

Совет по оптимизации: если ваши виртуальные вызовы стоят дорого, вместо этого в C++ вы можете подумать об использовании шаблонов (реализация так называемого полиморфизма времени компиляции); CRTP — это один (хотя и не единственный) способ сделать это.

Аллокации

В наши дни аллокаторы как таковые могут быть довольно быстрыми; в частности, аллокаторы tcmalloc и ptmalloc2 могут потратить всего 200-500 тактов ЦП для выделения/освобождения небольшого объекта [TCMalloc].

Тем не менее, есть существенное предостережение, связанное с аллокацией, и добавление к косвенным затратам на использование аллокаций: аллокация, как старое доброе правило большого пальца, означает уменьшение локальности памяти, что, в свою очередь, отрицательно влияет на производительность (из-за взаимодействий с незакэшированной памятью, описанных выше). Чтобы проиллюстрировать, насколько это плохо на практике, мы можем взглянуть на 20-строчную программу в [NoBugs]; эта программа при использовании vector<> выполняется от 100 до 780 раз быстрее (в зависимости от компилятора и конкретного поля), чем эквивалентная программа, использующая list<> — все из-за плохой локальности памяти последнего :-(.

Совет по оптимизации: думайте о сокращении количества аллокаций в ваших программах, особенно если есть этап, когда большая часть работы выполняется с данными только для чтения. В некоторых реальных случаях сглаживание ваших структур данных (т.е. замена выделенных объектов упакованными) может ускорить вашу программу до 5 раз.

Реальная история по теме. Когда-то давным-давно была программа, в которой использовались гигабайты оперативной памяти, что считалось слишком большим; окей, я переписал ее в «сплющенную» версию (то есть каждый узел был сначала сконструирован динамически, а затем в памяти был создан эквивалентный «сплющенный» объект только для чтения); идея «сглаживания» заключалась в уменьшении объема памяти. Когда мы запускали программу, мы заметили, что не только объем памяти уменьшился в 2 раза (что и было тем, что мы ожидали), но также, как очень хороший побочный эффект, скорость выполнения увеличилась в 5 раз.

Вызовы ядра ОС

Если наша программа работает под операционной системой (да, есть еще программы, которые работают без нее), то у нас есть целая группа системных API. На практике (по крайней мере, если мы говорим о более или менее обычной ОС) многие из этих системных вызовов приводят к вызовам ядра, которые включают в себя переключения в режим ядра и обратно; это включает в себя переключение между различными «кольцами защиты» (на процессоре Intel обычно между «кольцом 3» и «кольцом 0»). В то время как переключение между уровнями процессора занимает всего около 100 тактов, другие связанные с этим накладные расходы, как правило, делают вызовы ядра намного более дорогими, поэтому обычный вызов ядра занимает не менее 1000-1500 тактов процессора [Wikipedia.ProtectionRing].

Исключения C++

В наши дни про исключения C++ говорят, что они ничего не стоят до тех пор, пока не сработают. Действительно ли ничего — все еще не на 100% ясно (ИМО даже не ясно, может ли вообще задаваться такой вопрос), но он, безусловно, очень близок.

Тем не менее, эти «беззатратные пока не сработавшие» реализации стоят за огромной кучей работы, которая должна выполняться всякий раз, когда возникает исключение. Все согласны с тем, что стоимость брошенного исключения огромна, однако (как обычно) экспериментальных данных мало. Тем не менее, эксперимент [Ongaro] дает нам примерное количество около 5000 тактов процессора (чума!). Более того, в более сложных случаях я бы ожидал, что это число будет еще больше.

Возврат ошибки и проверка

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

В принципе, стоимость возврата-и-проверки состоит из трех отдельных стоимостей. Первая из них — это стоимость самого условного перехода, и мы можем с уверенностью предположить, что в 99+% случаев он будет предсказан правильно; это означает, что стоимость условного перехода в этом случае составляет около 1-2 тактов. Вторая стоимость — это затраты на копирование кода ошибки, и до тех пор, пока он остается в пределах регистров, это простое MOV, которое при данных обстоятельствах составляет от 0 до 1 такта (0 тактов означает, что MOV не имеет дополнительную стоимость, поскольку она выполняется параллельно с некоторыми другими операциями). Третья стоимость гораздо менее очевидна — это стоимость дополнительного регистра, необходимого для переноса кода ошибки; если мы вышли из регистров — нам понадобится пара PUSH/POP (или разумная факсимиле), которая, в свою очередь запись + чтение L1 или 1 + 4 такта. С другой стороны, давайте иметь в виду, что шансы PUSH/POP быть необходимыми, варьируются от одной платформы к другой; например, на x86 любая реалистическая функция потребует их почти наверняка; однако на x64 (у которого есть двойное число регистров) вероятность того, что PUSH/POP будут необходимы, значительно снизится (и в довольно многих случаях, даже если регистр не является полностью свободным, компилятор сделать его доступным дешевле, чем тривиальный PUSH/POP).

Объединив все три стоимости, я бы оценил затраты на возврат-кода-ошибки-и-проверку (в нормальном случае) в пределах от 1 до 7 тактов ЦП. Это, в свою очередь, означает, что если у нас есть одно исключение на 10000 вызовов функций, нам, вероятно, будет лучше с исключениями; однако, если у нас есть одно исключение на 100 вызовов функций, нам, вероятно, будем лучше с кодами ошибок. Другими словами, мы только что подтвердили очень хорошо известную передовую практику — «используйте исключения только для ненормальных ситуаций».

Переключения контекста потока

Последнее, но, конечно, не менее важное, нам нужно поговорить о стоимости переключения контекста потока. Одна из проблем с их оценкой заключается в том, что их очень сложно понять. Общая мудрость говорит, что они «чертовски дороги» (эй, должна же быть причина, почему nginx превосходит Apache), но насколько это «чертовски дорого»?

Из моих личных наблюдений цена составляла не менее 10000 тактов ЦП; однако есть много источников, которые дают НАМНОГО более низкие цифры. Фактически, однако, речь идет о том, «что именно мы пытаемся измерить». Как отмечено в [LiEtAl], существуют две разные стоимости по отношению к переключениям контекста.

• Первая стоимость — прямые затраты на переключение контекста потока, и они измеряются примерно в 2000 тактов ЦП (3 то есть, если моя математика правильна при преобразовании из микросекунд в такты)
• Однако вторая стоимость намного выше; это связано с аннулированием кэша потоком; согласно [LiEtAl], он может быть примерно 3M тактов ЦП. Теоретически, с полностью случайным шаблоном доступа, современный процессор с 12M кэша L3 (и с учетом штрафа порядка 50 тактов за доступ) может вызвать задержку в 10M тактов за контекстный переключатель; однако на практике штрафы обычно несколько ниже, поэтому число 1M от [LiEtAl] имеет смысл. Эта «намного более высокая» оценка также согласуется с количеством спинлоков на x64 (по умолчанию это 4000, по крайней мере для Windows/x64): если обычно полезно ждать 4000 итераций (в сумме, по крайней мере, до 15-20 тыс. тактов ЦП и больше, чем 40-50K тактов, из моего опыта), считывая эту переменную-которая-в-настоящее-время-заблокирована в замкнутом цикле — просто в надежде, что переменная откроется до того, как закончится 4000 итераций, все эти проблемы и такты ЦП просто для того, чтобы избежать переключения контекста — это означает, что стоимость переключения контекста обычно намного выше, чем те десятки-тысяч-процессорных-тактов-которые-мы-готовы-потратить-на-замкнутый-цикл-не-делающий-ничего-полезного.

Подытожим

Фух, было сделано довольно много работы, чтобы найти ссылки на все эти более или менее известные наблюдения.

Также учтите, что, хотя я честно пытался собрать все связанные цены в одном месте (проверяя сторонние выводы на моем собственном опыте в процессе), это всего лишь первая попытка, поэтому, если вы найдете достаточно убедительные доказательство того, что что-то неправильно — сообщите мне, я буду рад сделать диаграмму более точной.

THE END

Как всегда ждём тапков, вопросов в комментариях или на Дне открытых дверей