시작해봅니다.

1. 문자열의 문제점

문자열을 비교하는 함수 strcmp(), 문자열을 복사하는 함수 strcpy() 모드 O(n)의 동작이다.

ⓐ 문자열 클래스

- 문자열 객체를 넘길 때는 값이 아닌 참조로 넘길 것

- 일찍 코드를 프로파일링하고 자주해서 문자열 클래스가 프레임 저하의 주원인이 되지 않게 살필 것

ⓑ 고유 식별자

- 식별자에 문자을 쓰는 것은 자연스러운 일이지만 strcmp()를 사용하는 것은 너무 느리다.

- 그래서 해시 문자열ID를 사용한다.

- 문자열을 정수 처럼 비교하기 때문에 빠르다.

- 해시 테이블에 저장하면 해시 코드를 통해 언제든 문자열을 가져올 수 있다.

* 대부분의 게임 엔진들을 런타임에 해시 값을 계산하지 않는다. ( 해시 함수를 통가하는 속도는 느리기 때문)

* 그렇기 때문에 문자열을 해싱하는 것을 인턴이라고 하는데 인턴을 미리 해두고 저장해서 해시함수를 통과하지 않고 사용하는 것이 좋다.

2. 현지화

ⓐ 유니코드

- 영어와 다른 문자를 사용하기 위한 문자 셋 시스템

ⓑ UTF-8

- 각 문자 코드는 8비트지만 어떤 문자들은 1바이트 보다 큰 공간을 차지하기도 한다. ( 멀티 바이트 셋 MBCS)

- 장점은 ANSI 인코딩과 호환이 된다. 멀티바이트의 문자의 첫 바이트는 항상 가장 높은 비트가 1이기 때문이다.

ⓒ UTF-16

- 표준은 더 간단하지만 좀 더 비싼 방법을 사용한다.

- 와이드 캐릭터 셋(WCS) 이라고 부르는데 16비트를 사용한다.

ⓓ 윈도우 환경에서 유니코드

- UTF-16 하나의 데이터 타임은 wchat_t 이고 UTF-8이나 ANSI 문자열을 나타내는 것은 char이다.

- 캐릭터 셋에 무관하게 짤 수 있는 방법은 TCHAR을 사용하는 것이다.

( typedef를 사용해서 ANSI 모드에선 char이 되고 UTF-16(WCS)으로 컴파일 할 때는 wchar_t가 된다.)

- 모든 윈도우 API에서 접미사나 접두사로 w, wcs, W 가 붙은 것들은 와이드 문자를 의미한다.

- t, tcs, T 가 붙은 것들은 현재 사용하는 문자 타입을 의미한다.

ex) std::string은 STL의 ANSI문자열 클래스이고, std::wstring은 와이드 캐릭터 클래스다.

- 윈도우에서 WCS, MBCS 문자열 다루는 함수는 버전이 따로 존재한다.

ⓓ 콘솔에서의 유니코드

- 프로젝트에서 어떤 인코딩을 사용할지 가능한 한 빨리 정한 다음, 그 후 일관되게 사용하기만 한다면 실제로 어떤 것을 사용하는지는 별로 중요하지 않다.

STL의 장점

 * STL은 풍부한 기능들을 지원한다.

 * 다양한 플랫폼에서 쓸 수 있는 대체적으로 안정적인 구현들이 존재한다.

 * 거의 모든 C++ 컴파일러는 STL을 표준으로서 지원한다.

STL의 단점

 * STL은 처음에 배우기기 힘들다.

 * 구체적인 목적을 위한 자료구조에 비해 성능이 떨어진다.

 * 대부분의 경우 자체 제작한 자료 구조보다 메모리를 더 많이 먹는다.

 * 동적 메모리 할당을 많이 사용하다.

 * 여러 플랫폼을 지원하는 엔진에서 사용하기 힘들다.

1. 동적 배열과 메모리 할당

  동적 할당은 느리기 때문에 동적 배열은 개발기간에 사용하고 버퍼의 크기를 알게 되면 고정크기 배열로 바꾸어 사용하는 것도 좋다.

2. 연결 리스트

  ⓐ 고려사항

    - 빈 리스트에 첫 요소를 추가하는 경우

    - 현재의 머로 요소 앞에 새 요소를 추가하는 경우

    - 현재의 꼬리 요소 뒤에 새 요소를 추가하는 경우

    - 중간에 요소를 추가하는 경우

  ⓑ 링크 자료구조

