Float 및 Double의 빠른 곱셈/2 나누기(C/C++)

Float 및 Double의 빠른 곱셈/2 나누기(C/C++)

제가 쓰고 있는 소프트웨어에서, 저는 수백만 번의 곱셈이나 나눗셈을 제 가치의 2(또는 2의 거듭제곱)로 하고 있습니다.는 이 로 였으면 .int에 접근할 수 하기 .

int a = 1;
int b = a<<24

하지만 저는 할 수 없고 복식을 고수해야 합니다.

제 질문은: 복식(기호, 지수, 가수)의 표준 표현이 있는데 지수로 2의 거듭제곱으로 빠른 곱셈/분할을 얻을 수 있는 방법이 있습니까?

비트 수가 고정될 것이라고 가정할 수도 있습니다(소프트웨어는 항상 64비트 길이의 두 배가 되는 컴퓨터에서 작동합니다).

추신: 네, 알고리즘은 대부분 이러한 작업만 수행합니다.이것이 병목 현상입니다(이미 멀티스레드가 되어 있습니다).

편집 : 아니면 완전히 잘못 알고 영리한 컴파일러가 이미 나에게 최적화된 것입니까?

---

일시적인 결과(시간 측정을 위한 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;간(200ms)와에서 실행됩니다.D = ldexp (d,5);훨씬 느립니다( 6000ms).이것이 마이크로 벤치마크라는 것을 알고 있습니다. 그것은 Chrome이 실행할 때마다 갑자기 내 등에 Pi를 계산해 달라고 요청했기 때문에 갑자기 RAM이 폭발적으로 증가했습니다.ldexp()이 벤치마크는 도 없습니다,.그래도 간직할 거예요.

다른 한편으로는, 저는 그 일을 하는데 어려움을 겪고 있습니다.reinterpret_cast<uint64_t *>가 있기 때문에consts더)volatile키워드 간섭)

이것은 응용성이 높은 특정한 것들 중 하나입니다.어떤 경우에는 도움이 될 수도 있고 어떤 경우에는 도움이 되지 않을 수도 있습니다. (대부분의 경우에는 간단한 곱셈이 여전히 가장 좋습니다.)

이렇게 하는 "직관적인" 방법은 비트를 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 장치에서 정수 장치(및 뒤로)로 데이터를 이동하는 데 드는 오버헤드는 단순히 곱셈만 하는 것보다 훨씬 더 많은 비용이 듭니다.이것은 특히 x87 FPU에서 메모리로 값을 저장한 다음 정수 레지스터로 다시 읽어야 하는 SSE 이전 시대의 경우에 해당합니다.

SSE 시대에서 Integer SSE와 FPS SSE는 동일한 ISA 레지스터를 사용합니다(아직 별도의 레지스터 파일이 있음).Agner Fog에 따르면 Integer SSE와 FPS SSE 실행 유닛 간의 데이터 이동에는 1~2 사이클 페널티가 있습니다.따라서 x87 시대보다는 비용이 훨씬 낫지만, 여전히 그 자리에 있습니다.

대체적으로, 파이프라인에 있는 다른 것들에 따라 달라질 겁니다.하지만 대부분의 경우 곱셈은 여전히 더 빨라질 것입니다.저는 이전에 이와 똑같은 문제에 부딪힌 적이 있어서 직접 경험해 본 것입니다.

이제 FP 명령만 지원하는 256비트 AVX 명령을 사용하면 이와 같은 속임수를 사용할 유인은 더욱 줄어듭니다.

ldexp는 어떻습니까?

반쯤 괜찮은 컴파일러는 당신의 플랫폼에 최적의 코드를 생성할 것입니다.

그러나 @Clinton이 지적한 바와 같이 단순히 "명백한" 방법으로 작성하는 것만으로도 충분합니다.현대 컴파일러의 경우 2의 거듭제곱으로 곱하고 나누는 것이 아이들의 놀이입니다.

부동 소수점 표현을 직접 녹이는 것은 휴대용이 아닌 것 외에도 속도가 더 빠르지 않을 것이 거의 확실합니다.

그리고 물론 프로파일링 도구가 지시하지 않는 한 이 질문에 대해 생각하는 데 시간을 낭비해서는 안 됩니다.하지만 이 충고를 듣는 사람들은 절대로 필요하지 않을 것이고, 필요한 사람들은 절대 듣지 않을 것입니다.

[업데이트]

네, 그래서 그냥 g++ 4.5.2로 ldexp를 해봤는데요.cmath합니다에 합니다.__builtin_ldexp 도

가 발사됩니다.ldexp기능. 는 이 최적화하기에 것이라고 이지만, 것 .저는 이 내장이 최적화하기에 사소할 것이라고 생각했을 것이지만, GCC 개발자들은 그것에 접근하지 못했던 것 같습니다.

