Optimized C++

 

 

5.5 최적화 패턴

최적화된 코드에는 반복되는 패턴이 있다. 개발자가 자료구조와 알고리즘을 연구하는 이유는 보통 여기에 성능 향상을 위한 아이디어가 담겨있기 때문이다. 유용한 성능 향상 기법을 알아보자.

 

사전 계산(precomputation)

프로그램 실행 초기나 링크 타임, 컴파일 타임, 디자인 타임에서 자주 사용하는 코드를 미리 계산해 최적화한다.

 

지연 계산(lazy evaluation)

계산 코드를 실제로 필요한 부분과 최대한 가까운 곳으로 미뤄 최적화한다.

 

배칭(batching)

한 번에 여러 항목을 계산해 최적화한다.

 

캐싱(caching)

계산 비용이 높은 코드의 결과를 저장한 뒤 재사용해 최적화한다.

 

특수화(specialization)

사용하지 않는 일반화된 코드를 제거해 최적화한다.

 

더 큰 조각 선택하기

입력 데이터를 한 번에 많이 가져와 반복 작업을 줄여서 최적화한다.

 

힌팅(hinting)

성능을 향상할 수 있는 힌트를 제공해 최적화한다.

 

예상 경로 최적화

발생할 가능성이 가장 낮은 입력이나 이벤트의 런타임부터 테스트해 최적화한다.

 

해싱(hashing)

가변 길이를 갖는 문자열처럼, 크기가 큰 자료구조를 해시로 계산합니다. 해시는 자료구조를 대신해 성능을 향상시킬 수 있다.

 

이중 검사(double-checking)

비용이 크지 않은 검사를 수행하되, 비용이 큰 검사는 필요한 경우에만 수행해 최적화한다.

 

5.5.1 사전 계산(Precomputation)

사전 계산은 자주 사용하는 코드를 미리 계산해 실행 횟수가 많은 부분의 계산량을 줄이는 일반적인 최적화 기법이다. 자주 사용하는 코드를 자주 사용하지 않는 코드나 링크 타임, 컴파일 타임, 디자인 타임에 옮기는 등 기법을 다양하게 변형할 수 있다. 보통은 일찍 계산할수록 좋다.

사전 계산은 계산할 값이 문맥에 종속되지 않는 선에서 할 수 있다. 코드가 프로그램에서 종속되는 부분이 하나도 없다면 컴파일러가 미리 계산할 수 있다.

int sec_per_day = 60 * 60 * 24;

5.5.2 지연 계산(Lazy Evaluation)

지연 계산의 목표는 계산 코드를 실제로 필요한 부분과 최대한 가까운 곳으로 미뤄서 계산하는 것이다. 몇 가지 장점이 있는데, 함수에서 모든 실행 경로(분기)에서 계산할 필요가 없다면 결과가 필요한 경로에서만 계산하도록 만들 수 있다. 지연 계산의 예는 다음과 같다.

 

2부 구성

인스턴스를 정적으로 생성하려고 할 때 객체를 생성하는데 필요한 정보가 존재하지 않을 때가 종종 있다. 이 때 생성자는 객체의 모든 정보를 한꺼번에 할당하지 않고 빈 객체를 생성하는데 필요한 최소한의 코드만 포함한다. 나중에 

 

COW

객체를 하나의 인스턴스에서 다른 인스턴스로 복사할 때, 동적 멤버 변수를 복사하는 대신 하나의 복사본을 공유한다. 두 인스턴스가 변수를 수정할 때까지 복사를 지연한다.

5.5.3 배칭

 

5.5.7 힌팅(Hinting)

힌팅은 힌트를 사용해 연산 비용과 계산량을 줄이는 최적화 기법

예를 들어, std::map의 멤버 함수인 insert()의 오버로드 중 하나는 삽입 위치를 인수로 받는데, 이 인수에 위치를 전달할 것인지를 선택할 수 있어 이를 전달하면 삽입 비용이 O(1)이 되고 그렇지 않으면 O(log2N)이 된다.

