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

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

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

---

РАЗДЕЛ ОДИН: Оригинальный тестовый пример

Для полного однонаправленного последовательного обхода известно, что связанный список и массив имеют схожую производительность, но из-за удобства кэш-памяти (эталонной локальности) смежного массива он может выполнять (немного) лучше. Чтобы узнать, как это работает на практике (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 ms, а второй тест дает 80-85 ms. Кажется, что итерация связанного списка на 100% медленнее.

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

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

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

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

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

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

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

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

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

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

@irreputable:

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

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

@Torben comments:

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

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

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

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

---

РАЗДЕЛ ВТОРОЙ: Модифицированные тестовые случаи

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

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

Я изменил структуру связанных списков таким образом, что направление его указателей 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 ms! Исходный тестовый пример составил 40-41 мс.

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

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

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

Подводя итоги моих результатов:

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

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

Любые идеи?

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

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

[..]

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

[..]

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

ОБНОВЛЕНИЕ 2: Я провел тесты на ПК (архитектура Core i7 Nehalem с февраля 2009 года, 8 ГБ оперативной памяти, Windows 7). Я использовал С#.NET в проекте исходного кода .NET 2.0 (но .NET 4 установлен на компьютере). Мои результаты с 25 миллионами экземпляров Message:

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

Направление чтения, по-видимому, не влияло на результаты.