template< typename ELEMENT >

struct Link

{

Link<ELEMENT>* m_pPrev;

Link<ELEMENT>* m_pNext;

Link<ELEMENT>* m_pElem;

};

  ⓒ 돌출 리스트 (extrusive list)

    - Link 자료구조와 요소 자료 구조가 완전 별개인 연결리스트 이다.

    - 연결리스트에 요소가 추가될 때면 링크를 하나 새로 할당하고 요소에 대한 포인터 및 다음과 이전 링크에 대한 포인터를 맞게 설정한다.

    - 장점은 한 요소가 동시에 여러 연결리스트에서 포함할 수 있다는 것이다.

    - 단점은 링크 객체를 동적할당 해야한다는 것이다. 링크는 언제나 크기가 같기 때문에 풀할당자를 사용하는 경우가 많다.

  ⓓ 함몰 리스트 (Instrusive list)

    - Link 자료구조가 요소의 자료구조 안에 포함되는 연결 리스트다.

    - 링크 객체를 동적 할당하지 않아도 되는 이점이 있다.

    - Link 안에는 요소를 가리키는 포인터가 있어야 하지만, 상속을 사용하면 없어도 된다.

  ⓓ 머리와 꼬리 포인터 : 순환리스트

    - Head 포인터와 tail 포인터를 가지고 있으면 삭제나 추가 시 복잡해진다.

    - 그러므로 이 두개의 포인터를 m_root포인터로 합치면 순환하는 리스트가 된다.

  ⓔ 단순 연결 리스트

    - 이전을 가리키는 포인터가 없기 때문에 제거 동작은 O(n)이고 이중연결리스트에선 O(1)이다.

    - 리스트의 Head나 Tail에서 제거 동작이 발생하는 경우에는 단순 연결로 메모리를 절약할 수 있다.

3. 사전과 해시 테이블

사전은 키-값 쌍의 테이블이다. 

사전은 대부분 이진트리나 해시테이블을 사용하는다.

이진트리의 검색 연산은 O(logn)이다.

해시 테이블은 키를 정수형태로 변환하고 모듈로(modulo) 연산으로 검색하기 때문에 O(1)이다.

  ⓐ 충돌 : 개방형 해시 테이블과 폐쇄형 해시 테이블

    - 개방형 해시 테이블은 충돌을 해결하기 위해 단순하게 인덱스 하나에 여러개의 키-값 쌍을 저장하는 방식을 쓴다.

    - 구현하기 쉽고 저장할 수 있는 키-값 쌍의 수에도 제약이 없지만 새로운 키-값 쌍을 추가할 때 동적 메모리 할당이 발생한다.

    - 폐쇄형 해시 테이블은 충돌이 발생하면 빈 슬롯을 찾을 때 까지 탐지하는 과정을 반복한다.

    - 구현이 까다롭고 키-값 쌍의 수에 제한이 있다. 하지만 정해진 양만큼의 메모리를 사용하고 동적 메모리 할당이 필요 없다.

  ⓑ 해시 값 계산

    - 해시 값 계산(Hashing)은 임의의 데이터 타입인 키 값을 정수로 부꾼 후 이 정수와 테이블 크기를 모듈로 연산해 테이블에 대한 인덱스를 얻는 과정이다.

    h = H(k)    i = h mod N

    - 해시 테이블의효율성은 해시 함수 품질에 달려 있다. 좋은 해시 함수란 모든 키값을 테이블 전체에 고르게 배분하는 함수이고, 충돌을 최소화 한다.

    - 결정적이어야 한다. 입력이 같으면 그 출력도 같아야 한다.

  ⓒ 폐쇄형 해시 테이블 구현

    - 폐쇄형 해시 테이블 상식에서는 키-값 쌍을 각 테이블 항목마다 하나씩 연결 리스트에 저장하는것이 아니라 테이블 안에 직접 저장한다.

    - 이렇게 되면 해시 테이블을 사용할 메모리 양을 미리 정확히 알 수 있다.

    - 충돌이 일어나서 탐자 과정을 할때 가장 간단한 방식은 선형 탐지다. 충돌이 일어난 곳 부터 하나씩 탐지하는 것이다.

    ( 요소들이 뭉치게 된다.)

    - 그래서 이차 탐지 알고리즘을 쓰는데 하나씩이 아니라 i의 제곱씩 늘려가며 탐색한다.

    - 폐쇄형 해시는 크기를 소수로 하는 것이 좋다. 이차 탐색을 했을 때 고르게 배치 할 수 있다.

