📝 상세 정리 # 지금까지는 대상 머신의 기능들을 활용하지 않고, 프로시져의 오버헤드 줄이기, 최적화 방해요소 없애기 등에 초점을 두었다. 성능을 더욱 극대화하기 위해 프로세서의 명령어 단에서의 기반 설계까지 활용해서 최적화해보자. 현대 프로세서는 프로그램 성능을 극대화 하기 위해 복잡한 하드웨어를 이용하는데, 이때문에 생각보다 실제 작동 방식이 기계어랑은 조금 다를 수 있다. 코드 수준에서는 명령어가 하나씩 순차적으로 수행하는걸로 보이지만 실제로는 여러 명령어가 동시에 평가되고 있으니까! 앞에서 파이프라이닝 해봤으니 잘 알지 현재 프로그램의 최대 성능을 특징짓는 두가지 하한선이 있는데 지연시간 한계 한 연산의 결과가 다음 연산이 시작되기 전에 필요할 때. 연산이 순서대로 발생해야 하는 경우 처리량 한계 프로세스의 기능 유닛이 가진 원시적인 컴퓨팅 능력 5.7.1 Overall Operation # ❔질문 사항 # 🔗 참고 자료 #

📝 상세 정리 # CSAPP 5.5 Reducing Procedure Calls 에서 최적화한 코드를 어셈블리로 보면 다음과 같다. 1 . L17: loop: 2 vmovsd (%rbx), %xmm0 Read product from dest 3 vmulsd (%rdx), %xmm0, %xmm0 Multiply product by data[i] 4 vmovsd %xmm0, (%rbx) Store product at dest 5 addq $8, %rdx Increment data+i 6 cmpq %rax, %rdx Compare to data+length 7 jne .L17 If !=, goto loop 문제점이 조금 보인다. dest는 %rbx에 저장되어있고, 반복문 인덱스 i는 %rdx에, 루프 종료는 %rax의 값이랑 비교하면서 감지한다. dest, 즉 %rbx를 계속해서 읽고쓰고 하고있다!! 그럴 필요가 없는데. 1 /* Accumulate result in local variable */ 2 void combine4(vec_ptr v, data_t *dest) 3 { 4 long i; 5 long length = vec_length(v); 6 data_t *data = get_vec_start(v); 7 data_t acc = IDENT; 8 9 for (i = 0; i < length; i++) { 10 acc = acc OP data[i]; 11 } 12 *dest = acc; 13 } 그 파트를 위와 같이 수정해보자. data_t acc가 생긴게 차이점이다. 메모리를 다시 읽지 않고, 레지스터 하나에서 고정해서 계산할 수 있게 되었으므로 훨씬 빨라진다! 이는 컴파일러 최적화로 왜 자동으로 잡히지 않았을까? *dest가 v의 원소엿다고 생각해보자. 이런 alias가 발생했다면, 마음대로 바꾸는것만으로는 배열이 훼손되면서 값이 달라지게 된다!! 따라서 컴파일러는 그런 오류를 방지하기 위해 최적화하지 못하고, 느리게 작동한다. ❔질문 사항 # 🔗 참고 자료 #

📝 상세 정리 # 앞서 살펴본 바와 같이 프로시져 호출은 오버헤드를 발생시키고, 프로그램 최적화를 발생할 수 있다. 8 for (i = 0; i < length; i++) { 9 data_t val; 10 get_vec_element(v, i, &val); 11 *dest = *dest OP val; 12 } 이런 부분에서, get_vec_element가 매 루프 반복마다 호출되고, 이 안에서 i가 유효한 인덱스인지 매번 검사하는데, 이 또한 비효율적이다. 1 data_t *get_vec_start(vec_ptr v) 2 { 3 return v->data; 4 } 1 /* Direct access to vector data */ 2 void combine3(vec_ptr v, data_t *dest) 3 { 4 long i; 5 long length = vec_length(v); 6 data_t *data = get_vec_start(v); 7 8 *dest = IDENT; 9 for (i = 0; i < length; i++) { 10 *dest = *dest OP data[i]; 11 } 12 } 위와 같이 바꾸면 함수를 호출하는 대신 배열에 직접 접근하고, 더 빨라질 것을 기대할 수 있다. 하지만 실제로 테스트해보면 명백한 성능 향상을 일어나지 않고, 정수 ADD는 오히려 성능이 저하되었다. 5.11.2에서 왜 위의 함수가 성능향상이 발생하지 않는지 확인할 수 있다. 아직은 이 변환이 궁극적으로 성능향상을 위한 단계중 하나로 작용할 수는 있다는 것 까지만 알아두자. ❔질문 사항 # 🔗 참고 자료 #

