코드 튜닝을 위한 규칙 <생각하는 프로그래밍>

 

생각하는 프로그래밍 존 벤틀리 저/윤성준,조상민 공역

프로그램의 성능 향상을 위해 코드 튜닝이 필요하지만 상황에 맞게 적용되어야 한다. 만약 성능 향상은 미비한데 코드의 가독성을 떨어뜨려 코드를 이해하기 어렵게 만드는 경우라면 코드 튜닝을 지양해야 한다.

 

코드 튜닝을 위한 규칙

1. 시간 단축을 위한 공간 규칙

2. 공간 절약을 위한 시간 규칙

3. 루프 규칙

4. 논리 규칙

5. 프로시저 규칙

6. 수식 규칙

 

1. 시간 단축을 위한 공간 규칙

Data Structure Augmentation

빈번한 연산을 하는 데 필요한 시간은 종종 부가적 정보로 데이터 구조를 늘리거나 또는 데이터 구조 내의 정보를 변경하여 더 쉽게 접근할 수 있도록 함으로써 감소시킬 수 있다.

Store Precomputed Results

비용이 많이 드는 함수값을 다시 계산하는 비용은 함수를 한 번만 계산하고 그 결과를 저장하는 방법으로 감소시킬 수 있다. 그 이후에 함수가 호출될 때는 다시 계산하기보다는 테이블을 검색하여 처리한다.

Caching

빈번하게 접근하는 데이터는 그 접근 비용이 가장 적어야 한다.

Lazy Evaluation

어떤 아이템이 실제로 필요하기 전까지는 평가를 하지 않음으로써 아이템에 대한 불필요한 평가를 피한다.

 

2. 공간 절약을 위한 시간 규칙

Packing

촘촘한 데이터 구조를 사용하면 데이터를 저장하고 검색하는 데 필요한 시간은 늘어나지만 메모리 비용을 줄일 수 있다.

Interpreters

어떤 프로그램을 표현하기 위한 메모리는 많이 발생하는 일련의 오퍼레이션을 간결하게 표현하는 인터프리터를 사용하여 감소시킬 수 있는 경우가 종종 있다.

 

3. 루프 규칙

Code Motion Out of Loops

어떤 계산을 루프가 반복될 때마다 실행하는 것보다는 루프 밖에서 한 번만 실행하는 것이 낫다.

Combining Tests

효율적인 내부 루프는 가능한 적은 테스트를 포함하고 있어야 하며, 단지 하나의 테스트만을 포함하고 있는 것이 바람직하다. 따라서 프로그래머는 루프의 몇 가지 종료 조건을 다른 종료 조건을 이용하여 시뮬레이트해 봐야 한다.

Loop Unrolling

루프를 펼치는 것은 루프 인덱스 값을 변경해야 하는 비용을 제거하고, 또한 파이프라인 지연을 피하도록 도와주며, 분기를 감소시키고, 명령어 수준의 병렬처리를 증가시킨다.

Transfer-Driven Loop Unrolling

만약 내부 루프에서 많은 비용이 단순한 대입문에 소모된다면, 이런 대입문은 코드를 반복하고 변수의 사용을 변경하여 제거할 수 있다.

Unconditional Branch Removal

빠른 루프에는 무조건적 분기를 포함하면 안 된다. 루프의 마지막 부분에 있는 무조건적 분기는 루프를 회전시켜 루프의 마지막에 조건적 분기를 갖도록하여 제거할 수 있다.

Loop Fusion

근처에 있는 두 루프가 같은 요소의 집합에 대해 동작하고 있다면, 동작 부분을 묶어 하나의 루프에서 처리하도록 한다.

 

4. 논리 규칙

Exploit Algebraic Identities

만약 논리식을 평가하는 데 비용이 많이 든다면, 평가하는 데 비용이 덜 드는 대수적으로 동치인 논리식으로 대체한다.

Short-Circuiting Monotone Functions

만약 여러 변수에 대한 어떤 단조 증가 함수가 특정 한계를 초과하는지 검사하려 할때, 특정 한계를 한 번 넘은 다음에는 다른 변수에 대해서 평가를 할 필요가 없다.

Reordering Tests

논리식은 비용이 적게 들고 결과가 참인 경우가 많은 식이 비용이 많이 들고 결과가 참인 경우가 거의 없는 식보다 앞에 와야 한다.

Precompute Logical Functions

작고 유한한 도메인에 대한 논리 함수는 그 도메인을 나타내는 테이블에 대한 검색으로 대체할 수 있다.

Boolean Variable Elimination

Boolean 변수 v에 대한 대입식을 v가 참일 때와 거짓일 때를 처리하는 if-else문으로 바꾸어 프로그램에서 boolean 변수를 제거할 수 있다.

 

5. 프로시저 규칙

Collapsing Function Hierarchies

함수가 다른 함수를 호출하는 구조로 되어 있는 경우 호출되는 함수를 인라인화하고 넘겨지는 변수를 묶어서 함수를 재작성하면 종종 실행시간을 단축할 수 있다.

Exploit Common Cases

함수는 모든 경우를 정확히 처리하고 비번한 경우에 대해서는 효율적으로 처리해야 한다.

Coroutines

다중 패스 알고리즘은 종종 협동루틴(coroutines)을 사용하여 단일 패스 알고리즘으로 바꿀 수 있다.

Transforamtions on Recursive Functions

재귀함수는 종종 다음과 같이 변환하여 실행시간을 줄일 수 있다.
- 명시적인 프로그램 스택을 사용하여 재귀를 반복으로 변환한다.
- 만약 함수의 마지막 부분에서 자신을 재귀적으로 호출하면, 그 부분을 함수의 첫 번째 부분으로 분기하도록 바꿀 수 있는데, 이것을 Removing Tail Recursion이라고도 한다.
- 작은 부분문제를 풀 때는 재귀를 반복하여 크기가 0 또는 1에 대한 문제를 풀게 하는 것보다는 보조 프로시저를 사용하는 편이 더 효율적일 수 있다.

Parallelism

하드웨어가 병렬처리를 지원하는 경우, 프로그램은 가능한 많이 병렬처리를 사용할 수 있는 구조로 작성되어야 한다.

 

6. 수식 규칙

Compile-Time Initialzation

가능한 많은 변수가 프로그램이 실행되기 전에 초기화되어 있어야 한다.

Exploit Algebraic Identities

만약 평가하는 데 비용이 많이 드는 수식이 있다면, 평가하는 데 비용이 적게 들면서 대수적으로 동치인 수식으로 바꾼다.

Common Subexpression Elimination

만약 포함된 변수가 변하지 않은 채로 동일한 수식이 두 번 평가된다면, 첫 번째 평가 결과를 저장한 다음 두 번째로 수식을 평가하는 부분에서 사용하여 같은 수식을 두 번 평가하는 것을 피할 수 있다.

Pairing Computation

만약 비슷한 두 수식이 빈번하게 함께 평가된다면, 그 둘을 하나의 쌍으로 평가하는 새로운 프로시저를 만들어야 한다.

Exploit Word Parallelism

비용이 많이 드는 수식을 평가할 때는 컴퓨터 하부 구조가 제공하는 기본적인 데이터 경로의 폭을 최대로 사용하라.

 

- James Song