Расположение данных в памяти или знай что замеряешь 2
В предыдущей заметке я привел парадоксальные результаты замера скорости итерации по ArrayList: итерация по первым 1M элементам работает медленней на моем тесте (4.62 нс на элемент), чем итерация по 10M элементам этого же массива (3.67 нс на элемент). Более того, наблюдаемый эффект очень не стабилен. Он сильно зависит от используемой версии JVM и от её настроек.
Сразу скажу, что этот эффект ни как не связан с JIT компиляцией Java кода. При замерах времени в своей тестовой программе я не учитываю первый проход, во время которого основной цикл компилируется, и вообще использую Java HotSpot Server VM, которая создает машинный код, оптимизированный на том же уровне, как это делают популярные C/C++ компиляторы.
В заметке я дал две подсказки. Первая подсказка содержалась в названии заметки: "знай что замеряешь". Вторая подсказка в ссылке на мою заметку " Память это новый диск". В ней была наглядна показана прямая зависимость скорости работы простого алгоритма итерации от объема памяти, который использует структура данных. Однако, подсистема работы с памятью современных процессоров загружает данные из памяти не отдельными байтами, а подгружает целый блок данных в кэш процессора. В процессоре, на котором я проводил тестирование, размер блока кэша равен 64 байтам. Объект Integer, который мы храним в списке, занимает всего 16 байт, однако если все объекты в списке будут располагатьcя в своих собственных блоках кэша, то их эффективный размер, с точки зрения алгоритма итерации по списку, будет равен 64 байтам, ибо для загрузки каждого объекта процессор все равно подгрузит 64 байта в память. Если же все объекты Integer располагаются в памяти последовательно, по 4 объекта в каждом блоке, то при последовательной итерации по массиву никаких лишних байтов в память подгружаться не будет - из каждого блока, загруженный из памяти за один раз, процессор возьмет четыре последовательно идущих объекта.
Скорость работы этого примитивного алгоритма зависит не от объема занимаемой структурой данных памяти, а от объема памяти, которую фактически придется прочитать процессору при исполнении данного алгоритма. Наш тест измерял то, насколько удачно объекты Integer расположились в памяти. Парадоксальные замеры времени исполнения наблюдаются потому, что первые 1M массива легли в памяти хуже, чем последующие 9М элементов.
Чтобы продемонстрировать тот факт, что такое расположение действительно имеет место, нужно узнать адреса по которым объекты расположились в памяти. На языке Java этого сделать нельзя даже используя такие трюки, как работа через класс sun.misc.Unsafe. У этого есть очень веские причины. Сборщик мусора перемещает объекты по памяти, то есть объект, который сейчас находится по одному адресу в следующий момент времени, с точки зрения программы, может оказаться по другому адресу. Поэтому "небезопасные" методы работы с объектами в классе sun.misc.Unsafe принимают в качестве аргумента не адрес объекта в памяти, а ссылку на объект и смещение внутри объекта. Расположение же всех переменных и полей ссылочного типа в программе на Java известно для JVM и автоматически корректируется при перемещении объекта в памяти сборщиком мусора.
Для доступа к адресу потребуется написать небольшой кусочек кода на C, который будет вызваться из Java через JNI. В JNI все ссылочные Java типы представлены типом jobject. Изучение кода JVM, а именно метода allocate_handle в файле jniHandles.cpp, который преобразовывает oop (указатель на объект в JVM) в jobject, позволяет установить, что jobject это указатель на указатель на объект. А значит, следующий JNI метод в файле ArrayListAnalyzeAndTime.c позволить нам его достать в виде целого числа в этой JVM:
JNIEXPORT jlong JNICALL Java_ArrayListAnalyzeAndTime_getCurrentObjectAddress(JNIEnv *evn, jclass cls, jobject obj) { return (jlong) *((void**)obj); }
Используя этот метод getCurrentObjectAddress в классе ArrayListAnalyzeAndTime я могу получить текущие адреса объектов Integer, которые были положены в ArrayList. Я не будут пытаться точно подсчитать, сколько памяти процессору придется прочитать при последовательном проходе по такому массиву объектов. Для этого пришлось бы промоделировать всю иерархию кэшей процессора, да еще учесть наличие буферов ассоциативной трансляции. Можно воспользоваться встроенными в процессор возможностями профилирования для точного подсчета количества блоков загруженных в память, но не в этот раз, ибо я хочу показать откуда именно берутся эти результаты, а не еще раз подтвердить факт их существования.
Я воспользуюсь очень простой эвристикой для оценки качества расположения данных в памяти. Проходясь последовательно по адресам я буду вычислять номер блока памяти, в котором находится этот адрес, и зачитывать любую смену номера блока как загрузку нового блока. Посчитав среднее число байт, которые приходится загружать при просмотре n первых элементов списка, получим следующую зависимость от n при расчете для блоков размером 64 байта на моей машине с 32-bit Java 1.7.0_02 HotSpot Server. В той же таблице приведено среднее время итерации по этим же n объектам. Используя опцию -verbose:gc я убеждаюсь что между анализом адресов и замерами времени не было сборки мусора, а значит объекты все еще находятся по тем же адресам, которые были проанализированы.
Размер nЗагружаемых байтВремя нс 1 00018.81.30 10 00017.91.65 100 00017.81.92 1 000 00019.44.64 10 000 00017.23.68
Напомню, что быстрая скорость на размерах до 100K элементов объясняется тем, что все данные помещаются в 3Mb кэш моего процессора. Видно, что аномальный скачок времени работы на 1M элементах заметен и при анализе среднего количества загружаемых байт с помощью простейшей эвристики.
Аномалия легко исправляется, если сразу запустить JVM с большим размером кучи указав опции -Xmx1G -Xms1G. Сборка мусора произойдет всего один раз, минимизировав возможные перетасовки объектов, и положительно скажется на результатах:
Размер nЗагружаемых байтВремя нс 1 00018.41.34 10 00017.71.71 100 00017.71.80 1 000 00017.73.31 10 000 00017.53.39
Справедливости ради надо заметить, что при переносе объектов сборщик мусора в JVM пытается выложить сложные структуры данные правильным образом. Например, копирующий конструктор переносит данные в том порядке, в которым они изначально были выделены.
Знай что замеряешь. При оценке времени работы алгоритмов, которые работают с нетривиальными структурами данных, надо всегда знать, что именно вы замеряете в своих тестах - эффективность вашего кода или то, как удачно или неудачно ваша структура данных легла в память процессора.
UPDATE: А еще учитывайте как именно вы используете измеряемый код, особенно если там есть полиморфизм. Подробности в заметке " Цена полиморфизма в Java или фактическая полиморфность имеет значение".