Самый быстрый способ циклично выполниться через 2-й массив?

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

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

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

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

у вас, вероятно, будет меньше промахов кеша. Скорее всего.

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

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

у вас, вероятно, будет меньше промахов кеша. Скорее всего.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

index = row * numColumns + col;

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

index = index++;

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

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

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

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