Неверные результаты теста ArrayList и HashSet

Ответ 1

Что случилось с теорией, упомянутой в цитируемом ответе? Это ложь?

Мы можем сделать некоторые вычисления, чтобы получить оценку:

Посмотрим на источник OpenJDK для ArrayList и HashMap (поскольку HashSet - это всего лишь оболочка вокруг HashMap) для подсказок.

Предположим, что у вас есть элементы n для хранения.

ArrayList

Элементы сохраняются в поле transient Object[] elementData;. Поэтому длина elementData должна быть не менее n.
Предположим, вы создали экземпляр списка с new ArrayList<>(n), и поэтому elementData.length - это точно n. Тогда размер вашего списка равен n*c bytes (где c - размер ссылки на объект). Здесь я проигнорировал поле size и заголовок объекта в списке.

HashMap

HashMap хранит элементы в transient Node<K,V>[] table;, где node имеет поля

final int hash;
final K key;
V value;
Node<K,V> next;

Затем для хранения элементов n вам нужны n узлы или n*(3*c + 4) байты i.e каждый node имеет 3 ссылки на объекты - 3*c bytes - и int - 4 байта.
Согласно HashMap javadoc:

Когда количество записей в хэш-таблице превышает произведение коэффициента загрузки и текущей емкости, хеш-таблица повторно отображается (то есть внутренние структуры данных перестраиваются), так что хэш-таблица имеет примерно вдвое больше ковши.

Исходя из этого, я буду оценивать, что table.length == 2*n.
Для суммирования hashmap требуется n*2*c + n*(3*c + 4) = n*5*c + n*4 байт.

Резюме

Теперь предположим, что у вас есть 64-битная JVM, а размер ссылки на объект - 8 байтов (т.е. c = 8) (пусть воспламеняется такие вещи, как сжатые oops). Тогда n*5*c + n*4 = n*5*8 + n*4 = n*44 и n*c = n*8.
Наконец n*44 / n*8 = 5.5

Итак, оригинальная теория, что HashSet потребляет в 5,5 раз больше памяти, чем ArrayList, кажется вполне правдоподобной, и кажется, что с вашими измерениями что-то не так.

Ответ 2

Пожалуйста, добавьте объект измерения в качестве возвращаемого значения.

measure method "Int" in {
  using(sizes) curve listS in { i =>
    val c = new util.ArrayList[Int](i)
    (0 until i).map(t => c.add(t))
    c // return c
  }

  using(sizes) curve setS in { i =>
    val c = new util.HashSet[Int]()
    (0 until i).map(t => c.add(t))
    c // return c
  }
}

Ответ 3

Думаю, здесь есть две проблемы:

• Как отметил Анджей, вы не возвращаете свои коллекции из эталонных фрагментов. Scalameter измеряет отпечаток, выполняя GC до и после эталонного исполнения (найдите здесь здесь). Если вы не вернете коллекцию, она просто удаляется из памяти GC после тестирования, и результаты теста бесполезны. Это объясняет, почему следы памяти в тестах остаются небольшими (около четырех байт на объект) и не отличаются друг от друга. Но это не объясняет, почему след увеличивается, когда размер коллекции растет, и здесь возникает вторая проблема.

• Некоторые сборщики мусора (особенно CMS и G1) не гарантируют, что после выполнения сборки мусора все мертвые объекты удаляются из памяти. Если ваша JVM выбирает один из этих коллекционеров (или если вы укажете его вручную), это объяснит восходящий тренд памяти. Вы можете проверить, какой коллекционер используется, предоставив -XX:+PrintFlagsFinal вариант вашего теста и найти значения флагов UseG1GC и UseConcMarkSweepGC.