Работа с массивами

← →
Loginov Dmitry © (2006-01-11 12:20) [0]

Сделал для себя только что важное открытие :)
Оказывается, при обработке многомерных массивов в цикле порядок следования индексов должен соответствовать порядку следования счетчиков цикла.

Пример:

var
Ar: array[1..1000, 1..1000];
I, J: Integer;

begin

// ТАК ПРАВИЛЬНО!
for I := 1 to 1000 do
for J := 1 to 1000 do
Ar[I, J] := Random;

// ТАК НЕПРАВИЛЬНО!
for I := 1 to 1000 do
for J := 1 to 1000 do
Ar[J, I] := Random;
end.

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

Почему-то в книгах про этот эффект я материала не нашел (или книги не те были :)))

Кто нибудь может объяснить, почему так получается?

← →
Sandman29 © (2006-01-11 12:24) [1]

>Кто нибудь может объяснить, почему так получается?

Ассемблер может объяснить. Оптимизация адресной арифметики, наверное.

← →
Суслик © (2006-01-11 12:25) [2]

наверное дело в том, что двумерные массивы расположены в памяти так:
массив по второму индексу для первого занчения первого индекса,
массив по второму индексу для второго занчения первого индекса,
и т.д.

в первом случае получается последовательный доступ к массивы

← →
Владислав © (2006-01-11 12:27) [3]

> Кто нибудь может объяснить, почему так получается?

Кеш процессора?..

← →
wal © (2006-01-11 12:29) [4]

> Кто нибудь может объяснить, почему так получается?
Все дело в организации n-мерных массивов в памяти. В результате в памяти все-равно все одномерное и получаем следующее:
1.1 1.2 1.3 ... 1.1000 2.1 2.2 2.3 ... 2.1000 ... 1000.1 1000.2 1000.3 ... 1000.1000
В первом варианте доступ к памяти илет последовательно, как написано выше, во втором мотаемся по памяти туда-сюда и такой хороший механизм, как кэширование, перестает работать.

С уважением.

← →
Альф (2006-01-11 12:33) [5]

.... эээ ... эта ... а последовательный доступ к памяти по сравнению с random seek :)
можно еще на разных конфигурациях попробовать, с разными процессорами, объемами кеша, попереключать банки, попробовать двуканальность и т.п.

← →
Loginov Dmitry © (2006-01-11 13:09) [6]

> такой хороший механизм, как кэширование, перестает работать

Доступ к элементам массива осуществляется по следующей формуле

Real(Pointer((Adr + ((Row - 1) * ColCount + Col - 1) shl 3))^) := Value;

Тут мы сначала определяем адрес массива (Adr := Integer(@Ar))

В общем, обращение к элементам по этой формуле выполняется с такой же скорость, что и для таком обращении: Ar[Row, Col] := Value;

Как для этой формулы выполняется кэширование?

← →
wal © (2006-01-11 13:29) [7]

> Real(Pointer((Adr + ((Row - 1) * ColCount + Col - 1) shl
> 3))^) := Value;
А смысл? Ar[Row,Col] := Value сделает то же самое.

> Как для этой формулы выполняется кэширование?
Никак. Кэширование делается не для формул, а для памяти. Лучший случай, когда данными из памяти используются последовательно, а не случайным образом.

← →
Loginov Dmitry © (2006-01-11 13:35) [8]

Насколько я понимаю, кэширование - это запоминание каких-либо данных. А в нашем случае что запоминается, какие данные?

> Loginov Dmitry © (11.01.06 13:35) [8]
> Насколько я понимаю, кэширование - это запоминание каких-
> либо данных. А в нашем случае что запоминается, какие данные?

Следующие сразу за запрошенными - упреждающее кеширование чтения.

> Насколько я понимаю, кэширование - это запоминание каких-либо
> данных.
Абсолютно верно.

> А в нашем случае что запоминается, какие данные?
В нашем случае, все выглядит примерно так:
Когда ты обращаешься к Ar[1,1] система (не ОС, а железо) предполагает, что следующее обраащение будет к Ar[1,2], и считывает из памяти ДО того, как реально было обращение. Если следующее будет именно [1,2], то тебе подадут уже готовенькое, иначе готовенькое выкидывается за ненадобностью, и снова лезем в память (а это достаточно долго) за нужным значением.

С уважением.

> Real(Pointer((Adr + ((Row - 1) * ColCount + Col - 1) shl > 3))^) := Value;
> А смысл? Ar[Row,Col] := Value сделает то же самое.

Скорей всего имеется Имеется в виду алгоритм вычисления адреса ячейки массива.

Массивы начинающиеся с нуля быстрее т.к. не придётся вычислять row-1 и Col-1.
По скорости судя по всему, массив может быть разбросан по разным страницам памяти. Ксати интересно, из чего у тебя Array? Страница памяти в Windows если не ошибаюсь - 4 Кб.

> Никак. Кэширование делается не для формул, а для памяти.
> Лучший случай, когда данными из памяти используются последовательно,
> а не случайным образом.

Это то да, но какой-таки проц используется? Кэширование понятие растяжимое.

Про скорость массивов ветка была, длинная, Суслик должен помнить.

> Ксати интересно, из чего у тебя Array

Ar: array[1..1000, 1..1000] of Real;

> Это то да, но какой-таки проц используется?

Celeron 1300

Работа с массивами Найти похожие ветки