c++ - std::unordered_map 不释放内存

Question

我观察到 std::unordered_map 的奇怪行为在 MSVC14 (VS2015) 中。考虑以下场景。我创建一个无序映射并用虚拟结构填充它，这会消耗大量内存，比如说 1Gb，总共插入了 100k 个元素。然后开始从 map 中删除元素。假设您已经删除了一半的元素，那么您预计会释放一半的内存。正确的？错误的!我看到当映射中的元素数量超过某个阈值时，内存就会被释放，在我的例子中是 1443 个元素。
有人可能会说它是 malloc优化使用 VirtualAllocEx 从操作系统分配大块或HeapAlloc实际上它并没有将内存释放回系统，因为优化决定了策略并且可能不会调用 HeapFree以便将来重用已分配的内存。
为了消除这种情况，我为 allocate_shared 使用了自定义分配器，它没有达到目的。所以主要问题是为什么会发生这种情况，以及可以采取哪些措施来“压缩”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());
}

然后，当它没有帮助时，尝试一些愚蠢的事情，例如创建临时容器、复制/移动剩余条目、清除原始条目，以及从临时容器复制/移回原始条目。像这样的事情

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()));
}

最后，替换 shared_ptr与 allocate_shared并通过 SimpleAllocator
此外，我到处修改了STL代码，比如调用std::vector::shrink_to_fit上std::unordered_map's vector ( unordered_map 的 msvc STL 实现基于 list 和 vector )，它也不起作用。

EDIT001:对于所有非信徒。以下代码与之前的代码大致相同，但使用 std::vector<Entity>而不是unordered_map 。内存被由操作系统回收。

#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

你是对的，但部分正确。

C++之道unordered_map在 VC++ 中实现是通过使用内部 std::vector ，这是愿望 list ，以及 std::list其中保存 map 的节点。

在图表中，它看起来像这样:

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);
}

查看调试器中的原始 View ，我们看到:

+       _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 个，因此我们持有 262144*8/(1024*1024) = 2MB 的几乎未使用的数据。 这是您看到的高内存使用率。

调用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> > > > > > > > >

这就是您正在寻找的解决方案。

(PS:最近我违背自己的意愿做了很多 .NET 工作。这个问题确实展示了 C++ 的优点:我们可以使用调试器进入标准库代码，准确查看事情如何以及何时发生，然后我们随后可以对它们采取行动。如果可能的话，在 .NET 中做这样的事情将是一个人间 hell 。)