Самый быстрый способ прокрутки массива 2d?

Я просто наткнулся на это сообщение в блоге. Автор показывает два примера кода, которые проходят через прямоугольник и вычисляют что-то (моя догадка заключается в том, что вычислительный код является просто заполнителем). На одном из примеров он просматривает прямоугольник вертикально, а с другой - по горизонтали. Затем он говорит, что второй - самый быстрый, и каждый программист должен знать, почему. Теперь я не должен быть программистом, потому что для меня это выглядит точно так же. Может ли кто-нибудь объяснить это мне?

Спасибо.

Ответ 1

Когерентность кеша. Когда вы сканируете по горизонтали, ваши данные будут ближе друг к другу в памяти, поэтому у вас будет меньше промахов в кеше, и, следовательно, производительность будет быстрее. Для небольшого прямоугольника это не имеет значения.

Ответ 2

Ответ был принят, но я не думаю, что это целая история.

Да, кеш - большая часть причины, по которой все эти элементы должны храниться в памяти в некотором порядке. Если вы индексируете их в том порядке, в котором они хранятся, вы, вероятно, будете иметь меньше промахов в кеше. Скорее всего.

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

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

Ответ 3

Кэш действительно является причиной, но если вы хотите узнать мясо аргумента, вы можете взглянуть на "Что каждый программист должен знать о памяти" У. Дреппера:

http://people.redhat.com/drepper/cpumemory.pdf

Ответ 4

Чтобы немного расширить предыдущие ответы:

Обычно, как программисты, мы можем рассматривать адресную память наших программ как плоский массив байтов от 0x00000000 до 0xFFFFFFFF. Операционная система зарезервирует некоторые из этих адресов (все они ниже 0x800000000, скажем) для собственного использования, но мы можем делать то, что нам нравится, с другими. Все эти ячейки памяти находятся в ОЗУ компьютера, и когда мы хотим прочитать их или написать им, мы выдаем соответствующие инструкции.

Но это не так! Существует множество сложностей, связанных с простейшей моделью памяти процесса: виртуальная память, свопинг и кеш.

Говорить с ОЗУ занимает довольно много времени. Это намного быстрее, чем переход на жесткий диск, так как нет никаких вращающихся пластин или магнитов, но он все еще довольно медленный по стандартам современного процессора. Поэтому, когда вы пытаетесь читать из определенного места в памяти, ваш процессор не просто считывает это место в регистр и называет его хорошим. Вместо этого он считывает это местоположение и/или соседние местоположения /, в кеш процессора, который живет на процессоре и может быть доступен гораздо быстрее, чем основная память.

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

Теперь мы видим, почему второй фрагмент кода быстрее первого. Во втором примере мы сначала получаем доступ к a[0], b[0] и c[0]. Каждое из этих значений кэшируется вместе со своими соседями, например a[1..7], b[1..7] и c[1..7]. Затем, когда мы получаем доступ к a[1], b[1] и c[1], они уже находятся в кеше, и мы можем быстро их прочитать. В конце концов, мы переходим к a[8] и снова должны вернуться в ОЗУ, но семь раз из восьми мы используем красивую быструю кэш-память вместо неуклюжей медленной памяти RAM.

(Итак, почему бы не обращаться к a, b и c удалять друг друга из кеша? Это немного сложно, но по существу процессор решает, где хранить заданное значение в кеше по его адресу, поэтому три объекта, которые не находятся рядом друг с другом пространственно, вряд ли будут кэшироваться в одно и то же место.)

В отличие от этого, рассмотрим первый фрагмент из сообщения lbrandy. Сначала мы читаем a[0], b[0] и c[0], кеширование a[1..7], b[1..7] и c[1..7]. Затем мы получаем доступ к a[width], b[width] и c[width]. Предполагая, что ширина равнa >= 8 (что, вероятно, так или иначе, мы бы не заботились об этой низкоуровневой оптимизации), нам нужно снова перейти в ОЗУ, кэшируя новый набор значений. К тому времени, когда мы дойдем до a[1], его, вероятно, вышвырнут из кеша, чтобы освободить место для чего-то еще. В не-необычном случае трио массивов, которые больше, чем кеш процессора, вероятно, что каждый из них будет читать/будет пропускать кеш, значительно ухудшая производительность.

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

Ответ 5

Да, "когерентность кеша"... конечно, это зависит, вы можете оптимизировать распределение памяти для вертикального сканирования. Традиционно видеопамять выделяется слева направо, сверху вниз, назад. Я уверен, что дни экранов ЭЛТ, которые вытаскивали строки сканирования одинаково. Теоретически вы можете это изменить, хотя все это говорит о том, что нет горизонтального метода.

Ответ 6

Причина в том, что на самом деле нет такой вещи, как 2-мерный массив, когда вы переходите на аппаратный уровень того, как выделяется память. Поэтому, сканируя "вертикально", чтобы перейти к следующей ячейке, которую нужно посетить, вы выполняете операцию в этих строках.

Для двумерного массива, индексированного как (строка, столбец), это нужно преобразовать в массив одномерного измерения массива [index], поскольку память на компьютере является линейной.

Итак, если вы сканируете вертикально, следующий индекс рассчитывается как:

index = row * numColumns + col;

однако, если вы сканируете по горизонтали, следующий индекс выглядит следующим образом:

index = index++;

Единственное дополнение будет меньше кодов op для CPU, а затем умножение AND добавление, и, следовательно, горизонтальное сканирование происходит быстрее из-за архитектуры памяти компьютера.

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