Преобразование GCC Inline Assembly CMOV в Visual Studio Assembler

Question

В статье Linear vs. Binary Search существует быстрая реализация двоичного поиска, в котором используется команда CMOV. Я хотел бы реализовать это в VC++, поскольку приложение, над которым я работаю, полагается на производительность двоичного поиска.

Реализация имеет некоторые GCC встроенного ассемблера, который объявлен следующим образом:

static int binary_cmov (const int *arr, int n, int key) { 
    int min = 0, max = n; 
    while (min < max) { 
      int middle = (min + max) >> 1; 

      asm ("cmpl %3, %2\n\tcmovg %4, %0\n\tcmovle %5, %1" 
       : "+r" (min), 
        "+r" (max) 
       : "r" (key), "g" (arr [middle]), 
        "g" (middle + 1), "g" (middle)); 

      // Equivalent to 
      // if (key > arr [middle]) 
      // min = middle + 1; 
      // else 
      // max = middle; 
    } 
    return min; 
} 

Я хотел бы преобразовать эту GCC Ассемблер в Microsoft Visual Studio, совместимый ассемблере, но как GCC нуб не знал, с чего начать.

Может ли кто-нибудь помочь или хотя бы объяснить GCC Inline Assembler? ТИА!

Answer 1

рефакторинга кода для того, чтобы лучше выразить намерение составителя:

int binary_cmov (const int *arr, int n, int key) 
{ 
    int min = 0, max = n; 
    while (min < max) 
    { 
     int middle = (min + max) >> 1; 
     min = key > arr[middle] ? middle + 1 : min; 
     max = key > arr[middle] ? max : middle; 
    } 
    return min; 
} 

С gcc5.3 -O3, выходы:

binary_cmov(int const*, int, int): 
     xorl %eax, %eax 
     testl %esi, %esi 
     jle  .L4 
.L3: 
     leal (%rax,%rsi), %ecx 
     sarl %ecx 
     movslq %ecx, %r8 
     leal 1(%rcx), %r9d 
     movl (%rdi,%r8,4), %r8d 
     cmpl %edx, %r8d 
     cmovl %r9d, %eax 
     cmovge %ecx, %esi 
     cmpl %eax, %esi 
     jg  .L3 
     rep ret 
.L4: 
     rep ret 

Мораль - не встраивать ассемблер , Все, что вы делаете, делает код не переносным.

идти дальше ...

почему бы не выразить намерение еще более явно? Выход

#include <utility> 

template<class...Ts> 
    auto sum(Ts...ts) 
{ 
    std::common_type_t<Ts...> result = 0; 
    using expand = int[]; 
    void(expand{ 0, ((result += ts), 0)... }); 
    return result; 
} 

template<class...Ts> 
    auto average(Ts...ts) 
{ 
    return sum(ts...)/sizeof...(Ts); 
} 

int binary_cmov (const int *arr, int n, int key) 
{ 
    int min = 0, max = n; 
    while (min < max) 
    { 
     int middle = average(min, max); 
     auto greater = key > arr[middle]; 
     min = greater ? middle + 1 : min; 
     max = greater ? max : middle; 
    } 
    return min; 
} 

Компилятор:

binary_cmov(int const*, int, int): 
     xorl %eax, %eax 
     testl %esi, %esi 
     jle  .L4 
.L3: 
     leal (%rax,%rsi), %ecx 
     movslq %ecx, %rcx 
     shrq %rcx 
     movslq %ecx, %r8 
     leal 1(%rcx), %r9d 
     movl (%rdi,%r8,4), %r8d 
     cmpl %edx, %r8d 
     cmovl %r9d, %eax 
     cmovge %ecx, %esi 
     cmpl %eax, %esi 
     jg  .L3 
     rep ret 
.L4: 
     rep ret 

Answer 2

Создание небольшое изменение кода Ричард Ходжес также позволяет Visual Studio 2013, чтобы использовать команду CMOV:

int binary_cmov (const int *arr, int n, int key) 
{ 
    int min = 0, max = n; 
    while (min < max) 
    { 
     int middle = (min + max) >> 1; 
     int middle1 = middle + 1; 
     min = key > arr[middle] ? middle1 : min; 
     max = key > arr[middle] ? max : middle; 
    } 
    return min; 
} 

Компиляция с cl /Ox /Fa /c t286.c генерирует:

; Listing generated by Microsoft (R) Optimizing Compiler Version 18.00.40629.0 

binary_cmov PROC 
    mov QWORD PTR [rsp+8], rbx 
; Line 3 
    xor eax, eax 
    mov ebx, r8d 
    mov r11d, edx 
; Line 4 
    test edx, edx 
    jle SHORT $LN9@binary_cmo 
$LL2@binary_cmo: 
; Line 6 
    lea r10d, DWORD PTR [r11+rax] 
    sar r10d, 1 
; Line 8 
    movsxd r8, r10d 
    lea r9d, DWORD PTR [r10+1] 
    cmp ebx, DWORD PTR [rcx+r8*4] 
; Line 9 
    cmovg r10d, r11d 
    cmovg eax, r9d 
    mov r11d, r10d 
    cmp eax, r10d 
    jl SHORT $LL2@binary_cmo 
$LN9@binary_cmo: 
; Line 12 
    mov rbx, QWORD PTR [rsp+8] 
    ret 0 
