C/C++ 최적화 기법

C를 배우는 이유

- 컴퓨터 내부의 원리를 더 쉽게 이해할 수 있습니다.

- C언어에서 파생되어 생겨난 언어를 배우는데 많은 도움이 됩니다.

- 엄청나게 많은 코드들이 C언어로 작성되어 있습니다.

따라서, 어느 정도 수준 이상에 도달하게 된다면 C언어를 결코 피하실 수 없을 것입니다.

\n 엔터:개행문자, \은 Escape character라고 합니다.
- 기수법?? : 수를 표현하는 방법 2/10/16진수등으로 표현하는 방법

 

워드(Word)라고 부르는 단위가 있습니다.

컴퓨터에서 연산을 담당하는 CPU에는 레지스터(register)라는 작은 메모리 공간이 있는데, 이곳에다가 값을 불러다 놓고 연산을 수행하게 됩니다. CPU에서 연산을 수행하기 위해 잠시 써놓는 부분을 레지스터라고 합니다. 레지스터의 크기는 컴퓨터 상에서 연산이 실행되는 최소 단위라고 볼 수 있고, 이 크기를 워드라고 부릅니다. 32bit – 4byte, 64bit – 8byte

전처리기 문에서만 사용가능 #define PrintVaruableName(var) print(#var “\n”);

#은 인자를 문자열로 바꾸어줍니다. #define AddName(x, y) x##y x에 있는 것과 y에 있는 것을 하나로 합쳐줍니다. 이런 매크로 함수의 괄호가 빠져 오류가 나는 경우 디버깅하기 매우 까다로워 제시한 것이 인라인(inline) 함수 함수의 경우 호출을 하게 되면 프로그램의 흐름이(인자전달, 리턴) 완전히 다른 곳으로 넘어가게 됩니다. 인라인 함수는 main에서 연산이 이루어짐, 단 매크로 함수와 차이점으로 인라인 함수는 전처리기가 무식하게 치환해 버리는 것이 아니고 컴파일러가 인라인 함수를 사용한 문장 내부에서 ‘우리가 보통 함수를 사용하는 것처럼 바꿔 줍니다. 직접 작업(치환) > max함수 호출, 리턴 – 비용비교 산술 연산 관련

 

부동 소수점 (float, double)은 되도록 사용하지 말자

부동 소수점은 그 수의 특정한 규격이 정해진 것이기 때문에 상당히 복잡하고 따라서 연산이 매우 느려 소수점 첫째나 둘째 자리 정도의 정밀도를 요구한다면 단순히 그 수에 x 10, x 100을 하여 다루는 것이 좋습니다.

 

나눗셈을 피하라 (1)

나눗셈은 매우매우 느린 연산이라는 것이다.

만약 60보다 커질 일이 없다는 것을 알고 있다면 %60연산보다 if 60일 때만 0을 리턴 해주면 됩니다.

- if문은 나눗셈 보다 훨씬 빠름 분기문(if)문은 프로그램 속도를 저하시킬 수 있습니다. Cpu는 파이프라이닝을 통해 실행 속도를 향상시키는데 다음에 실행될 명령어를 이전 명령어의 실행이 채 끝나기 전에 미리 실행시키는 것과 비슷하다고 보면 됩니다.

 

문제는 분기문이 있을 경우 다음에 실행할 명령어가 무엇인지 모른다는 점입니다. 그렇다면 CPU가 second >= 60이 끝날 때까지 기다릴까요? 아닙니다. 이전의 추세를 보아 대충 참일지 거짓일지 예측한 다음 다음에 올 명령어를 실행하게 됩니다. 분기 예측(branch prediction)이라 합니다. 예측이 틀렷더라면 여태까지 작업한 것을 모두 버리고 원래 수행했어야 할 명령어를 다시 실행해야 합니다. Intel Skylake CPU의 경우 해당 페널티가 20 cycle정도입니다. 정수 나눗셈 연산(DIV) 10 cycle, 덧셈 1 cycle 따라서 만약에 분기 예측 정확도를 50% 이상으로 할 수 만 있다면 위와 같이 코드를 바꿨을 때 효율적으로 최적화를 했다고 볼 수 있습니다.

 

나눗셈을 피하라(2)
2의 멱수(2,4,8,16,32…)으로 나눌 때에는 ‘쉬프트’연산을 사용하여 시간을 절약할 수 있습니다.
Ex) 32로 나누는 것 : i / 32, i >> 5


비트 연산 활용하기(1)
비트 연산( OR, AND, XOR 등등)은 컴퓨터에서 가장 빠르게 실행되는 연산들 입니다.

