Dirty Flag, 더티 플래그 [디자인패턴](최적화)

 

의도는 불필요한 작업을 피하기 위해 실제로 필요할 때까지 그 일을 미루는 것이다.

게으른 초기화랑 비슷한 느낌을 가지고 있다.

한 번 알아보자

 

---

 

 

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

렌더링 코드에서는 장면 그래프를 이용해서 어떤 것을 화면에 그려야 하는지를 결정한다.

 

장면 그래프를 가장 간단하게 만들겠다면 그냥 객체 리스트 하나만 있으면 된다.

모든 객체에는 모델 혹은 그래픽에 관련된 기본 단위 데이터와 함께 변환 값이 들어 있다.

변환 값은 객체의 위치, 회전, 크기 조절 (Position, Rotation, Scale) 등이 있다.

변환 값만 바꾸면 쉽게 객체를 옮기거나 회전시킬 수 있다.

 

렌더러가 객체를 그릴 때에는 먼저 객체 모델을 받아서 변환을 적용한 뒤에 화면에 그린다.

장면 그래프가 아닌 단순한 장면 집합이었다면 더 이상 고민할 것 없이 이걸로 구현이 끝났을 것이다.

 

**다시 말해서 렌더러가 모델을 변환하는 작업을 거쳐야 Screen에 나타낼 수 있다는 것이다.

 

하지만 장면 그래프는 거의 계층형이다.

장면 그래프의 객체는 자신에게 붙어 있는 객체의 상위 객체가 될 수 있다.

이럴 때 하위 객체의 변환 값은 절대 위치가 아닌 상위 위치에 상대적인 값으로 저장된다.

 

**나의 예로 들자면 몸통이 (1,2,,1)에 존재한다. 팔은 (2,2,2) 에 존재한다고 하자.

그렇다면 (2,2,2)에 가면 실제로 팔이 있느냐?

없다.

(2,2,2)는 몸의 하위 객체로 (1,2,1) 에서의 LocalPosition을 뜻한다.

실제 Global, World Position은 (1,2,1) + (2,2,2) = (3,4,3)에 있을 것이다.

 

아래서도 마찬가지다.

->라는 것은 속한다는 의미다.

Parrot이 Pirate에 속하고.. 쭉 그렇다.

 

상위 객체가 움직이면 하위 객체들도 같이 움직인다.

배의 지역 변환 값이 바뀌면 하위 객체들의 값도 다 바뀌는 것이다.

 

하지만 렌더링을 위해서는 LocalPosition이 아닌 WorldPosition을 알아야 한다.

지역 변환 값이 아닌 월드 변환 값을 알아야 한다.

 

앵무새를 그린다해보자.

 

위와 같이 변환이 된다.

모델 별로 필요한 행렬 곱셈은 몇 안된다고 해도

모든 객체에 대해서 매 프레임마다 월드 변환 계산을 해서 렌더링하는 것은 쉽지 않다.

상위 객체의 이동이 하위 객체에게 재귀적으로 영향을 미치기 때문이다.

 

뭐 그냥 렌더링할 때마다 새로 계산하는 것도 좋긴 하지만

CPU 자원을 아끼고자 한다면.. 어떻게 해야할까?

 

모든 객체를 새로하는 것보다 움직이는 객체만 계산하는 것은 어떨까?

에서 나온 것이 DIrty Flag다.

 

굳이 가만히 있는 객체의 값은 변하지 않으므로 변할 때까지 해당 연산을 미루는 것이다

 

---

 

확실한 방법은 변환 값을 캐시해서 가지고 있는 것이다.

모든 객체의 지역 변환 값과 파생 월드 변환 값을 저장한다.

렌더링할 때 미리 계산해놓은 월드 변환 값을 사용하고

객체가 움직이지 않으면 캐시에서 꺼내서 쓰면 된다.

 

객체가 움직이면 월드 변환 값도 같이 업데이트해주면 된다.

** 역시나 해당 객체의 하위 객체도 같이 업데이트하는 것이다.

 

만약 저기 해적 배는 파도에 출렁이고

망대는 바람에 흔들리면

움직이는 객체는 몇개일까?

 

우선 배가 출렁임

망대도 흔들림

해적은 망대에서 같이 흔들림

앵무새는 해적 위에서 같이 흔들림

 

 

??

배가 흔들려도 하위 객체인 앵무새까지

계산하고