5.5.8 예상 경로 최적화

여러 else-if문이 있는 if-then-else 코드에서 조건문을 무작위 순서로 배치했다면 프로그램이 if-then-else 블록을 통과할 때마다 약 절반의 조건문을 검사한다. 만약 하나의 조건을 만족할 확률이 95%라면 해당 조건문을 가장 앞으로 배치해 전체 시간의 95%를 하나의 조건문만 검사하도록 만들 수 있다.

(→ if문을 만날 때 마다 CPU는 분기 예측(branch prediction)을 해야 하기 때문에, 가장 가능성이 높은 조건을 가장 앞으로 배치함으로써 성능의 이득을 보는 것이다. 이후의 7.4.1절 참고)

6.3.2 정적 자료구조를 사용하세요

std::string, std::vector, std::map, std::list는 C++ 개발자들이 매일 사용하는 컨테이너이다. std::string, std::vector는 컨테이너에 요소를 추가할 때 저장 공간(= capacity)이 가득차면 새로운 저장 공간을 재할당한다. std::map, std::list는 추가되는 새로운 요소마다 새로운 노드를 할당한다. 어떨 때는 비용이 너무 클 수 있어, 대안이 필요하다.

std::vector 대신 std::array를 사용하세요

배열의 크기가 고정되었거나, 사용할 최대 크기를 컴파일 타임에 알 수 있다면 std::array를 사용하는 것을 권장한다. std::array는 비슷한 인터페이스를 제공하지만 고정 크기 배열을 사용하며 메모리 관리자를 호출하지 않는다.

이진 트리를 배열로 만드세요

이진 트리의 각 노드는 왼쪽과 오른쪽 자식 노드를 가리키는 포인터를 포함하는 클래스의 인스턴스이다. 이러한 방식의 문제점은 클래스가 문자 하나를 저장할 때 포인터 2개 크기의 저장 공간이 필요하며 메모라 관리자때문에 오버헤드가 발생한다는 것이다. 즉 배보다 배꼽이 더 커진다는 문제가 있다.

대안으로 이진 트리를 배열로 만드는 방법이 있다. 자식 노드를 가리키는 포인터를 포함하는 대신 노드의 색인으로 자식 노드의 색인을 계산한다. 노드의 색인이 i라면 두 자식 노드는 색인 2i와 2i+1에 있다.하나 더 말하자면 노드의 부모는 색인 i/2에 있다. <<, >> 시프트 연산으로 이런 곱셈과 나눗셈을 구현할 수 있기 때문에 계산비용 또한 저렴하다.

배열로 구현된 트리의 노드에는 왼쪽 자식과 오른쪽 자식이 트리에서 nullptr인지 확인하는 메커니즘이 필요하다. 만약 트리가 왼쪽 균형을 이루고 있다면 첫 번째로 유효하지 않은 노드의 배열 색인을 저장하는 정수 하나만으로 충분하다.

단, 균형 이진 트리에서는 연결 리스트로 표현하는 방법보다 배열로 표현하는 방법이 효율적이지 않을 수 있다. 균형을 유지하는 알고리즘에 따라 n개의 노드를 갖는 균형 이진 트리를 저장하기 위해 최대 2n개의 위치를 저장하는 배열이 필요하다(상황에 따라 균형을 유지하기 위해 Rotate 연산이 필요한데, 이 때 추가적인 저장 공간이 필요하다는 의미아닐까?). 게다가 규현을 맞추기 위해서는 단순히 포인터를 갱신하는게 아니라 노드를 다른 배열 위치에 복사해야 하는데, 노드의 크기가 큰 경우에는 복사 비용이 매우 크다. 하지만 노드의 크기가 포인터 3개보다 작다면 배열로 표현하는 방법이 더 나은 성능을 갖는다.

