Недавно я повстречался с коллегой, и он жаловался на то, что некоторые процессы работают медленно. Он оценил количество сгенерированных байтов данных, посчитал, сколько проходов обработки было выполнено, а также сколько байтов оперативной памяти необходимо. Коллега предположил, что современные видеокарты с пропускной способностью памяти до 500 Гб/с. выполнят его задачу, не моргнув глазом.

Я счёл его точку зрения интересной. У меня иной подход к решению задач.

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

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


Вот мой мысленный эксперимент. Допустим, у нас в памяти есть цельный массив из миллиарда 32-битных целых чисел. Он занимает 4 гигабайта. Сколько времени уйдёт на итерирование массива и суммирование всех значений в нём? Сколько байтов в секунду сопутствующих данных процессор сможет прочитать из памяти? Какая скорость случайного доступа? Насколько это можно распараллелить?

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

Тем не менее, я считаю, что этот вопрос стоит рассмотреть внимательнее. Я не пытаюсь найти ответ. Но я считаю, что можно определить верхнюю и нижнюю границу пропускной способности, а также какие-то интересные пороги между ними. И, надеюсь, чему-то научиться в процессе.

Числа, которые должен знать любой программист

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


Источник: Jonas Boner

Прекрасный список. Я встречаю его на HackerNews как минимум раз в год. Каждый программист должен знать эти числа.

Но эти числа относятся к другому вопросу. Задержка и пропускная способность — не одно и то же.

Задержка в 2020-м

Это список из 2012-го. Я пишу в 2020-м, времена изменились. Вот значения для Intel i7, взятые со StackOverflow.

Удачное обращение к L1-кэшу,                                  ~4 цикла (2,1 - 1,2 нс)
Удачное обращение к L2-кэшу,                                  ~10 цикла (5,3 - 3,0 нс)
Удачное обращение к L3-кэшу, неразделённая строка             ~40 цикла (21,4 - 12,0 нс)
Удачное обращение к L3-кэшу, разделённая строка в другом ядре ~65 цикла (34,8 - 19,5 нс)
Удачное обращение к L3-кэшу, изменена в другом ядре           ~75 цикла (40,2 - 22,5 нс)
Локальная память                                              ~60 нс

Интересно! Что же изменилось?

• L1 стал медленнее, 0,5 нс -> 1,5 нс.
• L2 стал быстрее, 7 нс -> 4,2 нс.
• Относительная скорость между L1 и L2 стала гораздо меньше, 14- и 2,5-кратная разница.
• L3 теперь стал стандартным, 12 нс -> 40 нс.
• Оперативная память стала быстрее, 100 нс -> 60 нс.

Не хочу делать далеко идущие выводы. Непонятно, как были получены первые значения. В данном случае мы не сравниваем яблоки с яблоками.

А вот пропускная способность и размеры кэшей для моего процессора согласно wikichip:

Пропускная способность памяти: 39,74 Гигабайта в секунду
L1-кэш: 192 Кб (по 32 Кб на ядро)
L2-кэш: 1,5 Мб (по 256 Кб на ядро)
L3-кэш: 12 Мб (общий; по 2 Мб на ядро)

Что я хочу узнать:

• Каков верхний предел производительности оперативной памяти?
• Каков нижний предел?
• Каковы ограничения для кэшей L1/L2/L3?

Простой бенчмарк

Давайте прогоним тесты. Я написал на C++ простой бенчмарк. Очень упрощённо он выглядит так.

// Генерируем случайный элемент
std::vector<int> nums;
for (size_t i = 0; i < 1024*1024*1024; ++i) // один миллиард int-ов
    nums.push_back(rng() % 1024); // маленькие числа для предотвращения переполнения

