#44: SIMD в базах данных

[00:07] Александр: Здарова! Меня зовут Саша Пахомов, и я инженер, который любит своё дело. Вы слушаете 44-й выпуск подкаста «Тысяча фичей». Сегодня мы погрузимся в мир процессоров и посмотрим на них глазами системного инженера. Это большой выпуск, в нём очень много информации и инсайдов. Я искренне старался сделать его доступным для широкой аудитории, но тема настолько зубодробительная, что в некоторых местах присутствует жесть. Если в какой-то момент вам станет что-то непонятно — не переживайте, я с вами. В этом выпуске я задаю кучу вопросов и пытаюсь пересказать материал своими словами так, чтобы было понятно даже мне. А чтобы вы знали, какие темы мы сегодня обсудим, вот вам некоторые ключевые слова, которые я выписал во время монтажа: как работает процессор, что такое кэш-линии, стек, prefetch, спекулятивное выполнение, memory model, happens-before, CAS, SIMD, автовекторизация, portability. И это не полный список. В общем, выпуск огонь. Заваривайте чай, кофе, настраивайтесь на два часа интереснейшего инженерного контента. Ну а мы с Максимом начинаем.

[01:41] Максим: Всем привет. Сегодня мы как раз хотели поговорить именно про процессоры, а потом уже погрузиться глубже в SIMD-инструкции. Начнём с процессора. Совсем базовые вещи говорить, наверное, не буду, но можно представить себе, что наш код компилируется в какой-то объектный файл, и внутри него находятся инструкции, которые процессор использует. Это тот код, который он, например, будет выполнять. У каждого процессора, у каждого семейства процессоров совершенно разные инструкции, совершенно разный encoding инструкций. Даже у одного семейства процессоров между версиями encoding может отличаться. Поэтому, вообще говоря, бинарные файлы не портируемые в общем случае. Про это мы потом, когда дойдём до SIMD, ещё поговорим. Но в целом вот у нас есть бинарный файл и наивное представление о pipeline процессора. Наивное — потому что текущие процессоры немного по-другому работают, но про это чуть позже. Для пользователя это представление наивное, но правильное. Грубо говоря, любые оптимизации, которые происходят в процессоре, для вас как бы невидимые.

[02:26] Максим: Можно представлять себе так: есть некий курсор, который где-то там условно в коде, и процессор по этому курсору читает код. В разных процессорах этот курсор по-разному называется — обычно code pointer, специальный регистр для этого. Процессор читает инструкцию и выполняет её. Но внутри процессора эта операция, понятное дело, очень сложная, многостадийная. Можно думать про неё так: сначала инструкцию нужно декодировать, достать из неё какие-то аргументы, понять, что это вообще за инструкция. Потом, если инструкция взаимодействует с памятью, сходить в эту память, достать какое-то значение и затем уже выполнить саму инструкцию.

[03:11] Максим: Тут внутри процессора — это не деталь, но в принципе важная штука — есть различные юниты, которые выполняют различные инструкции. Например, есть арифметико-логический юнит, он выполняет простые арифметические операции типа add. Есть floating-point-юнит, который выполняет операции с регистрами, содержащими значения с плавающей точкой. У разных процессоров может быть много разных других юнитов. И когда мы выполняем инструкцию, работает как раз один из таких юнитов. Но важная ещё вещь — это память.

[03:41] Максим: Процессор и память работают вместе, и ваш код, когда вы его запускаете, где-то находится в памяти, и процессор с этой памятью взаимодействует. Например, вы аллоцируете какую-то память, просите у операционной системы оперативную, и процессору нужно как-то с ней работать. Я не знаю процессоров, у которых есть инструкции, которые могут одновременно что-то прочитать и записать в память. В большинстве случаев нужно сначала из памяти прочитать в регистры, что-то с ними поделать и только затем записать обратно в память. Это тоже важная вещь.

[04:11] Максим: Базово можно представить это так: наивное представление — у тебя есть процессор, который выполняет инструкции, инструкцию он достаёт из бинарного файла, который находится в памяти, и он может взаимодействовать с памятью — что-то читать в регистры из памяти и писать в память. Но это очень наивное представление. Скорость процессора в миллион раз быстрее скорости памяти, особенно для простых операций. Ну не в миллион, наверное, в тысячу.

[04:34] Александр: Да, это, наверное, 10 в третьей, по-моему.

[04:36] Максим: Да. Скорость доступа к оперативной памяти — сотни наносекунд, в зависимости от того, есть ли там NUMA и прочее. Там ещё разные сложные штуки, но в целом можно считать 100–200 наносекунд. А инструкция выполняется очень-очень быстро, даже меньше наносекунды. И вот это взаимодействие было бы невероятно тормознутым: инструкция выполняется меньше чем за наносекунду, но ей нужно постоянно что-то читать и писать в память, и за счёт этого получается, что мы почти всё время должны были бы ждать память.

[05:05] Максим: И в современных процессорах — да и вообще в весьма старых — для этого придумали механизм кэширования. Кэширование устроено очень сложно. Обычно у процессоров есть несколько уровней кэша, и каждый уровень, в зависимости от того, насколько далеко он от процессора, тем больше по размеру, но тем медленнее доступ. Например, к L1-кэшу скорость доступа примерно 1 наносекунда, поэтому инструкция работает даже быстрее. Стоимость доступа к L2-кэшу — по-моему, уже 5–6 наносекунд. Эти кэши помогают сгладить разницу в скорости между памятью и процессором.

[05:46] Максим: Что важно понимать про кэши? Вообще в компьютер-сайенс для разных приложений нужны совершенно разные кэши, разные политики кэширования, но в процессорах люди давным-давно поняли, что паттерны работы очень понятные. Есть два важных свойства кэша: временная локальность и пространственная локальность. Что это значит? Обычно считается так: вот вы обратились к какой-то ячейке памяти — скорее всего, после этого вы обратитесь к какой-то соседней ячейке. Это пространственная локальность. А временная локальность — это то, что если мы обратились к какой-то ячейке, скорее всего, мы к ней обратимся ещё раз.

[06:19] Максим: Вообще говоря, кэши работают не на уровне ячеек памяти — то есть, например, на 64-битных процессорах не на уровне 8 байт, — а на уровне кэш-линии. Размер кэш-линии бывает разный: он не всегда 64 байта, как на x86, может быть, например, 128 байт. И вот это взаимодействие памяти и процессора устроено сквозь такую иерархию кэшей. Когда процессору нужно прочитать из памяти какую-то ячейку, он запрашивает сразу кэш-линию. И эта кэш-линия записывается и попадает сразу и в L3, и в L2, и в L1. А когда вы пишете в память, процессор пишет сначала в L1, и потом постепенно перетекает в L2 и L3. Стоит добавить, что у современных процессоров много ядер, и у каждого ядра обычно свои L1 и L2, а L3 общий. Знание про кэши уже может весьма сильно помочь вам писать оптимизированные программы.

[07:19] Александр: Для тех, кто немножко поплыл — тема не самая простая, — давай я сейчас проговорю ещё раз, себе в голове структурирую, эту картинку дорисую. Мы начали с того, что есть процессор — юнит, который за один такт исполняет какую-то инструкцию. У него есть некоторый указатель… ну или не за один такт, есть некоторые инструкции, которые за несколько тактов.

[07:40] Максим: Да, такие инструкции, конечно, есть. Например, инструкции, которые работают с floating-point, могут даже много тактов использовать.

[07:46] Александр: Ладно, про такт забыли. Короче, инструкции есть, они считываются одна за другой на уровне одного процессора. Они лежат в памяти, которая в целом — отображение нашего бинарного файла. Типа мы взяли бинарный файл, загрузили в память, процессор такой «оп» и пошёл читать инструкции. В этих инструкциях может быть много разного. Если кто-то писал на ассемблере — это очень похоже, там работают с регистрами, очень-очень низкоуровневые примитивные штуки, в которых нет if-ов, циклов, всё делается руками жёстко. И эти инструкции могут работать с регистрами. Регистры — это рабочая область процессора, они являются частью инструкции. Скопировать одно, добавить в другое — это будет происходить с регистрами. То есть, по сути, это то, что процессор держит в руках и чем оперирует, правильно?

[08:34] Максим: Да-да, всё верно. Это регистры, они на кристалле. Их очень-очень маленькое количество — десятки или сотни, если мне не изменяет память, если рассматривать самый примитивный. В них мы не можем загрузить, например, хэш-мапу из Java: она в регистр не поместится.

[08:49] Александр: Соответственно, чтобы забирать что-то большее из памяти, перебрать весь наш замечательный ArrayList, процессору придётся ходить в оперативную память, RAM, которая на такие порядки, на тысячу медленнее, чем исполнение инструкций, не требующих доступа к этой памяти. Из регистра в регистр переложить — будет x или там n. А переложить из памяти в регистр, потом обратно в память — это будет уже тысяча x, а то и больше. Соответственно, это супер неэффективно: если мы выполняем какие-то инструкции, мы постоянно замедляемся, и, по сути, скорость выполнения программ будет равна скорости работы памяти. Поэтому процессоры работают с памятью через систему кэширования, которую можно представить как пирамидку из трёх плашечек. Первая, самая маленькая плашечка, ближе всего расположена к кристаллу — по сути, на кристалле или где-то очень близко. Вторая шире, но дальше. Третья самая широкая — ближе всего к RAM, но дальше всего от процессора. Соответственно, стоимость похода в эти участки разная: самая быстрая, в несколько наносекунд, — в первую, довольно быстрая — вторая, третья ещё медленнее. И только потом идёт плашка с оперативной памятью.

[10:12] Александр: Таким образом, когда процессор зачем-то идёт в оперативную память, он думает: а зачем я буду ходить каждый раз за одним значением? Буду-ка я сразу загружать себе целую кэш-линию — размера моей самой маленькой кэш-линии. Допустим, туда помещается 128 байт. Тогда за один момент обращения к памяти, за момент времени x, я стяну 128 байт. Даже если 127 из них мне не понадобятся, по скорости это будет то же самое, как если бы я стянул один байт за тот же x. То есть я просто скопом докидываю себе всё, что лежит рядом. И вероятность того, что я в цикле нахожусь и считываю следующее значение из массива, очень велика. Если посмотреть на весь flame graph работы всех программ в мире, там очень много будет циклов, и вероятность того, что мы будем попадать в кэш, а не считывать каждое новое значение из памяти, довольно велика. Просто эмпирически инженеры пришли к тому, что это работает лучше, чем что-либо другое, поэтому мы забираем из памяти кэш-линиями.

[11:19] Александр: Эта схема, этот паттерн взаимодействия процессора, кэшей и памяти — вот на нём будет дальше основываться наш диалог о том, как этим эффективно пользоваться и как, например, отвечать на интересные вопросы на интервью, которые как раз Макс хотел рассказать.

[11:36] Максим: Циклы — это понятно. Но вот представьте, есть объект, структура, у которой несколько полей, и ты обращаешься к ней по указателю. В системных языках структура лежит в памяти as-is. И когда ты идёшь фетчить эту структуру из памяти, ты её как бы всю затянул.

[11:50] Александр: As-is — это ты говоришь, она прям неразделимый кусок памяти, эта структура?

[11:54] Максим: Да, continuous, так скажем, array of bytes.

[11:57] Александр: А, например, если мы говорим про Java — объект из пяти Integer и десяти Long, — у объектов в Java ссылки хранятся внутри, поэтому не факт, что этот объект будет continuous array of bytes.

[12:10] Максим: Скорее всего, не будет. Я, кстати, немного про стек хотел рассказать, сейчас к нему вернусь. В Java так не будет. Но если ты в Java вместо объектов заиспользуешь просто Long и int, примитивные типы, то будет, как я сказал.

[12:23] Александр: Да, да.

[12:23] Максим: То есть в целом это может решать: если ты какой-то прям низкоуровневый код колбасишь, поменять в каком-то классе, который ты в цикле часто откуда-то фетчишь — может, из ArrayList какого-нибудь, — это в принципе может сыграть.

[12:36] Максим: Хотел ещё немного сказать про стек. Для чего нужен стек? Для того, чтобы мы могли условно функции вызывать. У каждого процессора есть stack pointer — у всех процессоров по-разному, тут, наверное, на x86 не стоит концентрироваться, я вот, например, и на ARM иногда код пишу. Pointer указывает на вершину стека — обычно у всех процессоров именно так. И, например, если тебе нужно аллоцировать память на стеке, хочешь сделать локальный массив, то в целом ты можешь от этого указателя отнять какое-то число — и вот ты память аллоцировал. Поэтому аллокация памяти на стеке обычно сильно-сильно-сильно быстрее, потому что эта память всегда прогрета.

[13:07] Максим: Про стек не нужно думать как о чём-то волшебном или странном. Стек — это просто область памяти, которую изначально, когда ваша программа начала выполняться и вызывать какие-то функции… Или, например, стек ещё может использоваться в некоторых системах как часть calling convention, когда нужно передавать аргументы. Есть разные calling conventions, и в некоторых из них, если аргументов очень много — какая-то безумная функция принимает очень много аргументов, — то их нужно передавать уже через стек. И для системных вызовов стек тоже часто используется. Эту область памяти для нас заготавливает обычно ядро операционной системы, когда запускает вашу программу. Про это нужно думать просто как о куске памяти, не что-то сверхъестественное — тоже область памяти, просто про неё нужно понимать, что там есть аллокация памяти на стеке. Если тебе нужно аллоцировать маленький массивчик, лучше не идти к аллокатору, который в каком-то худшем случае может сделать системный вызов, пойти в операционную систему. Обычно такого не происходит, но в любом случае в аллокаторе код весьма сложный, намного сложнее, чем отнять от вершины стека какое-то число — это обычно одна инструкция.

[14:09] Александр: Так, а про стек давай ещё — это довольно интересная штука. Получается, стек — это область памяти, которая, ты сказал, прогрета скорее всего больше всего. Мне интересно поподробнее понять: а почему именно эта память прогрета, за счёт чего? Почему вообще это стек, а не, не знаю, куча или очередь? Почему такая структура данных выбрана и почему она прогрета?

[14:36] Максим: В целом стек выбран потому, что, например, когда мы делаем вызов функции, мы кладём какие-то аргументы на стек, а когда выходим из функции — снимаем. То есть это натуральный стек получается: какие-то аргументы наложил, потом какие-то сбросил. А прогрета она как раз потому, что ты постоянно, когда нужно что-то аллоцировать на стеке, вызываешь функции, внутри функции — какие-то локальные переменные; очень часто стек используется. Почти в любой более-менее крупной функции стек приходится использовать, потому что банально может просто регистров не хватать, и когда их не хватает, компилятор обычно начинает аллоцировать память на стеке. Поэтому аллокация памяти на стеке по факту бесплатная. Она как бы всегда прогрета в том плане, что мы всегда что-то с ней делаем, всегда к ней обращаемся.

[15:18] Александр: То есть я так думаю, что вероятность того, что кусок стека, который нужен сейчас процессору, окажется в кэш-линии, сильно выше, чем любая другая.

[15:27] Максим: Да, мне кажется, стек почти всегда валиден в кэше. Единственное — если у вас какая-то безумная программа, где вы что-то аллоцировали на стеке, взяли на переменную указатель, пошли, вызвали ещё 40 функций, а потом обратились к этой переменной, — есть вероятность, что она уже не окажется в кэше. Но таких программ почти нет. Кстати, такой подход — что-то аллоцировали на стеке, потом куда-то указатель передали — нужно очень аккуратно делать, потому что когда мы уходим из функции, стек чистится, потом перезаписывается, и если вы по этому указателю пойдёте читать, вы, скорее всего, прочитаете мусор. Или иногда даже всё будет работать, вы прочитаете то же значение. Ну, короче, это просто баг.

[16:13] Александр: Так, про стек поговорили, про кэши примерно поняли, про процессоры, про регистры тоже. Ты хотел рассказать вопросик с интервью — я всё жду.

[16:23] Максим: Да, давай с интервью, перед тем как про более advanced-штуки в процессорах говорить. Вот, например, если спрашивают, почему итерация по ArrayList быстрее, чем по… я не уверен, как в Java это называется, просто по linked list, так скажем.

[16:34] Александр: Да, LinkedList.

