Накладные расходы памяти Hashset

В программе C# у меня есть два элемента Queues элементов longs, 26M и четыре элемента HashSets элементов longs, 50M. Таким образом, мои контейнеры хранят 75M longs, который дает 600MB данных. Использование памяти программы 3GB.

Почему эти контейнеры нуждаются в такой большой памяти? Что такое сложность памяти HashSet? Даже если все структуры удваивают свою способность, он даст 1.2GB, а не 3GB.

EDIT: Да, я не имел в виду сложность. Сколько памяти HashSet нужно сохранить long? Простая двоичная куча не нуждается в дополнительной памяти. Есть ли альтернатива для HashSet, если мне нужно снизить использование памяти или мне нужно реализовать ее самостоятельно?

Ответ 1

Обзор

HashSet имеет 12 байтов служебной информации на слот (который может содержать элемент или быть пустым). Эти издержки на 150% больше, чем размер данных в случае хранения длинных.

HashSet также содержит пустые слоты для новых данных, а количество элементов в вашем примере (~ 12,5 млн. Элементов на HashSet) приводит к увеличению использования памяти примерно на 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 - Mono

Стратегия распределения слотов - удваивает размер таблицы при каждом выделении.

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%
Resize Factor: удваивает размер при достижении коэффициента заполнения

Использование памяти - на слот - обе реализации

Таблица: 1 х 4 байта на слот = 4 байта на слот
Ссылки: 2 x 4 байта на слот = 8 байт/слот
Слоты: 1 x (размер T) байтов = 8 байт/слот (для T = длинный)
Всего: 20 байт/слот

Слоты, используемые в примере - Mono

В примере содержится 12,5 миллиона элементов в каждом хэш-наборе.

слоты = 10 * 2 ^ потолок (log2 (предметов /10))

log2 (12 500 000/10) ~ = 20,5

слоты ~ = 21 миллион

Память, используемая в примере - вычисленная - моно

Очередь: 25 миллионов длинных * 8 байт/длинных = 200 МБ

Каждый HashSet: 21 миллион слотов * 20 байтов/слот = 420 МБ

Все HashSets: 1,68 ГБ

Итого: 1,88 ГБ (+ пустое пространство в кучах больших объектов)

Память, используемая в примере - наблюдается с помощью Son of Strike - реализация MSFT

3,5 ГБ памяти в кучах .Net

400 МБ массивов Int32 (используется HashSet, а не для хранения данных)

2,5 ГБ объектов слотов HashSet

Примечание. Размер слота MSFT составляет 8 байт плюс размер данных (в данном случае 8 байт), что в сумме составляет 16 байт. 2,5 ГБ объектов Slot - это 156 миллионов слотов, для хранения только 50 миллионов элементов.

свалка -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.