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

Question

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

Спасибо.

Answer 1

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

Answer 2

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

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

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

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

Answer 3

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

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

Answer 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], и нам приходится снова обращаться к ОЗУ, но семь раз из восьми мы используем хорошую быструю кеш-память вместо громоздкой медленной оперативной памяти.

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

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

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

Answer 5

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

Answer 6

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

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

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

index = row * numColumns + col;

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

index = index++;

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

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