(→ Heap Tree인 std::priority_queue의 경우 트리임에도 기본적으로 std::vector로 구현되어있다. 즉, 부모/자식 노드에 접근하기 위한 포인터를 저장하는 오버헤드가 사라진다. Self-Balancing Binary Search Tree인 std::map의 경우, 부모/자식 포인터를 저장하는 일반적인 트리로 구현되어 있다.)

 

 

 

 

 

 

 

 

 

6.5.3 함수 반환에서 복사 제거하기

함수가 값을 반환하면 반환 타입과 동일한 익명의 임시 변수가 반환값으로 복사 생성된다.

int, double, 포인터와 같은 기본 타입에서는 복사 생성이 자명하지만, 변수가 클래스라면 복사 생성자는 일반적으로 실제 함수를 호출한다. 클래스가 크고 복잡할수록 복사 생성자가 소비하는 시간도 그만큼 길어진다. 아래 예제를 보자.

std::vector<int> scalar_product(std::vector<int> const& v, int c)
{
    std::vector<int> result;
    result.reserve(v.size());
    for (auto val : v)
        result.push_back(val * c);
    return result;
}

 

이미 생성된 반환값을 복사 생성하는 비용은 이전 절에서 설명했던 것처럼 경우에 따라 참조를 반환하는 방법으로 피할 수 있다.

불행히도, 반환될 값이 함수 안에서 계산한 값이고 자동 저장 기간을 갖는 변수에 할당했다면 이 트릭은 작동하지 않는다. 이러한 변수는 함수가 반환될 때 범위를 벗어나게 된다. 따라서 조만간 다른 값으로 덮어써진 뒤 스택의 끝에서 알 수 없는 바이트를 가리키는 쓸모없는 참조로 남게 된다. 애석하게도 일반적으로 함수안에서 결과를 계산하는 경우가 많으므로 대부분의 함수는 참조가 아닌 값을 반환한다.

반환 값으로 복사 생성하는 비용이 그다지 나쁘지 않은 것처럼, 함수에서 반환된 값은 아래 처럼 종종 호출자의 변수에 할당된다.

auto res = scalar_product(argarray, 10);

 

 

따라서 함수 안에서 복사 생성자를 호출한 뒤 호출자에서 또 다른 복사 생성자나 대입 연산자가 호출된다.

이렇게 이중으로 복사 생성하는 작동은 C++ 프로그램의 성능을 엄청나게 저하하는 킬러 역할을 했다. 다행히도 최신 C++ 표준에서 이중으로 복사 생성하는 작동을 없애는 방법을 발견했는데, 이 최적화를 복사 생략(Copy Elision) 또는 반환값 최적화(Return Value Optimization)라고 한다. RVO를 들어본 개발자들은 비용 걱정없이 객체를 값으로 반환할 수 있는 기법이라고 생각할지도 모른다. 하지만 사실이 아닌데, 컴파일러가 RVO를 수행할 수 있는 조건은 매우 구체적이다. 함수는 함수 내부에서 생성된 객체를 반환해야 한다. 컴파일러는 모든 제어 경로에서 똑같은 객체를 반환하는지 확인할 수 있어야 한다. 객체는 함수에서 선언했던 반환 타입과 똑같은 타입이어야 한다. 함수가 간단하고 제어 경로가 하나뿐이라면 컴파일러는 RVO를 수행할 가능성이 높다. 함수가 크거나 제어 경로가 분기된다면 컴파일러가 RVO가 가능한지 판단하기 어려워진다.

함수안에서 클래스 인스턴스의 생성을 제거할 뿐만 아니라 함수에서 반환하는 과정에서 이중으로 복사 생성(복사 생성자 이후 대입 연산자)하는 작동을 제거하는 방법이 있다. 개발자가 직접 작업하므로 주어진 상황에서 컴파일러가 RVO를 수행하기를 바라는 것보다 확실한 방법이다. return문을 사용해 값을 반환하는 대신, 출력용 매개변수(Out Parameter)를 사용해 값을 반환할 수 있다. 출력용 매개변수는 함수안에서 반환된 값으로 갱신하는 참조 인수이다.

