C 언어의 경우 프로그램 성능 최적화 - 제5장 독서 노트

사실 대부분의 컴파일러 자체는 간단한 최적화를 제공할 수 있다. 예를 들어 gcc는 O2 또는 O3 옵션을 사용하여 프로그램을 최적화할 수 있다.그러나 컴파일러의 최적화도 시종 한계가 있다. 왜냐하면 최적화 과정이 프로그램의 기능에 변동이 없도록 조심스럽게 보장해야 하기 때문이다.그러므로 프로그래머 자체는 프로그램에 대해 최적화 의식을 가져야 한다.내가 보기에 이것도 반드시 있어야 할 좋은 프로그래밍 습관이다.
몇 가지 간단한 최적화 조치:
　　1.코드 이동
여러 번 (예를 들어 순환 중) 실행하지만 계산 결과가 바뀌지 않는 계산을 코드 앞에 여러 번 값을 구하지 않는 부분으로 이동합니다.극단적인 예를 들다.

/* convert string to lowercase: slow*/
void lower( char *s ){
    int i;
    for( i = 0;i < strlen(s);i++ )
        if( s[i] >= 'A' && s[i] <= 'Z' )
            s[i] -= ( 'A' - 'a');

}

C 언어의 문자열은null로 끝나기 때문에 함수strlen도null 문자를 만날 때까지 이 서열을 한 걸음 한 걸음 검사해야 합니다.만약 문자열 s가 매우 긴 문자열이라면 이 함수는 자연히 많은 불필요한 비용을 초래할 것이다!!그러므로 순환체내에서는 계산 결과가 변하지 않는 계산을 앞쪽으로 이동시켜 여러 번 반복되는 계산을 피해야 한다.
최적화 코드:

/* convert string to lowercase: faster*/
void lower( char *s ){
    int i;
    int len = strlen(s);
    for( i = 0;i < len;i++ )
        if( s[i] >= 'A' && s[i] <= 'Z' )
            s[i] -= ( 'A' - 'a');

}

 
　　2.불필요한 스토리지 참조 제거
C 언어에서 포인터 변수로 읽기와 쓰기는 CPU 레지스터로 간접적으로 주소를 찾아 메모리에서 읽기와 쓰기를 하고 함수 내부의 국부 변수를 사용하면 CPU의 일반 레지스터를 사용한다.메인 메모리 읽기와 쓰기는 CPU 내부의 일반 레지스터의 주소 찾기 속도와 수십 배의 차이가 난다.작은 예를 하나 들다

for( i = 0;i < len;i++ ){
    *dest = *dest + data[i];
}

이 순환체는 매번 메인 메모리에서 읽기와 쓰기를 하는데 다음과 같이 최적화된다.

int acc;
for( i = 0;i < len;i++ ){
    acc = acc + data[i];
}
*dest = acc;

이렇게 하면 그 바늘을 한 번만 쓸 수 있고 acc 변수는 cpu의 실행 과정에서 cpu 내부의 일반적인 레지스터를 사용하여 읽기와 쓰기를 하기 때문에 속도를 높일 수 있다.
　　3.순환 전개
순환 전개는 말 그대로 한 걸음 한 걸음의 교체 순환을 한 걸음 두 걸음 이상으로 전개하여 교체 횟수를 줄이는 것이다.순환 전개는 두 가지 측면에서 프로그램의 성능을 개선한다. 첫째, 프로그램 결과에 직접적으로 도움이 되지 않는 조작 수량, 예를 들어 순환 인덱스 계산과 조건 지점을 감소시킨다.그 다음으로 코드를 더욱 변화시키고 계산 중의 관건적인 경로의 조작 수량을 줄일 수 있는 방법을 제공했다.다음 두 함수를 비교해 보면 첫 번째는 일반 순환이고 두 번째는 순환 전개 함수이다.

//normal function to add all element of v
void combine1( vec_ptr v,data_t *dest ){
    int i = 0;
    long int length = vec_length( v );
　　 data_t *data = get_vec_start( v );
　　 data_t acc = IDENT;
for( i = 0;i < length;i++ ){
        acc = acc + data[i];
    }
    *dest = acc;
}

 

//unroll loop by 2
void combine2( vec_ptr v, data_t *dest ){
    int i;
    long int length = vec_length( v );
    loing int limit = length -1;
    data_t *data = get_vec_start( v );
    data_t acc = IDENT;
    
    for( i = 0;i < limit;i += 2 ){
        acc = ( acc + data[i] ) + data[i+1];
    }

    for( ;i < length;i++ ){
        acc = acc + data[i];
    }

    *dest = acc;
}

두 번째 함수는 순환을 전개하고, 마지막에 누락되지 않았는지 검사합니다.몇 가지 관건적인 절차를 줄여서 프로그램을 최적화시켰다.
　　4.병행성 향상
cpu에서 프로그램은 어셈블리 명령으로 번역되지만 하나의 명령이 순서대로 집행되는 것이 아니라 유수선이 동시에 집행되는 것이다. 즉, 여러 개의 상관없는 명령이 공동으로 집행되는 것이다.이것은 cpu의 기계 특성이다. 우리가 해야 할 일은 바로 이런 기계 특성을 많이 이용하는 것이다.
프로그램의combine2의 핵심 순환 내부 문장을 분석해 봅시다. acc=(acc+data[i])+data[i+1];이 순환에서 데이터 [i+1]의 계산은 (acc+데이터 [i]) 뒤에 두어야 한다. 왜냐하면 이것은 서로 관련되어 있기 때문에 프로그램의 병행 조작에 불리하기 때문에 다음과 같이 개선되었다.

//unroll loop by 2，2-way parallelism
void combine3( vec_ptr v, data_t *dest ){
    int i;
    long int length = vec_length( v );
    loing int limit = length -1;
    data_t *data = get_vec_start( v );
    data_t acc0 = IDENT;
    data_t acc1 = IDENT;
    
    for( i = 0;i < limit;i += 2 ){
        acc0 =  acc0 + data[i];
        acc1 = acc1 + data[i+1];
    }

    for( ;i < length;i++ ){
        acc0 = acc0 + data[i];
    }

    *dest = acc0 + acc1;
}

이 코드는 acc를 acc0과 acc1로 나누어 프로그램이 동시에 계산할 수 있도록 하고 마지막으로 두 그룹의 결과를 추가하여 프로그램 성능을 향상시킨다.
코드 최적화는 통상적으로 읽을 수 있는 감소를 가져올 수 있기 때문에 어떻게 취사선택을 해야 하는지를 잘 고려하고 필요할 때 주석을 많이 넣어야 할지도 모른다.