캐쉬 미스와 페이지 폴트를 줄이는 방법, Array

MSDN에서 최적화된 코딩 방법에 대한 글을 일부 번역한 것입니다. 

처리속도가 빠른 코드를 만들기 위해서는 여러 방면으로 어플리케이션을 분석하고, 그 코드가 시스템과 어떤 상관관계를 취하고 있는지 조사 할 필요가 있습니다. 여기서는 코드의 타임 크리티컬한 부분의 퍼포먼스를 향상 시키기 위한, 몇가지의 코딩 테크닉에 대해서 설명합니다. 

타임 크리티컬한 코드를 고속화 할려면 이하의 점을 확인합니다. 
• 프로그램의 어느 부분을 고속화 해야되는가 
• 코드의 사이즈와 실행속도은 어느 정도인가. 
• 새로운 기능에 관계되는 코스트는 어느 정도인가 
• 처리를 완료 할려면 최소한 어느 정도의 작업이 필요한가 

코드 퍼포먼스에 관한 정보를 수집 할 때에는 퍼포먼스 모니터(perfmon.exe)를 사용합니다. 





캐쉬 미스와 페이지 폴트 

내부 캐쉬 및 외부 캐쉬를 히트 하지 않은 경우도, 페이지 폴트(프로그램 명령이랑 데이터를 2차원 스트레이지로 검색을 하는 것)가 발생한 경우와 같이 프로그램의 퍼포먼스가 저하된다. 

CPU 캐쉬가 히트 하지 않으면 10 ~ 20 클락 분의 로스가 발생한다고 계산된다. 
외부 캐쉬가 히트 하지 않으면 20 ~ 40 클락 분의 로스가 생긴다. 페이지 폴트가 발생한 경우는 프로세스가 매초 5억의 명령어를 처리하고, 1회 페이지 폴트로 2미리초가 걸린다고 가정하면, 100만 클락 분의 로스가 생긴다. 이를테면, 프로그램을 고속화 할려면, 캐쉬의 미스 히트와 페이지 폴트를 줄이는 세세한 주의를 줄 필요가 있다. 

프로그램이 느린 원인의 하나로써, 필요 이상으로 페이지 폴트랑 캐쉬의 미스 히트가 발생하고 있다고 생각 될 수 있다. 이것을 피하려면, 데이터 참조의 국소성(局所性 )이 높은 높은 데이터 구조체를 사용해야 되므로 관련이 있는 데이터를 모아 두는 것이 중요하다. 
일견 좋게 보이는 데이터 구조체라도, 데이터 참조의 국소성이 낮기 때문에 퍼포먼스가 나빠지게 되는 경우도 있고, 역으로 너무 나쁘게 보이는 데이터 구조체라도 데이터 요소의 국소성이 높기 때문에 고속으로 되는 것도 있다. 2개의 예를 다음에 나타내면. 

동적 메모리 할당으로 만들어진 링크드 리스트는 프로그램의 퍼포먼스를 저하 시키는 원인이 된다. 리스트 내의 아이템을 참조하기도 하고, 리스트 최후까지 이동하는 경우, 링크를 되돌아 갈 때마다 캐시의 미스 히트랑 페이지 폴트가 발생 하는 경우가 있기 때문이다. 실제, 단순한 배열로 구현딘 리스트쪽이 캐시가 유효하게 동작하여 페이지 폴트 회수가 낮기 때문에, 엄청나게 고속이다. 배열의 사이즈를 확장할 때마다 여분의 처리가 필요하다는 것을 참고하여도, 역시 이쪽이 고속이다. 

동적 메모리 할당으로 만들어진 링크드 리스트를 사용한 해쉬 테이블도 퍼포먼스를 저하시키는 원인이 된다. 이와 같은 링크드 리스트에 해쉬 테이블의 내용만을 저장하고 있는 경우라도, 예상이상을 퍼포먼스가 저하하는 경우도 있다. 실제, 배열을 사용한 단순한 리니아 서치 쪽이 최종적으로는 고속이라는 예도 있다. 배열 베이스의 해쉬 테이블(일명 “클로즈 해쉬 법)은 안 좋게 보이지만 퍼포먼스적으로는 뛰어난 방법이다. 



