handle system 번역

http://gamesfromwithin.com/managing-data-relationships

Data Relationships

Data is everything that is not code: meshes and textures, animations and skeletons, game entities and pathfinding networks, sounds and text, cut scene descriptions and dialog trees. Our lives would be made simpler if data simply lived in memory, each bit totally isolated from the rest, but that’s not the case. In a game, just about all the data is intertwined in some way. A model refers to the meshes it contains, a character needs to know about its skeleton and its animations, and a special effect points to textures and sounds.

How are those relationships between different parts of data described? There are many approaches we can use, each with its own set of advantages and drawbacks. There isn’t a one-size-fits-all solution. What’s important is choosing the right tool for the job

코드가 아닌 모든 것이 데이터입니다. 메쉬와 텍스쳐, 애니메이션, 스켈레톤, 게임 엔티티와 길 찾기 네트워크, 사운드와 텍스트, 컷 씬 설명과 다이얼로그 트리 등등. 데이터가 단순히 메모리 속에서 다른 것들로부터 완전히 분리되어 존재한다면 우리의 인생이 좀 더 편하겠지만 현실은 그렇지 않습니다. 실제 게임에서는 거의 모든 데이터가 어떻게든 서로 엮여있습니다. 모델은 메쉬를 참조하고, 캐릭터는 스켈레톤과 애니메이션을 알아야 하며, 이펙트는 텍스처와 사운드를 가리킵니다.

이처럼 다양한 곳에 있는 데이터들의 관계는 어떻게 표현되어야 할까요? 여러 방법이 있겠지만 저마다의 장점과 단점이 있습니다. 모든 걸 해결하는 방법은 없기에, 작업에 알맞는 도구를 선택하는 것이 중요합니다.

Pointing The Way

In C++, regular pointers (as opposed to “smart pointers” which we’ll discuss later on) are the easiest and most straightforward way to refer to other data. Following a pointer is a very fast operation, and pointers are strongly typed, so it’s always clear what type of data they’re pointing to.

C++에서 일반적인 포인터 (추후에 논의할 “스마트 포인터”와 반대로)는 다른 데이터를 참조할 때 가장 쉽고 직관적인 방법입니다. 포인터를 따라 가는건 매우 빠른 연산이고, 타입 안전적이라 어떤 데이터을 가리키는지 늘 분명하게 알 수 있습니다.

However, they have their share of shortcomings. The biggest drawback is that a pointer is just the memory address where the data happens to be located. We often have no control over that location, so pointer values usually change from run to run. This means if we attempt to save a game checkpoint which contains a pointer to other parts of the data, the pointer value will be incorrect when we restore it.

그렇지만 단점도 존재합니다. 가장 큰 단점은 포인터가 그저 데이터가 위치할만한 메모리 주소일 뿐이라는 것입니다. 우리에게는 해당 주소에 대한 통제권이 없기 때문에 , 포인터의 값은 실행할 때마다 바뀌게 됩니다. 만약 다른 영역에 있는 데이터에 대한 포인터를 포함한 게임의 체크포인트를 저장하려 한다면, 복원된 포인터는 잘못된 정보가 될 것입니다.

Pointers represent a many-to-one relationship. You can only follow a pointer one way, and it is possible to have many pointers pointing to the same piece of data (for example, many models pointing to the same texture). All of this means that it is not easy to relocate a piece of data that is referred to by pointers. Unless we do some extra bookkeeping, we have no way of knowing what pointers are pointing to the data we want to relocate. And if we move or delete that data, all those pointers won’t just be invalid, they’ll be dangling pointers. They will point to a place in memory that contains something else, but the program will still think it has the original data in it, causing horrible bugs that are no fun to debug.

포인터는 다대 일 관계를 나타냅니다. 한 방향으로만 포인터를 따라갈 수 있고, 같은 데이터를 여러 개의 포인터가 가리키고 있을 수도 있습니다. (여러 모델이 같은 텍스쳐를 가리키는 것 처럼) 이는 포인터가 참조한 데이터의 자리를 옮기는 것이 쉽지 않다는 걸 의미합니다. 추가적인 기록을 하지 않는 이상, 재배치하려는 데이터를 가리키고 있는 모든 포인터에 대해 알 방법은 없습니다. 또 데이터를 옮기거나 지우려고 할 때 포인터들이 단순히 무효화되는 것이 아닌, 댕글링 포인터가 되어버립니다. 무언가 다른 것을 담고 있는 메모리를 가리키고 있음에도 프로그램은 여전히 기존의 데이터라고 생각하여 찾는 재미도 없는 끔찍한 버그를 일으킬 것입니다.

