[More Effective C++] 18. 과도 선행 평가

항목 18. 예상되는 계산 결과를 미리 준비하면 처리 비용을 깎을 수 있다.

 

 

 

과도 선행 평가(over-eager evaluation)

• 자주 요구될 것 같은 계산이 있다면, 그 요구를 효율적으로 처리할 수 있는 자료구조를 설계하여 비용을 낮추자.

template<typename NumericalType>
class DataCollection
{
public:
    // 아래 수치 데이터들은 과도 선행 평가로 성능 향상을 꾀할 수 있다.
    NumericalType min() const;
    NumericalType max() const;
    NumericalType avg() const;
    ...
};

 

 

 

캐싱(caching)

• 가장 간단하게 구현할 수 있는 방법
• 계산이 끝났고, 또 다시 사용될 것 같은 값을 캐싱한다.

int findCubicleNumber(const string& employeeName)
{
    typedef map<string, int> CubicleMap;
    static CubicleMap cubes; // 캐싱 데이터 컨테이너
    
    CubicleMap::iterator it = cubes.find(employeeName);
    
    if(it == cubes.end())
    {
        // 값이 없으면 캐싱한 후 리턴한다.
        int cubicle = cubes[employeeName] = cubicle;
        return cubicle;
    }
    else
    {
        // 값이 있으면 캐싱된 값을 리턴한다.
        return (*it).second;
    }
}

 

 

 

미리 가져오기(Prefetching)

• 사용자가 요구하는 양 이상의 양을 미리 할당해둔다.
• 라면을 여러 박스 샀을 때 라면 값을 할인받는 것과 비슷하다.
• 디스크 컨트롤러는 디스크에서 데이터를 읽을 때,
• 프로그램 쪽에서 적은 양의 데이터만 요구했더라도, 블록 하나 혹은 섹터 하나를 통째로 읽는다.
  • 조금씩 여러 번 읽는 것보다 한번 많이 읽는 쪽이 빠르기 때문이다.
  • 또한, 인접한 데이터들이 연달아 사용되는 경우가 많기 때문이다.
    • 참조 위치의 근접성(locality of reference)

templcate<typename T>
class DynArray { ... }; // 자체 확장할 수 있는 배열

DynArray<double> a;
a[22] = 3.5; // a의 유효범위는 0 ~ 22
a[32] = 0; // a의 유효범위는 0 ~ 32

// 추가 메모리 할당의 기본적인 로직
template<typename T>
T& DynArray<T>::operator[](int index)
{
    if(index < 0)
        throw 예외; // 음수는 불가
    
    if(index > 현재의 최대 인덱스)
    {
        new를 사용하여 현재 인덱스를 index까지 추가 메모리 할당
    }
    
    return 배열 내 index 번째 요소
}

// 과도 선행 평가를 반영한 로직
template<typename T>
T& DynArray<T>::operator[](int index)
{
    if(index < 0)
        throw 예외; // 음수는 불가
    
    if(index > 현재의 최대 인덱스)
    {
        int diff = index - 현재의 최대 인덱스;
        
        현재의 최대 인덱스 = index + diff 가 되도록 메모리 할당
        // 즉, 필요한 메모리 양의 두배 만큼을 한당한다.
    }
    
    return 배열 내 index 번째 요소
}

DynArray<double> a;

// 과도 선행 평가를 사용한 경우
a[22] = 3.5; // 인덱스 44가 유효하도록 메모리가 할당된다.
a[32] = 0; // 인덱스 44 이내이기 때문에 메모리 할당이 없다.

 

 

 

정리

• 메모리를 많이 쓰면 속도가 빨라진다.
  • 공간과 시간은 함께 절약하기 힘들다.
• 물론 항상 그런 것은 아니다.
  • 메모리 점유량이 큰 객체는 가상 메모리나 캐시 페이지에 들어가지 못한다.
  • 아주 드문 경우지만, 객체의 크기를 키워도 소프트웨어의 효율이 떨어질 수도 있다.
  • 운영체제의 메모리 관리 시스템이 페이징을 하는 횟수가 늘어나면 캐시 적중률(hit ratio)가 떨어지기 때문이다.
  • 그러므로 프로파일링은 필수! (항목 16 참조)
• 과도 선행 평가가 지연 평가와 상충되는 것은 아니다.
  • 지연 평가는 자주 사용되는 게 아니면 최대한 늦게 하기.
  • 과도 선행 평가는 자주 사용된다면 미리 많이 하기.