[Перевод] О языке С и производительности08.12.2016 21:48

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

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

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

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

Вы действительно думаете, что интернет вещей будет разрабатываться на высокоуровневых языках? А будущие видеокодеки? VR-приложения? Сети? Операционные системы? Игры? Автомобильные системы, например автопилоты, системы предупреждения о столкновении? Всё это, как и многие другие продукты, пишется на низкоуровневых языках вроде С или сразу на ассемблере.

Вы можете наблюдать развитие «новых» архитектур, например очень интересных ARM-процессоров, которые стоят в 98% смартфонов. Если сегодня вы используете Java для создания Android-приложений, то лишь потому, что сам Android написан на Java и С++. А язык Java — как и 80% современных высокоуровневых языков — написан на С (или С++).

Язык С пересекается с некоторыми родственными языками. Но они используют императивную парадигму, а потому мало распространены или не столь развиты. Например, Fortran, относящийся к той же «возрастной группе», что и С, в некоторых специфических задачах более производителен. Ряд специализированных языков могут быть быстрее С при решении чисто математических задач. Но всё же С остаётся одним из наиболее популярных, универсальных и эффективных низкоуровневых языков в мире.

Приступим

Для этой статьи я воспользуюсь машиной с процессором X86_64, работающей под управлением Linux. Мы рассмотрим очень простую программу на С, которая суммирует 1 миллиард байтов из файла менее чем за 0,5 секунды. Попробуйте проделать это на любом из высокоуровневых языков — вы и не приблизитесь по производительности к С. Даже на Java, с помощью JIT, с параллельными вычислениями и хорошей моделью использования памяти в пространстве пользователя. Если языки программирования не обращаются напрямую к машинным инструкциям, а являются некой промежуточной формой (определение высокоуровневых языков), то они не сравнятся по производительности с С (даже с помощью JIT). В некоторых областях разрыв можно уменьшить, но в целом С оставляет соперников далеко позади.

Сначала мы подробно разберём задачу с помощью С, затем рассмотрим инструкции X86_64 и оптимизируем программу с помощью SIMD — разновидности инструкций в современных процессорах, позволяющей обрабатывать большие объёмы данных одной инструкцией в несколько циклов (несколько наносекунд).

Простая программа на С
Чтобы продемонстрировать возможности языка, я приведу простой пример: открываем файл, считываем из него все байты, суммируем их, а полученную сумму сжимаем в один байт без знака (unsigned byte) (то есть несколько раз будет переполнение). И всё. Ах да, и всё это мы постараемся выполнить как можно эффективнее — быстрее.

Поехали:

#include 
#include 
#include 
#include 
#include 

#define BUF_SIZE 1024

int main(int argc, char **argv)
{
    int f, i;
    ssize_t readed;

    unsigned char result = 0;
    unsigned char buf[BUF_SIZE] = {0};

    if (argc != 2) {
        fprintf(stderr, "Использование: %s \n", argv[0]);
        exit(-1);
    }

    f = open(argv[1], O_RDONLY);

    if (f == -1) {
        perror("Не могу открыть файл");
    }

    while ((readed = read(f, buf, sizeof(buf))) > 0) {
        for (i=0; i < readed; i++) {
            result += buf[i];
        }
    }

    close(f);

    printf("Чтение завершено, сумма равна %u \n", result);

    return 0;
}

Для нашего примера возьмём файл на 1 Гб. Чтобы создать такой файл со случайными данными, просто воспользуемся dd:

> dd if=/dev/urandom of=/tmp/test count=1 bs=1G iflag=fullblock

Теперь передадим файл в нашу программу (назовём её file_sum) в качестве аргумента:

> file_sum /tmp/file
Read finished, sum is 186

Можно просуммировать байты самыми разными способами. Но для эффективности нужно понимать:

Как работает CPU и что он умеет (какие вычисления может производить).
Как работает ядро ОС (kernel).