binary_cmov ENDP 

Это также работает с компиляторами Visual Studio 2015 и 2010. С Visual Studio трюк, похоже, заключается в использовании трехмерных операторов и использовании простых переменных в качестве второго и третьего операндов. Если вы замените middle1 на middle + 1 в первом тернарном операторе выше, тогда Visual Studio генерирует только одну инструкцию CMOV для этой функции. Первый тернарный оператор вместо этого генерирует ветвь.

Как уже упоминалось Yakk в комментарии, предстоящий компилятор Visual Stdio 2015 Update 3 содержит основное обновление оптимизатора, которое должно изменить это поведение, что позволяет с большей вероятностью генерировать инструкции CMOV.

Answer 3

Люди уже указывали (неоднократно) на то, что вам следует избегать встроенного asm, если это возможно. Я согласен со всеми из них.

При этом вы также попросили «по крайней мере, объяснить GCC Inline Assembler."Эта часть может быть спорной, но FWIW:

Начиная с шаблоном на ассемблере:.

"cmpl %3, %2\n\tcmovg %4, %0\n\tcmovle %5, %1" 

Есть пару вещей происходит здесь, что может выглядеть странно программист VS

1. cmpl - По умолчанию в asm используется gc as & t синтаксис вместо intel.Это приводит к тому, что некоторые вещи имеют тонкую разницу. Например, l здесь указывает, что сравнение должно применяться к longs (где долго в этом контексте означает 4 тес). Одно из других различий заключается в том, что операнды меняются на противоположные. Таким образом, intel может использовать mov eax, 1, но att будет использовать movl $1, %eax (знак доллара означает постоянный,% обозначает регистр). Есть сайты, которые рассказывают обо всех различиях здесь.
2. \n\t - gcc выводит код на ассемблер. Чтобы поместить каждую из этих трех команд в свои собственные строки, вы добавляете '\ n' для новой строки и '\ t' для того, чтобы вкладка хорошо отображалась.
3. % 0-% 5 - Вы должны подумать о шаблоне ассемблера (строка, содержащая ассемблер), скорее, как строка формата, которую вы отправляете printf. Некоторые части печатаются буквально, а другие детали заменяются (думаю: printf("2 + 2 = %d\n", 2+2);). Таким же образом gcc заменит части шаблона следующими параметрами. % 0 - первый параметр, а% 5 - шестой (пронумерованный в порядке их появления).

Это приводит нас к остальной части команды. Элементы, которые приходят после первого двоеточия являются выходными параметрами:

   : "+r" (min), 
       "+r" (max) 

Знак «+» здесь означает, что переменные чтения и записи. Если они были только выводятся, вы должны использовать '='. Если вы собираетесь читать, но не изменять, вы должны указать его как входной параметр (т. Е. После следующего двоеточия). «R» указывает, что значения должны быть перемещены в регистры перед выполнением asm. Он оставляет решение о , которое регистрируется компилятором. Программисту не нужно знать; он может использовать% 0 для min и% 1 для max, и токен будет заменен соответствующим образом.

Что приводит нас к выходным параметрам. Довольно многое, чего вы ожидаете, кроме того, что 'g' является общим типом ограничения. Теоретически это позволяет сохранять значения в регистре, памяти или в непосредственном значении. В основном это просто регистр.

   : "r" (key), "g" (arr [middle]), 
       "g" (middle + 1), "g" (middle)); 

Есть страницы документов о инлайн ассемблере GCC (см https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html), которые описывают все это в мучительных подробно. Также есть несколько страниц, на которых обсуждаются ограничения, отличные от «r» и «g» (https://gcc.gnu.org/onlinedocs/gcc/Constraints.html).

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

Именно поэтому друзья не говорят друзьям, чтобы они использовали inline assembler.

Эй, вы спросили ...

Answer 4

С обновлением VS2015 3, я мог убедить компилятор использовать cmova и cmovbe путем изменения второго сравнения с> к = <:

int binary_cmov(const int *arr, int n, int key) 
{ 
    int min = 0, max = n; 
    while (min < max) 
    // cmp   r9,r8 
    // jb   binary_cmov+1B0h 
    { 
     int middle = (min + max) >> 1; 
     // lea   rdx,[r8+r9] 
     // shr   rdx,1 
     int middle1 = middle + 1; 
     // lea   rax,[rdx+4] 
     min = key > arr[middle] ? middle1 : min; 
     // cmp   r10,dword ptr [rdi+rdx*4] 
     // cmova  r9,rax 
     max = key <= arr[middle] ? middle : max; 
     // cmovbe  r8,rdx 
    } 
    return min; 
} 

Измерение производительности на i7-5600U с реальным приложением (поиска адресов точек останова), линейный поиск выполняет бинарный поиск до массивов из 512 записей. Я думаю, что скорость ограничена заполнением кеша, а бинарный поиск> 512 записей в основном работают лучше, потому что это позволяет избежать получения части таблицы из памяти.

Код для линейного поиска указателя с Дозорный:

// the array must be terminated with a value that is larger than 
// any value searched for e.g. MAX_INT (the sentinel) 
// the index of the equal or greater entry is returned 
int find_in_terminated_array(const int *arr, int key) 
{ 
    int * p = arr; 
    while(key > *p) +p; 
    return p - arr; 
}