망대가 흔들려도 앵무새까지...

해적도 앵무새까지..

???

앵무새는 최하위 객체로 4번이나 계산을 해야한다.

 

??? 뭐지 중복계산하는 느낌이다.

맞다. 객체는 4개가 움직였는데

월드변환 값 연산은 10번이나 한다.

그 중에 6개는 계산되어 놓고도 중복되어 버려졌다.

결국 연산은 10번 했지만 4번의 결과만 쓰였다.

 

여기서 문제점이 생긴 이유는

월드 변환이 여러 개의 지역 변환에 의존한다는 점이다.

상위 객체의 지역 변환 중 하나라도 바뀌면 하위 객체들이 모두 재계산 되다 보니 

한 프레임 내에서도 같은 변환을 여러 번 재계산하게 되는 것이다.

 

그래서 중복되는 계산을 피하기 위해서

지역 변환 값 변경과 월드 변환 값 업데이트를 분리하고자 한다.

이렇게 한다면 필요한 지역 변환 값붜 한 번에 전부 변경한 뒤에

업데이트해야 하는 월드 변환 값 연산을 렌더링 직전에 딱 한번만 하면 된다.

 

이를 위해서 장면 그래프에 들어가는 객체에 Flag, 플래그를 추가한다.

**프로그래밍에서 플래그는 On,Off 또는 True,False처럼 2가지 상태만을 가질 수 있는 데이터를 뜻한다.

 

지역 변환 값이 바뀌면 플래그를 키고

객체의 월드 변환 값이 필요할 때에는 플래그를 검사하고 

플래그가 켜져있다면 월드 변환을 계산하고 플래그를 끈다.

 

이 때 플래그는 "월드 변환 값이 이전과 달라짐"을 의미한다. 

그것을 영어로 Dirty라고 하기 때문에 Dirty Flag라고 한다.

 

 

즉, 위 그림처럼

배 이동, 망대 이동, 해적 이동, 앵무새 이동을 4번 계산하고

결국 렌더링 직전에 해당 변환된 값을 월드 변환을 하는 것이다.

 

그니까 월드 변환이 필요할 때만 계산하겠다는 말이다.

이전에는 항상 지역 변환 값이 바뀔 때 마다 월드 변환 값을 가지고 있었으니까.

 

여기서 얻는 장점은

상위 노드를 따라가면서 여러 번 지역 변환이 중복되던 계산이 사라진다.

움직이지 않는 객체는 변환 계산을 하지 않는다. (flag가 꺼져있으면 움직이지 않는 객체라는 것이겠다)

**그냥 캐시에 저장된 값을 씀

그 외에로 렌더링 전에 제거될 객체에 대해 월드 변환 연산이 이뤄지지 않아서 효율적이다.

 

---

 

이러한 패턴은

기본 값이 변경이 존재해서 내가 다시 계산해야하느냐?

그리고 

순간 변한 것을 바로 변환해서 값으로 가지고 있어야 하느냐?

에 대해서 고찰한 결과로 나왔다.

 

즉, 계속해서 변경되는 "기본 값"이 있고 "파생 값"은 기본 값에 비용이 큰 작업을 거쳐야 한다.

때문에 "기본 값"을 순간마다 비용을 들여서 "파생 값"으로 바꾼다면

"기본 값"이 많이 변하는 것만으로도 비용이 막대하다.

"파생 값"이 필요할 때 그 때의 "기본 값"으로 연산하는 것이 경제적이다.

"기본 값"의 변경을 체크해주는 것이 플래그고

플래그가 꺼져있다면 해당 변경이 없다는 의미로 그냥 캐싱된 값을 쓰면 된다.

 

---

 

그렇다면 언제 쓸 것인가? 가 문제다.

우선 이 패턴은

계산과 동기화라는 작업에 사용된다고 볼 수 있다.

둘 다 "기본 값"으로부터 "파생 값"을 얻는 것이 비용이 크다.

 

- 기본 값이 파생 값이 사용되는 횟수보다 많이 변경된다.

이 패턴은 기본 값이 변경되어 중간에 생긴 파생 결괏값이 쓸모가 없어지는 것을 막는다.

필요할 때 파생 값을 계산하기 때문이다. (중간 중간 연산하지 않는다)

 

-점진적으로 업데이트가 어려워야 한다.

앞서 본 렌더링 예제대로 변경 사항이 있을 때만 업데이트하는 것이 낫다.

 

