std :: unordered_map이 메모리를 해제하지 않습니다.

Question

MSVC14 (VS2015)에서 std::unordered_map의 이상한 동작을 관찰하고 있습니다. 다음 시나리오를 고려하십시오. 정렬되지 않은 맵을 생성하고 상당한 양의 메모리를 소비하는 더미 구조체로 채우면 1Gb, 전체 100k 요소가 삽입됩니다. 그런 다음지도에서 요소를 삭제하기 시작합니다. 당신이 요소의 절반을 삭제했다고 가정하면, 절반의 메모리가 해제 될 것이라고 예상 할 수 있습니다. 권리? 잘못된! 맵의 요소 수가 임계 값을 넘었을 때 메모리가 해제 된 것을 볼 수 있습니다. 제 경우에는 1443 요소였습니다.
VirtualAllocEx 또는 HeapAlloc을 사용하여 OS에서 큰 청크를 할당하는 것은 malloc 최적화라고 말할 수 있습니다. 실제로 최적화가 정책을 지정하고 이후에 이미 할당 된 메모리를 다시 사용할 수 있도록하기 위해 시스템에 메모리를 해제하지 않습니다.
allocate_shared에 대한 사용자 지정 할당자를 사용한이 경우를 제거하기 위해 트릭을하지 않았습니다. 그래서 주요한 질문은 왜 일어나는 것이며, 무엇이 "compact"메모리로 수행 할 수 있습니까? unordered_map에 의해 사용됩니까?

#include <windows.h> 
#include <memory> 
#include <vector> 
#include <map> 
#include <unordered_map> 
#include <random> 
#include <thread> 
#include <iostream> 
#include <allocators> 

HANDLE heap = HeapCreate(0, 0, 0); 
template <class Tp> 
struct SimpleAllocator 
{ 
    typedef Tp value_type; 
    SimpleAllocator() noexcept 
    {} 
    template <typename U> 
    SimpleAllocator(const SimpleAllocator<U>& other) throw() 
    {}; 
    Tp* allocate(std::size_t n) 
    { 
     return static_cast<Tp*>(HeapAlloc(heap, 0, n * sizeof(Tp))); 
    } 
    void deallocate(Tp* p, std::size_t n) 
    { 
     HeapFree(heap, 0, p); 
    } 
}; 
template <class T, class U> 
bool operator==(const SimpleAllocator<T>&, const SimpleAllocator<U>&) 
{ 
    return true; 
} 
template <class T, class U> 
bool operator!=(const SimpleAllocator<T>& a, const SimpleAllocator<U>& b) 
{ 
    return !(a == b); 
} 

struct Entity 
{ 
    Entity() 
    { 
     _6 = std::string("a", dis(gen)); 
     _7 = std::string("b", dis(gen)); 
     for(size_t i = 0; i < dis(gen); ++i) 
     { 
      _9.emplace(i, std::string("c", dis(gen))); 
     } 
    } 
    int _1 = 1; 
    int _2 = 2; 
    double _3 = 3; 
    double _4 = 5; 
    float _5 = 3.14f; 
    std::string _6 = "hello world!"; 
    std::string _7 = "A quick brown fox jumps over the lazy dog."; 
    std::vector<unsigned long long> _8 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0}; 
    std::map<long long, std::string> _9 = {{0, "a"},{1, "b"},{2, "c"},{3, "d"},{4, "e"}, 
    {5, "f"},{6, "g"},{7, "h"},{8, "e"},{9, "j"}}; 
    std::vector<double> _10{1000, 3.14}; 
    std::random_device rd; 
    std::mt19937 gen = std::mt19937(rd()); 
    std::uniform_int_distribution<size_t> dis = std::uniform_int_distribution<size_t>(16, 256); 
}; 

using Container = std::unordered_map<long long, std::shared_ptr<Entity>>; 

void printContainerInfo(std::shared_ptr<Container> container) 
{ 
    std::cout << std::chrono::system_clock::to_time_t(std::chrono::system_clock::now()) 
     << ", Size: " << container->size() << ", Bucket count: " << container->bucket_count() 
     << ", Load factor: " << container->load_factor() << ", Max load factor: " << container->max_load_factor() 
     << std::endl; 
} 

