当A是无符号vs有符号时,为什么A/<constant-int>更快？

Question

我一直在阅读优化C++ wikibook.在更快的操作章节中,其中一条建议如下:

整数除以常数

将整数(已知为正或零)除以常量时,将整数转换为无符号.

如果s是有符号整数,则u是无符号整数,C是常数整数表达式(正或负),操作s/C比u/C慢,s%C慢于u%C.当C是2的幂时,最重要的是,但在所有情况下,在分割期间必须考虑符号.

然而,从有符号到无符号的转换是免费的,因为它只是对相同位的重新解释.因此,如果s是有符号整数,您知道它是正数或零,则可以使用以下(等效)表达式加速其除法:(无符号)s/C和(无符号)s%C.

我用gcc测试了这个语句,u / C表达式似乎始终优于s / c

下面还提供了以下示例:

#include <iostream>
#include <chrono>
#include <cstdlib>
#include <vector>
#include <numeric>

using namespace std;

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

    constexpr int vsize = 1e6;
    std::vector<int> x(vsize);
    std::iota(std::begin(x), std::end(x), 0); //0 is the starting number

    constexpr int a = 5;

  auto start_signed = std::chrono::system_clock::now();
  int sum_signed = 0;
    for ([[gnu::unused]] auto  i : x)
    {
        // signed is by default
        int v = rand() % 30 + 1985;   // v in the range 1985-2014

        sum_signed += v / a;
    }
  auto end_signed = std::chrono::system_clock::now();

  auto start_unsigned = std::chrono::system_clock::now();
  int sum_unsigned = 0;
    for ([[gnu::unused]] auto  i : x)
    {
        int v = rand() % 30 + 1985;   // v in the range 1985-2014
        sum_unsigned += static_cast<unsigned int>(v) / a;
    }
  auto end_unsigned = std::chrono::system_clock::now();

  // signed
  std::chrono::duration<double> diff_signed = end_signed - start_signed;
  std::cout << "sum_signed: " << sum_signed << std::endl;
  std::cout << "Time it took SIGNED: " << diff_signed.count() * 1000 << "ms" << std::endl;

  // unsigned
  std::chrono::duration<double> diff_unsigned = end_unsigned - start_unsigned;
  std::cout << "sum_unsigned: " << sum_unsigned << std::endl;
  std::cout << "Time it took UNSIGNED: " << diff_unsigned.count() * 1000 << "ms" << std::endl;

  return 0;
}

您可以在此处编译并运行示例:http://cpp.sh/8kie3

为什么会这样？

Answer 1

在经历了一些玩笑之后,我相信我已经通过标准来确定问题的根源,即从C++ 11开始,负整数除法被舍入为零.对于最简单的情况,即除以2,请查看以下代码和相应的程序集(godbolt链接).

constexpr int c = 2;

int signed_div(int in){
    return in/c;
}

int unsigned_div(unsigned in){
    return in/c;
}

部件:

signed_div(int):
  mov eax, edi
  shr eax, 31
  add eax, edi
  sar eax
  ret

unsigned_div(unsigned int):
  mov eax, edi
  shr eax
  ret

这些额外的指令完成了什么？shr eax, 31(右移31)只是隔离符号位,这意味着如果输入是非负的eax == 0,否则eax == 1.然后输入添加到eax.换句话说,这两条指令转换为"如果输入为负,则添加1到它.添加的含义如下(仅适用于负输入).

• 如果输入是偶数,则将其最低有效位设置为1,但是移位丢弃它.输出不受此操作的影响.

• 如果输入是奇数,则其最低有效位已经是,1因此加法会使余数传播到其余数字.当发生右移时,如果我们没有将符号位添加到输入,则丢弃最低有效位并且输出比我们输出的输出大1.因为默认情况下,在两个补码中右移向负无穷大,输出现在是相同除法的结果,但是向零舍入.

简而言之,即使负数也不受影响,奇数现在向零舍入而不是向负无穷大舍入.

对于非幂2的常数,它会变得更复杂一些.并非所有常量都提供相同的输出,但对于其中很多常量,它看起来类似于以下(godbolt链接).

constexpr int c = 3;

int signed_div(int in){
    return in/c;
}

int unsigned_div(unsigned in){
    return in/c;
}

部件:

signed_div(int):
  mov eax, edi
  mov edx, 1431655766
  sar edi, 31
  imul edx
  mov eax, edx
  sub eax, edi
  ret
unsigned_div(unsigned int):
  mov eax, edi
  mov edx, -1431655765
  mul edx
  mov eax, edx
  shr eax
  ret

我们不关心程序集输出中常量的更改,因为它不会影响执行时间.假设mul并且imul花费相同的时间(我不确定,但希望比我更有知识的人可以在其上找到源),签名版本再次花费更长时间,因为它有额外的指令来处理符号位对于负面的操作数.

笔记

• 使用x86-64 GCC 7.3和-O2标志在godbot上进行编译.

• 从C++ 11开始,标准强制要求零行为.根据此 cppreference页面,在实现定义之前.