📝 상세 정리 # 함수의 다음 부분을 최적화 해보자. 7 for (i = 0; i < vec_length(v); i++) { 8 data_t val; 9 get_vec_element(v, i, &val); 10 *dest = *dest OP val; 11 } vec_length(v)를 매 반복마다 호출해서 비교하게된다. 이를 위에서 변수로 저장하고, 그 변수랑만 비교하면 해당 함수로 인한 반복되는 계산을 줄일 수 있다. 이 최적화를 code motion 이라고 한다. 최적화 컴파일러는 이 code motion을 수행하려고 시도하지만, 앞에서 배운것과 같이 어떤 예외사항이 발생할지 모르기때문에 꽤나 신중하다. 프로그래머가 명시적으로 수행하는게 좋을 수도 있다. 극단적인 예시로, 다음을 보자. 1 /* Convert string to lowercase: slow */ 2 void lower1(char *s) 3 { 4 long i; 5 6 for (i = 0; i < strlen(s); i++) 7 if (s[i] >= `A' && s[i] <= `Z') 8 s[i] -= (`A' - `a'); 9 } 10 11 /* Convert string to lowercase: faster */ 12 void lower2(char *s) 13 { 14 long i; 15 long len = strlen(s); 16 17 for (i = 0; i < len; i++) 18 if (s[i] >= `A' && s[i] <= `Z') 19 s[i] -= (`A' - `a'); 20 } 21 22 /* Sample implementation of library function strlen */ 23 /* Compute length of string */ 24 size_t strlen(const char *s) 25 { 26 long length = 0; 27 while (*s != `\0') { 28 s++; 29 length++; 30 } 31 return length; 32 } strlen함수의 시간복잡도가 $O(N)$이라서, $O(N^2)$가 될 정도로 차이가 존재한다. 하지만 이는 컴파일러가 인식하기 어려운 상황이고, 따라서 프로그래머가 직접 변환을 수행해주어야 한다. ❔질문 사항 # 🔗 참고 자료 #

📝 상세 정리 # 앞으로는 벡터 자료구조를 기반으로 예제를 생각할 것이다. 벡터는 헤더와 데이터 배열이라는 두개의 메모리 블록으로 표현된다. 1 /* Create abstract data type for vector */ 2 typedef struct { 3 long len; 4 data_t *data; 5 } vec_rec, *vec_ptr; data_t, OP등을 조절해서 최적화 없이 그대로 어셈블리로 옮긴 경우와 -O1을 적용한 경우를 비교하면, int / float 여부, + / * 여부에따라 조금 다르지만 아무튼 최적화가 일어난다. 따라서 일반적으로 어떤 수준의 최적화를 활성화하는 습관을 들이는 것이 좋다. ❔질문 사항 # 🔗 참고 자료 #

📝 상세 정리 # 프로그램 성능 개선을 표현하기 위해 CPE(cycles per element)라는 지표를 도입하겠다. 이는 반복 프로그램의 루프 성능을 설명하기 좋다. 이미지 픽셀 처리, 행렬 곱셈과 같이 반복연산을 하는 프로그램에 적합하다. 앞에서 배웠듯 프로세서에 의한 활동의 순서는 클럭에 의해서 제어되고, 클럭의 각 사이클마다 파이프라인이 하나 진행된다. 간단한 누적합을 계산하는 코드에서, 한 사이클/반복 당 한개의 항을 계산하는 대신 두개씩 계산하면 반복 횟수를 줄일 수 있다. 이를 루프 언롤링이라고 한다. ❔질문 사항 # 🔗 참고 자료 #

📝 상세 정리 # 현대 컴파일러는 프로그램에서 어떤 값이 계산되고 어떻게 사용되는지를 결정하기 위해 정교한 알고리즘을 사용한다. 식 단순화, 계산결과 재활용, 계산 횟수 감소 등을 지원한다. 대부분의 컴파일러는 -Og, -O1, -O2…처럼 최적화 레벨도 지정할 수 있다. 여기서는 일단 -O1로 컴파일도니 코드를 위주로 고려하겠다. 컴파일러는 프로그램에 대해 안전하지 않은 최적화를 적용해서는 안된다. 다음과 같은 함수가 있다고 생각해보자. 1 void twiddlel(long *xp, long *yp) 2 { 3 *xp += *yp; 4 *xp += *yp; 5 } 6 7 void twiddle2(long *xp, long *yp) 8 { 9 *xp += 2* *yp; 10 } 첫번째 함수는 메모리 참조 6번, 두번째 함수는 3번이니 알아서 최적화하지 않을까? 싶다. 하지만 xp와 yp가 같다면, 그렇게 하면 결과가 달라지게 된다! 이렇게 두 포인터가 동일한 메모리 위치를 가리킬 수 있는 경우를 메모리 별칭(memory aliasing) 이라고 한다. 안전한 최적화만 수행하는 컴파일러는 서로 다른 포인터가 겹칠 수 있다 (alias 될 수 있다)고 가정해야 한다. ❔질문 사항 # 🔗 참고 자료 #