int main() 
{ 
    constexpr size_t maxEntites = 100'000; 
    constexpr size_t ps = 10'000; 
    stdext::allocators::allocator_chunklist<Entity> _allocator; 
    std::shared_ptr<Container> test = std::make_shared<Container>(); 
    test->reserve(maxEntites); 

    for(size_t i = 0; i < maxEntites; ++i) 
    { 
     test->emplace(i, std::make_shared<Entity>()); 
    } 

    std::random_device rd; 
    std::mt19937 gen(rd()); 
    std::uniform_int_distribution<size_t> dis(0, maxEntites); 
    size_t cycles = 0; 
    while(test->size() > 0) 
    { 
     size_t counter = 0; 
     std::cout << "Press any key..." << std::endl; 
     std::cin.get(); 
     while(test->size() > 1443) 
     { 
      test->erase(dis(gen)); 
     } 
     printContainerInfo(test); 
     std::cout << "Press any key..." << std::endl; 
     std::cin.get(); 
     std::cout << std::endl; 
    } 
    return 0; 
} 

상황이 지금까지 시도 코드 : 부하 계수가 어떤 임계 값에 도달하면 /재탕 크기를 조정하는 것을 시도하십시오 - 제전 while에서 나던 때 그런 다음이

if(test->load_factor() < 0.2) 
{ 
    test->max_load_factor(1/test->load_factor()); 
    test->rehash(test->size()); 
    test->reserve(test->size()); 
    printContainerInfo(test); 
    test->max_load_factor(1); 
    test->rehash(test->size()); 
    test->reserve(test->size()); 
} 

같은 것을 추가 임시 컨테이너 만들기, 남은 항목 복사/이동, 원래 항목 지우기, temp에서 원본으로 복사/이동과 같은 무언가를 시도하십시오. 이

if(test->load_factor() < 0.2) 
{ 
    Container tmp; 
    std::copy(test->begin(), test->end(), std::inserter(tmp, tmp.begin())); 
    test->clear(); 
    test.reset(); 
    test = std::make_shared<Container>(); 
    std::copy(tmp.begin(), tmp.end(), std::inserter(*test, test->begin())); 
} 

같은 것을 마지막으로, allocate_shared와 shared_ptr를 교체하고 그것에 SimpleAllocator 인스턴스를 전달합니다.
또한 std::unordered_map'svector (의 msvc stl 구현은 list 및 vector을 기반으로 함)에 std::vector::shrink_to_fit을 호출하는 것처럼 여기 저기에 STL 코드를 수정 했으므로 작업하지 못했습니다.

EDIT001 : 신자가 아닌 모든 사람들에게. 다음 코드는 이전 코드와 다소 차이가 있지만 unordered_map 대신 std::vector<Entity>을 사용합니다. 은 OS가 회수 한입니다.

#include <memory> 
#include <vector> 
#include <map> 
#include <random> 
#include <thread> 
#include <iostream> 

struct Entity 
{ 
    Entity() 
    { 
     _6 = std::string("a", dis(gen)); 
     _7 = std::string("b", dis(gen)); 
     for(size_t i = 0; i < dis(gen); ++i) 
     { 
      _9.emplace(i, std::string("c", dis(gen))); 
     } 
    } 
    int _1 = 1; 
    int _2 = 2; 
    double _3 = 3; 
    double _4 = 5; 
    float _5 = 3.14f; 
    std::string _6 = "hello world!"; 
    std::string _7 = "A quick brown fox jumps over the lazy dog."; 
    std::vector<unsigned long long> _8 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0}; 
    std::map<long long, std::string> _9 = {{0, "a"}, {1, "b"}, {2, "c"}, {3, "d"}, {4, "e"}, 
              {5, "f"}, {6, "g"}, {7, "h"}, {8, "e"}, {9, "j"}}; 
    std::vector<double> _10{1000, 3.14}; 
    std::random_device rd; 
    std::mt19937 gen = std::mt19937(rd()); 
    std::uniform_int_distribution<size_t> dis = std::uniform_int_distribution<size_t>(16, 256); 
}; 

