Blog

C++ 예제로 배우는 소프트웨어 설계 기법 (10) — 컨테이너 설계(Container)

스택이나 리스트 같은 컨테이너는 원소 타입과 무관하게 같은 알고리즘을 쓴다. 문제는 "아무 타입이나 담는다"를 어떻게 표현하느냐다. C는 void*, Java는 모든 클래스의 공통 기반 Object, C++은 템플릿을 쓴다. 방식마다 타입 안전성, 값 저장 가능 여부, 바이너리 크기가 다르다. 이 글에서는 스택을 void* 기반에서 Object 기반, 템플릿, 얇은 템플릿(thin template)으로 바꿔 가며 비교하고, 리눅스 커널식 침투형(intrusive) 리스트까지 g++ 13.3으로 확인한다.

이 시리즈의 다른 글

void* 기반 컨테이너

#include <cstdio>

class Stack {                                     // 무엇이든 담는 void* 스택
    void* buf_[16];
    int top_ = 0;
public:
    void push(void* p) { buf_[top_++] = p; }
    void* pop() { return buf_[--top_]; }
};

struct Point { int x, y; };

int main()
{
    Stack s;
    int n = 42;
    Point pt{3, 4};
    s.push(&n);
    s.push(&pt);
    // s.push(10);                                // 값은 못 넣는다: 주소가 필요
    int* wrong = static_cast<int*>(s.pop());      // 실제로는 Point*: 컴파일러는 모른다
    std::printf("  popped as int: %d\n", *wrong);
    Point* p2 = static_cast<Point*>(s.pop());     // 실제로는 int*
    std::printf("  popped as Point: (%d, %d)\n", p2->x, p2->y);
}
$ g++ -std=c++20 -Wall -o vp voidptr.cpp
$ ./vp
  popped as int: 3
  popped as Point: (42, -968898360)

넣은 순서와 다른 타입으로 꺼냈는데 컴파일러는 경고 하나 없고, 실행하면 쓰레기 값이 나온다. 주소만 담을 수 있으므로 10 같은 값은 넣지 못한다.

Object 기반 컨테이너

#include <cstdio>
#include <memory>
#include <string>
#include <vector>

struct Object {                                   // 모든 원소의 공통 기반 (Java 스타일)
    virtual ~Object() = default;
    virtual std::string to_string() const = 0;
};

class Stack {
    std::vector<std::unique_ptr<Object>> v_;
public:
    void push(std::unique_ptr<Object> o) { v_.push_back(std::move(o)); }
    std::unique_ptr<Object> pop() { auto o = std::move(v_.back()); v_.pop_back(); return o; }
    void dump() const { for (auto& o : v_) std::printf("  %s\n", o->to_string().c_str()); }
};

struct Integer : Object {                         // int를 담으려면 포장 클래스가 필요
    int v;
    explicit Integer(int v) : v(v) {}
    std::string to_string() const override { return "Integer(" + std::to_string(v) + ")"; }
};
struct Text : Object {
    std::string s;
    explicit Text(std::string s) : s(std::move(s)) {}
    std::string to_string() const override { return "Text(" + s + ")"; }
};

int main()
{
    Stack s;
    s.push(std::make_unique<Integer>(1));
    s.push(std::make_unique<Text>("hi"));
    s.dump();
    auto o = s.pop();
    if (auto* i = dynamic_cast<Integer*>(o.get())) std::printf("  int %d\n", i->v);   // 꺼낼 때 캐스팅
    else std::printf("  not an Integer: %s\n", o->to_string().c_str());
    std::printf("  sizeof(Integer)=%zu (int=%zu)\n", sizeof(Integer), sizeof(int));
}
$ g++ -std=c++20 -Wall -o ob object_based.cpp
$ ./ob
  Integer(1)
  Text(hi)
  not an Integer: Text(hi)
  sizeof(Integer)=16 (int=4)

공통 기반 덕분에 원소가 to_string() 같은 공통 동작을 갖지만, int 하나를 담으려고 vptr이 붙은 16바이트 포장 객체를 힙에 만든다. 꺼낼 때는 dynamic_cast로 타입을 확인해야 한다.

템플릿 컨테이너

#include <cstdio>
#include <string>

