17.12.2018 03:03
32bit_me 20 4400 Источник

Проклятие недетерминизма



Моя первая попытка написать проход LLVM — люблю эти сегфолты

Недавно я столкнулся с интересной задачей — мне понадобился детерминированный и кросплатформенный способ определения времени выполнения кода С++. Под словом «детерминированный» я подразумеваю, что один и тот же код будет выполняться за одно и то же количество единиц времени. Под кроссплатформенностью я понимаю, что один и тот же код под Windows и под Ubuntu будет выполняться за одно и то же количество единиц времени.

Естественно, измерение времени на CPU не удовлетворяет этим условиям. Машинный код меняется в зависимости от архитектуры и операционной системы, и один и тот же код займёт различное количество времени при выполнении. Даже на одной и той же машине, такие факторы, как промахи кэша, будут играть большую роль — достаточную для того, чтобы исказить результаты измерения времени выполнения одного и того же кода. Мне нужно было что-либо более умное…

Мотивация


Я столкнулся с этой проблемой, когда работал над моим проектом, Code Character. Code Character — это онлайновое соревнование AI, в котором участники пишут ботов для управления армией в пошаговой стратегии. Я хотел ограничить количество кода, которое участник может выполнить за один ход.

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

Байткод LLVM


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

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

Если вы не знакомы с LLVM, он представляет собой коллекцию модульных и повторно используемых технологий компилятора и тулчейна. Одним из главных проектов является LLVM IR и бэкенд. В простых терминах, разработано промежуточное представление (Intermediate Representation), в которое компилирующий фронтенд компилирует код. Затем этот код, LLVM IR, компилируется в машинный код бэкендом LLVM. Таким образом, если вы делаете новый язык, вы можете решить позволить LLVM поддерживать генерацию машинного кода и его оптимизацию, и написать фронтенд для преобразования вашего языка в LLVM IR.


Clang конвертирует код C++ в LLVM IR, который затем преобразуется в машинный код бэкендом LLVM.

Clang является фронтендом LLVM. Так как нам нужен кроссплатформенный метод измерения кода, мы не можем инструментировать бинарный код. LLVM IR, однако, является платформенно-независимым, так как это только промежуточное представление кода. Инструментирование IR кода с помощью библиотек LLVM является простым кросс-платформенным решением.

Решение


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

Базовым блоком называется набор инструкций, в котором входной точкой может быть только первая инструкция, а выходной точкой — только последняя инструкция. (также запрещены любые переходы внутри базового блока — прим. перев.) Чтобы понять это, попробуйте разделить код на куски, в которых инструкции ветвления (переходов, циклов и возвратов) могут быть только последними в наборе, а вход в блок (первая инструкция в функции, цикле или блоке if/else) возможен только на первую инструкцию. В результате получается набор базовых блоков — блоков последовательного кода, который просто выполняется последовательно, без принятия решений о том, какая инструкция выполняется следующей.

Почему бы нам не попробовать прямо сейчас? Это фрагмент кода, предоставленного участником Code Character:

// Make the soldiers who aren't patrolling attack the enemy
for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) {
    auto &soldier = state.soldiers[i];
    if (soldier.hp == 0) // If this soldier is dead, skip it
        continue;

    for (auto enemy_soldier : state.enemy_soldiers) {
        if (enemy_soldier.hp != 0) { // Ensure your prospective target has
                                     // not already been slain
            soldier.soldier_target = enemy_soldier.id;
            break;
        }
    }
}

Ссылка на Github: https://gist.github.com/JHurricane96/8c9c3a45ec5e969de4d9fecb47ebef69#file-player_code-cpp

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

//-------------------------------- BB 1 ----------------------------------
for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) {
//-------------------------------- BB 2 ----------------------------------
    auto &soldier = state.soldiers[i];
    if (soldier.hp == 0)
//-------------------------------- BB 3 ----------------------------------
        continue;
//-------------------------------- BB 4 ----------------------------------
    for (auto enemy_soldier : state.enemy_soldiers) {
//-------------------------------- BB 5 ----------------------------------
        if (enemy_soldier.hp != 0) {
//-------------------------------- BB 6 ----------------------------------
            soldier.soldier_target = enemy_soldier.id;
            break;
//-------------------------------- BB 7 ----------------------------------
        }
    }
}

Ссылка на Github
Это помогло нам понять, как работают базовые блоки, теперь рассмотрим этот алгоритм в LLVM IR:


; <label>:140:                                    ; preds = %181, %139
%141 = load i32, i32* %19, align 4
%142 = sext i32 %141 to i64
%143 = icmp slt i64 %142, 20
br i1 %143, label %144, label %184

; <label>:144:                                    ; preds = %140
%145 = getelementptr inbounds %"struct.player_state::State",
    %"struct.player_state::State"* %2, i32 0, i32 1
%146 = load i32, i32* %19, align 4
%147 = sext i32 %146 to i64
%148 = call dereferenceable(72) %"struct.player_state::Soldier"*
    @_ZNSt5arrayIN12player_state7SoldierELm20EEixEm(
    %"struct.std::array.10"* %145, i64 %147) #3
