哈希集内存开销

Question

在C#程序中,我有两个Queues的longs,26M元素结合在一起,四HashSets中longs,50M元素结合在一起.所以我的容器存储75M longs了600MB数据.程序的内存使用情况是3GB.

为什么这些容器需要这么多内存？什么是内存复杂性HashSet？即使所有的结构加倍他们的能力,它会给1.2GB,不会3GB.

编辑:是的,我并不是指复杂性.HashSet需要存储多少额外内存long？简单的二进制堆不需要任何额外的内存.HashSet如果我需要降低内存使用量或者我需要自己实现一个,是否还有其他选择？

Answer 1

概观

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.