dev.log2007. 11. 21. 01:05

rebind의 중요성

우리의 GS군이 어제 STL할당자를 만들다가.. rebind때문에 고생을 좀;; (이거 모르는 사람 은근히 많다)
STL할당자는.. 어떤 타입 T에 대해서 할당을 해주도록 되어 있다. 이를테면,

template < class T, class A = std::allocator<T> > class vector;

이런 식이다. 근데 이게 벡터 같은 놈에서는 별 상관 없는데, 리스트나 데크[각주:1], 맵, 셋등 에서는 약간 미묘하다. 이들이 할당하는 건 T가 아니기 때문이랄까. 리스트는 list_node<T> 따위, 맵에서는 tree_node<T> 따위 단위로 할당하기 때문이다. 이 글을 여기까지 읽는 사람이라면, 자료구조 수업시간에 링크드 리스트나 바이너리 서치트리 따위는 다 만들어 봤을 테니, 무슨 소리인지 알 거라고 본다.

따라서 리스트, 맵, 셋 등에서 필요한 할당은 T타입이 아니라, XXXX_node<T>타입에 대한 할당자이다. 어떤 할당자 A가 T를 할당하도록 만들어져 있는 상황에서, 컨테이너한테 A가 주어졌는데, 컨테이너가 필요한 것은 A가 할당하는 T가 아니라 N<T> 타입.

이걸 위해서 STL에는 할당자가 rebind라는 타입을 내부에 정의하도록 되어 있다. rebind는 다른게 아니라, A한테 "T말고 N<T>를 할당하려면 어떤 할당자를 쓰면 좋겠느냐-"라고 물어볼 수 있는 구석을 만들어 놓겠다는 것이다. 그럼 컨테이너에서는 T가 아닌 다른 타입을 (이를테면, N<T>) 할당 할 때는, A에서 정의한 rebind라는 녀석이 지정해 놓은 할당자를 새로 만들어서 그놈한테서 할당받으면 된다는 이야기.

 템플릿 A의 멤버 템플릿 rebind 구조체는 보통 다음과 같이 정의한다.

template < class _Other >
struct rebind
{
    typedef A<_Other> other;
};

컨테이너는 A가 주어지면, A::rebind<XXXX_node>::ohter 를 할당자로 사용해서 작업하면 된다.
이러면 '끗'.


  1. deque를 '디큐' 내지는 '데큐' 라고 읽는 사람도 은근히 많다 -_- 데크는 메모리의 '블럭'단위로 할당하여 이 포인터들을 한개의 테이블에다 저장해 놓는데, 이 테이블을 할당할 때에도 rebind가 쓰인다. [본문으로]
Posted by uhm
geek.log2007. 11. 8. 03:44

미국 게임사의 할로윈

간단하지만 강렬!

미국 게임사 직원들은 할로윈때 저런걸 하는 모냥..
원출처는여기인듯;
Posted by uhm
dev.log2007. 9. 6. 02:31

컴파일러 만세

벡터를 정규화하는 다음 두 코드를 보자.

void vector3::normalize()
{
    scalar_t len = scalar_t(1)/length();
    x *= len;
    y *= len;
    z *= len;
}

void vector3::normalize()
{
    scalar_t len = length();
    x /= len;
    y /= len;
    z /= len;
}

어느쪽이 빠를까? 언뜻보기에는 첫번째가 빨라보인다. 일반적으로 나눗셈은 곱셈보다 느리므로. 그런데 실제 50만번씩 정규화한 수행시간을 QueryPerformanceCounter로 재 보면,

47690907 : 44902704
45215687 : 44940973
45526767 : 45290300
46242218 : 44798457
44906158 : 46730200

임의로 5행을 뽑아봤는데, 놀랍게도, 대동소이하다. 왜 그럴까? 이 두 코드를 VC에서 기본 속도 최적화 옵션으로 컴파일하면 놀랍게도 다음과 같은 동일한 코드가 나온다.

 

; 78   :        scalar_t len = scalar_t(1)/length();

    fld DWORD PTR [ecx+8]
    fld DWORD PTR [ecx+4]
    fld DWORD PTR [ecx]
    fld ST(0)
    fmul    ST(0), ST(1)
    fld ST(2)
    fmul    ST(0), ST(3)

; 79   :        x *= len;
; 80   :        y *= len;
; 81   :        z *= len;

    faddp   ST(1), ST(0)
    fld ST(3)
    fmul    ST(0), ST(4)
    faddp   ST(1), ST(0)
    fsqrt
    fstp    ST(3)
    fstp    ST(0)
    fstp    ST(0)
    fdivr   DWORD PTR __real@3f800000
    fld ST(0)
    fmul    DWORD PTR [ecx]
    fstp    DWORD PTR [ecx]
    fld ST(0)
    fmul    DWORD PTR [ecx+4]
    fstp    DWORD PTR [ecx+4]
    fmul    DWORD PTR [ecx+8]
    fstp    DWORD PTR [ecx+8]