[16:34] Максим: Вы можете сразу сказать: потому что кэши работают. В сценарии, где вы просто должны итерироваться по списку, можно считать, что каждый следующий фетч элемента — это всегда кэш-промах. Процессор там особо ничего prefetch’ить не может. А в случае, когда мы бежим по вектору, мы читаем этими кэш-линиями: прочитали кэш-линию — и буквально несколько следующих элементов тоже сразу читаем.

[16:56] Александр: У меня ещё простенький есть вопрос, из той же серии. А почему копирование ArrayList быстрее, чем LinkedList? Ответ, видимо, тот же самый.

[17:10] Максим: Да, ответ в принципе тот же самый. И что я ещё хотел сказать — эту тему мы обсуждали, но хочется проговорить явно. Мы обычно работаем на очень высоком уровне абстракции: пишем код на C++, Rust, Java, Go, и думаем, что вот мы написали код, вроде как нормально — нормальная архитектура, нормальные интерфейсы. Но процессору, как мы уже разобрались, на это вообще всё равно. Он просто будет исполнять ваш файл, который скомпилирован. Ему на вашу архитектуру всё равно, на качество и красоту вашего кода — тоже. Ему нужно, чтобы вы работали с ним так, как он хочет. Процессор — это некоторая абстракция, штука, которая выполняет ваши инструкции. Но в случае с процессором эта абстракция такая текучая — leaky abstraction, так иногда говорят. Вы должны понимать детали её реализации внутри, чтобы выжимать из ваших программ максимум.

[17:56] Максим: Давай, наверное, ещё расскажу про очень важную штуку — это prefetch. В современных процессорах, если ты будешь итерироваться по массиву, например int[100], ты будешь делать запросы к памяти последовательно. Процессор понимает, что ты, наверное, итерируешься по массиву, и затем будет делать prefetch следующих кусочков памяти, чтобы они у тебя уже были. Это на самом деле очень сложная технология. Насколько мне известно, у всех процессоров алгоритмы prefetch строго засекречены. Почему так? У современных процессоров эти алгоритмы умеют не просто когда ты линейно идёшь по памяти, а даже когда ты галопирующе идёшь, прыгаешь как-то — они даже в этом могут найти паттерны и сделать тебе prefetch. Но в целом самое надёжное — если ты условно последовательно обращаешься к памяти, то у тебя, во-первых, хорошо работает кэш, а во-вторых, работает prefetch. Про этот механизм тоже стоит знать, что он где-то там есть.

[18:12] Александр: А prefetch — это что-то типа асинхронного запроса в память? В то время как процессор выполняет какую-то инструкцию, уже идёт процесс кэширования следующих страниц?

[18:18] Максим: Да. Модель, про которую я рассказал в самом начале — что процессор выполняет одну инструкцию за такт, — неправильная. Процессоры, вообще говоря, могут выполнять много инструкций за такт, и у них всё устроено сильно сложнее. У них есть несколько условно декодеров, несколько арифметико-логических юнитов — тоже много. По факту в процессоре может быть, например, 4 арифметико-логических юнита, и одновременно вы можете делать 4 операции — потенциально 4 операции, например XOR, какие-то такие. На самом деле это можно увидеть только в каком-то очень интересном коде — который, например, делает сжатие данных или криптографию. Вот там такое действительно может происходить. Это код, который может начать упираться в CPU. Это, вообще говоря, редко бывает.

[20:08] Максим: Нужно представлять себе, что современный процессор не одну инструкцию выполняет. Он как бы смотрит наперёд и может делать некоторое спекулятивное выполнение. Он может смотреть вперёд, что у вас есть какое-то ветвление, и пытаться его наперёд выполнять. Если вы пишете какое-то ветвление, обычно лучше всего часть, которая чаще будет выполняться, в ассемблере расположить так, чтобы инструкции шли сверху, последовательно. Тогда у вас чаще всего будет branch проходить, и всё будет хорошо. Но если процессор запустил этот этап спекулятивного выполнения и неправильно выполнил if — этот if не сбылся, так скажем, процессор заранее не может это понять, — то в таком случае нужно делать какие-то операции: как-то пофлашить pipeline, всё откатить. Такая штука называется branch misprediction. Например, такой event можно в perf найти. Он не очень дорогой, но, по-моему, прилично дорогой: 3 или 5 наносекунд. Относительно тех порядков, о которых мы говорим, это прилично времени занимает. Про это тоже нужно думать: грубо говоря, процессор выполняет ваш код ещё и наперёд.

[20:55] Максим: Интересное практическое замечание: часто про это думать особо не надо, но есть кейсы, когда надо. Вот самый важный кейс. Например, вы написали код, и в нём — представим, что это процессор, — 4 инструкции; могу ли я выполнять их параллельно? Чтобы выполнять параллельно, они, скорее всего, должны работать с разными данными, в разных регистрах, и между ними не должно быть зависимости — dependency, как в мануалах пишут. Вы должны написать код так, чтобы этого не было. Тяжело придумать пример, потому что обычно за вас это старается делать компилятор. Именно руками это нужно было делать не так уж и часто, по правде скажу. Но бывала пара сценариев, когда в практике приходилось такое делать. В большинстве случаев можно считать, что компилятор сделает это за вас. Он очень аккуратно постарается весь ваш код зареордерить: инструкции, которые вы написали на высокоуровневом языке, он попытается зареордерить так, чтобы удовлетворить процессор, чтобы код выполнялся максимально быстро.

[22:15] Александр: Мне очень часто так стреляет — я, по-моему, даже в подкасте ни разу это не озвучивал, — что то, как устроен на самом низком уровне процессор со своими кэшами, эта абстракция, как с ней системные программы работают, безумно похоже на то, как мы пишем код для баз данных, как мы базу данных разрабатываем. Там тоже есть prefetch’и, например, если ты выполняешь граф запроса. Или транзакции. Ты сейчас сказал «причинно-следственные связи» — так это же serializable-уровень транзакции. То, как движки баз данных гарантируют нам serializable, — они говорят: чуваки, вы написали код на SQL, вы его одновременно выполняете, но для вас как будто бы вы одни в системе. И тут так же: ты написал код на Java, думай о нём, что он выполняется последовательно. Но по факту компилятор может так сделать, что некоторые части будут выполняться параллельно или произойдёт реордеринг. Тебя как программиста это не волнует, потому что у тебя есть договорённость с компьютером, что оно как будто бы вот так выполняется. И компьютер эту договорённость выполняет.

[23:24] Максим: Да, сейчас мы, наверное, будем ещё глубже погружаться. Мне аналогия твоя понравилась, я как раз думал про неё рассказать. Я даже скажу, что процессор — это настоящая распределённая система. Всё, что мы пока проговорили, — это уже нормальное представление о том, как работает процессор. И нужно ещё добавить то, что процессоров много. Когда процессоров много, у нас программы обычно многопоточные, и возникает много сложностей.

[23:47] Максим: Давай сразу первую сложность разберём. Есть такая штука в процессоре, называется протокол когерентности кэшей.

[23:53] Александр: Вот, интересно уже.

[23:55] Максим: Этот протокол — очень-очень сложная штука. И вообще говоря, нет опубликованных алгоритмов, которые реально в системах работают, — у процессоров про это не написали, это засекречено. Но есть протокол, который называется MESI. Это модель, в которой про это можно думать. Она говорит, что ваша кэш-линия на процессоре может находиться в четырёх состояниях: Modified, Exclusive, Shared и Invalid. Modified говорит, что кэш-линия находится в кэше процессора и она грязная. Exclusive — что она находится в кэше процессора, но она чистая. Shared — что она находится в нескольких кэшах процессоров. И Invalid — что она невалидная, то есть не используется.

[24:42] Максим: Я прямо в детали сейчас не буду заходить. Там нужно очень сложную машину себе представить — как процессоры должны между собой синхронизироваться, чтобы у них ничего не разломалось. Например, когда процессор хочет записать что-то в кэш-линию, он должен другим процессорам сообщить по шине, что эта кэш-линия теперь должна поменять своё состояние. И затем эти процессоры, когда будут читать, тоже должны читать из памяти. Это очень сложная штука, но про неё нужно знать очень часто. Это знание нужно, когда мы пишем конкурентные программы, пишем какие-нибудь примитивы синхронизации или используем их.

[25:23] Максим: Давай, наверное, я сначала приведу пример просто с кэшами, а уже потом немного с многопоточностью, потому что это немного разное. Чтоб сейчас от кэшей не убежать далеко.

[25:32] Максим: Хороший пример, с которого можно получить профит и который вообще не интуитивный. Представь, у тебя есть две матрицы, и ты хочешь их перемножить. Ты, например, не знаешь про всякие хитрые алгоритмы, а хочешь перемножить просто, строка на столбец — стандартный алгоритм перемножения матриц. Мы берём первую строку, первый столбец, перемножаем и получаем результирующую ячейку в первой строке, первом столбце, и так двигаемся. Если такой код напишешь наивно, с какой проблемой ты столкнёшься? Каждый раз, когда тебе нужно обратиться ко второй матрице, когда ты идёшь по столбцам, — а матрица это просто один большой кусок памяти, один большой массив, — тебе нужно вычислить offset. Мы говорим: нужна, например, пятая строка, пятая колонка. Мы должны понять, сколько всего колонок, умножить строку на это количество плюс прибавить колонку.

[26:29] Александр: Ну, offset вычислить.

[26:30] Максим: Да, вычислить offset в этом огромном continuous-массиве. И если делать это наивно, то у нас получается большая беда, потому что мы постоянно прыгаем в этом continuous-куске в разные места с огромными offset’ами — буквально на размер колонки. Хотя кажется, что код ты написал, алгоритм просто реализовал правильно. Но как это оптимизировать — будет очень неочевидно звучать. Для каких-то слушателей это очевидно, но мы можем транспонировать вторую матрицу, и когда умножаем — умножать строку на строку, потому что во второй матрице столбцы стали строками. Такая программа будет работать в 3–10 раз быстрее в зависимости от процессора. Мне этот пример чем нравится: мы сделали, кажется, какую-то странную вещь. Ты напишешь такой код, и если не напишешь комментарий, человек подумает: блин, а зачем он это делает, он делает лишнюю работу. «Сейчас я оптимизирую, уберу это транспонирование, кажется, оно реально бесполезное» — ведь затем мы просто итерируемся по матрице, что так, что так. Но результаты слушатель может проверить: написать код на C, C++, Rust, Java — разница будет колоссальная.

[27:44] Александр: Да, это очень хороший, показательный пример, как неочевидна может быть такая штука. И как раз тут абстракция работы процессора прям протекает, потому что мы должны знать, как работают кэши, и что последовательное расположение элементов в памяти сильно ускоряет работу. А кэш на уровне абстракции особо и не говорит, что надо вот так, что я транспонированные матрицы перемножу быстрее, потому что у тебя последовательные плюс последовательные. Ещё раз быстренько проговорю проблему. Две матрицы — это две плашки. Мы представляем, что одна плашка — это столбец первый, затем столбец второй, третий, четвёртый и так далее. Индексация первая по столбцу идёт сначала, и получается, что нужно делать длинные прыжки.

[29:02] Александр: Чем это плохо? Тем, что каждый прыжок, во-первых, сложно как-то prefetch’ить, во-вторых, это будет триггерить больше походов в оперативную память, потому что вся эта плашка, скорее всего, не уместится в кэше. И процессору сильно больше нужно приседаний делать, чтобы по факту выполнить такой же цикл, который в программировании выглядит что так, что так — мы i и j местами поменяли, и всё. Снаружи это выглядит абсолютно так же, но для процессора требуется сильно больше работы. И неочевидная оптимизация такая: давайте мы будем перемножение делать колонка на колонку или строчка на строчку.

[29:38] Максим: Строчка на строчку.

[29:39] Александр: Да, строчка на строчку, потому что по строчкам мы бежим быстро. А чтобы «строчка на колонку» превратилась в «строчка на строчку», нужно одну из матриц, вторую, транспонировать. Такая математическая операция равносильная получается — но насколько лучше процессору от этого становится?

[29:57] Максим: Намного лучше.

[30:02] Максим: Ещё забыл, но хотел сказать очень интересную историю про спекулятивное выполнение. Может, кому-то интересно, кто, может, security занимается: такие проблемы, как Spectre и Meltdown, которые обнаружили в Linux, — там довольно сложный сетап, но они как раз связаны со спекулятивным выполнением. Процессор мог прочитать память другого процесса или даже память ядра за счёт того, что в его кэшах аккуратно всё оседало. Это спекулятивное выполнение работало, насколько я помню, так: у нас было какое-то ветвление, и мы перед этим ветвлением всегда попадали в нужную ветку. Процессор начинал всегда спекулятивно её выполнять, а во время спекулятивного выполнения у процессора весьма много прав. И происходил security-issue, потому что процессор этот if уже не должен был выполнять, но там очень хитро сделано, что он почти всегда его выполняет.

[31:01] Максим: Это даже иногда нужно думать в контексте того, как security в операционных системах работает. Я в этой теме не так хорошо разбираюсь, но люди, которые security занимаются, могут почитать. Я когда эти примеры смотрел — это как бы голову сносит, как люди додумались так хитро код написать, чтобы это привело к уязвимостям.

[31:16] Александр: Да, про security, когда всё это случилось, я вообще тогда особо не понял. Я понял, что есть branch prediction, как он работает, но как его эксплуатировать — вот настолько надо хитро проникнуть, чтобы там… Представляю, насколько нетривиальный там код. Про branch prediction, кстати, я на себе заметил: последнее время, когда пишу горячие циклы и прямо осознанно понимаю, что здесь будет много итераций, сотни тысяч, я такой: так, а я любитель, знаешь, early return сделать отовсюду, откуда возможно. Из функций всегда проверяю: если невалидные входные или что-то — сразу return. И в циклах как-то по наитию тоже пишу вначале: если какое-то состояние такое, то всё, пошли отсюда, return. И потом я понял: так я же как раз misprediction делаю. Я в начале каждой итерации проверяю что-то, что чаще всего false, и процессор должен каждый раз это проверять. А один раз, когда это будет true, тогда произойдёт выход из цикла. И я подумал, что лучше, наверное, писать так, чтобы проверка всегда была true, а один раз false на выходе. Тогда у меня будет один branch misprediction вместо сотен тысяч. И я очень хотел померить это бенчмарками, потому что есть подозрение, что такие места — я чаще на Java пишу — JIT может осилить и перевернуть условие if, и оно будет работать что так, что так. Не знаю, надо проверить.

[32:43] Александр: Я таки написал простенький цикл на Java, и разницы в производительности действительно нет. По крайней мере, на моём примере.

[32:53] Максим: Мне кажется, операторы очень-очень часто это могут менять. Чтобы зафорсить, например, в Clang или GCC есть такая pragma likely или unlikely. Мы, кстати, её даже в C++ добавили — то ли в 17-м, то ли в 20-м. В Rust тоже, кажется, такое есть. То есть можно специально пометить. А если не пометить, то маловероятно, что он сам не попробует это как-то угадать, как тебе лучше.

[33:14] Александр: Ну да.

[33:16] Максим: Второй пример. Он как раз связан с конкуренцией, и в нём знание протокола когерентности кэшей может помочь. Из того, что я рассказал про этот протокол: мы хотим, чтобы у нас не было ситуации, при которой кэш-линии между процессами шарятся, когда нам это не нужно. Такая ситуация часто называется false sharing. Может быть такое: например, мы хотим написать counter. В ClickHouse, например, мы хотим смотреть количество запросов или количество доступов к какому-нибудь кэшу. На консистентность этого counter мы можем немного пренебрегать — например, если мы это в какой-нибудь Prometheus экспортируем, там можем немножко разъезжаться. Наивный способ: мы хотим написать counter, давай заведём Atomic.

[34:00] Максим: Atomic — если сейчас будем прям очень серьёзно разбираться, то много времени потеряем. Про модели памяти мы, наверное, лучше обойдём стороной. Скажу так: на уровне процессора Atomic — это просто то, что какие-то инструкции могут быть атомарны. Там есть ещё штуки, которые называются барьеры памяти, которые могут сказать процессору: вот этот код ты не пытайся… Со стороны человека это иногда выглядит как реордеринг, но со стороны процессора это обычно детали реализации того, как внутри процессора что-то устроено.