store %"struct.player_state::Soldier"* %148,
    %"struct.player_state::Soldier"** %20, align 8
%149 = load %"struct.player_state::Soldier"*,
    %"struct.player_state::Soldier"** %20, align 8
%150 = getelementptr inbounds %"struct.player_state::Soldier",
    %"struct.player_state::Soldier"* %149, i32 0, i32 2
%151 = load i64, i64* %150, align 8
%152 = icmp eq i64 %151, 0
br i1 %152, label %153, label %154

; <label>:153:                                    ; preds = %144
br label %181

Ссылка на Github

Если вы посмотрите внимательно, вы заметите, что фрагмент кода, приведённый выше, представляет собой первые три блока фрагмента кода С++, скомпилированный в LLVM IR (каждая строка — это начало базового блока).

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

Сейчас у нас есть базовые блоки и LLVM API, становится простым делом подсчитать количество выполняемых инструкций при помощи такого простого алгоритма:

  1. Напишем функцию IncrementCount, которая принимает целое и инкрементирует статическое целое этим значением, при каждом вызове. Её нужно слинковать с кодом участника.
  2. Делаем итерации по всем базовым блокам. Для каждого базового блока выполняем шаги 3 и 4
  3. Находим n — число инструкций в этом базовом блоке.
  4. Вставляем вызов функции IncrementCount перед последней инструкцией базового блока, с аргументом n.
  5. Статическое целое, с которым работает IncrementCount, и будет счётчиком инструкций после того, как код будет выполнен. Он может быть сохранён где-то и затем проверен.

Наш инструментированный IR работает так:

; <label>:140:                                    ; preds = %181, %139
%141 = load i32, i32* %19, align 4
%142 = sext i32 %141 to i64
%143 = icmp slt i64 %142, 20
call void @_Z14IncrementCountm(i32 4)
br i1 %143, label %144, label %184

; <label>:144:                                    ; preds = %140
%145 = getelementptr inbounds %"struct.player_state::State",
    %"struct.player_state::State"* %2, i32 0, i32 1
%146 = load i32, i32* %19, align 4
%147 = sext i32 %146 to i64
%148 = call dereferenceable(72) %"struct.player_state::Soldier"*
    @_ZNSt5arrayIN12player_state7SoldierELm20EEixEm(
    %"struct.std::array.10"* %145, i64 %147) #3
store %"struct.player_state::Soldier"* %148,
    %"struct.player_state::Soldier"** %20, align 8
%149 = load %"struct.player_state::Soldier"*,
    %"struct.player_state::Soldier"** %20, align 8
%150 = getelementptr inbounds %"struct.player_state::Soldier",
    %"struct.player_state::Soldier"* %149, i32 0, i32 2
%151 = load i64, i64* %150, align 8
%152 = icmp eq i64 %151, 0
call void @_Z14IncrementCountm(i32 10)
br i1 %152, label %153, label %154

; <label>:153:                                    ; preds = %144
call void @_Z14IncrementCountm(i32 1)
br label %181

Ссылка на Github

Как мы видим, вызов IncrementCount сделан в конце каждого базового блока прямо перед последней инструкцией. Используя статический int, с которым работает IncrementCount, мы можем получить число инструкций в конце каждого хода участника. Этот способ детерминированный и кросс-платформенный, т.к. один и тот же исходный код гарантированно порождает один и тот же LLVM IR, если мы используем ту же версию компилятора и те же флаги.

Заключение


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

Исходный код прохода вы можете взять здесь.

