p.473 gpg gems8



어떠한 클래스 계통구조가 주어졌을 때, 클래스 A가 클래스 B의 하위 클래스(subclass)인지 알아내고자 할 때

아래가 전형적인 방법이다.

bool IsA( Class* pA, Class* pB )
{
    while( *pA != NULL )
    {
        if( pA == pB )
        {
            return true;
        }

        pA = pA->GetParentClass();
    }
}

이렇게 될 경우 운이 나쁘면 비교하는 작업의 시간이 길어질 수 있다.


프로젝트 막바지에 운이 좋게 아래와 같이 정확히 두개씩 자식노드가 분기되는 형태로 되었다고 가정하자.



이름         아이디        클래스색인
Object         1                 수준1
Human        2                 수준2
Weapon      3                 수준3
Warrior       4                 수준3
Mage          5                 수준3
Sword         6                 수준3
Bow            7                  수준3

여기서 클래스 색인과 아이디를 이용해 반복문 없이 자식관계를 판정할 수 있다.

판정을 할 때 BitScanReverse 함수를 사용한다. 이 함수는 주어진 값의 비트들에서 제일 왼쪽에 있는 1비트의 위치를 돌려준다.

1        ( 10진수 1 )    -> 0
10      ( 10진수 2 )    -> 1
11      ( 10진수 3 )    -> 1
111    ( 10진수 7 )    -> 2

위의 균형잡힌 트리대로 노드가 구축되어 있다면 비트연산을 통해 부모관계를 판단하기가 쉽다.

위 노드들을 2진수로 표현해 보자.



여기서 BitScanReverse 를 이용해 부모관계를 판단해 보자.

우선 가장 위쪽에 있는 1을 BitScanReverse로 값을 받으면 0 이 나온다.

왼쪽에서 0번째 값이 1인 노드들은 최상위 1의 자식들이다.

그렇다. 여기 그림에 있는 모든 노드는 1의 자식이다. 왼쪽 0번째 값이 1이 아닌 값이 없기 때문이다.

그 다음으로 10으로 보자. 10진수로 2인데 BitScanReverse로 값을 받으면 1 이 나온다.

왼쪽에서 0번째, 1번째 값이 10 이면 10 의 자식이다. 여기서 100, 101 이 자식이 된다.

다음으로 11으로 보자. 10진수로 3인데 BitScanReverse로 값을 받으면 1 이 나온다.

왼쪽에서 0번째, 1번째 값이 11 이면 11의 자식이다. 여기서 110, 111 이 자식이 된다.


아래가 위 내용을 판단하는 코드이다.