Struct HUMAN {
Int is_Alive;
Int is_Walking;
Int is_Running;
Int is_Jumping;
Int is_Sleeping;
Int is_Eating;
};
6가지 state를 나타내는데 192개의 비트나 소모하였습니다. Char로 바꿔도 결국 같은 얘기
굳이 하나의 정보를 한 개의 비트에 대응시켜서 사용할 수 도 있는데 이를 각각의 변수에 모두 대응 시켜서 사용한 것이 문제이지요.


#define ALIVE 0x1 // 2 진수로 1

#define WALKING 0x2 // 2 진수로 10

#define RUNNING 0x4 // 2 진수로 100

#define JUMPING 0x8 // 2 진수로 1000

#define SLEEPING 0x10 // 2 진수로 10000

#define EATING 0x20 // 2 진수로 100000
Int main() {
Int my_status = ALIVE | WALKING | EATING;
If (my_status & ALIVE) {
Printf(“I am ALIVE!! \n”);
}
If (my_status & WALKING) {
Printf(“I am ALIVE!! \n”);
}
If (my_status & RUNNING) {
Printf(“I am ALIVE!! \n”);
}
If (my_status & JUMPING) {
Printf(“I am ALIVE!! \n”);
}
If (my_status & SLEEPING) {
Printf(“I am ALIVE!! \n”);
}
If (my_status & EATING) {
Printf(“I am ALIVE!! \n”);
}}


비트 연산 tip

1. 어떠한 정수의 특정자리를 1로 만들고 싶다면 그 자리만 1이고 나머지는 0인 수와 OR하면 됩니다.
2. 어떠한 정수의 특정 자리가 1인지 검사하고 싶다면 그 자리만 1이고 나머지는 0인 수와 AND하면 됩니다.
   
   

비트 연산 활용하기 (2)
비트 연산을 가장 많이 활용하는 예로 또한 홀수/짝수 판별이 잇습니다.
If ( I % 2 == 1)
If ( I & 1) – 만일 어떤 정수가 홀수라면, 2진수로 나타냈을 때 맨 마지막 자리가 1이여야 합니다.




루프(loop) 관련
1부터 n까지 더하는 함수를 만들 때
For (I = 1; I <= n; i++) {
Sum += I;
} Sum = (n+1) * n/2;

• 끝낼 수 있을 때 끝내라 : break로 무의미한 루프 빠져 나오기
• 한번 돌 때 많이 해라 : 하나의 루프에서 같은 일을 2번 하는 것과, 하나의 루프에서 동일한 일을 한 번 하고 루프를 두번 돈다면 전자의 경우가 훨씬 효율적이다. 조건 비교에서 시간이 소모되게 때문에
  
  While (n != 0) { If (n & 1) one_bit++; n >>= 1; } 결과적으로 비트가 1인 것의 개수를 셉니다. 하지만 우리는 C언어에서 모든 정수 자료형의 크기가 8 비트의 배수 임을 알고 있습니다. Char 8비트, int 32비트 따라서 한비트씩 검사할 필요 없이 한꺼번에 묶어서 검사해도 상관이 없다는 말입니다. While (n != 0) { If (n&1) one_bit++; If (n&2) one_bit++; If (n&4) one_bit++; If (n&8) one_bit++; N >>= 4; } – 8bit은 너무 난잡하므로 4비트
  
  
• - 루프에서는 되도록 0과 비교하여라*
  For (i=0; i<10; i++) {
  Printf(“a”);
  } For (i=9; i!=0; i==) {
  Printf(“a”);
  } 0과 다른지 비교하는 명령어는 CPU에서 따로 만들어져 있기 때문에 더 빠르게 동작될 수 있습니다.

되도록 루프를 적게써라

루프문 자체에서 여러가지 비교를 수행하는데 시간이 들기 때문에 루프를 쓰지 않고 나타낼 수 있다면 그 방법을 선택하시기 바랍니다.

 

if 및 switch문 관련

Binary Breakdown – 1,2,3,4,5,6,7,8 -> 1,2/3,4 // 5,6/7,8 : worst 8회 비교 -> 3회 비교 - 순차적 비교에서는 switch 문을 사용해라 : 위와 같은 상황에서 단 한번의 비교만함

룩업 테이블(look up table, LUT)을 사용할 수 있으면 사용해라