One last drawback of pointers is that even though they’re easy to use, somewhere, somehow, they need to be set. Because the actual memory location addresses change from run to run, they can’t be computed offline as part of the data build. So we need to have some extra step in the runtime to set the pointers after loading the data so the code can use them. This is usually done either by explicit creation and linking of objects at runtime, by using other methods of identifying data, such as resource UIDs created from hashes, or through pointer fixup tables converting data offsets into real memory addresses. All of it adds some work and complexity to using pointers.

포인터의 마지막 단점은 비록 사용하기는 쉽지만, 어딘가에서 어떻게든 값이 우선 설정되어야 한다는 것입니다. 실제의 메모리 주소가 실행할 때마다 바뀌기 때문에 자료를 빌드할 때 ‘오프라인’으로 계산될 수가 없습니다.  따라서 런타임에 자료를 로딩하고 나서 추가적인 수순을 밟고 나서야만 코드가 사용할 수 있게 됩니다. 이는 런타임에 명시적으로 객체를 생성하고 연결하거나, 해시로 만든 리소스 UID를 사용하거나 데이터의 오프셋을 실제 메모리 주소로 변환하는 포인터 픽스업 테이블을 사용하는 등의 데이터를 식별하는 방법을 말합니다. 이 모든 건 포인터를 사용하는 것에 추가적인 작업과 복잡성을 부여합니다.

Given those characteristics, pointers are a good fit to model relationships to data that is never deleted or relocated, from data that does not need to be serialized. For example, a character loaded from disk can safely contain pointers to its meshes, skeletons, and animations if we know we’re never going to be moving them around.

이러한 특성에 따르면, 포인터는 절대로 삭제되거나 재배치되지 않고, 직렬화될 필요가 없는 데이터의 관계를 구성할 때 어울립니다. 우리가 메쉬, 스켈레톤, 애니메이션등을 절대 옮기지 않을 거라는 걸 알고 있을 때에는 포인터를 포함한 캐릭터를 디스크에서 안전하게 읽어들일 수 있을 것입니다.

Indexing

One way to get around the limitation of not being able to save and restore pointer values is to use offsets into a block of data. The problem with plain offsets is that the memory location pointed to by the offset then needs to be cast to the correct data type, which is cumbersome and prone to error.

The more common approach is to use indices into an array of data. Indices, in addition to being safe to save and restore, have the same advantage as pointers in that they’re very fast, with no extra indirections or possible cache misses.

포인터 값을 저장하고 복원하지 못하는 제한을 극복하는 한 가지 방법은 데이터 블록에 대한 오프셋을 이용하는 것입니다만, 일반적인 오프셋의 문제는 오프셋이 가리키는 메모리 주소가 올바른 데이터 타입으로 캐스팅 되어야 한다는 것인데, 이는 성가시고 에러가 발생하기 쉽습니다.

좀 더 흔한 방법은 데이터의 배열에 대한 인덱스를 사용하는 것입니다. 인덱스는 저장하고 복구하는 것이 안전할 뿐만 아니라 포인터와 마찬가지로 굉장히 빠르며 추가적인 참조비용이나 캐시 미스의 가능성이 없다는 장점이 있습니다.

Unfortunately, they still suffer from the same problem as pointers of being strictly a many-to-one relationship and making it difficult to relocate or delete the data pointed to by the index. Additionally, arrays can only be used to store data of the same type (or different types but of the same size with some extra trickery on our part), which might be too restrictive for some uses.

하지만 역시 포인터와 마찬가지로 다대 일 관계일 뿐 아니라 인덱스가 가리키는 데이터를 재배치하거나 삭제하기가 까다롭습니다. 또한 배열은 같은 타입의 데이터만 저장할 수 있습니다 (또는 추가적인 꼼수로 같은 크기의 다른 타입을 가지거나). 이는 용도에 따라 너무 제한적일 수 있습니다.

A good use of indices into an array are particle system descriptions. The game can create instances of particle systems by referring to their description by index into that array. On the other hand, the particle system instances themselves would not be a good candidate to refer to with indices because their lifetimes vary considerably and they will be constantly created and destroyed.

