4

在将整数写入十六进制字符串函数时，我注意到我有一个不必要的掩码和位移，但是当我删除它时，代码实际上变得更大（大约 8 倍）

char *i2s(int n){
    static char buf[(sizeof(int)<<1)+1]={0};
    int i=0;
    while(i<(sizeof(int)<<1)+1){    /* mask the ith hex, shift it to lsb */
//      buf[i++]='0'+(0xf&(n>>((sizeof(int)<<3)-i<<2))); /* less optimizable ??? */
        buf[i++]='0'+(0xf&((n&(0xf<<((sizeof(int)<<3)-i<<2)))>>((sizeof(int)<<3)-i<<2)));
        if(buf[i-1]>'9')buf[i-1]+=('A'-'0'-10); /* handle A-F */
    }
    for(i=0;buf[i++]=='0';)
        /*find first non-zero*/;
    return (char *)buf+i;
}

使用额外的位移位和掩码并用 编译gcc -S -O3，循环展开并减少为：

    movb    $48, buf.1247
    xorl    %eax, %eax
    movb    $48, buf.1247+1
    movb    $48, buf.1247+2
    movb    $48, buf.1247+3
    movb    $48, buf.1247+4
    movb    $48, buf.1247+5
    movb    $48, buf.1247+6
    movb    $48, buf.1247+7
    movb    $48, buf.1247+8
    .p2align 4,,7
    .p2align 3
.L26:
    movzbl  buf.1247(%eax), %edx
    addl    $1, %eax
    cmpb    $48, %dl
    je  .L26
    addl    $buf.1247, %eax
    ret

这就是我对 32 位 x86 的预期（应该是相似的，但 64 位的类似 movb 的操作数是其两倍）；但是，如果没有看似多余的掩码和位移，gcc 似乎无法展开和优化它。

任何想法为什么会发生这种情况？我猜这与 gcc 对符号位（过度？）谨慎有关。（C 中没有 >>> 运算符，因此如果设置了符号位，则使用 1 与 0 对 MSB >> 填充进行位移）

4

2 回答 2

2

我认为它必须在较短的版本中做到这一点，你左移 ((sizeof(int)<<3)-i<<2) 然后在表达式的后面右移相同的值，所以编译器能够基于该事实进行优化。

关于右移，C++ 可以做相当于 Java 的运算符 '>>' 和 '>>>'。只是在 [GNU] C++ 中，“x >> y”的结果将取决于 x 是有符号还是无符号。如果 x 有符号，则使用算术右移（SRA，符号扩展），如果 x 无符号，则使用逻辑右移（SRL，零扩展）。这样，>> 可用于将负数和正数除以 2。

展开循环不再是一个好主意，因为：1) 较新的处理器带有一个微操作缓冲区，这通常会加速小循环，2) 代码膨胀会占用 L1i 中的更多空间，从而降低指令缓存的效率。微基准将隐藏这种影响。

算法不必那么复杂。此外，您的算法存在一个问题，即它为 16 的倍数返回“0”，而对于 0 本身，它返回一个空字符串。

下面是算法的重写，除了循环退出检查（或者如果编译器决定展开它，则完全无分支）。它更快，生成更短的代码并修复了 16 倍数的错误。

无分支代码是可取的，因为如果 CPU 错误地预测了分支，就会有很大的损失（15-20 个时钟周期）。将其与算法中的位操作进行比较：它们每个只需要 1 个时钟周期，CPU 能够在同一时钟周期内执行其中的 3 或 4 个。

const char* i2s_brcfree(int n)
{
  static char buf[ sizeof(n)*2+1] = {0};
  unsigned int nibble_shifter = n;
  for(char* p = buf+sizeof(buf)-2; p >= buf; --p, nibble_shifter>>=4){
    const char curr_nibble = nibble_shifter & 0xF; // look only at lowest 4 bits
    char digit = '0' + curr_nibble;
    // "promote" to hex if nibble is over 9, 
    // conditionally adding the difference between ('0'+nibble) and 'A' 
    enum{ dec2hex_offset = ('A'-'0'-0xA) }; // compile time constant
    digit += dec2hex_offset & -(curr_nibble > 9); // conditional add
    *p = digit;
  }
  return buf;
}

