std::unordered_map不释放内存

Question

我在 MSVC14 (VS2015) 中观察到 std::unordered_map 的奇怪行为。考虑以下场景。我创建了一个无序映射并用虚拟结构填充它，它消耗了大量内存，比方说 1Gb，总共插入了 100k 个元素。然后开始从地图中删除元素。假设您已经删除了一半的元素，那么您希望释放一半的内存。正确的？错误的！我看到当 map 中的元素数量超过某个阈值时会释放内存，在我的例子中是 1443 个元素。
有人可能会说这是 malloc 从 [=54= 分配大块的优化] 使用 VirtualAllocEx 或 HeapAlloc 实际上它不会将内存释放回系统，因为优化决定了策略并且可能不会调用 HeapFree 以便将来重用已分配的内存。
为了消除这种情况，我为 allocate_shared 使用了自定义分配器，但没有成功。所以主要问题是为什么会发生这种情况以及可以对 unordered_map 使用的 "compact" 内存做些什么？
代码

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

到目前为止我尝试过的事情：当负载因子达到某个阈值时尝试 rehash/resize - 在擦除 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());
}

然后，当它无济于事时，尝试一些愚蠢的事情，比如创建临时容器，copying/moving 剩余的条目，清除原来的条目，然后 copy/move 从临时恢复到原来的状态。像这样

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::unordered_map's vector 上调用 std::vector::shrink_to_fit（unordered_map 的 msvc stl 实现基于 list 和 vector），它也没有用。

EDIT001：对于所有非信徒。以下代码与前面的代码大致相同，但使用 std::vector<Entity> 而不是 unordered_map。内存被回收 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

Lets say you have deleted half of elements, then, you expect half of memory being freed. Right?

实际上没有。我希望根据程序执行效率来编写内存分配器。我希望它分配比它需要的更多的内存，并仅在订购时或确定不再需要内存时才将内存释放回 OS。

我希望内存块在 user-space 中尽可能频繁地重复使用，并且它们被分配在连续的块中。

对于大多数应用程序，从 OS 分配内存并在对象被销毁时返回它的迂腐的内存分配器将导致程序非常缓慢和大量的磁盘抖动。这也（在实践中）意味着在所有流行的操作系统上，即使是最小的 40 字节字符串也会分配到它自己的 4k 页面，因为英特尔芯片组只能处理这种大小的页面中的内存（或者在某些情况下可能更大）系统？）

Answer 2

你是对的，但部分正确。

C++ unordered_map 在 VC++ 中的实现方式是使用内部 std::vector，即 存储桶列表 ，以及一个 std::list，其中 包含地图的节点 。

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

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

现在，当您擦除节点时，它们实际上是从列表中删除的，但它没有说明 buckets 数组。在达到某个阈值后调整 buckets 数组的大小（每个桶中的元素太多，或者对于元素数量而言桶太多）。

太证明我的观点了，这里是用最新的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 个桶。

所以，不是所有删除元素时释放内存。 map维护了另一段内存来book-keep buckets本身，那段内存比元素内存更顽固。

编辑：
让我们更狂野！

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 中做这样的事情本来就是一个活生生的地狱，如果可能的话。）

Answer 3

好的，在向 Microsoft 打开高级支持票后，我得到了以下答案。其中大部分我们已经知道，但有一部分我们没有考虑。

In windows memory is allocated in the heap in form of Pages

In the STL there is no caching whatsoever, we straightway call RtlHeapFree after you call erase

What you see is how Windows manages the Heap

Once you mark something for deletion it may not be returned to the OS where there is no memory pressure, it may decide that the cost of reallocating the memory in future is more than keeping it in the process

This is how any Heap algorithms work

Another thing to consider is that; if the values that you are deleting happens to spread out across pages; and unless all the values inside the page are empty it will be resident in the memory

If you are extremely particular about immediate reduction of your private bytes you may have to write your own memory manager and not depend on Windows Heap Handle.

重点是我的。我猜它回答了问题，或者问题就像"this is the way Windows heap management works"一样简单。在任何情况下，这个问题都没有（简单的）解决方案，也许最好使用 boost::intrusive 容器之类的东西，理论上应该提供更好的局部性，因此 Windows 内存管理器有更好的机会 return记忆到OS.

更新001： Boost 侵入式容器也没有成功。

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

std::unordered_map不释放内存

std::unordered_map does not release memory

c++

memory-management

stl

unordered-map

visual-c++