Home [게임 프로그래밍 패턴] Optimization Patterns: Dirty Flag
Post
Cancel

[게임 프로그래밍 패턴] Optimization Patterns: Dirty Flag

Posted Feb 28, 2022
By Nor-s
21 min read

Dirty Flag

  • 불필요한 작업을 피하기 위해 실제로 필요할 때까지 그 일을 미룬다

Motivation

  • 많은 게임에서 월드에 들어 있는 모든 객체를 장면 그래프(scene graph)라는 큰 자료구조에 저장한다.

    • 렌더링 코드에서는 장면 그래프를 이용하여, 화면에 그려야 할 것을 결정

  • 가장 간단한 장면 그래프 구현: 객체 리스트 하나

    • 모든 객체에는 모델 or 그래픽에 관련된 기본단위 데이터 + 트랜스폼(transform)이 들어 잇음
    • 트랜스폼: 객체의 위치, 회전, 스케일을 표현
    • 렌더러: 객체를 그릴 때 먼저 객체 모델을 받아서 트랜스폼 적용 => 화면에 그림

  • 장면 그래프: 계층형

    • 장면 그래프의 객체: 자신에게 붙어 있는 객체의 상위 객체가 될 수 있음
      • 하위 객체의 트랜스폼: 상위의 상대적인 값으로 저장됨
    • 하지만 렌더링하기 위해서 절대 위치를 알아야함
      • 객체의 Local transform 이 아닌 world transform을 알아야함.

  • 트랜스폼 == 변환 값

로컬 트랜스폼 과 월드 트랜스폼

  • 월드 변환 계산은 간단하다. (계속해서 합치면 끝)

상위 객체 없으면 로컬 == 월드

  • 이 계산을 계속해서 해 매 프레임마다, 최신값으로 유지해야함
    • 간단한 해결: 렌더링마다 새로 계산, 프레임마다 장면 그래프를 최상위 노드부터 순회할 때, 그때마다 월드 변환 값 계산
  • 위 해결방법: CPU 자원 낭비
    • 정적 지형같은 경우도 다시 계산해야됨 => 낭비

월드 트랜스폼 캐싱

  • 변환 값을 캐시하는것이 확실한 방법
    • 모든 객체의 지역 + 월드 변환 값을 저장

  • 렌더링 => 미리 계산해놓은 월드 변환 값 사용

    • 객체가 움직임 => 월드 값 업데이트
    • 하위 객체들 또한 월드 값 재귀적으로 재계산 필요
  • 매번 재계산하면 중복 게산이 많아진다.
    • ex) 배 => 배의 하위 객체들, 배의 하위 객체 => 그 아래의 하위 객체들 ….
    • 아래 그림에서 앵무새는 마지막 값만 필요함, 이전 값들은 없어짐
  • 문제: 월드 변환 => 여러 개의 로컬 변환에 의존
    • 같은 변환을 여러번 계산하게됨

재계산 미루기

  • 문제 해결: 로컬 변환과 월드 변환 값 업데이트 분리

  • 지역 변환 값부터 한 번에 전부 변경

    • 업데이트해야 하는 월드 변환 값을 렌더링 직전에 한 번만 재계산.
  • 이를 위해 장면 그래프에 들어가는 객체에 플래그를 추가
    • 지역 변환 값이 바뀌면 플래그를 킴.
    • 월드 변환값이 필요할 때 => 플래그 검사
      • 켜져있으면 계산 후 끔

  • 플래그: ‘월드 변환 값이 더 이상 맞지 않음’

    • 맞지 않음 == 더티
  • 더티 플래그 패턴 적용한 뒤 객체 이동은 다음과 같음.

1비트 추가의 결과

  • 상위 노드를 따라가면서, 여러 번 지역 변환을 곱하던 것을 객체당 한 번의 재계산으로 합친다.
  • 움직이지 않는 객체는 변환 계산을 하지 않는다.
  • 그 외에도 렌더링 전에 제거될 객체는 월드 변환 계산을 하지 않아도 된다는 장점.

