Всем привет, меня зовут Сергей Слотин, и мой доклад будет интерактивным.
Чтобы подключиться, нужно зайти прийти по ссылке, которая на слайде, либо зайти в чат московского трека, там тоже будет эта ссылка.
Можно подключиться к местному Wi-Fi, если вам надо.
И еще настоятельно рекомендуется указывать там такой же юзер-нейм, который у вас в телеграмме, чтобы вас потом можно было быстро найти.
Вот, эта совка здесь будет внизу слайды какое-то время.
Я пока расскажу, про что будет сам доклад.
Вот, если мы были на двух предыдущих конференциях, то вы знаете, что я люблю ускорять алгоритмы и написал про эту книжку.
И я и написал, потому что мне не нравится, как большинство разработчиков относятся к теме производительности и вообще подходят к оптимизации, используя какие-то такие общие соображения и общие правила.
В то время, как чтобы действительно что-то саптимизировать, нужно методично измерять время работы алгоритма, находить там bottleneck, как-то пытаться от него избавиться и продолжать, пока мы не упрёмся в какой-то теоретический предел.
И для этого таких общих соображений, вроде там не используются виртуальные функции или там не проходите по массиву всегда последовательно, они не работают и нужно глубоко знать, как работает железо.
И это знание, оно разделяется, например, для категории, что происходит внутри идра, то есть, как происходит вычисление, как исполняются инструкции и что происходит в памяти.
И вот время, та часть, которая связана с памятью, ей обычно уделяют гораздо меньше времени, и с моей точки зрения это несправедливо.
Нужно, наоборот, начинать с памяти.
Во-первых, потому что для большого количества приложений ботлонеком является именно память.
Там оптимизированные, неоптимизированные учисления там не важно, на ком языке, там сколько CPU не бросай, если ботлонек-память, то ботлонек-память.
Ещё другая причина — компляторы довольно хорошо справляются с оптимизацией всякой арифметики.
И там умеют викторизовать достаточно простые циклы.
Но при этом какие-либо оптимизации с памятью они делать не могут, просто потому что они не могут мотивицировать никак layout.
Это должна быть какая-то логихмическая изменения.
И еще вот если вы пишете какую-то программу и ожидаете от нее какой-то уровень производительности, то если вы что-то не знаете про вычисление, то обычно для вас это оборачивается каким-то приятным сюрпризом.
То есть комплятор за вас применен какой-то труб, о котором вы не знаете, и у вас получается какой-то спидап.
А когда вы что-то не знаете про память, то эти сюрпризы становятся негативными.
У вас там будет просадка по производительности, там вы больше не будете кладываться в SLA.
Вы не сможете обрабатывать данные в реалтайме, там возможность фигфолт будет.
И, в общем, такие проблемы нужно фиксить оперативно, а упущенные оптимизации – это не так уж и критично.
И вообще, если посмотреть на CPU,
И вот посмотреть на площадь всего, что прямо и легко связано с вычислениями, и на площадь всего, что прямо и легко связано с памятью.
То есть кыши внутри ядер, расшельный кеш, контроллер памяти и вот всё такое.
То чисто в точке зрения транзисторов, CPU это не машина для вычисления, CPU это машина для перекладывания байт.
Именно поэтому доклад будет про память.
Сколько стоит сложить два числа?
Вот если эти числа находятся в регистрах, то вот в узком смысле, в плане количества времени от начала до конца операции, займет один такт CPU.
Но если эти данные лежат где-то в памяти, то все усложняется.
Нужно загрузить один оперант, загрузить второй оперант, выполнить сложение и загрузить результат куда-то.
И это может занимать очень сильно празднову в зависимости от того, где эти данные лежат.
И все сложно, потому что память она устроена иерархически.
Вот на верхнем уровне есть, ну, есть регистра CPU, доступ к которым мгновенный.
Есть какое-то количество кашей в CPU, обычно их три.
Есть там оперативная память и есть там всякие SSD, жесткие диски, там что-нибудь, что подключается по сети, там NFS, S3, вот и прочее.
И каждый новый уровень, он примерно на порядок больше, там либо дешевле, но при этом в несколько раз медленнее.
Еще такая важная особенность, что
На всех уровнях мы работаем не с индивидуальными битами и байтами, а мы работаем с целыми блоками.
То есть читаем сразу целый блок или записываем сразу целый блок.
В случае с RAM и ECPU, по что будет основная часть доклада, эти блоки называются кэшлиниями, и они обычно 64 байта.
Вот каждый раз, когда выполняем какую-то операцию, чтение или запись,
Процессор сначала смотрит на нижний уровень каша.
Если там что, но данные находятся, то все хорошо.
Если нет, то он идет на следующий уровень каша, более медленный.
И в любом случае записывают вот эти новые данные в кэш, возможно выкидывая какой-то другой блок, как правило, самый протухший.
То есть это List Recently Used Cache LRU.
И весь этот процесс, он, в случае с процессорными кишами, работает автоматически и полностью, ну, программиста об этом обычно не думает.
Конфигурацию кушей можно посмотреть на отдельных сайтах вроде там wikichip, либо в документации вендера, либо в операционных системах, возможно даже в рантеме.
Но мы вместо того, чтобы читать документацию, мы поступим более интересно, мы за реверс инженерим, все это дело, и замерим все с помощью экспериментов.
Самое простое, что можно сделать, что можно замерить, это замерить пропускную способность памяти.
Для этого мы создадим массив, там интов, и применим ко всем элементам какую-то простую операцию, например, инкремент.
И вот первый вопрос, который должен отобразиться, если вы зашли на этот сайт с вопросами, и на который можно ответить.
Если мы увеличим размер массива с 2 в 10, это примерно 4 кБ, я должен вылезать в L1 cache, самый нижний уровень cache, до 2 в 32.
Это будет 32 мегабайта, и такой массив будет лежать полностью грамм.
То будет быстрее, примерно так же, или медленнее.
Мы измеряем время работы в расчете на одну операцию инкримента, то есть сколько мы инкриментов делаем в секунду.
И мы комплируем с O3 на самом негрессивном уровне оптимизации.
И мы запускаем это на современном CPU, где есть векторная инструкция.
Говорим об этом компилятору.
И еще добавляем там флаг, чтобы он циклы развернул, чтобы мы мерили именно то, что происходит в те рециклы.
Пять, четыре, три, два, один.
Вот половина ответила правильно.
Вот действительно у нас... Верните мне мои слайды, пожалуйста.
Да, вот график производительности от размера массива.
Отмечу, что здесь вкола X размер массива аналогрифмическая, то есть с каждым делением массив увеличивается вот два раза.
и вертикальными линиями указаны границы кашей.
И видно, что производительность тайна падает, когда мы переходим в новый уровень каша.
В самой левой части мы ограничены вычислительными ресурсами.
Как я говорил, на данном СПУ есть поддержка векторных инструкций.
И вот просто для тех, кого удивляет, что мы здесь исполняем что-то порядка десяти в десятой операции в секунду, пока массив лежит в каша.
Это вот потому, что процессор и вот комплятор выбрал использовать быстрые векторные инструкции, которые позволяют за один такт вот загрузить сразу 8 элементов, сложить вот прибавить к ним единичку, мы делаем increment и записать результат туда же, откуда их загрузил.
И все это телоцикла можно в среднем исполнить за один такт с CPU.
И у нас фиксированная частота тактовой частота, 2 ГГц.
То есть мы исполняем 2 миллиарда операции в секунду и за 2 миллиарда такта в секунду и за каждое так мы получаем обрабатываем 8 элементов и получаются вот 16 миллиардов операций в секунду.
такой теоретический верхний лимит, который мы, в случае саледин кышом, почти до него доходим.
А дальше мы ограничиваемся не вышлистными ресурсами, а мы ограничиваемся именно простой способностью очередного уровня кыша.
Вот предыдущий вопрос был скорее разминочный, а теперь пойдут серьезные вопросы.
Вот что будет, если мы в этой схеме увеличим тактовую частоту CPU?
И будет сразу два вопроса последовательно.
Сначала что будет в случае, если у нас массив маленький и лежит полностью в самом мелком уровне каша?
И во втором случае, что будет, если наш массив большой или лежит почти полностью в оперативной памяти.
Вот будет в два раза быстрее, будет там чуть-чуть быстрее, но не в два раза.
Будет примерно так же, будет чуть медленнее или будет в два раза медленнее.
В случае с маленьким массивом.
И после этого будет второй.
И, к слову, для тех, кто смотрит онлайн, вот задержка от меня до зала, примерно 10 метров, делительно скорость звука, а задержка от меня до ютуба, мне сказали примерно полторы-две секунды, так что рекомендую сжать на кнопку чуть пораньше.
В два раза быстрее, в случае с маленькой массива.
Давайте начните второй опрос, что будет в том же случае, только если массив большой.
Это будет маленький хит-тейт.
Да, вот в случае с маленьким массивом будет 2 раза быстрее.
Вот это потому, что массив полностью лежит в CPU, в C6 CPU.
И все операции, все тайминги, они пропорциональны тактовой частоте.
Если мы увеличим тактовую частоту, то все, что внутри CPU происходит, оно ускорится в 2 раза.
И вот наш бинч-машка ускорится в 2 раза.
А если наш массив лежит в оперативной памяти, то мы будем операться именно в способности оперативной памяти.
Оперативная память — это отдельное устройство, отдельное от CPU, и у него собственная тактова частота, которая никак от тактова частоте от CPU не зависит.
И поэтому, во втором случае, когда массив большой, развитительность не изменится.
нижний уровень каша, L1 и L2, они приватны для каждого ядра.
А верхний уровень каша L3 и сама оперативная память, они поширены.
Это имеет важную импликацию для мультипроцессинга.
И чтобы это показать, мы запустим наш менч-парк параллельно в несколько тредов.
Вместо того, чтобы менять какой-нибудь код, мы просто будем более изящным, мы возьмем просто две гнушные тузы.
Parallel позволяет исполнить одну и ту же команду, только параллельно, возможно с разными аргументами.
И Taskset позволяет ограничить, на каких ядрах конкретно оно будет всплняться.
Это нам понадобится через пару секунд.
Вот если запустить наш бичмарк параллельно, то видим, что оно скелется с ядрами не очень хорошо.
Больше трёх ядер на моём ноутбуке, на котором я там бичмаркал, не имеет смысла, потому что мы быстро упираемся именно в правительность памяти.
Ещё важно, на каких конкретных ядрах мы это исполняем.
Вот на моём цепьём, как и на многих цепьём вообще, есть гипертрейдинг.
Гипертрейдинг – это такая особенность, это когда у ядра, у физического ядра есть что-то вроде раздвоения личности.
Там есть два логических треда, которые шерят между собой все железки, которые делают участление, все каши, все остальное.
Но поэтому логически незавидимы друг от друга.
И если запустить два потока на одном и том же физическом ядре и на разных физических ядрах, то будет сильно разная производительность.
Лучше запускать их на разных физических ядрах.
Или вот на другой моей машине, вот такая топология, там нет гипертрейдинга.
Но L3Cash он не общий для всех, а разделен на две половины.
Первые четыре ядра свои четыре мегабайта имеют, а вторые четыре ядра тоже свои четыре мегабайта имеют.
И здесь тоже, если запустить бенчмарк на двух разных половинах и на одной половине, то будет отличаться производительность как будто у одной из них каша в два раза меньше, что в принципе так и есть.
Еще другой способ определить производительность — это как задержку, как время от начала операции до конца.
И задержка — это не то же самое, что и один делительный пропускной способность, потому что CPU может исполнять несколько операций с памятью одновременно, то есть перекрывать их.
Вот в случае с бенчмарком, где мы делали бенчмарк или вот этот инкремент, CPU, например, может посмотреть на последовательность инструкции, которую он будет исполнять, и посмотреть на там 20 траций вперед,
и узнать, какой адрес мы будем фечить через 20 титраций.
И начать фечить этот адрес сильно раньше.
Или есть еще такой механизм.
Это можно сделать на уровне самого контроллера памяти.
Там есть специальный такой хардверный перифетчер, который смотрит на наш аксесс паттерн, на те, какие кашлинии мы фечим.
Если там есть какой-то такой простой паттерн, например, если мы фечим последовательные линейки,
то он это соображает и начинает фейчить их дальше за нас в L3 в самый быстрый кэш, чтобы когда они нам понадобились, они пришли к нам быстрее.
И чтобы измерить задержку, нам нужно каким-то образом обойти вот эти два механизма и сделать так, чтобы у CPU не было возможности предсказать, какие доступы мы будем делать в будущем.
Это можно сделать так, можно сгенерировать случайную пересновку,
и можно сделать из нее такой цикл, в котором мы вот каждый элемент указывают на какой-то другой.
И если мы начнем с любого элемента и будем переходить по этим указателям, мы пройдемся по всем элементам массива ровно один раз и придем в исходный.
И мы после этого начинаем с какого-то элемента, проходим по этим указателям много-много раз, и эту часть бенчмаркаем.
И так СПЮ не может присказать, какие элементы мы будем читать, и так можно вот померить завершку.
И такой антибатор называется вот Пейтерчейсинг.
Вот график такого бичмарка выглядит так, можно примерно прикинуть, какая на каждом уровне каша задержка.
И я обращу внимание, что в отличие от того графика, который у нас был с пропускной способностью, он получился тут сглаженным.
Это связано с тем, что...
Тут, когда массив переходит за размером каша, у нас не каждая следующее считение будет из нового уровня каша.
У нас мы читаем случайные элементы, и возможно, эти элементы они шерят вот кашлиния, вот эти вот блоки по 63 байта.
И какие-то из них, ну может произойти такое, что мы прочитали какой-то элемент, а рядом с ним был какой-то другой элемент, который мы тоже прочитали недавно, и он оказался в кошее более низкого уровня, и поэтому задержка для него будет меньше.
Вот это происходит с какой-то там вероятностью, зависящей от размера кошая и размера массива.
Вот и поэтому здесь график получается такой сглаженный, и мы мерим не совсем чистую задержку.
Мы померим задержку нормально чуть позже в конце доклада, а пока ответим на такой вопрос.
Вот как вы думаете, если по аналогии с предыдущим, что будет, если мы увеличим тактову частоту процессора снова в два раза?
в случае с маленьким массивом и в случае с большим массивом.
В прошлый раз на маленьком массиве было ускорение 2 раза, а на большом массиве ускорение не было.
Будет ли здесь что-то отличаться?
Есть специальные тузы, которые позволяют зафиксировать какую-то тактову частоту.
Точнее, не какую-то тактову частоту, это обычно не сделать нельзя, а какой-то промежуток, от какой-то до какой-то.
На Linux это называется CPU Power, такая у тильта.
Для бинч-маркинга очень выгодная, лучше фиксировать какую-то тактову частоту, чтобы бинч-марки всегда корректные были, чтобы не было интерфинанса.
Покажите нам результат первого вопроса.
Будет в два раза быстрее, действительно.
Давайте теперь второй вопрос начнем.
Вот что изменится, если у нас большой массив?
Вот здесь правильный ответ, оно ускорится, но не в два раза.
Вот верните мои слайды, пожалуйста.
Вот график вот синий, когда мы ускорили все в два раза, на него удобнее смотреть, когда мы вот один график поделили на другой и посмотрели на относительный спидап.
Вот здесь отличие в том, что вот CPU нужно, перед тем, как идти в RAM, нужно сначала проверить свой cache.
И в случае с пропускной способностью, пропускная способность всей системы будет минимум из пропускной способности этой системы каша и пропускной способности оперативной памяти.
И так как все оперативную оперативную память, то не было важно, ускорение скорости работы каша ни на что не блело.
А в случае с задержкой, задержки складываются.
Задержка всей системы, это задержка каша.
Только после этого мы идем оперативную память и фичим ее.
И у нас получается две такие компоненты.
Одна из них зависит от тактовы 4CPU, а другая никак не зависит от тактовы 4CPU.
И поэтому у нас происходит ускорение, но при этом оно происходит не в два раза.
Еще я хочу обратить внимание, что
За время, которое нужно, чтобы один распрыгнуть по указателю, мы можем сделать примерно 50-100 инклиментов.
На этом графике latency и профессиональная способность совмещены.
Слева на красном графике у нас сколько мы можем распрыгнуть по указателю за единицу времени.
А справа и на синем графике, вот две разные шкалы, у нас, ну, сколько мы можем сделать инклиментов, пропускная способность, то есть, видницу времени.
И вот такая большая разница, вот на два прятка из-за того, что, во-первых, мы читаем не по одному элементу, не по одному инту, а сразу всю кашлинию.
И во-вторых еще, как я говорил, запросы могут и очень часто перекрываются, и CPU может поддерживать много из них.
Из-за этого такая большая родница.
И вот это имеет очень большие импликации в производительности структур данных, особенно тех, которые где-то обычно используют указателя.
Вот, например, если там открыть учебник полгритм для первокурсников и посмотреть, как авторы предлагают реализовывать какие-нибудь очереди, или там, в связи, списки, или там деки, стеки, вот что-то такое, то, скорее всего, они предлагают для каждого нового элемента создавать новые
новую ноду и в ней хранить указатель на предыдущий элемент, возможно следующий или что-то такое.
И это работает медленно, потому что при удалении из этой очереди, или если мы хотим какой-то элемент найти, нам нужно прыгать постоянно по этим указателям, что в случае с оперативной памяти можно заниматься сотни минут на секунд.
И вместо этого мы можем реализовать очередь, например, на векторе, то есть просто убрать из этих нод указателя и просто ноды хранить в соседних элементах вектора, при добавлении элементов в очередь просто делать pushback, а при удалении элемента из начала просто сдвигать указатель на начало этого вектора на единичку вправо.
И нам не нужно здесь прыгать по каким указателям, и все будет работать там на порядок быстрее.
Вот и менее тривиальные примеры с всякими там хэштаблицами, с деревьями, с кучами.
Там тоже есть два пути, либо можно сделать для каждой вершины, действительно сделать вершину и указательно на детей, либо можно вести какую-нибудь такую хитрую номерацию, где мы будем оперировать с номерами вершин, но не проходиться напрямую по указателям.
Еще вот мы можем померить такую штуку.
Вот в бенчмарке, где мы делали, где мы бенчмаркали скорость инкремента, мы на самом деле делаем не одну операцию с памятью, мы делаем две операции с памятью.
Чтобы что-то инкомитировать, нужно сначала прочитать какое-то значение, прибавить к нему одничку и записать обратно.
То есть мы делаем не одну операцию с памятью, мы делаем учтение и запись.
А вот что будет, если мы будем делать только учтение или только запись?
Вот только чтение мы можем делать, если мы почитаем, например, только сумму, а только запись мы можем делать, если мы, например, записываем все элементы каким-то одним значением.
Вот и вот вопрос, что будет в случае, если у нас массив большой и лежит полностью в оперативной памяти?
И тот-то другой цикл компиатор сможет викторизовать, так что в исчезненной части проблемы не будет.
Давайте, в случае сочтения, давайте 5, 4, 3, 2, 1.
Стоп, покажите нам результаты.
В случае с учением будет в два раза быстрее.
То есть мы делаем не две операции, мы делаем одну и получается в два раза быстрее.
А что будет в случае с записью?
А в случае с записью почему-то будет также.
Верните мне, пожалуйста, слайда.
Вот такие вот графики получаются.
В случае с течением мы действительно вот делаем одну операцию вместо другой.
И когда у нас мы ограничены памятью, две операции будут работать два раза дольше, чем одна.
А с записью есть такой нюанс,
Что нам нужно, когда мы что-либо читаем или записываем, нам нужно еще обновить каши.
Чтобы там всегда в Валядин и во всех стильных кашах жили корректные значения.
И когда мы читаем что-то в оперативную память,
Могло получиться такое, что какое-то другое ядро тоже записывает что-то в оперативную память, в то же самое место.
И получается такой трейс-кондишн, а нам и тому ядро, и другому нужно свои киши поддерживать корректными.
И чтобы его разрешить сразу после записи в оперативную память, посылается еще одно такое фантомное чтение, чтобы сделать запись, чтобы прочитать значение, которое мы только что записали.
И поэтому в случае с записью мы на самом деле тоже делаем две операции, только с начала чтения, а потом вот эту фантомную запись.
От нее можно избавиться, если посмотреть, как будет работать вот этот цикл, где мы записываем значение.
Компиаторе его скорее всего автовиктуизует примерно так.
И, к слову, MIMSET оптимально и примерно так реализовывается в его середине.
То есть он просто будет использовать вот эту вот векторную инструкцию, которая записывает там всем 8 элементом одно и то же значение в данном случае 0.
И у этой инструкции есть вариант, вот non-temporal write.
Это такой вариант, который игнорирует
Вот всю эту систему кашей игнорирует эту механику, что нам когда что-то записываем, мы должны еще и каши обновить.
То есть эта инструкция, она пишет напрямую в память, минуя все там каши.
Она изначально предназначалась для того, чтобы, если мы точно знаем, что мы какие-то данные не будем использовать, чтобы можно было что-то вот записать один раз и чтобы оно нам не загрязняло каши, потому что они может использоваться для чего-то еще.
Можно сделать такой non-temporal meme set, который полностью игнорирует куши, как вы видите, потому что он никак не реагирует на эти вертикальные линии.
И он работает быстро, и он работает еще быстрее, чем чтение.
Вот интуитивное объяснение в том, что реализовать операцию записи проще, чем реализовать операцию чтения.
Что-то прочитать из оперативной памяти, вот контролью памяти нужно послать туда сначала адрес, там кышление, которое мы читаем.
подождать, скажем, 100 на секунд и записать ответ куда-то еще.
А чтобы что-то записать, можно сразу одним пакетом послать вот по такому адресу, запишу вот такую токашлиню, и не нужно ничего поддерживать.
Но это такая, на пальцах объяснения, почему еще быстрее, чем запись.
И, к слову, такой мемсет можно использовать как альтернативу обычного мемсета, но с большой такой звездочкой, что он будет быстрее, только когда вы уверены, что вы почти точно не будете использовать эти данные сразу после ток, вы их записали.
Если вы их потом будете, то их нужно будет заново читать с оперативной памяти, и никакого спидап не будет.
Ещё я много раз упоминал, тот факт, что мы работаем не с индивидуальными байтами, а мы работаем сталыми кашляниями.
То есть память разделана на блоке по 64 байта.
И если мы загружаем какой-то один байтик, то нам нужно загрузить все кашлянии.
То есть нам нужно загрузить 63 соседа этого байта.
Но мы пока экспериментально с учитыванием кашлянии не подтвердили.
И можно написать такой бенчмарк, где мы тоже инклиментируем элементы массива.
Но мы это делаем с каким-то шагом вот D. То есть мы инкремтируем не каждое, а мы инкремтируем каждые деты.
Если у нас массив большой, и мы вот прикасаемся к каждому DET-му элементу, то будет в D раз быстрее, в 2 раза быстрее, примерно так же, в 2 раза медленнее или в D раз медленнее.
Вот сначала D16, а потом D32.
Инт это 4 байта, и 16 интов это 64 байта.
Вот, а 32 инта это 128 байта, такая подсказка.
Стоп, покажите результат первого.
Вот, почему-то будет примерно так же, если мы каждый 16 элемент читаем, вместо того, чтобы читать каждый элемент.
И давайте следующий вопрос.
Что будет в случае, если мы каждый 32 элемент читаем?
Извините, майстайд, пожалуйста.
Вот график этих трех случаев.
Вот когда наш массив лежит весь в оперативной памяти, то все, о чем нужно париться, это то, какие кошлини, сколько кошлиний мы читаем.
Вот оперативная память в bottleneck, и мы читаем из нее по
И вот в случае, если мы читаем каждый элемент, суммарно реквестов будет больше, но контроль для памяти он не дурак, он будет все эти реквесты дедублицировать.
И все эти 16 реквестов, они будут в одну и ту же кошлинию.
И, соответственно, их можно заменить одним реквестом.
И будет то же самое, как и в случае, когда мы запрашиваем каждый 16 элемент.
И когда мы запрашиваем каждый 16 элемент, мы, по сути, будем запрашивать первый элемент каждой кашлинии.
Но мы и в обоих случаях будем идей одинаковые кашлинии запрашивать.
И поэтому, если читать всё, если читать каждый 16 элемент, будет одинаково.
А когда мы читаем каждый 32 элемент, мы, по сути, прыгаем через кашлиню, и мы запрашиваем каждую вторую кашлиню, и всего нам нужно запросить в два раза меньше кашлиний, и поэтому будет в два раза быстрее.
Ещё я вот в начале упомянул, что
Мы, что cache работает как LRU cache.
То, что там, когда мы что-то туда добавляем, самое тухлое cache-линия, самое тухлое блока, оттуда нужно выпихнуть, чтобы освободить место.
Вот на самом деле, не совсем так.
Вот здесь вот на схеме справа указаны различные локации в памяти, различные блоки, которыми можно сгружать в cache, а слева указаны вот cache-линии места в cache.
И вот пунктерная линия означает, что такой-то блок можно замапать в такую-то cache-линю.
Вот такую схему в железе реализовать очень дорого.
И поэтому можно легко реализовать вот такую, где каждый блок ему соответствует ровно одна кашлиния.
И соответственно кашлиния у них есть какие-то множества блоков, множество локаций памяти, за которые она отвечает.
и эти множества у разных кошли не пересекаются.
Вот такое легко реализовать, но вот такой схемы, проблема в том, что слишком часто разные блоки будут вышибать друг другу из кошла.
Можно несложной математикой показать, что если у нас есть тен блоков, то есть рабочий с этим блоков, и у нас размер кошла то же, а то в случае с полностью ассоциативным кошом,
он будет работать идеально с хитрейтом 100%.
А если у нас DirectMapCache, и эти блоки как-то случайно мапуются в кашлине, то хитрейт будет где-то примерно 1-3, то есть фактически у нас эффективный cache будет его в 3 раза меньше.
Поэтому из-за этого проблемы используют такой вот компромиссный вариант.
где кашлини разделяют на группы, которые называются к60.
И вот здесь вот на схеме размер каждой группы 2, размер каждой группы называется ассоциативностью, но обычно ассоциативность это 8 или 16 элементов.
И каждая такая группа, она действует как свой такой маленький LRU cache на 8 или 16 элементов.
Вот каждая локация в памяти, ей с ней ассоциирована один кашлят, в который она может попасть.
То есть 8 или 16 кашлиний, которые действуют вместе как один ЛРУ кэш, в который эта локация в памяти может быть записана.
И, соответственно, когда она записана среди этих 8 или 16 элементов, ищется самой продухшей и выбивается из каша.
И в реальности вот киши работают так.
И вот если мы посмотрим на адрес с точки зрения вот этой киш системы, то там можно выглядеть три такие составные части.
Во-первых, так мы работаем со целыми кишлиниями.
Последние 6 бит, они будут указывать только offset внутри этой кишлинии.
То есть они будут указывать, только кодировать, только byte.
Афсет внутри кашлиния, и мы работаем с отдельными кашлиниями сразу, и поэтому что там конкретно записано с точки зрения систем бампси, неважно.
Дальше будет какое-то количество бит, которые будут указывать на кэшсет, которым это место в память все соответствует.
Вот это количество бит зависит от размера кэша и зависит от этого параметра ассоциативности, то есть сколько кэшлений в каждой группе.
И все остальное, оно, по сути, используется только для того, чтобы отличать кэшление друг от друга.
Вот такой вот вопрос предпоследний.
Вот если мы создадим массив какой-то, который вмещается в кэш.
И мы будем атерироваться по нему с шагом 256 и атерироваться по нему с шагом 257.
то будут ли они как-то отличаться значительно по прозвительности и как?
Будут ли первые сильно быстрее?
Будут ли первые в Дарзе быстрее?
Будут ли они примерно одинаковые?
256-257 считается примерно одинаковым.
Будут ли они... Будут ли второй в Дарзе быстрее или будет ли второй сильно быстрее?
Это, возможно, как-то связано с тем, что я только что рассказал.
256 это ровно 16 кишлений, 256 линтов в каждое кишление по 16 линтов.
257 это 16 линей плюс чуть-чуть еще.
Вот, и такой очень контратитивный ответ.
Второй вариант, когда мы и трируем с шагом 257, ну точнее вот, вот первый вариант, он медленнее в 10 раз, чем вот второй вариант с страйдом 257.
Верните мои слайды, пожалуйста.
Да, и это на самом деле так не только для конкретно шага 257, но и для любых таких вот круглых, делящихся на большую степень двойки шагов.
Вот когда мы прыгаем вот на следующий элемент с фагом каким-то кратным большой степень дуйки, у нас в нашем адресе последние сколько-то бит они не меняются, потому что мы прибавляем в какую-то большую степень дуйки.
И эти биты они отвечают за кэшсет, в который мы этот адрес мапается.
Если они остаются постоянно неизменными, то получается так, что
У нас фактически используется меньше различных cache-сетов, и наш эффективный cache, который действительно используется, будет сильно меньше.
Вот так как мы загружаем каждую cache-линию в первом варианте, каждую 16-ую cache-линию, то их, соответственно, будет используемых cache-сетов в 16 раз меньше.
А когда у нас совсем не степень двойки, то вот это уж такое иногда, вот раз в 16-е трат, или сколько там съезжает на следующую cache-линию, и мы используем весь наш cache.
И поэтому вот такая вот большая разница, нам каша не хватает, и мы начинаем читать массив либо со следующего уровня каша, либо из оперативных памяти, которые обычно на порядке медленнее.
И вот такая ситуация, она на самом деле возникает гораздо чаще, чем вы думаете, потому что программисты просто любят использовать везде степени двойки, ну, там, по разным причинам.
А те программисты, которые не любят использовать степени двойки, не любят большие круглые двоичные числа, любят большие круглые юдестичные числа,
и они тоже делятся на степени двойки, потому что двойка 10.
И вот несколько вот реальных примеров, вот если взять, если взять матричное умножение из учебника и запустить его на квадраты матрицы размера 256, то оно будет на 30 процентов медленнее, чем на квадраты матрицы размера 257.
Вот это происходит потому, что нам во время алгоритма нужно вот итерироваться по столбцу одной из матриц, и мы это делаем, соответственно, со сетом
Но с шагом кратным размером матрицы, если это размер матрицы кратен какой-то степени двойки, то у нас будут вот такие же проблемы с ассоциативностью.
Или вот другой менее тривельный пример.
Если запустить бинарный поиск на массиве размера 2 степени 20,
то он будет на 20% медленнее, чем на массиве размера 2 степени 20 плюс 123, какой-то там не круглый.
Вот это связано с тем, что нам в бинарной поиске важно вот эти вот первые элементы, с которыми мы всегда сравниваемся, то есть там с середины массива, с середины и левой половиной, с середины и правой половиной.
Нам важно, чтобы они были в каша, потому что мы с ними часто всегда сравниваемся.
И когда у нас массив размера 2 в степени 20, какой-то большой степени двойки, то у нас середина массива, она тоже будет большой степени двойки, вот 2 в степени 19.
И середина левая половина тоже будет большой степени двойки, середина правая половина тоже будет большой степени двойки и так далее.
То есть они будут мапаться в одни и те же кашсеты, и на них не будет хватать вот каша.
и поэтому будет замедление вот для таких выделящих на большей степени двойки размеров.
Вот я в предыдущих примерах, когда вот показывал Пойнтеры, я показывал не настоящие Пойнтеры, я просто на клавиатуры накликал какую-то случайную последовательность 32.0 единичек.
Вот реальные указатели выглядят не так.
Вот если вот взять какой-нибудь там, выделить массив чаров и сделать риентор предказ от него и там побитого расчатывать, то получится что-то такое.
Во-первых, он больше, потому что используются 64-битные указатели.
Вот когда-то использовались 32-битные указатели, но 32-битные указатели могут адресовать только 2-32 различных байт, это 4 гигабайта.
И когда людям стало не хватать 4 гигабайт, перешли сразу на 64-битные указатели, и в них можно адресовать, получается, вот, гига, терапета, экзо, вот, 16 экзобайт.
И если вам кажется, что прыжок сразу до 16 хб, это слишком overkill, то вы не одни.
Производителям железа тоже такаются.
И поэтому в действительности используются не 64 бита, а только нижние 48.
А верхние 16 на практике всегда зонуляются и игнорируются.
И в них, кстати, можно хранить какие-нибудь данные.
Вот, но нижние 48 все еще используются.
И игно достаточно, чтобы адресовать 256 терабайт данных.
И вот на моём компьютере, на моём ноутбуке столько нет.
На моём ноутбуке всего 16 гигабайт, этого хватает примерно для трёх вкладок в хроме.
И для трёх, для 16 гигабайт нужно достаточно 34 бита.
И, соответственно, всё, по идее вот всё, что выше 34-го бита, по идее должно быть за нулено.
Но здесь оно не за нулено.
Здесь вот эта вот красная область, в ней что-то есть на нулевое.
Вот что здесь происходит?
Все дело в том, что пользовательские процессы используют не физические адреса, они используют не физические адреса, не локации каких-то там флифлопов или конденсаторов оперативной памяти, а они используют виртуальные адреса.
Вся память вот физическая, она разбитая на блоке по умочанию вот по четыре килобайта, вот на странице.
И когда что-то лоцируется, вот где-то есть свободный блок из четырех килобайт,
И выдается вместо физического указательного на него, выдается, генерируется виртуальный.
И эти виртуальные адресы, они рандомизируются в целях безопасности.
То есть вот все вот эти 48 бит,
Они могут быть не нулевыми, потому что они сгенерены случайно.
И эта вся схема нужна для виртуализации, для изоляции процессов и многих других полезных вещей.
Вот как это связано с производительностью?
Чтобы нам загрузить что-то из оперативной памяти,
Нам нужно, мы это делаем с помощью физического адреса.
А у нас в процессе используются виртуальные.
И нам нужно замапать этот виртуальный адрес в физический.
И это довольно сложная задача, потому что вот если вот посчитать, сколько нам нужно хранить вот этих маппингов, то нужно вот мои 16 гигабайт поделить на 4 килобайта размер страницы.
И получается 4 миллиона страниц.
И это делает специальная отдельная структура, таблица страниц, почитайбл.
И чтобы она работала быстрее, у нее есть отдельный транслейшн Лукасайт бафер сокращен на TLB.
На данном конкретном CPU у TLB есть два уровня.
На первом уровне есть маппинг для 63 страниц.
И на втором уровне, чуть более медленным, есть маппинг для 2048 страниц.
И вот в связи с этой информацией, давайте снова посмотрим на этот график, где мы здесь делаем константное количество итераций, инкримицируем элементы, просто делаем это с разными страйдами, перескакиваем через разное количество элементов.
А если мы увеличим размер вот этого D step size с нескольких сотен до порядка тысяча, то будет сильно быстрее, чуть быстрее, примерно так же, чуть медленнее или сильно медленнее.
И мы ставим размер ступеньки не тысяча, а что-то тысяча только не круглее, там тысяч или один или тысяча двадцать пять.
Что будет, если вот этот график направил продолжить?
И покажите последний вопрос.
Покажите обратно слайдно.
Да, вот, начиная с какого-то момента, вот если у нас строят больше, чем 256, то если вот посчитать, сколько вот этого область памяти, которую мы когда-либо затрагиваем, занимается в страницах, то получается, что там
У нас для страйда больше, чем 256, нужно 2000 страниц или более.
У нас в TLB вмещается только 2000 страниц.
И, соответственно, для страйда больше, чем 256 мы будем не вмещаться в TLB, и мы будем обращаться к этой медленной странице, таблице страниц.
и которая работает гораздо медленнее.
И поэтому будет такое резкое замедление в пять раз.
Это правда легко полещить.
Можно изменить размер страницы, которые используются.
Это можно сделать либо глобально.
В разных операционных системах это делается по-разному.
Можно это сделать либо глобально, чтобы вообще на каждой локации выделялась большая страница.
Вот CPU по умолчанию использует вот четыре килобайта.
И там обычно есть опция выделить страницу в 2 мегабайта, а на каких-нибудь сервенных CPU есть опция выделить страницу по гигабайтам.
Это нужно для каких-нибудь сервенных, где там совсем много памятей, чтобы каждый раз он учитывался с L1TLB, с минимальной сдержкой.
Либо это можно сделать для какой-то одной конкретной локации, но это в разных операционных системах делается по-разному.
Вот и проблема такая полностью исчезает, потому что мы используем большие страницы, и нам нужно сохранить папинг для меньшего количества страниц, и он вмещается в отелда.
Еще большие страницы они также помогают снизить задержку.
И вообще, если вы можете пожертвовать гранулярностью, то практически всегда имеет смысл вывключать.
Я где-то в интернете видел пост какого-то Linux геймера, который включил у себя вот huge pages, большая страница, и за все какую-то игру и по учетам прирост FPS на 10% просто заменил одну настройку в операционной системе.
Вот, и если вы работаете с более чем несколько мегабайтами памяти, практически всегда их имеет смысл вывключать.
Но я знаю один такой интересный контр-пример.
Вот если мы будем атерироваться с очень большим страйдом, делящимся на степень двойки, то если мы включим большие страницы, то это будет работать 5 раз медленнее, чем с обычными страницами.
Вот здесь такой замысловатый механизм.
Вот суть в том, что если мы
Если мы прыгаем с какими-то большим offset-ом, то наш адрес физической страницы мы прыгаем на какую-то другую страницу, обычно, если у нас маленькие страницы.
И его физический адрес как бы рерандомизируется.
То есть наша виртуальная страница меняется и она мапается в какую-то абсолютно другую физическую страницу.
И поэтому вот эти вот верхние биты в физическом адресе они как бы рерандомизируются.
С большими страницами нам нужно прыгать на гораздо большее offset, чтобы это происходило.
И поэтому, когда мы прыгаем на какой-то offset большой степень двойки, и у нас включены большие стринцы, то у нас в физическом адресе гораздо больше последних бит не меняются, и у нас все эти проблемы со статевностью становятся еще хуже.
Я оцениваю, что примерно 20% из вас поняли это объяснение.
Если вы в эти 20% не входите, то не беспокойтесь.
Если вы и так решаете эту проблему социативностью, то эта проблема у вас не возникнет.
Этот пример просто интересен тем, что это такой вот пример как
самый худший и возможный способ читать что-то из памяти.
Вот и для контраста вот можно взять, написать второй цикл, где мы интервируемся со страйдом 2 в степени 18 плюс 123.
Ну, с каким-то таким же только не круглым.
И первый цикл будет работать 280 раз.
А если мы еще выкрутим тактовую частоту процессора на всю катушку, то он будет работать в 520 рассмертания, чем второй.
То есть это разница между чтениями постоянно из-за леденкаша на процессоре, который работает почти на частоте 5 ГГц.
И вот с таким вот кейсом, когда все, что может идти плохо, идет плохо, и на каждом уровне каша есть проблемы с состемностью.
Вот последнее, про что я хотел поговорить, это вот я обещал нормально замерять Лейтенце.
Вот мы его замеряли, и там получился такой вот неудобный график, где у нас, где нельзя нормально восстановить залежку.
И мы сейчас знаем достаточно, чтобы его померить нормально.
Для этого нужно построить такую персновку, которая каждый раз прыгает на новую страницу и еще и прыгает на новую кашлинию, чтобы ничего нигде не шарилось.
И здесь получаются такие вот явные ступеньки, по которым можно установить latency.
Но, к слову, в реальных бенчмарках с такими странными персновками не связываются и просто заходят в BIOS, отключают Prefetching и используют там специальные hardware performance counters, чтобы замерить это все дело напрямую.
Мы поговорили про довольно много тем, но еще больше тем мы не затронули.
И если вы хотите дальше погружаться в эту область, то в моей книжке есть 9-я глава.
на которой доклад основывается.
Там есть все бенч-парки, все коды и там все детали.
Есть еще такая вот every programmer should know about memory.
Это такая PDF-ка из 2007 года на 114 страниц двухколоночного текста, на которой выросло несколько поколений программистов.
И если вам, в принципе, нравится доклад такого стиля, вот у Тюмура Думлера есть one fast C++, но ее hardware, очень рекомендую.
Вот, и если у вас есть какие-то вопросы, там пожелания, и особенно если у вас есть какие-то такие вот интересные аномалии, то присылайте.
Если хотите получить ответ в ближайшие 5 минут или сколько у меня будет на вопросы, то присылайте их в чат Московского трека.
Если вы это смотрите на YouTube через, там, спустя 4 месяца, то присылайте их в личку либо на почту.
Вот, на этом моменте у меня всё, спасибо.
Это называется, когда приготовил так много интересных примеров, что времени на вопросы не осталось.
Поэтому все вопросы задавайте в чат московского трека, и Сергей на них ответит.