// Запускаем тест в 1-12 потоках
for (int thread_count = 1; thread_count <= MAX_THREADS; ++thread_count) {
    auto slice_len = nums.size() / thread_count;
    
    // Для каждого потока
    for (size_t thread = 0; thread < thread_count; ++thread) {
        
        // распределение данных
        auto begin = nums.begin() + thread * slice_len;
        auto end = (thread == thread_count - 1)
            ? nums.end() : begin + slice_len;

        // создание потоков
        futures.push_back(std::async([begin, end] { 
            
            // последовательное сложение чисел
            int64_t sum = 0;
            for (auto ptr = begin; ptr < end; ++ptr)
                sum += *ptr;
            return sum;
        }));
    }

    // объединение результатов
    int64_t sum = 0;
    for (auto& future : futures)
        sum += future.get();
}

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

Также я хочу измерить скорость случайного обращения. Это не так просто. Я попробовал несколько способов и в результате выбрал предварительное вычисление и перемешивание индексов. Каждый индекс в единственном экземпляре. И с помощью внутреннего цикла итерирую индексы и вычисляю sum += nums[index].

std::vector<int> nums = /* ... */;
std::vector<uint32_t> indices = /* перемешаны */;

// случайное обращение
int64_t sum = 0;
for (auto ptr = indices.begin(); ptr < indices.end(); ++ptr) {
    auto idx = *ptr;
    sum += nums[idx];
}
return sum;

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

Я тестировал на трёх типах данных:

• int — обычные 32-битные целые числа.
• matri4x4 — содержит int[16]. Помещается в 64-байтную строку кэша.
• matrix4x4_simd — использует механизм __m256i.

Большой блок

Мой первый тест оперирует большим блоком памяти: один гигабайт T—элементов заполнен маленькими случайными значениями. Простой цикл итерирует по массиву N раз, то есть нужно обратиться к N Гб памяти для вычисления int64_t sum. Распределим массив между несколькими потоками вычисления, каждый поток будет обращаться к строго одинаковому количеству элементов.


Тадам! Для этого графика взята средняя длительность суммирования элементов и преобразована из исполнения_в_наносекундах в гигабайты_в_секунду.

Получилось довольно аккуратно. int32 позволяет последовательно считывать в одном потоке 11 Гб/с. Скорость линейно возрастает, пока не стабилизируется на уровне 38 Гб/с. matrix4x4 и matrix4x4_simd растут быстрее, но упираются в тот же потолок.

Верхний предел скорости считывания данных из памяти очевиден. На моей системе это около 40 Гб/с, что сопоставимо с современными спецификациями, приведёнными выше.

Посмотрим на три нижние линии на графике. Случайное обращение работает очень медленно. Производительность однопоточного int32 составляет жалкие 0,46 Гб/с. Это в 24 раза медленнее, чем последовательное суммирование на скорости 11,03 Гб/с! matrix4x4 работает лучше, потому что оперирует полными кэш-строками. Но всё равно получается в 4-7 раз медленнее по сравнению с последовательным чтением, и в пике достигает 8 Гб/с.

Маленький блок, последовательное чтение

В моей системе на каждое ядро приходятся кэши L1/L2/L3 размером 32 Кб, 256 Кб и 2 Мб. Что произойдёт, если взять блок элементов размером 32 Кб и итерировать его 125 000 раз? Это эквивалентно обращению к 4 Гб памяти, но при этом мы всегда будем попадать в кэш.


Круто! Однопоточная производительность такая же, как при чтении большого блока, около 12 Гб/с. За исключением этого случая, многопоточная обработка достигает 40 Гб/с. Так и должно быть: данные остаются в кэше, так что мы не упираемся в узкое место в виде оперативной памяти. Данные, которые не помещаются в L3-кэш, достигают потолка около 38 Гб/с.

matrix4x4 демонстрирует тот же паттерн, но работает ещё быстрее: 31 Гб/с при однопоточной и 171 Гб/с при многопоточной обработке.


Теперь посмотрим на matrix4x4_simd. Обратите внимание на ось Y.


matrix4x4_simd работает охрененно быстро, в 10 раз быстрее int32. При работе с блоком в 16 Кб пробивает потолок в 1000 Гб/с.

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

