在 C#
程序我有两个 Queues
的 longs
, 26M
元素在一起和四个 HashSets
的 longs
, 50M
元素在一起。所以我的容器正在存放 75M
longs
这使 600MB
数据的。程序的内存使用情况是 3GB
。
为什么这些容器需要这么多内存?什么是内存复杂性 HashSet
?即使所有结构都使他们的能力增加一倍,它也会给予 1.2GB
不是 3GB
。
编辑:
是的,我并不是指复杂性。多少额外的内存 HashSet
需要存储 long
?简单的二进制堆不需要任何额外的内存。有没有其他选择 HashSet
如果我需要降低内存使用量或者我需要自己实现一个?
概观
HashSet每个插槽有12个字节的开销(可以包含一个项目或为空)。在存储long的情况下,此开销比数据大小大150%。
HashSet还为新数据保留空插槽,示例中的项目数(每个HashSet约1250万个项目)导致内存使用量增加约66%,原因是空插槽。
如果你需要在集合中确认存在O(1),那么HashSet可能是你能做的最好的。如果您对数据有所了解(例如,如果连续数百个项目包含“运行”),那么您可能会想出一种更聪明的方法来表示需要更少内存的数据。如果不了解有关数据的更多信息,很难就此提出建议。
测试程序
static void Main(string[] args)
{
var q = new Queue<long>();
var hs = new []
{
new HashSet<long>(),
new HashSet<long>(),
new HashSet<long>(),
new HashSet<long>()
};
for (long i = 0; i < 25000000; ++i)
{
q.Enqueue(i);
if (i < 12500000)
{
foreach (var h in hs)
{
h.Add(i);
}
}
}
Console.WriteLine("Press [enter] to exit");
Console.ReadLine();
}
HashSet实现 - 单声道
插槽分配策略 - 每次分配时表的大小加倍。
https://github.com/mono/mono/blob/master/mcs/class/System.Core/System.Collections.Generic/HashSet.cs
HashSet实现 - MSFT
插槽分配策略 - 使用素数分配。这可能会导致大量的空白空间,但会减少必须重新分配和重新分配表的次数。
http://referencesource.microsoft.com/#System.Core/System/Collections/Generic/HashSet.cs
内存使用 - 一般大小调整 - 单声道实现
- 初始尺寸:10个插槽
- 填充因子:90%完全触发器调整大小
- 调整因子:达到填充因子时的大小加倍
内存使用 - 每个插槽 - 两个实现
- 表:每个插槽1 x 4字节int = 4字节/插槽
- 链接:每个插槽2 x 4字节整数= 8字节/插槽
- 插槽:1 x(sizeof T)字节= 8字节/槽(对于T = long)
- 总计:20字节/插槽
示例中使用的插槽 - 单声道
该示例在每个HashSet中有1250万个项目。
slots = 10 * 2 ^ ceiling(log2(items / 10))
log2(12,500,000 / 10)〜= 20.5
插槽〜= 2100万
示例中使用的内存 - 计算 - 单声道
队列:2500万长* 8字节/长= 200 MB
每个HashSet:2100万个插槽* 20个字节/插槽= 420 MB
所有HashSet:1.68 GB
总计:1.88 GB(大对象堆中的空白空间)
示例中使用的内存 - 与Strike之子一起观察 - MSFT实现
.Net堆中的3.5 GB内存
400 MB的Int32数组(由HashSet使用,不适用于我们的数据存储)
2.5 GB的HashSet Slot对象
注意:MSFT的Slot对象是8个字节加上数据的大小(本例中为8个字节),总共16个字节。 2.5 GB的Slot对象是1.56亿个插槽,仅用于存储5000万个项目。
dumpheap -stat
!dumpheap -stat
Statistics:
MT Count TotalSize Class Name
00007ffb549af228 1 24 System.Collections.Generic.GenericEqualityComparer`1[[System.Int64, mscorlib]]
[snip]
00007ffb53e80bd8 159 6926 System.String
00007ffb53e81250 27 36360 System.Object[]
00000042ed0a8a30 22 48276686 Free
00007ffb53f066f0 3 402653256 System.Int64[]
00007ffb53e83768 14 431963036 System.Int32[]
00007ffaf5e17e88 5 2591773968 System.Collections.Generic.HashSet`1+Slot[[System.Int64, mscorlib]][]
Total 343 objects
eeheap -gc
!eeheap -gc
Number of GC Heaps: 1
generation 0 starts at 0x00000042800472f8
generation 1 starts at 0x0000004280001018
generation 2 starts at 0x0000004280001000
ephemeral segment allocation context: none
segment begin allocated size
0000004280000000 0000004280001000 000000428004b310 0x4a310(303888)
Large object heap starts at 0x0000004290001000
segment begin allocated size
0000004290000000 0000004290001000 0000004290009728 0x8728(34600)
00000042dc000000 00000042dc001000 00000042e7717e70 0xb716e70(191983216)
000000433e6e0000 000000433e6e1000 000000434f9835b0 0x112a25b0(287974832)
00000043526e0000 00000043526e1000 000000435a6e1038 0x8000038(134217784)
000000435e6e0000 000000435e6e1000 0000004380c25c00 0x22544c00(575949824)
00000043826e0000 00000043826e1000 000000438826c788 0x5b8b788(95991688)
000000438a6e0000 000000438a6e1000 00000043acc25c00 0x22544c00(575949824)
00000043ae6e0000 00000043ae6e1000 00000043b426c788 0x5b8b788(95991688)
00000043b66e0000 00000043b66e1000 00000043d8c25c00 0x22544c00(575949824)
00000043da6e0000 00000043da6e1000 00000043e026c788 0x5b8b788(95991688)
00000043e26e0000 00000043e26e1000 0000004404c25c00 0x22544c00(575949824)
0000004298000000 0000004298001000 00000042a8001038 0x10000038(268435512)
Total Size: Size: 0xcf1c1560 (3474724192) bytes.
------------------------------
GC Heap Size: Size: 0xcf1c1560 (3474724192) bytes.