Вкратце: необходимы некоторые знания по электронике и низкому уровню ОС, на которых выполняется наша программа.Помните о ядре
Здесь мы не будем углубляться в работу ядра. Но помните, что мы не станем просить процессор взаимодействовать с диском, на котором хранится наш файл. Дело в том, что на дворе 2016 год, и мы создаём так называемые программы пользовательского пространства (ППП). Одно из определений гласит, что такие программы НЕ МОГУТ напрямую обращаться к оборудованию. Когда возникает необходимость воспользоваться оборудованием (обратиться к памяти, диску, сети, картридеру и так далее), программа с помощью системных вызовов просит операционную систему сделать это для неё. Системные вызовы — это функции ОС, доступные для ППП. Мы не будем спрашивать диск, готов ли он обработать наш запрос, просить его переместить головку, считать сектор, перенести данные из кеша в основную память и так далее. Всё это делает ядро ОС вместе с драйверами. Если бы нам нужно было заняться такими низкоуровневыми вещами, то мы писали бы программу «пространства ядра» — по сути, модуль ядра.

Почему так? Почитайте мою статью про распределение памяти. Там объясняется, что ядро управляет одновременным выполнением нескольких программ, не позволяя им обрушить систему или перейти в необратимое состояние. При любых инструкциях. Для этого ядро переводит процессор в режим третьего кольца защиты. А в третьем кольце программа не может обращаться к аппаратно отображаемой памяти (hardware mapped memory). Любые подобные инструкции будут генерировать в процессоре исключения, как и все попытки доступа к памяти за пределами совершенно конкретных границ. На исключение в процессоре ядро отвечает запуском кода исключения (Exception code). Он возвращает процессор в стабильное состояние и завершает нашу программу с помощью какого-то сигнала (возможно, SIGBUS).

Третье кольцо защиты — режим с самыми низкими привилегиями. Все ППП выполняются в этом режиме. Можете его опробовать, считав первые два бита CS-регистра в своём X86-процессоре:

gdb my_file
(gdb) p /t $cs
$1 = 110011

Первые два бита (младшие) обозначают текущий уровень кольца защиты. В данном случае — третий.

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

Вернёмся к нашему коду. Мы не можем управлять производительностью чтения с диска, поскольку за это отвечают ядро, низкоуровневая файловая система и аппаратные драйверы. Мы воспользуемся вызовами open()/read() и close(). Я не стал брать функции из libC (fopen(), fread(), fclose()), в основном потому, что они являются обёртками для системных вызовов. Эти обёртки могут как улучшать, так и ухудшать общую производительность: всё зависит от того, какой код прячется за этими инструкциями и как они используются самой программой. LibC — это прекрасно спроектированная и высокопроизводительная библиотека (ряд её ключевых функций написан на ассемблере), но всем этим функциям «ввода-вывода» нужен буфер, которым вы не управляете, и они по своему усмотрению вызывают read (). А нам надо полностью контролировать программу, так что обратимся напрямую к системным вызовам.

На системный вызов ядро чаще всего отвечает вызовом read() файловой системы, давая аппаратному драйверу команду ввода/вывода. Все эти вызовы можно отследить с помощью Linux-трассировщиков, например perf. Для программ системные вызовы затратны, потому что приводят к переключению контекста — переходу из пользовательского пространства в пространство ядра. Стоит этого избегать, поскольку переходы требуют от ядра значительного объёма работ. Но нам нужны системные вызовы! Самый медленный из них — read(). Когда он делается, процесс наверняка будет выведен из очереди выполнения в CPU и переведён в режим ожидания ввода/вывода. Когда операция завершится, ядро вернёт процесс в очередь выполнения. Эту процедуру можно контролировать с помощью флагов, передаваемых вызову open ().

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

Получше узнайте своё железо и компилятор
Итак, мы знаем, что не в силах целиком управлять производительностью трёх системных вызовов: open(), read() и close(). Но давайте здесь доверимся разработчикам пространства ядра. Кроме того, сегодня многие используют SSD-накопители, так что можно с определённой долей уверенности предположить, что наш одногигабайтный файл считается достаточно быстро.

Что ещё замедляет код?

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

> gcc -Wall -g -O0 -o file_sum file_sum.c

Затем отпрофилируем с помощью команды time:

> time ./file_sum /tmp/big_1Gb_file
Read finished, sum is 186 

real    0m3.191s
user    0m2.924s
sys     0m0.264s

Не забудьте запустить несколько раз, чтобы прогреть кеш страницы ядра. У меня после нескольких прогонов суммирование одного гигабайта с SSD заняло 3,1 секунды. Процессор ноутбука — Intel Core i5–3337U @ 1,80 ГГц, ОС — Linux 3.16.0–4-amd64. Как видите, самая обычная X86_64-архитектура. Для компилирования я использовал GCC 4.9.2.