배열에 대한 인덱스의 좋은 사용 예는 파티클 시스템입니다. 게임은 파티클 시스템의 인스턴스를 해당 정보를 담은 배열의 인덱스를 참조함으로서 만들어낼 수 있습니다. 반면 각각의 인스턴스 자체는 라이프타임이 다양하고 지속적으로 생성 소멸하기 때문에 인덱스에 대한 좋은 예는 되지 못합니다.

It’s tempting to try and extend this approach to holding pointers in the array instead of the actual data values. That way, we would be able to deal with different types of data. Unfortunately, storing pointers means that we have to go through an extra indirection to reach our data, which incurs a small performance hit. Although this performance hit is something that we’re going to have to live with for any system that allows us to relocate data, the important thing is to keep the performance hit as small as possible.

이러한 관점에서 보면 실제의 데이터 값 대신 포인터를 배열에 담으려는 시도가 해봄직할 것입니다. 다양한 타입의 데이터를 처리할 수 있을 테니까요. 하지만 포인터를 저장한다는 건 데이터에 도달하기 위해 약간의 우회를 한다는 것이고 이는 작은 성능 손실을 일으킵니다. 이런 손실은 데이터를 재배치하는 걸 허용하는 시스템에서 안고 가야하는 문제이긴 하지만, 가능하면 성능 손실은 최소화 하는 것이 중요합니다.

Because of these drawbacks, indices into an array of pointers is usually not an effective way to keep references to data. It’s usually better to stick with indices into an array of data, or extend the idea a bit further into a handle system, which is much safer and more versatile.

이러한 단점들 덕분에, 포인터 배열에 대한 인덱스는 데이터에 대한 참조를 유지하는 효율적인 방법이 못됩니다. 보통은 데이터의 배열에 대한 인덱스를 유지하거나, 좀 더 안전하고 기능이 많은 핸들 시스템으로 생각을 넓히는 것도 좋을 것입니다.

Handle-Ing The Problem

Handles are small units of data (32 bits typically) that uniquely identify some other part of data. Unlike pointers, however, handles can be safely serialized and remain valid after they’re restored. They also have the advantages of being updatable to refer to data that has been relocated or deleted, and can be implemented with minimal performance overhead.

핸들은 작은 단위의 데이터(보통 32비트)로, 다른 데이터를 고유하게 식별하는 데 사용됩니다. 포인터와는 다르게 핸들은 안전하게 직렬화되며 복구된 후에도 유효합니다. 또한 재배치되거나 삭제된 데이터에 대한 참조를 갱신할 수 있다는 장점이 있고, 최소한의 성능 오버헤드로 구현할 수 있습니다.

The handle is used as a key into a handle manager, which associates handles with their data. The simplest possible implementation of a handle manager is a list of handle-pointer pairs and every lookup simply traverses the list looking for the handle. This would work but it’s clearly very inefficient. Even sorting the handles and doing a binary search is slow and we can do much better than that.

핸들은 핸들 매니저의 키로 사용되는데,  핸들 매니저는 데이터와 핸들을 연결합니다. 핸들 매니저를 구현하는 가장 간단한 방법은 핸들-포인터 페어의 리스트로서 모든 조회는 단순히 리스트를 순회하며 핸들을 찾는 것이 됩니다. 이런 방식도 작동하겠지만 분명 매우 비효율적일 것입니다. 핸들을 정렬하고 이진탐색을 하는 것도 느리기 때문에 이보다 좋은 방법이 필요합니다.

Here’s an efficient implementation of a handle manager (released under the usual MIT license, so go to town with it). The handle manager is implemented as an array of pointers, and handles are indices into that array. However, to get around the drawbacks of plain indices, handles are enhanced in a couple of ways.

핸들 매니저에 대한 효율적인 구현. 핸들 매니저는 포인터의 배열로 구현되어 있고, 핸들은 그 배열에 대한 인덱스입니다.  하지만 일반적인 인덱스에 대한 단점을 극복하기 위해 핸들은 좀 더 개선되었습니다.

핸들이 포인터보다 유용하기 위해서 비트들을 여러 목적으로 나누어서 사용할 것입니다. 주어진 32비트는 다음과 같이 사용됩니다.