bool FastIsA( Class* pA, Class *pB )
{
    int nAIndex = pA->GetClassIndex();
    int nBIndex = pA->GetClassIndex();

    return nBIndex == ( nAIndex >> ( BitScanReverse(nAIndex) - BitScanReverse(nBIndex) );
}


위 경우는 반드시 균현잡힌 트리 구조일 때 사용이 가능하다. 하지만 모든 프로젝트에서 정보를 저렇게 구현한다고는

생각하기 어렵다.

그래서 균형 이진 트리가 아니더라도 허위 노드를 삽입해서 균형 이진트리 비슷한 모양을 구축하면 위 방법대로 사용할 수 있다.

자식노드의 개수와 레벨을 통해 허위 노드를 어떻게 만들지 판단한다.


void BuildTree( Class* pA )
{
    int nCurrentClassIndex = pA->GetClassIndex();
    int nNumChildClasses = pA->GetNumberOfChildClasses();
    int nNumLevels = BSR(nNumChildClasses) + 1;
    int nChildIndexStart = nCurrentClassIndex << nNumLevels;

    for( int i = 0 ; i < nNumChildClasses ; ++i )
    {
        class* pChild = pA->GetChildClass( i );
        pChild->SetClassIndex( nChildIndexStart + i );
        BuildTree(pChild);
    }
}

모양은 바꼈지만 위 방식대로 부모관계를 판단할 수 있는 기틀을 마련할 수 있다.




많은 곳에서 IsA를 이렇게 판단하고 있다면 이 방법을 적용해서 제법 속도향상을 기대할 수 있겠다.

요즘은 제너럴 프로그램을 통해 CPU속도를 빠르게 하는 방법에 대해 관심을 가지고 있어서

이러한 내용들을 계속 공부해 보려 한다.

그리고 요즘 게임에서 돈잔치를 벌이는데 있어 유용한 기술의 보조작업을 하고 있다.

알고리즘 적으로 막히는 부분은 다 해결되서 상당히 기쁘다.


그리고 아래는 라이트 셰프트를 어떻게 해서든 적용해 보고싶은 개발자 아버지를 둔 가정의 흔한 식사 모습.




라이트 셰프트도 마저 해야 하는데........

_BitScanReverse, _BitScanReverse64

p.513 4.4 gpg gems 8


CPU 처리속도는 빨라졌지만 메모리 접근속도는 그만큼 빨라지지 못했다.

이문제를 해결하기 위해 캐시를 유용하게 사용해야 한다.

문제는 메모리가 CPU에 비해 굉장히 느리다는 것이다. 그 이유는 CPU와 멀리 떨어져 있기 때문이다.

해결책이 최근 쓰인 주 메모리 비트들의 복사본을 캐시에 담아두는 것이다.

L1, L2, L3 캐시가 있으며 L1캐시가 가장 작고 가장 빠르다.


아래 제안을 추천.

-낭비 피하기

꼭 필요한 자료만 읽는다.

그리고 자료조직화와 메모리를 연속적으로 읽거나 쓰면 좋다. 이 부분은 뒷부분에 다시 설명.


- 자료 줄이기

자료가 작을수록 캐시에 잘 들어맞는다. 아주 크지 않는 정수의 경우 2 BYTE 정수(short)나 그냥 1 BYTE를 사용하는것도 좋다.

64비트 부동소수점( double ) 대신 32비트 단정도 부동소수점 ( float )을 사용할 수도 있다.

가장 큰 절약은 부울 형식에서 발생하는데 참 또는 거짓을 나타내는 부울값 하나가 많게는 4바이트까지 차지하는데,

이를 1비트로 표현한다면 공간을 엄청나게 절약할 수 있다.

그리고 구조체를 잘 조직화해서 속도를 올릴 수 있다고 한다.

아래는 단순히 변수의 순서만 큰것에서 작은 것으로 변경한 것인데 구조체의 크기 차이가 발생한다.

채움(padding)이 줄어들었기 때문이라고 한다.

struct WastedPadding // 총 20바이트
{
char var1; // 1바이트
float var2; // 4바이트
char var3; // 1바이트
int var4; // 4바이트
char var5; // 1바이트
};


struct OptimalPadding // 총 12바이트
{
float var2; // 4바이트
int var4; // 4바이트
char var1; // 1바이트
char var3; // 1바이트
char var5; // 1바이트
};

구조체의 경우 변수가 큰것을 먼저 선언해서 사용하도록 하자.


- 자료 조직화

캐시에 신경써서 조직화 해야 한다. 자료구조를 연속이되게 하고 자주쓰이는 자료는 한데 모으고, 자주 사용하지 않는 자료는

멀리 떨어지게 만든다.

연결 리스트의 경우 캐시 성능을 떨어뜨린다. 노드로의 포인터를 저장하는데 공간이 낭비되고 노드들의 메모리가

여기저기 흩어질 수 있기 때문이다. 즉, 공간 국소성이 나쁘다. 연속해서 저장하는 STL의 vector나 deque 사용을 추천한다.

그리고 자주 사용되는 자료와 그렇지 않은 자료 구조체 혹은 클래스를 나누어서 만드는 것이 좋다.




그리고 자료를 미리 가져와서 사용할 수 있도록 하는 것이 좋다.

자료가 도착할 때 까지 CPU가 놀고 있어야 하므로, CPU가 사용할 준비가 되었을 때 자료가 이미 캐시에 들어 있도록 자료를

미리 가져온다면 속도가 빨라진다.


다음번 배열 요소 네개를 미리가져오는 예.

for( int i = 0 ; i < 4 * n ; i += 4)
{
Touch( array[ i + 4 ] ); // 메모리 미리 가져오기
Process( array[ i + 0 ] );
Process( array[ i + 1 ] );
Process( array[ i + 2 ] );
Process( array[ i + 3 ] );
}

자료를 너무 일찍 가져오면 실제로 쓰이기 전에 캐시에서 방출될 수 있고 너무 늦으면 여전히 CPU가 기다려야 할 수 있다.

이 작업들이 확실히 효과가 있는지는 프로파일러로 검사해보는 것 뿐이다.

CPU가 자료를 기다리느라 시간을 낭비하기 때문인지 아닌지는 CPU 자체에 내장된 성능측정 도구인

성능 카운터( performance counter )로 확인이 가능하다.

p.697    gpg gems 8

게임 플레이 도중에 로딩이 되더라도 처음에 기다리는 시간을 최소화 할 때 유용.

로딩이 덜 된 정보는 그리지 않거나 더미 텍스쳐를 입혀서 렌더링.

지형정보를 조각조각 내서 로딩 시키고 로딩 후 생성해 내는 알고리즘은 다시 자세히 보자.