c - 避免 if in 循环

Question

上下文

Debian 64。 Core 2 二人组。

摆弄循环。我使用了同一循环的不同变体，但我希望尽可能避免条件分支。

但是，即使我认为它也很难被击败。

我考虑过 SSE 或位移位，但它仍然需要跳转(看看下面计算的 goto)。剧透:计算跳跃似乎不是正确的方法。

该代码是在没有 PGO 的情况下编译的。因为在这段代码上，它使代码变慢..

标志: gcc -march=native -O3 -std=c11 test_comp.c

展开循环在这里没有帮助..

63 在 ascii 中是“?”。

printf 在这里强制执行代码。仅此而已。

我的需要:

避免该情况的逻辑。我认为这是对我的节日的挑战:)

代码:

用句子进行测试。人物 '？'保证存在，但位置随机。

hjkjhqsjhdjshnbcvvyzayuazeioufdhkjbvcxmlkdqijebdvyxjgqddsyduge?iorfe

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv){

/* This is quite slow. Average actually. 
 Executes in 369,041 cycles here (cachegrind) */
   for (int x = 0; x < 100; ++x){

        if (argv[1][x] == 63){
            printf("%d\n",x);
            break;
        }

    }


/* This is the slowest. 
 Executes in 370,385 cycles here (cachegrind) */
    register unsigned int i = 0;
    static void * restrict table[] = {&&keep,&&end};

keep:

    ++i;
    goto *table[(argv[1][i-1] == 63)];

end:
    printf("i = %d",i-1);


/* This is slower. Because of the calculation.. 
  Executes in 369,109 cycles here (cachegrind) */

    for (int x = 100; ; --x){

        if (argv[1][100 - x ] == 63){printf("%d\n",100-x);break;}


    }

    return 0;
}

问题

有没有办法让它更快，也许可以避免分支？ 分支未命中率高达 11.3%(cachegrind 带有 --branch-sim=yes)。

我认为这不是能达到的最好结果。

如果你们中的一些人有足够的才能来管理装配，请加入。

Answer 1

假设您有一个已知大小的缓冲区，能够容纳要测试的最大数量的 char，例如

char buffer[100];

增大一个字节

char buffer[100 + 1];

然后用要测试的序列填充它

read(fileno(stdin), buffer, 100);

并将测试字符 '?' 放在最后

buffer[100] = '?';

这允许您进行只有一个测试条件的循环:

size_t i = 0;
while ('?' != buffer[i])
{
  ++i;
}

if (100 == i)
{
  /* test failed */
}
else
{
  /* test passed for i */  
}

所有其他优化都留给编译器。

但是我无法抗拒，所以这里有一个可能的方法来进行微观优化

char buffer[100 + 1];

read(fileno(stdin), buffer, 100);
buffer[100] = '?';

char * p = buffer;
while ('?' != *p)
{
  ++p;
}

if ((p - buffer) == 100)
{
  /* test failed */
}
else
{
  /* test passed for (p - buffer) */  
}