EASTL - 할당자(allocator)

EASTL - Electronic Arts Standard Template Library은 거대 게임 개발사인 EA가 C++ 표준 라이브러리인 STL을 게임 개발에 맞게 수정한 라이브러리이다.

EASTL에서 가장 많이 수정된 부분은 할당자인데, 이 부분만 살펴보자. STL의 할당자를 class-based에서 instance-based로 변경하자는 Halpern proposal를 따랐다.

EASTL은 instance-based 할당자(Allocator)를 사용한다.

template <class T>
class allocator
{
    typedef T* pointer;
    ...
    pointer allocate(...);
    void deallocate(...);

    void construct(...);
    void destroy(...);
    ...
}

std::allocator 는 class-based 할당자이다. 위와 같이 정의된 할당자를 인스턴스(instance) 단위로 사용하지 않고 클래스 단위로 사용한다. 할당자를 사용하는 컨테이너를 예로 들면, std::vector<int, std::allocator<int>> a 와 std::vector<int, std::allocator<int> > b 는 각기 다른 인스턴스이지만 각자 따로 메모리를 할당해 쓰는 게 아니라 템플릿 인스턴스화(template instantiation)를 거친 std::allocator<int> 에서 정의한 메모리를 사용하게 된다.

할당자 안에 객체별 전용 데이터를 허용하지 않는 제약이 생긴 이유는 표준 라이브러리의 런타임/메모리 효율에 대한 강한 압박 때문이었다. 리스트 하나만 놓고 보면 할당자가 차지하는 오버헤드는 새 발의 피 수준일지 모르나, 그 리스트에 포함된 모든 링크가 데이터를 하나씩 물고 있다면 과다 출혈로 새가 쓰러질 수도 있는 것이다.

TC++PL 19.4.3 일반화된 할당자

비야네 아저씨는 왜 이렇게 했을까? TC++PL(The C++ Programming Language)를 찾아보니 런타임과 메모리 효율 때문이라고 한다. 메모리 효율과 속도만을 생각한다면 인스턴스마다 할당자를 따로 관리할 필요 없는 class-based 할당자로 제한하는 것도 좋은 선택이라고 생각된다.

그러나 세상에는 공짜가 없다. class-based 할당자라서 애초 목표인 할당자와 컨테이너 분리가 제대로 이루어지지 않았다. 템플릿 매개변수로 넘겨줘서 할당자 정의를 하는데, 할당자가 다르면 다른 클래스로 정의된다. 그 결과 반복자(iterator) 비교가 불가능해지는데, std::range_equal(SharedList.begin(), SharedList.end(), TestList.begin(), TestList.end()) 과 같은 STL 알고리즘을 SharedList와 TestList의 할당자가 다르다면 사용할 수 없게 된다. 즉, 할당자가 다른 컨테이너 사이의 연산이 불가능해지는 상황이 발생하게 된다.

instance-based 할당자를 쓰면 어떤 할당자를 쓰던지 상관없이 컨테이너 사이의 연산이 가능해진다. 그리고 타입에 얽매이지 않고 용도에 맞게 할당자를 골라 쓸 수 있다. 가령 임시로 쓰고 버릴 컨테이너 같은 경우에 힙에서 메모리를 할당받지 않고 로컬 메모리를 사용해서 성능상 페널티를 줄일 수 있게 된다. 단, 인스턴스마다 할당자의 정보를 저장해야 하는 메모리상의 손해는 감수해야 한다.

template <class T, class Allocator = eastl::allocator>
class container
{
public:
    typedef Allocator                          allocator_type;
    ...
    public:
    container(const allocator_type& allocator = allocator_type());
    ...
    allocator_type&       get_allocator();
    const allocator_type& get_allocator() const;
    void                  set_allocator(allocator_type& allocator);
};

EASTL에서는 rebind 함수를 제거하고 할당자에 템플릿을 제거했다. 기존 컨테이너와의 호환성을 위해 템플릿 매개변수 중 할당자는 그대로 놔뒀으며 eastl::allocator를 상속받은 클래스를 컨테이너를 생성할 때 매개변수로 넣어 주거나 set_allocator 멤버 함수의 매개변수로 넣어서 할당자를 변경할 수 있다. 물론 해당 인스턴스만 변경한다.

Allocator의 rebind가 제거됐다.

template <class T>
class allocator
{
public:
    ...
template <class U> struct rebind { typedef allocator<U> other; };
};

아무 타입이나 할당할 수 있게 하는 rebind 함수는 컨테이너를 생성하는 데 필요한 데이터를 할당하는데 사용한다. 예를 들면 List 같은 경우 int와 같이 저장하는 데이터외에 Linked List를 구성하려면 앞,뒤 노드의 포인터를 저장할 공간이 추가로 필요하다. 이때 이 rebind 함수를 사용한다.

rebind 함수를 정의한 목적인 “아무 타입이나 할당” 때문에, 템플릿 함수일 수밖에 없다. 그 때문에 코드 부풀림(code bloat) 현상이 일어나고 그에 따른 성능에서 손해가 발생하게 된다.

template <class T, class Allocator = eastl::allocator>
class container
{
public:
    ...
typedef impl-defined                       node_type;
    ...
};

EASTL에서는 할당자의 rebind를 없애버리고 컨테이너가 사용하는 데이터 타입을 정의했다. 그리고 할당자를 템플릿 클래스가 아닌 클래스로 정의했다.

새로 만들지 않고 STL을 고쳐서 쓰는 건 현명한 판단이다.

STL은 신뢰하지 않는 사람들이 많은 라이브러리이다. C++ 표준 라이브러리인데도 말이다. EA 정도 규모의 개발 회사면 자체 표준 라이브러리 개발을 할 충분한 여력이 있다고 생각된다. 하지만 STL을 대체하는 라이브러리를 새로 만들기보단 STL에서 마음에 안 드는 부분을 개선했다. 라이브러리의 안정화에 드는 비용과 새로 만든 라이브러리의 교육 비용을 생각해보면 STL을 개선해서 사용하는 게 훨씬 합리적인 선택이라고 생각된다.