[34:37] Максим: Я приведу пример на x86, чтобы слушатели поняли проблему. Сразу скажу, что это довольно сложный пример, чтобы себе представить, но он покажет всю проблему, и после этого человеку, скорее всего, станет очень страшно.

[34:51] Александр: Давай, напугай.

[34:51] Максим: Представь, у тебя есть два потока. У тебя есть две переменные x и y, изначально они нули. Первый поток пишет в y единицу и читает из x в свой локальный x. Второй поток пишет в x единицу и читает из y в свой локальный y. Возможно ли, что получилось 0,0? В какой ситуации может получиться 0,0?

[35:16] Александр: Что первый сначала пишет, потом читает, да, оба?

[35:20] Максим: Да, первый поток пишет в y, читает из x в локальный x; второй пишет в x, читает из y в локальный y. У них прям инструкции друг за другом.

[35:30] Александр: Логически, если рассудить: когда он записал, потом прочитал, то между этими двумя действиями есть некоторая причинно-следственная связь — по очереди выполнил. Соответственно, когда ты один записал, а второй читаешь, то ты сначала единичку проставил, а нолик считать можешь, если ты первый поток, который это делает. То есть один нолик там точно может быть. Но если второй записывает единицу и потом начинает считывать, то он уже второй, соответственно, до него… Подожди, может ли он считать ноль? Он точно запишет единицу, а ноль считать он… Блин, слушай, что ж так сложно-то представить? Вроде там x, y и всё, два потока.

[36:18] Максим: Ты рассуждаешь сейчас в модели чередования.

[36:19] Александр: Да.

[36:19] Максим: Модель чередования выглядит так: ты берёшь свой код, скопипастил, два потока, на каждый поток поставил курсор и как бы пытаешься все варианты перебрать. В таком исполнении не получится — если так все варианты перебрать. Но что интересно: на реальной аппаратуре может получиться 0,0. И почему такое происходит? Эти переменные — ну понятно было, что мы вообще ни про какие атомики не говорим, это обычные четыре Long. Часто это люди объясняют как реордеринги: как будто бы у нас записи переехали за чтения. Ты визуально можешь себе это представить так, но на самом деле что у тебя произошло? Я скажу, как на x86 это работает.

[37:00] Максим: На x86 внутри тоже никто не знает, что происходит, это засекречено, но у процессоров есть такая вещь, которая называется операционная модель. Сейчас мы говорим про память — и вот это именно операционная модель памяти. Она говорит, как мы можем думать про то, как процессор работает, — даёт нам какую-то чёткую модель. Настоящий процессор работает безумно сложно, но мы используем эту операционную модель и можем понять. И на x86 операционная модель выглядит так — в ней, кстати, даже нет кэшей: есть только CPU, store-буфер и память. Store-буфер — это то, куда попадают записи. И они там могут зависать, пока мы их оттуда не сбросим. В нашем случае человек наивно говорит «reordering», типа записи как-то переупорядочились. Но по факту они попали в store-буфер и зависли там. И получается, что первый записал в y единицу, второй записал в x единицу, а дальше они прочитали нули — потому что записи вообще в память не попали. Они записывают в свои store-буферы, и это не флашится сразу.

[37:56] Александр: Да, это не флашится.

[38:00] Максим: А на ARM там вообще безумно сложно, разные кэши. Там разные ядра могут видеть записи разных ядер, там это вообще какой-то tournament получается. Этот тест, который я тебе сказал, очень простой, и в нём понятно, что что-то может пойти не так. Но есть тесты, которые прям очень сложно представить, что что-то может сломаться. Там прям с тремя потоками на ARM — слушатель может реально это загуглить — можно с ума сойти. По факту как раз для этого используются атомарные инструкции, которые, например, на x86 могут взять lock на кэш-линию, взять её к себе, потом пофлашить. И дополнительно у большинства процессоров есть ещё барьеры, которые позволяют сказать: сбросим store-буфер или сбросим эту кэш-линию. И процессор эти инструкции спекулятивного выполнения сквозь эти барьеры не может наперёд забегать и выполнять. Вот это внутри железа как-то сделано.

[38:57] Максим: А с точки зрения именно языков программирования, у каждого языка обычно есть декларативная модель памяти. И Java, кстати, по-моему, первый язык, у которого она появилась, — который объясняет это всё не с точки зрения операционного подхода. Потому что то, как работают эти барьеры, — это уже прям внутрянка, её понимать очень сложно, про неё думать невозможно. У разных процессоров она своя: например, на x86 я ещё хоть чуть-чуть разбираюсь, а на ARM вообще уже почти ничего не понимаю. И для этого в языках сделана вещь, которая называется модель памяти, и она отвечает на вопрос, какую запись видит какое чтение. Она даже звучит по-другому. Декларативная модель говорит «какую запись видит чтение», а операционная модель говорит «а вот процессор работает так» — он работает, как бы проинтерпретируя, и отвечает на вопрос, что будет. То есть слишком много вещей надо держать в голове, чтобы ответить, по сути, на тот же самый вопрос, нежели когда мы на уровне модели памяти рассуждаем.

[39:53] Максим: В модели памяти они все построены примерно одинаково. Модель памяти C++ безумно сложная, но если пренебречь consume-семантикой — есть у Atomic такая семантика, — то в целом она примерно похожа на Java. У нас есть, как ты говоришь, причинность внутри потока — это sequenced-before, ну там C++-семантика. В Java это happens-before. Получается, когда мы говорим про код внутри потока, у него есть связь sequenced-before. Но когда происходит взаимодействие через Atomic — там не только через Atomic, но и через другие примитивы синхронизации, например через Mutex, или когда мы thread запускаем и делаем thread join, — там тоже happens-before происходит. И это такой частичный порядок, который говорит нам, что если такая синхронизация произошла, то все чтения увидят все записи, которые были в том потоке.

[40:42] Максим: И дополнительно всего этого недостаточно — нужно ещё сделать синхронизацию, ввести частичный порядок, который в C++ называется что-то вроде total strong order, а в Java как-то так называется. Он говорит, что есть некоторый глобальный порядок записи и чтения между всеми атомиками в твоей программе и этими примитивами синхронизации. И в таком случае, если ты все эти частичные порядки соберёшь вместе в этой модели памяти, то ты сможешь — если ничего странного делать не будешь и используешь по дефолту всё — например, в Java Atomic это volatile-переменная, — рассуждать в модели чередования. Если для этих двух переменных ты поставишь volatile, то всё будет ок. Но это гарантия, которая в модели чередования работает, только если у тебя нет data race’ов.

[41:29] Максим: В случае с этим странным тестом: если мы эти две переменные поменяем на атомики, то у нас data race’ов не будет. Но изначально переменные — не атомики. По сути, именно атомики — это только для языка программирования, так скажем. Ты эти свои синхронизирующие переменные размечаешь, чтобы компилятор мог расставить нужные барьеры, которые нужны для конкретной операционной модели конкретного процессора. То есть это на самом деле контракт между программистом — как я пишу код, — компилятором — как он мой код компилирует — и процессором. Это очень-очень сложная вещь. Если бы мы решили про это поговорить, мы бы вообще закопались, можно было бы отдельный выпуск делать. Но я хотел просто немного рассказать, чтобы слушателям стало интереснее, что внутри там безумно сложно работает.

[42:15] Максим: Ну вот, например, в модели памяти C++ есть ещё разные гарантии, которые мы получаем в зависимости от того, какие операции с атомиками делаем. Там есть sequential consistency-семантика, acquire-release-семантика, relaxed-семантика, есть ещё consume-семантика — но она в большинстве программ не нужна, а из-за неё много сложностей в модели памяти.

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

[42:45] Максим: Да, давай расскажу. Как раз, кстати, на HighLoad, когда я рассказывал, как мы в YDB переводили код на ARM, мы с этим больше всего гребли. Потому что в разных процессорах, понимаешь, как бывает: есть декларативная модель, у которой все эти гарантии, она такая математическая, но есть реальный процессор, и на нём некоторые инструкции — математически семантика разная, но физически инструкция будет одна и та же. И ты можешь неправильно написать свой код синхронизации, но он скомпилируется всё равно в те же инструкции — просто потому что, например, на x86 только такие инструкции есть, а на ARM они другие. И когда ты начинаешь переносить свою программу, ты понимаешь, что люди, скорее всего, плохо в этом разбирались. Модели памяти появились в Java рано, мне кажется, в 2005-м, может, даже раньше; в C++ — в 2011-м. Но код же до этого надо было писать многопоточный, поэтому люди разбрасывали барьеры просто так, по приколу, очень сложные штуки делали. И пока нет такой модели, про которую можно думать, писать будет страшно.

[43:49] Максим: Как про это можно думать? Давай снизу вверх. Вообще, атомики, по-моему, до сих пор нерешённая проблема компьютер-сайенс — как они себя вообще должны вести. Но суть в том, что это гарантия, что мы имеем некоторую историю модификации значений на одном атомике, на одной атомарной ячейке памяти. В Java это volatile. Но volatile в Java имеет не relaxed-семантику, а sequential consistency, к которой мы потом придём. В C++ можно для оптимизации ослабить это до relaxed. И у нас есть эта история модификаций, и любой поток, который читает из этого атомика, прочитает какую-то подысторию. Не сказать, что это мощная гарантия, но на практике в большинстве случаев такую гарантию используют только для того, чтобы делать всякие счётчики. Например, ты делаешь какую-нибудь операцию типа fetch_add, и с теоретической точки зрения не совсем понятно, как это всё работает, но с практической — получается, есть какой-то счётчик, в котором есть некоторый рассинхрон, но он на практике работает.

[44:49] Максим: Тут нужно понимать: представь, я в одном потоке записал 10 — изначально был атомик 0, я записал 10. Прошёл час, я во втором потоке прочитал этот атомик. Скорее всего, я прочитаю 10, но модель математическая, она как бы не запрещает, что я прочитаю 0. Там ещё всякие странные штуки не запрещены, например, есть такая штука out of thin air и самоисполняющееся пророчество, где ты можешь написать какой-то странный код, но за счёт того, что модель математическая, там можешь получать странные результаты. Типа ты, например, никогда не использовал число 42 в своей программе, написал «если этот атомик равен 42, то прочитай значение из другого атомика» — модель памяти говорит, что ты можешь прочитать это значение 42, хотя его как бы нигде и не было. Ну и всё, в C++ такие программы вроде как просто забанены. Я этим всем интересовался пару лет назад, и на тот момент по крайней мере не было такой модели памяти, которая бы эти вопросы решала. Это уже отдельная тема.

[45:39] Максим: Relaxed на практике работает так, что, скорее всего, ты прочитаешь последнее значение, и можешь делать атомарные операции, например fetch_add — ходим к атомику, читаем значение и сразу прибавляем. Это будет такой счётчик, у тебя будет гарантия, что вроде как ты мог прочитать старое значение, добавил — и оно eventually должно сойтись. На практике оно нормально работает.

[46:01] Александр: То есть это очень похоже на eventual consistency, по сути, наверное, оно и есть в каком-то роде.

[46:05] Максим: С этими relaxed-атомиками на практике, я честно скажу, их можно использовать, только если тебе нужен счётчик. Я не помню, чтобы даже в ClickHouse мы их использовали для чего-то ещё. Они могут ещё использоваться в очень хитром коде, где ты синхронизируешься через другие атомики, тебе там нужно как-то избавляться от data race — скорее всего, это что-то сложное. В C++, кроме этих атомиков, есть ещё барьеры памяти, которые тоже нужны для каких-то своих сложных штук. Очень тяжело представить настолько оптимизированный код, где это понадобится. Relaxed говорит следующее: когда ты читаешь значение из relaxed-ячейки, ты прочитаешь на 100% что-то, что в ней было. Но не факт, что это то, что соседний поток туда записал мгновение назад.

[46:47] Александр: Да, ты будешь читать именно монотонную подысторию. Но ты не можешь прочитать прошлое.

[46:53] Максим: Тут, конечно, тяжело сказать «прошлое значение», потому что на них никакой синхронизации нет. Наверное, это неправильно говорить. Ты просто будешь читать какую-то монотонную подысторию — историю изменения этого атомика.

[47:01] Александр: Мне кажется, на этих атомиках, знаешь, можно что-то близкое к state-машинам писать, где нужно чего-то дожидаться и менять какое-то состояние, где тебе не нужно прямо сейчас 100%, а ты можешь на следующих 10 итерациях это увидеть, и тебе ок с точки зрения алгоритма.

[47:16] Максим: С практической точки зрения для такого лучше использовать acquire-release, потому что relaxed-атомики — понятная штука, понятно, что они делают, но с точки зрения математической модели ты не можешь про это рассуждать, потому что вдруг пройдёт 10 часов, а у тебя это значение не подъехало.

[47:33] Максим: На практике реально полезная — это acquire-release-семантика. И acquire-release-семантика как раз таки триггерит happens-before. Если ты, используя acquire-чтение, прочитал значение, которое было записано с использованием release-записи, это значит, что у тебя произошёл happens-before. То есть все записи, которые были в том потоке, ты их увидел.

[47:58] Александр: Все записи конкретно вот этой ячейки или вообще все?

[48:02] Максим: Все записи для любых ячеек именно в том потоке. Ты их увидишь, они как бы к тебе доедут.

[48:08] Александр: То есть даже если он писал в переменные без acquire-release-семантики, но затриггерил одну, то она затриггерит все?

[48:15] Максим: Да, именно так. Она затриггерит все, и это безумно важно, потому что компилятор синхронизацию вставляет только в точках синхронизации, а в остальных местах он может это как угодно реордерить, и процессор как угодно может реордерить — спекулятивное выполнение и всё такое. Потому что когда эта гарантия happens-before возникает, этот частичный порядок, ты видишь сразу все записи, которые там были. Произошла синхронизация — и эти чтения-записи ты можешь реордерить. Для процессора и компилятора очень важно иметь такую свободу оптимизации. То есть сложная вещь происходит именно на синхронизации этих атомиков.

[48:51] Максим: И последняя гарантия — это sequential consistency. Снизу вверх: relaxed даёт тебе modification order, acquire-release даёт modification order плюс acquire-release-семантику happens-before, а sequential consistency даёт дополнительно глобальный порядок чтения и записи во всех атомиках.

[49:15] Александр: Глобальный порядок чтения и записи во всех — то есть как будто бы… модель чередования?

[49:17] Максим: То, как ты про свой код рассуждал: у тебя, например, куча переменных, это атомики, ты запустил потоки, начал в них писать. Ты можешь про это рассуждать в модели чередования.

[49:26] Александр: То есть я могу рассуждать, что вот эта запись и чтение — как будто бы атомарная штука, как будто бы не существует кэшей?

[49:32] Максим: Да, ты можешь именно так рассуждать. И даже больше: ты можешь про это рассуждать, как ты у себя скопировал код в голове два или три раза — сколько у тебя потоков — и вот так вот курсорами идёшь. Грубо говоря, можешь делать шажок одним потоком, несколько шажков другими, все варианты перебрать — и это будет работать. Этот глобальный порядок между разными атомиками гарантируется только с использованием sequential consistency-семантики. И в Java он по умолчанию, когда ты используешь volatile-переменные. В Java пошли самым понятным путём — глобальный порядок, самый safe, безопасный. Программист может думать просто в модели чередования. Но это всё работает, только если у тебя нет data race.

[50:15] Максим: Data race как определение — это когда у тебя есть две операции взаимодействия с ячейкой памяти, где по крайней мере одна из них запись. То есть у тебя может быть два чтения — это не data race. А чтение-запись — это data race, запись-запись — data race. Но в декларативных моделях памяти data race — это когда у тебя происходит взаимодействие с ячейкой памяти неупорядоченно через happens-before. Дальше, понятное дело, ты никакие гарантии давать не можешь, потому что у тебя не было синхронизации через атомики, значит, ты мог что угодно прочитать, там всё разломано. Про это даже дальше нельзя рассуждать. Поэтому то, что тебе компилятор гарантирует — модель чередования или happens-before-семантику для acquire-release, — он гарантирует, только если у тебя нет data race в программе.

[51:00] Александр: Так, давай data race ещё раз проговорим. Что ты имеешь в виду, когда говоришь?