나는 특히 이 패턴을 많이 쓴 것 같기는 하다.

하지만 저런 의도는 아니다.

 

---

 

간단한 패턴이니까 괜찮네 하면서 막 써도 되나?

라고 생각할 수 있다.

다만 다른 패턴과 마찬가지로 몇가지 주의할 점이 있다.

 

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

더티 프래그 패턴은 오래 걸리는 작업을 실제로 필요할 때까지 지연하지만

막상 해당 작업에 대한 결과를 "빨리" 얻고 싶은 경우가 있다.

하지만 애초에 이 패턴을 사용하는 이유는 결과 계산이 "느려서" 그렇다. (비용이 커서)

 

예제와 같이 월드 좌표 계산은 한 프레임 안에서도 금방할 수 있기 때문에

해당 패턴을 써도 상관이 없지만

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

이런 작업을 지연한다면 플레이어가 보기를 원할 때 연산을 시작하면

화면 프리징 현상이 생길 수도 있다.

 

또한 작업의 지연은 문제가 생겼을 때 작업 모두가 날아갈 수 있다는 점이다.

영속적인 상태 저장에 더티 플래그 패턴을 사용할 때는 더 그렇다.

 

예를 들어 텍스트 편집기는 "변경된 내용이 저장되지 않았음"을 알고 있다.

즉, "기본 값"이 많이 변했지만 정작 저장을 하기 위해서 연산된 값인 "파생 값"을 구하지 않았다는 말이다.

만약 컴퓨터가 다운이라도 된다면.. 저장하지 않은 내용들이 다 날아가게 되는 일이 일어난다.

 

 

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

파생 값은 기본 값으로부터 계산해서 얻는 값이기 때문에

본질적으로는 캐시와 같다. 데이터를 캐시할 때 가장 어려운 부분이 "캐시 무효화"인데

캐시 무효화란 원본 데이터가 변경될 때 캐시 값이 더 이상 맞지 않음을 알려주는 작업이다.

이 패턴에서는 기본 값이 바뀌었을 때를 말한다.

 

한 곳에서라도 놓치면 무효화된 파생 값을 사용하게 된다.

이렇게 되면 게임이 이상하게 작동하게 된다.

따라서 이 패턴을 사용할 때에는

기본 값을 변경하는 모든 코드가 더티 플래그를 같이 설정하도록 주의해야 한다.

 

 

**이럴 때 기본 값을 변경하는 코드를 인터페이스 같은 걸로 캡슐화하는 것도 한 방법이다.

상태를 하나의 API에서만 변경할 수 있다면 더티 플래그를 놓치지 않고 켤 수 있다.

 

 

마지막으로 메모리에 이전 파생 값이 저장되어야 한다.

파생 값이 필요할 때 더티 플래그가 꺼져 있다면 이전에 계산된 파생 값을 그대로 써야 하기에

캐시 메모리같이 어디엔가 이전의 파생 값이 저장되어 있어야 한다.

 

즉, 추가적으로 메모리가 든다는 것인데

하지만 비교적 공간적 비용이 부담이 덜하기 때문에 그렇게 큰 주의사항으로 여겨지지는 않는다.

 

 

---

 

예제로 알아보자

 

class Transform
{
public:
  static Transform origin();

  Transform combine(Transform& other);
};

 

여기에서 필요한 연산은 combine( ) 뿐이다.

combine은 상위 노드를 따라서 지역 변환 값을 전부 결합하여 객체의 월드 변환 값을 만들어 반환한다.

 

다음으로는 간단하게 장면 그래프에 들어갈 객체의 클래스를 보자.

더티 플래그 패턴을  적용하기 이전 클래스는 대강 다음과 같다.

 

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

private:
  Transform local_;
  Mesh* mesh_;

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

 

모든 노드에는 상위 노드를 기준으로 위치 등을 나타내는 지역 변환 값이 들어 있다. 

Mesh는 실제로 객체를 표현하는 그래픽스 객체다.

(보이지는 않지만 하위 노드를 묶는 용도로 사용되는 노드에서는 mesh_ 포인터가 NULL일 수 있다.)

 

마지막으로 노드에는 하위 노드 컬렉션이 있는데, 이 컬렉션은 비어 있을 수 있다.

 

이들 클래스를 사용하는 장면 그래프는 월드에 있는 모든 객체를 하위에 두는

