Chapter 26. Code-Tuning Techniques (코드 최적화 기법)

 

속도 향상 & 코드 크기 줄이기

 

성능 = 속도 + 크기

 

크기 줄이기 = 코드 최적화보다는 클래스와 데이터의 재설계를 통해 더 많이 이루어짐.

코드 최적화 = 대규모 설계 변경보다는 소규모 변경을 의미

 

이 장에서 다루는 변경은 "안티 리팩토링"

= 내부 구조를 개선하는 대신, 성능 향상을 위해 구조를 저하시킵니다. 구조가 저하되지 않는다면 이를 최적화라고 간주하지 않으며, 기본적으로 표준 코딩 관행으로 사용하는 것

 

---

26.1 Logic (논리)

 

Stop Testing When You Know the Answer

 

프로그래밍에서 논리 표현식을 최적화하는 중요한 방법 중 하나는 조건을 알게 되면 테스트를 멈추는 것

 

예를 들어, 배열에서 음수 값을 찾을 때, 음수 값을 발견하면 더 이상 배열을 계속 스캔하지 않고 즉시 루프를 종료하는 방식으로 성능을 최적화할 수 있음. 이와 같은 방식은 코드의 실행 속도를 개선하는 데 도움이 됨

 

negativeInputFound = false;
for ( i = 0; i < count; i++ ) {
    if ( input[ i ] < 0 ) {
        negativeInputFound = true;
    }
}

 

Order Tests by Frequency (테스트 순서 정렬)

 

논리 테스트에서 가장 빈번하고 빠른 조건을 먼저 실행하도록 코드를 정렬하는 것이 성능을 향상시킬 수 있음.

 

case 문이나 if-then-else 문에서 빈도가 높은 조건을 앞에 배치하면, 코드가 더 적은 테스트를 수행하게 되어 성능을 개선할 수 있음. 그러나 결과는 컴파일러와 언어 구현에 따라 달라질 수 있으므로, 최적화 방법을 적용하기 전에 테스트와 분석이 필요.

예시)

C#과 Java의 경우는 switch-case 문 구조로(이 언어들에서는 값이 범위로 나열되는 대신 개별적으로 나열됨) 인해 최적화가 안 될 때가 있음.

 

Compare Performance of Similar Logic Structures(유사한 논리 구조의 성능 비교)

 

유사한 논리 구조의 성능을 비교할 때, case 문과 if-then-else 문 사이의 성능 차이는 환경에 따라 달라질 수 있음. 동일한 문법을 사용하는 언어라도 성능 결과가 다를 수 있음.

=> 코드 최적화에서는 "경험법"이나 "논리"에 의존하기보다는, 실제 성능을 측정하는 것이 가장 중요합니다.

 

Substitute Table Lookups for Complicated Expressions(복잡한 표현식을 테이블 조회로 대체하기)

 

복잡한 논리 체인을 처리할 때, 테이블 조회 방식을 사용하면 성능이 개선될 수 있음. 특히 분류 후 작업을 수행하는 방식에서는 테이블을 사용해 논리를 단순화하고, 가독성 및 유지보수성을 높일 수 있음.

 

* 안 좋은 예시

//복잡한 논리 체인
if ( ( a && !c ) || ( a && b && c ) ) {
    category = 1;
}
else if ( ( b && !a ) || ( a && c && !b ) ) {
    category = 2;
}
else if ( c && !a && !b ) {
    category = 3;
}
else {
    category = 0;
}

 

* 좋은 예시 - 테이블 조회 적용

// 복잡한 논리 대신 테이블 조회 사용
// categoryTable 정의
static int categoryTable[ 2 ][ 2 ][ 2 ] = {
    // !b!c   !bc   b!c   bc
    0, 3, 2, 2,  // !a
    1, 2, 1, 1   // a
};
...
category = categoryTable[ a ][ b ][ c ];

 

테이블 정의가 읽기 어려울 수 있지만, 잘 문서화되어 있다면 복잡한 논리 체인 코드보다 읽기 어렵지 않으며, 정의가 변경되면 이전의 논리 체인보다 테이블을 유지보수하는 것이 훨씬 더 용이 함.

 

