Fez*_*vez 25 c c++ optimization multiplication division
在我正在编写的软件中,我正在进行数百万乘法或除以2(或2的幂)的值.我真的希望这些值int能够访问bitshift运算符
int a = 1;
int b = a<<24
但是,我不能,而且我必须坚持双打.
我的问题是:由于存在双精度(符号,指数,尾数)的标准表示,是否有一种方法可以与指数一起使用以2的幂来获得快速乘法/除法？
我甚至可以假设位数将被修复(该软件将在总是具有64位长的双倍的机器上工作)
PS:是的,该算法主要只执行这些操作.这是瓶颈(它已经是多线程的).
编辑:或者我完全错了,聪明的编译器已经为我优化了一些东西？
临时结果(用Qt测量时间,矫枉过正,但我不在乎):
#include <QtCore/QCoreApplication>
#include <QtCore/QElapsedTimer>
#include <QtCore/QDebug>
#include <iostream>
#include <math.h>
using namespace std;
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
while(true)
{
QElapsedTimer timer;
timer.start();
int n=100000000;
volatile double d=12.4;
volatile double D;
for(unsigned int i=0; i<n; ++i)
{
//D = d*32; // 200 ms
//D = d*(1<<5); // 200 ms
D = ldexp (d,5); // 6000 ms
}
qDebug() << "The operation took" << timer.elapsed() << "milliseconds";
}
return a.exec();
}
运行建议D = d*(1<<5);并D = d*32;在同一时间运行(200 ms),而D = ldexp (d,5);速度要慢得多(6000 ms).我知道这是一个微型基准测试,突然之间,我的内存已经爆炸,因为我每次运行时都会突然要求我在后面计算Pi ldexp(),所以这个基准测试没什么价值.但我会保留它.
另一方面,我遇到了麻烦,reinterpret_cast<uint64_t *>因为存在const违规行为(似乎volatile关键字会干扰)
Mys*_*ial 19
这是特定于应用程序的高级特性之一.它可能在某些情况下有所帮助,而在其他情 (在绝大多数情况下,直接乘法仍然是最好的.)
执行此操作的"直观"方法是将位提取为64位整数,并将移位值直接添加到指数中.(只要你没有点击NAN或INF,这将有效)
所以像这样:
union{
uint64 i;
double f;
};
f = 123.;
i += 0x0010000000000000ull;
// Check for zero. And if it matters, denormals as well.
请注意,此代码不以任何方式符合C标准,并且仅用于说明该想法.任何实现此操作的尝试都应该直接在汇编或SSE内在函数中完成.
但是,在大多数情况下,将数据从FP单元移动到整数单元(和返回)的开销将比直接进行乘法花费更多.对于SSE之前的时代尤其如此,需要将值从x87 FPU存储到存储器中,然后读回整数寄存器.
在SSE时代,整数SSE和FP SSE使用相同的ISA寄存器(尽管它们仍然具有单独的寄存器文件).根据Agner Fog,在整数SSE和FP SSE执行单元之间移动数据会有1到2个周期的惩罚.所以成本比x87时代好得多,但它仍然存在.
总而言之,它取决于你在管道上还有什么.但在大多数情况下,乘法仍然会更快.我之前遇到过这个完全相同的问题所以我从第一手经验开始说话.
现在使用仅支持FP指令的256位AVX指令,更不用说像这样的技巧了.
你可以非常安全地假设IEEE 754格式化,其中的细节可以得到相当的gnarley(特别是当你进入subnormals时).但是,在常见情况下,这应该有效:
const int DOUBLE_EXP_SHIFT = 52;
const unsigned long long DOUBLE_MANT_MASK = (1ull << DOUBLE_EXP_SHIFT) - 1ull;
const unsigned long long DOUBLE_EXP_MASK = ((1ull << 63) - 1) & ~DOUBLE_MANT_MASK;
void unsafe_shl(double* d, int shift) {
unsigned long long* i = (unsigned long long*)d;
if ((*i & DOUBLE_EXP_MASK) && ((*i & DOUBLE_EXP_MASK) != DOUBLE_EXP_MASK)) {
*i += (unsigned long long)shift << DOUBLE_EXP_SHIFT;
} else if (*i) {
*d *= (1 << shift);
}
}
编辑:做了一些时间后,这个方法比我的编译器和机器上的double方法慢得多,甚至剥离到最小执行代码:
double ds[0x1000];
for (int i = 0; i != 0x1000; i++)
ds[i] = 1.2;
clock_t t = clock();
for (int j = 0; j != 1000000; j++)
for (int i = 0; i != 0x1000; i++)
#if DOUBLE_SHIFT
ds[i] *= 1 << 4;
#else
((unsigned int*)&ds[i])[1] += 4 << 20;
#endif
clock_t e = clock();
printf("%g\n", (float)(e - t) / CLOCKS_PER_SEC);
在DOUBLE_SHIFT中,在1.6秒内完成,内部循环为
movupd xmm0,xmmword ptr [ecx]
lea ecx,[ecx+10h]
mulpd xmm0,xmm1
movupd xmmword ptr [ecx-10h],xmm0
与2.4秒相反,内部循环为:
add dword ptr [ecx],400000h
lea ecx, [ecx+8]
真意外!
编辑2:神秘解决了!VC11的一个变化是它现在总是向量化浮点循环,有效地强制/拱形:SSE2,尽管VC10,甚至/ arch:SSE2仍然更糟,3.0秒内循环:
movsd xmm1,mmword ptr [esp+eax*8+38h]
mulsd xmm1,xmm0
movsd mmword ptr [esp+eax*8+38h],xmm1
inc eax
没有/arch的VC10 :SSE2(甚至带/ arch:SSE)是5.3秒...... 具有1/100的迭代次数!,内循环:
fld qword ptr [esp+eax*8+38h]
inc eax
fmul st,st(1)
fstp qword ptr [esp+eax*8+30h]
我知道x87 FP堆栈很糟糕,但是500倍更糟糕有点荒谬.您可能不会看到这些类型的加速转换,即矩阵操作转换为SSE或int hacks,因为这是加载到FP堆栈,执行一个操作并从中存储的最坏情况,但它是为什么x87的一个很好的示例是不是要做任何事情的方法.有关.
任何半合适的编译器都会在您的平台上生成最佳代码.
但是正如@Clinton所指出的那样,简单地以"明显"的方式写它也应该做得很好.乘以和除以2的幂是现代编译器的儿童游戏.
除了不可移植之外,直接修改浮点表示几乎肯定不会更快(并且可能更慢).
当然,除非你的分析工具告诉你,否则你不应该浪费时间思考这个问题.但听取这个建议的人永远不会需要它,而那些需要它的人永远不会听.
[更新]
好的,所以我只是尝试使用g ++ 4.5.2进行ldexp.在cmath头内联它作为一个电话__builtin_ldexp,这反过来又...
...发出对libm ldexp函数的调用.我原本以为这个内置版本很容易进行优化,但我想GCC开发人员从未接触过它.
因此,1 << p正如您所发现的那样,乘以可能是您最好的选择.
最快的方法可能是：
x *= (1 << p);
可以通过调用机器指令添加p到指数中来简单地完成这种事情。告诉编译器取而代之的是使用掩码提取一些位并对其手动执行操作，这可能会使操作变慢，而不是更快。
请记住，C / C ++不是汇编语言。使用位移位运算符不一定要编译为位移位汇编操作，使用乘法不一定要编译为乘法。发生了各种奇怪而奇妙的事情，例如正在使用哪些寄存器以及可以同时运行哪些指令，这些我还不够聪明，无法理解。但是，您的编译器由于拥有多年的知识和经验，并且拥有大量的计算能力，因此在做出这些判断方面要好得多。
ps请记住，如果您的双精度数位于数组或其他平面数据结构中，则您的编译器可能非常聪明，并且可以同时使用SSE进行多个2倍甚至4个双精度运算。但是，进行很多移位可能会使编译器感到困惑，并阻止这种优化。