Почему "inc dword [esp + ebx]" быстрее, чем "inc [esp]"?

У меня есть следующая программа сборки NASM, которая длится около 9,5 секунд:

section .text
global _start

_start:
  mov eax, 0
  mov ebx, 8
  loop:
    inc dword [esp + ebx]
    inc eax
    cmp eax, 0xFFFFFFFF
    jne loop

  mov eax, 1
  mov ebx, 0
  int 0x80

Но если я заменил [esp + ebx] на [esp + 8] (такое же место памяти, что и ebx = 8) или даже просто [esp], он запустится через 10,1 секунды...

Как это возможно? Не проще [esp] вычислить процессор, чем [esp + ebx]?

Ответы

Ответ 1

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

Различные альтернативы, которые вы указали, собраны в следующие кодировки.

0:  ff 04 1c                inc    DWORD PTR [esp+ebx*1]
3:  ff 04 24                inc    DWORD PTR [esp]
6:  ff 44 24 08             inc    DWORD PTR [esp+0x8]

[esp] и [esp+reg] оба кодируются в 3 байта, [esp+8] занимает 4 байта. Поскольку цикл начинается в некотором случайном месте, дополнительный байт выталкивает (часть) инструкцию jne loop в следующую строку кэша.

Линия кэша обычно составляет 16 байт.

Вы можете решить эту проблему, переписав код следующим образом:

  mov eax, 0
  mov ebx, 8
  .align 16             ;align on a cache line.
  loop:
    inc dword ptr [esp + ebx]                 ;7 cycles
    inc eax                                   ;0 latency drowned out by inc [mem]
    cmp eax, 0xFFFFFFFF                       ;0   "          "
    jne loop                                  ;0   "          "

  mov eax, 1
  mov ebx, 0
  int 0x80

Этот цикл должен принимать 7 циклов на итерацию.

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

  mov eax, 1      ;start counting at 1
  mov ebx, [esp+ebx]
  .align 16
  loop:         ;latency   ;comment
    lea ebx,[ebx+1]  ; 0   ;Runs in parallel with `add`
    add eax,1        ; 1   ;count until eax overflows
    mov [esp+8],ebx  ; 0   ;replace a R/W instruction with a W-only instruction   
    jnc loop         ; 1   ;runs in parallel with `mov [mem],reg`

  mov eax, 1
  xor ebx, ebx
  int 0x80

Этот цикл должен принимать 2 цикла на итерацию.

Заменив inc eax на add и заменив inc [esp] инструкциями, которые не изменяют флаги, вы позволяете процессору параллельно выполнять инструкции lea + mov и add+jmp.
add может быть быстрее на более новом процессоре, потому что add изменяет флаги all, тогда как inc изменяет только подмножество флагов.
Это может привести к задержке частичного регистра в команде jxx, поскольку она должна дождаться разрешения частичной записи в регистр флагов. mov [esp] также быстрее, потому что вы не выполняете цикл read-modify-write, вы только записываете в память внутри цикла.

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

Подводя итог:

  • Избегайте инструкций Read-modify-write в цикле, попробуйте заменить их отдельными инструкциями для чтения, изменения и записи или переместите чтение/запись вне цикла.
  • Избегайте inc для управления счетчиками циклов, вместо этого используйте add.
  • Попробуйте использовать lea для добавления, когда вас не интересуют флаги.
  • Всегда выравнивайте небольшие циклы в строках кэша .align 16.
  • Не используйте cmp внутри цикла, команда inc/add уже изменяет флаги.