것.1 << p아마 당신이 알아낸 바와 같이 최선의 선택일 겁니다

IEEE 754 포맷을 안전하게 가정할 수 있으며, 이 포맷에 대한 세부 정보는 상당히 갸리하게 될 수 있습니다(특히 서브노멀 상태에 들어가면).그러나 일반적인 경우에는 다음과 같이 작동해야 합니다.

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 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);

DUBLE_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의 변경 사항 중 하나는 부동 소수점 루프를 항상 벡터화하여 /arch를 효과적으로 강제한다는 것입니다.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초입니다.100분의 1의 반복!!, 내부 루프:

fld         qword ptr [esp+eax*8+38h]  
inc         eax  
fmul        st,st(1)  
fstp        qword ptr [esp+eax*8+30h]

저는 x87 FP 스택이 대단하다는 것을 알고 있었지만, 500배나 더 나쁜 것은 좀 우스꽝스럽습니다.매트릭스 ops를 SSE 또는 int 핵으로 변환하는 것을 볼 수 없을 것입니다. 이것은 FP 스택에 로드하고, 하나의 op를 수행하고, 여기서 저장하는 최악의 경우이기 때문입니다. 하지만 x87이 왜 완벽한 것을 위한 방법이 아닌지에 대한 좋은 예입니다.관련된.

가장 빠른 방법은 다음과 같습니다.

x *= (1 << p);

이런 종류의 일은 단순히 기계 명령을 불러 추가함으로써 이루어질 수 있습니다.p기하급수적으로컴파일러에게 대신 마스크를 사용하여 일부 비트를 추출하라고 지시하고 수동으로 무언가를 수행하면 작업 속도가 빨라지지 않고 느려질 수 있습니다.

C/C++는 어셈블리어가 아닙니다.비트 시프트 연산자를 사용한다고 해서 반드시 비트 시프트 어셈블리 연산에 컴파일되는 것은 아니며, 곱셈을 사용한다고 해서 반드시 곱셈에 컴파일되는 것도 아닙니다.어떤 레지스터가 사용되고 있는지, 어떤 명령을 동시에 실행할 수 있는지 등 여러 가지 이상하고 멋진 일들이 벌어지고 있습니다. 저는 이해할 만큼 똑똑하지 않습니다.하지만 여러분의 컴파일러는 다년간의 지식과 경험과 많은 계산 능력을 가지고 있기 때문에 이러한 판단을 훨씬 더 잘합니다.

p.s. 만약 당신의 더블이 배열이나 다른 플랫 데이터 구조에 있다면, 당신의 컴파일러는 정말 똑똑할 수 있고 SSE를 여러 개의 더블에 동시에 사용하거나 심지어 4개의 더블에 사용할 수 있습니다.그러나 많은 비트 이동을 수행하면 컴파일러가 혼란스러워지고 최적화를 방해할 수 있습니다.

c++17부터는 16진수 부동 리터럴을 사용할 수도 있습니다.그렇게 하면 2의 높은 거듭제곱을 곱할 수 있습니다.예를 들어 다음과 같습니다.

d *= 0x1p64;

배가 될 것입니다d2^64만큼나는 그것을 나의 빠른 정수 연산을 두 배로 변환하는 데 사용합니다.

이 알고리즘이 요구하는 다른 작업은 무엇입니까?플로트를 int 쌍(사인/맨티사 및 크기)으로 분할하여 처리하고 마지막에 재구성할 수 있습니다.

를 곱하면 를 2를 값으로 할 수 x *= 2입니다에 합니다.x += x.

2로 나눈 값은 0.5로 곱하기로 대체할 수 있습니다.곱셈은 보통 나눗셈보다 훨씬 빠릅니다.

이중 유형의 플로트에 대해서는 2개의 힘을 처리하는 데 실질적인 이점이 거의/없지만 이중 유형의 경우에는 이에 대한 사례가 있습니다.이중 곱셈과 나눗셈은 일반적으로 복잡하지만 2의 거듭제곱으로 곱셈과 나눗셈에는 사소한 것입니다.

예를 들어 을 위해

typedef struct {double hi; double lo;} doubledouble;
doubledouble x;
x.hi*=2, x.lo*=2; //multiply x by 2
x.hi/=2, x.lo/=2; //divide x by 2

는 에 .<<그리고.>>위해서doubledouble정수와 비슷하도록 말입니다.

//x is a doubledouble type
x << 2 // multiply x by four;
x >> 3 // divide x by eight.

곱셈에 따라 충분히 반복되는 데이터가 있는 경우 룩업 테이블을 사용하면 메모리 비용으로 더 나은 성능을 제공할 수 있습니다.

언급URL : https://stackoverflow.com/questions/7720668/fast-multiplication-division-by-2-for-floats-and-doubles-c-c