CSAPP(5) - Optimizing Program Performance

프로그램의 주 목적은 모든 조건에서 정확하게 동작하는 것이다. 또한 프로그래머는 깔끔하고 간결한 코드를 작성해야 한다. 반면에 성능 개선이 필요한 경우도 있다. 이번 장에서는 어떻게 프로그램을 최적화해서 빠르게 만들 수 있는지 알아본다.

프로그래머는 컴파일러가 효율적으로 최적화하도록 소스코드를 작성해야 한다.

1. Capabilities and Limitations of Optimizing Compilers

컴파일러가 대부분의 최적화를 도와주지만, 그럴 수 없는 경우도 있다. 때문에 코드 작성 시에 함수는 size effect가 없게(전역 상태를 참조하지 않게) 하는 게 좋겠다.

2. Expressing Program Performance

CPE(cycles per element) 방식으로 함수 성능을 측정한다.

3. Program Example

4. Eliminating Loop Inefficiencies

• code motion
  • 루프 순회 시 반복된 계산을 앞으로 빼는 것
    • 문자열 길이까지 순회하는 경우 등
  • 컴파일러가 최적화하지 못하는 경우도 있으니 프로그래밍해주자.

5. Reducing Procedure Calls

• 순회 할 때마다 함수 콜하는 것보다, 반복문 내에서는 가능하다면 함수 호출을 줄이자.
• 모듈화를 손상시킬 수는 있다.
• 책 내 예제에서는 성능 향상을 보이지 못했다. 뒷 장에서 설명해준다고 함.

6. Eliminating Unneeded Memory References

• 순회 할 때마다 포인터 역참조 등으로 메모리 데이터를 변경하는 것은 비효율적이다.
• 축적된 값을 지연 변수로 선언해서 메모리 접근을 줄이자.

7. Understanding Modern Processors

코드 레벨을 넘어 각 머신 레벨의 최적화를 하려면 프로세서 구조를 알아야 한다. 나중에 보기로…

8. Loop Unrolling

• 루프 언롤링이란 매 순회 시 계산하는 요소의 수를 증가시켜 전체 순회 개수를 줄이는 방법이다.
• 한 루프 당 계산하는 요소의 수를 k개로 정하는데, 2개 이상은 큰 최적화 효과가 없다.
• 2개로 하더라도 큰 최적화를 기대할 수는 없다.
  • 프로세서 수준에서는 전체를 순회하는 것과 큰 차이가 나지 않는다. 순차적으로 이전 작업 완료를 기다려야 함.

9. Enhancing Parallelism

9.1. Multiple Accumulators

• 결합 연산(reduce)이 결합법칙과 교환법칙을 만족한다면(덧셈, 곱셈), 전체 집합을 쪼개서 수행하고 병합할 수 있다.
• loop unrolling과 함께 수행 가능
  • k X k loop unrolling이라 함.
• 루프 언롤링과 함께 사용 시 성능 향상 된다.
  • 프로세서가 더 이상 이전 작업 수행 완료를 기다리지 않아도 됨. 지연시간 임계점을 넘을 수 있음.
• 컴파일러는 교환/결합법칙만 만족한다면 최적화할 수 있다.
  • 정수 가능, 부동소수점 불가능(2장에서 봄)

9.2. Reassociation Transformation

• 괄호의 위치를 바꾸는 것 만으로 순차적으로 실행되는 문제를 해결 가능
  • 재결합 변환
  • 프로세스 수준에서 축적되는 값을 루프 당 한번만 변경하기 때문(이전 loop unrolling 결과에서는 2번 변경)
  • 당연히 연관법칙이 성립되야 하므로 부동소수점에는 적용 불가능
• 다만 Multibple Accumulators 방식보다 큰 성능 개선은 안됨.

10. Summary of Results for Optimizing Combining Code

• 지금까지의 최적화는 10-20배 성능 향상되었다.
• 이러한 최적화는 C 컴파일러가 해준다.

11. Some Limiting Factors

실제 머신에서 성능 제한에 영향을 주는 다른 요소들

11.1. Register Spilling

• 루프 병렬화 수준은 사용 가능한 레지스터 수에 의해 제한됨.
  • 사용 가능한 레지스터 수를 초과하는 병렬화는 메모리 런타임 스택에 임시 값을 저장해야 한다.
• 모던 x86-64 프로세서는 16개의 정수, 16개의 부동소수점 저장 가능 레지스터를 가지고 있다.

11.2. Branch Prediction and Misprediction Penalties

• 모던 프로세서는 instruction pipelining 을 통해 실제 데이터가 어떻게 처리될지를 미리 예측하여 구성해둔다.
• 투기적 실행을 하는 프로세서에서는 예측한 브랜치를 수행한다.
  • 예측이 맞으면 결과를 커밋. 레지스터나 메모리에 값을 저장
  • 예측이 틀리면 롤백 후 다시 수행. 느리다.

12. Understanding Memory Performance

13. Life in the Real World: Performance Improvement Techniques

• 고수준 설계 : 적절한 자료구조와 알고리즘 선택하기
• 기본 코딩 원칙 : 컴파일러가 최적화를 수행할 수 있도록.
  • 과도한 함수 호출을 제거. 루프 밖으로 계산을 이동. 프로그램 모듈화 vs 성능 타협하기.
  • 불필요한 메모리 참조 제거. 중간 결과를 저장하는 임시 변수 활용. 최종 값이 계산되었을 때만 배열이나 전역변수에 결과 저장.
• 저수준 최적화
  • loop unrolling
  • 명령어 레벨의 병렬화를 증가시키기 위한 기술적인 방법 찾기. Multiple Accumulators, Reassociation Transformation
  • 조건부 연산을 함수형 스타일로 작성하기. 조건부 데이터 전송을 가능하게 한다.(명령형 스타일로 작성하면 조건부 제어 전송)

최적화를 한다고 에러를 발생시키는 실수를 하지 말자.

14. Identifying and Eliminating Performance Bottlenecks

프로파일러를 이용하면 함수 호출 시 소요 시간과 함수 호출이 몇 번 되었는지를 파악할 수 있고, 이를 활용하여 병목을 제거할 수 있다. 암달에 법칙에 의해서 가장 많은 시간을 소모하는 함수에 최적화를 집중해야 한다.

15. Summary

• 대부분의 최적화는 컴파일러가 수행하지만, 프로그래머는 컴파일러를 도울 수 있다.
• 어떤 컴파일러도 비효율적 알고리즘 혹은 자료구조를 대체할 수는 없다.
  • 프로그램 설계는 프로그래머의 주요 고려사항이다.

등등 요약

출처

• https://csapp.cs.cmu.edu/
• 책 “Computer Systems : A Programmer’s Perspective”