std :: unordered_map 매우 높은 메모리 사용량

Question

어제 unordered_map을 사용하려고 시도했는데이 코드는 사용 된 메모리 양을 혼란스럽게합니다.

typedef list<string> entityId_list; 
struct tile_content { 
    char cost; 
    entityId_list entities; 
}; 
unordered_map<int, tile_content> hash_map; 

for (size_t i = 0; i < 19200; i++) { 
    tile_content t; 
    t.cost = 1; 
    map[i] = t; 
} 

이 코드 부분은 모두 MS VS2010에서 디버그 모드로 컴파일되었습니다. 내 작업 관리자에서 본 것은 약 1200kb의 "깨끗한"프로세스 였지만 hash_map을 채운 후 8124KB의 메모리를 사용합니다. unordered_map의 정상적인 동작입니까? 왜 그렇게 많은 메모리가 사용 되었습니까?

Answer 1

은 unordered_map 구조는 조회를하게 추가, 삭제하는 방법으로 많은 수의 개체를 유지하도록 설계 orderless 효율적으로 통과된다. 소규모 데이터 구조에 메모리 효율적인 것은 아닙니다. 크기 조정과 관련된 벌칙을 피하기 위해 처음 생성 될 때 많은 해시 체인 헤드를 할당합니다.

Answer 2

이 반드시 해시 맵이 너무 많은 메모리를 사용하지만, 프로세스는 OS에서 해당 많은 메모리를 요구 한 것을 의미하지 않는다.

이 메모리는 프로그램에 의한 malloc/new 요청을 만족시키는 데 사용됩니다. 일부 (또는 대부분, 나는 이것에 대해 확신하지 못한다) 메모리 할당자는 효율을 위해 그 시점에서 필요한 것보다 더 많은 메모리를 OS에서 필요로한다.

내가 perftools 같은 메모리 프로파일 러를 사용하는 것과 unordered_map도에 의해 사용되는 메모리 양을 알아야합니다.

Answer 3

약 20MB 개체의 경우 약 6MB이므로 개체 당 300 바이트입니다. 해시 테이블의 크기가 현재 항목보다 몇 배 더 많은 버킷을 가질 수 있다고 가정하면 각 버킷 자체가 충돌 객체 목록 또는 벡터에 대한 포인터가 될 수 있으며 모든 힙 할당은 아마도 가장 가까운 값으로 반올림되었을 것입니다 2의 힘, 그리고 당신은 약간의 부풀게를 생성 할 수있는 디버그를 가지고 있습니다.

어쨌든, 당신은 디버그 빌드의 ;-P에서 아무것도의 메모리 나 CPU의 효율성에 대한 공감을 얻을 않을거야. Microsoft는 사용자가 좋아하는 슬롭을 주입 할 수 있으며 사용자는 성능과 관련하여 기대할만한 권리가 없습니다. 최적화 된 빌드에서 문제가 있다고 판단되면 이야기 할 내용이 있습니다.

일반적으로 size()으로 크기를 조정하는 방법은 매우 중요하지만 상대적으로 작은 정렬되지 않은지도가 많은 프로그램이 어떻게 생성되는지 궁금해하는 것이 좋습니다. 특정 벡터 아래에있는 무차별 한 검색, 정렬 된 벡터에서의 이진 검색 또는 이진 트리가 정렬되지 않은 맵보다 성능이 좋을뿐만 아니라 더 많은 메모리를 효율적으로 사용할 수 있다는 점에 유의해야합니다.