template <typename T, int N = 16>
class Stack {
    T buf_[N];
    int top_ = 0;
public:
    void push(const T& v) { buf_[top_++] = v; }
    T pop() { return buf_[--top_]; }
};

struct Point { int x, y; };

int main()
{
    Stack<int> si;
    si.push(10);                                  // 값 그대로, 포장 없음
    Stack<Point> sp;
    sp.push({3, 4});
    Point p = sp.pop();
    std::printf("  %d (%d, %d)\n", si.pop(), p.x, p.y);
    // int* wrong = sp.pop();                     // 타입이 맞지 않으면 컴파일 에러
    Stack<std::string> ss;
    ss.push("template");
    std::printf("  %s\n", ss.pop().c_str());
}
$ g++ -std=c++20 -Wall -o tp tmpl.cpp
$ ./tp
  10 (3, 4)
  template

타입마다 컴파일러가 전용 스택을 만들어 주므로 값을 그대로 담고, 잘못된 타입으로 꺼내면 컴파일 에러다. 대신 타입 수만큼 코드가 생긴다.

템플릿 코드 비대와 얇은 템플릿

포인터 타입 30개에 같은 스택을 쓰는 코드를 생성해 두 구현을 비교했다.

# 포인터 타입 30개에 대해 같은 스택을 쓰는 코드 생성: fat(일반 템플릿) vs thin(void* 코어 + 얇은 템플릿)
import sys
mode = sys.argv[1]
print('#include <cstdio>\n#include "%s_stack.h"' % mode)
for i in range(30):
    print(f"struct T{i} {{ int v = {i}; }};")
    print(f"__attribute__((noinline)) int use{i}() {{ Stack<T{i}*> s; T{i} a, b; s.push(&a); s.push(&b); s.reserve(64);"
          f" int sum = 0; while (!s.empty()) sum += s.pop()->v; return sum; }}")
print("int main() { int t = 0;" + "".join(f" t += use{i}();" for i in range(30)) + ' std::printf("%d\\n", t); }')
#pragma once
#include <cstdlib>
#include <cstring>

template <typename T>
class Stack {                                     // 모든 코드가 T마다 새로 생성된다
    T* buf_ = nullptr;
    std::size_t size_ = 0, cap_ = 0;
public:
    ~Stack() { std::free(buf_); }
    void reserve(std::size_t n)
    {
        if (n <= cap_) return;
        T* nb = static_cast<T*>(std::malloc(n * sizeof(T)));
        if (size_) std::memcpy(nb, buf_, size_ * sizeof(T));
        std::free(buf_);
        buf_ = nb;
        cap_ = n;
    }
    __attribute__((noinline)) void push(T v) { if (size_ == cap_) reserve(cap_ ? cap_ * 2 : 4); buf_[size_++] = v; }
    __attribute__((noinline)) T pop() { return buf_[--size_]; }
    bool empty() const { return size_ == 0; }
};
#pragma once
#include <cstdlib>
#include <cstring>

class StackBase {                                 // void* 코어: 한 번만 컴파일된다
    void** buf_ = nullptr;
    std::size_t size_ = 0, cap_ = 0;
public:
    ~StackBase() { std::free(buf_); }
    __attribute__((noinline)) void reserve(std::size_t n)
    {
        if (n <= cap_) return;
        void** nb = static_cast<void**>(std::malloc(n * sizeof(void*)));
        if (size_) std::memcpy(nb, buf_, size_ * sizeof(void*));
        std::free(buf_);
        buf_ = nb;
        cap_ = n;
    }
    __attribute__((noinline)) void push(void* v) { if (size_ == cap_) reserve(cap_ ? cap_ * 2 : 4); buf_[size_++] = v; }
    __attribute__((noinline)) void* pop() { return buf_[--size_]; }
    bool empty() const { return size_ == 0; }
};

template <typename T> class Stack;
template <typename T>
class Stack<T*> : private StackBase {             // 얇은 템플릿: 캐스팅만 담당 (인라인)
public:
    using StackBase::reserve;
    using StackBase::empty;
    void push(T* p) { StackBase::push(p); }
    T* pop() { return static_cast<T*>(StackBase::pop()); }
};
$ python3 gen_bloat.py fat > fat_main.cpp && python3 gen_bloat.py thin > thin_main.cpp
$ g++ -std=c++20 -O2 -o fat fat_main.cpp && g++ -std=c++20 -O2 -o thin thin_main.cpp
$ ./fat; ./thin
870
870
$ size fat thin
   text	   data	    bss	    dec	    hex	filename
  22523	    632	      8	  23163	   5a7b	fat
   9691	    632	      8	  10331	   285b	thin
