[게임 프로그래밍 패턴] Optimization Patterns: Object Pool

Object Pool

---

• 객체를 매번 할당, 해제하지 않고 고정 크기 풀에 들어 있는 객체를 재사용함으로써 메모리 사용 성능을 개선한다.

Motivation

---

• 파티클 시스템
  • 파티클을 굉장히 빠르게 만들 수 있어야함.
  • 생성, 제거하는 과정에서 메모리 단편화(memory fragmentation)가 생겨서는 안됨.

메모리 단편화의 저주

• 단편화: 힙에 사용 가능한 메모리 공간이 크게 뭉쳐 있지 않고 작게 조각나 있는 상태

  • 전체 사용 가능한 메모리 양은 많아도 연속해서 사용 가능한 영역이 작을 수 있음

• 아래는 힙이 단편화되면, 이론적으로 충분한 메모리가 있음에도 메모리 할당이 실패하는 것을 보여주는 이미지이다.

• 단편화를 계속 놔두면, 지속적으로 힙에 구멍과 틈을 내서 힙을 사용하지 못하게 하고, 게임을 망가뜨림.

많은 콘솔 제조사에서, 게임 출시 전에 먼저 게임을 데모 모드로 며칠 동안 켜두는 ‘침투 테스트(soak test)’ 통과를 요구한다.(메모리 누수 + 메모리 단편화 예방하기 위해)

둘 다 만족시키기

• 게임이 실행할 때 => 메모리 미리 크게 잡아놓고 끝날 때까지 계속 들고 있으면 된다.

• 이 패턴은 이를 만족시킬 수 있다.

  • 메모리 관리자 입장: 처음에 한번 메모리 잡음, 게임이 실행되는 동안 계속 들고 있을 수 있음
  • 오브젝트 풀 사용자 입장: 마음껏 객체를 할당, 해제 가능

The pattern

---

• 재사용 가능한 객체들을 모아놓은 오브젝트 풀 클래스 정의
  • 여기에 들어가는 객체는 현재 자신이 ‘사용중’인지 여부를 알 수 있는 방법을 제공해야 한다. -초기화: 사용할 객체들 미리 생성, ‘사용 안함’ 상태로 초기화
• 새로운 객체가 필요하면 풀에 요청
  • 풀은 사용 가능한 객체를 찾아 ‘사용 중’으로 초기화한 뒤 반환한다.
• 메모리나 다른 자원 할당을 신경 쓰지 않고 객체를 생성, 삭제 가능

언제 사용?

---

• 게임 개체나 시각적 효과같이 눈으로 볼 수 있는 것에 많이 사용된다.

  • 사운드 같이 눈에 잘 보이지 않는 객체에도 사용
• 객체를 빈번하게 생성/삭제해야 하는 경우
• 객체들의 크기가 비슷한 경우
• 객체를 힙에 생성하기가 느리거나 메모리 단편화가 우려될 경우
• 데이터베이스 연결이나 네트워크 연결같이 접근 비용이 비싸면서 재사용 가능한 자원을 객체가 캡슐화하고 있는 경우

주의 사항

---

• 오브젝트 풀 사용 == ‘메모리를 어떻게 처리할지를 사용자가 더 잘 안다’라고 선언하는것
  • 오브젝트 풀의 한계도 사용자가 직접 해결해야 한다.

윈도우에서 16kb 이하의 메모리를 많이할당 => LFH(low-fragmentation heap)을 쓰면 효과가 좋다.

객체 풀에서 사용되지 않는 객체는 메모리 낭비와 다를 바 없다

• 객체 풀은 필요에 따라 크기를 조절해야 한다.
  • 크기가 너무 작으면 크래시남
  • 너무 커도 문제

한 번에 사용 가능한 객체 개수가 정해져 있다

• 메모리를 객체 종류별로 별개의 풀로 나누면 한번에 이펙트가 많이 터진다고 파티클 시스템이 메모리를 전부 먹는다거나, 메모리가 부족해 새로운 적 객체를 생성하지 못하는 문제를 막을 수 있다.