Комментарии (20)


  1. dipsy
    17.12.2018 08:50
    #19508320

    А соревнования тоже на виртуальной машине проводятся или всё-таки на реальной?

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


    1. mwizard
      17.12.2018 09:04
      #19508348

      Почему по среднему? Обычно оценивают по наименьшему времени. Быстрее минимума не выполнишь, все остальное — джиттер, вносимый системой.


      1. dipsy
        17.12.2018 09:45
        #19508446

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


        1. mwizard
          17.12.2018 12:47
          #19509542

          Реальное время выполнения программы (T) состоит из времени выполнения собственно самой программы (t) + накладные расходы на работу планировщика + все другие задачи, которые вклинились планировщиком во время выполнения нашей задачи + джиттер процессора из-за переключения во всякие SMM и другие прерывания, над которыми у ОС нет контроля.

          Т.е. в идеальном случае T = t в большинстве случаев, затем T = t + q в меньшем количестве случаев, T = t + 2q в еще меньшем, T = t + 3q еще реже и т.д. Т.е. распределение не нормальное, и усреднять в таком случае бессмысленно.


  1. Imaskar
    17.12.2018 10:51
    #19508738

    То есть участник вложит 10 циклов друг в друга и получит 11 базовых блоков? Это будет нормальный алгоритм по вашей метрике.


    1. 32bit_me Автор
      17.12.2018 10:53
      #19508744

      Считается не количество базовых блоков, а количество команд в базовых блоках, которые были фактически выполнены при запуске программы.


      1. Imaskar
        17.12.2018 11:02
        #19508796

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


        1. 32bit_me Автор
          17.12.2018 11:24
          #19508906

          Нет. Здесь мы считаем не только инструкции перехода, а все инструкции.


  1. lieff
    17.12.2018 13:33
    #19509872
    +1

    Тоже нужен был детерминированный профайлинг, только для реальных архитектур x86/x64/armv7/aarch64/mips. Сделал через QEMU github.com/lieff/qemu-prof.
    Очень удобно профайлить в CI и отслеживать изменения от коммита к коммиту. По времени такое не сделать т.к. изменения обычно небольшие, и если измерять на хардваре, то даже если много циклов делать, — зависит от фазы луны и температуры в датацентре. Не говоря уже о том, что в CI сборщик обычно не фиксирован и реального железа архитектур отличных от x86 обычно нет.


    1. atrosinenko
      17.12.2018 14:22
      #19510274
      +1

      Кстати о птичкахQEMU: насколько мне известно, при указании опции -icount (возможно, ещё с какими-то параметрами) — получаете подсчёт инструкций "из коробки" (вроде, там в каждый translation block добавляется соответствующее изменение счётчика выполненных инструкций и, можно надеяться, исключения тоже обрабатываются корректно). Вот только с user-mode эмуляцией никогда на это не смотрел (я вообще на неё особо не смотрел)… Возможно, к этому счётчику можно как-то прицепиться, правда логика там малость запутанная.


      Кстати, а Valgrind в режиме cachegrind чего-нибудь подобного не умеет?


      1. lieff
        17.12.2018 15:53
        #19510922

        С -icount как-то не получилось, qemu-system-arm на нее не ругается, а вот qemu-arm пишет:

        qemu: unknown option 'icount'

        Да и в любом случае блоки нужны, чтобы показать профайл по функциям, а посчитать блок и самому не так сложно + можно тяжелые инструкции, если что, пропарсить, и им больше клоктиков приписать.
        А так мне самому интересно, как это еще сделать менее костыльно, выдача блоков все-таки сильно тормозит QEMU, если влезть в его код можно профайл сильно ускорить. И ничего более путного чем QEMU я не нашел пока для этих целей.


  1. atrosinenko
    17.12.2018 14:35
    #19510350

    LLVM IR, однако, является платформенно-независимым, так как это только промежуточное представление кода.

    Немного позанудствую: разработчики LLVM пишут, что совсем платформенно-независимый код не получится (препроцессор, размеры типов и т.д.)


    Кстати, эта задача напомнила мне то, с чем столкнулись разработчики mozilla rr (это time-travelling debugger, основанный на полном воспроизведении недетерминированного поведения) — им потребовалось в точности (или почти?) воспроизводить количество инструкций между некоторыми точками выполнения (вероятно, переключениями потоков/процессов) — в итоге их инструмент работает только на достаточно свежих Интеловских процессорах с достаточно стабильными используемыми ими performance counter-ами (были попытки поддержи Ryzen, но чем закончились, не знаю). Ну, то есть стабильность зависит от микроархитектуры, а не конкретного экземпляре процессора. :) Впрочем, здесь уже никакой платформенно-независимостью и не пахнет, конечно.


  1. kITerE
    17.12.2018 14:48
    #19510416

    Интересный подход, но все же интересно насколько инструкции LLVM IR одинаково легковесны относительно друг друга. Грубо говоря: 1000 инкрементов регистра процессора и 1000 обращений к оперативной памяти совсем не эквиваленты.


    1. 32bit_me Автор
      17.12.2018 15:01
      #19510500

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


  1. ser-mk
    17.12.2018 15:25
    #19510692
    +1

    Очень интересную задачу рассмотрели. Жалко только с Pintool не сравнили производительность. Мне почему то кажется что оверхед не такой большой получится. Причем скорее всего на большом проекте прием с llvm будет проигрывать в памяти, за счет раздувания программы из-за вставок.


    1. 32bit_me Автор
      17.12.2018 15:27
      #19510712

      Да, это же перевод. Про pintool почитаю, интересно.


      1. ser-mk
        17.12.2018 15:34
        #19510768

        Да видел, что перевод. Это немного риторическое высказывание было)

        и поэтому что-либо типа инструмента PIN не подходит для наших целей.

        вот здесь автор как раз упомянул его, но дальше, к сожалению не стал сравнивать.
        Хотя на самом деле правильно производительность мерить, не менее простая задача.
        P.S. скоро как раз будет статья про Pintool.


        1. 32bit_me Автор
          17.12.2018 15:38
          #19510800

          Будет интересно почитать.


  1. Sap_ru
    17.12.2018 22:44
    #19512938

    Сдаётся мне, что результат будет на уровне «посчитать количество операций в программе C».
    Т.к. время выполнения инструкций отличается на порядки, легковесность инструкций для разных архитектур тоже. Даже x32 и x64 будут в реальности давать сильно разные результаты.


    1. 32bit_me Автор
      17.12.2018 23:19
      #19513010

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