Согласно данным time, большую часть времени (90%) мы провели в пользовательском пространстве. Время, когда ядро что-то делает от нашего имени, — это время выполнения системных вызовов. В нашем примере: открывание файла, чтение и закрывание. Довольно быстро, верно?

Обратите внимание: размер буфера чтения равен одному килобайту. Это означает, что для одногигабайтного файла приходится вызывать read() 1024×1024 = 1 048 576 раз. А если увеличить буфер, чтобы уменьшить количество вызовов? Возьмём 1 Мб, тогда у нас останется только 1024 вызова. Внесём изменения, перекомпилируем, запустим несколько раз, отпрофилируем:

#define BUF_SIZE 1024*1024
.
> gcc -Wall -g -O0 -o file_sum file_sum.c
> time ./file_sum /tmp/big_1Gb_file
Read finished, sum is 186 

real    0m3.340s
user    0m3.156s
sys     0m0.180s

Отлично, удалось снизить с 264 до 180 мс. Но не увлекайтесь увеличением кеша: у скорости read() есть определённый предел, а буфер находится в стеке. Не забывайте, что максимальный размер стека в современных Linux-системах по умолчанию 8 Мб (можно изменять).

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

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

Язык С — ничто без компилятора. Это лишь приемлемый для человека язык программирования компьютера. А чтобы преобразовать С-код в низкоуровневые машинные инструкции, требуется компилятор. Сегодня мы по большей части используем С для создания систем и решения низкоуровневых задач, потому что хотим иметь возможность без переписывания портировать код с одной процессорной архитектуры на другую. Именно поэтому в 1972 году был разработан С.

Так вот, без компилятора язык С — пустое место. Плохой компилятор или его неверное использование может привести к низкой производительности. То же самое справедливо и для других языков, компилируемых в машинный код, например для Fortran«а.

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

Ассемблер несложно освоить. Всё зависит от архитектуры, и здесь мы рассмотрим только наиболее распространённый вариант с X86 (для 2016 года — X86_64).

В архитектуре X86_64 также нет ничего сложного. Просто в ней ОГРОМНОЕ количество инструкций. Когда я делал первые шаги в ассемблере (под Freescale 68HC11), то использовал несколько десятков инструкций. А в X86_64 их уже тысячи. Мануалы в то время были такими же, как сегодня: непонятными и многословными. А поскольку PDF тогда не было, то приходилось таскать с собой огромные книги.

Вот, к примеру, мануалы Intel по X86_64. Тысячи страниц. Это первичный источник знаний для разработчиков ядра и самых низкоуровневых разработчиков. А вы думали, что можно было бы улучшить ваши онлайн-мануалы по PHP?

К счастью, для нашей маленькой программы нет нужды читать все эти цифровые фолианты. Здесь применяется правило 80/20 — 80% программы будет сделано с помощью 20% общего количества инструкций.

Вот С-код и дизассемблированная часть, которая нас интересует (начиная с цикла while ()), скомпилированная без оптимизаций с помощью GCC 4.9.2:

#define BUF_SIZE 1024

int main(int argc, char **argv)
{
    int f, i;
    ssize_t readed;

    unsigned char result = 0;
    unsigned char buf[BUF_SIZE] = {0};

    if (argc != 2) {
        fprintf(stderr, "Использование: %s \n", argv[0]);
        exit(-1);
    }

    f = open(argv[1], O_RDONLY);

    if (f == -1) {
        perror("Не могу открыть файл");
    }

    while ((readed = read(f, buf, sizeof(buf))) > 0) {
        for (i=0; i < readed; i++) {
            result += buf[i];
        }
    }

    close(f);

    printf("Чтение закончено, сумма равна %u \n", result);

    return 0;
}