[51:07] Максим: Ну представь, ты создал два потока, и у тебя есть одна переменная — не атомарная, не volatile, как в Java, — и ты просто, например, прибавляешь в неё единичку. Ты можешь получить в результате один. Хотя ты вроде бы с двух потоков это прибавлял, но так будет, потому что ты сначала с одного потока прочитал из памяти, прибавил в регистр единицу, записал, — и произошёл data race, ты с другого потока прочитал, тоже прибавил единичку. Но ты прочитал нолик: первый поток уже записал единицу, ты должен был бы прочитать единицу, но прочитал нолик и опять записал единицу. То есть у тебя сложился data race. И в таких ситуациях ты про это думать вообще никак не можешь. Если у тебя есть такие обращения к неатомарным ячейкам памяти, где два или больше обращений и хотя бы одно из них — запись, всё, ты дальше про это думать никак не можешь, эту модель использовать не можешь.

[51:53] Александр: А, я понял, что ты имеешь в виду. То есть у нас есть это happens-before, есть некоторые гарантии, но они работают только в рамках этой модели. А выходим мы за эту модель, когда перестаём использовать атомики?

[52:06] Максим: Да, но на самом деле ничего сверхъестественного не происходит. Ты просто начинаешь видеть операционную модель процессора — что вообще в процессоре происходит. И на разных процессорах ты будешь видеть разные прикольные спецэффекты. Но с практической точки зрения мы в теории разобрались — там много деталей, но более-менее. С практической: relaxed я по крайней мере видел, как мы его в ClickHouse используем для счётчиков. Acquire-release — это уже понятная штука: у тебя есть какой-то порядок на одном атомике, и это часто используется, например, в lock-free-алгоритмах или в спинлоках. Понятное дело, это можно использовать, когда у тебя несколько атомиков, просто про это очень сложно рассуждать становится. Но когда у тебя есть, например, спинлок — поток, который взял lock, делает release; грубо говоря, есть атомарный bool, ты взял lock, записал в этот bool единицу, а когда делаешь release — пишешь ноль, тебе достаточно release-семантики. А тот поток, который приходит захватывать lock, пытается для этого значения сделать операцию exchange, которая меняет это значение на единицу и получает предыдущее значение. Такие операции — read-modify-write. Грубо говоря, ты и читаешь, и пишешь в одной атомарной операции. И атомики в языках программирования обычно дают тебе такую семантику. В Java же ты можешь ++ написать, как у volatile-переменной.

[53:27] Александр: Compare-and-swap есть, CAS.

[53:29] Максим: Да, есть ещё CAS, fetch_add. Это операции, которые и читают, и пишут. В большинстве случаев, когда говорят про декларативные модели памяти, рисуют всякие графы: fetch_add, или read-modify-write операция, будет являться и acquire, и release. То есть для себя она может сделать happens-before с тем, кто до этого сделал release, — два ребра может иметь в этом графе, может, даже больше. И для того, кто после неё читает, с ним happens-before произойдёт после того, как она запишет release. И вот для спинлока как раз этого достаточно: первый поток пришёл, сделал эту операцию, и когда следующие пришли делать acquire, они это увидели — они этот exchange увидели.

[54:11] Максим: Ну, в общем, acquire-release может сам принять happens-before, может произойти для этого потока с каким-то другим потоком, который сделал release-запись. И вот для спинлока этого достаточно. И для очень многих других простых примитивов синхронизации тоже достаточно. То есть одного атомика достаточно, чтобы написать Mutex, condition variable. Почти все самые базовые примитивы синхронизации можно написать с использованием одного атомика, а более сложные — с использованием Mutex и condition variable, которые внутри написаны с одним атомиком.

[54:48] Александр: Когда ты говоришь «атомик», ты имеешь в виду примитив языка программирования, на котором мы пишем?

[54:53] Максим: Да, атомик существует только в языке программирования, у него есть класс. В Java, наверное, есть атомик-класс, но вообще есть, например, AtomicReference.

[55:03] Александр: AtomicReference есть.

[55:04] Максим: Атомик — это именно конструкция языка программирования, которая даёт какие-то гарантии, когда ты в этот атомик читаешь и пишешь или делаешь read-modify-write операцию. А на уровне процессоров там уже операционная модель работает. Там ты про атомики не думаешь, ты думаешь про атомарные инструкции — это другой, более низкий уровень. И sequential consistency — это самая высокая гарантия. В целом она нужна, если ты хочешь рассуждать в модели чередования. С практической точки зрения это может быть полезно для каких-то сложных lock-free-алгоритмов, но на практике, по крайней мере из того, что я видел, например, в ClickHouse большинство примитивов синхронизации пишутся с использованием acquire-release-семантики. На этот глобальный порядок мы условно никак не закладываемся.

[55:54] Максим: В большинстве случаев примитивы синхронизации пишут люди, которые очень жёстко это всё оптимизируют, и поэтому очень редко тебе нужен sequential consistency. Наверное, он нужен. Гарантия sequential consistency именно на атомике может нечасто быть нужна, но эта гарантия распространяется ещё на все другие языковые конструкции — скорее не примитивы синхронизации. Например, ты создал thread, сделал thread join — эта операция триггерит именно sequential consistency. Модель гарантирует нам какой-то глобальный порядок join’а всех потоков. В Java это точно так. Про это тогда проще рассуждать, потому что рассуждаешь в модели чередования. А модель чередования самая естественная для человека, про которую вообще можно рассуждать.

[56:35] Александр: Да, да, да.

[56:43] Александр: Так, хорошенько мы прошлись. Вообще, если попросить человека что-то вынести из этой части подкаста и запомнить, то я бы, наверное, сказал так: понять вообще, откуда всё это взялось. Не как оно работает в конкретной ситуации — это сложно запомнить раз и навсегда, а потом всем ходить и рассказывать «сейчас я тебе расскажу acquire-семантику через пять лет после универа». Наверное, нет — придётся ещё раз прочитать, сходить освежить в памяти. Наш подкаст — это очередное освежение, за которым последует некоторое отложение части информации. Но что запомнить и понять довольно интересно, легко и просто — это то, чем люди мотивировались, зачем они вообще придумали эту модель.

[57:30] Александр: Меня всегда интересовал вопрос: когда я в Java спрашиваю про модель памяти Java, я вначале думаю — а какая модель? Вот есть процессор, есть память, вот он ходит, вот есть кэши — что вам ещё надо, какая модель памяти, она уже есть. А когда начинаешь глубже разбираться, понимаешь, что настолько сложно человеку представить, как оно работает, чтобы писать безопасный софт без багов, что нужно придумать какое-то промежуточное представление того, как это работает, чтобы человек мог рассуждать. Это как язык программирования: почему он появился — что человеку сложно писать на ассемблере, давайте будем на языке программирования. И тут что-то похожее, только: давай ты будешь думать про то, как устроена память, вот этими абстракциями, которые тебе ближе, с которыми проще думать. А я — компилятор, рантайм, язык программирования, что угодно — сделаю так, чтобы эти абстракции соблюдались со стороны процессора. Вот, мне кажется, это самая суть того, что мы обсуждали, потому что остальное — такие детали, я бы сказал.

[58:32] Максим: Да, именно так. Дополнительно можно сказать, что на самом низком уровне по сути решается задача — какую запись прочитает чтение. Это всё, что ты сказал, плюс: какую запись прочитает чтение, чтобы вообще человек про это мог рассуждать, не прибегая к тому, как работает процесс, как внутри железа, а просто используя эту математическую модель.

[58:54] Александр: Да, то есть ты говоришь: при каждом чтении, если что-то запутался, можно думать так — «так, я откуда сейчас читаю? Из условно локального буфера или из глобальной памяти?». Всё вокруг этого чтения строится, и дальше развивать вопрос: а если вот, а тот, кто…

[59:09] Максим: Локальный буфер, глобальная память и локальные буферы других процессоров ещё существуют. Вот эти три сущности — про них можно думать и понимать. Типа «я прочитаю из глобального, значит, читаю что-то ближе к первому уровню». Знаешь, вот даже так рассуждать немного сложновато. Когда ты пишешь примитив синхронизации, у тебя есть какой-то условно атомик, на котором ты синхронизируешь какие-то данные, и ты приходишь и думаешь: я читаю какую-то условную переменную, которая не атомарная. Для атомарной переменной тоже про это думаешь — а какую запись я могу увидеть? И ты понимаешь: окей, если я увидел то, что записал другой поток, значит, у нас там произошёл этот happens-before, значит, из других чтений я прочитаю, например, вот это. И так ты можешь развивать: я читаю из неатомарной переменной — окей, а с чем я синхронизировался? Значит, где-то с чем-то синхронизировался. Идёшь и смотришь: а с чем? Если ни с чем — у тебя data race. Если с чем-то — а кто записал в эту атомарную переменную, что тот поток записывал? Удобно именно так про это рассуждать, потому что ты идёшь от вопроса «а что я сейчас увижу вот в этой переменной, что я прочитаю».

[1:00:16] Александр: Мне кажется, отлично. Давай, наверное, пойдём дальше.

[1:00:24] Максим: Давай вернёмся к примеру с глобальным счётчиком. Мы так ушли, но про этот пример всё равно нужно рассказать, это стандартный пример. Вот представь, у тебя есть счётчик. Мы уже знаем, что такое атомик, наконец-то выяснили, поэтому теперь можем счётчик сделать как атомарную переменную, в которую новый поток приходит и прибавляет единичку. И вот все потоки ломанулись это делать. Но смотри, какая проблема. На низком уровне атомарная переменная требует, во-первых, какой-то синхронизации — на самом низком уровне там будут какие-то атомарные инструкции, это требует дополнительной синхронизации, там может быть какой-нибудь барьер в памяти. Ещё нужно понимать, что атомарная переменная находится в какой-то кэш-линии. То есть я эту кэш-линию должен затянуть к себе, и, скорее всего, в эксклюзивном доступе — потому что вдруг её кто-то другой будет менять. И эти кэш-линии начинают… Представь, много потоков приехали, она в одной кэш-линии. И они начинают просто эту кэш-линию между ядрами тягать, потому что каждый из них должен её поменять эксклюзивно, и все другие ядра должны это увидеть.

[1:01:33] Максим: Частая оптимизация — давай мы сделаем много атомиков. Мы сделаем, например, 16 атомиков, которые будут нашим счётчиком. И когда к нам приходит поток, мы возьмём идентификатор, похешируем его, и он попадёт в один из этих атомиков. Он делает добавление, прибавляет единичку к одному из этих атомиков. А когда мы хотим прочитать все значения нашего счётчика, мы идём по всем этим атомикам, читаем значения и прибавляем. Понятно, они могут немного разъехаться, потому что другие потоки приходили, что-то записывали, но в целом такой счётчик намного быстрее будет работать.

[1:02:10] Максим: Но тут нужно ещё одну важную вещь добавить. В языке программирования атомик — например, атомарная переменная в Java — у неё layout 8 байт. А ты хочешь, чтобы кэш-линия, с которой ты работаешь, всё-таки была твоя, и ты не хочешь в другие кэш-линии попадать. И обычно дополнительно добавляют padding. Для этого даже уже специальные конструкции в C++17 или C++20 появились. Такое сложное название — hardware_destructive_interference_size и hardware_constructive_interference_size. В C++17 появилось, и это значит, что там есть константы, которые говорят тебе, какой нужен offset между двумя объектами, чтобы у тебя не происходил false sharing, чтобы разные потоки не работали с разными объектами в одной кэш-линии.

[1:02:56] Александр: Прикольно. Я даже не знал, что такое есть — размер в языках программирования.

[1:03:00] Максим: А вторая — это hardware_constructive_interference_size. Это максимальный размер кусочка памяти, continuous, чтобы у тебя наоборот работал false sharing.

[1:03:13] Александр: А зачем он нужен? Чтобы синхронизировать как-то через это?

[1:03:15] Максим: Это может быть тебе нужно, когда, например, ты хочешь запаковать какую-нибудь структуру. Ты знаешь, что сейчас притащил эту структуру, записал что-то в атомик, у тебя она уже в кэш-линии есть, и ты можешь с ней сразу работать. То есть иногда тебе нужно это разделять, а иногда тебе нужно структуру гнать к себе, как наоборот одна кэш-линия.

[1:03:38] Александр: Ага, прикольно.

[1:03:39] Максим: В нашем случае мы могли бы воспользоваться hardware_destructive_interference_size и такой align у объекта сделать. Для разных процессоров там своя константа, но на x86 мы могли бы смело сделать padding в 56 байт — 64 минус 8. В кэш-линии размер 64 байта. После этого всё работало бы супер быстро. Грубо говоря, у нас такой должен быть layout: атомик 8 байт, массив атомиков — атомик 8 байт, 56 байт padding, атомик 8 байт, 56 байт padding. Таким образом каждый процессор берёт себе свой атомик — вычисляет как индекс массива — и забирает себе этот атомик плюс padding. Таким образом он не притягивает к себе соседние атомики.

[1:04:27] Александр: А что плохого случится, если он притянет? Он же их читать не будет.

[1:04:34] Максим: Смотри, если ты не будешь использовать hardware_destructive_interference_size или padding, то у тебя будет проблема false sharing: чтобы записать в атомик, тебе нужно притащить эту кэш-линию к себе, а в одной кэш-линии запакуется сразу 8 атомиков. Грубо говоря, 8 разных потоков могут эту кэш-линию пытаться таскать к себе.

[1:04:53] Александр: А, то есть мы-то знаем, что они модифицируют разные части кэш-линии, а для процессора это как бы одна часть, и они её всегда-всегда будут гонять.

[1:05:00] Максим: Да, false sharing — это серьёзная проблема, потому что она может возникать, знаешь когда? Вот представь, у тебя нет даже никаких data race’ов. У тебя есть, например, 8 Long. Ты запустил 8 потоков, и каждому из этих Long прибавляешь единичку.

[1:05:17] Александр: Так.

[1:05:19] Максим: У тебя всё будет тормозить. Они даже не атомарные, ты из каждого потока работаешь со своим Long, в разные не пишешь. Но без hardware_destructive_interference_size, без этого offset’а между двумя объектами, чтобы не было false sharing, всё будет тормозить. И, кстати, интересно, что в названии сделали: Destructive — это когда у тебя минимальный offset, чтобы избежать false sharing, а Constructive — это минимальный offset, чтобы у тебя был false sharing.

[1:05:49] Александр: Блин, прикольно. Я просто в последнее время многопоточный код, который писал, старался… Ну, я не то чтобы прям совсем горячие места программирую, поэтому, очевидно, это всё надо в бенчмарках смотреть. Но интуитивное представление было такое: а, да, вот сейчас я возьму массив, и каждый индекс массива — это отдельный поток, его кусочек данных, и он его будет фигачить, я вообще не буду заморачиваться о синхронизации, а потом в конце точно узнаю, что все работы закончили, этот массив схлопну и верну результат. Но получается, что я вполне мог как раз false sharing затриггерить, и в целом оно параллельное, но очень сильно друг другу мешающее.

[1:06:26] Максим: Да, без hardware_destructive_interference_size, без специального padding’а, у тебя всё будет ужасно тормозить как раз потому, что кэш-линии будут просто туда-сюда ездить между процессорами.

[1:06:36] Александр: А как это интересно у Java сделать? Мне кажется, у нас даже нет способа.

[1:06:41] Максим: Да, я не знаю, давай попробуем найти аналог hardware_destructive_interference_size. Слушай, я так быстро найти не могу. Наверное, тебе придётся реально бахнуть padding — прям посчитать.

[1:06:56] Александр: А padding же зависит от процессора, верно?

[1:06:58] Максим: Да, он зависит от размера кэш-линии, но если ты возьмёшь 128, то у тебя точно всё будет.

[1:07:02] Александр: А, то есть я возьму больше, не меньше — главное.

[1:07:06] Максим: Да, тебе главное не взять меньше.

[1:07:08] Александр: Супер. В следующий раз буду padding’и добавлять к своим Long и потом всем объяснять, что…

[1:07:14] Максим: В начале разговора я хотел про это рассказать, но, понимаешь, чтобы про это рассказать, тебе нужно знать, что такое атомик, кэш-линия, как работает процессор. Это первая история, которую хотел рассказать Максим, если что.