void scalar_product(std::vector<int> const& v, int c, vector<int>& OutResult)
{
    OutResult.clear();
    OutResult.reserve(v.size());
    for (auto val : v)
        OutResult.push_back(val * c);
}

 

위 코드에서 출력용 매개변수 result가 함수의 인수 목록에 추가되었습니다. 이 메커니즘은 몇 가지 장점이 있다.

• 함수가 호출되었을 때 객체는 이미 생성되어 있다. 어떨 때는 객체를 지우거나 다시 초기화해야 하지만 생성하는 비용보다 크지는 않다.
• 함수안에서 갱신된 객체는 return문에서 익명의 임시 객체로 복사할 필요가 없다.
• 실제 데이터가 인수로 반환되기 때문에 함수의 반환 타입을 void로 하거나 상태 또는 오류 정보를 반환하도록 만들 수도 있다.
• 갱신된 객체는 이미 호출자의 이름에 바인딩되어 있으므로 함수에서 반환할 때 객체로 복사하거나 할당할 필요가 없다.

여러 자료구조(문자열, 벡터, 해시 테이블)는 동적 할당 배열을 가지는데, 이 배열은 프로그램에서 함수를 두 번이상 호출할 경우 종종 재사용된다. C++에는 객체를 값으로 반환할 수밖에 없는 곳이 한 군데 있는데, 바로 연산자 함수이다. 대신, 효율을 최대로 높이기 위해 RVO와 이동 문법을 사용할 수 있도록 연산자 함수를 신중하게 구현해야 한다.

(→ More Effective C++에서도 해당 주제에 관하여 RVO와 같이 언급된 적 있는 것 같다.)

6.6 이동 문법 구현하기

 

6.6.6 이동 문법의 미묘한 부분

이동 문법은 미묘한 부분이 있으몰, 충분한 지식을 갖고 신중하게 사용해야 하는 C++의 특징 중 하나이다.

 

std::vector 안에 있는 인스턴스 이동하기

객체가 std::vector 안에 있을 때 효율적으로 이동하고 싶다면 이동 생성자와 이동 대입 연산자를 작성하는 것만으로는 뭔가 부족하다. 개발자는 이동 생성자와 이동 대입 연산자를 noexcept로 선언해야 하는데, std::vector는 연산하는 과정에서 예외가 발생하면 연산하기 적의 상태로 되돌리는 강력한 예외 안전성 보장(string exception safety guarantee)를 제공하기 때문이다. 복사 생성자는 원본 객체를 변경하지 않는다. 이동 생성자는 원본 객체를 파괴한다. 이동 생성자에서 발생하는 모든 예외는 강력한 예외 안전성 보장을 위반한다.

이동 생성자 및 이동 대입 연산자를 noexcept로 선언하지 않으면, std::vector는 이동 연산 대신 덜 효율적인 복사 연산을 사용한다. 컴파일러에서는 이동 연산 대신 복사 연산을 사용한다는 경고 메시지는 발생하지도 않는다. noexcept는 매우 강력한 약속인데, 메모리 관리자, I/O, 예외를 던질 수 있는 다른 함수를 호출하지 않는다는 것을 의미한다. 또는, 프로그램에서 예외가 발생했다고 보고하지 않고 모든 예외를 감춰버린다는 것을 의미한다.

 

 

 

6.7 평평한 자료구조(Flat Data Structure)

자료구조의 요소들이 인접한 저장 공간에 함께 저장되었다면 자료구조가 평평하다(flat)고 말할 수 있다. 평평한 자료구조는 포인터로 연결된 다른 자료구조보다 성능 면에서 더 많은 장점을 갖는다.

 

평평한 자료구조는 포인터로 연결된 자료구조보다 생성할 때 메모리 관리자(동적 할당을 의미하는 듯)를 호출 하는 횟수가 적다. 일부 자료구조(list, deque, map, unordered_map)는 동적 객체를 많이 만드는 반면 다른 자료구조(vector)는 이보다 적게 만듭니다. 10장에서 다시 언급되겠지만, 비슷한 연산이 같은 O() 성능을 갖는다고 해도 std::vector, std::array같은 평평한 자료구조가 갖는 장점은 상당히 많다.

 