Use Lazy Evaluation(지연 평가)

지연 평가는 필요할 때까지 연산을 미루는 기법 => 불필요한 연산을 방지하고 성능을 최적화

JIT 방식과 유사하게, 연산을 수행해야 하는 순간이 오기 전까지 불필요한 작업을 하지 않음.

 

예시)

1. 5000개의 값을 미리 생성하는 대신, 프로그램이 해당 값을 사용할 때만 계산하여 성능을 최적화할 수 있음. 캐싱을 활용하면, 한 번 계산된 값을 재사용하여 추가적인 연산 비용을 줄일 수 있음.

2. 프로그래밍 언어의 Lazy Evaluation: Haskell은 기본적으로 지연 평가를 사용하여 성능을 최적화

3. 데이터베이스 쿼리 최적화: 필요할 때만 데이터를 불러오는 방식

4. UI 렌더링 최적화: 사용자에게 보이지 않는 UI 요소는 나중에 렌더링.

---

26.2 Loops

Unswitching (반전 스위칭) 

 

루프 내부에서 반복적으로 수행되는 조건문을 루프 외부로 이동하는 기법

=> 조건문의 값이 루프 실행 동안 변경되지 않는 경우에 적용할 수 있으며, 이를 통해 불필요한 분기(branch)를 제거하고 성능을 향상시킬 수 있음

 

적용 전 

for ( i = 0; i < count; i++ ) {
    if ( sumType == SUMTYPE_NET ) {
        netSum = netSum + amount[i];
    } else {
        grossSum = grossSum + amount[i];
    }
}

 

적용 후

if ( sumType == SUMTYPE_NET ) {
    for ( i = 0; i < count; i++ ) {
        netSum = netSum + amount[i];
    }
} else {
    for ( i = 0; i < count; i++ ) {
        grossSum = grossSum + amount[i];
    }
}

 

차이점

 

1. 불필요한 조건문 제거: if 조건을 루프 밖으로 이동하여, 루프 내부에서는 단순한 덧셈 연산만 수행하도록 개선됨.
2. 성능 향상: 루프가 클수록 불필요한 조건문 평가를 줄이는 효과가 커지며, 약 20%의 성능 향상이 가능.

 

Unswitching 적용 여부 판단 기준

 

1. 루프 내 조건문이 실행될 때마다 동일한 결과를 반환하는가?
2. 루프가 매우 긴 경우, 조건문 평가 비용이 성능에 영향을 미치는가?
3. 코드 유지보수성을 고려할 때, 중복 코드가 큰 부담이 되지 않는가?
4. 컴파일러가 자동으로 최적화를 수행하는지 확인했는가?

 

즉, Unswitching은 성능 최적화에 유용하지만, 유지보수성과 가독성을 고려해야 하는 트레이드오프가 있음.
무조건 적용하는 것이 아니라, 측정(benchmarking)과 테스트를 통해 성능 향상을 확인한 후 사용하는 것이 바람직 함.

 

Jamming (루프 병합, Loop Fusion)

Jamming(루프 병합) 또는 Fusion(융합)은 같은 범위에서 실행되는 두 개 이상의 루프를 하나로 결합하는 최적화 기법

=> 루프 오버헤드를 줄여 성능을 향상시키는 것이 목적

 

적용 전

For i = 0 To employeeCount - 1
    employeeName(i) = ""
Next

For i = 0 To employeeCount - 1
    employeeEarnings(i) = 0
Next

 

적용 후

For i = 0 To employeeCount - 1
    employeeName(i) = ""
    employeeEarnings(i) = 0
Next

 

차이점 

 

1. 루프 오버헤드 감소: For 루프를 하나로 줄여 반복문 실행 비용을 절반으로 감소
2. 캐시 효율성 증가: 여러 개의 데이터 배열을 동시에 처리하여 메모리 캐시를 보다 효율적으로 사용
3. 성능 향상: 특히 대량의 데이터를 처리할 때, 반복 횟수가 줄어들어 전체 실행 속도가 향상됨

 

Jamming 적용 여부 판단 기준

 