Но урок-то реальный. Скорость оперирования данными внутри кэша высока. Больше 100 Гб/с при одном потоке и больше 1000 Гб/с при нескольких потоках. Помещение данных в кэш происходит медленно, в сумме не выше 40 Гб/с.

Маленький блок, случайное чтение

Теперь сделаем то же самое, но со случайным чтением. Это моя любимая часть статьи.



Чтение случайных значений из оперативной памяти выполняется медленно со скоростью 0,46 Гб/с. Чтение случайных значений из L1-кэша очень-очень быстрое, 13 Гб/c. Это быстрее, чем 11 Гб/с при последовательном чтении int32 из оперативной памяти.


matrix4x4 демонстрирует такой же паттерн, но работает примерно вдвое быстрее, чем int.


Случайное чтение matrix4x4_simd выполняется безумно быстро.

Итоги тестирования случайного чтения

Случайное чтение из оперативной памяти выполняется медленно. Катастрофически медленно. Меньше 1 Гб/с для int32. Случайное чтение из кэша выполняется примечательно быстро, на уровне последовательного чтения из памяти.


Идём дальше. При переходе от блока 16 Кб (размер L1) к блоку 256 Кб (размер L2) скорость снижается до двух раз.

Думаю, у этого есть глубокие последствия.

Связные списки можно считать вредными

Обращение к указателю — дело плохое. Очень плохое. Насколько? Я сделал ещё один тест, в котором matrix4x4 обёрнуто в std::unique_ptr. Каждое обращение проходит через указатель. В результате получаем ужасный, кошмарный, плохой, отвратительный результат.

     1 поток           |   matrix4x4   | unique_ptr |  Разн. |
-----------------------|---------------|------------|--------|
Большой блок, послед.  |   14,8 Гб/с   |  0,8 Гб/с  |  19x   |
16 Кб, послед.         |   31,6 Гб/с   |  2,2 Гб/с  |  14x   |
256 Кб, послед.        |   22,2 Гб/с   |  1,9 Гб/с  |  12x   |
Большой блок, случ.    |    2,2 Гб/с   |  0,1 Гб/с  |  22x   |
16 Кб, случ.           |   23,2 Гб/с   |  1,7 Гб/с  |  14x   |
256 Кб, случ.          |   15,2 Гб/с   |  0,8 Гб/с  |  19x   |

     6 потоков         |   matrix4x4   | unique_ptr |  Разн. |
-----------------------|---------------|------------|--------|
Большой блок, послед.  |   34,4 Гб/с   |  2,5 Гб/с  |  14x   |
16 Кб, послед.         |  154,8 Гб/с   |  8,0 Гб/с  |  19x   |
256 Кб, послед.        |  111,6 Гб/с   |  5,7 Гб/с  |  20x   |
Большой блок, случ.    |    7,1 Гб/с   |  0,4 Гб/с  |  18x   |
16 Кб, случ.           |   95,0 Гб/с   |  7,8 Гб/с  |  12x   |
256 Кб, случ.          |   58,3 Гб/с   |  1,6 Гб/с  |  36x   |

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

При обращении к указателю скорость падает в 10-20 раз. Не позволяйте своим друзьям и коллегам использовать связные списки. Прошу вас, подумайте о детях кэше.

Определяем Frame Budgets

Для разработчиков игр является нормой планировать потребление ресурсов процессора и объёма памяти для подсистем. Но я не разу не сталкивался с планированием обращения к памяти.

Современные игры используют всё более высокую частоту кадров. 60 кадров в секунду стало нормой. VR использует 90 кадров в секунду. У меня игровой монитор с частотой обновления 144 Гц, это офигенно, и частота в 60 кадров уже выглядит паршиво. Я никогда не вернусь на меньшую частоту. Профессиональные геймеры используют мониторы с частотой 240 кадров в секунду. ASUS представил на CES монстра с частотой 360 кадров.

