Dr. ABT - 1 year ago 241

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!

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**