using Container = std::vector<std::shared_ptr<Entity>>; 

void printContainerInfo(std::shared_ptr<Container> container) 
{ 
    std::cout << std::chrono::system_clock::to_time_t(std::chrono::system_clock::now()) 
       << ", Size: " << container->size() << ", Capacity: " << container->capacity() << std::endl; 
} 

int main() 
{ 
    constexpr size_t maxEntites = 100'000; 
    constexpr size_t ps = 10'000; 
    std::shared_ptr<Container> test = std::make_shared<Container>(); 
    test->reserve(maxEntites); 

    for(size_t i = 0; i < maxEntites; ++i) 
    { 
     test->emplace_back(std::make_shared<Entity>()); 
    } 

    std::random_device rd; 
    std::mt19937 gen(rd()); 
    size_t cycles = 0; 
    while(test->size() > 0) 
    { 
     std::uniform_int_distribution<size_t> dis(0, test->size()); 
     size_t counter = 0; 
     while(test->size() > 0 && counter < ps) 
     { 
      test->pop_back(); 
      ++counter; 
     } 
     ++cycles; 
     if(cycles % 7 == 0) 
     { 
      std::cout << "Inflating..." << std::endl; 
      while(test->size() < maxEntites) 
      { 
       test->emplace_back(std::make_shared<Entity>()); 
      } 
     } 
     std::this_thread::sleep_for(std::chrono::seconds(1)); 
     printContainerInfo(test); 
     std::cout << std::endl; 
    } 
    return 0; 
} 

Answer 1

Microsoft에 프리미엄 지원 티켓을 여는 즉시 다음 답변을 얻었습니다. 그것의 대부분은 우리가 이미 알았지 만, 우리가 고려하지 않은 부분에 있습니다.윈도우 메모리에서

1. 우리는 당신이 삭제 호출 한 후 RtlHeapFree를 호출 스트레이트, 어떠한 캐싱이없는 STL에서
2. 페이지
의 형태로 힙에 할당
3. 당신이 볼 것은 윈도우 관리하는 방법입니다 힙
4. 삭제할 항목을 표시하면 메모리가 부족한 OS로 되돌릴 수 없으므로 나중에 의 메모리를 다시 할당하는 비용이 과정 인
5. 이것은 모든 힙 알고리즘이 작동하는 방법입니다.
6. 고려해야 할 또 다른 사항은 다음과 같습니다. 삭제하려는 값이 페이지 전체에 퍼지면 페이지 내의 모든 값 가 비어하지 않는 한 당신은 당신이 당신의 자신의 메모리 관리자를 작성해야하고 윈도우에 의존하지 수 있습니다 귀하의 개인 바이트의 즉각적인 감소에 대해 매우 특별한 경우 그것은 메모리
7. 에 거주 할 것 힙 손잡이.

강조는 내 것입니다. 나는 그것이 질문에 답하는 것 같아요, 또는 질문은 "이것은 Windows 힙 관리가 작동하는 방식입니다"라고 간단합니다. 어쨌든이 문제에 대한 (단순한) 솔루션이 없다면 이론적으로 더 나은 지역을 제공 할 것으로 가정 된 boost :: intrusive 컨테이너와 같은 것을 사용하는 것이 더 좋을 수 있으므로 Windows 메모리 관리자가 메모리를 OS로 반환 할 더 좋은 기회를 갖게됩니다.

UPDATE001 : 부스트 침입 컨테이너가 트릭을 수행하지 못했습니다.

struct Entity : public boost::intrusive::unordered_set_base_hook<> 
{ 
    explicit Entity(size_t id) 
    { 
     first = id; 
     _6 = std::string("a", dis(gen)); 
     _7 = std::string("b", dis(gen)); 
     for(size_t i = 0; i < dis(gen); ++i) 
     { 
      _9.emplace(i, std::string("c", dis(gen))); 
     } 
    } 