1. 두 루프가 같은 범위를 반복하는가?
2. 각 루프가 독립적인 연산을 수행하는가?
3. 루프를 병합해도 코드의 가독성이 유지되는가?
4. 벤치마킹 결과, 성능이 개선되는가?

 

주의점

 

1. 잘못된 병합은 코드 유지보수성을 떨어뜨리고, 오히려 성능을 저하시킬 수 있음

 

Loop Unrolling (루프 풀기, 전개, 전개 최적화)

루프의 반복 횟수를 줄여 루프 제어 오버헤드를 감소시키는 기법
=> 루프를 한 번에 여러 번 실행하도록 변경하면, 루프 횟수가 줄어들고 성능이 향상될 수 있음.

 

적용 전

i = 0;
while (i < count) {
    a[i] = i;
    i = i + 1;
}

 

적용 후

// 1단 적용
i = 0;
while (i < count - 1) {
    a[i] = i;
    a[i + 1] = i + 1;
    i = i + 2;
}
if (i == count - 1) { 
    a[count - 1] = count - 1; 
}

 

// 2단 적용
i = 0;
while (i < count - 2) {
    a[i] = i;
    a[i + 1] = i + 1;
    a[i + 2] = i + 2;
    i = i + 3;
}
if (i <= count - 1) { 
    a[count - 1] = count - 1; 
}
if (i == count - 2) { 
    a[count - 2] = count - 2; 
}

 

Loop Unrolling 적용 여부 판단 기준

 

1. 루프 내 연산이 단순한가?
2. 루프 반복 횟수가 크고 고정적인가?
3. 컴파일러가 자동으로 Unrolling을 적용하지 않는가?
4. 벤치마킹을 통해 성능 향상이 확인되는가?

 

주의점

 

1. 코드의 가독성과 유지보수성을 해칠 수 있으므로 신중하게 적용해야 함

2. 벤치마킹을 통해 실제 성능 향상을 확인하고 적용 여부를 결정하는 것이 중요

 

Minimizing the Work Inside Loops (루프 내 작업 최소화)

루프 내부의 작업을 최소화하면 코드의 성능을 향상시킬 수 있음.

특히, 반복적으로 수행되는 복잡한 연산을 루프 바깥으로 이동하면 CPU 연산 비용을 줄이고, 코드의 가독성을 개선할 수 있음.

 

적용 전

for ( i = 0; i < rateCount; i++ ) {
    netRate[i] = baseRate[i] * rates->discounts->factors->net;
}

 

적용 후

quantityDiscount = rates->discounts->factors->net; // 값을 한 번만 가져오기

for ( i = 0; i < rateCount; i++ ) {
    netRate[i] = baseRate[i] * quantityDiscount;
}

 

주의점

 

1. 컴파일러 최적화를 고려하더라도, 명확한 변수 활용이 성능 향상에 기여할 수 있음
2. 성능 최적화가 항상 필요한 것은 아니므로, 프로파일링 후 적용하는 것이 중요

 

Sentinel Values (보초 값)

루프에서 복합 조건 검사(compound test)를 최적화하는 기법 중 하나

=> 반복문의 조건 검사를 단순화하고, 실행 속도를 향상시킬 수 있음

 

적용 전

bool found = false;
int i = 0;

while ((!found) && (i < count)) { // 매번 두 가지 조건 검사
    if (item[i] == testValue) {
        found = true;
    } else {
        i++;
    }
}

if (found) {
    // testValue가 배열 안에 존재함
}

 

적용 후

// 기존 배열 마지막 값을 백업 (보초 값 추가 전)
int initialValue = item[count];

// 보초 값 추가 (배열 끝에 testValue 삽입)
item[count] = testValue;

int i = 0;
while (item[i] != testValue) { // 단일 조건만 검사
    i++;
}

// testValue가 원래 배열에 있었는지 확인
if (i < count) {
    // testValue가 존재함
} else {
    // testValue가 존재하지 않음
}

// 보초 값을 원래 값으로 복구
item[count] = initialValue;

 

Sentinel Value 기법을 적용할 수 있는 사례

 