$ nm -C fat | grep -c "Stack<.*>::push"; nm -C thin | grep -c "Stack.*::push"
30
1

일반 템플릿은 push가 30벌 생겨 코드 영역(text)이 22.5KB, 얇은 템플릿은 void* 코어 하나에 캐스팅만 인라인되어 9.7KB다. 타입 안전성은 템플릿 쪽 인터페이스가 그대로 지킨다.

침투형 리스트

#include <cstddef>
#include <cstdio>

struct ListHead { ListHead* next; ListHead* prev; };   // 리눅스 커널 list_head와 같은 구조

inline void list_init(ListHead* h) { h->next = h->prev = h; }
inline void list_add_tail(ListHead* n, ListHead* h)
{
    n->prev = h->prev; n->next = h;
    h->prev->next = n; h->prev = n;
}

#define container_of(ptr, type, member) \
    reinterpret_cast<type*>(reinterpret_cast<char*>(ptr) - offsetof(type, member))

struct Task {
    int pid;
    ListHead run_node;                            // 실행 큐 연결고리
    ListHead all_node;                            // 전체 목록 연결고리: 한 객체가 두 리스트에 동시에
};

int main()
{
    ListHead run_q, all;
    list_init(&run_q);
    list_init(&all);
    Task t[3] = {{100, {}, {}}, {200, {}, {}}, {300, {}, {}}};   // 노드 할당 없음
    for (auto& x : t) list_add_tail(&x.all_node, &all);
    list_add_tail(&t[2].run_node, &run_q);
    list_add_tail(&t[0].run_node, &run_q);

    std::printf("  all   :");
    for (ListHead* p = all.next; p != &all; p = p->next) std::printf(" %d", container_of(p, Task, all_node)->pid);
    std::printf("\n  run_q :");
    for (ListHead* p = run_q.next; p != &run_q; p = p->next) std::printf(" %d", container_of(p, Task, run_node)->pid);
    std::printf("\n");
}
$ g++ -std=c++20 -Wall -o in intrusive.cpp
$ ./in
  all   : 100 200 300
  run_q : 300 100

연결 고리(ListHead)를 원소 안에 넣고 container_of로 원소를 되찾는다. 노드를 따로 할당하지 않고, 한 객체를 여러 리스트에 동시에 넣을 수 있어 리눅스 커널이 이 방식을 쓴다.

방식타입 안전값 저장코드 크기원소 쪽 요구 사항
—————
void*아니오아니오 (주소만)작음없음
Object 기반실행 중 캐스팅포장 객체작음공통 기반 상속
템플릿예예타입마다 증가없음
얇은 템플릿예포인터작음없음
침투형매크로 수준원소 자체작음연결 고리 멤버 포함

주의사항

상황문제대응
———
void* 컨테이너에서 꺼낸 값 캐스팅타입 불일치가 실행 중 메모리 오류로얇은 템플릿으로 감싸 캐스팅 고정
Object 기반 컨테이너에 기본 타입포장 객체 할당·vptr 오버헤드템플릿 사용
템플릿 컨테이너를 많은 타입에 사용코드 비대, 빌드 시간 증가타입 독립 부분을 비템플릿 기반으로 분리
얇은 템플릿 코어로 값 타입 처리크기·복사 의미가 타입마다 다름포인터 특수화에만 적용
침투형 리스트에 들어 있는 객체 소멸리스트에 dangling 노드소멸 전 반드시 리스트에서 제거

마무리

  • void*와 Object 기반 컨테이너는 코드는 하나지만 타입 검사를 실행 시간으로 미룬다.
  • 템플릿은 타입 안전성과 값 저장을 얻는 대신 타입마다 코드가 생기며, 얇은 템플릿으로 공통 코드를 한 번만 만들 수 있다.
  • 할당 없이 한 객체를 여러 목록에 넣어야 하면 침투형 리스트를 쓴다.

참고

Tags: , , , , , , , , , , , ,

답글 남기기