Массив / связанный список: производительность зависит от * направления * обхода? [закрытый]

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

Первоначальное название этой темы было "полная итерация по массиву значительно быстрее, чем со связанным списком". Название было изменено в связи с новыми результатами тестирования (представленными во втором разделе).

---

Раздел первый: первоначальный тест Дело

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

Во-первых, мои наивные предположения. Давайте рассмотрим следующий класс:

private static class Message {

    public int value1;

    public Message next;



    public Message(java.util.Random r, Message nextmsg) {

        value1 = r.nextInt();

        next = nextmsg;

    }

}

В первом сценарий измерения, его поле next не будет использоваться вообще. Приведенный ниже код создает массив из 1 000 000 экземпляров Message, а затем повторяет его в цикле. Он измеряет, сколько времени занимает итерация.

Log.i("TEST", "Preparing...");          



final int cnt = 1000000;

int val = 0;

java.util.Random r = new java.util.Random();

Message[] messages = new Message[cnt];

for (int i = 0; i < cnt; i++) {

    messages[i] = new Message(r, null);

}           



Log.i("TEST", "Starting iterating...");

long start = SystemClock.uptimeMillis();



for (int i = 0; i < cnt; i++) {

    Message msg = messages[i];

    if (msg.value1 > 564645) {

        val++;

    }

}       

Log.w("TEST", "Time: " + (SystemClock.uptimeMillis() - start) + ", result: " + val);

Второе измерение вместо этого строит и измеряет связанный список объектов Message:

Log.i("TEST", "Preparing...");          



final int cnt = 1000000;

int val = 0;

java.util.Random r = new java.util.Random();

Message current = null;

Message previous = null;

for (int i = 0; i < cnt; i++) {

    current = new Message(r, previous);

    previous = current;

}

previous = null;



Log.i("TEST", "Starting iterating...");

long start = SystemClock.uptimeMillis();

while (current != null) {

    if (current.value1 > 564645) {

        val++;

    }

    current = current.next;

}           



Log.w("TEST","Time: " + (SystemClock.uptimeMillis() - start) + ", result: " + val);

Первое испытание постоянно производит 41-44 МС, в то время как второй тест дает 80-85 МС. итерация связанного списка, по-видимому, равна 100% замедлившийся.

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

Хорошо, мы часто можем прочитать, что массив является непрерывным блоком памяти, и, таким образом, доступ к его элементам последовательно более удобен для кэша, чем в случае связанного списка. но В нашем случае элементами массива являются только ссылки на объекты , а не сами объекты Message (в Java у нас нет типа значения т. е. struct, как в C# которые мы могли бы хранить в виде встроенного массива). Таким образом," локальность ссылки " применяется только к самим элементам массива, и они определяют только адрес объектов. Следовательно, экземпляры Message (В общем случае) все еще могут быть "где угодно" в памяти, поэтому "локальность ссылки" не применяется к самим экземплярам. С этой точки зрения мы выглядим так же, как и в случае связанного списка: сами экземпляры могут находиться "где угодно" в памяти: массив только гарантирует, что их ссылки хранятся в непрерывном блоке...

...и вот вам пример использования: полный последовательный обход (итерация). Во-первых, давайте рассмотрим, как мы получаем ссылки на экземпляры в каждом случае. В случае с массивом это очень эффективно, потому что они находятся в непрерывном блоке. но В случае связанного списка мы также хороши, потому что как только мы получили доступ к экземпляру Message (Вот почему мы повторяем!), мы сразу же имейте ссылку наследующий экземпляр. И поскольку мы уже получили доступ к полю Message, доступ к другому полю ("next") должен поддерживаться кэшем (поля того же объекта также имеют локальность ссылок AFAIK, они также находятся в непрерывном блоке). Подводя итог, он, по-видимому, сводится к следующему:

1. массив предлагает удобную для кэша итерацию по ссылкам. Message сами экземпляры могут быть "где угодно" в памяти, и нам нужно посетить их, тоже.


2. связанный список предлагает, чтобы ссылка на следующий элемент получалась при обращении к текущему экземпляру Message. Это "бесплатно", потому что каждый экземпляр Message должен быть посещен в любом случае (как и в случае с массивом).

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

Мои догадки следующие:

1. 
   

   Вероятно, не кэш-дружелюбие массива ответственно за 100% разница. Вместо этого JIT выполняет оптимизацию, которая не может быть выполнена в случае обхода связанного списка. Если проверка диапазона и (VM-level) проверка null исключены, то я предполагаю, что инструкция "array-get" байт-кода может быть быстрее, чем моя инструкция "field-get" (или как она там называется) в случае связанного списка (?).



2. 
   

   Несмотря на то, что экземпляры Message могут быть "где угодно "в памяти, они, вероятно, очень близки друг к другу, потому что они были выделены" в одно и то же время время". Но 1 000 000 экземпляров не могут быть кэшированы, только часть из них. В таком случае последовательный доступ был бы удобен для кэширования как в массиве, так и в связанном списке, поэтому это не объясняет разницу.



3. 
   

   Некоторые умные "предсказание" (предварительная выборка) из Message экземпляр мне доступ? Т. е. каким-то образом сохраняется кэш-дружелюбие с самими экземплярами Message, но только В случае доступа к массиву.

Обновление: так как несколько замечания были получены, я хотел бы отреагировать на них ниже.

@irreputable:

Связанный список посещается с верхнего адреса на нижний адрес. а что если
все наоборот, то есть next указывает на более новый объект, а не на
предыдущий объект

Очень хорошее место! Я не думал, что эта маленькая деталь может повлиять на тест. Я проверю его сегодня и вернусь с результатами. (Edit: результаты здесь, я обновил этот пост с помощью "Раздел 2").

@Torben Комментарии:

Кроме того, я бы сказал, что все это упражнение кажется довольно бесполезным. Вы
речь идет об улучшении 4ms за 100000 итераций. Похоже, что
преждевременная оптимизация. Если у вас есть ситуация, когда это
узкое место, тогда, пожалуйста, опишите его, и мы сможем заглянуть в него (потому что
это определенно была бы более интересная проблема, чем эта).

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

Я ценю мысль, которую вы вложили в это, но я действительно не могу найти
вопрос с вашего поста. :) Edit: и итерация массива на 50% быстрее.
100% быстрее означало бы ноль затраченного времени.