하나의 최상단 Graph Node가 된다.

 

GraphNode* graph_ = new GraphNode(NULL);
// Add children to root graph node...

 

장면 그래프를 그리기 위해서는 루트부터 시작해서 전체 노드 트리를 순회하면서

각 노드마다 알맞은 월드 변환과 메시 값을 인수로 renderMesh 함수를 호출하면 된다.

 

void renderMesh(Mesh* mesh, Transform transform);

 

여기에서 renderMesh( )를 따로 구현하지는 않는다.

그냥 렌더링 코드가 특정 메시를 월드 어딘가에 그리는 데 필요한 작업을 한다고 치자.

장면 그래프에 있는 모든 노드에 대해서 이 함수를 정확하고 효과적으로 호출해주기만 하면 된다.

 

---

 

매번 월드 위치를 계산하면서 장면 그래프를 렌더링하기 위한 기본 순회코드부터 만들어보자.

이 코드는 최적화되지 않았지만 그만큼 단순하다.

GraphNode 클래스에 메서드를 추가해주자

 

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);
  }
}

 

상위 노드의 월드 변환 값은 parentWorld 값으로 들어온다.

이것을 노드의 지역 변환 값과 결합하기만 하면 노드의 정확한 월드 변환 값을 얻을 수 있다.

이미 노드를 순회하면서 하위 노드를 따라 내려올 때 변환 값을 같이 결합해가면서 왔기 때문에

따로 상위 노드를 따라 올라가면서 월드 변환을 하지 않아도 된다.

 

먼저 노드의 월드 변환을 계산해서

world 변수에 저장한 뒤

mesh_가 있을 경우에 메시를 그린다.

 

마지막으로 계산한 노드의 월드 변환을 인수로 하여 모든 하위 노드에 대해 재귀 호출을 한다.

render( )는 한 번에 모든 작업을 처리할 수 있는 굉장히 깔끔하면서도 단순한 재귀 함수다.

 

장면 그래프 전체를 그리기 위해서는 다음과 같이 루트 노드부터 시작하면 된다.

 

graph_->render(Transform::origin());

 

 

아래 코드는 모든 메시를 정확한 위치에 그린다는 점에서 제대로 동작한다.

다만 매 프레임마다 장면 그래프에 있는 모든 노드에 대해서

local_.combine(parentWorld)를 호출한다는 것이 비효율적이다.

 

더티 플래그 패턴으로 해결해보자.

 

 

우선 GraphNode에 필드 2개를 추가한다.

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

  // Other methods...

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

 

world_ 필드에는 이전에 계산한 월드 변환 값을 저장한다.

dirty_는 더티 플래그다.

dirty_는 초기 값이 참으로 시작한다.

(처음 만들어진 노드는 월드 변환 연산을 하지 않아 지역 변환 값이 반영이 되어있지 않기 때문)

 

더티 플래그 패턴은 움직일 수 있는 객체에 필요하니 움직이는 기능을 넣어보자

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

 

setTransform( )이 호출될 때 더티 플래그도 같이 켜진다는 점이 중요하다.

하위 노드들도 챙겨주자

 

상위 노드의 이동은 하위 노드들의 월드 변환 값을 무효화 시킨다.

하지만 여기서는 하위 노드의 더티 플래그 값을 켜지 않는다.

켜도 되겠지만 재귀함수를 호출해야 하고 느리다.

 

그보다는 렌더링할 때 처리할 수 있다.

 

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);
  }
}

 

 

월드 변환 값을 계산하기 전에 먼저 노드가 dirty 값을 확인하고

계산한 월드 변환 값을 지역 변수가 아닌 필드에 저장한다.

여기서 노드가 dirty하지 않는다면 combine( ) 부분을 건너 뛰고 이미 계산해 놓은 world_ 값을 사용한다.

 

dirty 매개변수가 핵심이다.

노드의 상위 노드에서 따라 내려오면서 한 노드가 더럽다면

해당 더티 플래그 값이 그 노드부터 아래로 따라 내려온다.

 

덕분에 setTransform( )에서 모든 하위 노드의 dirty_ 플래그를 재귀로 켜지 않아도 된다.

대신 렌더링할 때 상위 노드의 더티 플래그 값을 전달해서 월드 변환 값을 재계산해야 하는지 여부를 검사한다.

 

결과적으로 지역 변환 값을 몇 번의 대입으로만 바꿔도 되고