[1:07:24] Александр: Ещё забавно, что, когда мы начинали разговор, я хотел слушателям сказать: вообще говоря, реально иногда приходится код очень сильно усложнять. Когнитивная нагрузка от такого счётчика сильно-сильно выше. Тебе нужно реально понимать, что внутри происходит, зачем этот padding, что за массив. «Надо это всё удалить, какой-то дурак писал».

[1:07:45] Максим: Но интересно, что, например, есть такая структура данных — ring buffer. Она часто во всяких операционных системах используется как кэш, как очередь задач. И вот ты хочешь тоже, чтобы она работала атомарно, чтобы у тебя никаких мьютексов не было, хочешь lock-free-реализацию. Наивно можно сказать, что там нет локов, но у тебя есть какой-то глобальный прогресс, и даже если ты какой-то один из потоков остановишь, у тебя будет глобальный прогресс. Почему с мьютексами такое не происходит? Потому что если ты берёшь мьютекс и твой поток останавливают навсегда, то глобальный прогресс завершился. То есть lock-free стоит понимать так: это не значит, что там совсем нет блокировок, это значит, что дедлок сложнее или невозможно получить.

[1:08:29] Максим: Мне кажется, там есть две гарантии, которые важны. Есть ещё obstruction-free, это уже не супер важно. Есть две гарантии, которые во всяких сложных алгоритмах: lock-free и wait-free. Wait-free говорит тебе, что без разницы, что будут делать другие потоки, твоя операция, твоя функция выполнится за конечное число шагов. Это прям очень жёсткая гарантия, потому что, представьте, вообще без разницы, что остальные потоки делают. Вот, например, наш счётчик, который мы написали, по факту это lock-free-алгоритм. Потому что любая операция «добавить значение» — нам другие потоки никак не помешают это делать, мы за конечное число шагов это делаем. Но гарантия lock-free говорит немного другое: что у тебя будет глобальный прогресс в системе, даже если какой-то из потоков уснёт навсегда.

[1:09:19] Александр: Угу.

[1:09:20] Максим: Эта гарантия говорит тебе lock-free, потому что если ты взял lock, то у тебя уже всё, ничего не будет. Часто говорят, lock-free — это нет мьютексов. Но нет. Даже если у тебя есть спинлок, ты взял какую-то блокировку, и другие потоки, пока ты не отпустишь этот спинлок, зайти в критическую секцию не могут — всё, у тебя не lock-free.

[1:09:38] Максим: В lock-free чаще всего используется такая инструкция, называется CAS, compare-and-swap. Она реально даёт интуицию lock-free. Давай возьмём пример со списком. У тебя есть атомарная голова списка — кстати, в Java такой код даже будет multi-producer, multi-consumer. Такой можно написать lock-free стек Трайбера. Ну, это такой алгоритм, так называется. Как он работает? Рассмотрим только операцию push, операцию pop можно потом сделать. Кстати, операцию pop в языках типа C++ или Rust, где нет garbage collection, сделать очень сложно — там нужно применять всякие техники, а в Java весьма просто. Давай рассмотрим push. Мы прочитали голову, атомарно сделали чтение головы. Потом заходим в цикл. И операция CAS — у неё, знаешь, какая семантика: мы берём и пытаемся поменять ячейку памяти, если в ней во время операции находилось такое-то значение. Грубо говоря, нам никто не помешал это сделать, никто её не перезаписал. И в результате мы получаем предыдущее значение, которое мы увидели.

[1:10:36] Александр: Точнее, мы никого не перезаписали.

[1:10:38] Максим: Да, мы никого не перезаписали, и в результате обычно получаем предыдущее значение, которое было не наше. Мы заходим в цикл, делаем push, CAS и пытаемся: вот мы наш элемент аллоцировали, к этому узлу списка добавили ту голову, которую хотим подвести, теперь хотим голову поменять — вот так атомарно. И мы хотим эту операцию сделать, только если текущая голова — это та, которую мы прочитали до этого атомарно. Ну и всё. Если сделали — да, всё ок. Если CAS не удался, нам возвращается предыдущее значение. Оно всегда возвращается. Вообще говоря, удался CAS или нет — проверяется тем значением, которое было. Значение всегда возвращается — то, которое было на момент операции. Просто в языках программирования иногда есть такая обвязка, что и значение возвращается, и ещё возвращается true или false.

[1:11:28] Максим: Видимо, эта абстракция в языках на разных архитектурах может быть по-разному, потому что CAS — семантическая операция. Например, на ARM, если по-специальному их не компилировать, CAS в атомиках появился только с какой-то версии, а до этого там настоящий цикл: читается значение, пытается его поменять и смотрит, а не поменял ли его кто-то. Это скорее детали реализации, но суть в том, что можно считать, что оно возвращает и старое значение, и значение, которое было, когда мы попытались операцию сделать, плюс true или false — удалось или нет. И если не удалось, мы просто идём на новый цикл. Вот в этом стеке нам, например, голову не надо перечитывать, потому что нам вернулась новая голова, и мы на неё пытаемся заново.

[1:11:20] Максим: Но смотри, вот почему тут такой прям чистый lock-free. Если мы не смогли это сделать, значит, кто-то другой совершил это действие. То есть кто-то другой делает эту работу — значит, прогресс у нас в системе есть.

[1:11:26] Александр: Да, да. Получается такая красивая идея. Про это тоже можно думать, что CAS, когда он проваливается, — прогресс в системе есть. Потому что кто-то другой сделал этот CAS.

[1:12:36] Александр: Да, это как когда ты открываешь pull request, и всё нормально, а потом приходишь — а там конфликт. И ты такой: ну, по крайней мере, хоть кто-то что-то смержил, раз там есть конфликт.

[1:12:44] Максим: Интересно, что есть ещё CAS, например, в C++ добавится более оптимизированная версия, которая может тебе вернуть операцию false, когда тебе никто не помешал. Действие не удалось сделать, но тебе никто не помешал. Насколько я понимаю, это может быть связано с тем, что просто кэш-линию кто-то потрогал, и мы просто свалились — потому что кэш-линию, возможно, кто-то потрогал, себе утянул, и мы не смогли операцию сделать. То есть strong-версия на ARM будет этот цикл делать, пока прям точно операция не провалится. А weak-версия просто попробует один раз это сделать, и всё. Мне кажется, разница именно такая. На C++ есть strong- и weak-версия этого CAS, и strong может вернуть нам false, что действие не удалось, только если кто-то другой сделал действие; а weak может говорить, что действие сделать не удалось, но никто другой действие не делал.

[1:13:35] Александр: Ну, блин, в Java такого, по-моему, точно сейчас нет. Но прикольно, что ты думаешь: ну, CAS-CAS, что там ещё можно сделать? Compare-and-swap. А оказывается, можно ещё сделать так, что ты можешь — как бы это назвать-то? Не CAS, а надо вообще новое слово придумать для этого — когда ты это сделал и тебе никто не помешал, и ты такой: а, значит, я это точно сделал. Либо ты сделал, но тебе помешал, фиг его знает что, короче, ещё раз пробуй. В то время, когда ты делал, с кэш-линией что-то произошло.

[1:14:05] Максим: Поэтому там есть две версии, weak и strong, в C++. В Rust, наверное, тоже есть weak и strong. В Java, наверное, просто только strong.

[1:14:13] Александр: Наверное, да.

[1:14:20] Александр: Окей, так, мы сейчас на каком этапе? Мы вообще хотели про SIMD поговорить, но…

[1:14:24] Максим: Ну да, но мне кажется, у нас всё есть, чтобы сейчас про SIMD поговорить. Расшифровка: SIMD — это Single Instruction Multiple Data. Это некоторое расширение процессора, которое добавляет новые инструкции и новые регистры. Эти регистры широкие: они могут быть не 64 бита, как 8-байтовый регистр, а, например, 128-битные, 256-битные, 512-битные. И, работая с этими регистрами, дополнительно появляются специальные инструкции. В чём, собственно, профит? Представим, что у нас есть два массива одинакового размера — для простоты, — и мы хотим их сложить. Мы берём размер, двигаемся в цикле по нему и в результирующий массив записываем сумму первого и второго массива для соответствующих элементов, по индексу их достаём. Просто написать — и мы вырубаем автовекторизацию, про которую я расскажу потом, то есть компилятор сам иногда умеет SIMD-инструкции использовать.

[1:14:57] Максим: Такой код, скорее всего, компилятор заанроллит: попытается, например, разнести этот цикл на несколько операций. Он, например, 4 операции заинлайнит и будет итерироваться не по одному элементу, а по 4. Плюс индекс, по которому мы цикл пишем, он будет говорить index += 4. Это будет значить, что мы поработали сразу с 4 элементами. Зачем это нужно? Loop unrolling хорошо работает именно для суперскалярных процессоров, потому что мы можем полностью утилизировать pipeline, видим больше инструкций, и у нас могут быть инструкции, которые параллельно могут выполняться, — у которых пропускная способность больше, чем 1. Например, у нас 4 арифметико-логических юнита. То есть мы их можем все таким образом утилизировать.

[1:15:35] Александр: Я, кстати, про этот loop unrolling прикольную штуку видел недавно в коде. Был такой One Billion Row Challenge в Java-комьюнити, где нужно было запроцессить миллиард строк на Java. Народ соревновался, кто быстрее это сделает. Там такое скользящее окно надо было сделать, агрегаты посчитать по всей свежке. И победители, топ-10 алгоритмов, все использовали не i + 1, а i + 3, i + 4 — по нескольку операций делали в одном цикле. Не знаю уж почему там…

[1:16:39] Максим: Я знаю, почему. Потому что все эти топовые на GraalVM были написаны, а это ahead-of-time-компиляция, там JIT нет, соответственно, они руками делали.

[1:16:47] Александр: Всё, я даже сейчас додумался. То есть да, там код такой — ты смотришь, зачем здесь по 3 операции в теле цикла, если можно по одной просто инкрементить. А вот как раз за этим.

[1:16:56] Максим: Да, это в принципе полезно. Иногда даже самому приходится писать loop unrolling, но в большинстве случаев компилятор это сам делает. Это первая возможная оптимизация. Вторая — как раз использовать эти SIMD-инструкции. В Intel история этих SIMD-инструкций примерно такая: сначала появились MMX-инструкции. Для них не было специальных регистров, это просто были специальные инструкции, которые могут, кажется, работать с 8 байтами, и ты можешь с ними как-то аккуратно поработать. Затем появились SSE-инструкции, потом SSE2, SSE3, SSE4. Грубо говоря, эти instruction sets включают в себя всё предыдущее и добавляют что-то своё новое. И вот уже в SSE добавляется 8 XMM-регистров, 128-битных, и дополнительные инструкции, чтобы с ними работать. Там есть floating-point-инструкции, integer-инструкции и куча разных дополнительных. Суть в том, что эти инструкции позволяют тебе работать с этим широким регистром за раз.

[1:17:54] Максим: Это может быть очень полезно. Представим, у нас есть 4 Integer. Integer — это 4 байта, то есть в 128-битный регистр можно засунуть 4 Integer. И мы сразу можем найти инструкцию, которая возьмёт два таких широких регистра и сложит их. Одной такой инструкцией. Это будет работать в лучшем случае в 4 раза быстрее. На практике в 4 раза не получается за счёт того, что если просто даже цикл заанроллить, там будет instruction-level параллелизм, про который мы говорили, что инструкции будут параллельно выполняться. Там x4 не будет, но на практике x2 точно может быть. Сейчас мы говорим просто про наивный алгоритм. Теперь можно ещё дополнительно взять и заанроллить этот цикл. До этого мы анроллили цикл и использовали простые инструкции — просто писали в эти переменные. Теперь можем заанроллить цикл и использовать SIMD-инструкции. Давай возьмём int[]. За одну SIMD-инструкцию мы обрабатываем 4. Мы можем 4 раза эту операцию заанроллить, и получится, что одновременно мы будем обрабатывать 16 элементов.

[1:18:56] Максим: Если ты просто включишь автовекторизацию в своём проекте, обычно результат сильно хороший — в 2, 2,5, 3, даже, может быть, 4 раза улучшение для каких-то циклов. Именно для таких наивных. Я пока не говорю про SIMD-алгоритмы, про это ещё потом скажу. И затем появлялись AVX. Сначала AVX просто, потом AVX2. AVX даёт возможность работать только с floating-point-инструкциями, поэтому он не супер полезный: Integer-ов всё-таки больше, чем float-ов, чаще в программах на практике работают с Integer, чем с float. И вот потом AVX2. AVX2 уже умел работать с Integer. Он добавил кучу инструкций и ещё кучу регистров: добавились YMM-регистры, их 16. И любой YMM-регистр может ещё работать как XMM-регистр. То есть 128-битный широкий регистр является половинкой большого 256-битного регистра, и он может исполняться и как тот, и как другой, в зависимости от ситуации.

[1:20:00] Максим: И это AVX2. Там, кстати, добавились ещё всякие интересные инструкции — про которые я потом расскажу, про SIMD-алгоритмы. И затем AVX-512. AVX-512 — это технология, там есть 32 регистра, ZMM-регистры. ZMM-регистр может быть как YMM-регистром, так и XMM-регистром. А YMM-регистр — это половина ZMM-регистра, который до этого был в AVX2. И там ещё больше всяких интересных инструкций добавили именно для SIMD-алгоритмов. Теперь, наверное, можно рассказать про эти SIMD-алгоритмы, что это вообще за зверь. Может, какие-то вопросы к тому, что я сейчас рассказал, чтобы уже к более сложному приходить?

[1:20:42] Александр: Да-да-да. Если не запоминать все эти названия…

[1:20:44] Максим: Ну, так.

[1:20:46] Александр: …то мы сейчас говорим о том, что появился ряд регистров, которые шире, чем обычные, в 2–4 раза.

[1:20:55] Максим: В 2, в 4, в 8 раз.

[1:20:59] Александр: Соответственно, мы можем в них положить пропорционально больше данных — насколько они больше. И помимо того, что можем больше данных положить, мы можем и специальные инструкции на них исполнить, которые недоступны на обычных регистрах. И тогда мы можем, например, 4 Integer положить в один этот большой регистр и сказать: вот тебе один такой регистр, вот второй, сложи их. Но сложи их не как ты складываешь обычные регистры — 2 плюс 2, 4, — а сложи, как будто бы это два массива из четырёх Integer, и каждый между собой сложи. И получи 4 числа, сложенных попарно. Семантика операции ADD другая на этих регистрах: мы не интерпретируем этот большой регистр как большущий Long, и вот этот как большущий Long, и получаем третий большущий Long. А мы векторную операцию выполняем.

[1:21:46] Максим: Да. Это позволяет сделать более эффективную обработку чисел, float-ов. И ещё плюс к этому мы можем размножить эти операции: если мы в цикле, то есть 4 таких штуки делать. И если у нас несколько этих арифметико-логических устройств с поддержкой таких инструкций, то они тоже параллельно могут выполняться.

[1:22:07] Александр: Да. И мы ещё на 4, условно, уровень параллелизма можем увеличить. Таким образом, x16 в идеальной среде можем достичь; на практике, наверное, x7 плюс-минус можно получить.

[1:22:18] Максим: Да, на практике чётко x16 не получается, но получается обычно неплохо. Просто компиляторы обычные-обычные циклы анроллят, и на текущих процессорах суперскалярная архитектура, то есть instruction-level параллелизм, — там x4 не получается, но x2 почти всегда смело можно сказать бывает. И вот как раз я хотел дальше перейти к тому, что под эти инструкции существует ряд алгоритмов, семейство алгоритмов, которые заточены исключительно для того, чтобы в такой модели работать, и они перформят по крайней мере лучше. И в базах данных это, наверное, чаще всего — я думаю, может быть, в каком-то computer vision реже, может, где-то ещё в ML, но в базах данных, то, что мне ближе и про что наш подкаст, эти алгоритмы используются довольно часто и агрессивно. В такой базе данных, как ClickHouse, это используется.

[1:22:56] Александр: И, собственно, понимание того, как они работают, может помочь нам, разработчикам, писать более оптимальные запросы и организовывать наши данные более оптимально, чтобы движки баз данных процессили их сильно быстрее. Про это мы, наверное, поговорим в следующей части.