인덱스 필드 : 이 비트들이 핸들 관리자로의 실제 인덱스를 만들어 냅니다. 따라서 핸들로부터 포인터로의 이동은 매우 빠른 연산이 됩니다. 이 필드는 핸들을 동시에 얼마나 많이 사용할 지에 따라 가능한 크게 만들어야 합니다. 14비트는 16,000 개의 핸들을 제공하고 대부분의 응용프로그램에 적당하지만, 좀 더 필요하다면 추가적인 비트를 사용해서 65,000개의 핸들을 사용할 수도 있을 것입니다.

카운터 필드 : 이런 종류의 핸들을 구현하는 핵심적인 부분입니다. 우리는 필요하다면  핸들을 제거하고 해당 인덱스를 다시 사용하기를 원합니다. 그런데 프로그램의 어떤 부분에서 방금 삭제된 핸들을 저장하고 있는데 해당 슬롯이 새로운 핸들로 재사용된다면, 이전의 핸들이 무효화되었다는 건 어떻게 감지해낼 수 있을까요? 카운터 필드가 그 답입니다. 이 필드는 인덱스의 슬롯이 재사용될 때마다 증가합니다. 핸들 매니저가 핸들을 포인터로 변환하려할 때, 먼저 카운터 필드가 저장된 엔트리와 일치하는지 확인합니다. 아니라면 핸들이 만료되었음을 확인하고 널을 반환합니다.

타입 필드 : 이 필드는 포인터가 어떤 타입의 데이터를 가리키는지 알려줍니다. 하나의 핸들 매니저가 아주 다양한 타입의 데이터를 다루지는 않을 것이기에 6~8비트면 보통 충분할 것입니다. 만약 같은 타입의 데이터를 다루고 있거나 하나의 기반 클래스에서 상속되었다면 타입 필드가 아예 필요 없을 지도 모릅니다.

struct Handle {    Handle() : m_index(0), m_counter(0), m_type(0)    {}    Handle(uint32 index, uint32 counter, uint32 type)        : m_index(index), m_counter(counter), m_type(type)    {}    inline operator uint32() const;        uint32 m_index : 12;    uint32 m_counter : 15;    uint32 m_type : 5; }; Handle::operator uint32() const {    return m_type << 27 | m_counter << 12 | m_index; }

핸들 매니저 자체의 작동은 꽤나 단순합니다. HandleEntry 타입의 배열을 갖고 있는데, 각 HandleEntry는 데이터로의 포인터와 몇 가지 기록을 위한 필드를 갖고 있습니다. 효율적인 배열 삽입을 위한 freelistindex, 각 엔트리에 대응하는 카운터 필드, 그리고 엔트리가 사용중인지, 리스트의 끝인지 표시해줄 플래그.

struct HandleEntry { HandleEntry(); explicit HandleEntry(uint32 nextFreeIndex); uint32 m_nextFreeIndex : 12; uint32 m_counter : 15; uint32 m_active : 1; uint32 m_endOfList : 1; void* m_entry; };

Accessing data from a handle is just a matter of getting the index from the handle, verifying that the counters in the handle and the handle manager entry are the same, and accessing the pointer. Just one level of indirection and very fast performance.

핸들로 데이터를 접근하는 건 핸들에서 인덱스를 얻어내고, 핸들의 카운터와 핸들 매니저의 엔트리의 카운터가 일치하는 지 확인하고, 포인터에 접근하는 것만 하면 됩니다. 딱 한 계층의 우회뿐이기에 성능이 매우 빠릅니다.

기존의 핸들을 재배치하거나 무효화하는 건 핸들 매니저의 엔트리가 새로운 장소를 가리키게 업데이트하거나 삭제되었다는 플래그를 세우기만 하면 됩니다.

핸들은 장소가 바뀌거나 제거될 수 있는 데이터, 직렬화될 필요가 있는 데이터에 대한 완벽한 참조입니다. 게임 엔티티는 굉장히 다이내믹하기 때문에 빈번하게 생성되고 소멸됩니다. 따라서 게임 엔티티에 대한 참조에 핸들은 안성맞춤입니다.  만약 다른 게임 엔티티가 참조를 하고 있거나, 어떤 상태가 저장되거나 복구되어야 한다면 더욱 그렇습니다. 이런 형태의 관계에 대한 예로는 플레이어가 들고있는 객체, 적 AI가 락온한 대상 등이 있습니다.

Getting Smarter