; 85   :   scalar_t len = length();

    fld DWORD PTR [ecx+8]
    fld DWORD PTR [ecx+4]
    fld DWORD PTR [ecx]
    fld ST(0)
    fmul ST(0), ST(1)
    fld ST(2)
    fmul ST(0), ST(3)

; 86   :   x /= len;
; 87   :   y /= len;
; 88   :   z /= len;

    faddp ST(1), ST(0)
    fld ST(3)
    fmul ST(0), ST(4)
    faddp ST(1), ST(0)
    fsqrt
    fstp ST(3)
    fstp ST(0)
    fstp ST(0)
    fdivr DWORD PTR __real@3f800000
    fld ST(0)
    fmul DWORD PTR [ecx]
    fstp DWORD PTR [ecx]
    fld ST(0)
    fmul DWORD PTR [ecx+4]
    fstp DWORD PTR [ecx+4]
    fmul DWORD PTR [ecx+8]
    fstp DWORD PTR [ecx+8]

코드가 같으니, 수행 시간도 사실상 동일할 수밖에. MS의 컴파일러가 제법 똑똑하게 최적화를 시켜 준다. 그런데 더 놀라운 결과는, SSE옵션을 켰을때다. SSE2 옵션을 켜고 컴파일 한 후 수행시간을 보면,

46711544 : 38123657
44900658 : 37913161
45154923 : 38187996
52286080 : 37779577
45221726 : 42707852

이번엔 오히려 나눗셈으로 계산을 한 쪽이 더 빠르다. 왜 그럴까? 컴파일된 결과를 보면 답이 나온다.

; _this$ = ecx
; 78   :        scalar_t len = scalar_t(1)/length();
    fld DWORD PTR [ecx+8]
    fld DWORD PTR [ecx+4]
    fld DWORD PTR [ecx]
    fld ST(0)
    fmul    ST(0), ST(1)
    fld ST(2)
    fmul    ST(0), ST(3)
; 79   :        x *= len;
; 80   :        y *= len;
; 81   :        z *= len;
    faddp   ST(1), ST(0)
    fld ST(3)
    fmul    ST(0), ST(4)
    faddp   ST(1), ST(0)
    fsqrt
    fstp    ST(3)
    fstp    ST(0)
    fstp    ST(0)
    fdivr   DWORD PTR __real@3f800000
    fld ST(0)
    fmul    DWORD PTR [ecx]
    fstp    DWORD PTR [ecx]
    fld ST(0)
    fmul    DWORD PTR [ecx+4]
    fstp    DWORD PTR [ecx+4]
    fmul    DWORD PTR [ecx+8]
    fstp    DWORD PTR [ecx+8]


; _this$ = ecx
; 84   :    {
    push    ecx
; 85   :        scalar_t len = length();
    fld DWORD PTR [ecx+8]
; 86   :        x /= len;
    movss   xmm0, DWORD PTR 
    fld DWORD PTR [ecx+4]
    fld DWORD PTR [ecx]
    fld ST(0)
    fmul    ST(0), ST(1)
    fld ST(2)
    fmul    ST(0), ST(3)
; 87   :        y /= len;
; 88   :        z /= len;
    faddp   ST(1), ST(0)
    fld ST(3)
    fmul    ST(0), ST(4)
    faddp   ST(1), ST(0)
    fsqrt
    fstp    ST(3)
    fstp    ST(0)
    fstp    ST(0)
    fstp    DWORD PTR _len$[esp+4]
    divss   xmm0, DWORD PTR _len$[esp+4]
    movaps  xmm1, xmm0
    mulss   xmm1, DWORD PTR [ecx]
    movss   DWORD PTR [ecx], xmm1
    movaps  xmm1, xmm0
    mulss   xmm1, DWORD PTR [ecx+4]
    mulss   xmm0, DWORD PTR [ecx+8]
    movss   DWORD PTR [ecx+4], xmm1
    movss   DWORD PTR [ecx+8], xmm0
; 89   :    }
    pop ecx

보면, 곱셈으로 계산을 한 쪽은 변화가 없고 나눗셈으로 계산을 한 쪽은 SSE명령이 생성되었다. 왜 그런지는 모른다 -_- 따라서 코드만 보고 짐작하지 말고, 직접 측정을 해봐야 한다는 결론. 컴파일러가 알아서 해주는 게 더 빠를지도 모르니까

Posted by uhm

티스토리툴바