1. 배열에서 특정 값 검색 (Linear Search)
2. 연결 리스트에서 특정 노드 탐색
3. 텍스트 처리 (문자열 끝을 Sentinel 값으로 활용 가능)

 

주의점

 

1. 보초 값을 배열 크기를 초과하지 않도록 설정해야 함
2. 원래 데이터를 보존하려면 Sentinel 삽입 전에 값을 백업해야 함
3. Sentinel 값이 실제 데이터와 겹치지 않도록 적절한 값 선택

 

=> 데이터 탐색 최적화가 필요하다면 Sentinel Value를 적극 활용

 

Putting the Busiest Loop on the Inside (가장 바쁜 루프를 안쪽에 배치하기)

자주 실행되는 루프(= 바쁜 루프)를 안쪽(inner)에 배치하면, 불필요한 반복을 줄여 성능을 향상시킬 수 있음.
바깥쪽(outer) 루프가 너무 자주 실행되면 초기화, 증가, 종료 조건 검사 비용이 커지므로 비효율적

 

적용 전

for (int column = 0; column < 100; column++) { // 바깥쪽 루프 (100번 실행)
    for (int row = 0; row < 5; row++) { // 안쪽 루프 (5번 실행)
        sum = sum + table[row][column];  
    }
}

 

적용 후

for (int row = 0; row < 5; row++) { // 바깥쪽 루프 (5번 실행)
    for (int column = 0; column < 100; column++) { // 안쪽 루프 (100번 실행)
        sum = sum + table[row][column];  
    }
}

 

루프 최적화 적용 대상

 

1. 배열 또는 행렬을 탐색하는 루프 최적화
2. 데이터 접근 패턴이 중요한 경우 (캐시 효율성 고려)
3. CPU 연산이 많은 경우 (루프 비용 절감 효과가 큼)

 

=> 중첩 루프를 작성할 때는 항상 "가장 바쁜 루프를 안쪽에 배치할 수 있는지" 고민할 것

Strength Reduction (강도 감소 최적화)

비싼 연산(예: 곱셈)을 더 저렴한 연산(예: 덧셈)으로 대체하면 성능이 향상될 수 있음.
 특히, 루프 내에서 반복적으로 곱셈을 수행하는 경우, 이를 누적 덧셈(accumulation)으로 변경하면 효율적.

 

적용 전

For i = 0 to saleCount - 1
    commission(i) = (i + 1) * revenue * baseCommission * discount
Next

 

적용 후

incrementalCommission = revenue * baseCommission * discount
cumulativeCommission = incrementalCommission

For i = 0 to saleCount - 1
    commission(i) = cumulativeCommission
    cumulativeCommission = cumulativeCommission + incrementalCommission
Next

 

Strength Reduction 적용 대상

 

1. 반복문 내에서 특정 값이 일정한 배율로 증가하는 경우
2. 배열 인덱스를 기반으로 수식을 계산하는 경우
3. 수치 연산이 반복적으로 수행되는 경우 (특히 곱셈이 포함될 때)

 

=> 루프 내에서 반복적인 곱셈이 있다면 Strength Reduction을 고려할 

 

---

26.3 Data Transformations (데이터 변환 최적화)

데이터 타입을 적절히 변환하면 프로그램 크기를 줄이고 실행 속도를 개선할 수 있음.
데이터 구조 설계는 광범위한 주제이지만, 데이터 타입의 작은 변경만으로도 성능 최적화가 가능

 

Use Integers Rather Than Floating-Point Numbers ( 부동소수점 대신 정수 사용하기)

Why?

1. 정수 연산(덧셈, 곱셈)은 부동소수점 연산보다 일반적으로 빠름.

2. 부동소수점 수는 처리하기가 더 복잡하고 시간이 많이 소요되므로 루프 인덱스나 산술 연산에서 정수를 사용하는 것이 더 효율적

 

 

Use the Fewest Array Dimensions Possible(배열의 차원 수 최소화하기)

가능하면 배열의 차원 수를 최소화하는 게 더 빠르게 처리할 수 있음.

 

 

=> 언어와 컴파일러에 따라 결과가 다를 수 있으므로 실제 환경에서 최적화 효과를 테스트하는 것이 중요.

 