소프트 웨어의 성능은 어떤 알고리즘을 썼느냐도 중요하지만 어떻게 RAM을 잘 활용했는지도 영향을 받는다.

메모리가 성능에 영향을 끼치는 형태는 다음 두가지가 있다.

* 동적 메모리 할당은 느리다. 동적 메모리할당을 피하거나, 할당비용을 줄일 수 있는 메모리 할당자를 직접 만들어야 한다.

* 메모리를 효율적으로 배치해되 있을수록 속도가 빠르다.

1. 동적 메모리 할당 최적화

 동적 메모리 할당이 느린 이유

  * 힙 할당자는 범용 목적이기 때문에 이렇게 하면 관리하는 부가적인 비용이 들기 때문이다.

  * malloc(), free()를 호출할 때 대부분 운영체제 에서는 먼저 유저 모드에서 커널 모드로 컨텍스트 전환을 하고, 필요한 동작을 수행한 후 다시 프로그램으로 컨텍스트 전환을 해야한다.

 사용자 제작 할당자가 빠른 점

  * 미리 할당된 블록을 이용할 수 있다. 즉, 유저모드에서만 처리하기 때문에 컨텍스트 스위칭이 일어나지 않는다.

  * 사용 패턴을 예측할 수 있기 때문에 범용 힙 할당자에 비해 훨씬 효율적으로 동작한다.

2. 커스텀 할당자의 종류

  ⓐ 스택 할당자 - 데이터를 쌓아가며 할당하고 그러므로 해제할땐 순서대로 해제해야 한다. 해제 시 해제하고 할당 된만큼 꼭대기의 주소를 내려줘야 한다.

  ⓑ 풀 할당자 - 개별 원소들의 크기에 정확히 배수가 되는 큰 메모리 블록을 할당하는 것이다. 처음에는 모든 풀의 원소들이 사용 가능 리스트에 들어가 있다가 할당 요청이 오면 제일 처음 원소를 가져와서 리턴한다.

  ⓒ 정렬된 할당자 - 실제 요청된 것보다 조금 큰 메모리를 할당하고 블록의 주소를 살짝 위로 조정해서 정렬을 맞춘 다음 조정된 주소를 리턴한다.

  ⓓ 단일 프레임 할당자 - 메모리를 해제하지 않고 한 프레임 마다 메모리 블록의 가장 아래로 꼭대기 포인터를 초기화 한다. 프레임 진행 중 할당이 일어나면 블록의 위방향으로 진행한다.

3. 메모리 단편화

 - 메모리가 충분히 있음에도 연속되 있지 않아서 할당에 실패한다.

해결 방안

 ⓐ 스택할당자와 풀할당자를 사용한다.

   - 이 두 할당자는 메모리 단편화를 겪지 않는다.

 ⓑ 조각 모음과 재배치

   - 할당된 메모리들을 메모리 구멍을을 메워가며 앞으로 당긴다.

   - 하지만 메모리를 가리키고 있는 포인터가 있을 경우 문제가 생길 수 있으니 메모리들을 옮기면서 이 과정 또한 다시 재배치 해주어야 한다.

    (스마트 포인터가 스스로 재배치를 하게 하거나 핸들을 사용한다.)

   - 조각 모음이 한 프레임에 모든 블록을 옮긴다면 속도가 굉장히 느릴 것이다 그러므로 한프레임당 8개나 16개 정도 갯수를 조정하는 것이 좋다.