• 오브젝트 풀의 모든 객체가 사용 중이어서 재사용할 객체를 반환받지 못할 때를 대비해야함

  • 이런 일이 생기지 않도록 해야함: 풀의 크기 조절 잘하기. 상황에 따라 풀의 크기를 다르게 조절할 수 있는지 고려해야함.
  • 그냥 객체를 생성하지 않음: 파티클의 경우, 크게 상관은 없다.(파티클이 전부 사용되는 경우, 화면은 이미 화려하다)
  • 기존 객체를 강제로 제거: 사운드의 경우, 소리가 가장 작은 것과 교체, 덮어 쓴다.
  • 풀의 크기를 늘린다: 런타임에 늘리거나 보조 풀을 생성, 나중에 크기를 돌릴것인지 유지할것인지 결정해야함

객체를 위한 메모리 크기는 고정됨

• 다른 자료형이 모인 풀: 가장 큰 자료형에 맞춰야함
• 객체 크기가 다양하면 메모리 낭비 일어남

메모리관리자는 블록 크기에 따라 풀을 여러 개 준비한다. 메모리 요청을 받으면 크기에 맞는 풀에서 사용 가능한 메모리를 찾아 반환한다.

재사용되는 객체는 저절로 초기화되지 않음

• 거의 모든 메모리 관리자가 디버깅을 위해 새로 할당한 메모리를 초기화하거나 삭제된 메모리를 구별할 수 있도록 0xdeadbeaf값을 덮어 쓴다.

  • 이는 초기화되지 않은 변수나 이미 해제된 메모리를 사용하는 바람에 생기는 버그를 찾는데 도움이됨

• 새로운 객체를 초기화할 경우 주의해서 객체를 완전히 초기화해야함.

  • 객체를 회수할 때 객체에 대한 메모리를 전부 초기화 하는 디버깅 기능을 추가하는것도 고려할만함.

사용 중이지 않은 객체도 메모리에 남아 있다

• GC를 지원하는 시스템은 GC가 메모리 단편화 알아서 처리함.

• GC와 오브젝트 풀을 같이 사용한다면 충돌을 주의해야함

  • 오브젝트 풀에서는 객체가 사용중이 아니더라도 메모리를 해제하지 않기 때문에 계속 메모리에 암음.
  • 이 때 이들 객체가 다른 객체 참조 중이라면, GC는 그 객체를 회수하지 않음

예제 코드

---

• 예제는 단순한 파티클 시스템 (정해진 한 방향으로 이동 후 사라짐)

• 최소로 구현된 파티클 클래스는 다음과 같다.

  • 기본 생성자에서는 파티클을 ‘사용 안함’으로 초기화 한다
  • 파티클은 매 프레임마다 한번씩 실행되는 animate()를 통해서 애니메이션된다.

    업데이트 메서드 패턴을 사용한 예

  • inUse(): 풀은 어떤 파티클을 재사용할 수 있는지 알기 위해서 inUse()를 호출한다.

class Particle
{
public:
  Particle()
  : framesLeft_(0)
  {}

  void init(double x, double y,
            double xVel, double yVel, int lifetime)
  {
    x_ = x; y_ = y;
    xVel_ = xVel; yVel_ = yVel;
    framesLeft_ = lifetime;
  }

  void animate()
  {
    if (!inUse()) return;

    framesLeft_--;
    x_ += xVel_;
    y_ += yVel_;
  }

  bool inUse() const { return framesLeft_ > 0; }

private:
  int framesLeft_;
  double x_, y_;
  double xVel_, yVel_;
};

• 풀: 객체를 재사용할 수 있는지 알기 위해 파티클 클래스의 inUse()를 호출한다.
  • _framesLeft => 정히진 시간동안 유지 => 사용중인지 확인
  • animate()를 호출해 풀에 들어 있는 파티클을 차례차례 애니메이션한다.

class ParticlePool
{
public:
  void create(double x, double y,
              double xVel, double yVel, int lifetime);

  void animate()
  {
    for (int i = 0; i < POOL_SIZE; i++)
    {
      particles_[i].animate();
    }
  }

private:
  static const int POOL_SIZE = 100;
  Particle particles_[POOL_SIZE];
};

• particles_는 고정 길이 배열이다.(동적 배열이나, 템플릿 매개변수로 크기 전달 가능)

void ParticlePool::create(double x, double y,
                          double xVel, double yVel,
                          int lifetime)
{
  // Find an available particle.
  for (int i = 0; i < POOL_SIZE; i++)
  {
    if (!particles_[i].inUse())
    {
      particles_[i].init(x, y, xVel, yVel, lifetime);
      return;
    }
  }
}