[1:22:54] Максим: Да, я хотел ещё дополнительно сказать, что обычно, например, ты используешь SSE4.2, но решил перейти на AVX2 — регистр в два раза больше. Обычно такой переход даёт x2 или x1,5 — то, что я видел на практике, по крайней мере, у нас в ClickHouse. Перед SIMD-алгоритмами я, наверное, лучше всё остальное разберу, потому что это отдельная тема в бок.

[1:23:42] Александр: Давай.

[1:23:48] Максим: Хорошо. Это мы обсудили. Теперь я хотел обсудить два вопроса. Первый — вопрос автовекторизации. Второй — вопрос портируемости. Во-первых, автовекторизация. В компиляторах есть два вида векторайзеров. Например, в Clang есть SLP-векторайзер и Loop-векторайзер, по-моему, как-то так называется. SLP-векторайзер умеет векторизовать операции, даже если они не циклы. Иногда бывает так, что у тебя есть в коде какой-то паттерн: структура из четырёх Integer, и ты каждому из них зачем-то прибавляешь единичку. Он это поймёт и возьмёт offset этой структуры — так как мы вначале сказали, что в структуре данные лежат continuous. Даже в Java они continuous: если там объект, то там указатель куда-то в другое место, но данные всегда в структурах continuous лежат, последовательно, во всех языках. И компилятор понимает, что он может взять указатель на структуру, прибавить к нему offset, и вот эти четыре Integer, что дальше, сложить в SIMD-регистр — в зависимости от того, SSE4.2 это или AVX2, сколько там Integer-ов помещается, — и, например, прибавить к ним единичку. Компилятор в целом может даже использовать SIMD-инструкции в обычном коде, который не похож на цикл. Это первое, что я хотел сказать.

[1:25:06] Максим: Второй кейс — это когда всё-таки ваш код похож на цикл. Там всё очень сложно. Закладываться можно только на то, что компилятор очень простые циклы будет анроллить. Прям супер-супер-супер простые. Сложные циклы компиляторы до сих пор не анроллят, и у компиляторов есть диагностики на этот счёт. Можно попросить компилятор рассказать тебе loop-vectorizer-path, попросить рассказать, что он там что-то не анроллит. Он обычно там сложные ошибки пишет, но с опытом понятно, что там какую-то переменную или if какой-то был внутри цикла, и у него там что-то не срослось.

[1:25:40] Максим: Плюс часто бывает так — пример чисто из практики. У нас в ClickHouse был такой агрегат sum: просто есть массив чисел, мы хотим их просуммировать. У структурки, класса sum, было поле sum — результат. Она принимает этот массив и хочет результат записать. Был написан цикл по этому массиву, который суммировал в этот член класса. Но компилятор не векторизовал такой цикл, потому что он внутри себя почему-то не мог доказать, что это безопасно делать. Он такой цикл не понимал, как векторизовать, потому что не понимал, видимо, может ли произойти что-то с этим членом класса не то — может ли его что-то поменять, какая-то dependency, не совсем мне понятно, но такой сценарий не векторизовался. И решение было такое: взять этот Integer, эту переменную, вынести в функцию как локальную переменную, просуммировать всё в неё, а потом эту локальную переменную просуммировать в член класса. И вот уже в таком кейсе компилятор это мог векторизовать.

[1:26:38] Максим: Я скорее говорю про то, что это очень тонкая материя — сможет ли компилятор векторизовать конкретный цикл и будет ли вообще это делать, потому что в некоторых случаях ему нужно какие-то сложные инструкции использовать, которые в его модели стоимости, кажется, лучше не использовать. Поэтому на автовекторизацию лично я считаю, что нужно закладываться. В Clang единственный минус — что пока нельзя точно сказать компилятору: если ты этот цикл не смог векторизовать, кинь ошибку, не компилируйся. Я делал pull request, чтобы это добавить, но потом к нему уже не возвращался — возможно, нужно вернуться. Функциональность в проектах типа ClickHouse очень полезная, потому что у тебя могут быть циклы, которые ты must have хочешь векторизовать. Если оно не векторизуется, у тебя серьёзная просадка по перфу. Тот пример с суммой, когда мы его векторизовали, там вообще всё летать начало. Представь, сколько людей считают сумму в ClickHouse — просто агрегат sum, без GROUP BY: SELECT sum какого-нибудь счётчика из таблицы. То есть просто массив данных из таблицы, которые нужно просуммировать.

[1:27:44] Максим: Ещё почему нужно на это закладываться. Есть такой момент: если ты делаешь loop unrolling руками, простые циклы, ты приходишь к непортируемому коду. Вот, например, у тебя есть SSE4.2. Ты взял этот цикл и заанроллил его руками — просто позвал эти intrinsics в C++, которые эти регистры из себя представляют, какую-то библиотеку заиспользовал (может, в Java что-то своё, в Rust своё, в Go своё). Ты это заиспользовал, но теперь заложился, что у тебя код x86 с поддержкой SSE4.2. Хочешь AVX2? Ты заложился, что это код AVX2. Или когда тебе нужно переезжать под ARM, у тебя просто этот код не компилируется, потому что его не компилятор автовекторизовал, а ты. Это очень плохо, это прям очень тяжело может быть потом для переезда на другие архитектуры. Я бы не сказал, что это часто бывает, хотя в последние годы, кажется, всё-таки часто, потому что ClickHouse переезжал на ARM, и YDB переезжал на ARM. Наверное, есть тенденция, что люди будут переезжать на ARM, и у тебя действительно будут возникать такие проблемы.

[1:28:43] Максим: Плюс, когда ты сам это всё руками векторизуешь, ты можешь банально какой-нибудь баг допустить. Говорят, даже если ты просто по интернетикам код пишешь, он всё равно получается сложным. Это то же самое, что ты делаешь unrolling руками: например, теперь индекс увеличиваешь, но когда ты векторизуешься в цикле, например, на 4 или на 16, тебе нужно очень аккуратно обработать хвостики. Нужно не забывать про это, потому что у тебя есть массив, а мы идём по 16, а у тебя 17 элементов — ты хвост не обработал. Там всегда нужно обработку хвостика добавлять.

[1:29:10] Максим: Потом ещё компилятор дополнительно — вы, например, написали цикл, он дополнительно для аргументов, массивов, которые к нему приходят, проверяет, что они не оверлапят. Это тоже может быть дополнительная проверка, как векторизовать это безопасно. В C++, по-моему, есть restrict. Он говорит, что этот указатель ни с каким другим указателем внутри этой функции не пересекается, когда ты с ним работаешь. Это на самом деле очень важная штука, потому что оверлаппинги указателей по дефолту компилятору — это тоже полезно размечать, чтобы он понимал, что это можно векторизовать. Но это для более примитивных компиляторов. Для Clang вроде как такое не нужно, потому что он прямо в начале функции может дополнительный код вставлять — который, кстати, если ты напишешь restrict, уйдёт. Поэтому тебе всё равно полезно писать restrict. Но этот код проверит размер этих массивов, с которыми он дальше в цикле работает, посмотрит, оверлапятся они или нет. Если не оверлапятся — всё ок. А если оверлапятся, то оно перейдёт на наивную реализацию, где мы просто итерируем всё по циклу.

[1:30:06] Максим: С автовекторизацией я просто считаю: надо на неё закладываться. Нужно немножко ещё в компилятор инструментов добавить, чтобы точно быть уверенным, что оно всё-таки будет векторизовано для mission-critical приложений типа ClickHouse. А так в целом это хороший инструмент, потому что в очень большом количестве сценариев у тебя всё-таки циклы простые, их векторизовать компилятор может.

[1:30:26] Александр: То есть автовекторизация всё-таки есть, но довольно редко срабатывает, реже, чем нам хотелось бы и как бы мы ожидали от системы.

[1:30:34] Максим: Ну да, у неё есть какой-то набор паттернов.

[1:30:38] Александр: Можно прямо зайти — SLP-векторайзер, который не с циклами, у него есть набор паттернов, когда он срабатывает, когда там обычная инструкция, но он понимает, что тут можно заиспользовать SIMD-инструкции. И в циклах, Loop-векторайзер, у него тоже есть набор паттернов, которые он умеет векторизовать. То есть он понимает: вот я этот цикл векторизую, буду использовать вместо обычных инструкций векторные, SIMD-инструкции. Но есть набор паттернов, которые он просто не может векторизовать, а человек может.

[1:31:03] Максим: Плюс всё, что связано с SIMD-алгоритмами, — это сразу out of scope, потому что они обычно очень хитрые, tricky, и компилятор так просто не умеет делать. Они прям очень часто специализированные, хитренькие, поэтому их нельзя обобщить.

[1:31:19] Александр: Ну и давай тогда к SIMD-алгоритмам.

[1:31:22] Максим: Да, только вот сначала про portability расскажу. Про portability важно понимать следующий вопрос. Когда мы говорим про языки типа Java или Go, там тебе на portability в принципе пофиг, потому что она как бы из коробки.

[1:31:36] Александр: By design.

[1:31:38] Максим: Да, она by design, там, где архитектура поддерживает компилятор Go, а для Java есть виртуальная машина. Виртуальная машина Java наверняка есть на меньшем количестве архитектур, чем, например, поддерживает GCC — он поддерживает даже архитектур намного больше, чем Clang, всяких экзотических. Поэтому в каком-то смысле portability там, где есть Java. Но суть в том, что для архитектур, которые на практике почти всегда используются, — то есть не какие-то IoT, а обычные x86, ARM, Linux, Windows, macOS, — Java даёт хороший уровень абстракции. Но мы сейчас конкретно говорим про SIMD-инструкции, поэтому это скорее будет разговор именно про процессоры.

[1:32:11] Максим: И вопрос такой. По дефолту ты хочешь использовать какой-то приличный instruction set, но хочешь, чтобы в целом большинство современных процессоров его поддерживало, и не хочешь какие-то процессоры исключать — не сильно старые. В ClickHouse по дефолту используется SSE4.2, и, насколько мне известно, в Google тоже: весь Google компилируется с SSE4.2. В целом это золотой стандарт, с чем компилироваться, если хочешь более-менее портируемо использовать хоть какие-то SIMD-инструкции. Ты используешь SSE4.2 и доволен. Но не совсем: мы же говорили про AVX2, про AVX-512, и хочется их использовать.

[1:32:53] Максим: Но чтобы их использовать, ты не можешь просто написать AVX2-инструкции, потому что если ты в это место в коде придёшь и попытаешься эту инструкцию выполнить, процессор тебе кинет interrupt, illegal instruction, и всё, твоя программа упадёт. Такой инструкции просто у процессора нет: он попытался её декодировать, у него не получилось. И для этого есть техника, называется CPU dispatch. Она часто используется в очень-очень высокопроизводительном коде: например, во всяких библиотеках сжатия данных, в библиотеках, которые работают с аудио, видео, изображениями. По сути, твоя программа на рантайме спрашивает у процессора, используя CPUID — на x86 есть специальная такая инструкция, — а что ты поддерживаешь? Поддерживаешь ли ты, например, SSE4.2, AVX2, AVX-512? Ты спросил, процессор сказал: я такое-то использую.

[1:33:43] Максим: Но что ещё хочется? Хочется, чтобы тебе не нужно было руками для простых циклов — ты хочешь, чтобы всё работало из коробки. Вот представь простой цикл, который суммирует два массива, пишет третий. Ты хочешь, чтобы он был автовекторизован, и ещё хочешь, чтобы у тебя было portability. Кажется, что ты хочешь слишком много. Но на самом деле это можно сделать. В ClickHouse мы это делали, и я переделывал — у нас там изначально была реализация, которая умеет такое поддерживать, но я прямо из этого сделал полноценный фреймворк для CPU dispatcher.

[1:34:21] Максим: Как это в принципе работает? То, что ты можешь процессор спросить, поддерживает ли он SSE4.2, AVX2, AVX-512, мы разобрались — просто if поставил, спросил процессор. Второй момент: после этого if ты должен прыгнуть в функцию, которая скомпилирована с AVX2. То есть у тебя весь код скомпилирован без AVX2, но одна функция скомпилирована с AVX2.

[1:34:46] Александр: Так, ну такая специальная.

[1:34:46] Максим: Да, специальная функция с таким циклом. Это можно сделать, компилятора можно попросить скомпилировать. На самом деле это, конечно, для тех, кто на Java, жутко звучит — попросить компилятор скомпилировать свою функцию с другим instruction set. Но такое реально делают, мы в ClickHouse так делаем. Ты можешь компилятора попросить: а вот скомпилируй мне эту функцию с AVX2. Окей, он эту функцию компилирует, но ты её ещё обязательно компилируешь с дефолтным instruction set, например с SSE4.2, — чтобы у тебя была дефолтная ветка, в которую ты прыгнешь. Дефолтная реализация этой функции на тот instruction set, на который твой бинарник по дефолту распространяется. И обычно, например, я хочу AVX-512, AVX2 и SSE4.2 — такой dispatch сделать. На самом деле этот dispatch — мы сейчас говорим в контексте SIMD, но в контексте всяких библиотек сжатия, криптографии они иногда проверяют просто интересные им инструкции: например, есть BMI-инструкции, ещё какие-то интересные, которые они могут заиспользовать. И они могут какие-то функции dispatch’ить даже не по AVX2, а по какой-то нужной им инструкции. Это я так в сторону сказал.

[1:35:52] Максим: И, собственно, у нас получается так. В бинаре три версии функции, которые скомпилированы из AVX2, AVX-512 и SSE4.2. И после того, как мы это скомпилировали, мы вставляем if, там switch по архитектуре, которую мы спрашиваем у процессора: ты поддерживаешь AVX-512? Если да — прыгаем в эту реализацию. Если AVX2 поддерживает — прыгаем в AVX2-реализацию. Если SSE4.2, наш дефолтный, — фолбечимся на дефолтную реализацию.

[1:36:19] Максим: Тут ещё нужно сказать, какие проблемы у такого фреймворка с точки зрения реализации. Ты хочешь функцию написать один раз. Ты не хочешь скомпилировать её три раза. И ты ещё хочешь, чтобы функция поддерживалась, чтобы её можно было не делать статической, чтобы она работала как член класса, чтобы её можно было помечать внутри члена класса. И в C++, конкретно в фреймворке, который я делал для ClickHouse, это делается через макросы. И ты ещё хочешь, чтобы функция поддерживала шаблоны, обязательно. Короче, там конструкция получается интересная. Помощь от компилятора можно получить, если ты её напишешь прямо перед функцией. Но шаблоны находятся ещё раньше. То есть ты хочешь воткнуть свой код до шаблонов, перед функцией, а после этого сделать тело функции.

[1:37:11] Максим: Сейчас я даже точно скажу, как я это делал. Я разбивал функцию на её заголовок — то есть header, где могут находиться темплейты, — её имя, которое ты подсовываешь, и прямо перед именем функции нужно помощь от компилятора попросить, и её тело. Выглядит это так: ты говоришь, что у тебя есть multi-target функция — функция, которая будет и с AVX2, и с SSE4.2 работать. Ты отдельно в макрос заворачиваешь её header, отдельно её имя, отдельно её body. И затем эту функцию несколько раз клонируешь, и к имени — зачем имя отдельно делать — ты хочешь ещё к имени дополнительно добавить, с каким instruction set она работает. И затем у тебя такой код, который делает dispatch, — это отдельная функция. Она обычно проверяет: если поддерживается AVX2, прыгаем в реализацию с AVX2; поддерживается AVX-512 — прыгаем в реализацию с AVX-512; если не поддерживается — прыгаем в дефолтную реализацию. Вот так оно работает.

[1:38:06] Максим: На самом деле этот pull request, который я это делал, — не считая того, что там эти макросы, — фреймворк реально довольно удобный. Ты видишь функцию, которую хочешь векторизовать, приходишь в неё, закручиваешь её в этот макрос, делаешь функцию с таким же именем, которая делает dispatch, и всё. То есть функция с таким же именем просто сделает эти if-ы, switch по архитектуре, и сделает dispatch в нужную тебе версию. И это прекрасно работает. Но а как найти места, которые улучшатся? Как найти циклы, которые потенциально ты хочешь вот так обернуть, куда это вставлять?

[1:38:43] Максим: В ClickHouse я это сделал так. У нас были performance-тесты, и я взял и скомпилировал ClickHouse по дефолту с AVX2 вместо SSE4.2. И после этого я увидел тесты, которые начали работать быстрее. Это значит, скорее всего, где-то там цикл спрятался внутри. Если я его скомпилирую с AVX2, я получу тоже ускорение, только руками. И вот я все такие места в ClickHouse нашёл и туда эти макросы запихал.