MFC 라이브러리와 클래스 라이브러리 

MFC를 사용하면, 코드의 기술이 간단하게 됩니다. 타임 크리티컬한 코드를 기술하는 경우, 클래스에 의한 오버헤드가 생길 가능성이 있으므로 주의가 필요합니다. 타임 크맅컬한 부분에서 사용하는 MFC 코드를 조사하여 그 코드가 요구하는 퍼포먼스에 합당한지 어떨지 판단한다. MFC 클래스 및 함수에 대한 주의점을 아래에 나타냅니다. 

• CString MFC는 C 런타임 라이브러리를 호출하여 CString의 메모리를 동적으로 할당합니다. 통상, CString은 동적으로 할당돤 문자열과 같은 역할을 합니다. CString은 동적으로 할당되어 그 외의 문자열과 같이 동적 활당하여 할당 해제 때에 오버헤드가 발생합니다. 많은 경우, 스택에서 단순한 chat 형의 배열을 잡으면, 같은 처리를 고속화 할 수 있습니다. CString은 정수 문자열의 저장에 사용하지 말아야 됩니다. 정수문자열에서는 const char*를 사용합니다. CString 오브젝트를 사용하는 처리에는 보통 오버헤드가 생김으로 런 타임 라이브러의 문자열 함수를 사용한 쪽이 고속화 할 수 있는 경우가 있습니다. 

• CArray는 통상의 배열에는 없는 유연성이 있지만 프로그램에 의해 그 유연성이 필요하지 않은 경우도 있습니다. 배열의 고유의 제한을 알고 있는 경우는 사이즈 고정형의 글로벌 배열을 사용 할 수 있습니다. CArray를 사용하는 경우는 CArray::SetSize를 사용하여 사이즈와 재 할당시의 증가 요소수를 지정합니다. SetSize를 사용하지 않으면, 요소를 추가 할 때마다 배열의 재 할당과 복사를 하기 때문에 실행속도가 저하되고 메모리가 단편화 합니다. 또 배열에 아이템을 삽입하면, CArray는 메모리 내의 후속 아이템을 이동하기 때문에 배열의 학장이 필요로 하는 경우가 있습니다. 이런 처리는 캐쉬의 미스 히트와 페이지 폴트의 원인이 됩니다. MFC에서 사용하는 코드를 조사하여 퍼포먼스의 향상에 무엇이 필료한지 확인하세요. 예를 들면, CArray는 템플리트이므로 특정의 형에 대해서 CArray의 특별한 형식을 지정 할 수 있습니다. 

• CList는 더블 링크드 리스트 이므로, 리스트의 선두, 꼬리, 및 지정된 위치로의 요소 삽입이 고속입니다. 정확히 값이랑 인덱스에 의해 요소를 검색할 때에는 연속적인 검색이 필요합니다. 이것은 리스트가 길어지면 시간이 걸립니다. 코드에 더블 링크드 리스트가 필요하지 않은 경우는 CList를 사용할 필요가 있을지 어떨지 재 검토해주세요. 연속 리스트를 사용하면, 여분의 포인터 때문에 메모리를 소비 할 일이 없고, 포인터의 갱신에 의한 오버헤드가 생기는 일도 없습니다. 여분 메모리의 소비자체는 그다지 큰 문제는 없습니다만, 캐쉬의 미스 히트랑 페이지 디폴트를 증가시키는 원인이 됩니다. 

• IsKindOf 이 함수는, 많은 함수 호출을 하는 것에 의해, 다른 데이터 영역에 다양한 메모리 접근을 합니다. 다시 말해, 데이터 참조가 국소적이지 않습니다. 이 함수는 디버그 빌드에서는 편리하여 ASSERT 호출등에서 사용됩니다. 릴리즈 빌드에서는 사용은 피해 주십시오 

출처 : http://coder.egloos.com/m/2804749