Geekly Articles each Day

コードの最適化：CPU

すべてのプログラムが正しい必要がありますが、一部のプログラムは高速でなければなりません。 プログラムがビデオフレームまたはネットワークパケットをリアルタイムで処理する場合、パフォーマンスが重要な要素です。 効率的なアルゴリズムとデータ構造を使用するだけでは不十分です。 コンパイラーが簡単に最適化し、高速実行可能コードに変換するコードを作成する必要があります。

画像

この記事では、プログラムのパフォーマンスを何度も向上させることができる基本的なコード最適化手法について説明します。 また、プロセッサデバイスについても触れます。 効果的なプログラムを作成するには、プロセッサの動作を理解する必要があります。

Computer Systems：A Programmer's Perspectiveの5番目の章は、この記事を書くきっかけになりました。 すべてのプログラムは、 Pentium 2117Uプロセッサを搭載したマシンでテストされています。マシンのパフォーマンスは異なる場合があります。 このシリーズの別の記事「コードの最適化：メモリ」では、キャッシュ使用率を改善するための最適化手法について説明します。

最適化ブロッカー


コンパイラ自体は、コードを最適化しようとします。 -Ogパラメーターを指定してGCCを起動すると、基本的な最適化レベルが実行され、-O1パラメーターが最初の最適化レベルになります。 -O2、-O3など、より高いレベルの最適化があります。最適化のレベルが高いほど、コンパイラはプログラムをより過激にします。 コンパイラは安全な最適化のみを使用できます。 これは、コンパイラがすべての入力データの動作を変更しないように、プログラムを変更できるだけであることを意味します。

プログラマとして、コンパイラが最適化を実行できないコードの特性があることを理解する必要があります。 それらを最適化ブロッカーと呼びます。 2種類の最適化ブロッカーを検討してください。 それらの1つはポインターです。 コンパイラは、2つのポインタが同じメモリ領域を指すかどうかを確実に知ることができないため、いくつかの最適化を実行しません。 例を考えてみましょう：

void twiddle1(long *xp, long *yp) {
    *xp += *yp;
    *xp += *yp;
}

void twiddle2(long *xp, long *yp) {
    *xp += 2*(*yp);
}

twiddle2 , ( *xp, *yp, *xp), , twiddle1 ( ). , . , xp yp . twiddle1 *xp , twiddle2 — . . .

— . , , . :

long f();

long func1() {
    return f() + f() + f() + f();
}

long func2() {
    return 4*f();
}

f , — . , . f , , :

long counter = 0;

long f() {
    return counter++;
}

func1 func2 . , . , .


. , . CPE (cycles per element). , CPE 2.5, 2.5 .

, . vec float. combine0 . . 5000 .

typedef struct {
    long len;
    float *data;
} vec;

long vec_len(vec *v) {
    return v->len;
}

void combine0(vec *v, float *dest)
{
    long i;
    *dest = 1;
    for (i = 0; i < vec_len(v); i++) {
        *dest *= v->data[i];
    }
}

#define SIZE 5000
float a[SIZE];
vec v = {SIZE, a};

int main() {
    float res;
    for (i = 0; i < SIZE; i++)  //    
        a[i] = rand();

    combine0(&v, &res);
}

GCC -Og ( ). , CPE 11.05.

CPE rdtsc, . . , . . , .

#include <time.h>
#include <stdio.h>

//        
static __inline__ unsigned long long rdtsc(void)
{
    unsigned hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}

//  ,   
#define SIZE 100000000

int main(void)
{
    double time1 = clock() / (double)CLOCKS_PER_SEC;
    long cycles1 = rdtsc();
    //----------    ----------
    for (int i = 0; i < SIZE; i++) {
        i * i;
    }
    //----------------------
    double time2 = clock() / (double)CLOCKS_PER_SEC;
    long cycles2 = rdtsc();

    long cycles = cycles2 - cycles1;      //    
    double cpe = cycles / (double)SIZE;   //       
    double cpu_time = time2 - time1;      //   

    printf("CPU TIME: %.2f sec\n", cpu_time);
    printf("CPE:      %.2f\n", cpe);
}




, . . vec_len, . , . . .

void combine1(vec *v, float *dest)
{
    long i, len = vec_len(v);
    *dest = 1;
    for (i = 0; i < len; i++) {
        *dest *= v->data[i];
    }
}

— CPE 11.05. , . GCC -Og . : combine0 — CPE 12.7, combine1 — CPE 11.1.

. , , . - , . , :

void lower(char *s) {
    for (long i = 0; i < strlen(s); i++)
        if (s[i] >= 'A' && s[i] <= 'Z')
            s[i] -= ('A' - 'a'); 
}