std::array 및 std::vector와 같은 평평한 자료구조는 list, map, unordered_map과 같은 노드 기반의 자료구조보다 메모리를 적게 차지한다. 노드 기반 구조에 있는 링크 포인터의 비용 때문이다. 소비하는 총 바이트 수는 문제가 되지 않는데, 평평한 자료구조는 요소들이 서로 인접한 위치에 있어 Cache Locality가 향상되어 더 효율적으로 탐색할 수 있기 때문이다.

7.1.10 그 밖에 다른 기법

널리 알려진 두 가지 저수준 최적화 기법이 있다.

중간값을 저장하고 반환할 필요가 없기 때문에 i++ 보다 ++i가 더 빠르다고 하거나, 반복문에서 조건식 및 증감문의 총 실행 횟수를 줄이기 위해 반복문 풀기 기법(Loop Unrolling)을 사용하라는 방식이다. 하지만 최신 C++ 컴파일러는 이미 위 같은 최적화 기법을 자동으로 적용시키기 때문에 프로그래머가 직접 최적화하는 것이 의미가 없을 확률이 크다.

 

7.2 함수에서 코드 제거하기

함수는 반복문과 마찬가지로 두 부분으로 구성되어 있다. 함수의 본문인 코드 블록과 인수 목록과 반환 타입이 있는 함수의 헤드 부분으로 나뉜다. 또한 반복문과 마찬가지로 두 부분을 따로따로 최적화할 수 있다.

함수 본문을 실행하는 비용은 내용에 따라 커질 수 있지만, 함수를 호출하는 비용은 매우 작다. 하지만 함수를 여러 번 호출하면 비용이 곱해져 비용이 커질 수 있어 이를 줄이는 것이 중요하다.

 

7.2.1 함수 호출 비용

함수가 호출되면 컴퓨터는 현재 실행 중인 코드의 위치를 저장하고, 함수 본문으로 실행 흐름을 바꾼 다음, 함수 호출이 끝나고 이전에 실행하던 명령어의 다음 위치로 복귀함으로써 실행 흐름에 함수 본문을 효율적으로 집어넣게된다.

프로그램은 함수를 호출할 때마다 다음 작동을 수행한다.

1. 실행 코드는 함수의 인수와 지역 변수를 저장하기 위해 호출 스택에 새 프레임을 삽입한다. (매개 변수, 지역 변수)

2. 각 인수 표현식을 계산한 뒤 스택 프레임에 복사한다.

3. 현재 실행 주소를 복사해서 스택 프레임에 리턴 주소로 넣는다. (리턴 주소)

→ 따라서, 스택 프레임에 매개 변수, 지역 변수, 리턴 주소가 존재하게 됨

4. 실행 코드는 실행 주소를 (함수를 호출한 후의 다음 문장 대신,) 함수 본문의 첫 번째 문장으로 갱신한다.

5. 함수 본문에 있는 명령어들을 실행

6. 스택 프레임에 저장되어 있는 리턴 주소를 명령어 주소에 복사한다. 그리고 함수를 호출한 후의 문장으로 제어권을 넘김

7. 호출 스택에서 스택 프레임을 삭제

 

7.2.4 사용하지 않는 다형성을 제거하세요

C++에서는 런타임 다형성(runtime polymorphism)을 구현하기 위해 가상 멤버 함수를 자주 사용

프로그램이 가상 함수인 drawObjPtr->Draw()를 호출하면, drawObjPtr이 가라키는 인스턴스에서 가상 함수 테이블(vftable)을 역참조해 어떤 Draw() 구현을 호출할 것 인지 선택. 런타임에 어떤 함수를 호출해야 할지 결정하기 위해, 가상 함수 테이블은 메모리를 추가로 두 번 불러오고 연관된 파이프라인 스톨의 오버헤드에도 불구하고 매우 빠른 메커니즘으로 작동함.

