Внедрение блокировки билета с атомами генерирует дополнительный мотив

Я написал наивную реализацию простой блокировки билетов. Запирающая часть выглядит следующим образом:

struct ticket {
    uint16_t next_ticket;
    uint16_t now_serving;
};

void lock(ticket* tkt) {
    const uint16_t my_ticket =
        __sync_fetch_and_add(&tkt->next_ticket, 1); 
    while (tkt->now_serving != my_ticket) {
        _mm_pause();
        __asm__ __volatile__("":::"memory");
    }   
}

Тогда я понял, что вместо использования gcc-intrinsic я могу написать это с помощью std::atomic s:

struct atom_ticket {
    std::atomic<uint16_t> next_ticket;
    std::atomic<uint16_t> now_serving;
};

void lock(atom_ticket* tkt) {
    const uint16_t my_ticket =
        tkt->next_ticket.fetch_add(1, std::memory_order_relaxed);
    while (tkt->now_serving.load(std::memory_order_relaxed) != my_ticket) {
        _mm_pause();
    }   
}

Они генерируют почти идентичную сборку, но последняя генерирует дополнительную инструкцию movzwl. Почему этот дополнительный mov? Есть ли лучший, правильный способ написать lock()?

Сборка с -march=native -O3:

 0000000000000000 <lock(ticket*)>:
    0:   b8 01 00 00 00          mov    $0x1,%eax
    5:   66 f0 0f c1 07          lock xadd %ax,(%rdi)
    a:   66 39 47 02             cmp    %ax,0x2(%rdi)
    e:   74 08                   je     18 <lock(ticket*)+0x18>
   10:   f3 90                   pause  
   12:   66 39 47 02             cmp    %ax,0x2(%rdi)
   16:   75 f8                   jne    10 <lock(ticket*)+0x10>
   18:   f3 c3                   repz retq 
   1a:   66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)


 0000000000000020 <lock(atom_ticket*)>:
   20:   ba 01 00 00 00          mov    $0x1,%edx
   25:   66 f0 0f c1 17          lock xadd %dx,(%rdi)
   2a:   48 83 c7 02             add    $0x2,%rdi
   2e:   eb 02                   jmp    32 <lock(atom_ticket*)+0x12>
   30:   f3 90                   pause  
=> 32:   0f b7 07                movzwl (%rdi),%eax <== ???
   35:   66 39 c2                cmp    %ax,%dx
   38:   75 f6                   jne    30 <lock(atom_ticket*)+0x10>
   3a:   f3 c3                   repz retq

Почему не просто cmp (%rdi),%dx напрямую?

Ответы

Ответ 1

Прежде всего, я думаю, вам нужно использовать std::memory_order_acquire, так как вы приобретаете блокировку. Если вы используете mo_relaxed, вы можете увидеть устаревшие данные перед некоторыми магазинами, которые сделал предыдущий держатель блокировки. Блог Jeff Preshing превосходный, и у него есть пост по выпуску/приобретению семантики.

В x86 это может произойти только в том случае, если компилятор переупорядочивает нагрузки и хранилища, которые mo_relaxed сообщает, что это разрешено. Приобретающая нагрузка компилируется так же, как и расслабленная нагрузка на x86, но без переупорядочения. Каждая загрузка x86 asm уже является приобретением. На слабоупорядоченных архитектурах, которые в ней нуждаются, вы получите инструкции, необходимые для получения нагрузки. (И на x86 вы просто остановите компилятор от переупорядочения).

Я поставил версию кода на godbolt, чтобы посмотреть на asm с различными компиляторами.

