如何加速浮点到整数的转换?[复制品]

这里的大多数其他答案只是试图消除循环开销。

只有 deft_code's answer 找到了真正的问题——在x86处理器上,将浮点转换为整数的代价是惊人的昂贵。deft代码的解决方案是正确的,尽管他没有给出引用或解释。

这是技巧的来源,有一些解释,还有一些特定于您是要向上取整、向下取整还是向零取整的版本: Know your FPU

很抱歉提供了一个链接,但实际上,这里写的任何东西,除了复制那篇优秀的文章之外,都不能让事情变得清楚。

inline int float2int( double d )
{
   union Cast
   {
      double d;
      long l;
    };
   volatile Cast c;
   c.d = d + 6755399441055744.0;
   return c.l;
}

// this is the same thing but it's
// not always optimizer safe
inline int float2int( double d )
{
   d += 6755399441055744.0;
   return reinterpret_cast<int&>(d);
}

for(int i = 0; i < HUGE_NUMBER; i++)
     int_array[i] = float2int(float_array[i]);

双参数不是错误的!有一种方法可以直接使用浮点数来实现这个技巧,但是如果试图覆盖所有的角盒,就会变得很难看。在其当前形式中,如果要截断,此函数将对最接近的整数进行浮点取整,请使用6755399441055743.5(小于0.5)。

I ran some tests 关于进行浮点到int转换的不同方法。简单的答案是假设您的客户有支持SSE2的CPU,并设置/arch:SSE2编译器标志。这将允许编译器使用SSE 标量 指令的速度甚至是幻数技术的两倍。

否则,如果要研磨长串浮球,请使用SSE2打包的操作系统。

SSE3指令集中有一个fistp指令,它可以满足您的需要,但至于它是否可以被使用,并产生比libc更快的结果,我不知道。

时间是否足够长,以至于超过了启动几个线程的成本?

假设您的设备上有一个多核处理器或多个处理器可以利用,那么这将是一个跨越多个线程并行化的简单任务。

关键是要避免_ftol()函数,因为它速度不必要。对于这样的长数据列表,最好的选择是使用SSE2指令cvtps2dq将两个打包的浮点转换为两个打包的int64s。这样做两次(在两个SSE寄存器中获得四个int64s),然后将它们混在一起获得四个int32s(丢失每个转换结果的前32位)。您不需要程序集来执行此操作;MSVC将编译器内部函数公开给相关的指令-- _mm_cvtpd_epi32() 如果我的记忆正确的话。

如果您这样做,非常重要的一点是您的float和int数组是16字节对齐的,以便SSE2加载/存储内部函数能够以最大效率工作。另外,我向您推荐一些软件管道和流程 十六 在每个循环中一次浮动,例如(假设这里的“函数”实际上是对编译器内部函数的调用):

for(int i = 0; i < HUGE_NUMBER; i+=16)
{
//int_array[i] = float_array[i];
   __m128 a = sse_load4(float_array+i+0);
   __m128 b = sse_load4(float_array+i+4);
   __m128 c = sse_load4(float_array+i+8);
   __m128 d = sse_load4(float_array+i+12);
   a = sse_convert4(a);
   b = sse_convert4(b);
   c = sse_convert4(c);
   d = sse_convert4(d);
   sse_write4(int_array+i+0, a);
   sse_write4(int_array+i+4, b);
   sse_write4(int_array+i+8, c);
   sse_write4(int_array+i+12, d);
}

这样做的原因是SSE指令具有很长的延迟,因此,如果您使用依赖于xmm0的操作立即将负载加载到xmm0中,那么您将遇到停顿。同时有多个寄存器“正在运行”会稍微隐藏延迟。(理论上,一个无所不知的神奇编译器可以用它的方式来解决这个问题,但实际上它没有。)

如果此SSE JUJU失败,您可以向MSVC提供/qifst选项,这将导致它发出单个操作码。 拳头 这意味着它将只使用CPU中设置的舍入模式,而不确保它是ANSI C的特定截断操作。Microsoft文档say/qifst已被弃用,因为它们的浮点代码现在很快,但反汇编程序将向您显示这是不合理的乐观。even/fp:fast只会导致调用ftol-sse2,虽然比excegious-ftol快,但仍然是一个函数调用,后面跟着一个潜在的sse-op,因此速度不必要地慢。

我假设你是在x86架构上,顺便说一句——如果你是在PPC上,有等价的vmx操作,或者你可以使用上面提到的幻数乘技巧,然后是一个vsel(屏蔽非尾数位)和一个对齐的存储。

您可以使用一些神奇的汇编代码将所有整数加载到处理器的SSE模块中,然后执行等效代码将值设置为int,然后将其作为浮点进行读取。不过,我不确定这会更快。我不是SSE专家,所以我不知道怎么做。也许有人可以插话。