The pattern

  • 계속해서 변경되는 기본 값(primary data)
  • 파생값(derived data)은 기본 값에 비싼 작업을 거쳐야 얻을 수 있음.
  • 더티 플래그는 파생 값이 참조하는 기본 값의 변경 여부 추적
    • 기본 값 변경 => 켜짐
    • 파생 값 사용 => 더티 플래그 켜진 상태 => 재계산, 플래그 끔
      • 꺼진 상태 => 이전 캐시해놓은 파생 값 사용

언제 사용?

  • 계산과 동기화라는 두 종류의 작업에 사용
    • 둘 다 기본 값으로부터 파생 값을 얻는 게 오래 걸리거나 비용이 크다.
  • 장면 그래프 에제: 계산 양이 많음
  • 동기화: 파생 값이 디스크나 네트워크상에 있는 다른 기기 등, 원격에 있어 가져오는 비용이 큼

요구사항

  • 파생 값이 사용되는 횟수보다 기본 값이 더 자주 변경 되어져야함
    • 기본 값이 변경 => 이전 계산된 파생 값 무효화 되는 것을 막음
    • 기본값이 바뀔 때마다 파생 값이 항상 필요하면, 이 패턴은 쓸모 없음
  • 점진적으로 업데이트하기 어려워야함
    • 무게를 계산할 때 배에 무언가를 쌓는다면, 매번 무언가가 늘어날 때 재 계산하기보다는, 전체 값을 유지한 채 더하고 빼는게 좋음 => 더티 플래그가 유용하지 않은 예

주의 사항

너무 오래 지연하려면 비용이 든다

  • 더티 플래그 패턴: 오래 걸리는 작업을 결과가 실제로 필요할 때까지 지연
    • 하지만, 막상 결과가 당장 필요할 때가 많음.

  • 전체를 처리하는 데 상당한 시간이 걸리는 작업이 있다 해보자.

    • 이 작업을 지연 => 결과를 보고싶을 때 처리 => 하면 멈춤.

      GC 정책에서도 비슷함. 참조 상태가 바뀔 때 마다 => 모든 레퍼런스 횟수 업데이트 => CPU 낭비

    단순한 GC: 메모리 꽉차면 메모리 회수 => GC가 정리할 때 까지 멈춤 => GC pause 현상(STW)

    복잡한 GC: 지연 레퍼런스 카운팅( deferred ref-counting), 증분(incremental)은 두 방식을 절충(참조 횟수 업데이트, 메모리 회수)

  • 작업 지연 문제: 작업이 전부 날아갈 수 있음. - 영속적인 상태 저장에 더티 플래그 패턴을 사용할 경우(when you’re using this pattern to save some state to a more persistent form.) - ex. 텍스트 편집기 => 변경내용 저장되지 않았음. - 도중에 끄면 자동저장 기능이 없다면 전부 날라감(자동저장 => 단점 보완)

상태가 변할 때마다 플래그를 켜야함

필킬턴: “컴퓨터 과학에서 어려운 것은 캐시 무효화와 이름 정하기”

  • 기본 값 => 파생 값

    • 파생값은 본질적으로 캐시
    • 캐시 무효화(cache invalidation): 데이터를 캐시할 때 어려운 부분, 원본 데이터가 변경될 때 캐시 값이 더 이상 맞지 않음을 제때 알려주는 작업.(기본 값 변경시 더티플래그 켜주는 작업)
  • 이를 놓치면, 무효화된 파생 값 사용됨
    • 버그 생길 가능성 높음
    • 기본 값을 변경하는 모든 코드가 더티 플래그를 수정하도록 해야함
  • 해결 방법: 기본 값을 변경하는 코드를 인터페이스로 캡슐화
    • 하나의 API에서 수정하도록

이전 파생 값을 메모리에 저장해야함

동기화에 사용될 경우 메모리에 저장되지 않으므로 상관없음.

  • 더티플래그 사용x: 계산한 후 값 버리기(계산 비용 생기지만, 메모리 캐시 부담 피함)

  • 더티 플래그: 속도를 위해 메모리 희생

압축알고리즘: 압축을 푸는 데 필요한 계산 시간을 비용 삼아 공간을 최적화

예제 코드

트랜스폼 예제: 패턴 적용전 
1
2
3
4
5
6
7

