C ++中的有效整数下限函数

Question

我想定义一个有效的整数下限函数，即从float或double转换为向负无穷大执行截断。

我们可以假设这些值使得没有整数溢出发生。到目前为止，我有一些选择

• 转换为int 这需要对负值进行特殊处理，因为转换会截断为零。

  I= int(F); if (I < 0 && I != F) I--;
  

• 将floor的结果转换为int；

  int(floor(F));
  

• 强制转换为int以获得较大的正数（对于较大的值，这可能会返回错误的结果）；

  int(F + double(0x7fffffff)) - 0x7fffffff;
  

众所周知，将数据类型转换为int很慢。如果测试也是如此。我尚未设置发言权功能的时间，但是看到帖子声称它也很慢。

您能在速度，准确性或允许范围方面考虑更好的替代方法吗？它不需要是便携式的。目标是最新的x86 / x64体系结构。

Answer 1

众所周知，将数据类型转换为int很慢。

自从x86-64以来，您可能一直生活在一块岩石下，或者以其他方式错过了在x86上一段时间以来并非如此的情况。:)

SSE / SSE2有一条指令以截断方式进行转换（而不是默认的舍入模式）。ISA精确地支持此操作，因为在实际的代码库中使用C语义进行转换并不罕见。x86-64代码使用SSE / SSE2 XMM寄存器进行标量FP数学运算，而不使用x87寄存器，因为这样做以及其他一些使效率更高的事情。甚至现代的32位代码也使用XMM寄存器进行标量数学运算。

在针对x87进行编译（不使用SSE3 fisttp）时，编译器曾经不得不将x87舍入模式更改为截断，FP存储到内存，然后再次将舍入模式更改回。（然后再从内存中重新加载该整数，通常是从堆栈中的本地重新加载，如果用它做更多的事情的话。）x87对此很糟糕。

是的，那真是太慢了，例如在2006年，如果您仍然有32位CPU或使用x86-64 CPU运行32位代码，那么@Kirjain答案中的链接就被编写了。

不直接支持使用截断或默认（最接近）以外的舍入模式进行转换，直到SSE4.1 roundps/ roundpd最好的选择是魔术数技巧，例如@Kirjain的答案中的2006链接。

那里有一些不错的技巧，但仅适用于double-> 32位整数。double如果您有可能不值得扩展float。

或更常见的是，只需添加一个大数字以触发舍入，然后再次将其减去以返回原始范围。float无需扩展到即可解决此问题double，但是我不确定进行floor工作有多么容易。

无论如何，这里显而易见的解决方案是_mm256_floor_ps()and _mm256_cvtps_epi32（vroundpsand vcvtps2dq）。非AVX版本可以与SSE4.1一起使用。

我不确定我们是否可以做得更好。如果您有大量数组要处理（并且无法将这项工作与其他工作进行交错处理），则可以将MXCSR舍入模式设置为“ towards -Inf”（floor），然后简单地使用vcvtps2dq（使用当前的舍入模式） 。然后放回去。但是最好是缓存阻止转换或在生成数据时立即进行转换，这大概是来自其他需要将FP舍入模式设置为默认的Nearest的FP计算中。

roundps/ pd / ss / sd在Intel CPU上为2 uops，但在AMD Ryzen上仅为1 uop（每128位通道）。 cvtps2dq也是1 uop。打包的double-> int转换还包括一个改组。标量FP-> int转换（复制到整数寄存器）通常也为此花费额外的成本。

因此，在某些情况下，魔术数字技巧有可能获胜。也许值得研究_mm256_floor_ps()+ cvt是否是关键瓶颈的一部分（或更可能是如果您有double并想要int32）。

int foo = floorf(f)如果使用gcc -O3 -fno-trapping-math（或-ffast-math）编译带有-march=SSE4.1或AVX的东西，@CássioRenan 实际上会自动矢量化。 https://godbolt.org/z/ae_KPv

如果您将此代码与其他未经人工向量化的标量代码一起使用，则可能会很有用。特别是如果您希望编译器将对整个过程进行自动向量化。

Answer 2

看看魔术数字。网页上提出的算法应该比简单的转换有效得多。我自己从未使用过它，但这是它们在站点上提供的性能比较（xs_ToInt和xs_CRoundToInt是建议的功能）：

Performing 10000000 times:
simple cast           2819 ms i.e. i = (long)f;
xs_ToInt              1242 ms i.e. i = xs_ToInt(f); //numerically same as above
bit-twiddle(full)     1093 ms i.e. i = BitConvertToInt(f); //rounding from Fluid
fistp                  676 ms i.e. i = FISTToInt(f); //Herf, et al x86 Assembly rounding 
bit-twiddle(limited)   623 ms i.e. i = FloatTo23Bits(f); //Herf, rounding only in the range (0...1]  
xs_CRoundToInt         609 ms i.e. i = xs_CRoundToInt(f); //rounding with "magic" numbers

此外，显然修改了xs_ToInt，从而提高了性能：

Performing 10000000 times:
simple cast convert   3186 ms i.e. fi = (f*65536);
fistp convert         3031 ms i.e. fi = FISTToInt(f*65536);
xs_ToFix               622 ms i.e. fi = xs_Fix<16>::ToFix(f);

简要说明“幻数”方法的工作原理：

“基本上，为了添加两个浮点数，您的处理器将这些数字的小数点“排列”起来，以便可以轻松地添加这些位。它通过“归一化”这些数字来实现，从而保留了最高有效位，即较小的数字“归一化”以匹配较大的数字。因此xs_CRoundToInt（）使用的“幻数”转换的原理是：我们添加了足够大的浮点数（一个大到足以有效位数仅到小数点为止，之后没有一个）到您要转换的小数点，这样：（a）处理器将数字归一化为整数等值，并且（b）将这两个数相加不会擦除整数您要转换的数字的有效位（即XX00 + 00YY = XXYY）。”

引用来自同一网页。