(Pipeline Stall이 발생한다 - 의 의미는 무엇일까? : 가상 함수는 런타임에 어떤 함수가 호출될지 결정되는 동적 바인딩이므로, 어떤 함수가 호출될지 결정되는 동안에는 다음 instruction을 미리 결정할 수 없기 때문에 해당 clock cycle 동안 Stall이 발생한다고 추측해본다)

 

사용되지 않을 다형성 때문에 불필요한 오버헤드가 발생할 수 있음

1) 클래스는 원래 구현되지 않은 파생 클래스의 계층 구조를 용이하게 만들기 위한 목적으로 설계되었을 수 있음

2) 구현되지 않은 다형성 작동을 예상해 함수를 미리 virtual로 선언했을 수도 있음

3) override된 함수가 없는 경우, DrawableObject 클래스의 Draw() 함수 선언부에서 virtual 지정자를 제거하면 Draw()를 호출하는 속도가 빨라지게 된다.

→ 가상 함수 테이블을 조회할 필요가 없으므로, 정적 바인딩으로 변경되기 때문

 

7.3.2 상수를 함께 모으세요

컴파일러는 상수 표현식을 미리 계산할 수 있다. 다음을 보자.

seconds = 24 * 60 * 60 * days;
seconds = days * (24 * 60 * 60);

 

컴파일러는 표현식의 상수 부분을 계산해 다음과 같이 만든다.

seconds = 86400 * days;

 

프로그래머가 다음과 같이 작성했다면, 

seconds = 24 * days * 60 * 60;

 

곱셈을 런타임에 계산해야 한다.

항상 상수 표현식을 모아 괄호로 묶거나 표현식의 왼쪽에 배치하자. const 변수의 초기화 값으로 분리하거나, C++11이상일 경우 constexpr 함수에 넣는 것도 좋은 방법이다. 컴파일 타임에 상수 표현식을 효율적으로 계산할 수 있다.

7.3.3 비용이 적은 연산자를 사용하세요

CPU는 덧셈을 반복함으로써 곱셈 연산을 하는데, 나눗셈의 경우 반복 연산을 조금 더 복잡하게 한다. 이런 비용을 최적화할 여지가 생긴다. 예를 들어 정수 표현식 x*8을 x<<3으로 변경하면 조금 더 효율적으로 계산할 수 있다. 이미 대부분의 컴파일러가 이 최적화 기법을 지원한다. 하지만 표현식이 x * y 또는 x * func()라면 어떨까? 컴파일러는 대부분의 경우 y나 func()이 항상 2의 거듭제곱 값인지를 확인할 수 없다. 이 때 프로그래머가 지식과 기술로 컴파일러를 능가할 수 있을 때이다. 2^k 형태의 값이 아니라 k를 제공하도록(다시 말해서, 8, 16을 리턴하는 것이 아니라 3, 4를 리턴하도록) 프로그램을 수정할 수 있다면 곱셈 연산 대신 시프트 연산을 사용하도록 표현식을 재작성할 수 있다.

곱셈 연산을 시프트 연산과 덧셈 연산으로 재작성하는 기법도 존재한다. x*9는 x*8+x*1로 작성될 수 있다. 이를 다시 (x<<3)+x로 작성할 수 있다. 이 최적화는 상수 피연산자가 많은 세트 비트를 포함하지 않을 때 가장 효과적이다. 

(→ 여기서 세트 비트(set bits)라 함은, 시프트 연산 및 덧셈에 해당되는 숫자의 set된 비트를 의미하는 듯하다. 예를 들어, 7의 경우 0111(2)이므로 set bit가 3개이다. 시프트 연산을 해야할 경우 총 3개의 비트를 시프트시켜야 한다. 8의 경우 1000(2)이므로 1개의 비트만 시프트시켜도 된다.)

7.4 제어 흐름 최적화