Я уверен, что из моего сообщения было довольно очевидно, что я задаюсь вопросом, почему присутствует очень существенная разница, когда аргументы подразумевают обратное. Спасибо за поправку: действительно, я хотел написать, что случай связанного списка на 100% медленнее.

---

Раздел второй: модифицированные тестовые случаи

у неопровержимого было очень интересное наблюдение для меня:

Связанный список посещается с верхнего адреса на нижний адрес. а что если
все наоборот, то есть next указывает на более новый объект, а не на
предыдущий объект

Я изменил структуру связанного списка таким образом, что направление его указателей next равно порядку создания экземпляров его узлов:

Message current = null;

Message previous = new Message(r, null);

Message first = previous;

for (int i = 0; i < cnt; i++) {

    current = new Message(r, null);

    previous.next = current;

    previous = current;

}       

previous = current = null;

(Обратите внимание, что алгоритм создания может быть не самым компактным, я думаю, что знал немного более приятный способ.) Код, который повторяется через этот связанный список:

while (first != null) {

    if (first.value1 > 564645) {

        val++;

    }

    first = first.next;

}

И теперь результат, который я получаю, постоянно 37-39 ms (хорошо, мы можем сказать, что это точно производительность массива, но на самом деле, это немного быстрее в каждом тестовом случае, постоянно.) Вместо того, чтобы 80 ms из связанного списка" обратное направление", это в два раза быстрее!

Затем я сделал аналогичный тест с оригинальным тестовым случаем массива: я изменил обход массива в противоположное направление (на обратный отсчет петля):

for (int i = cnt - 1; i >= 0; i--) {

    Message msg = messages[i];

    if (msg.value1 > 564645) {

        val++;

    }

}

И результат постоянно 85-90 МС! Первоначальный тестовый случай дал 40-41 МС.

Похоже, что теперь есть два новых вывода (и один вопрос):

1. 
   

   Исходное утверждение, по-видимому, верно, что "локальность ссылки" массива (из-за смежного блока памяти) не обеспечивает преимущества В случае массивов "ссылочного типа" (т. е. объектов), когда они сравниваются со связанными списками. Это происходит потому, что объект массивы содержат только ссылкина экземпляры объектов, а не сами экземпляры объектов (которые теоретически могут быть "где угодно" в памяти, как и в случае связанного списка).



2. 
   

   В моих тестовых случаях результат, похоже, зависит от направления обхода , даже в случае сценария массива (!). Как такое возможно?

Чтобы подвести итоги моего теста:

1. 
   

   В" прямом " направлении обхода, связанный список немного превосходит обход массива (точно так, как и ожидалось: мы имеем следующую ссылкусразу после получения экземпляра Message, т. е. даже нет необходимости обращаться к элементу массива для получения его адреса).



2. 
   

   При обходе в обратном направлении оба имеют примерно на 100% более низкую производительность (и связанный список также немного превосходит массив).

Есть идеи?

Обновление 1: dlthorpe сделал очень ценные комментарии. Я скопирую их здесь, так как они могут помочь в поиске ответа на эту "загадку".

Есть ли какие-либо признаки того, что аппаратное обеспечение реализует страницу предвидения
предварительная выборка в контроллере кэша памяти? Вместо загрузки только
страница памяти, необходимая для ссылки на память, также загружает следующую более высокую
страница в ожидании прогрессивного чтения вперед? Это было бы
исключить загрузку страниц ожидает прогрессии вперед через память, но
не исключил бы страницу нагрузка ожидает обратного прогрессирования через
память.

[..]

Я бы предложил провести тестирование на радикально отличающемся оборудовании. Большинство мобильных
устройства работают под управлением какой-то формы ARM SoC. Посмотрите, показывают ли тестовые случаи
подобный перекос на оборудовании Intel, как ПК или Mac. Если сможешь откопать
старый PowerPC Mac, даже лучше. Если они не показывают похожих результатов,
тогда это указывало бы на что-то уникальное на платформе ARM или ее
реализация Java.

[..]

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

Обновление 2: я провел тесты на ПК (Core i7 Nehalem architecture от Feb. 2009, 8 ГБ оперативной памяти, Windows 7). Я использовал C#.NET в проекте исходного кода .NET 2.0 (но установлен .NET 4 на машине). Мои результаты, с 25 миллионами экземпляров Message:

• связанный список: 57-60 ms


• массив: 60-63 ms

Направление чтения, казалось, не влияло на результаты.