Доклад с конференции Т-Банка, планы на 2026 и полезности на новогодние каникулы

Привет! 2025 близок к завершению, в связи с чем хотел бы поделиться с уважаемыми подписчиками несколькими полезными вещами 🎁


Доклад с JVM Days

За окном уютно лежит свежий рыхлый снег - а ведь всего несколько месяцев назад были жаркие дни конца августа, когда Т-Банк и провел свою конференцию. Все записи уже доступны, здесь же я оставлю ссылку на свой доклад, в котором рассказываю не самые тривиальные (но и не сверх-специфичные!) способы оптимизации производительности на реальном примере одной платежной системы. Рассказываю про:

🔷 многопоточные конвейеры - как искать место для точечного ускорения

🔷 улучшенные способы вставки больших батчей в Postgres и волшебную функцию unnest

🔷 и немного про GC - на примере такого явления, как spiral of death, которое может выстреливать и в Java, и в Go, и вообще практически в любом рантайме со сборкой мусора


Планируемый доклад на SnowOne и подкаст "Тысяча фичей"

Сейчас мне интересна тема актуализации и +- адекватного сравнения алгоритмов сборки мусора и их реализаций в Java и Go; пока я все еще собираю и изучаю материалы

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

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

Во-первых, будет традиционный технический доклад на SnowOne / JPoint, на котором и будут разбираться данные вопросы. Ценовая политика у конференций разная: цена дороги до Нск + SnowOne вполне может оказаться дешевле, чем просто билет на JPoint; в любом случае, спустя ~полгода запись станет доступна всем

Во-вторых, уважаемый @apakhmv предложил мне записаться в январе на подкасте "Тысяча фичей", где я попробую рассказать про всё вот это только голосом - без каких-либо картинок и слайдов. Не знаю, удачно ли получится у меня, но сам подкаст интересный: рубать солёные огурцы для оливье под разбор внутрянки Cassandra - самое то, советую послушать на этих каникулах!

Преподавание в университете

Конец года принес мне авантюрное предложение от одного университета - сделать авторский курс по многопоточному программированию для студентов 2 курса, которые знают Go и классический Си

Авантюрное оно для меня, потому что я никогда раньше не преподавал (но всегда хотелось попробовать); лекции только-только начинают писаться, а в качестве практической работы я планирую предложить студентам написать свою простейшую реализацию LSM-based базы данных целиком в памяти - там есть большое количество шестеренок и механизмов, которые должны работать конкурентно друг с другом: начиная от потокобезопасных MemTable / SSTable и заканчивая компатизаторами и другими фоновыми механизмами

Курс будет на Go, с вкраплениями C, но не могу не поделиться прекрасным материалом от Одноклассников, который и вдохновил меня на эту идею: на курсе люди с нуля делают свою простую реализацию Cassandra на чистой Java. Чистое удовольствие!

На этом пока все. Поздравляю с наступающим Новым годом и Рождеством! До встречи в 2026🎄

пока искал иллюстрации для лекций, наткнулся на сайт, посвященный истории появления вычислительной техники с её первых дней. Конкретно эта фотография: программистка и её программа, 62 500 карточек, ~ 5 Мб, 1955 год

поздравляю с окончанием первой рабочей недели 📝

Разбор квиза 1/3: какая же из реализаций наивного алгоритма умножения матриц эффективнее?

Выбор метрики

Во-первых, как правильно заметили в комментариях, под эффективностью можно понимать разные вещи, например:

✅время исполнения
✅число выполненных инструкций на CPU
✅энергетическая эффективность (сколько энергии потратили на выполнение всей задачи)

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

Выбираем размер матрицы

Во-вторых, надо бы зафиксировать объем задачи, чтобы можно было сравнивать реализации: тут это просто размер матрицы n. Для маленьких матриц вся эта возня с индексами очевидно не будет интересной, поэтому пусть n = 1000

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

Пишем простейший go-бенчмарк и замеряем

Единственный момент, поскольку у нас присутствуют накладные расходы: начальное создание и заполнение матриц числами - это нужно правильно учесть в дальнейшем

Поэтому в бенчмарке есть NOP/baseline - матрицы не умножаются, но работа по подготовке матриц ведется

Результаты

Замеры делались на Intel i9-12900K
(для чистоты эксперимента энергоэффективные E-ядра отключены), и вот что получилось:

🥇 i → k → j : 784 ms (по опросу: 2)
🥈 k → i → j : 942 ms (по опросу: 3)

🥉 j → i → k : 1257 ms (по опросу: 5-6)
🥉 i → j → k : 1302 ms (по опросу: 1)

❌ j → k → i : 1996 ms (по опросу: 5-6)
❌ k → j → i : 2044 ms (по опросу: 4)

Почему-то i → k → j работает быстрее всех, фаворит опроса оказался середняком, а худшие варианты почти в 2,5 раза медленнее лучших.

В следующих постах разбираемся, как же так получилось👇

Разбор квиза 2/3: гипотеза о кэшах

Паттерны обращения к памяти

Заметим - обращение всегда идет по конкретным индексам:

🌀 матрица А: a[i][k]
🌀 матрица B: b[k][j]
🌀 матрица C: c[i][j]

Формула: c[i][j] += a[i][k] * b[k][j]

Давайте визуализируем паттерн этих обращений внутри самого вложенного цикла с помощью серого цвета

Например, для i → j → k последний вложенный цикл - по k, а значит в этом цикле:

💡чтение a[i][k] будет происходить в рамках строки i
💡чтение b[k][j] будет происходить в рамках столбца j
💡позиция элемента c[i][j] в рамках цикла по k фиксирована и не меняется

Кэши процессора

Если бы программа работала на абстрактной RA-машине (на чьей модели и строится теория анализа сложности алгоритмов) - паттерны доступа к памяти не имели бы никакого значения

