std :: map 표준 할당 자 성능 대 블록 할당 자

Question

std :: list, std :: set, std :: multi_set, std :: map과 같은 STL 컨테이너의 표준 할당자인 C++ 최적화 쿡북을 읽었습니다 , std :: multi_map은 더 좋은 수행자 블록 할당 자으로 대체 될 수 있습니다.

블록 할당자는 높은 성능, 낮은 단편화 및 효율적인 데이터 캐싱을 제공합니다.

웹에서 표준보다 빠른 FSBAllocator를 찾았습니다. http://warp.povusers.org/FSBAllocator/

나는 표준 : :지도를 시도하고 빠른 실제로 것으로 보인다 찾았지만, 내 질문은 STL 구현이 특정 할당에 비해 너무 느릴 수있는 방법이며, 다른 할당의 단점이 무엇했습니다 이식성과 견고성 측면에서 표준보다 내 코드는 다양한 아키텍처 (win32, osx, linux)에서 컴파일해야합니다. 누군가가 그런 종류의 고정 크기 블록 할당 자에 대한 경험이 있습니까?

Answer 1

블록 할당자는 무료 저장소/힙에 대해 하나의 큰 할당을 수행 한 다음이 메모리를 내부적으로 청크로 분할합니다. 한 가지 단점은이 덩어리 (큰 크기가 필요하고 종종 유스 케이스별로 사용자가 지정해야 함)를 똑같이 할당하므로 모든 메모리를 사용하지 않아도 그 메모리가 묶여 있다는 것입니다. 둘째, 표준 메모리 할당자는 new/delete의 맨 위에 만들어지며, malloc/free의 맨 위에 만들어진다. malloc/free가 모든 상황에서 스레드 안전성이 보장되는지는 기억하지 않지만 일반적으로 그렇습니다.

마지막으로 블록 할당자가 정상적으로 작동하는 이유는 표준 할당자가 제공하지 않는 정보를 갖고 있으며 매우 다양한 사용 사례를 다루지 않아도되기 때문입니다. 예를 들어, std::map< int, int >()을 수행하고 1MB를 할당했다면 화가 났을 것입니다. 그러나 std::map< int, int, std::less<int>, block_alloc< 1024 * 1024 > >()을 수행하면 예상 할 수 있습니다. 표준 할당 자들은 블럭으로 할당하지 않고, 새로운 메모리를 통해 새로운 메모리를 요구하고, 새로 문맥을 전혀 갖지 않습니다. 임의의 크기의 메모리 요청을 가져오고 반환 할 인접 바이트 수를 찾아야합니다. 대부분의 구현은 여러 배수로 유지되는 일련의 메모리 영역을 보유하고 있습니다 (예 : 4 바이트에 대한 요청이 많아지기 때문에 4 바이트에 대한 요청이 많을 수도 있음). 요청이 짝수 배가 아닌 경우 공간을 낭비하지 않고 조각을 생성하지 않고 좋은 청크를 반환하는 것이 더 어려워집니다. 기본적으로 임의의 크기에 대한 메모리 관리는 상수 시간, 분절화, 스레드 안전성 등에 가까울 경우 매우 어렵습니다.

Boost pool allocator 설명서에는 좋은 블록 할당자가 작동하는 방법에 대한 좋은 정보가 있습니다.