저번 주의 조준에 관한 블로그 포스트를 읽지 않으셨다면, 이곳에서 확인해보실 수 있습니다: https://www.sanctuary-rts.com/post/how-to-choose-a-target-from-10-000-options 주의: 프로그래머들을 위한 기술 용어가 다수 포함되어 있습니다. 전혀 이해 못 하더라도 걱정하지 마세요.
조준 알고리즘에 멀티스레딩을 채용함으로서 생기는 핵심 문제 중 하나는 유니티 Burst에서도 사용할 수 있는 재사용 가능한 병렬 리스트를 만들어내는 것이었습니다. 저번 주에 설명했듯이, 유니티의 nativeList는 동시에 사용되면서 크기 조정이 불가능했으니까요. 또한 이 리스트는 스레드에 사용될 수 없었습니다. 가치 구조에 의해 통과되는 방식이었고, 그렇기에 각각의 독립적인 스레드가 복사본을 가지고 있었으니까요. 스레드를 더하거나 크기를 조정하는 것은 복사본만을 바꾸었습니다. 이것이 동시에 이루어지기를 원했던 저희에게는 문제였죠
그래서 저는 이것을 직접 만들어보기로 했습니다: 복사도 가능하고, 스레드에 따라 크기 조종도 가능한 리스트 모음집을 말입니다.. 이동될 때마다 메모리를 같이 옮기는 것은 연산을 많이 잡아먹었기에 채용하고 싶지 않았고, 그래서 대신 분절 형태의 리스트와 비슷한 무언가를 만들어보려고 했지만, 머지않아 이것이 작동하지 않을 것이란 사실을 깨달았습니다. 1000 이하의 리스트들에서는 성능이 떨어졌으니까요. 그래서 그냥 이미 존재하는 UnsafeList 모음을 위한 스레딩 안전 포장지 비슷한 것을 만들기로 결정했죠.
문제는 버스트가 일반적으로 병렬 프로그램에서 사용되는 잠금을 지원하지 않는다는 것이었습니다. 여기서 바로 우리의 구세주, spinlocks이 등장합니다.
spinlock이 무엇인지 모르는 분들을 위해 비유를 사용해 설명해보겠습니다. 한 사람 크기의 화장실에 사람이 들어간 상태라, 당신은 다른 누군가와 함께 밖에서 기다리며 사람이 나왔는지 확인해보기 위해 잠금을 확인하는 상황이라고 상상해봅시다. 진짜 화장실과 다르게 이 화장실에는 여러 개의 다양한 문이 있고, 당신은 사람이 나오는 모습을 볼 수 있습니다. 가장 중요한 것은 당신과 다른 사람이 문이 열려있다고 해서 동시에 화장실에 들어갈 수 없다는 것입니다.
이 문제를 해결하기 위해 우리는 원자적 비교 교환 지시(atomic compare exchange instruction)를 사용했습니다. 원자적 Atomicity 이란 말은 해당 지시가 동시에 여러 스레드에서 수행되고 부정확한 답을 내어서는 안 된다는 뜻이고, 그렇기에 당신은 그것을 사용해서 화장실의 모든 문을 한 번에 잠가놓고 쓸 수 있는 것입니다. 그 뒤에는 잠금을 해제해 나오는 것이 필요하죠.
그래서 저는 그것을 사용했고, 거의 먹히긴 했지만, 여전히 몇몇의 race conditions이 남아있었습니다. 하지만 어떻게 해야 할까요? 음, 제가 이 문제를 해결하기 위해 할 수 있는 것들 중 하나는 리스트에 무언가를 추가할 때 계속해서 락이 잘 먹히는지 확인하는 것이었지만, 그건 최적화 문제에 악영향을 끼쳤을 겁니다. 제가 데이터를 추가할 때가 아니라, 리스트를 추가할 때만 락을 걸어야 했을 테니까요. 그래서 기본 코드는 대략 이런 모습이 되었습니다:
nextId = interlockedIncrement(idCounter);
while(lock) wait;
if(nextId == capacity)
{
Lock();
Expand();
Unlock();
}
Add(data);
하지만, 만약 어떻게 해서든지 두 스레드가 동시에 진입을 하게 된다면, 둘 모두가 락 체크를 통과하게 될 겁니다: 첫 번째는 정상적으로 작동하지만, 두 번째에서는 오류가 발생할 수도 있었죠. 그렇기에 다음 시도는 용량이 충분한지 확인하고, 그렇지 않다면 스핀을 돌리는 것이었습니다.
nextId = interlockedIncrement(idCounter);
while(lock) wait;
if(nextId == capacity)
{
Lock();
Expand();
Unlock();
}
while(capacity < nextId) wait;
Add(data);
하지만 여태까지의 작업에 관심을 기울이셨다면, 제가 지금 두 개의 락을 만들었을 뿐이라는 사실을 깨달으셨을 겁니다. 그래서 대신에, 저는 제 spinlock이 compareExchange를 사용해 적용되는 대신 interlockedIncrement를 사용해 적용되게 만들었습니다.
nextId = interlockedIncrement(idCounter);
while(capacity < nextId) wait;
if(nextId == capacity)
{
Expand();
}
Add(data);
리고 마침내 해피 엔딩이 찾아왔죠. 제대로 작동한 겁니다!
다시 이전 개발자 로그에서 올렸던 FinishAddingTargetsAndDistributeThem 기능을 한번 봅시다. 지금까지의 해결책 중, 이 기능은 가장 많이 최적화에 기여하고 있습니다. 대략적으로 90% 정도나 되죠.
이건 플레임 그래프로, 간단하게 설명하자면 코드가 어떻게 cpu에서 연산되는지 볼 수 있는 방식이라고 할 수 있습니다.
가장 높은 위치에 있는 “void Unity.Collections.NativeSortExtension.Sort” 기능을 한번 봅시다. 이건 목표물들이 분류되는 부분이지만, 지금 이 순간에는 스택 대부분이 유닛이 조준되어야 하는지 확인하는 데 쓰이고 있습니다.
예를 들어서 공중 유닛과 지상 유닛이 섞여있는데 조준하는 유닛은 지상 유닛만 공격할 수 있다던가, 방공 차량에게 다른 유닛보다 공중 유닛이 우선 순위인 것처럼 더 중요한 목표물 가치를 지닌 유닛이 있을 때와 같은 상황들 말입니다. 현재 이러한 유닛 카테고리들은 리스트로 구현되어져 있고, 따라서 특정한 요소를 포함하고 있는지 확인하기 위해서는 리스트 전체를 확인하게 되는데, 이러면 처리 과정이 엄청나게 느려지게 됩니다.
그래서 그 대신 one hot encoding을 하는 방식으로 최적화가 가능합니다. 이것은 일종의 해시 테이블이지만, 해시 테이블은 단순한 배열 액세스보다 느린 편에 속합니다. 그래서 속도가 빨라지긴 하지만 많이 빨라지지는 않죠. 현재 대부분의 시선 목표 카테고리들을 건너다니며 그것들이 배열 안에 있는지 확인하는 과정에서 소모되니, 최적화할 필요가 있는 셈입니다.
또다른 최적화가 필요했던 부분은 유닛들이 목표물을 찾고 그 다음에 추적을 멈춰야만 했지만, 제가 유닛의 체력을 고려하지 않은 탓에 모든 유닛들이 주변의 모든 유닛을 확인하며 체력이 있는 유닛을 찾아보려고 했던 문제였습니다. 모든 유닛들이 서로를 사거리에 둔 소위 ‘최악의 시나리오’에서는 문제가 발생할 수밖에 없었죠. 현재 우리는 94973713/(1000*1000) = 약 94백만번의 비교를 하고 있는 상태입니다.
유닛들에게 체력을 부여하면: 94백만 -> 36백만번으로 줄어들고요.
유닛 사거리를 100에서 15로 줄이면: 15백만 -> 1백만번으로 줄어들었습니다.
그러니까 체력이나 사거리를 고려한다면 100배 더 빠르게 돌아가는 셈이었죠. 그럼에도 한 가지 남아있는 중요한 문제는 목표물 리스트가 이전의 조준하는 유닛이 제외한 대상을 기억하지 못해, 체력이 0 이상인 목표물을 찾으려고 더 많은 반복 작업을 수행한다는 것이었습니다.
또한, 많은 유닛들을 포함한 적은 수의 그룹이 있을 때, 그룹의 규모가 극도로 차이가 나는 상황이 있을 수 있습니다. 한 그룹은 5000개 이상의 유닛을 포함하고 있는데, 다른 그룹 5개는 각각 500개씩만 있던가 하는 상황 말이죠. 즉, 그룹 단위에서는 평행적인 것처럼 보이지만, 그룹 안에서는 그렇지 못하고, 이런 상황은 굉장히 불균형한 작업과 그에 따른 분배를 만들어낼 수 있습니다.
하지만, 이것은 어디까지나 가장 최악의 시나리오고, 여기서 소개한 것처럼 모든 유닛이 한 번에 목표물을 찾아야 하는 상황은 게임플레이에서 거의 발생하지 않습니다.
또한 그룹 구조물 기능은 싱글 스레드지만 1.82ms가 소요되고, 전체적으로는 더 나아질 수 있지만 지금은 이 정도면 충분한 수준입니다.
다음 로그에서는 우리가 어떻게 lua 지원같은 기능을 넣을 수 있었는지 알아보도록 할게요.
또 만나요! BADUMP