Dr. ABT Dr. ABT - 3 months ago 26
C++ Question

Convert GCC Inline Assembly CMOV to Visual Studio Assembler

In the article Linear vs. Binary Search, there is a fast implementation of binary search which uses the CMOV instruction. I would like to implement this in VC++ as the application I'm working on relies on the performance of Binary Search.

enter image description here

The implementation has some GCC inline assembler which is declared as follows:

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;
}


I'd like to convert this GCC Assembler to Microsoft Visual Studio compatible assembler, but as a GCC noob wouldn't know where to start.

Can anyone help, or at least explain the GCC Inline Assembler? TIA!

Answer

refactoring the code in order to better express intent to the compiler:

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;
}

With gcc5.3 -O3, yields:

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

moral of the story - don't embed assembler. All you do is make the code non-portable.

going further...

why not express intent even more explicitly?

#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;
}

compiler output:

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