왜 std :: deque의 효율성이 그렇게 좋지 않습니까?

std :: deque를 사용하고 싶었지만 소비 된 오버 헤드 메모리가 너무 과도하게 보입니다. 내가 뭔가 잘못하고 있니? (32 비트 Windows 시스템에서)왜 std :: deque의 효율성이 그렇게 좋지 않습니까?

#include "windows.h" 
#include "psapi.h" 

#include <iostream> 
#include <vector> 
#include <queue> 

int main (int, char* []) 
{ 
    PROCESS_MEMORY_COUNTERS pm; 
    GetProcessMemoryInfo(GetCurrentProcess(), &pm, sizeof(pm)); 
    size_t mem1 = pm.WorkingSetSize; 

    std::vector<int> v(10000000); 

    GetProcessMemoryInfo(GetCurrentProcess(), &pm, sizeof(pm)); 
    size_t mem2 = pm.WorkingSetSize; 

    std::deque<int> q(10000000); 
    GetProcessMemoryInfo(GetCurrentProcess(), &pm, sizeof(pm)); 
    size_t mem3 = pm.WorkingSetSize; 

    std::cout << mem2 - mem1 << std::endl; 
    std::cout << mem3 - mem2 << std::endl; 

    return 0; 
}

출력 :

40087552 
72564736

보너스 질문 : 왜 MEM2 - MEM1 정확히 40000000?

출처

2013-05-24 MarkB

당신은 올바르게했습니다. 마이크로 소프트가 잘못 했어. –

@MooingDuck Explain. –

@KonradRudolph : 음, Microsoft가 코드를 소유하고 있습니다. Dinkumware가 먼저 작성했습니다.'deque'는 GCC의 512에 비해 16 바이트의 블록을 사용합니다. 아주 작은 세트의 경우 오버 헤드가 훨씬 적습니다. 중형 또는 대형 세트의 경우 ... –

deques가 연속 메모리 블록에 할당되어 있다고 생각하지 않습니다. (http://www.cplusplus.com/reference/deque/deque/)에서 :

벡터와 deques 모두 매우 유사한 인터페이스를 제공하고 유사한 목적을 위해 사용할 수 있지만 매우 다른 방법으로 내부적으로 두 작업 : 벡터는 가끔 재 할당해야 할 하나의 배열을 사용하는 동안 확장을 위해 deque의 요소는 저장소의 다른 부분에 분산 될 수 있으며 컨테이너는 필요한 정보를 내부적으로 유지하여 일정 시간 및 균일 한 순차 인터페이스로 요소에 직접 액세스 할 수 있습니다. 따라서, deques는 벡터보다 내부적으로 조금 복잡하지만, 특정 상황에서는 더욱 효율적으로 성장할 수 있습니다. 특히 재 할당이 더 비쌉니다.

출처

2013-05-24 20:39:12

앞에서 언급 한 바와 같이 deque은 인접한 메모리 블록에 할당되지 않습니다. 메모리 블록을 추적하려면 데이터를 보관해야합니다. 세부 사항은 구현에 따라 다르지만 일부 세부 사항은에서 찾을 수 있습니다 STL internals: deque implementation

작업 세트는 사용중인 실제 메모리의 양입니다. working set 설명서.

프로세스의 작업 집합은 현재 실제 메모리에 상주하는 프로세스의 가상 주소 공간에있는 페이지 집합입니다.

일부 메모리가 디스크로 페이지 아웃되어 discrepency가 추가 될 가능성이 있습니다.

mem2 - mem1이 40000000과 같지 않은 몇 가지 이유가 있습니다. 간단히 std::vector 개체에 추가 멤버 변수가있을 수 있습니다. 크기 변수를 추적하고 반복자를 시작하고 끝낼 수 있습니다. 또 다른 이유는 Windows 힙 또한 메모리를 추적해야하기 때문에 메모리가 필요합니다. 현실에서 Managing Heap Memory

에서

는하지만, 힙 관리자는 힙 메모리를 관리하기위한 추가 메모리가 필요합니다. 따라서 요청 된대로 100 바이트 만 할당하는 대신 각 특정 메모리 덩어리를 관리하기위한 공간을 할당합니다. 메모리 유형 및 할당 크기에 따라이 추가 메모리의 크기가 결정됩니다.

당신은 int* v = new int[10000000];와 std::vector<int>를 대체하여, 이것을 시도 할 수 있습니다 당신은 메모리 차이가 40000000 바이트를 초과 것을 볼 수 있습니다.

출처

2013-05-24 21:02:29 Steve

사실상 연결된 목록은 사용할 수 없습니다. 왜냐하면'deque'는 랜덤 액세스 반복자를 필요로하기 때문입니다. –

@BenVoigt가 수정 해 주셔서 감사합니다. 나는 대답을 수정했습니다. – Steve

@MooingDuck 이것은'vector'를 생성하기 직전에'mem1'을 측정 한 후 곧바로'mem2'를 측정함으로써 고려됩니다. 나는 그 구성 요소 중 하나에 사용 된 메모리가 그 당시에 변경되었을 것이라고 생각하지 않습니다. 내가 놓친 게 아니라면? – Steve

왜 std :: deque의 효율성이 그렇게 좋지 않습니까?

답변

관련 문제