[1:39:09] Александр: Мне интересно, что твои коллеги думали. Ты пришёл с вот этой штукой: я тут какие-то места…

[1:39:15] Максим: Все обрадовались, там улучшения были прям очень крутые. И, знаешь, самое интересное для меня открытие было, что одна функция — обычно это функция в ClickHouse, которая работает с колонками и в результате возвращает колонку, в ней всегда какой-то цикл кроется по колонкам, — одна из таких функций, по-моему, round_duration или что-то такое, ускорилась в 7 раз. Ты думаешь, с чего ускорится в 7 раз, если все остальные ускорились — реально, например, когда мы с SSE4.2 на AVX2 переходили, у нас dispatch был между AVX2 и SSE4.2 — все функции ускорились в 1,5–2 раза, 2,5 раза, а вот одна — в 7 раз.

[1:39:54] Максим: Эта техника лучше всего работает, когда функция… Ты полагаешься на автовекторизацию. И компилятор, когда понимает, что у него, например, instruction set AVX2, а в AVX2 есть специальные дополнительные инструкции, которых нет в SSE4.2, которые могут что-то хитрое сделать, более сложную операцию, — компилятор может эту инструкцию заиспользовать, и за счёт этого у тебя просто… Представь, у тебя там был внутри цикла if какой-то, ещё что-то, ещё что-то, и он это всё сжал в одну инструкцию. У тебя там pattern, if какой-то, потом set, например, или что-нибудь такое. И вот он придумал, как это векторизовать одной инструкцией, которая есть именно в AVX2, и получил x7 profit.

[1:40:33] Александр: Прикольно. Тут тоже очень интересная тема, что между instruction set’ами появляется много новых инструкций, и, знаешь, все инструкции держать в голове — нужно быть прям серьёзным SIMD-программистом: типа, о, блин, у меня тут AVX2, но тут я так не могу сделать, а если я на AVX-512 решу это сделать, то там есть специальная инструкция, тут мне нужно как-то её по-другому выражать. А компиляторы простые вещи, конечно, могут делать, но они всё равно это сделают за тебя.

[1:40:59] Александр: У меня есть вопрос, возможно, он ясность не внесёт, но мне интересно. Вот этот код я видел, по-моему, в лекциях у Энди Павло. Если ты не смотрел — про SIMD или про JIT, — очень похожий код я видел из ClickHouse. Я потом в него пошёл, и там, по-моему, даже ты автор pull request был.

[1:41:18] Максим: Я есть в лекциях Энди Павло.

[1:41:20] Александр: Да-да-да. Если ты смотрел лекцию про хэш-таблицу, там есть ссылка на мой доклад про хэш-таблицу.

[1:41:24] Максим: Вот это твой доклад, да, и, кстати, по-моему, я оттуда про него узнал. И вот этот код я точно видел, этот useMultiTarget код, я такой: блин, что здесь написано вообще, вообще жесть, — закрыл. А сейчас ты мне его показал, я такой: я понял.

[1:41:39] Максим: Тут всё очень сильно от продукта зависит, потому что в ClickHouse — а если бы я писал своё какое-то приложение, я бы, наверное, это не использовал. Я просто знаю, что мы делаем ClickHouse, поэтому пофиг на сложность, мы будем делать. Но тут вот ещё важный момент: этот код выглядит страшно, но он всегда изолирован. У нас есть красивые интерфейсы в ClickHouse, там интерфейс IFunction, например, и оно где-то в недрах какой-то специальной функции. Чтобы понять, что эта функция делает, как с ней работать, ты смотришь интерфейс. А если хочешь понять, что внутри, пооптимизировать, то идёшь в реализацию. Это код, для читателя, наверное, будет ссылка, его не надо вставлять в то место, где люди будут читать код. Это специализированное решение для конкретной функции. Такого кода полно, но он очень должен быть спрятан. Если такой код торчит — это ужас.

[1:42:22] Максим: Мне кажется, это очень сильно development productivity снижает, потому что если тебе, для того чтобы понять, как каждая функция работает, или если этот код в каком-нибудь супер жёстком месте, которое реально в агрегации прям торчит, — то любому человеку, который хочет понять, что там происходит, поправить какую-то бизнес-логику, придётся в этом разобраться. Это не скейлится, потому что к тебе может на проект прийти какой-нибудь студент, который на втором курсе, он хочет какую-нибудь фичу сделать, но про этот SIMD ещё не слышал. Ты хочешь, чтоб он фичу делал, может, алгоритм какой-то сложный, но не хочешь, чтоб он разбирался с этим.

[1:42:56] Александр: Нет, ну, мы хотим, чтоб он разбирался с этим, но не хотим, чтобы оно отвлекало его, чтобы ему приходилось с этим… на выходные.

[1:43:11] Максим: Кстати, такую шутку хотел сказать.

[1:43:15] Александр: В прошлом выпуске не получилось сказать. Помнишь, мы говорили про work-life balance?

[1:43:19] Максим: Да-да-да.

[1:43:21] Александр: У меня есть чат, где иногда люди из крупных компаний пишут всякие свои штуки. В общем, суть такая. Там какой-то человек пишет, типа: ой, беда, теперь у меня на работе просят работать два дня из дома. Человек пишет: я с самого начала работал два дня из дома. И вот знаешь, сначала прочитал, я подумал: ну странно. А потом я понял, что это шутка — что про выходные.

[1:44:01] Александр: И к вопросу про portability ещё можно заметить, что мы не использовали AVX-512. И это как бы по делу. Вообще с AVX-512 немного странная история. Во-первых, AMD-процессоры это не поддерживают. Плюс с AVX-512 даже на Intel есть проблемы. На старых процессорах Intel возникает проблема с overclocking или как-то так, из-за которой они понижают частоту. Но представь, у тебя работает один ClickHouse — ну тогда тебе как бы пофиг, работает ClickHouse, и всё. А представь, что мы всё-таки обычно живём в каком-то multi-tenant environment, может, на виртуалке, где у тебя есть даже другие процессы. У тебя вообще на гипервизоре другие системы, какие-то другие пользователи живут. И представь: к такому пользователю ты заиспользовал эти инструкции, понизил частоту процессора, потом шедулер как-то так пошедулил, это ядро уехало на другой процесс.

[1:45:00] Максим: Или это даже внутри процесса одной операционной системы — так проще думать. И у тебя другое приложение начало тормозить. В Google, по-моему, до сих пор не используют AVX-512, и с этим реально сложно. Объясню почему. AVX-512 — это просто очень крутой instruction set, в котором добавили очень много всего для SIMD-алгоритмов. Безумно много всего. Там есть такая библиотека, которая называется simdjson, и эта библиотека по сути всё, что можно, выжимает из AVX-512. Она на текущих современных процессорах Intel просто будет офигеть как быстро работать. Понятное дело, там есть fallback для AVX2 и так далее — я просто говорю про современный процессор Intel. И хочется иногда всё-таки это использовать. Вот в ClickHouse мы начали это использовать, когда, например, знаешь, что задеплоишься на современный процессор Intel — если ты в клауде, то это можно включать, это нормально. Но если ты не знаешь, куда задеплоишься, то лучше пока это не использовать. Это может быть проблема. По слухам, в Google прям у компании были такие проблемы с этим AVX-512 — история про даунклокинг на AVX-512 вообще довольно известная. Это опасная вещь, используйте с осторожностью.

[1:45:06] Александр: Блин, я так ещё подумал: а как такие проблемы… Вот когда ты особо не знаешь, как вообще понять, в чём причина. Это же охренеть можно.

[1:46:14] Максим: Я думаю, в компаниях типа Google и Facebook это не используется, потому что они просто боятся — ну типа, а как ты это поймёшь? У тебя программа просто стала тормозить. Это такая external вещь из-за какой-то другой программы. Причинно-следственную связь невозможно будет найти.

[1:46:28] Александр: Я зато теперь знаю, как объяснять флаки-тесты на CI. Флаки-тест — это просто планеты не так выстроились, космические лучи там.

[1:46:36] Максим: А теперь AVX-512 просто использует какая-то система.

[1:46:40] Александр: Сеть моргнула ещё такая. Ну да.

[1:46:42] Максим: И поэтому это действительно опасно использовать. Мне кажется, в ClickHouse мы это где-то используем, но не везде. Если коснуться вопроса portability, там ещё такая проблема, что этот код, который я тебе скинул на макросах, он просто нереально много кода генерирует. Ну ты представь, например, функция sum. Она суммирует все Integer — unsigned int, signed int — и все float. Получается: unsigned — это int8, int16, int32, int64; signed — int8, int16, int32, int64; и float32, float64. У тебя, грубо говоря, 10 вариантов, 10 специализаций. И ты эти 10 специализаций функции sum ещё дублируешь, компилируешь с SSE4.2, AVX2 и AVX-512. Так я сказал 10 — то есть 10 умножил на 3 раза. То есть ты 30 функций сгенерил на ровном месте.

[1:47:33] Максим: Но это мы говорим сейчас про функцию sum, а это один аргумент. Как ты понимаешь, в ClickHouse мы таким же образом используем, например, функцию, которая принимает два аргумента, — бинарная функция, например +. И ещё для констант. Функции sum констант нету, но эта схема с автовекторизацией для констант тоже прекрасно работает, потому что константный Integer очень легко превратить в SIMD-регистр — он просто в 4 раза дублируется в нём. И для Integer мы считали, что у нас может быть 10 вариантов, с одной стороны, и 10 с другой. И ещё может быть 10 вариантов, что это может быть константа. То есть, грубо говоря, 20: у тебя может быть 10 вариантов — первый аргумент обычный Integer и 10 вариантов, что это константный один из этих Integer. И с другой стороны то же самое. То есть слева 20, справа 20, всего 400 комбинаций. Ты берёшь 400 комбинаций и ещё умножаешь на 3.

[1:48:04] Александр: А размер бинаря прям заметно возрастает?

[1:48:06] Максим: Мне кажется, размер бинаря заметно возрастает, но там, понимаешь, на размер бинаря в ClickHouse мы так особо не смотрели, плюс у нас бинарь сжатый. Мы сжимаем бинарь, и когда ClickHouse запускается, он себя разжимает. В ClickHouse бинарь был не очень большой, может, там 600 мегабайт, может, даже если с дебаг-символами; даже разжатый ещё меньше. Вот в YDB был бинарь 4 гигабайта. Там так много кода было, что возникали проблемы с тем, как вообще с ним работать, с address sanitizer, как его линковать, потому что у тебя там могут быть закладки, offset’ы какие-то 32-битные — да, они уже выскакивают.

[1:48:53] Максим: В общем, короче, там можно ещё дебаг-символы отдельно таскать. Я бы сказал, это минорная проблема. Просто когда код распухает — это большая проблема, потому что есть ещё кэш инструкций, он может иногда тоже тупить, потому что сам бинарь иногда может из кэша вымываться, если бинарь большой, типа как в ClickHouse. Но в этом случае мы, когда запускаем ClickHouse, весь его бинарь лочим в памяти, чтобы у нас не могло возникнуть фолта на бинаре — чтобы из оперативной памяти он на диск не падал.

[1:49:36] Александр: Да, да, чтобы такого не было.

[1:49:37] Максим: Это делается, но это прям ужасный код: там нужно взять, аллоцировать память размера своего бинаря, скопировать его туда, прыгнуть туда и залочить его. То есть там что-то сложное. Мне кажется, оно по дефолту даже у нас не включено, то есть мы боимся включать, хотя, может, уже и включено. Но, по-моему, мы это использовали для перф-тестов, потому что в перф-тестах это всё-таки добавляет диск.

[1:50:01] Александр: Да, эти свопы картину нарушают, и нельзя понять, что не так. У тебя могут результаты этих перф-тестов лапать немножко.

[1:50:07] Максим: Ну, наверное, с portability всё. Единственное, что ещё стоит сказать: если не нужны такие проблемы, как мы сейчас рассказали, можно просто использовать JIT-компиляцию. JIT-компиляция — когда ты какую-то функцию компилируешь всё-таки под конкретный процессор. То есть JIT-компилятор понимает, что мой код будут прямо тут, сейчас исполнять. Это не обязательно — ты можешь JIT-компилятору сказать: ну, ты на x86, скомпилируй мне код на ARM и отправь на какую-нибудь ARM-машину. Но это редко бывает. Хотя, знаешь, есть такой прикол: представь, у тебя в кластере есть машина x86, и какие-то поддерживают AVX-512 или AVX2, а какие-то не поддерживают, поддерживают только SSE4.2. Если ты на машине с AVX2 скомпилируешь код и решишь его отправлять по кластеру, то можешь отправить его случайно на инстанс, где AVX2 не поддерживается, и тоже это всё может взорваться.

[1:50:57] Александр: Я понял, насколько это… Да, мы просто тоже делаем: я пишу код, который… Отправляешь код на другую тачку, инстанциируешь, запускаешь — деплоймент такой.

[1:51:07] Максим: Но это другой уровень. Когда ты уже JIT’ованный код отправляешь — вот это уже прям стрельнуть может нормально. Мы когда говорили про JIT, мы говорили про такое, когда ты генерируешь LLVM IR, то есть генерируешь ассемблер, ещё такой понятный код. Но иногда приходится генерить прям код на C++ и прямо отправлять чуть ли не файлы на C++ — вот как в Amazon в Redshift. В Amazon есть база данных Redshift, и, по-моему, они прям компилируют C++. Реально генерят огромные C++ файлы, которые исполняют эти запросы, отправляют их на флот машин в кластере. Их основная задача — компилировать код. Всё, что они делают, — компилируют код и, видимо, дальше на узлы рассылают. Про это тоже нужно знать. Но в целом с JIT-компиляцией в контексте SIMD-инструкций просто плюс, что код не распухает, ты только нужный код генерируешь. Это приятно.

[1:52:00] Александр: Да.

[1:52:06] Максим: Да, про алгоритмы давай немного проговорим. Если говорить про SIMD-алгоритмы, они в основном построены на такой интересной инструкции, которая называется pmovmskb. Что эта инструкция делает? Представь, у тебя есть широкий регистр, в нём что-то есть. Ты этот широкий регистр хочешь превратить в битовую маску. Для многих алгоритмов это нужно, и вот используется эта инструкция pmovmskb, которая из этого регистра тебе делает — например, если у тебя 16-байтный широкий регистр, то она делает тебе 16-битную битовую маску. И это может быть полезно для всяких хитрых алгоритмов, где тебе такую конвертацию нужно делать. Это ключевая инструкция. На ARM, кстати, её нет, там нужно эмулировать. В целом даже проблема возможна. Я не уверен про RISC-V и остальные архитектуры, но это первая инструкция, она на SSE4.2, и она очень часто используется.

[1:53:01] Максим: Где она могла бы тебе пригодиться? Ну, блин, она так много где может пригодиться, что тут даже такой пример…

[1:53:07] Александр: А у меня вот есть пример, кстати, я недавно писал такой код. Допустим, мы говорили, что при строчном представлении данных в таблице данные хранятся в так называемых таплах, где строка — это тапл. И в целом, если это большая строка — допустим, тысяча полей, грубо говоря, в экстремальной ситуации, — в этих тысячах полей 950 могут быть NULL. Мы же не хотим хранить внутри этого тапла какие-то специальные заглушки. Мы, например, можем как раз это в битсете хранить, который будет в заголовке этого тапла: типа, вот по тем позициям NULL, а по тем — нет. Соответственно, там, где нет, ты высчитываешь offset относительно оставшегося места. Таким образом, ты экономишь место и не вычитываешь лишнее. Вот это как раз такое представление данных в заголовках. Битсет как будто бы очень удобно. Но я не знаю, как его в SIMD применить.