00400afc:   jmp 0x400b26 < main+198>
00400afe:   movl $0x0,-0x4(%rbp)
00400b05:   jmp 0x400b1b < main+187>
00400b07:   mov -0x4(%rbp),%eax
00400b0a:   cltq 
00400b0c:   movzbl -0x420(%rbp,%rax,1),%eax
00400b14:   add %al,-0x5(%rbp)
00400b17:   addl $0x1,-0x4(%rbp)
00400b1b:   mov -0x4(%rbp),%eax
00400b1e:   cltq 
00400b20:   cmp -0x18(%rbp),%rax
00400b24:   jl 0x400b07 < main+167>
00400b26:   lea -0x420(%rbp),%rcx
00400b2d:   mov -0xc(%rbp),%eax
00400b30:   mov $0x400,%edx
00400b35:   mov %rcx,%rsi
00400b38:   mov %eax,%edi
00400b3a:   callq 0x4005d0 < read@plt>
00400b3f:   mov %rax,-0x18(%rbp)
00400b43:   cmpq $0x0,-0x18(%rbp)
00400b48:   jg 0x400afe < main+158>
00400b4a:   mov -0xc(%rbp),%eax
00400b4d:   mov %eax,%edi
00400b4f:   callq 0x4005c0 < close@plt>

Видите, насколько неэффективный код? Если нет, то позвольте мне кратко рассказать вам об ассемблере под X86_64 с комментариями к вышеприведённому дампу.

Основы ассемблера под X86_64

Здесь мы пробежимся по верхам, а за подробностями обратитесь к материалам один, два и три.

Мы будем оперировать байтами и степенями 2 и 16.

Каждая инструкция хранится в памяти по определённому адресу, указанному в левой колонке.
Каждая инструкция уникальна и имеет имя (мнемоническое): LEA — MOV — JMP и так далее. В современной архитектуре X86_64 существует несколько тысяч инструкций.
X86_64 — это CISC-архитектура. Одна инструкция может преобразовываться в конвейере в несколько более низкоуровневых инструкций, для выполнения каждой из которых иногда требуется несколько процессорных циклов (clock cycles) (1 инструкция != 1 цикл).
Каждая инструкция может принимать максимум 0, 1, 2 или 3 операнда. Чаще всего 1 или 2.
Существует две основные модели ассемблера: AT&T (также называется GAS) и Intel.
- В AT&T вы читаете INSTR SRC DEST.
- В Intel вы читаете INSTR DEST SRC.
- Есть и ряд других отличий. Если ваш мозг натренирован, то можно без особого труда переключаться с одной модели на другую. Это всего лишь синтаксис, ничего более.
- Чаще используется AT&T, кто-то предпочитает Intel. Применительно к X86 в модели AT&T по умолчанию используется GDB. Подробнее о модели AT&T.
В X86_64 применяется порядок следования байтов от младшего к старшему (little-endian), так что готовьтесь преобразовывать адреса по мере чтения. Всегда группируйте побайтно.
В X86_64 не разрешены операции «память-память». Для обработки данных нужно использовать какой-нибудь регистр.
$ означает статичное непосредственное значение (например, $1 — это значение '1').
% означает доступ к регистру (%eax — доступ к регистру EAX).
Круглые скобки — доступ к памяти, звёздочка в С разыменовывает указатель (запись (%eax) означает доступ к области памяти, адрес которой хранится в регистре EAX).

Регистры

Регистры — это области памяти фиксированного размера в чипе процессора. Это не оперативная память! Регистры работают гораздо быстрее RAM. Если доступ к оперативке выполняется примерно за 100 нс (в обход всех уровней кеша), то доступ к регистру — за 0 нс. Самое главное в программировании процессора — это понимать сценарий, который повторяется раз за разом:

Из оперативной памяти в регистр грузятся данные: теперь процессор «обладает» значением.
С регистром выполняется что-нибудь (например, его значение умножается на 3).
Содержимое регистра отправляется обратно в оперативную память.
Если хотите, то можно перемещать данные из регистра в другой регистр того же размера.

Напоминаю, что в X86_64 нельзя выполнять обращения «память-память»: сначала нужно передать данные в регистр.

Существуют десятки регистров. Чаще всего используются регистры «общего назначения» — для вычислений. В архитектуре X86_64 доступны следующие «универсальные» регистры: a, b, c, d, di, si, 8, 9, 10, 11, 12, 13, 14 и 15 (в 32-битной X86 набор другой).

Все они 64-битные (8 байтов), НО к ним можно обращаться в четырёх режимах: 64-, 32-, 16- и 8-битном. Всё зависит от ваших потребностей.

Регистр A — 64-битный доступ. RAX — 32-битный. EAX — 16-битный. AX — 8-битный. Младшая часть: AL, старшая часть: AH.

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