Хорошо заметили, что это похоже на неудачу оптимизации gcc, по-прежнему присутствует как минимум в 6.0 (отмечен Wandbox, используя main, который выполняет return execlp("objdump", "objdump", "-Mintel", "-d", argv[0], NULL);, чтобы вывести сам вывод дизассемблера, включая функции, которые нас интересуют.

Похоже, что clang 3.7 делает это еще хуже. Он выполняет нагрузку 16 бит, затем нулевое расширение, затем сравнивает.

gcc особенно относится к атомным нагрузкам и, по-видимому, не замечает, что он может сворачивать его в сравнение. Вероятно, это был шаг оптимизации, который мог бы произойти, когда атомная нагрузка все еще была представлена ​​иначе, чем обычные нагрузки или что-то в этом роде. Я не gcc-хакер, так что это в основном догадки.

Я подозреваю, что у вас есть старый gcc (4.9.2 или старше), или вы строите на/для AMD, потому что ваш компилятор использовал rep ret даже с -march=native. Вы должны сделать что-то об этом, если вы заботитесь о создании оптимального кода. Я заметил, что gcc5 лучше делает код, чем gcc 4.9. (не то, что это помогает в этом случае, хотя:/)

Я пробовал использовать uint32_t, не повезло.

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

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

IDK, если прыжок в середину цикла имел какие-либо неблагоприятные последствия для кэша uop микроархитектур семейства Intel SnB. Это что-то вроде кэша трассировки. тестирование Agner Fog показало, что один и тот же фрагмент кода может иметь несколько записей в кэше uop, если он имеет несколько точек входа перехода. Эта функция уже немного uop-cache недружелюбна, так как она начинается с mov r, imm / lock xadd. Блокировка xadd должна выполняться в строке кэша uop сама по себе, потому что она микрокодирована (на самом деле это более 4-х дисков 9). Безусловный переход всегда завершает линию кэша uop. Я не уверен в принятой условной ветки, но я бы предположил, что взятый jcc заканчивает линию кэша, если она была предсказана, когда она была расшифрована. (например, запись предсказателя ветвей все еще хороша, но исключена запись старого кэша uop).

Таким образом, первая версия - потенциально 3 строки кэша uops для быстрого пути: один mov (и если вложенный, надеюсь, в основном полный с предыдущими инструкциями), один lock xadd один, один макро-fused cmp/je для следующий код (если указано, если нет, то переход к ret, который может закончиться 4-й строкой кэша для этого 32-байтового кодового блока, который не разрешен. Таким образом, для не-встроенной версии это всегда может быть каждый раз перекодировать?)

Версия std:: atomic снова представляет собой одну строку uop-cache для начального mov imm (и предыдущих инструкций), затем lock xadd, затем add / jmp, затем... uh oh, 4-я тайна кеширования для movzx / compare-and-branch uops. Таким образом, эта версия, скорее всего, будет иметь узкое место декодирования даже при наложении.

К счастью, внешний интерфейс все же может получить некоторую прибыль и получить команды, поставленные в очередь для ядра ООО при запуске этого кода, потому что lock xadd составляет 9 часов. Этого достаточно, чтобы покрыть цикл или два из меньших удалений от внешнего интерфейса и переключиться между декодированием и извлечением uop-cache.

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

Быстрый путь - это 11 совпадающих доменов для старой версии (1 mov imm, 9 lock xadd, 1 cmp/je macro fused). cmp/je включает в себя операнд с микроплавкой памяти.

Быстрый путь - это 41 скомпилированный домен uops для новой версии (1 mov imm, 9 lock xadd, 1 add, 1 jmp, 1 movzx, 1 cmp/je macro fused).

Использование add вместо использования 8-битного смещения в режиме адресации movzx действительно снимает себя в ногу, IMO. IDK, если gcc думает впереди достаточно далеко, чтобы сделать выбор таким образом, чтобы цель ветки ветки получалась на границе 16B, или если это было просто немой удачей.

Эксперимент с идентификатором компилятора на godbolt с использованием кода OP:

  • gcc 4.8 и более ранние версии: всегда используйте rep ret, когда он нацелен на ветвление, даже с -march=native -mtune=core2 (на Haswell) или с помощью только -march=core2.
  • gcc 4.9: Использует rep ret с -march=native на Хасуэлле, вероятно, потому, что Хасуэлл слишком новичок в этом. -march=native -mtune=haswell использует только ret, поэтому он знает имя haswell.
  • gcc 5.1 и более поздние версии: использует ret с -march=native (на Haswell). Все еще использует rep ret, когда -march не указан.

Ответ 2

В первом случае

12:   66 39 47 02             cmp    %ax,0x2(%rdi)

cmp - комбинированная команда mov и cmp (она, скорее всего, сгенерирует две команды в наборе команд микроархитектуры)

Атомный вариант делает отдельное чтение для now_serving с помощью

32:   0f b7 07                movzwl (%rdi),%eax

а затем делает то же самое сравнение с

35:   66 39 c2                cmp    %ax,%dx