strlen , . . , . , strlen , . , , . .


. . , . , , - .

. , dest, dest. . dest . -, , dest. - , .

void combine2(vec *v, float *dest)
{
    long i, len = vec_len(v);
    float acc = 1;
    for (i = 0; i < len; i++) {
        acc *= v->data[i];
    }
    *dest = acc;
}

. CPE 11.05 CPE 5.02. , , dest - . . , . .


CPE 5.02. , 5 . , .

int. , float, int, CPE 1.0? . CPE 1.58. ?

, , , , , : , , . , . , «» .

, , . «» , . , , . , :

void combine_plus(vec *v, int *dest)
{
    long i, limit = vec_len(v)-1;
    int acc = 0;
    for (i = 0; i < limit; i+=2) {
        acc = acc + v->data[i] + v->data[i+1];
    }
    if (i < len) acc += v->data[i];  //   ,    
    *dest = acc;
}

. , , . CPE 1.58 1.15. , CPE 1.03, , .

CPE 5.02, , , . , , , , . CPE 1.04 . , , .


. , , . , , , . , , , , . , . .

, , . : , , , . . , . , .

, 100 . , . , . , .

. ( , if-else), , . , , , . . 20 .


, , . , N , 5*N . , .

, - . . , . : , , . . . , . . , , N ( N ) N .

. , . , , . . , , . , 3-30 .


, CPE 5.02, CPE 1.02? . . , , , , , . . , . . , , , .

-. . , , . , . , . .

, . , . , , . , .

, . , . .

float combine3(float a[], long size)
{
    long i, limit = size-1;
    float acc0 = 1;
    float acc1 = 1;

    for (i = 0; i < limit; i+=2) {
        acc0 *= a[i];
        acc1 *= a[i+1];
    }
    while (i < size) acc0 *= a[i++];
    return acc0 * acc1;
}

, , , . CPE 5.02 2.5. :

float combine4(float a[], long size)
{
    long i, limit = size-3;;
    float acc0 = 1;
    float acc1 = 1;
    float acc2 = 1;
    float acc3 = 1;

    for (i = 0; i < limit; i+=4) {
        acc0 *= a[i];
        acc1 *= a[i+1];
        acc2 *= a[i+2];
        acc3 *= a[i+3];
    }
    while (i < size) acc0 *= a[i++];
    return acc0 * acc1 * acc2 * acc3;
}

CPE 1.28. CPE 1.04, , . .

, . Core i7 Haswell , CPE 0.5, . , C N , C*N.


, , , - . . GCC , . , . , , , , .

, , , . , . . float . , . , . , .

, .


. CPE 1.04, — . , SSE AVX, . , %ymm0-%ymm15, 16 32 . AVX 32 64- , 32- , . 32 , 32 .

, . GCC C, . , , , . , 4 8 , . , CPE 0.25 0.12.


, CPE 11.05. CPE 5.02. . , CPE 1.04. 11 . , 44-88 .

, , . , , , , . , , . CPE 5.02. CPE 1.04, , . . , 4-8 , .


, , . , . , . , , , CPE 2.0, . Core i7 Haswell , . , CPE 0.25. , — CPE 0.5.

. x86-64 16 16 YMM . , . , . 8 20, CPE 1.04 CPE 1.35.

, . , , . . .

:


, . - -, . .

for (long i = 0; i < limit; i+=3) {
        float x = a[i], y = a[i+1], z = a[i+2];
        acc = acc * x * y * z;
}

CPE 5.02. C, , . , , acc. , . -:

acc = acc * ((x * y) * z);

x, y z . , , . CPE 1.69.

:


, , . ( je, jg, jl . . ), . , . .

cmov. , - . , . . .

, , . . if-else, je, jg, jl . ., cmov. if-else:

if ()
    v = 1;
else
    v = 2;

, , , , . , :

v1 = 1;
v2 = 2;

v = () ? v1 : v2;

, - , cmov. , , , . , , , . , .

, , . , . .

void minmax1(int a[], int b[], int n)
{
    for (int i = 0; i < n; i++) {
        if (a[i] > b[i]) {
            int t = a[i];
            a[i] = b[i];
            b[i] = t;
        }
    }
}

void minmax2(int a[], int b[], int n)
{
    for (int i = 0; i < n; i++) {
        int min = a[i] < b[i] ? a[i] : b[i];
        int max = a[i] < b[i] ? b[i] : a[i];
        a[i] = min;
        b[i] = max;
    }
}

. , a , b . : , . min max , . , : minmax1 — CPE 15.6, minmax2 — CPE 1.18 ( 13.2 ).


. , . « » . : , , .

, . .

:

Source: https://habr.com/ru/post/J309796/

More articles:


All Articles