在VisualC++ 2008中,编译器自己生成SSE2调用,如果您使用MAXOUT OUT优化选项进行发布构建,并查看一个反汇编(尽管必须满足某些条件,然后与您的代码一起运行)。

有关加快整数转换的信息,请参阅以下英特尔文章:

http://software.intel.com/en-us/articles/latency-of-floating-point-to-integer-conversions/

根据微软的说法,/qifst编译器选项在VS2005中被弃用,因为整数转换已经加快。他们忽略了如何加快速度,但查看反汇编列表可能会提供线索。

http://msdn.microsoft.com/en-us/library/z8dh4h17(vs.80).aspx

大多数C编译器为每个浮点到int转换生成对ftol或其他内容的调用。如果您理解并接受此开关的其他效果,那么使用减少的浮点一致性开关(如fp:fast)可能会有所帮助。除此之外,如果您确定并理解不同的舍入行为,请将该对象放入一个紧密的程序集或SSE内部循环。 对于类似示例的大型循环,您应该编写一个函数,该函数设置一次浮点控制字,然后只使用fistp指令进行大容量舍入,然后重置控制字-如果您对仅x86代码路径没问题,但至少不会更改舍入。 阅读FLD和FISTP FPU指令和FPU控制字。

您使用的编译器是什么?在微软最近的C/C++编译器中,有一种在C/C++ +Gt代码生成-GT;浮点模型下的选择,它具有快速、精确、严格的选择。我认为精确是默认的,在某种程度上通过模拟fp操作来工作。如果您使用的是MS编译器,这个选项是如何设置的?设置为“快速”有帮助吗?在任何情况下,拆卸都是什么样子的?

如上文所述,CPU可以转换 float<->int 在本质上是一条指令,它不会比这更快(缺少一个SIMD操作)。

另外请注意,现代CPU对单(32位)和双(64位)FP数字都使用相同的FP单元,因此,除非您试图保存存储大量浮点的内存,否则实际上没有理由支持 float 超过两倍。

On Intel 您的最佳选择是内联SSE2调用。

我对你的结果感到惊讶。您使用的编译器是什么?您是否一直在编译优化?您确认使用了吗 valgrind 而kcachegrind,这就是瓶颈所在?你用的是什么处理器?程序集代码是什么样子的?

转换本身应编译为单个指令。一个好的优化编译器应该展开循环,这样每个测试和分支就可以完成几个转换。如果没有,你可以 用手展开回路 :

for(int i = 0; i < HUGE_NUMBER-3; i += 4) {
     int_array[i]   = float_array[i];
     int_array[i+1] = float_array[i+1];
     int_array[i+2] = float_array[i+2];
     int_array[i+3] = float_array[i+3];
}
for(; i < HUGE_NUMBER; i++)
     int_array[i]   = float_array[i];

如果您的编译器真的很糟糕,您可能需要使用常见的子表达式来帮助它,例如,

int *ip = int_array+i;
float *fp = float_array+i;
ip[0] = fp[0];
ip[1] = fp[1];
ip[2] = fp[2];
ip[3] = fp[3];

一定要报告更多的信息!

如果您不太关心舍入语义,可以使用 lrint() 功能。这使得舍入更加自由,而且可以更快。

从技术上讲,它是一个C99函数,但是您的编译器可能在C++中公开它。一个好的编译器也会把它内联到一条指令中(现代的G++会)。

lrint documentation

仅舍入 绝妙的把戏,只有用6755399441055743.5(少0.5)来做舍入是行不通的。

6755399441055744=2^52+2^51溢出尾数末尾的小数,留下您希望在fpu寄存器的位51-0中使用的整数。

在IEEE 754中
6755399441055744.0=

符号指数尾数
0 100001100011 1000000000000000000000000000000000000000000000000000000000

6755399441055743.5 但也将编译为 010000110001100000000000000000000000000000000000000000000000000000000

0.5从末尾溢出(四舍五入),这就是为什么它首先起作用。

要进行截断,您必须在double中添加0.5,然后执行此操作 保护数字应注意四舍五入到这样做的正确结果。 另外,要注意64位GCC Linux,long相当恼人地表示64位整数。

如果您有非常大的数组(大于几MB——CPU缓存的大小),请给代码计时,看看吞吐量是多少。可能是内存总线饱和了,而不是FP单元。查找CPU的最大理论带宽,看看离它有多近。

如果您受到内存总线的限制,那么额外的线程只会使情况更糟。您需要更好的硬件(例如更快的内存、不同的CPU、不同的主板)。

您是对的:FPU是一个主要的瓶颈(并且使用XS CroundToInt技巧可以使内存总线非常接近饱和)。

