Форум: "Прочее";
Текущий архив: 2006.02.05;
Скачать: [xml.tar.bz2];
ВнизРабота с массивами Найти похожие ветки
← →
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]Насколько я понимаю, кэширование - это запоминание каких-либо данных. А в нашем случае что запоминается, какие данные?
← →
Igorek © (2006-01-11 13:49) [9]
> Loginov Dmitry © (11.01.06 13:35) [8]
> Насколько я понимаю, кэширование - это запоминание каких-
> либо данных. А в нашем случае что запоминается, какие данные?
Следующие сразу за запрошенными - упреждающее кеширование чтения.
← →
wal © (2006-01-11 13:52) [10]
> Насколько я понимаю, кэширование - это запоминание каких-либо
> данных.
Абсолютно верно.
> А в нашем случае что запоминается, какие данные?
В нашем случае, все выглядит примерно так:
Когда ты обращаешься к Ar[1,1] система (не ОС, а железо) предполагает, что следующее обраащение будет к Ar[1,2], и считывает из памяти ДО того, как реально было обращение. Если следующее будет именно [1,2], то тебе подадут уже готовенькое, иначе готовенькое выкидывается за ненадобностью, и снова лезем в память (а это достаточно долго) за нужным значением.
С уважением.
← →
tesseract © (2006-01-11 22:41) [11]
> Real(Pointer((Adr + ((Row - 1) * ColCount + Col - 1) shl > 3))^) := Value;
> А смысл? Ar[Row,Col] := Value сделает то же самое.
Скорей всего имеется Имеется в виду алгоритм вычисления адреса ячейки массива.
Массивы начинающиеся с нуля быстрее т.к. не придётся вычислять row-1 и Col-1.
По скорости судя по всему, массив может быть разбросан по разным страницам памяти. Ксати интересно, из чего у тебя Array? Страница памяти в Windows если не ошибаюсь - 4 Кб.
> Никак. Кэширование делается не для формул, а для памяти.
> Лучший случай, когда данными из памяти используются последовательно,
> а не случайным образом.
Это то да, но какой-таки проц используется? Кэширование понятие растяжимое.
Про скорость массивов ветка была, длинная, Суслик должен помнить.
← →
Loginov Dmitry © (2006-01-11 22:48) [12]
> Ксати интересно, из чего у тебя Array
Ar: array[1..1000, 1..1000] of Real;
> Это то да, но какой-таки проц используется?
Celeron 1300
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2006.02.05;
Скачать: [xml.tar.bz2];
Память: 0.48 MB
Время: 0.013 c