Почему производительность ArrayList отличается, если на нее ссылаются как на List?

В статье kjellkod было указано, что если мы передадим ArrayList в методе, который получает List в качестве аргумента, тогда мы теряют производительность, поскольку ArrayList реализует дополнительный RandomAccess интерфейс. Пример из статьи:

// SLOWER: as shown in http://ideone.com/1wnF1
private static void linearInsertion(Integer[] intArray, List<Integer> list) {
[...]
int list_size = list.size();
for (int i = 0; i < list_size; i++) {
if (integer.compareTo(list.get(i)) >= 0) { // ... more code

// FASTER: as shown in http://ideone.com/JOJ05
private static void linearInsertion(Integer[] intArray, ArrayList<Integer> list) {
[...]
int list_size = list.size();
for (int i = 0; i < list_size; i++) {
if (integer.compareTo(list.get(i)) >= 0) { // ... more code

Из справки:

Алгоритмы обобщенного списка рекомендуется проверять, соответствует ли данный список является экземпляром этого интерфейса перед применением алгоритма, который будет обеспечивать низкую производительность, если она будет применена к последовательному список доступа и изменить их поведение, если это необходимо, чтобы гарантировать приемлемая производительность.

Однако, если мы действительно передадим ArrayList в вышеуказанных методах и проверим list instanceof RandomAccess, это будет верно в обоих случаях. Итак, мой первый вопрос: , почему Java VM должна интерпретировать это как последовательный список в первом методе?

Я изменил тесты из статьи, чтобы проверить это поведение на моей машине. Когда тест выполняется на ideone, он показывает результаты, похожие на kjellkod's. Но когда я запускал его локально, я получил неожиданные результаты, которые противоречат объяснению статьи, а также моему пониманию. Похоже, что в моем случае ArrayList, как итерация List, на 5-25% быстрее, чем ссылка на ArrayList:

enter image description here

Как объяснить эту разницу? Зависит ли она от архитектуры или количества процессорных ядер? Моя рабочая конфигурация машины - Windows 7 Professional x64, Intel Core i5-3470 (4 ядра, 4 потока), 16 ГБ оперативной памяти.

Ответы

Ответ 1

Итак, мой первый вопрос - почему Java VM должна интерпретировать это как последовательный список в первом методе?

JVM не имеет понятия последовательных или произвольных списков доступа. (Помимо интерфейса маркера) Это разработчик реализации, который распознает, что ArrayList выполняет поиск в произвольном порядке в O (1) раз, а не O (n).

Это зависит от архитектуры или количества процессорных ядер?

Нет, вы увидите разницу между -client например. 32-битные Windows и -server, например. любой 64-разрядной JVM.

Я подозреваю, что вы запустили второй тест List. Скорее всего, это будет быстрее, поскольку код будет более предупрежден как в JIT, так и в кеше процессора. Я предлагаю вам выполнить каждый тест как минимум три раза, сначала выполнив самые длинные тесты и проигнорировав первый запуск.

Примечание: contains() - это O (n) для списка, поэтому ваши тайминги растут O (n ^ 2). Очевидно, вы не использовали бы List, если бы вы хотели игнорировать дубликаты и рассматривали поведение действительно неэффективных код может быть запутанным, так как вы очень восприимчивы к тонкостям того, что оптимизируется, а что нет. Вы получите гораздо более значимые результаты от сравнения кода, который уже достаточно оптимален.

Ответ 2

Несмотря на то, что в обоих методах один и тот же код по-прежнему теоретически, может быть разница, поскольку на уровне JVM вызов метода интерфейса отличается от вызова метода класса. Это две различные операции байт-кода: invokeinterface и invokevirtual. См. http://bobah.net/d4d/source-code/misc/invokevirtual-vs-invokeinterface-performance-benchmark