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

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

Первоначальное название этой темы было «Полная итерация по массиву значительно быстрее, чем со связанным списком». Название было изменено в связи с более новыми результатами испытаний (представлено в Разделе 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 поле не будет использоваться вообще. В приведенном ниже коде создается массив из 1000 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 у нас нет типа значения, т.е. структуры, как в C #, которую мы могли бы хранить в массиве). Следовательно, «локальность ссылки» применяется только к элементам массива, и они указывают только адрес объектов. Следовательно, экземпляры Message (в общем) все еще могут быть «в любом месте» в памяти, поэтому «местность ссылок» не применяется к самим экземплярам. С этого момента похоже, что мы такие же, как в случае связанного списка: сами экземпляры могут находиться «в любом месте» в памяти: массив только гарантирует, что их ссылки хранятся в смежном блоке …

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

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

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

Мои догадки заключаются в следующем:

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

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

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

ОБНОВЛЕНИЕ: Поскольку было получено несколько комментариев, я хотел бы ответить на них ниже.

@irreputable:

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

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

@Torben комментирует:

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

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

Я ценю мысль, которую вы вложили в это, но я действительно не могу найти вопрос с вашего поста. 🙂 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 мс (хорошо, мы можем сказать, что это точно производительность массива, но на самом деле он немного быстрее в каждом тестовом случае , постоянно). Вместо 80 мс «обратного направления», Связанный список, он в два раза быстрее!

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

 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, но только в одном направлении (prefetch следующий более высокий адресный блок), то это исказит результаты в пользу тестов, которые выполняются в этом направлении.

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

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

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

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

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

Локально, на Core i7, я получаю несколько лучшие результаты для версии связанного списка в ~ 3.3 мс для всей итерации, против 3,5 мс для версии массива – при использовании исходной программы (которая выполняет итерацию списка ссылок в обратном порядке создания) , Поэтому я не вижу того же эффекта, который вы сделали.

Внутренний цикл для вашего теста, проверяющий значение val, оказывает большое влияние. Текущий цикл вызовет много ошибок, если JIT-компилятор достаточно умен, чтобы использовать CMOV или что-то подобное. Кажется, что в моем тесте это было – с тех пор, как я получил около 1 нс / итерацию для небольших итераций, которые соответствуют L1. 1 нс (около 3 циклов) не согласуется с полным предсказанием ветвления. Когда я изменил его, чтобы выполнить безусловный val + = msg.value1, версия массива получила значительное повышение, даже в 1 000 000 случаев итерации (что, вероятно, даже не поместится в L3).

Интересно, что одно и то же преобразование (val + = msg.value1) сделало версию связанного списка немного медленнее. При преобразовании версия массива была значительно быстрее при малых подсчетах итераций (внутри L2, и оба подхода были сопоставимы снаружи). Из суппорта:

  length method ns linear runtime 100 ARRAY 63.7 = 100 LINKED 190.1 = 1000 ARRAY 725.7 = 1000 LINKED 1788.5 = 1000000 ARRAY 2904083.2 === 1000000 LINKED 3043820.4 === 10000000 ARRAY 23160128.5 ========================== 10000000 LINKED 25748352.0 ============================== 

Поведение для небольших вычислений итераций проще объяснить – связанный список, который должен использовать преследовательский указатель, имеет зависимость данных между каждой итерацией цикла. То есть каждая итерация зависит от предыдущего, потому что адрес для загрузки происходит из предыдущего элемента. Массив не имеет такой же зависимости от данных – только инкремент i зависит, и это очень быстро (я, конечно, находится в регистре здесь). Таким образом, цикл может быть намного лучше конвейерным в массиве.

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

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

Надеюсь это поможет.