class Transform
{
public:
  static Transform origin();

  Transform combine(Transform& other);
};
  • combine(): 상위 노드를 따라서 로컬 값을 전부 결합, 월드 값 리턴

  • origin(): 단위 행렬 리턴

  • 장면 그래프에 들어갈 객체의 클래스는 다음과 같다.(패턴 적용전)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class GraphNode
{
public:
  GraphNode(Mesh* mesh)
  : mesh_(mesh),
    local_(Transform::origin())
  {}

private:
  Transform local_;
  Mesh* mesh_;

  GraphNode* children_[MAX_CHILDREN];
  int numChildren_;
};

  • mesh_: 그래픽스 객체, 보이지 않을 경우 NULL

  • 장면 그래프는 모든 객체를 하위에 두는 하나의 최상단 GraphNode

1
2

GraphNode* graph_ = new GraphNode(NULL);
// Add children to root graph node...
  • 장면 그래프를 그리기 위해, 루트부터 시작해서 전체 노드 트리를 순회해야함.
    • 각 노드마다 월드 변환과 메시값을 인수로 renderMesh 호출
1

void renderMesh(Mesh* mesh, Transform transform);
트랜스폼 예제: 패턴 적용 전 순회 코드
  • 렌더링하기위해 다음 메서드 추가
1
2
3
4
5
6
7
8
9
10
11

void GraphNode::render(Transform parentWorld)
{
  Transform world = local_.combine(parentWorld);

  if (mesh_) renderMesh(mesh_, world);

  for (int i = 0; i < numChildren_; i++)
  {
    children_[i]->render(world);
  }
}
  • 장면 그래프 전체 그리기: 루트 노드부터 시작
1

graph_->render(Transform::origin());
트랜스폼 예제: 패턴 적용

  • 이 예제 코드는 모든 매시를 정확히 그리지만 매 프레임마다 모든 노드에 대해 local_.combine(parentWorld)를 호출하고 있다는 점에서 비효율적이다.

  • 더티 플레그 패턴으로 해결

    • 월드 값과 플래그 추가
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class GraphNode
{
public:
  GraphNode(Mesh* mesh)
  : mesh_(mesh),
    local_(Transform::origin()),
    dirty_(true)
  {}

  // Other methods...

private:
  Transform world_;
  bool dirty_;
  // Other fields...
};

  • 플래그 초기 값: 참(월드 값 계산 반영 전)

  • 이동하기 위해 트랜스폼 변환 함수를 추가해보자

1
2
3
4
5

void GraphNode::setTransform(Transform local)
{
  local_ = local;
  dirty_ = true;
}

  • setTransform()이 호출할 때마다 플래그도 같이 켜짐

  • 상위 노드가 이동 => 모든 하위 노드들의 월드 값 무효화

    • 하지만 전체 플래그를 변경하면 느림
    • 렌더링할 때 처리하면 됨.

여기에서는 if문 검사가 행렬 곱셈보다 빠르다고 가정

요즘 CPU에서는 파이프라이닝 기법에 많이 의존하므로 분기 예측 실패가 일어나면 사이클 많이 낭비할 가능성도 있음을 주의해야함

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void GraphNode::render(Transform parentWorld, bool dirty)
{
  dirty |= dirty_;
  if (dirty)
  {
    world_ = local_.combine(parentWorld);
    dirty_ = false;
  }

  if (mesh_) renderMesh(mesh_, world_);

  for (int i = 0; i < numChildren_; i++)
  {
    children_[i]->render(world_, dirty);
  }
}
  • 플래그가 꺼져있으면 combine 연산하지 않음을 코드에서 볼 수 있음.
  • 또한 플래그 값을 넘겨 setTransform()에서 상위가 움직였을 경우 하위 플래그들의 플래그를 변경안해줘도됨
  • 결과적으로 노드의 로컬 값을 몇 번의 대입만으로 바꿀 수 있고, 렌더링 할 때에는 이전 프레임 이후로 변경된 노드에 대해서만 최소한으로 월드 값을 계산하면됨.