    size_t first = 1; 
    int _1 = 1; 
    int _2 = 2; 
    float _5 = 3.14f; 
    double _3 = 3; 
    double _4 = 5; 
    std::string _6 = "hello world!"; 
    std::string _7 = "A quick brown fox jumps over the lazy dog."; 
    std::vector<unsigned long long> _8 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0}; 
    std::map<long long, std::string> _9 = {{0, "a"}, {1, "b"}, {2, "c"}, {3, "d"}, {4, "e"}, 
              {5, "f"}, {6, "g"}, {7, "h"}, {8, "e"}, {9, "j"}}; 
    std::vector<double> _10{1000, 3.14}; 
    std::random_device rd; 
    std::mt19937 gen = std::mt19937(rd()); 
    std::uniform_int_distribution<size_t> dis = std::uniform_int_distribution<size_t>(16, 256); 
}; 

struct first_is_key 
{ 
    typedef size_t type; 

    const type& operator()(const Entity& v) const { return v.first; } 
}; 

using Container = boost::intrusive::unordered_set<Entity, boost::intrusive::key_of_value<first_is_key>>; 

void printContainerInfo(const Container& container) 
{ 
    std::cout << std::chrono::system_clock::to_time_t(std::chrono::system_clock::now()) 
       << ", Size: " << container.size() << ", Bucket count: " << container.bucket_count() << std::endl; 
} 

int main() 
{ 
    constexpr size_t maxEntites = 100'000; 
    Container::bucket_type* base_buckets = new Container::bucket_type[maxEntites]; 
    Container test(Container::bucket_traits(base_buckets, maxEntites)); 

    std::random_device rd; 
    std::mt19937 gen(rd()); 
    std::uniform_int_distribution<size_t> dis; 

    while(test.size() < maxEntites) 
    { 
     auto data = new Entity(dis(gen)); 
     auto res = test.insert(*data); 
     if(!res.second) 
     { 
      delete data; 
     } 
    } 

    printContainerInfo(test); 
    while(test.size() > 0) 
    { 
     while(test.size() > maxEntites * 2/3) 
     { 
      test.erase_and_dispose(test.begin(), [](Entity* entity) 
            { 
             delete entity; 
            }); 
     } 

     printContainerInfo(test); 
     while(test.size() < maxEntites) 
     { 
      auto data = new Entity(dis(gen)); 
      auto res = test.insert(*data); 
      if(!res.second) 
      { 
       delete data; 
      } 
     } 
    } 
    return 0; 
} 

Answer 2

는, 요소의 삭제 절반이 후, 당신은 메모리의 절반이 해제되는 기대 말할 수 있습니다. 권리?

실제로는 없습니다. 나는 메모리 할당자가 내 프로그램의 실행 효율성 측면에서 기록 될 것으로 기대한다. 나는 그것이 필요할 때보 다 더 많은 메모리를 할당하고, 주문을 받았을 때 또는 메모리가 다시 필요하지 않을 것이라고 확신 할 때만 OS에 메모리를 다시 릴리스 할 것으로 기대한다.

사용자 공간에서 가능한 한 자주 메모리 블록을 재사용하고 연속 블록으로 할당 할 것으로 예상됩니다.

대부분의 응용 프로그램에서는 OS에서 메모리를 할당하고 객체가 파괴 된 순간에이를 반환하는 메모리 사용량 할당 기가 엄청나게 느린 프로그램과 많은 양의 디스크 스 래싱을 초래합니다. 인텔 칩셋은이 크기의 페이지에서 메모리를 프로세스로 보호 할 수 있기 때문에 (실제로는) 모든 인기있는 운영 체제에서 최소 40 바이트 문자열에도 자체 4k 페이지가 할당된다는 것을 의미합니다 (또는 일부 시스템?)

Answer 3

당신은 정확하지만 부분적입니다.
방법 C++ unordered_map는 VC에서 구현이 ++ 버킷리스트 및 이 도면에서지도

의 노드를 보유 std::list인 내부 std::vector 사용함으로써, 그것은 그것과 같다

당신이 노드를 삭제로

buckets : [][][*][][][][][][*][][][][][][*] 
       |   |   | 
       |   |   | 
      ---    ------  | 
      |     |  | 
      V     V  V 
elements: [1,3]->[5,7]->[7,1]->[8,11]->[10,3]->[-1,2] 