Один байт = 8 битов, это наименьшее доступное количество информации. Обозначается как BYTE.
Двойной байт = 16 битов, обозначается как WORD.
Двойной двойной байт = 32 бита, обозначается как DWORD (двойной WORD).
8 смежных байтов = 64 бита, обозначается как QWORD (четверной WORD).
16 смежных байтов = 128 битов, обозначается как DQWORD (двойной четверной WORD).

Больше информации об архитектуре X86 можно найти на http://sandpile.org/ и сайтах Intel/AMD/Microsoft. Напоминаю: X86_64 работает несколько иначе, чем X86 (32-битный режим). Также почитайте выборочные материалы из манулов Intel.

Анализ кода X86_64

00400afc:   jmp 0x400b26

JMP — это безусловный переход (unconditional jump). Перейдём по адресу 0×400b26:

00400b26:   lea -0x420(%rbp),%rcx
00400b2d:   mov -0xc(%rbp),%eax
00400b30:   mov $0x400,%edx
00400b35:   mov %rcx,%rsi
00400b38:   mov %eax,%edi
00400b3a:   callq 0x4005d0 < read@plt>

В этом коде делается системный вызов read(). Если вы почитаете конвенцию вызовов в X86_64, то увидите, что большинство параметров передаются не стеком, а регистрами. Это повышает производительность вызова каждой функции в X86_64 Linux по сравнению с 32-битным режимом, когда для каждого вызова используется стек.

Согласно таблице системных вызовов ядра, в read(int fd, char *buf, size_t buf_size) первый параметр (дескриптор файла) должен быть передан в RDI, второй (буфер для заполнения) — в RSI, а третий (размер буфера для заполнения) — в RDX.

Рассмотрим вышеприведённый код. Здесь используется RPB (Register Base Pointer, указатель базового регистра). RBP запоминает самое начала пространства текущего стека, в то время как RSP (Register Stack Pointer, указатель стека регистра) запоминает вершину текущего стека, на случай, если нам понадобится с этим стеком что-то сделать. Стек — это просто большой кусок памяти, выделенный для нас. Он содержит локальные переменные функции, переменные alloca(), адрес возврата, может содержать аргументы функций, если их несколько штук.

В стеке хранятся локальные переменные функции main(), в которой мы сейчас находимся:

00400b26:   lea -0x420(%rbp),%rcx

LEA (Load Effective Address) хранится в RBP минус 0×420, вплоть до RCX. Это наша переменная буфера — buf. Обратите внимание, что LEA не считывает значение после адреса, только сам адрес. Под GDB вы можете напечатать любое значение и произвести вычисления:

> (gdb) p $rbp - 0x420
$2 = (void *) 0x7fffffffddc0

С помощью info registers можно отобразить любой регистр:

> (gdb) info registers
rax            0x400a60 4196960
rbx            0x0      0
rcx            0x0      0
rdx            0x7fffffffe2e0   140737488347872
rsi            0x7fffffffe2c8   140737488347848
... ...

Продолжаем:

00400b2d:   mov -0xc(%rbp),%eax

Поместим значение по адресу, указанному в RBP минус 0xc — в EAX. Скорее всего, это наша переменная f . Это можно легко подтвердить:

> (gdb) p $rbp - 0xc
$1 = (void *) 0x7fffffffe854
> (gdb) p &f
$3 = (int *) 0x7fffffffe854

Идём дальше:

00400b30:   mov $0x400,%edx

Поместим в EDX значение 0×400 (1024 в десятичном выражении). Это sizeof(buf): 1024, третий параметр read().

00400b35:   mov %rcx,%rsi
00400b38:   mov %eax,%edi
00400b3a:   callq 0x4005d0 < read@plt>

Запишем содержимое RCX в RSI, второй параметр read(). Запишем содержимое EAX в EDI, третий параметр read(). Затем вызовем функцию read().

При каждом системном вызове его значение возвращается в регистр A (иногда ещё и в D). read() возвращает значение ssize_t, которое весит 64 бита. Следовательно, для чтения возвращаемого значения нам нужно проанализировать весь регистр A. Для этого воспользуемся RAX (64-битное чтение регистра A):

00400b3f:   mov %rax,-0x18(%rbp)
00400b43:   cmpq $0x0,-0x18(%rbp)
00400b48:   jg 0x400afe < main+158>