Однако запускается то программа на реальном железе - в моем случае на x86. Между вычислительными устройствами процессора (они и исполняют инструкции) и памятью (в которой хранятся данные) находится иерархия из нескольких промежуточных кэшей: L1, L2, L3

CPU Core
  |
  v
L1 cache: ~32KB
  |
  v
L2 cache: ~256KB
  |
  v
L3 cache: ~10-30MB
  |
  v
 RAM    : гигабайты

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

Кэш-линии и их вытеснение

Когда происходит чтение области памяти по адресу address, и это значение ещё не хранится в кэше - происходит так называемый cache miss, в результате которого эта область и будет загружена в кэш - чтобы при дальнейшем обращении к ней доступ был быстрее. Все это происходит автоматически на уровне железа, и у прикладного разработчика нет возможности явно управлять этим механизмом

Кэш оперирует не отдельными адресами, а непрерывными областями памяти (обычно размером 64 байта, выравнивание такое же)

Когда происходит cache miss - в кэш загружается не только переменная по address, но и небольшая область памяти рядом с этой переменной - так называемая кэш-линия

Кэш имеет ограниченный размер, поэтому каждая загрузка кэш-линии будет приводить к тому, что какая-то другая кэш-линия будет вытеснена из кэша

Гипотеза

Теперь можно сформулировать теорию

Когда происходят доступы к элементам матрицы в рамках одной строки - загрузка кэш-линии помогает, чтения идут из этой же кэш-линии - это быстро 🔋

Когда доступы идут в рамках конкретного столбца - кэш-линия от текущего чтения никак будет использоваться при чтении следующего элемента столбца

Более того, чтение может вытеснять какую-то другую кэш-линию! Таким образом, мы гораздо хуже утилизируем кэш и работаем менее эффективно 🔋

Это объясняет почему i → k → j работает эффективнее: обращения идут построчно, что дает лучшую кэш-локальность

Но, конечно же, пока все это только теория. В следующем посте замеряем эффекты на практике 👇

Разбор квиза 3/3: проверка теории

В прошлой части мы сформулировали гипотезу:
порядок циклов влияет на локальность доступа к памяти → локальность влияет на кэш → кэш влияет на время выполнения

Теперь проверим это в реальности

Perf

Используем perf - стандартный Linux инструмент для анализа производительности. Для начала соберем существующий go-бенчмарк в виде бинарного файла:

go test -c -o bench.test

Для каждого варианта умножения запустим perf в режиме сбора событий:

perf stat -r 5 -e \
cpu_core/instructions/,\
cpu_core/cycles/,\
cpu_core/L1-dcache-loads/,\
cpu_core/L1-dcache-load-misses/ \
-- ./bench.test \
-test.run=^$ \
-test.bench='MatMul/IJK' \
-test.count=1 \
-test.benchtime=10x \
-n=1000

Что замеряем

В результате для каждого варианта получим результаты в таком формате:

 Performance counter stats for './bench.test -test.run=^$ -test.bench=MatMul/IJK -test.count=1 -test.benchtime=10x -n=1000' (5 runs):

   297 353 515 594      cpu_core/instructions/           #    3,83  insn per cycle              ( +-  0,00% )
    77 606 222 836      cpu_core/cycles/                                                        ( +-  0,21% )
   108 062 152 268      cpu_core/L1-dcache-loads/                                               ( +-  0,00% )
    10 936 805 980      cpu_core/L1-dcache-load-misses/  #   10,12% of all L1-dcache accesses   ( +-  0,25% )

Где:
instructions - сколько инструкций реально выполнил CPU
cycles - cколько тактов процессора потребовалось
Из этих двух чисел выводится IPC (instruction-per-cycle) - количественная метрика, показывающая насколько эффективно наша программа работает с точки зрения CPU

L1-dcache-loads - количество попыток прочитать данные из L1-кэша
L1-dcache-load-misses - количество случаев, когда запрошенных данных не оказалось в L1 (пошли дальше по пути L2 → L3 → RAM)
Из этих двух чисел выводится, какая доля обращений к L1 оказалась cache-miss

Что получилось

Для каждой реализации я собрал соответствующие события, отнял baseline и отобразил на изображении

Для всех реализаций:
😀 количество инструкций почти одинаковое
😀 разница - в cycles и IPC
😀 разница коррелирует с L1 miss rate

У i → k → j:
✅меньше всего L1-промахов
✅ выше IPC
✅ меньше cycles

У k → j → i:
❌ больше всего промахов
❌ ниже IPC
❌ больше cycles

Теория полностью совпала с практикой!

Важное уточнение

В прошлом посте мы рассматривали только самый внутренний цикл. Но тот же принцип работает и для промежуточного цикла. Именно поэтому, например, i → k → j и k → i → j тоже отличаются по результатам. Надо учитывать общий паттерн доступа к памяти!

Давайте подводить итоги👇

Квиз: итоги

Разумеется, никто в реальной жизни таким наивным алгоритмом матрицы не перемножает - есть куда более продвинутые техники. Если интересно, отличный разбор: Achieving Peak Performance for Matrix Multiplication in C++

Но цель этого упражнения была другой - показать, как одинаковый алгоритм с одинаковым количеством инструкций и одинаковой асимптотикой может давать разницу почти в 2,5 раза

Причина - кэши процессора и паттерны доступа к памяти

Ничего не меняя математически, просто начав ходить по памяти так, как это удобно железу - и все стало работать эффективнее

И это, по сути, и есть та самая mechanical sympathy - когда есть понимание, как система работает внутри, и не заставляешь ее делать то, что ей неудобно

Понравился ли вам данный лонгрид, делать ли еще такие, или что-то поменять в формате? Пишите в комментариях ❤️