원론적으로 특정 데이터에서 다른 데이터로 변환할 때 사용되는 테이블 예를 들어 컴퓨터에서 3D처리를 할 때 많은 수의 sine이나 cosine 연산들이 들어가게 됩니다. 이 때 sin값 계산은 꽤 오래 시간 걸리는 계산임, 프로그램 실행 초기에 sin1부터 sin90까지 미리 다 계산해 둔 뒤 표로 만들어 버리면 단순히 표에서 값을 찾으면 되니까 아주 편하겠지요. Char* table[] = {“EQ”, “NE”, “CS”, “CC”, “MI”, “PL”, “VS”, “VC”, “HI”, “LS”, “GE”, “LT”, “GT”, “LE”}; Return table[condition]; 위와 같이 룩업 테이블을 이용하면 좋은 점이 코드의 길이가 훨씬 짧아진다는 점이고 실제 프로그램의 크기도 줄어든다는 점에 있습니다.

함수 관련

함수를 호출할 때에는 시간이 걸린다.
함수를 10번 호출 하는 것 보다 한번 호출하고 10번 반복하는게 더 빠르게 작동합니다.

 

 

인라인(inline) 함수를 활용하자
함수호출시간보다 내부 수행작업이 단순한 경우 더 빠르게 실행하기 위하여 함수가 아닌 인라인 함수를 사용하는 것이 훨씬 효율적입니다.

 

 

인자를 전달할 때에는 포인터를 이용해라
Struct big {
Int arr[1000];
Int str[1000];
};
과 같은 거대한 구조체에서 arr[3]값을 얻어 오는 함수를 만들고 싶다면
Void modify(struct big arg) {}
이 함수를 호출하게 될경우 구조체 변수의 모든 데이터 복사가 되야 하므로 엄청난 시간이 걸리게 됩니다. 또한 메모리 공간 할당도 필요함
Void modify(struct big *arg) {}
이 함수는 구조체 변수의 주소값을 얻어오기 때문에 단순히 4바이트의 주소값 복사만 일어납니다.
단순히 arg->arr[3] 과 같은 방식으로 손쉽게 읽을 수 있다.

0과 비교하는 감소 루프문 연산이 일반적인 증가 루프문 연산보다 3%정도 느립니다.
나눗셈을 if문 한번으로 구별한 뒤 쉬프트 연산이나 뺄셈 몇번으로 간단하게 해결 할 수 있다면, 시간 최적화 면에서 당연히 하는 것이 좋죠.

파이프라이닝하는 프로세서에서 if문은 나눗셈을 훨씬 능가하는 파이프라인 리셋이라는 치명적 성능저하를 불러옵니다. 오히려 if문이 나눗셈으로 바꾸는 것이 좋습니다.

제어문 블록구조를 사용하지 않고 중구난방으로 jmp내지 goto를 하는 코드를 작성해대는 문화가 심각할 정도였습니다.

Signed/unsigned형 간의 연산이 혼재될 때에 나타나는 여러 가지 예측이 어려운 side effect 나와 있고, 구글 코드 가이드라인에서도 unsigned형을 사용하지 못하도록 하고 있음
Unsigned를 사용하여 예측하기 어려운 버그를 만드는 것보다 long long int(64비트 정수)처럼 표현범위가 넓은 자료형을 사용하는 것이 낫습니다.

단순한 정수형으로써 수치값을 나타내는 경우엔 64bit형을 써서라도 signed형을 쓰는 것이 맞지만, C/C++의 개발업무의 특성상 경우에 따라선 wrap around와 and mask를 통해 코드의 효율성을 높이는 활용법이 있기에 unsigned를 절대 쓰지 말라는 것은 스크립터에게나 어울리는 얘기

예를들어 char형 변수의 알파벳 대문자를 소문자로 변환할 때, signed char형으로써 판단하려면 최소/최대값을 검사하는 if문 2회가 필요합니다. 이 경우처럼 분기예측률이 낮은 중첩 if문은 현대의 프로세서 구조상 쥐약이죠. 하지만 unsigned형을 사용하면 뺄셈 한번에 분기예측률이 높은 if문 한번으로 간단하게 해결되어 성능을 크게 올립니다.

구글의 개발지침도 실제 의미는 특별한 이유가 없는 한 signed를 쓰라는 얘기지 절대 쓰지 말라는 얘긴 아닙니다.

goto문은 아주아주아주 나쁜것, goto문을 사용하게 되면(특히 자주 사용하게 되면) 프로그램의 온전한 흐름을 해치고 코드 가독성이 떨어지는 등 엄청난 문제점이 있기 때문에 사용하지 않는 것이 좋습니다.

 

 

 

 

참조 : https://modoocode.com/129