Запишем возвращаемое значение read() из RAX по адресу, указанному в RBP минус 0×18. Быстрая проверка подтверждает, что это наша переменная readed из С-кода.

CMPQ (Compare Quad-Word, сравнение четверного WORD). Сравниваем значение readed со значением 0.

JG (Jump if greater, переход по условию «больше»). Переходим по адресу 0×400AFE. Это всего лишь сравнение в цикле while() из нашего С-кода.

Продолжаем читать буфер и переходим по адресу 0×400AFE, это должно быть начало цикла for().

00400afe:   movl $0x0,-0x4(%rbp)
00400b05:   jmp 0x400b1b < main+187>

MOVL (Move a Long, копирование длинного целого). Записываем LONG (32 бита) значения 0 по адресу, указанному в RBP минус 4. Это i — целочисленная переменная в C-коде, 32 бита, то есть 4 байта. Потом она будет сохранена как самая первая переменная в стековом фрейме main() (представленном RBP).

Переходим по адресу 0×400B1B, здесь должно быть продолжение цикла for().

00400b1b:   mov -0x4(%rbp),%eax
00400b1e:   cltq 
00400b20:   cmp -0x18(%rbp),%rax
00400b24:   jl 0x400b07

Записываем в EAX значение, указанное в RBP минус 4 (вероятно, целое число).

CLTQ (Convert Long To Quad). CLTQ работает с регистром A. Он расширяет EAX до 64-битного целочисленного значения, получаемого RAX.

CMP (Compare value, сравнение значения). Сравниваем значение в RAX со значением, на которое указывается по адресу в RBP минус 0×18. То есть сравниваем переменную i из цикла for() с переменной readed.

JL (Jump if Lower, переход по условию «меньше»). Переходим по адресу 0×400B07. Мы на первом этапе цикла for(), так что да, переходим.

00400b07:   mov -0x4(%rbp),%eax
00400b0a:   cltq 
00400b0c:   movzbl -0x420(%rbp,%rax,1),%eax
00400b14:   add %al,-0x5(%rbp)
00400b17:   addl $0x1,-0x4(%rbp)
00400b1b:   mov -0x4(%rbp),%eax
00400b1e:   cltq 
00400b20:   cmp -0x18(%rbp),%rax
00400b24:   jl 0x400b07 < main+167>

А теперь самое интересное.

Записываем (MOV) i в EAX (как говорилось выше, i — это –0×4(%rbp)). Затем делаем CLTQ: расширяем до 64 бит.

MOVZBL (MOV Zero-extend Byte to Long). Добавляем нулевой байт к длинному целому, хранящемуся по адресу (1*RAX+RBP) минус 0×420, и записываем в EAX. Звучит сложно, но это просто математика ;-) Выходит вычисление buf[i] с помощью одной инструкции. Так мы проиллюстрировали возможности указателей в языке C: buf[i] — это buf + i*sizeof(buf[0]) байтов. Получившийся адрес легко вычисляется на ассемблере, а компиляторы выполняют кучу математических вычислений, чтобы сгенерировать такую инструкцию.

Загрузив значение в EAX, мы добавляем его в result:

00400b14:   add %al,-0x5(%rbp)

Помните: AL — младший байт 8-байтного RAX (RAX и AL представляют собой регистр A) — это buf[i], поскольку buf относится к типу char и весит один байт. result находится по адресу –0×5(%rbp): один байт после i, расположенного на расстоянии 0×4 от RBP. Это подтверждает, что result — это char, весящий один байт.

00400b17:   addl $0x1,-0x4(%rbp)

ADDL (Add a long, добавление длинного целого — 32 бита). Добавляем 1 к i

И снова возвращаемся к инструкции 00400b1b: циклу for().

Краткий итог

Устали? Это потому, что у вас нет опыта в ассемблере. Как вы могли убедиться, расшифровка ассемблера — это всего лишь арифметика на уровне начальной школы: сложить, извлечь, умножить, разделить. Да, ассемблер прост, но очень многословен. Чувствуете разницу между «труден» и «многословен»?

