Java 8 hashmap высокая память Использование

Question

Я использую hashmap для хранения QTable для реализации алгоритма обучения усилению. Мой хэш должен хранить 15000000 записей. Когда я запустил свой алгоритм, я увидел, что память, используемая процессом, превышает 1000000K. Когда я вычислил память, я ожидаю, что она будет использовать не более 530000K. Я попытался написать пример, и я получил такое же использование памяти:

public static void main(String[] args) { 
    HashMap map = new HashMap<>(16_000_000, 1); 
    for(int i = 0; i < 15_000_000; i++){ 
     map.put(i, i); 
    } 
} 

Моя calulation память:

Каждый entryset имеет 32 байта
Емкость 15000000
HashMap Instance использует: 32 * SIZE + 4 * МОЩНОСТЬ memory = (15000000 * 32 + 15000000 * 4)/1024 = 527343.75K

Где я ошибаюсь в расчетах моей памяти?

Answer 1

Ну, в лучшем случае мы принимаем размер слова 32 бит/4 байта (с CompressedOops и CompressedClassesPointers). Затем запись карты состоит из двух слов: служебные данные JVM (указатель klass и слово метки), ключ, значение, hashcode и следующий указатель, составляющие всего 6 слов, другими словами, 24 байта. Таким образом, имея 15 000 000 экземпляров ввода, будет потреблять 360 МБ.

Кроме того, имеется массив, содержащий записи. В HashMap используются мощности мощностью 2, поэтому для 15 000 000 записей размер массива составляет не менее 16 777 216, потребляя 64 мегабайта.

Затем у вас есть 30 000 000 Integer экземпляров. Проблема заключается в том, что map.put(i, i) выполняет две операции по боксу, и, хотя JVM рекомендуется повторно использовать объекты при боксе, этого не требуется, и повторное использование не произойдет в вашей простой программе, которая может завершиться до того, как оптимизатор когда-либо вмешался ,

Чтобы быть точным, первые 128 Integer экземпляров повторно, потому что для значений в -128 … +127 диапазоне, совместное использование является обязательным, но реализация делает это путем инициализации весь кэша на первое использовании, поэтому для первых 128 итераций, он не создает два экземпляра, но кеш состоит из 256 экземпляров, что в два раза больше, поэтому мы закончим снова с 30 000 000 Integer экземпляров всего. Экземпляр Integer состоит из, по меньшей мере, двух конкретных слов JVM и фактического значения int, которое должно составлять 12 байтов, но из-за выравнивания по умолчанию фактически потребляемая память будет равна 16 байтам, разделяемой на восемь.

Таким образом, 30 000 000 созданных экземпляров Integer потребляют 480 МБ.

Это составляет 360 МБ + 64 Мбайт + 480 МБ, что составляет более 900 МБ, что делает размер кучи 1 ГБ вполне правдоподобным.

Но для этого нужны инструменты для профилирования. После запуска вашей программы, я получил

Обратите внимание, что этот инструмент сообщает только используемый размер объектов, то есть 12 байт в течение Integer объекта без учета отступов, что вы заметите, если смотреть на общем памяти, выделенной JVM.

Answer 2

У меня было такое же требование, как и вы .. так решил бросить мои мысли здесь.

1) Есть отличный инструмент для этого: jol.

2) Массивы тоже являются объектами, и каждый объект в java имеет два дополнительных заголовка: mark и klass, обычно 4 и 8 байтов (это можно настроить с помощью сжатых указателей, но не вдаваться в подробности).

3) Важно помнить о коэффициенте нагрузки на карте (поскольку это влияет на изменение размера внутреннего массива). Вот пример:

HashMap<Integer, Integer> map = new HashMap<>(16, 1); 

for (int i = 0; i < 13; ++i) { 
    map.put(i, i); 
} 

System.out.println(GraphLayout.parseInstance(map).toFootprint()); 

HashMap<Integer, Integer> map2 = new HashMap<>(16); 

for (int i = 0; i < 13; ++i) { 
    map2.put(i, i); 
} 

System.out.println(GraphLayout.parseInstance(map2).toFootprint()); 

Выход этого отличается (только соответствующие строки):