• 사용 가능한 파티클을 찾을 때까지 풀을 순회(비효율적)
  • 파티클 렌더링을 빼면, 이게 전부, 파티클은 스스로 비활성화

    파티클생성 복잡도 O(n)

free list

• 파티클 객체의 데이터 일부를 활용하여 사용가능한 파티클을 찾는법

• 사용되지 않는 파티클에서 위치나 속도 같은 데이터는 의미가 없음.

  • _frameLeft만 있으면됨

    class Particle
    {
    public:
      // ...
  
      Particle* getNext() const { return state_.next; }
      void setNext(Particle* next) { state_.next = next; }
  
    private:
      int framesLeft_;
  
      union
      {
        // State when it's in use.
        struct
        {
          double x, y;
          double xVel, yVel;
        } live;
  
        // State when it's available.
        Particle* next;
      } state_;
     };
  

• frameLeft_를 제외한 모든 멤버 변수를 state_ 공용체의 live 구조체 안으로 옮겼다.
  • 사용중이 아닐 때: 공용체의 next가 사용됨.
  • next: 이 파티클 다음에 사용 가능한 파티클 객체를 포인터로 가리킨다.
  • next: 풀에서 사용 가능한 파티클이 묶여 있는 연결 리스트를 만들 수 있다.
  • 이렇게 하면 추가 메모리 없이 객체의 메모리를 재활용해서 자기 자신을 사용 가능한 파티클 리스트에 등록하게 할 수 있다.
• 이와 같은 걸 빈칸 리스트(free list)기법이라고 부른다.
  • 이 경우 포인터를 초기화할 때, 파티클이 생성, 삭제될 때에도 포인터를 관리, 리스트의 head도 관리해야함.

class ParticlePool
{
  // ...
private:
  Particle* firstAvailable_;
};

• 처음 풀을 생성하면, 모든 파티클이 사용 가능하므로, 빈칸 리스트에 전체가 연결된다.

ParticlePool::ParticlePool()
{
  // The first one is available.
  firstAvailable_ = &particles_[0];

  // Each particle points to the next.
  for (int i = 0; i < POOL_SIZE - 1; i++)
  {
    particles_[i].setNext(&particles_[i + 1]);
  }

  // The last one terminates the list.
  particles_[POOL_SIZE - 1].setNext(NULL);
}

• 이제 새로운 파티클을 생성하기 위해서는 첫 번째 사용 가능한 파티클을 바로 얻어오면 된다.

void ParticlePool::create(double x, double y,
                          double xVel, double yVel,
                          int lifetime)
{
  // Make sure the pool isn't full.
  assert(firstAvailable_ != NULL);

  // Remove it from the available list.
  Particle* newParticle = firstAvailable_;
  firstAvailable_ = newParticle->getNext();

  newParticle->init(x, y, xVel, yVel, lifetime);
}

• 파티클이 죽으면, 다시 빈칸 리스트에 돌려줘야함.

  • 프레임 단위에서 파티클이 죽었는지를 알 수 있도록 animate() 반환 값을 불리언으로 바꾸고 죽을 때 true를 반환한다.

  bool Particle::animate()
  {
    if (!inUse()) return false;
  
    framesLeft_--;
    x_ += xVel_;
    y_ += yVel_;
  
    return framesLeft_ == 0;
  }
  

• 파티클이 죽으면 빈칸 리스트에 다시 넣는다.

void ParticlePool::animate()
{
  for (int i = 0; i < POOL_SIZE; i++)
  {
    if (particles_[i].animate())
    {
      // Add this particle to the front of the list.
      particles_[i].setNext(firstAvailable_);
      firstAvailable_ = &particles_[i];
    }
  }
}

디자인 결정

---

• 실제 코드에서는 위 예제는 부족함.
  • 객체 풀을 더 일반적이면서 사용하기에 안전하거나 유지보수하기 쉽게 만들 수 있음.

풀이 객체와 커플링되는가?

• 객체 풀을 구현
  • 객체가 자신이 풀에 들어 있는지를 알게 할 것인지부터 결정해야함.
    • 아무 객체나 담을 수 있는 일반적인 풀 클래스를 구현해야 한다면 이런걸 못할 수 있음

객체가 풀과 커플링된다면

• 더 간단하게 구현 가능: 객체에 플래그 하나만 두면 끝.
• 객체가 풀을 통해서만 생성할 수 있도록 강제 가능: C++에서는 풀 클래스를 객체 클래스의 friend로 만든 뒤 객체 생성자를 private에 두면 된다.
  • 객체 클래스를 어떻게 사용해야 하는지를 문서화하는 효과