Если вы хотите, чтобы ваш ребёнок стал хорошим программистом, то не делайте ошибки и не ограничивайте его изучением математики только с основанием 10. Тренируйте его переключаться с одного основания на другое. Фундаментальную алгебру можно полностью понять только тогда, когда вы можете представить любые величины с любым основанием, особенно 2, 8 и 16. Для обучения детей рекомендую использовать соробан.

Если вы чувствуете себя в математике не слишком уверенно, то лишь потому, что ваш мозг всегда натаскивали только на операции с основанием 10. Переключаться с 10 на 2 трудно, потому что эти степени не кратны. А переключаться между 2 и 16 или 8 легко. Потренировавшись, вы сможете вычислять большинство адресов в уме.

Итак, нашему циклу for() нужно шесть адресов памяти. Он был преобразован как есть из исходного C-кода: цикл выполняется для каждого байта с побайтным суммированием. Для одногигабайтного файла цикл приходится выполнять 0×40000000 раз, то есть 1 073 741 824.

Даже на 2 ГГц (в CISC одна инструкция != один цикл) прогон цикла 1 073 741 824 раза отнимает достаточно времени. В результате код выполняется около 3 секунд, потому что побайтное суммирование в считанном файле крайне неэффективно.

Давайте всё векторизуем с помощью SIMD
SIMD — Single Instruction Multiple Data, одна инструкция, множественный поток данных. Этим всё сказано. SIMD представляет собой специальные инструкции, позволяющие процессору работать не с одним байтом, одним WORD, одним DWORD, а с несколькими из них в рамках одной инструкции.

Встречайте SSE — Streaming SIMD Extensions, потоковое SIMD-расширение. Вам наверняка знакомы такие аббревиатуры, как SSE, SSE2, SSE4, SSE4.2, MMX или 3DNow. Так вот, SSE — это SIMD-инструкции. Если процессор может единовременно работать с многочисленными данными, то это существенно уменьшает общую продолжительность вычислений.

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

SIMD-инструкции позволяют очень сильно ускорять вычисления в процессоре. Они используются везде, где допускается параллельная обработка информации. Некоторые из сфер применения:

Матричные вычисления, лежащие в основе графики (но GPU делает это на порядок быстрее).
Сжатие данных, когда за раз обрабатывается по несколько байтов (форматы LZ, GZ, MP3, Divx, H264/5, JPEG FFT и многие другие).
Криптография.
Распознавание речи и музыки.

Возьмём, к примеру, оценку параметров движения (Motion Estimation) с помощью Intel SSE 4. Этот критически важный алгоритм используется в каждом современном видеокодеке. Он позволяет на основе векторов движения, вычисленных по базовому кадру F, предсказать кадр F+1. Благодаря этому можно программировать только перемещение пикселей от одной картинки к другой, а не кодировать картинки целиком. Яркий пример — замечательные кодеки H264 и H265, у них открытый исходный код, можете его изучить (только сначала прочитайте про MPEG).

Проведём тест:

> cat /proc/cpuinfo
processor  : 2
vendor_id  : GenuineIntel
cpu family : 6
model      : 58
model name : Intel(R) Core(TM) i5-3337U CPU @ 1.80GHz
(...)
flags      : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm ida arat epb xsaveopt pln pts dtherm tpr_shadow vnmi flexpriority ept vpid fsgsbase smep erms

Все эти флаги — по большей части поддерживаемые моим процессором инструкции и наборы инструкций.

Тут можно увидеть sse, sse2, sse4_1, sse4_2, aes, avx.

AES лежит в основе AES-шифрования! Прямо в CPU, с помощью кучи специализированных инструкций.

SSE4.2 позволяет одной инструкцией вычислять контрольную сумму CRC32, а с помощью нескольких инструкций — сравнивать строковые значения. Свежайшие функции str() в библиотеке libC основаны на SSE4.2, поэтому вы можете так быстро грепать слово из гигантского текста.

SIMD нам поможет

Пришло время улучшить нашу С-программу с помощью SIMD и посмотреть, станет ли она быстрее.

Всё началось с технологии MMX, которая добавляла 8 новых 64-битных регистров, от MM0 до MM7. MMX появилась в конце 1990-х, и отчасти из-за неё Pentium 2 и Pentium 3 стоили очень дорого. Теперь эта технология совершенно неактуальна.

Разные версии SSE, вплоть до последней SSE4.2, появлялись в процессорах примерно с 2000-го по 2010-й. Каждая последующая версия совместима с предыдущими.