'2.2.7 컴퓨터는 의사 결정을 잘 할지 못합니다'에서 설명했듯이, 실행 흐름 제어보다 계산하는 것이 빠르다. 비연속적인 메모리 주소로 Instruction Pointer를 갱신할 때 발생하는 Pipeline Stall때문이다. C++ 컴파일러는 Instruction Pointer의 갱신 횟수를 줄이려고 노력한다. 가장 빠른 코드를 작성하려면 컴파일러가 수행하는 작업이 무엇인지 알고 있어야 한다.

7.4.1 if-elseif-else 대신 switch를 사용하세요

if-else if-else문은 선형 제어 흐름이다. 각각의 케이스마다 조건을 매번 새롭게 확인해야 하는데, 모든 경우가 고르게 분산되었다면 O(n)번 비교하게 된다. 자주 실행되는 코드일 경우 Pipeline Stall 비용이 크게 증가하게 된다. switch문은 각 n개의 값을 하나의 변수로 테스트할 수 있다. switch문은 if-then-else if 시퀀스와 달리, 하나의 변수로 테스트하게 되는데, 일련의 상수로 비교한다면 컴파일러가 여러가지 유용한 최적화 기법을 수행할 수도 있다.

siwtch문은 보통 순차적인 값들의 집합에서 테스트할 상수를 가져와서 테스트 값 또는 테스트 값에서 에서 파생된 표헌식을 통해 인덱싱된 점프 테이블로 컴파일하게 된다. switch문은 인덱싱 작업을 한 번 수행하고 테이블에 있는 주소로 점프한다. 경우에 아무리 늘어나더라도 비교하는데 드는 비용은 O(1)이다. 경우를 순차적으로 나타내지 않아도 되는데, 컴파일러가 점프 테이블을 정렬할 수 있기 때문이다. 
인덱싱에 사용되는 상수의 간격이 아주 넓다면, 점프 테이블은 관리하기 어려울 정도로 커지게 된다.

컴파일러는 여전히 테스트한 상수를 정렬하고 이진 탐색을 수행하는 코드를 내보내는데, 해당 시간 복잡도는 O(log2N)이므로 최악의 경우에도 if-then문 보다 느린 switch문 코드를 내보내지는 않는다. (O(N) vs O(log2N))

단, if-elseif-else 로직에서 하나의 분기문을 실행할 가능성이 매우 높은 경우가 있다. (이는 프로그래머가 알고 있을 것이다)

이 때 가장 가능성이 높은 경우부터 테스트한다면 if문의 성능은 상수 시간에 가까워질 것이다.

7.4.2 switch나 if 대신 가상 함수를 사용하세요

C++이 나오기 전에는, 개발자가 다형성을 도입하기 위해 식별 변수를 가진 struct / union 탕비을 만들었다.

예를 들면,

if (p->animalType == TIGER)
{
    tiger_pounce(p->tiger);
}
else if (p->animalType == RABBIT)
{
    rabbit_hop(p->rabbit);
}
else if (...)

 

다음과 같이 중간쯤 객체직향화된 C++ 코드도 많이 볼 수 있다.

Animal::Move()
{
    if (this->animalType == TIGER)
    {
    	pounce();
    }
    else if (this->animalType == RABBIT)
    {
        hop();
    }
    else if (...)
    ...
}

 

최적화 관점에서 위 코드의 문제점은, 객체의 파생 타입을 구분하기 위해 if statement를 사용하는 것이다. 이미 C++ 클래스에는 식별 변수로 가상 멤버 함수와 vtable ptr이 포함되어 있다. 가상 함수를 호출하는 코드는 갓아 함수 본문의 주소를 가져오기 위해 vtable에 인덱싱하게 되는데, 이 동작은 항상 상수 시간에 수행된다.(일단은 상수 시간이다. 더 자세한 것은 7.2.4 참고)

따라서 기본 클래스의 가상 멤버 함수인 move()는 동물을 나타내는 파생 클래스로 오버라이드된다. 파생 클래스에는 여러 파생 클래스가 각각 동작하는 코드가 포함되어 있다.