[알고리즘] 시간 성능 향상을 위한 코드 최적화 (C/C++)

register 변수 사용

변수를 선언할 때 앞에 register 라는 키워드를 붙이면 변수는 RAM 대신 CPU의 레지스터를 사용한다.

따라서 변수에 접근하는 속도가 다른 일반적인 변수보다 빨라진다.

단, 레지스터의 개수는 한정되기에 "register"를 붙인다고 해서 모두 적용되는 것은 아니다.

많이 접근하는 변수에 사용할수록 효율이 좋아지기에, 반복문에서 많이 사용한다.

register int i, j;
for(i=0; i<N; ++i){
    for(j=0; j<N; ++j){
        ...
    }
}

　

인라인(inline) 함수 활용

함수호출시간보다 내부 수행작업이 단순한 경우 더 빠르게 실행하기 위하여 

함수가 아닌 인라인 함수를 사용하는 것이 훨씬 효율적이다.

매크로 처럼 작용 하며, 함수가 호출되는 대신 함수 본체가 직접 치환 된다.

inline int square(int x) {
    return x * x;
}

#include <MATH.H>

double length(int x, int y){
    return sqrt(square(x) + square(y));
}

 

인라인 함수를 이용하는 목적

- 함수 호출을 위한 비용이 발생하지 않는다. 

  (코드를 직접 읽어들이기 때문.)

- 일반적으로 인자를 넘기는 방식은 변수를 복사하는 것이기에

  보다 적은 비용이 발생한다.

  만약 인자가 상수라면 컴파일러는 더욱 높은 수준의 최적화 할 수 있다.

 

비트 연산

비트 연산은 정말 빠릅니다. + / - 은 비트 연산보다 조금 느리고, × / ÷ 은 더 느리다.

그렇기에 곱셈/나눗셈을 비트 연산으로 바꾸면 더 빨라집니다.

 

① 2의 멱수(2, 4, 8, 16, 32…)으로 나눌 때에는 Shift 연산을 사용할 수 있다.

     ex) 32로 나누는 것 : x / 32 → x >> 5 (나눗셈 연산 자제하기)

 

② 홀수 / 짝수 판별 

    만일 어떤 정수가 홀수라면, 2진수로 나타냈을 때 맨 마지막 자리가 "1"

    ex) if ( x % 2 == 1) → if ( x & 1)

 

▶ 비트마스크 (Bitmask)  

비트마스크 (Bitmask)

 

나눗셈 피하기

int inc_second(int second) 
{
    return (++second) % 60; 
}

초 를 증가시켜주는 함수를 구현한다고 했을 때, 

초의 범위는 0 부터 59 이므로 1 증가시킨 뒤에 만일 60 을 넘었을 때를 대비하여

 

위와 같이 60 으로 나눈 나머지를 구하는 방식으로 처리할 수 있다.

하지만 나눗셈은 매우 느린 연산이라는 문제가 있습니다.

int inc_second(int second) {
  ++second;
  if (second >= 60) 
    return 0;
  return second;
}

if 문은 나눗셈 보다는 훨씬 빠르게 처리가 되기 때문에 

위와 같이 처리하는 것이 효율적이다.

 

때로는 분기문이 프로그램 속도를 저하시킬 수 있다.

왜냐하면 CPU는 명령어 실행 속도를 위해 "파이프라이닝" 이라는 작업을 수행한다.

(다음에 실행될 명령어를 이전 명령어 실행이 채 끝나기 전에 미리 실행시키는 것과 비슷)

 

문제는 분기문이 있을 경우 다음에 실행할 명령어가 무엇인지 모른다는 점입니다. 

위 경우 if (second >= 60) 결과에 따라 return 0; 혹은 return second; 수행된다.

그렇다면 CPU 가 second >= 60이 끝날 때 까지 기다릴까? No!

 

이전 결과를 참고사아 참 / 거짓을 예측하여 다음에 올 명령어를 실행한다.

이렇게 분기문을 예측하는 것을 분기 예측(branch prediction) 이라 하는데

예측이 맞았다면 기분좋게 쭉쭉 진행할 수 있었지만, 

예측이 틀렸더라면 여태까지 작업한 것을 모두 버리고 

원래 수행했어야 할 명령어를 다시 실행해야 한다.

 

이러한 과정에서 동작하는 Cycle(CPU 에서 한 가지 작업을 수행하는데 걸리는 시간 단위)과

나눗셈, 덧셈과 같은 연산에 사용하는 Cycle이 다르다.

 

따라서 분기 예측 정확도를 50% 이상으로 할 수 있다면 위와 같이 코드를 바꿨을 때 

효율적으로 최적화를 했다고 볼 수 있다.

 

Look up table (LUT) 활용

원론적으로 특정 데이터에서 다른 데이터로 변환할 때 사용되는 테이블

 

예를 들어 컴퓨터에서 3D처리를 할 때 많은 수의 sine이나 cosine 연산들이 들어간다.

이때 sin값 계산은 꽤 시간 걸리기에, 프로그램 실행 초기에 sin1° ~ sin 90° 까지

미리 계산해서 표로 만들어 버리면 다음 호출 시에는 표에서 값을 찾으면 된다.

 

Look up Table을 이용하면 좋은 점이 코드의 길이가 훨씬 짧아지는 것과 동시에

실제 프로그램의 크기도 줄어든다는 점이다.

char* Condition_String1(int condition) {
  switch (condition) {
    case 0:
      return "EQ";
    case 1:
      return "NE";
    case 2:
      return "CS";
    case 3:
      return "CC";
    case 4:
      return "";
    default:
      return 0;
  }
}

 

Look Up Table 활용 적용 예제

char* Condition_String2(int condition) {
  if ((unsigned)condition >= 5) {
    return 0;
  }
  char* table[] = {"EQ", "NE", "CS", "CC"};
  return table[condition];
}

　

인자 전달 시 포인터 활용

struct big {
    int arr[1000];
    int str[1000];
};

위과 같은 거대한 구조체에서 arr[3]값을 얻어 오는 함수를 만들 때

아래와 같이 호출한다면 구조체 변수의 모든 데이터 복사가 되야 하므로

메모리 공간 할당은 물론 시간적으로 비효율적이다.

void modify(struct big arg) {}

 

그렇기에 아래와 같이 인자의 주소만 건네주는 방식을 사용한다면

구조체 변수의 주소값을 얻어오기 때문에 단순히 4바이트의 주소값 복사만 일어나고 좋다.

void modify(struct big *arg) {}

단순히 arg->arr[3]과 같은 방식으로 손쉽게 읽을 수 있다.

C++이 발전하면서 현재는 포인터 말고도 참조 연산자(&)를 이용하는 추세이기도 하다.

 

Reference

- 비트마스크 (Bitmask)

- [알고리즘] 알고리즘 문제에서 시간 복잡도는 어떻게 하는걸까?

- [알고리즘] 코딩 테스트 문제 풀 때, 시간 복잡도 계산해보기

- [C/C++] time(), clock()으로 실행시간 측정

- 정렬 알고리즘 비교