下面是一些核心2(Q6600)处理器的测试结果。该机器的理论主存储器带宽为3.2 GB/s(L1和L2带宽要高得多)。代码是用Visual Studio 2008编译的。32位和64位以及/o2或/ox优化的结果类似。

WRITING ONLY...
  1866359 ticks with 33554432 array elements (33554432 touched).  Bandwidth: 1.91793 GB/s
  154749 ticks with 262144 array elements (33554432 touched).  Bandwidth: 23.1313 GB/s
  108816 ticks with 8192 array elements (33554432 touched).  Bandwidth: 32.8954 GB/s

USING CASTING...
  5236122 ticks with 33554432 array elements (33554432 touched).  Bandwidth: 0.683625 GB/s
  2014309 ticks with 262144 array elements (33554432 touched).  Bandwidth: 1.77706 GB/s
  1967345 ticks with 8192 array elements (33554432 touched).  Bandwidth: 1.81948 GB/s

USING xs_CRoundToInt...
  1490583 ticks with 33554432 array elements (33554432 touched).  Bandwidth: 2.40144 GB/s
  1079530 ticks with 262144 array elements (33554432 touched).  Bandwidth: 3.31584 GB/s
  1008407 ticks with 8192 array elements (33554432 touched).  Bandwidth: 3.5497 GB/s

(Windows)源代码:

// floatToIntTime.cpp : Defines the entry point for the console application.
//

#include <windows.h>
#include <iostream>

using namespace std;

double const _xs_doublemagic = double(6755399441055744.0);
inline int xs_CRoundToInt(double val, double dmr=_xs_doublemagic) { 
  val = val + dmr; 
  return ((int*)&val)[0]; 
} 

static size_t const N = 256*1024*1024/sizeof(double);
int    I[N];
double F[N];
static size_t const L1CACHE = 128*1024/sizeof(double);
static size_t const L2CACHE = 4*1024*1024/sizeof(double);

static size_t const Sz[]    = {N,     L2CACHE/2,     L1CACHE/2};
static size_t const NIter[] = {1, N/(L2CACHE/2), N/(L1CACHE/2)};

int main(int argc, char *argv[])
{
  __int64 freq;
  QueryPerformanceFrequency((LARGE_INTEGER*)&freq);

  cout << "WRITING ONLY..." << endl;
  for (int t=0; t<3; t++) {
    __int64 t0,t1;
    QueryPerformanceCounter((LARGE_INTEGER*)&t0);
    size_t const niter = NIter[t];
    size_t const sz    = Sz[t];
    for (size_t i=0; i<niter; i++) {
      for (size_t n=0; n<sz; n++) {
        I[n] = 13;
      }
    }
    QueryPerformanceCounter((LARGE_INTEGER*)&t1);
    double bandwidth = 8*niter*sz / (((double)(t1-t0))/freq) / 1024/1024/1024;
    cout << "  " << (t1-t0) << " ticks with " << sz 
         << " array elements (" << niter*sz << " touched).  " 
         << "Bandwidth: " << bandwidth << " GB/s" << endl;
  }

  cout << "USING CASTING..." << endl;
  for (int t=0; t<3; t++) {
    __int64 t0,t1;
    QueryPerformanceCounter((LARGE_INTEGER*)&t0);
    size_t const niter = NIter[t];
    size_t const sz    = Sz[t];
    for (size_t i=0; i<niter; i++) {
      for (size_t n=0; n<sz; n++) {
        I[n] = (int)F[n];
      }
    }
    QueryPerformanceCounter((LARGE_INTEGER*)&t1);
    double bandwidth = 8*niter*sz / (((double)(t1-t0))/freq) / 1024/1024/1024;
    cout << "  " << (t1-t0) << " ticks with " << sz 
         << " array elements (" << niter*sz << " touched).  " 
         << "Bandwidth: " << bandwidth << " GB/s" << endl;
  }

  cout << "USING xs_CRoundToInt..." << endl;
  for (int t=0; t<3; t++) {
    __int64 t0,t1;
    QueryPerformanceCounter((LARGE_INTEGER*)&t0);
    size_t const niter = NIter[t];
    size_t const sz    = Sz[t];
    for (size_t i=0; i<niter; i++) {
      for (size_t n=0; n<sz; n++) {
        I[n] = xs_CRoundToInt(F[n]);
      }
    }
    QueryPerformanceCounter((LARGE_INTEGER*)&t1);
    double bandwidth = 8*niter*sz / (((double)(t1-t0))/freq) / 1024/1024/1024;
    cout << "  " << (t1-t0) << " ticks with " << sz 
         << " array elements (" << niter*sz << " touched).  " 
         << "Bandwidth: " << bandwidth << " GB/s" << endl;
  }

  return 0;
}