class Particle
{
  friend class ParticlePool;

private:
  Particle()
  : inUse_(false)
  {}

  bool inUse_;
};

class ParticlePool
{
  Particle pool_[100];
};

• ‘사용 중’ 플래그가 꼭 필요한 건 아닐 수도 있다.: 객체에 자신이 사용 중인지를 알 수 있는 상태가 이미 있는 경우가 많음.
  • ex. 화면 밖

객체가 풀과 커플링되지 않는다면

• 어떤 객체라도 풀에 넣을 수 있음
  • 일반적이면서 재사용 가능한 풀 클래스를 구현할 수 있다.

• ‘사용 중’ 상태를 객체 외부에서 관리해야한다

  • 비트 필드 따로 필요

  template <class TObject>
  class GenericPool
  {
  private:
    static const int POOL_SIZE = 100;
  
    TObject pool_[POOL_SIZE];
    bool    inUse_[POOL_SIZE];
  };
  
  

재사용되는 객체를 초기화할 때 어떤 점을 주의해야 하는가?

• 재사용을 위해, 새로 상태를 초기화 해야함.
  • 객체 초기화를 풀 클래스 안에서? 밖에서?

객체를 풀 안에서 초기화한다면

• 풀은 객체를 완전히 캡슐화할 수 있음
  • 객체를 풀 내부에 완전히 숨기기 가능
  • 객체를 아예 참조할 수 없어서 예상치 못한 재사용 막음

• 풀 클래스는 객체가 초기화되는 방법과 결합

  • 풀에 들어가는 객체 중에는 초기화 메서드를 여러개 지원하는 게 있을 수 있다.

  • 풀에서 초기화를 관리하려면, 풀에 들어 있는 객체의 모든 초기화 메서드를 풀에서 지원해야함. 객체에도 포워딩해야함

  class Particle
  {
    // Multiple ways to initialize.
    void init(double x, double y);
    void init(double x, double y, double angle);
    void init(double x, double y, double xVel, double yVel);
  };
  
  class ParticlePool
  {
  public:
    void create(double x, double y)
    {
      // Forward to Particle...
    }
  
    void create(double x, double y, double angle)
    {
      // Forward to Particle...
    }
  
    void create(double x, double y, double xVel, double yVel)
    {
      // Forward to Particle...
    }
  };
  

객체를 밖에서 초기화한다면

• 풀의 인터페이스는 단순해진다: 초기화 함수를 전부 제공할 거 없이 새로운 객체에 대한 레퍼런스만 반환하면 된다.

  class Particle
  {
  public:
    // Multiple ways to initialize.
    void init(double x, double y);
    void init(double x, double y, double angle);
    void init(double x, double y, double xVel, double yVel);
  };
  
  class ParticlePool
  {
  public:
    Particle* create()
    {
      // Return reference to available particle...
    }
  private:
    Particle pool_[100];
  };
  

• 밖에서 반환받은 객체의 초기화 메서드를 바로 호출할 수 있다.

  ParticlePool pool;

  pool.create()->init(1, 2);
  pool.create()->init(1, 2, 0.3);
  pool.create()->init(1, 2, 3.3, 4.4);

• 외부 코드에서는 객체 생성이 실패할 때의 처리를 챙겨야할 수 있다.
  • 풀이 비어있는 경우 => NULL 반환, 처리해야함

    Particle* particle = pool.create();
    if (particle != NULL) particle->init(1, 2);
    

관련 자료

---

• 경량 패턴과 비슷한 점이 많음
  • 둘 다 재사용 가능한 객체 집합을 관리
  • 차이점은 ‘재사용’의 의미
  • 경량: 같은 인스턴스를 여러 객체에서 공유 => 재사용, 같은 객체를 동시에 여러 문맥에서 사용함으로써 메모리 중복 사용을 피하는게 목적
  • 오브젝트 풀: 동시에 재사용하지 않음, 재사용의 의미는 이전 사용자가 다 쓴 다음에 객체 메모리를 회수해 가는 것을 의미, 한곳에서만 사용됨
• 같은 종류의 객체를 메모리에 모아두면 => CPU 캐시를 가득 채우는 데 도움이 됨.

출처

---

object-pool