[1:53:56] Максим: Да, ты хороший пример сказал. В SIMD эта инструкция используется, чтобы переходить из мира SIMD в мир обычного кода. Например, представь, у тебя может быть такой код, очень интересный, знаешь, строковый алгоритм. Это самый хороший пример, там вообще повсюду SIMD. У тебя есть UTF-8 и ASCII. Часто на практике тебе приходится функции поддерживать UTF-8. Но по факту часто реально бывает — high performance всяких сценариев — люди используют просто ASCII, ничего кроме ASCII не используют. То есть там нет никакого Unicode. Но тебе нужно делать какой-то dispatch между всем этим. Представь, у тебя есть строка, она к тебе прилетела как массив байт. Ты взял эти байты, 16. И ты можешь их сравнить с каким-то байтиком, который тебе скажет: можно ли сказать, что этот 16-байтный кусочек — ASCII? Его, по-моему, нужно сравнить, больше ли, чем 127; если там что-то есть, то это уже не ASCII. Ты сравниваешь, и у тебя получается ещё один регистр, в нём будут какие-то числа: если true, то одно, если false, то другое. Затем ты конвертируешь его в 16-битную битовую маску. И затем говоришь: окей, если эта битовая маска равна нулю или равна максимальному 16-битному Integer (я точно сейчас не вспомню), то это значит, что все числа ASCII. И значит, мы можем не пытаться обрабатывать UTF-8 для этого кусочка.

[1:55:23] Александр: Так, получается, к тебе приходит какая-то строка. Ты же такой генерализованный, обязан обрабатывать UTF-8. Но часто внутри UTF-8 лежит просто то, что можно интерпретировать как ASCII, потому что это английский алфавит и цифры. Это подавляющее большинство, наверное, строк, с которыми мы работаем, если не берём кириллицу. Как понять, что перед тобой строка не закодирована так, что её можно интерпретировать с помощью ASCII? Пройтись по каждому байту и посмотреть. Сколько там? 4 байта, по-моему. Короче, ты по каждому характеру проходишь и смотришь, умещается ли он в ASCII. Соответственно, ты прошёлся и составил карту того, выходит или не выходит. И вот это типа вектор. Ты его конвертируешь, этот результат, в битовую маску, и по ней можешь быстро сказать — ещё раз не итерироваться, а просто схлопнуть её — ASCII или не ASCII вся строка.

[1:56:17] Максим: Ты всё правильно сказал. Вот это такой пример. Представь другой пример, где приходит поток чисел.

[1:56:20] Александр: Я, кстати, вообще не знал даже. Прикольно.

[1:56:24] Максим: Там эти SIMD-алгоритмы — мы сейчас обсудим только самое простое, просто чтобы дать затравку. Там очень-очень хитро. Там есть такие инструкции, шафлы всяких байт. Представь, есть код, который JSON парсит с использованием SIMD. Представь, сколько он всего сложного делает — распарсить JSON. Даже просто написать код, который JSON распарсит: ты берёшь спецификацию, там дофига всего писать, нужно всё обрабатывать, всякие скобочки туда-сюда. А там генерятся специальные маски, специальные вектора, там как-то это сравнивается, шафлится. Это отдельно очень сложно, и очень хитрые есть алгоритмы. Другой пример. Знаешь, у нас часто бывает такая штука — тебе нужно распарсить число. Представь, у тебя какая-то программа, которая хочет парсить число. Это будет какой-то цикл, который проверяет: а вот этот характер, он больше либо равно маске '0' и меньше либо равно маске '9'? Если да, то я пытаюсь это число парсить. Но вот этот if потенциально весьма дорогой: тебе нужно две инструкции сделать, хотя они, кстати, могут даже параллельно выполняться, потому что это две отдельные проверки, потом получить результат. Но ты можешь взять всё это дело, загрузить в SIMD-регистр — кусочек, — сложить его так, проверить и понять, где у тебя заканчиваются, где уже не число.

[1:57:08] Александр: Принцип тот же: ты как бы взял эти 16 байт, сравнил больше либо равно '0', отдельно сравнил меньше либо равно '9', сложил эти — OR там сделал, или AND; в обычном коде мы писали AND. Сделал AND, сконвертировал в битовую маску и по битовой маске первую единичку нашёл. Там есть специальные инструкции для работы с битами — или тебе наоборот нужно сделать, чтобы получить именно позицию первой единички. Но суть в том, что ты эту логику написал, сконвертировал в битовую маску, получил какую-то позицию и сразу знаешь, сколько теперь в этом потоке данных характеров — это Integer, в плане это цифры. Такой пример.

[1:58:08] Максим: Ещё есть один пример, очень популярный, из хэш-таблиц, но он прям решает. Это гугловые Swiss-хэш-таблицы, и они именно так и работают. Гугловая Swiss-хэш-таблица устроена как linear probing — ну, она на самом деле не совсем как linear probing, но я для простоты так скажу. У тебя есть бакеты, ячейки, в которых есть ключ и значение. И обычно в хэш-таблицах возникает проблема: тебе нужно понимать, а эта ячейка вообще проинициализирована или нет? Эта ячейка удалена или нет? Тебе нужно метаданные где-то хранить. И есть несколько вариантов: их можно отдельно держать, можно пытаться придумать для linear-хэш-таблиц, где их можно как-то хитренько упаковать, можно запретить удаление, а проверку на нулевой элемент вообще отдельно вынести в отдельный сторож. Вот так, например, сделано в хэш-таблице в ClickHouse: там отдельный zero-буфер будет для нулевого элемента. И ты будешь знать, что в основной хэш-таблице у тебя просто не может быть бакета, который нулями проинициализирован, — потому что ты заранее это проверяешь. Там дополнительный branch возникает, он обычно хорошо предсказывается, но всё равно могут быть проблемы. На практике проблем нет, у нас хорошо работает эта хэш-таблица, но в целом это дополнительный лишний branch.

[1:59:13] Максим: А вот в хэш-таблице в Google они придумали такую схему. Представь, у тебя есть 16 ячеек. Ячейка в хэш-таблице — это ключ, значение, бакет, одна ячейка. У тебя 16 ячеек. И теперь ты к ним кладёшь 16 байт. Каждый байт будет относиться к соответствующей ячейке. Первый байт — байт метаданных для первой ячейки, второй байт метаданных для второй ячейки, шестнадцатый байт — для шестнадцатой. Например, ты хочешь понимать, ячейка пустая или нет. Это самое понятное — удаления у тебя может и не быть. Для этого ты будешь нижний бит, если ячейка не пустая, взводить его в единицу. Ну, блин, у тебя осталось лишних 7 бит.

[1:59:58] Александр: Да. А типа ты хочешь что-то туда засунуть.

[2:00:01] Максим: Люди в Google придумали: а давай мы туда засунем 7 нижних бит хэша.

[2:00:06] Александр: Так, стоп, подожди. Это уже надо подумать. Вот с одним битом было понятно. Так, 7 нижних бит хэша. А сколько там всего бит? Вот у нас, например, есть 64-битный хэш.

[2:00:19] Максим: 64. Мы берём из него 57 бит. Ну смотри, ты, например, посчитал хэш, вставил ключ какой-то в хэш-таблицу. Иногда есть хэш-таблицы, которые вообще весь хэш хранят — например, строковые хэш-таблицы так часто работают. И когда делаешь дополнительный lookup, ты не строки сравниваешь, а сначала сравниваешь хэши, потому что они 64-битные, их проще сравнить: тебе не нужно по строке, обычно это ещё переход по указателю, memory fetch какой-то лишний. Тебе проще сравнить хэши. Но в данном случае мы не хотим хранить хэши, мы хотим что-то сохранить в эти 7 бит, которые у нас остались для каждого байта метаданных. И мы туда можем засунуть верхних 7 бит хэша или нижних — какие-то 7 бит хэша, например нижних.

[2:00:58] Максим: Когда мы в нашу хэш-таблицу делаем lookup, мы посчитали 64-битный хэш, нижние 7 бит от него сохранили, и по остальным 57 битам мы попали в какие-то 16 бакетов, назовём это группа. Попали в какую-то из групп, используя только 57 верхних бит хэша. Мы взяли этот хэш и сделали остаток от деления — ну, как обычно в хэш-таблицах делается.

[2:01:20] Александр: То есть мы берём эти первые 57 бит хэша, который мы ищем, да?

[2:01:26] Максим: Да.

[2:01:26] Александр: Это как первый уровень навигации, он нас отправляет в какой-то регион, а в этом регионе мы остальные 7 берём уже в хэдере смотрим — а есть там такое? Если есть — да, если нет — нет.

[2:01:38] Максим: Да, именно так. Но если нет, то мы идём в следующую группу. Потому что вдруг группа переполнилась, и нам следующую пришлось записать. Это коллизия уровня первых 57 битов.

[2:01:51] Александр: Ну да, то есть первые 57 битов ты используешь для навигации в группу, но эти группы просто лежат как массив.

[2:01:58] Максим: Массив, где каждая группа — это 16 бакетов, ключ, значение, и 16 метаданных. Ну или, если у тебя просто хэш-сет, а не хэш-мап, то просто ключ без значения. В общем, пришли мы в группу, и у нас возникает задача. У нас есть 16 байт, и мы хотим понять, есть ли какой-то элемент в группе, у которого хэш — вот эти верхние 7 бит каждого байта — совпадает с нашим хэшем, с теми 7 битами, с которыми мы пришли. То есть сказать да-нет.

[2:02:21] Александр: То есть сказать да-нет.

[2:02:24] Максим: Да, мы хотим сказать да-нет. И мы берём эти 7 бит хэша, заготавливаем такой вектор из 16 байт, где у каждого байта из этих 16 верхние 7 бит будут значением этого хэша. Такой байт конструируем и создаём вектор из 16 элементов. И затем мы просто можем сделать AND и понять, есть ли у меня такое — взять эти две маски, сложить. После этого конвертируем в битовую маску и опять получаем индекс, из какого нам нужно смотреть.

[2:02:51] Александр: А, да, я понял. То есть вот это сложение масок, конвертация — это по сути в два шага мы и отвечаем на вопрос, и offset вычисляем, то есть понимаем, куда идти.

[2:03:01] Максим: Ну, скорее в три шага. Сначала мы создали вектор — пусть это будет предварительный шаг. Потом для вектора этих 16 байт, которые у нас есть — это вектор, мы его сразу взяли, — и вектора, который мы заготовили, мы сделали операцию AND. После этого мы хотим сделать инструкцию pmovmskb, то есть сделать битовую маску, и затем из этой битовой маски мы уже можем работать с битами — то есть перешли в мир обычного C++, обычных регистров, и сразу вычисляем. Там есть специальная инструкция, которая вычисляет первую единичку, индекс первой единички, быстро.

[2:03:32] Александр: Офигеть, да.

[2:03:32] Максим: И такая хэш-таблица реально работает супер офигенно. На всех практических сценариях, где такую хэш-таблицу ты можешь использовать — например, в своём приложении, где тебе не нужна какая-то специализированная агрегация, как в ClickHouse, — такая хэш-таблица перформит любую другую.

[2:03:48] Александр: Но там, где поддерживаются эти SIMD-инструкции.

[2:03:50] Максим: Да, но в данном случае тебе нужно только SSE4.2. То есть, по сути, оно поддерживается везде, на любых Intel. Но на ARM — реализацию я смотрел в Abseil — там она чутка хуже будет работать, потому что использует уже не векторные инструкции, а просто байты конструирует. С байтами ты то же самое можешь: взял там 8 байт, сделал AND, посчитал битовую маску, там сразу это работает. Но на ARM чуть похуже, а на Intel офигенно работает. И у этой хэш-таблицы ещё удивительно высокий load factor. Она работает с load factor 0.875 — как бы она может быть почти на 90% забита. Это офигеть как круто, потому что, например, кликхаусная хэш-таблица работает с load factor половина, 0.5. И на практике такая хэш-таблица потребляет в два раза меньше памяти всегда. Может, даже больше — не повезёт. Это очень хорошая вещь.

[2:04:42] Максим: SIMD-инструкции, понимаешь, в таких простых случаях они повсюду. Во всяких библиотеках нужно просто быть готовым к тому, что ты там такой код можешь увидеть. А более сложные алгоритмы просто более виртуозно придумывают, как эти маски делать, как их шафлить и всё такое. Это реально отдельный скилл. Нужно прям мозг такой иметь хитрый, чтобы понимать, как это шафлить так аккуратно. Это прям очень-очень низкоуровневая работа.

[2:05:04] Александр: Ну, интересно. Ты мне прям с этой хэш-таблицей прям захотелось посмотреть, разобраться, как она работает. И ещё про характеры и ASCII-код — то, что векторно, то есть можно UTF интерпретировать как ASCII, довольно быстро понять, — тоже прикольно.

[2:05:24] Максим: Кстати, знаешь, как можно ещё хорошо понимать, где такой код можно посмотреть? Обычно, если ты, например, открываешь проект на C или C++, можно поискать по #ifdef-у __SSE4_2__ или что-то такое. Обычно такой код всё-таки спрятан за макросы, платформозависимые на этапе компиляции. Можно по этому #ifdef-у быстренько пробежаться. Там, на самом деле, таких платформозависимых макросов очень много. Я когда в YDB переносил код на ARM, мне нужно было по всему проекту это найти. Там не один, там очень много всяких разных. Если это Intel — всякие такие макросы, ты по ним можешь легко поискать код, который тебя именно SIMD интересует, и посмотреть.

[2:06:01] Максим: Я честно тебе скажу, в ClickHouse ещё очень сложный был алгоритм, который я помню ревьюил и там домеживал. Кстати, SIMD-алгоритмы очень часто почему-то в ClickHouse приносят люди из Китая. Я не знаю почему — то есть из Intel много людей приносило, которые в Intel работают, видимо, экспериментируют на ClickHouse. И там был очень сложный алгоритм, который проверяет, есть ли элемент в массиве. Там полноценный SIMD. Есть ли элемент в массиве — там тоже можно именно таким же способом проверять: сделать специальный вектор, сделать условную операцию AND, тоже превращать в битовую маску. Но там было, по-моему, что-то более сложное, там ещё и шафлить приходилось. В общем, я скорее к тому, что такое повсюду есть. И, наверное, если слушатель захочет, он может в ClickHouse посмотреть на более сложные примеры.

[2:06:42] Александр: Да, да. Я думаю, что на код, который ты мне скинул, точно ссылочку оставишь.

[2:06:48] Максим: Оставим в описании. Или я его прям скопирую в Telegram — заходите в комментарии к посту. Тоже можно ссылочку на PR приклеить.

[2:07:07] Александр: В общем, да, очень плотно, как всегда. Четвёртый раз, и за три часа опять очень было интересно. Максим, спасибо тебе большое. Если тебе есть что напоследок сказать, может быть, поделиться какими-то ресурсами для тех, кто загорелся идеей, а ему слишком рано смотреть в ClickHouse, — может быть, какую-нибудь книжку классную на эту тему почитать?

[2:07:27] Максим: Как раз хотел. Есть такой Агнер Фог. Ссылку я прикреплю. Он много про такое пишет, именно про то, о чём мы сегодня говорили. Там намного подробнее, где он разбирает, как процессоры устроены, какие там латентности у инструкций — то есть через сколько инструкция будет выполнена, — какая пропускная способность у инструкций. Там есть даже прям таблица для разных процессоров, можно посмотреть числа. И у него есть гайды по оптимизации кода и гайды про автовекторизацию, просто про векторизацию, как писать код на ассемблере. Я не скажу, что это прям очень просто — на самом деле это довольно тяжёлые книги. Простую книгу по оптимизации, мне кажется, наверное, можно какие-то блоги порекомендовать, но мне для этого нужен какой-то список, я могу тебе потом скинуть. Но, скорее всего, самое важное — это, наверное, самому какой-то код писать, экспериментировать. Потому что, видишь, прям совсем не очевидно. Вот, например, когда мы говорили про матрицы, про транспонировать матрицы, — это совсем не очевидно, что оно так будет работать. И можно поискать какие-то такие примеры, продакшен-места в коде, которые реально хочется пооптимизировать, и почти наверняка вы можете придумать, как это заоптимизировать.

[2:08:31] Александр: Да, да, пространство есть всегда для оптимизации. Круто! Спасибо большое, Максим. Если будут какие-то большие релизы, апдейты или новости, которыми ты захотел бы поделиться, то подкаст «Тысяча фичей» всегда открыт для тебя, заходи. Ты любимчик однозначно, потому что чаще всех приходишь и классные штуки рассказываешь.

[2:08:53] Максим: Очень приятно поговорить с теми, кто непосредственно такие системы разрабатывает. Спасибо тебе большое.

[2:08:58] Александр: Спасибо.