Под многомерными мы будем подразумевать массивы размерности 2 и
более, а в качестве иллюстрации ограничимся именно двумерным массивом:
Real*8 A(N,N)
и примитивной фортранной процедурой занесения нулей во все его элементы
|
так: |
do i=1,N
do j=1,N
A(i,j) = 0
enddo
enddo
(Вариант 1)
|
или вот так: | do j=1,N
do i=1,N
A(i,j) = 0
enddo
enddo
(Вариант 2)
|
Информация к размышлению: примерно в 9 из каждых 10 виденных нами
программах отечественных авторов бездумно использовался вариант 1.
В то же время большинство популярных зарубежных вычислительных программ
явно отдает предпочтение варианту 2.
А не все ли равно? - заметит вдумчивый читатель, вроде бы и так
правильно, и эдак. Это, безусловно, верно, что правильно...
Но все же: давайте возьмем достаточно большое N и посмотрим,
при каком способе вложения этих двух циклов работа будет сделана быстрее.
Здесь вдумчивый читатель, мы надеемся, прервал чтение и попробовал сам,
так что наша задача заключается в том, чтобы объяснить полученный им эффект.
А для тех, кому было лень пробовать самому, сразу же и скажем,
в чем заключается этот самый эффект.
А именно: фрагмент слева (Вариант 1) работает НА ПОРЯДОК
МЕДЛЕННЕЕ, чем фрагмент справа!
Как уже было сказано выше, эффект проявляется только при достаточно
больших 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). Поэтому при обращении к любому элементу массива
соответствующая страница с некоей вероятностью P уже будет укачана
на диск. А всего, стало быть, случится примерно P * N**2
замещений страниц.
Оценим величину P. При случайном выборе кандидата на замещение
она равна примерно 1/40, поскольку программа "прыгает по памяти" с шагом 40
страниц. Однако, если используется наиболее часто
применяемый в операционных системах LRU-алгоритм замещения
страниц (укачивается Least Recently Used страница,
к которой долее всего не было обращений),
P будет довольно близка к 1! Итак, "прыгающая" программа
инициирует не менее 25000000/40 замещений страниц.
Соотнося обе полученные оценки, имеем:
25 000 000 / ( 200 000 *40 ) = 25/8 ~ 3
То есть вариант 1 гарантированно влечет втрое больше актов
замещения страниц, чем вариант 2. Причем каждый акт замещения -
это не один обмен с диском, а целых 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
|
! сначала - по последней размерности
! потом - по предпоследней
! и, наконец - по первой!
|
А вот Паскаль и С-компиляторы хранят массивы ровно
наоборот - "по строкам"! Надо полагать, и в этих случаях Вы примете
правильное решение.
|