지금, 그들은 실제로 목록에서 제거됩니다,하지만 버킷 배열에 대해 아무것도 말하지 않는다. 버킷 배열은 일부 임계 값에 도달하면 크기가 조정 된 후 크기가 조정됩니다 (버킷 당 요소가 너무 많거나 요소 수가 너무 많음)

내 포인트도 있습니다. 여기에 최신 VC++로 컴파일 된 예가 나와 있습니다. 디버거에서 원시보기를 찾고

std::unordered_map<int, std::vector<char>> map; 
    for (auto i = 0; i < 1000; i++) { 
     map.emplace(i, std::vector<char>(10000)); 
    } 

    for (auto i = 0; i < 900; i++) { 
     map.erase(i); 
    } 

, 우리는 다음을 참조하십시오

+  _List { size=100 } std::list<std::pair<int const ,std::vector<char,std::allocator<char> > >,std::allocator<std::pair<int const ,std::vector<char,std::allocator<char> > > > > 
+  _Vec { size=2048 } std::vector<std::_List_unchecked_iterator<std::_List_val<std::_List_simple_types<std::pair<int const ,std::vector<char,std::allocator<char> > > > > >,std::_Wrap_alloc<std::allocator<std::_List_unchecked_iterator<std::_List_val<std::_List_simple_types<std::pair<int const ,std::vector<char,std::allocator<char> > > > > > > > > 

우리는 100 개 요소가 있지만,지도 2048 버킷을 유지 것을 의미한다.

따라서 모두 요소를 삭제하면 메모리가 해제됩니다. 맵은 또 다른 메모리를 책으로 보관하고 버킷 자체를 보관하며, 그 메모리는 요소 메모리보다 더 고집 스럽다.

편집 :
의도 와일더 가자! 소거 루프의 끝에

std::unordered_map<int, std::vector<char>> map; 
for (auto i = 0; i < 100'000; i++) { 
    map.emplace(i, std::vector<char>(10000)); 
} 

for (auto i = 0; i < 90'000; i++) { 
    map.erase(i); 
} 

결과

+  _List { size=10000 } std::list<std::pair<int const ,std::vector<char,std::allocator<char> > >,std::allocator<std::pair<int const ,std::vector<char,std::allocator<char> > > > > 
+  _Vec { size=262144 } std::vector<std::_List_unchecked_iterator<std::_List_val<std::_List_simple_types<std::pair<int const ,std::vector<char,std::allocator<char> > > > > >,std::_Wrap_alloc<std::allocator<std::_List_unchecked_iterator<std::_List_val<std::_List_simple_types<std::pair<int const ,std::vector<char,std::allocator<char> > > > > > > > > 

이제, 64 비트에 std::_List_unchecked_iterator<...>의 크기가 8 바이트이다. 262144 * 8/(1024 * 1024) = 2MB 정도의 사용되지 않은 데이터가 있습니다. 이것은 높은 메모리 사용량입니다 ( 참조). 모든 여분의 노드가 제거 beign 후

는 map.rehash(1024*10)를 호출, 메모리 소비에 도움이 보인다

+  _List { size=10000 } std::list<std::pair<int const ,std::vector<char,std::allocator<char> > >,std::allocator<std::pair<int const ,std::vector<char,std::allocator<char> > > > > 
+  _Vec { size=32768 } std::vector<std::_List_unchecked_iterator<std::_List_val<std::_List_simple_types<std::pair<int const ,std::vector<char,std::allocator<char> > > > > >,std::_Wrap_alloc<std::allocator<std::_List_unchecked_iterator<std::_List_val<std::_List_simple_types<std::pair<int const ,std::vector<char,std::allocator<char> > > > > > > > > 

이 당신이 찾고 있던 솔루션입니다.

(필자는 최근에 나의 의지에 반하여 .NET을 많이 사용하고 있습니다.이 퀘스트는 C++에 대한 훌륭한 부분을 보여줍니다. 우리는 디버거를 사용하여 표준 라이브러리 코드를 단계별로 실행할 수 있습니다. 우리는 .NET에서 그러한 일을하는 것이 가능하다면 살아갈 지옥이 될 것입니다.)