Под многомерными мы будем подразумевать массивы размерности 2 и более, а в
качестве иллюстрации ограничимся именно двумерным массивом:
Real*8 A(N,N)
и примитивной фортранной процедурой занесения нулей во все его элементы:
do i=1,N
do j=1,N
A(i,j) = 0
enddo
enddo
I
|
или вот так |
do j=1,N
do i=1,N
A(i,j) = 0
enddo
enddo
II
|
Информация к размышлению: примерно в 9 из каждых 10 виденных нами программах
отечественных авторов бездумно использовался вариант I.
В то же время большинство популярных зарубежных вычислительных программ явно
отдает предпочтение варианту II.
А не все ли равно? - заметит вдумчивый читатель, вроде бы и так правильно,
и эдак. Это безусловно верно, что правильно...
Но все же: давайте возьмем достаточно большое N и посмотрим, при каком
способе вложения этих двух циклов работа будет сделана быстрее. Здесь вдумчивый
читатель, мы надеемся, прервал чтение и попробовал сам, так что наша задача
заключается в том, чтобы обьяснить полученный им эффект. А для тех, кому было
лень пробовать самому, сразу же и скажем, в чем заключается этот самый эффект.
А именно: фрагмент слева работает НА ПОРЯДОК МЕДЛЕННЕЕ, чем фрагмент справа!
Как уже было сказано выше, эффект проявляется только при достаточно
больших N, таких, что память, требуемая для размещения массива А, превышает
реальный размер физической памяти Вашего компьютера.
Предположим, Вы являетесь счастливым обладателем IBM PC с памятью 128 Мбайт.
Значит ли это, что Вы не можете взять N > 4000 ( 8*4000*4000 ~ 128 Мбайт)?
Конечно нет! 32-разрядные адресные регистры IBM PC позволяют адресовать
виртуальную память обьемом в 2**32 байт, то-есть 4 Гбайта. Впрочем,
операционная система отнимает у Вас половину этого количества, но 2 гигабайта
все же Ваши. Вот и возьмите N = 5000. Не так уж это и много, не правда ли?
Конечно, Вы можете получить от системы сообщение, что файл подкачки слишком мал.
Это произойдет в том случае, если Ваш массив превысил обьем системного раздела
(partition) Вашего диска, но обычно этот обьем достаточно велик, уж никак не
менее 2 Гб. Если это не так, Вам вообще не стоит думать о решении вычислительных
задач.
Итак, Ваша программа обрабатывает массив, который заведомо целиком не помещается
в оперативной памяти Вашего компьютера. А память практически у всех современных
компьютеров имеет СТРАНИЧНУЮ ОРГАНИЗАЦИЮ, то-есть делится на много непрерывных
областей одинакового размера, именуемых страницами. Обычно размер страницы
равен 1-2 Кбайтам.
Возьмем для определенности 1 Кбайт. Тогда Ваш массив займет 8*5000*5000 байт
или примерно 200000 виртуальных страниц, в то время как в Вашем компьютере всего
128000 физических страниц. Вы конечно в курсе, что при обращении к отсутствующей
в данный момент виртуальной странице производится так называемый акт замещения,
в просторечии - подкачка. Мы не будем здесь распространяться о том, что это
такое, а просто попытаемся оценить количество актов замещения, случившихся при
выполнении обоих наших программных фрагментов.
Фортранный компилятор распределяет память для двумерных массивов по столбцам,
то-есть первые 8*N байтов будут хранить 1-й столбец матрицы A, следующие 8*N
байтов - 2-й столбец, ... , последние 8*N байтов хранят N-й столбец матрицы.
Нетрудно заметить, что фрагмент, который справа, сканирует память ПОСЛЕДОВАТЕЛЬНО,
строго в одном направлении, и перебирает свои страницы одну за другой, никогда не
возвращаясь к уже пройденной странице. Следовательно, при его исполнении случится
не более 200000 замещений страниц.
Фрагмент же слева "прыгает" по своей памяти большими скачками, перемещаясь
от A(i,j) не к рядом лежащему A(i+1,j), а к удаленному на 8*N байтов
(примерно на 40 страниц!) элементу A(i,j+1). Поэтому, когда в конце внутреннего
цикла по j он, перебрав 200000/40 = 5000 страниц, снова вернется к 1-й странице, она
с некоей вероятностью P уже будет укачана на диск. И так будет N раз, по числу
проходов внешнего цикла! А всего, стало быть, случится примерно P * N**2
замещений страниц.
Оценим величину P. При случайном выборе кандидата на замещение она равна примерно
1/40, однако если используется наиболее часто применяемый в операционных системах
LRU-алгоритм замещения страниц (укачивается страница, к которой долее всего не было
обращений), P будет довольно близко к 1 !
Итак, "прыгающая" программа инициирует не менее 25000000/40 замещений страниц.
Соотнося обе полученные оценки, имеем:
25 000 000 / ( 200 000 *40 ) = 25/8 ~ 3
To-eсть, вариант I гарантированно влечет втрое больше актов замещения страниц,
чем вариант II. Причем каждый акт замещения - это не один обмен с диском,
а целых 2 (одна страница укачивается, а другая подкачивается).
В практическом примере, который мы не поленились выполнить на своем компьютере,
этот коэффициент получился гораздо больше, более 10.
Теперь, надеемся, Вы с большим вниманием отнесетесь к своим вложенным циклам!
Для 3-мерного фортранного массива A(NDX,NDY,NDZ) правильной схемой вложения
циклов будет:
do kz=1,NDZ
do ky=1,NDY
do kx=1,NDX
A(kx,ky,kz) = 0
enddo
enddo
enddo
|
! сначала по последней размерности
! потом - по предпоследней
! и наконец - по первой!
|
А вот Паскаль и С-компиляторы хранят массивы ровно наоборот - "по строкам"!
Надо полагать, и в этих случаях Вы примете правильное решение.