The term smart pointers encompasses many different classes that give pointer-like syntax to reference data, but offer some extra features on top of “raw” pointers.

스마트포인터라는 용어는 참조하는 데이터에 포인터스러운 문법을 제공하지만, “날” 포인터에 몇 가지 추가적인 기능을 제공하는 다양한 클래스들을 의미합니다.

A common type of smart pointer deals with object lifetime. Smart pointers keep track of how many references there are to a particular piece of data, and free it when nobody is using it. For the runtime of games, I prefer to have very explicit object lifetime management, so I’m not a big fan of this kind of pointers. They can be of great help in development for tools written in C++ though.

일반적인 타입의 스마트 포인터는 객체의 라이프타임을 다룹니다. 특정한 데이터에 얼마나 많은 참조가 있는지 추적하다가, 아무도 사용하지 않으면 해제하는 것입니다. 저는 게임의 런타임 동안에 명시적으로 객체의 라이프타임을 관리하는 걸 선호하기 때문에 이런 류의 포인터를 좋아하지 않습니다. 하지만 C++로 툴을 개발할 때에 큰 도움이 될 것입니다.

Another kind of smart pointers insert an indirection between the data holding the pointer and the data being pointed. This allows data to be relocated, like we could do with handles. However, implementations of these pointers are often non- serializable, so they can be quite limiting.

또 다른 종류의 스마트포인터에는 가리켜지는 데이터와 포인터를 저장하는 데이터 사이에 계층을 하나 더 두는 것이 있습니다. 이는 우리가 핸들로 한 것 처럼 데이터가 재배치 되는 걸 허용하지만, 이런 류의 포인터는 종종 직렬화가 불가능하게끔 구현되기에 다소 제한적입니다.

 

If you consider using smart pointers from some of the popular libraries (STL, Boost) in your game, you should be very careful about the impact they can have on your build times. Including a single header file from one of those libraries will often pull in numerous other header files. Additionally, smart pointers are often templated, so the compiler will do some extra work generating code for each data type you instantiated templates on. All in all, templated smart pointers can have a significant impact in build times unless they are managed very carefully.

만약 STL이나 Boost의 스마트 포인터를 사용하는 걸 고려하고 있다면 이들이 빌드 시간에 줄 영향을 잘 생각해봐야 합니다. 이 라이브러리 중 하나를 인클루드 하는건 종종 또다른 많은 헤더들을 끌어들이기 때문입니다. 또 스마트 포인터는 종종 템플릿화 되어있어서 여러분이 인스턴스화한 각각의 데이터 타입에 대한 코드를 생성하느라 컴파일러가 추가적인 작업을 해야 합니다. 결과적으로 템플릿화된 스마트 포인터는 대단히 조심스럽게 관리되지 않는 이상 빌드 시간에 큰 영향을 줄 수 있습니다

It’s possible to implement a smart pointer that wraps handles, provides a syntax like a regular pointer, and it still consists of a handle underneath, which can be serialized without any problem. But is the extra complexity of that layer worth the syntax benefits it provides? It will depend on your team and what you’re used to, but it’s always an option if the team is more comfortable dealing with pointers instead of handles.

 

핸들을 감싸는 스마트 포인터를 구현하여 일반적인 포인터 같은 문법을 제공하는 것도 가능하며 특별한 문제 없이 직렬화 하게끔 하는 것도 가능합니다만, 그런 문법이 제공하는 혜택이 추가적인 계층에 대한 복잡성에 해당하는 가치가 있을까요? 여러분이 하려는 것과 여러분의 팀에 따라 다르겠지만, 팀원들이 핸들보다 포인터를 다루는 것에 익숙하다면 항상 염두에 두어야 합니다.

Conclusion

There are many different approaches to expressing data relationships. It’s important to remember that different data types are better suited to some approaches than others. Pick the right method for your data and make sure it’s clear which one you’re using.

In the next few months, we’ll continue talking about data, and maybe even convince you that putting some love into your data can pay off big time with your code and the game as a whole.

This article was originally printed in the September 2008 issue of Game Developer.

[1] I'm not too happy about the strong distinction I was making between code and data. Really, data is any byte in memory, and that includes code. Most of the time programs are going to be managing references to non-code data, but sometimes to other code as well: function pointers, compiled shaders, compiled scripts, etc. So just ignore that distinction and think of data in a more generic way.