Minimize Array References (배열 참조 최소화하기)

배열을 자주 참조하는 코드에서는 배열 참조를 최소화하는 것이 성능을 향상시킬 수 있음.

 

적용 전

for (discountType = 0; discountType < typeCount; discountType++) {
    for (discountLevel = 0; discountLevel < levelCount; discountLevel++) {
        rate[discountLevel] = rate[discountLevel] * discount[discountType];
    }
}

 

적용 후

for (discountType = 0; discountType < typeCount; discountType++) {
    thisDiscount = discount[discountType];  // 배열 참조를 밖으로 이동
    for (discountLevel = 0; discountLevel < levelCount; discountLevel++) {
        rate[discountLevel] = rate[discountLevel] * thisDiscount;
    }
}

 

 

1. 배열을 반복적으로 참조하는 경우, 해당 참조를 루프 밖으로 이동시키면 성능을 향상시킬 수 있음.

2. 배열 참조를 최소화하면 반복문 내에서 불필요한 작업을 줄이고, 전반적인 실행 시간을 단축할 수 있음.

 

 

Use Supplementary Indexes (보조 인덱스 사용하기)

 

String-Length Index (문자열 길이 인덱스)

 

문자열의 길이를 추적하는 방식

 

C언어의 경우 문자열의 길이를 구하기 위해 시작부터 0이 나타날 때까지 각 바이트를 세어야 함.

Visual Basic의 경우 문자열 앞에 길이를 나타내는 바이트가 숨겨져 있음. => 길이를 추적하는 보조 인덱스가 존재

이와 같이 보조 인덱스를 사용하는 것이 연산을 빠르게 만들 수 있음.

 

Independent, Parallel Index Structure (독립적이고 병렬적인 인덱스 구조)

 

데이터 항목이 크거나 이동하기 어려운 경우(디스크에 저장된 데이터 등), 인덱스 참조를 정렬하고 검색하는 것이 데이터를 직접 다루는 것보다 빠를 수 있음.

 

Use Caching (캐싱 사용하기)

캐싱은 복잡성을 추가하고 오류가 발생할 가능성이 높지만, 비용이 많이 드는 작업을 최적화할 수 있어 유용한 기법

 

시간이 많이 걸리는 계산을 캐시할 수도 있습니다. 특히 계산의 파라미터가 간단할 때 유효

=> 같은 값이 반복적으로 요청되는 경우, 이 값을 캐시하여 계산을 피할 수 있음.

 

적용하는 경우

 

1. 같은 정보가 자주 요청될 때

2. 새로운 요소를 생성하는 데 시간이 많이 걸릴 때

3. 캐시된 정보를 접근하는 비용이 저렴할 때

4. 하드웨어가 캐시를 지원할 때

 

 

---

26.4 Expressions (보유식)

Exploit Algebraic Identities (대수적 항등식 활용하기)

 

1. not a and not b

2. not (a or b)

 

2가 더 효율적 => not 연산 한 번만 수행

 

Use Strength Reduction (강도 감소 사용하기)

=> 비용이 큰 연산을 더 저렴한 연산으로 바꾸는 방법

 

1. 곱셈을 덧셈으로 교체

2. 지수 연산을 곱셈으로 교체

3. longlong 정수는 long 또는 int로 교체 (다만, 네이티브 길이와 비네이티브 길이 정수에 따른 성능 차이를 고려)

4. 정수 곱셈/나누기 2는 비트 이동 연산으로 교체

 

Be Wary of System Routines (시스템 루틴에 주의하기)

시스템 루틴은 종종 비용이 많이 들고, 그 정확도가 실제로 필요한 것보다 과도한 경우가 많음.

 

=> 시스템 수학 루틴은 우주비행사를 달에 ±2피트로 정확히 착륙시키기 위해 설계되어 있음.

일반적인 계산에 이 정도의 정확도는 필요 없음.

 

Use the Correct Type of Constants (적절한 타입의 상수 사용)

변수에 할당되는 상수와 리터럴은 동일한 타입이어야 함.

덜 발전된 컴파일러나 인터프리터는 런타임에서 타입 변환을 처리할 수 있기 때문에 성능에 부정적인 영향을 미칠 수 있기 때문

 