1  80  80 [Ljava.util.HashMap$Node; // first case 
1  144  144 [Ljava.util.HashMap$Node; // second case 

Посмотрите, как размер больше во втором случае, так как массив поддержка в два раза больше (32 записи). Вы можете поместить только 12 записей в массив размером 16, потому что коэффициент загрузки по умолчанию равен 0,75: 16 * 0,75 = 12.

Почему 144? Математика здесь проста: массив - это объект, таким образом: 8 + 4 байта для заголовков. Плюс 32 * 4 для ссылок = 140 байт. Из-за выравнивания памяти по 8 байт для заполнения добавляются 4 байта, в результате чего получается 144 байта.

4) записи хранятся внутри Узла или TreeNode внутри карты (Node - 32 байта, а TreeNode - 56 байтов). Поскольку вы используете ТОЛЬКО целые числа, у вас будут только узлы, так как не должно быть хеш-коллизий. Там может быть коллизиями, но это еще не означает, что определенная запись массива будет преобразована в TreeNode, для этого есть порог. Мы можем легко доказать, что будут Узлы только:

public static void main(String[] args) { 

    Map<Integer, List<Integer>> map = IntStream.range(0, 15_000_000).boxed() 
      .collect(Collectors.groupingBy(WillThereBeTreeNodes::hash)); // WillThereBeTreeNodes - current class name 

    System.out.println(map.size()); 

} 

private static int hash(Integer key) { 
    int h = 0; 
    return (h = key.hashCode())^h >>> 16; 
} 

Результат этого будет 15_000_000, не было никакого слияния, таким образом, не хэш-коллизий.

5) Когда вы создаете объекты Integer, для них есть пул (от -127 до 128 - это также можно настроить, но давайте не будем для простоты).

6) Integer - это объект, поэтому он имеет 12-байтовый заголовок и 4 байта для фактического значения int.

---

Имея это в виду, давайте попробуем увидеть выход для 15_000_000 записей (так как вы используете коэффициент загрузки одного, нет необходимости в создании внутреннего потенциала 16_000_000). Это займет много времени, так что будьте терпеливы. Я также дал ему

-Xmx12G и -Xms12G

HashMap<Integer, Integer> map = new HashMap<>(15_000_000, 1); 

for (int i = 0; i < 15_000_000; ++i) { 
    map.put(i, i); 
} 

System.out.println(GraphLayout.parseInstance(map).toFootprint()); 

Вот что сказал Йол:

java.util.HashMap@9629756d footprint: 
    COUNT  AVG  SUM DESCRIPTION 
     1 67108880 67108880 [Ljava.util.HashMap$Node; 
    29999872  16 479997952 java.lang.Integer 
     1  48  48 java.util.HashMap 
    15000000  32 480000000 java.util.HashMap$Node 
    44999874   1027106880 (total) 

Начнем снизу.

общий размер Hashmap след: 1027106880 байт или 1 027 MB.

Узел экземпляра - класс обертки, в котором находится каждая запись. он имеет размер 32 байта; Есть 15 миллионов записей, таким образом линия:

15000000  32 480000000 java.util.HashMap$Node 

Почему 32 байта? Сохраняет хэш-код (4 байта), ссылку на ключ (4 байта), ссылку на значение (4 байта), следующую ссылку на Node (4 байта), 12-байтовый заголовок, 4 байта, в результате получается 32 байта.

1  48  48 java.util.HashMap 

Один экземпляр хэшмапа - 48 байтов для его внутренних компонентов.

Если вы действительно хотите знать, почему 48 байт:

System.out.println(ClassLayout.parseClass(HashMap.class).toPrintable()); 


java.util.HashMap object internals: 
OFFSET SIZE   TYPE DESCRIPTION        VALUE 
    0 12    (object header)       N/A 
12  4   Set AbstractMap.keySet      N/A 
16  4 Collection AbstractMap.values      N/A 
20  4   int HashMap.size        N/A 
24  4   int HashMap.modCount       N/A 
28  4   int HashMap.threshold       N/A 
32  4  float HashMap.loadFactor      N/A 
36  4  Node[] HashMap.table        N/A 
40  4   Set HashMap.entrySet       N/A 
44  4    (loss due to the next object alignment) 
Instance size: 48 bytes 
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total 

Следующая экземпляры Integer:

29999872  16 479997952 java.lang.Integer 

30 млн целых объектов (минус 128, которые кэшируются в бассейне)

1 67108880 67108880 [Ljava.util.HashMap$Node; 

У нас есть 15_000_000 записей, но внутренний массив HashMap имеет мощность двух размеров, это 16,777,216 ссылки по 4 байта каждый.

16_777_216 * 4 = 67_108_864 + 12 bytes header + 4 padding = 67108880