4. 캐시 일관성

 시스템이 메인 RAM에 접근하는 일은 시작부터 끝까지 항상 수천 프로세스 주기가 걸리기 때문에 언제나 느리다.

 대게 수십주기, 어떤 경우는 한주기만에 끝나기도 하는 CPU 레지스터 접근과 비교하면 엄청난 차이다.

 메인 RAM에서 읽고 쓰는 평균적인 비용을 줄이기 위해 오늘날의 프로세서는 고성능 메모리 캐시를 이용한다.

 캐시는 특수한 형태의 메모리로 CPI가 읽고 쓰는 속도가 메인 RAM 보다 훨씬 빠르다.

 메모리 캐싱의 기본적 원리는 메인 RAM의 영역을 처음 읽을 때, 작은 메모리 조각을 고성능 캐시에 읽어 들이는 것이다.

 이 메모리 조각을 캐시라인이라고 하고 보통 8바이트에서 512바이트 사이의 값이다.

 요청한 데이터가 캐시에 있을 땐 캐시에서 바로 읽어 들이고 그렇지 않으면 메인 RAM에 접근한다. 이 경우를 캐시 미스라고 한다.

 캐시 미스가 발생하면 캐시라인을 다시 읽어 들일 때 까지 프로그램은 기다려야 한다.

 RAM에 데이터를 쓰거나 읽어야 하기 때문에 캐시 미스를 완전히 피할 수는 없다.

  ⓐ 명령어 캐시(instruction I 캐시) 데이터(Data D 캐시) 캐시

    - 명령어 캐시는 실행 파일의 명령어 코드가 실행되기 전에 미리 불러오는데 쓰인다.

    - 데이터 캐시는 데이터를 메인 RAM에 읽고 쓰는 속도를 빠르게 하는 데 쓰인다.

  ⓑ 데이터 캐시 미스를 피하는 가장 좋은 방법은 데이터를 잘개 쪼개어 연속적인 블록으로 배치하고 순서대로 접근하는 것이다.

  ⓒ 명령어 캐시 미스를 피하는 방법은 코드의 메모리에서의 모양은 데이터와 링커에 달려 있다 그래서 다음위 규칙을 이용하면 좋다.

    - 함수 하나를 나타내는 기계어 코드는 항상 메모리에서 연속적이다.

      (인라인 함수는 예외)

    - 번역 단위의 소스코드에 나오는 순서대로 함수들이 메모리에 배열된다.

    - 같은 번역 단위 안에 있는 함수들은 거의 대부분 메모리에서 연속적으로 놓인다.

      ( 링커는 여러 번역 단위를 컴파일한 결과물들을 서로 섞어서 놓지 않는다.)

  * 성능이 중요한 코드는 가능한 한 기계어 명령어 수가 적어야 한다.

  * 성능에 결정적인 영향을 끼치는 코드에서는 함수 호출을 피애햐 한다.

  * 함수를 반드시 호출해야 하는 경우에는 가능한 현재 함수와 가까운 곳에 배치해야 한다. 다른 번역 단위에 있는 함수를 호출하면 안된다.( 거리를 보장할 수 없기 때문)

  * 인라인 함수를 사용할 때는 조심해야 한다. 인라인 함수는 코드의 크기를 크게 할하기 때문에 결정적 영향을 끼치는 코드가 캐시에 한번에 다 못 들어 가는 경우가 생길 수 있다.

시작 하는 순서는 하부시스템의 연관성에 따라 묵시적으로 결정된다.

종료하는 순서는 대개 반대로 종료된다.

1. C++ 정적 초기화 순서

  * C++ 에선 정적 객체와 전역 객체가 초기화 되는 순서가 정해져 있지 않다.

    (만약 초기화 순서를 지정할 수 있었다면 싱글턴 클래스 인스턴스를 전역으로 정의해 동적 메모리 할당을 하지 않아도 됐을 것이다.)

2. 주문형 생성

 활용할 수 있는 C++의 트릭이 하나 있는데, 함수 안에서 선언된 정적 변수는 main() 실행 전이 아니라 해당 함수가 처음으로 호출될 때 생성된다는 점이다.

class RenderManager

{

public :

static RenderManager& get()

{

static RenderManager sSingleton;

return sSingleton;

}

}

그리고 동적할당을 이용한 방법

static RenderManager& get()

{

static RenderManager* gpSingleton = NULL;

if ( gpSingleton == NULL)

{

gpSingleton = new RenderManager;

}

ASSERT( gpSingleton );

return *gpSingleton;

}

이 방법을 이용한 간단한 방법은 생성자와 소멸자에선 아무것도 하지 않으며

생성하는 함수와 종료하는 함수를 따로 두어 전역으로 선언한 뒤 Main에서 시작할때 순서대로 실행하는 것이다. 종료도 마찬가지로 반대로 실행한다.

장점

  * 방식이 단순하고 구현하기 쉽다.

  * 명확하다. 코드를 보기만 하면 바로 시작 순서를 알아낼 수 있다.

  * 디버깅하고 유지하기 쉽다. 제때 시작이 안되거나 너무 일찍 시작되는 것이 있으면 코드 한 줄만 이동하면 된다.