Precompute Results (결과 미리 계산하기)

자주 사용될 경우, 한 번 계산하고 그 값을 나중에 조회하는 방식이 더 효율적.

 

예시) 루프 내에서 표현식 일부를 계산하기보다는 루프 밖에서 미리 계산하는 경우

 

Eliminate Common Subexpressions (공통 부분식 제거하기)

공통 부분식 제거는 코드의 가독성을 높이는 동시에 성능을 개선할 수 있음.

but, 때로는 전체 성능에 미치는 영향이 미미할 수 있으므로, 성능 개선을 위해서는 다른 최적화 기법과 함께 사용하는 것이 중요

---

26.5 Routines (코드 최적화에서 중요한 도구)

Rewrite Routines Inline (코드 인라인으로 작성하기)

 

현대 시스템에서는 루틴 호출이 성능에 큰 영향을 미치지 않으므로, 루틴을 인라인으로 작성하는 것보다 일반적인 루틴 호출을 사용하는 것이 더 효율적일 수 있음.

루틴을 인라인으로 넣는 것이 성능을 향상시키는 경우는 매우 드물고, 오히려 코드의 가독성을 떨어뜨리고 유지보수를 어렵게 만들 수 있으니 주의

 

 

---

26.6 Recoding in a Low-Level Language (저수준 언어로 다시 작성하기)

 

특정 부분을 저수준 언어로 재작성하면 속도와 코드 크기를 모두 개선할 수 있음.

 

접근 방법

 

1. 고급 언어로 애플리케이션을 100% 작성합니다.

2. 애플리케이션을 완전히 테스트하고, 정확성을 확인합니다.

3. 애플리케이션을 프로파일링하여 성능에 큰 영향을 미치는 핫스팟을 찾습니다. 보통 프로그램의 5%가 50%의 실행 시간을 차지하므로 최적화할 부분을 쉽게 찾을 수 있습니다.

4. 성능 개선이 필요한 부분을 저수준 언어로 다시 작성하여 성능을 개선합니다.

 

어셈블리로 재작성한다고 해서 반드시 복잡하고 거대한 코드가 되는 것은 아닙니다. 이 예시처럼 어셈블리 코드는 고급 언어 코드보다 더 간결하고 효율적일 수 있음.

 

어셈블리 최적화를 위한 효과적인 전략

 

1. 컴파일러가 생성하는 어셈블리 리스트를 활용하여 최적화할 코드를 찾습니다.

2. 해당 어셈블리 코드를 별도의 파일로 추출하고, 성능을 개선하기 위해 수동으로 최적화합니다.

3. 각 최적화 단계에서 정확성을 체크하고, 성능 개선을 측정합니다.

4. 일부 컴파일러는 고급 언어의 주석을 어셈블리 코드에 포함하므로, 이를 문서화로 사용할 수 있습니다.

 

---

26.7 The More Things Change, the More They Stay the Same (변화는 있지만, 변하지 않는 것들)

 

컴퓨터가 너무 강력해져서, 많은 일반적인 프로그램에서는 이 장에서 논의한 성능 최적화 수준이 거의 중요하지 않게 됐음.

 

but, 하지만 성능 문제는 여전히 크게 변화하지 않음.

임베디드 시스템, 실시간 시스템 및 엄격한 속도나 공간 제한이 있는 시스템에서 소프트웨어를 작성하는 사람들은 여전히 이 장의 내용이 도움이 될 것임.

 

측정 가능한 개선을 요구하는 것이 불필요한 최적화를 피하는 좋은 방법임.

성능 최적화가 프로파일러를 사용해 성능 변화를 측정할 만큼 중요하다면, 가독성이나 유지보수성을 희생할 만큼 가치가 있음.

하지만 최적화가 그렇게 중요한지에 대해 프로파일링을 하지 않으면, 가독성이나 유지보수성에 미치는 부정적인 영향을 고려해야 함.

측정되지 않은 코드 최적화가 성능에 미치는 영향은 추측에 불과하고, 가독성에 미치는 영향은 확실하고 부정적이기 때문