렌더링할 때는 이전 프레임 이후로 변경된 노드에 대해서만 최소한으로 월드 변환 계산을 하면 된다.

 

---

 

그렇다면 세부 사항을 결정할 차례다.

몇 가지만 고려해보자

 

더티 플래그를 언제 끌 것인가?

- 결과가 필요할 때

결과 값이 필요 없다면 아예 계산하지 않을 수 있다. 파생 값이 사용되는 빈도보다 기본 값이 훨씬 자주 바뀔 때 더욱 이 패턴을 사용한다.

계산 시간이 오래 걸린다면 거슬리는 멈춤 현상이 생길 수 있다.

실제로 결과 값이 필요한 순간까지 작업을 늦추다 보면 게임플레이 경험을 해칠 수 있다. 일반적으로는 계산이 충분히 빠르기 때문에 문제가 안 되지만, 작업이 오래 걸린다면 일찍 계산하도록 만들어야 할 것이다.

 

-미리 정해놓은 시점에

때로는 시간이나 게임 흐름 상 지연해놨던 작업을 처리하는 것이 자연스러운 순간이 있다.

예를 들어 해적선을 항구에 정박할 때에만 게임을 저장하게 할 수 있다. 아니면 게임 시스템과는 상관없이, 로딩 화면이나 컷신이 나오는 동안 지연 작업을 뒤에서 처리하는 수도 있다.

 

지연 작업처리가 플레이에 영향을 미치지 않아서 좋다.

게임에서 작업을 바쁘게 처리하는 동안 플레이어의 관심을 돌릴 수 있는 화면 같은 것을 보여줄 수 있다.

(로딩창과 비슷)

전과는 반대로 작업 처리 시점을 제어할 수 없다.

이 방식에서는 지연 작업 처리를 언제 할지 세밀하게 제어할 수 있고 깔끔하게 게임에서 처리하게 할 수 있다.

하지만 플레이어를 정해진 위치에 억지로 보내거나 특정 행동을 하도록 강제할 수 없기 때문에

게임 상태가 의도치 않게 꼬이면 오래 작업이 지연될 수 있다.

 

-백그라운드에서 처리할 때

처음 값을 변경할 때 정해진 타이머를 추가하고 타이머가 돌아왔을 때 

지금까지의 변경 사항을 처리한다.

얼마나 자주 작업을 처리할 지 조절할 수 있다. 타이머 간격만 조절해주면 지연 작업을 얼마나 처리할 지 정할 수 있다.

필요 없는 작업임에도 타이머마다 처리를 하므로 굳이 변경되지 않은 데이터를 손을 대는 비효율적인 작업을 할 수도 있다.

비동기 작업을 지원해야 백그라운드에서 데이터를 처리 가능하다.

멀티스레드와 같은 동시성 기법을 적용해야만 하고 이를 위한 준비를 잘 해야 한다.

 

 

그렇다면 더티 플래그는 값 변화를 얼마나 세밀하게 관리해야 하는가?

 

만약 개발중인 배를 플레이어가 커스터마이징할 수 있다고 해보자

그렇다면 해당 배는 서버에 자동 저장되기 때문에

플레이어는 언제든지 이전 상태에서 다시 커스터마이징이 가능하다.

이때 어느 부분이 변경되어 값을 서버로 보내야 할지를 더티 플래그로 확인한다.

서버로 보내는 데이터에는 변경된 배에 대한 데이터와 배의 어디가 변경되었는지를

나타내는 메타데이터가 들어있다.

 

- 세밀하게 관리된다면..?

실제로 변경된 데이터만 처리해서 정확하게 배에서 실제로 변경된 부분만 서버로 전달하면 된다.

 

-적당히 관리한다면..?

변경 안 된 데이터도 같이 처리한다.

그냥 배에 장식품 하나만 달았어도 해당 장식품이 달린 판 전체를 서버로 보낸다.

 

그리고 더티 플래그에 드는 메모리가 줄어드는 장점이 있다.

장식품 하나마다 모두 더티 플래그를 단 것보다는 적다.

 

또한 고정 오버헤드에 드는 시간을 줄일 수 있다.

어떤 변경 데이터를 처리할 때 데이터 처리 외에도 일종의 고정 작업을 해야하는데

데이터를 더 큰 단위로 할수록 이러한 오버헤드가 줄어든다고 말할 수 있다.