Dr. ABT - 1 year ago 98

C++ Question

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.

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 Source

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
```