Сегодня самая распространённая версия — SSE4.2. В ней добавлено 16 новых 128-битных регистров (в X86_64): с XMM0 по XMM15. 128 битов = 16 байтов. То есть, заполнив SSE-регистр и выполнив с ним какое-то вычисление, вы обработаете сразу 16 байтов.

А если обработать два SSE-регистра, то это уже 32 байта за раз. Становится интересно.

С 16 байтами на регистр мы можем хранить (размеры LP64):

16 байтов: шестнадцать C-символов.
Два 8-байтных значения: два длинных значения из С или два числа с двойной точностью (double precision float).
Четыре 4-байтных значения: четыре целочисленных или четыре числа с одинарной точностью (single precision float).
Восемь 2-байтных значения: восемь коротких значений из C.

Например:

SIMD также называют «векторными» инструкциями, потому что они работают с «вектором» — областью, заполненной разными мельчайшими объектами. Векторная инструкция одновременно обрабатывает разные данные, в то время как скалярная инструкция — только одну порцию данных.

В нашей программе можно реализовать SIMD двумя способами:

Написать на ассемблере код, работающий с этими регистрами.
Использовать Intel Intrinsics — API, позволяющий писать C-код, который при компилировании преобразуется в SSE-инструкции.

Я покажу вам второй вариант, а первый сделаете сами в качестве упражнения.

Пропатчим наш код:

#include 
#include 
#include 
#include 
#include 
#include 

#define BUF_SIZE 1024

int main(int argc, char **argv)
{
    int f, i;
    ssize_t readed;
    __m128i r  = _mm_set1_epi8(0);

    unsigned char result = 0;
    unsigned char buf[BUF_SIZE] __attribute__ ((aligned (16))) = {0};

    if (argc != 2) {
        fprintf(stderr, "Использование: %s \n", argv[0]);
        exit(-1);
    }

    f = open(argv[1], O_RDONLY);

    if (f == -1) {
        perror("Не могу открыть файл");
    }

    while ((readed = read(f, buf, sizeof(buf))) > 0) {
        for (i=0; i < readed; i+=16) {
            __m128i a = _mm_load_si128((const __m128i *)(buf+i));
            r = _mm_add_epi8(a, r);
        }
        memset(buf, 0, sizeof(buf));
    }

    for (i=0; i<16; i++) {
        result += ((unsigned char *)&r)[i];
    }

    close(f);

    printf("Чтение завершено, сумма равна %u \n", result);

    return 0;
}

Видите новый заголовок tmmintrin.h? Это интеловский API. Для него есть прекрасная документация.

Для хранения результата суммирования (накопительного) я решил использовать только один SSE-регистр и заполнять его строкой из памяти. Вы можете поступить иначе. Например, взять сразу 4 регистра (или вообще все), и тогда вы будете суммировать 256 байтов в 16 операциях : D
Помните размеры SSE-регистров? Наша цель — суммировать байты. Это значит, что мы будем использовать в регистре 16 отдельных байтов. Если почитаете документацию, то узнаете, что существует много функций для «упаковки» и «распаковки» значений в регистрах. Нам они не пригодятся. В нашем примере не нужно превращать 16 байтов в 8 WORD или 4 DWORD. Нам нужно просто посчитать сумму. И в целом SIMD даёт гораздо больше возможностей, чем описано в этой статье.

Итак, теперь вместо побайтового сложения мы будем складывать по 16 байтов.

В одной инструкции мы обработаем гораздо больше данных.

__m128i r  = _mm_set1_epi8(0);

Предыдущее выражение подготавливает XMM-регитр (16 байтов) и заполняет его нулями.

for (i=0; i < readed; i+=16) {
    __m128i a = _mm_load_si128((const __m128i *)(buf+i));
    r = _mm_add_epi8(a, r);
}

Каждый цикл for() теперь должен увеличивать буфер не на 1 байт, а на 16. То есть i+=16.

Теперь обращаемся к буферу памяти buf+i и наводим его на указатель __m128i*. Таким образом мы берём из памяти порции по 16 байтов. С помощью _mm_load_si128() записываем эти 16 байтов в переменную a. Байты будут записываться в XMM-регистр как »16*один байт».

Теперь с помощью _mm_add_epi8() добавляем 16-байтный вектор к нашему аккумулят