编辑：C++ 没有定义右移负数的结果。我只知道 GCC 和 Visual Studio 在 x86 架构上这样做。

于 2017-06-19T17:29:08.383 回答
2

看来您使用的是 gcc4.7，因为较新的 gcc 版本生成的代码与您显示的不同。

gcc 能够看到带有额外移位和掩码的较长表达式始终'0' + 0为 ，但对于较短的表达式则不然。

clang 看穿了它们，并将它们优化为一个独立于函数 arg 的常数n，所以这可能只是 gcc 的错过优化。当 gcc 或 clang 设法优化第一个循环以仅存储一个常量时，整个函数的 asm 甚至从不引用函数 arg, n。

显然这意味着你的功能是错误的！这不是唯一的错误。

  • 在第一个循环中逐一，所以你写了 9 个字节，没有留下终止 0。（否则搜索循环可以优化到，只返回一个指向最后一个字节的指针。如所写，它必须搜索static数组的末尾，直到它找到一个非'0'字节。不幸的是，在搜索循环之前写 a 0(not '0') 并不能帮助 clang 或 gcc 摆脱搜索循环)
  • 在搜索循环中逐一进行，因此您总是返回buf+1或稍后返回，因为您buf[i++]在条件中使用了而不是 for() 循环，并在检查后增加了增量。
  • 在同一语句中使用i++和未定义的行为，没有将它们分开的序列点。i
  • 显然假设CHAR_BIT是 8。（类似于static char buf[CHAR_BIT*sizeof(n)/4 + 1]，但实际上除以 2 时需要四舍五入）。

clang 和 gcc 都警告-优先级低于<<，但我并没有试图找出你哪里出错了。 得到i一个整数的第 nibble 比你做的要简单得多： buf[i]='0'+ (0x0f & (n >> (4*i))); 不过，这编译成相当笨重的代码。gcc 可能在@Fabio 建议tmp >>= 4重复做的情况下做得更好。如果编译器将该循环卷起，它仍然可以使用shr reg, imm8而不需要变量移位。（clang 和 gcc 似乎没有将n>>(4*i)4 优化为重复移位。）

在这两种情况下，gcc 都在完全展开第一个循环。当每次迭代包括实际的移位、比较和分支或无分支处理从Ato的十六进制数字时，它是相当大的F。

当它可以看到它所要做的就是 store 时，它​​就很小了48 == 0x30 == '0'。（不幸的是，它并没有像 clang 那样将 9 字节存储合并成更广泛的存储）。

我在 Godbolt 上放了一个错误修正版本，以及你的原版。

法比奥的答案有一个更优化的版本。我只是想弄清楚 gcc 对你的 gcc 做了什么，因为 Fabio 已经提供了一个可以编译成更高效代码的好版本。（我也对我的进行了一些优化，但没有将 替换为n>>(4*i)。n>>=4）

gcc6.3 为您的更大表达制作了非常有趣的代码。它展开了搜索循环并优化了一些比较，但保留了很多条件分支！

i2s_orig:
    mov     BYTE PTR buf.1406+3, 48
    mov     BYTE PTR buf.1406, 48
    cmp     BYTE PTR buf.1406+3, 48
    mov     BYTE PTR buf.1406+1, 48
    mov     BYTE PTR buf.1406+2, 48
    mov     BYTE PTR buf.1406+4, 48
    mov     BYTE PTR buf.1406+5, 48
    mov     BYTE PTR buf.1406+6, 48
    mov     BYTE PTR buf.1406+7, 48
    mov     BYTE PTR buf.1406+8, 48
    mov     BYTE PTR buf.1406+9, 0
    jne     .L7    # testing flags from the compare earlier
    jne     .L8
    jne     .L9
    jne     .L10
    jne     .L11
    sete    al
    movzx   eax, al
    add     eax, 8
.L3:
    add     eax, OFFSET FLAT:buf.1406
    ret
.L7:
    mov     eax, 3
    jmp     .L3
 ... more of the same, setting eax to 4, or 5, etc.

将多jne条指令排成一行显然是没有用的。

于 2017-07-10T15:26:25.200 回答