У моего процессора верхний предел около 40 Гб/с. Вроде бы много! Но на 240 Гц это лишь 167 Мб на кадр. Настоящее приложение может потреблять 5 Гб/с при частоте 144 кадра в секунду, то есть по 69 Мб на кадр.

Вот некоторые данные:

        |   1   |   10   |   30   |   60   |   90   |  144   |  240   |  360   |
--------|-------|--------|--------|--------|--------|--------|--------|--------|
40 Гб/с | 40 Гб |  4 Гб  | 1.3 Гб | 667 Мб | 444 Мб | 278 Мб | 167 Мб | 111 Мб |
10 Гб/с | 10 Гб |  1 Гб  | 333 Мб | 166 Мб | 111 Мб |  69 Мб |  42 Мб |  28 Мб |
 1 Гб/с |  1 Гб | 100 Мб |  33 Мб |  17 Мб |  11 Мб |   7 Мб |   4 Мб |   3 Мб |

Мне кажется полезно представить проблему под таким углом. Это поможет понять, что некоторые идеи неосуществимы. Добиться 240 кадров в секунду непросто. Это не происходит само по себе.

Числа, которые должен знать любой программист (2020)

Список чисел, которые должен знать любой программист, устарел. Его нужно обновить с учётом реалий 2020-го.

Вот некоторые данные для моего домашнего компьютера. Они получены с помощью AIDA64, Sandra и моего бенчмарка. Эти числа не дают полного представления о ситуации, это лишь исходная точка.

Задержка L1:                   1 нс
Задержка L2:                   2,5 нс
Задержка L3:                   10 нс
Задержка оперативной памяти:   50 нс

(на одно ядро)
Пропускная способность L1:     210 Гб/с 
Пропускная способность L2:     80 Гб/с
Пропускная способность L3:     60 Гб/с

(вся система)
Пропускная способность оперативной памяти: 45 Гб/с 

Хорошо бы иметь маленький, простой бенчмарк с открытым кодом для определения подобных значений. Один файл на С, который можно исполнять на настольных компьютерах, серверах, мобильных устройствах, приставках и т.д. Я не смогу такое написать.

Примечание

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

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

Заключение

Мой коллега показал мне такой подход к решению проблем программирования, о котором я не знал. Это сподвигло меня на исследование производительности современно оперативной памяти.

Вот некоторые значения для современного настольного ПК, которые можно использовать в примерных расчётах:

• Производительность оперативной памяти
  
  • Верхний предел: 45 Гб/с
  • Примерная оценка: 5 Гб/с
  • Нижний предел: 1 Гб/с
• Производительность кэшей L1/L2/L3 (на ядро)
  
  • Верхний предел (SIMD): 210 Гб/с / 80 Гб/с / 60 Гб/с
  • Примерная оценка: 25 Гб/с / 15 Гб/с / 9 Гб/с
  • Нижний предел: 13 Гб/с / 8 Гб/с / 3,5 Гб/с

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

Главное — я научился по-новому подходить к решению проблем. Оперирование байтами в секунду или байтами на кадр позволяет взглянуть на задачу под другим углом. Полезный инструмент в моём арсенале.

Исходный код

Бенчмарк на C++

График на Python

data.json

Для дальнейших исследований

Эта статья лишь слегка затронула поднятый вопрос. Вряд ли я буду писать продолжение. Но если бы стал, но затронул бы такие вопросы:

• Скорость записи.
• Ложное разделение данных.
• Производительность std::atomic (или её отсутствие).
• Счётчики производительности.
• Производительность TLB.
• Протоколы кэширования.

Параметры системы

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

• Операционная система: Windows 10 v1903 build 18362.
• Процессор: Intel i7-8700k @ 3.70 ГГц
• Оперативная память: 2x16 GSkill Ripjaw DDR4-3200 (16-18-18-38 @ 1600 МГц)
• Материнская плата: Asus TUF Z370-Plus Gaming