К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 34
Текст из файла (страница 34)
е, независимо от количества реально прочитанных байт обработка страницы занимает столько времени, как если бы она была прочитана целиком. Отсюда— потоковые алгоритмы должны обращаться как можно к меныиему количеству страниц, т. е. в пределах одной страницы располагайте данные максимально плотно, не оставляя пуапот. Но постойте, постойте! Ведь если это предположение верно (а оно верно), насыщение должно наступать уже при четырехкилобайтном шаге. Действительно, чем шаг в восемь или двенадцать килобайт хуже четырех? Во всех трех случаях загрузка атрибутов страниц происходит на каждой итерации, т. е. цикл выполняется максимально неэффективно. Между тем, кривая, перевалив за 4 Кбайт, пусть и уменьшает свой наклон (на Р-П! уменьшение наклона практически не заметно, но все же есть) и упорно продолжает свой рост.
Почему?! Дело в том, что атрибуты страниц не разбросаны хаотично по всей памяти, а объединены в особые структуры — Раве ТаЫе (Страничные таблицы или Таблицы страниц). Каждый элемент страничной таблицы занимает одно двойное слово, но т. к. минимальная порция обмена с памятью превышает эту величину, то при обращении к одной странице процессор загружает из памяти атрибуты еще семи (пятнадцати — в АГЬ(оп) страниц, сохраняя эту информацию в сверхоперативной памяти, Вот вам и ответ на вопрос! Умножение восьми (пятнадцати) элементов на четыре (размер одной страницы в килобайтах) как раз и дает те загадочные 32 Кбайт (64 Кбайт на Ай!оп), ограничивающие рост кривой. Теперь становится понятно, почему вынос ььэ ььаэ в отельный массив значительно ускорил обработку списка.
— элементы * ь и ььэ вишь стали располагаться плотнее и уместились в меньшее количество страниц. Почему вынос элемента чьэ ьььк ухудшил производительность — понять несколько сложнее. Количество страниц, правда, в последнем случае будет несколько больше, но ненамного. Давайте подсчитаем. Первый вариант структуры занимает: (э(геоГ(*цех!) + яхеоГ ((п!) " АТТВ 5!УЕ + + з(хеоГ(*оЬ) Ьобу)) * Х ЕЕЕМ = 64 Кбайт (16 страниц).
Второй вариант: (э!хеоГ(*цех!) + э(хеоГ(*оЬ3 ацг) + ыгеоГ(*оЬ) Ьоду)) * Х ЕЬЕМ + яхеоГ((пг) * Оперативная память * АЫСз)ч) АТТК 51УЕ * 14 ЕЕЕМ = 76 Кбайт (19 страниц). Ну, пусть за счет округления набежит еще пара страниц. Тогда 21/16 = 1,3. В то же время соотношения производительности первого и второго вариантов составляют 1,4 для АФ1оп и аж 1,8 для Р-П1. Куда ухолят такты?! А вот кула. Стратегия выделения памяти функции ньыь такова, что при запросе маленьких блоков каждый последующий выделенный блок имеет меньший адрес, чем предыдущий. Таким образом, элементы страничного каталога читаются в обратном направлении, а пакетный цикл памяти — в прямом.
Как следствие, процессору приходится дольше ожидать получения атрибутов "своей" страницы, — стоит ли удивляться снижению производительности? Подытоживая все вышесказанное, сформулируем следующее правило: для достижения максимальной производшпельности все станицы, к которым происходит обращение, следует использовать целиком. Причем, страницы должны запрашиваться в порядке возрастания их линейных адресов. Стратегия распределения данных по 0ЯАМ-банкам Сформулированное в конце предыдущего разлела правило ориентировано исключительно на потоковые алгоритмы, обращающиеся к каждой ячейке (и странице!) памяти всего один раз. А если обращение к некоторым страницам памяти происходит неоднократно, то имеет ли значение порядок их обработки или нет? На первый взгляд, если обрабатываемые страницы уже находятся в ТЕВ, то шаг чтения данных никакого значения не имеет.
А вот давайте проверим! Для этого добавим в нашу тестирующую программу Мешогу/11зкзгер.с цикл: ты Гь = о; ь <= вьзск зтзе; Ъ ь= 4*к~ ь +=- *(грь *1 ~ (ьпюр ь ' ь заставляющий систему спроецировать все страницы и загрузить их в Т1В до начала замера времени исполнения. (Читателям достаточно лишь раском- ментировать определение пнтьв). В результате получится следующий график зависимости времени трассировки списка от шага чтения (рис. 2.26). Смотри-ка, а ведь время трассировки списка, и правда, многократно уменьшилось! Зависимость скорости обработки от величины шага на первый взгляд как будто бы исчезла, но при внимательном изучении графика на нем все же обнаруживается мелкая "рябь".
Строгая периодичность "волн" указывает нам на то, что это не ошибка эксперимента, а некая закономерность. Весь вопрос в том, — какая? Падение производительности на гребнях волны достигает 30% и списывать эту величину на "мелкие брызги" побочных эффектов было бы с нашей стороны откровенной наглостью. Характер кривой объясняется особенностями организации оперативной памяти. Как нам уже известно, время доступа к памяти непостоянно и зависит !62 Глава 2 от множества факторов. Максимальная производительность достигается когда: а) запрашиваемые ячейки находя)пся в открытыт стралипах ()йАбу; б) ни страница, ни банк памяти в момент обрагцения к ним не находятся на регенерации.
Исходя из пунктов а) и б), попробуйте ответить на вопрос: как изменяется время доступа к ячейкам памяти в зависимости от шага чтения? Рис. 2.26. График, иллюстрирующий время обработки блока данных е зависимости от шага чтения при отсутствии и присутствии страниц в ТЬВ. Обратите внимание на "волнистостсл нижней кривой. Это — прямое следствие регенерации ОЯАМ-банков оперативной памяти Так-так-так (глубоко затянувшись и откинувшись на спинку стула).
Начнем с пункта а). Из самых общих рассуждений следует, что по мере увеличения шага время доступа будет пропорционально расти за счет более частого огкрытия страниц. Так будет продолжаться до тех пор, пока длина шага не достигнет длины одной !)ВАМ-страницы (гипичная длина которой 1, 2 и 4 Кбайт), после чего открытия страниц станут происходить прп кааюдом доступе к ячейке и кривая, достигнув максимума насыщения, перейдет в горизонтальное положение. Попробуем проверить наше предположение на практике, запустив тест, представленный в листинге 2.!6 (см.
исходный текст программы ~асс~!2]лпептогу~0КАМхчаче.с, которая находится на прилагаемом компакт-диске), поскольку масштаб графика (рис, 2.26) не очень-то подходит для точных измерений. От(еративнля память // шапка для Ного'а ргтпгт("ятерь); тот(рд веге=яткр ятгк)рд зете<=мах Ря ягек)рд вехе+=(яткр ятзк*яткр РАстою ) ргьпгт("цгъп",рд зете))ргепгт("Хптеше")) // основной цикл, различные шаги чтения тот(рд везе=яткр Втек)рд веге<=илх Ра шзк)рд вгге+=(яткр ятгк*ятер тдстой)) /* начало Вамера време и зьвнцзюнин */ // цикл, читаянмй память с заданным шагом // поскольку количество физической памяти ограничено, // а при большом шаге чтения все читаемые ячейки поместятся // в каше, приходится хитрить и представлять память как О кольцевой массив в общем, // этот алгоритм нагляднее описывается кодом, чем словаки Гог (Ь -0)Ь<рд згге)Ьь=ятКР ятяК) Рог(а=Ь)а<ВЬОСК Я1ЯЕ/втгеот(ьпы )ат-(рд агге/втзеот(гпс))) хт=р[а)/ А ЕМО(0] /* конец замера времени выполнении */ ргепгг("~гъб",Ах яет(0))) /* печать времени выполнения */ Ршкт Рйоайкяя(тбо*рд вгге/ийх Ра ятзк): Смотрите (рис.
2.27) — восходящая ветвь кривой действительно ведет себя в соответствии с нашими предположениями, но не достигает максимума насыщения, а переходит в чрезвычайно испещренную пиками и рытвинами местность. Время доступа к ячейкам с ростом шага меняется непрерывно, но график — к счастью! — обнаруживает строгую периодичность, что вселяет надежду на возможность его расшифровки. Собственно, это не график даже, а кладезь информации, раскрывающий секреты внутренней структуры и организации микросхем памяти.
Итак, начинаем... Закон № ! (возьмите себе на заметку) где есть яериедичиеств, там всегда есть структура. Значит, память — это не просто длинная цепочка ячеек, а нечто более сложное и неоднородное. Да, мы знаем, что память состоит из страниц, но одного этого факта явно недостаточно для объяснения формы кривой. Требуется что-то еще. Глава 2 Рис. 2.27. "Волны" памяти несут чрезвычайно богатую информацию о конструктивных особенностях используемых микросхем памяти. Вот только основные характеристики; а. — расстояние между концом одной и началом следующей ОНАМ-страницы того же самого ОНАМ-банка; Ь. — расстояние между началом одной и началом другой ОНАМ- страницы того же самого ОНАМ-банка (».
е, размер всех ОНАМ-банков); с. и о.— размер одной ОНАМ-страницы. Количество ОНАМ-банков равно Ь./о. Не замешаны ли здесь расслоение памяти на банки и их регенерация? Давайте прикинем. Время доступа к ячейке без регенерации занимает; 2 (КАК 1о САЯ Ре!ау) + 2 (САЯ Ре!ау) + ! ч- 1 + ! = 7 тактов, а с регенерацией: 2 (КА8 Ргес!тагйе) + 2 (КАБ го САБ Ре!ау) + 2 (САЯ Ре1ау) + 1 + 1 + + 1 = 9 тактов, что в 1,225 раз больше. Согласно графику (см.
рис, 2.27), время обработки блока на "вершине" горы составляет 22 892 б45 тактов, а у ее "подножия" — !8 610 240 тактов, что соответствует отношению в 1,23 раза. 11ифры фантастическим образом сходятся! Значит, наше предположение на счет регенерации верно! (Точнее, как осторожные исследователи, мы должны сказать "скорее всего, верно", но это было бы слишком скучно). Вообще-то, на атом можно было бы и остановиться, поскольку "закладываться" на физическую организацию оперативной памяти столь же безрассудно, как и вкладывать свои ваучеры в "МММ".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