이런 기법은 GraphNode에서 render()외에는 최신 월드 변환 값을 필요로 하는 곳이 없을 때만 가능. 다른 곳에 최신 값이 필요하다면 다르게 구현해야함

디자인 결정

언제 플래그를 끄는가?

결과가 필요할 때

  • 결과 값이 필요 없다면 아예 계산하지 않을 수 있다
    • 파생 값 사용빈도 < 기본 값 변경 빈도 인경우 좋음
  • 계산시간이 오래 걸린다면 거슬리는 멈춤 현상이 생길 수 있음
    • 더 일찍 계산해야함.

At well-defined checkpoints

  • 어떤 지점에서 특정 이벤트를 작동 시킬 수 있거나 작동될경우

  • 로딩 화면이나 컷신 나오는 동안 작업 처리

  • 지연 작업 처리가 플레이 경험에 영향 주지 않음
    • 작업중 관심을 돌릴 수 있는 화면 출력 가능
  • 전과는 반대로 작업처리 시점을 제어할 수 없다
    • 지연 작업 처리 == 세밀하게 제어 가능, 게임에서 깔끔하게 처리 가능.
    • 체크포인트에 억지로 보내거나 특정행동을 하도록 강제할 수 없기 때문에 플레이어가 길을 잃거나 게임 상태가 꼬여버리면 의도했던 것보다 오래 작업이 지연될 수있다.

백그라운드로 처리할 때

  • 처음 값을 변경하면, 정해진 타이머를 추가하고 타이머가 돌아올 경우 변경사항 처리

    HCI(human-computer interaction)에서는 프로그램이 사용자 입력을 받았을 때 약간 기다렸다가 응답하는 것을 이력현상(hysteresis)라고 함

  • 얼마나 자주 작업을 처리할 지 조절 가능
    • 타이머 간격 조절

  • 필요 없는 작업을 더 많이 할 수 있음

    • 변경된 상태가 얼마 안된 것, 같이 처리하게됨
  • 비동기 작업 지원
    • ‘백그라운드’로 데이터 처리: 그동안 플레이어도 계속 하던 일 할 수 있음
    • 멀티스레딩 or 동시성 기법 => 데이터 접근
    • 동시성 => 데이터 안전하게 변경 가능

플래그는 값 변화를 얼마나 세밀하게 관리하는가?

  • 개발 중인 해적 게임에서, 배를 만들고 개조 가능하다고 가정
    • 배는 서버에 자동 저장, 이전 상태로 다시 시작 가능
    • 갑판이 변경 => 값을 서버로 보내야할지를 플래그로 확인
    • 서버로 보내는 데이터 => 변경된 배에 대한 데이터 + 배의 어디가 변경되었는지를 나타내는 메타데이터

더 세밀하게 관리

  • 갑판의 모든 널빤지마다 더티플래그

  • 실제로 변경된 데이터만 처리

    • 정확하게 변경된 부분만 서버로 전달

더 듬성듬성하게 관리

  • 갑판별 더티 비트

    • 갑판의 널빤치 어느 하나라도 변경 => 갑판 전체에 대한 비트가 켜짐

  • 변경 안된 데이터도 같이 처리

  • 더티 플래그에 드는 메모리 줄어든다
  • 고정 오버헤드에 드는 시간이 줄어든다
    • 데이터 처리 외의 일종의 고정작업(메타데이터), 데이터를 더 큰 단위 == 메타데이터 적음 == 오버헤드 적음

관련 자료

  • 앵귤러 같은 브라우저-사이드 웹 프레임워크에서도 흔하게 사용됨
    • 앵귤러는 브라우저에서 어느 데이터가 변경되었고 서버에 올려야 할지를 더티 플래그로 관리한다.
  • 물리엔진에서는 어떤 객체가 움직이는 중인지, 멈춰있는지를 기록한다.
    • 멈춰 있는 물체는 충격을 받기 전에는 움직이지 않음, 누가 건드리기 전에는 아무런 처리 x
    • 이런 isMoving 플래그는 객체가 힘을 적용받아 물리 처리를 해야 하는지를 알려주는 더티플래그가 됨.

출처

dirty-flag

pattern
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents

[게임 프로그래밍 패턴] Optimization Patterns: Data Locality

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