我观察到
std::unordered_map
MSVC14(VS2015)。
考虑以下场景。我创建了一个无序的映射,并用虚拟结构填充它,它消耗了大量内存,比如1Gb,总共插入了100k个元素。然后开始从地图中删除元素。假设您删除了一半的元素,那么您希望释放一半的内存。正当错误的我看到当地图中的元素数超过某个阈值时,内存就会释放,在我的例子中是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
具有
分配_共享
并通过
SimpleAllocator
实例。
此外,我还到处修改了STL代码,比如调用
std::vector::shrink_to_fit
在…上
std::unordered_map's
vector
(msvc stl实现
无序映射
基于
list
和
矢量
),它也不起作用。
EDIT001:适用于所有非信徒。以下代码或多或少与前面的代码相同,但使用
std::vector<Entity>
而不是
无序映射
.记忆
是
#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;
}
