К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 35
Текст из файла (страница 35)
С другой стороны: вполне можно выделить ряд рекомендаций, общих для всех или, по крайней мере, большинства моделей памяти. Особого прироста производительности их со- Оперативная память !65 блюдение, впрочем, не принесет, но вот избежать более чем 20 — 30%-ного падения производительности — поможет. Тонкая оптимизация для "гурманов" В первую очередь нас будет интересовать схема отображения физических ячеек памяти на адресное пространство процессора !см.
разд. "Отображение физических ЮКАМ-адресов на логические" этой главы), а также количество и размер банков, длина страниц и все остальные подробности. Достаточно очевидно, что гребень волны соответствует той ситуации, когда каждое обращение к памяти попадает в регенерируюшийся банк. Отсюда: расстояние между двумя соседними гребнями равно произведению длины одной ЙКАМ-страницы на количество банков (в нашем случае — 8 Кбайт), что удовлетворяет следующим комбинациям: ! Кбайт (длина ОВАМ-страницы) х х 8 (банков), 2 х 4, 4 х 8 и 8 х 1. Можно ли определить какой именно тип памяти используется в действительности? Да, можно и ключ к этому дает ширина склона "горы" (на рис.
2.27 она обозначена символом а.). Легко доказать, что ширина склона "горы" в точности соответствует длине одной ВйАМ-страницы. Действительно, пусть з — ллина одной страницы, а Х— количество банков. Тогда, расстояние между концом одной и началом другой страницы всякого банка равно: (Х вЂ” 1)*з, (2.1) соответственно, расстояние между двумя страницами одного банка равно Х*з, (2.2) а расстояние между началом одной и концом другой страниц (Х + 1)*з.
(2.3) Ситуация, определяемая формулой (2.1), соответствует самому подножию горы, — если шаг чтения меньше чем (Х вЂ” !)*з, то, независимо от смешения ячейки в странице, следующая запрашиваемая ячейка гарантированно не находится в том же самом банке. Но что произойдет, если шаг возрастет хотя бы на единицу? Правильно, при чтении последней ячейки одной ОВАМ-страницы очередная ячейка придется на следующую страницу того же самого банка! (Если не совсем понимаете, о чем идет речь, попробуйте изобразить это графически). Дальнейшее увеличение шага будет захватывать все больше и больше ячеек, вызывая неуклонное снижение производительности. Так будет продолжаться до тех пор, пока шаг чтения не сравняется со значением, определяемым формулой (2.2), после чего начнется обратный процесс. Теперь все больше и больше ячеек будут "вылетать" в страницы соседнего банка, уже готового к обработке запроса Отсюда: ширина склона "горы" равна М"з — (Х вЂ” 1)'з.
Раскрываем скобки и получаем: Х*з — Х*з + з = з, что и требовалось доказать. Зная же з, вычислить Х будет совсем не сложно: количество банков равно отношению рас- Глава 2 стояния между двумя никами к ширине склона одной "горы", т. е. приведенный график соответствует четырехбанковой памяти с ллиной страницы в 2 Кбайт.
Бесспорно, эта методика весьма перспективна в плане создания тестирующей программы (надо же знать какое оборудование вам подсунули продавцы), но поможет ли она нам в оптимизации программ? Ввиду большого количества "разношерстных" моделей памяти, величина оптимального (неоптимального) шага чтения памяти на сталии разработки программы неизвестна и должна определяться динамически на этапе исполнения, подстраиваясь под конкретную аппаратную конфигурацию. Причем, сказанное относится не только к трассировке списков и других ссылочных структур, но и к параллельной обработке нескольких потоков данных.
Рассмотрим, например, такой код (листинг 2.17). Спс *рГн юе рсо рг=ссысс!вьсск згвк*вь ссщс Ы !; р2- саысс(вьсск згкв*сьпесегьпм ы Ппснсср!рг,рз, вьсск ззкк*с'пссгспы! Как вы думаете: можно ли считать этот фрагмент программы оптимальным? А вот и нет! Ведь никто не гарантирует, что блоки памяти, возвращенные функцией нсы, не начинаются с одного и того же банка. Скорее, нам гарантировано обратное. Если размер блока превышает 512 Кбайт (а про обработку вот таких гигантских массивов памяти мы и говорим!), он не может быть размещен "в куче" и необходимую память приходится выделя~ь с помощью функции ч с 1«1т %1п32 АР!. К несчастью, возвращаемый ей адрес всегда выравнивается на границу 64 Кбайт, т.
е, величину, крарнную любым разумным сочетаниям АГ'з. Таким образом, попросту говоря, все выделяемые функцией ззсс блоки намяти начинаютсн с одного и того же банка! А это не есть хорошой Точнее — это просто "кретинизм"! Неужели разработчики системы проглядели такой ляп? Что ж, это не сложно проверить,— достаточно написать программку (листинг 2.18), выделяющую блоки памяти разного размера и анализирующую значения 11 и 12 битов (эти биты отвечают за выбор РВАМ-банка, см.
рис. 2.12). (Полный исходный текст программы читатель найдет в файле ~кто~[2!.пзепзогу~Ьапк.гпаПос.с, который находится на прилагаемом компакт-диске.) Оперативная память 4бегьпе опе Ь1Г Ебетгпе Гмо Ьгс 11 // эти биты отвечают.. 12 // ...эа выбор банка 4бег1пе МАЯК ( (1« опе Ь11) +(1« Гио Ьгс) ) Рбетгпе ггг(а) ((()пг) вш11ос(а) а маяк)» опе ьгг) вшьп () гпп а,Ь! РВ1МТ( ТЕХТ("= = Определение номеров ОРАМ-банков = = =~п"))1 РК1МТ Т1ТЬЕ1 Рггпог("В1ССКАп Я12Е и ВАМК - — -~п") рггпГГ("- ! Тог(а ВТЕР ГАСток) а < МАХ МЕМ Я12Е; ( — — — — Ап") а е ЯтЕР РАСТОЮ рггпГТ(ша04б:",а/1024)1 Тот (Ь = 01 Ь < М 1ТЕВ1 Ь++) рг)псе("Атьх",ггг(а))) ргьпГЕ("1п")) Результат работы этой программы будет следующим: ВЬССК Б1ЕЕ (Кб) и ВАМК 0100: 0 2 0 2 0 0200: 0 О 0 0 0 0300: О 2 0 2 0 0400: 2 2 2 0 0 0500: 2 0 2 0 2 4бетгпе М 1ТЕК Фбеаьпе ВТЕР РАСТОВ $бе11пе МАХ МЕМ Я1ЕЕ 9 // кол-во итераций (100*1024) // шаг приращения шага раэмера памяти (1024*1024) !вв Глава а 0000: 0 0 0 О 0 0 0 0 0 0700: 0 0 0 0 0 0 0 О 0 0800: О 0 0 О 0 0 0 0 0 0900: 0 0 0 0 0 0 0 0 0 1000: 0 0 0 О 0 0 0 0 0 Смотрите — до тех пор, пока размер выделяемых блоков не достиг 512 Кбайт, нам попадались как удачные, так и неудачные комбинации, но, начиная с 5!2 Кбайт, все выделенные блоки, действительно, начинаются с одного и того же банка.
Что же делать? Писать собственную реализацию функции гов? Конечно же, нет! Достаточно, динамически определив значения )Ч и б, проверить соответствующие биты в адресах, возращенных функцией ыос. И если они вдруг окажутся равны, то нужно увеличить любой из адресов на величину б (естественно, размер запрашиваемого блока необходимо заблаговременно увеличить на эту же самую величину). В результате мы теряем от 1 до 4 Кбайт, но получаем взамен, по крайней мере, 20 — 30%-ный выигрыш в производительности. Это тот редкий случай, когда знание приемов "черной магии" позволяет совершенно непостижимым для окружающих способом увеличить быстродействие чужой программы, добавив в нее всего одну строку, даже без анатиза исходных текстов.
Маленькое лирическое отступление. Однажды поручили мне в порядке конкурсного задания оптимизацию одной программы, уже и без того оптимизированной — по понятиям заказчика — "дальше не купа". Собственно, проблема заключалась в том, что львиная доля процессорного времени уходила не на вычисления, а на обмен с оперативной памятью, причем размер обрабатываемых данных был действительно сокращен до предела и заказчик пребывал в абсолютной уверенности, что оптимизировать тут более нечего.
Каково же было его удивление, когда я прямо на его глазах бегло пробежался контекстным поиском по исходным тестам и, даже не удосужившись запустить профилировщик, просто воткнул в нескольких местах код а'!а р += 9*гсза, после чего программа заработала приблизительно на треть быстрее. Он (заказчик) долго и недоверчиво спрашивал: уверен ли я, что зто не случайность и под всяким ли "железом" и операционной системой это будет работать? Нет, не случайность.
Уверен. Будет работать под любой ОС семейства %!пдот99 и дочти на любом "железе": микросхемах памяти с организацией 2 в 4, 4 а 2, 4 а 2, 4 х 4, а на чипсетах серии !пге! 815 !и других подобным им) вообще на всех типах памяти. Эти чипсеты отображают 8- и 9- биты номера столбца на 25- и 26-й биты линейного адреса, а вовсе не на 11- и 12-биты, как того следовало ожидать. Оперативная память Попросту говоря, программная длина 0ЯАМ-страниц на таких чипсетох всегда равна 2 Кбайт, потому на всех модулях памяти, имеюи~их, по крайней мере, четырехбанковую организацию (а все модули емкостью от б4 Мбайт и более такую организацию и имеют), сдвиг указателя на 4 Кбайт гарантированно исключает попадание в тот же самый 0КАМ-банк. Конечно, закладываться на такие особенности аппаратуры — лурной тон и в программах, рассчитанных на долговременное использование, настоятельно рекомендуется не лениться, а определять длину РВАМ-страниц автоматически или, на худой конец, позволять изменять эту величину опционально.
Планирование потоков данных С проблемами, сопутствующими параллельной обработке нескольких блоков памяти (далее по тексту — потоков данных), мы уже столкнулись в предыдущем разделе. Здесь же этот вопрос будет рассмотрен более подробно. Итак, первое (и главное) правило — добиться, чтобы потоки начинались с различных РйАМ-банков (за ТЕВ можно не беспокоиться, т. к. при параллельной обработке необходимые страницы уже там будут). Поскольку большинство современных молулей памяти имеет четырехбанковую организацию, очевидно, что работа с пятью и более потоками данных — нецелесообразна.
Однако это лишь вершина айсберга. Здесь, в "зарослях тростника", притаилось немало тонкостей. Возьмем, например, руководство по чипсету Ч(А КТ133. В нем черным по белому написано; "Биррот тах?тит 1б-банк 1пгег(еаие (й е., 1б раеез орел ейтийапеоиз!у)" — "Поддерживается чередование максимум 1б-ти банков (т.
е. 1б-ти страниц могут быть открытыми одновременно)...". Означает ли это, что на чипсете Ч!А КТ133 (и других подобных ему чипсетах) мы можем обрабатывать до 16 потоков данных? И да, и нет, причем скорее нет, чем да. Ключевое слово "максимум". Если воткнуть в системную плату всего один Р1ММ с четырехбанковой организацией, то никакие конструкторские ухищрения не позволят чипсету удержать открытыми пять и более страниц РВАМ-памяти. Поскольку микросхема памяти имеет всего лишь один сигнальный вывод ЙАБ, то для открытия еще одной страницы в том же самом банке этот сигнал придется сбросить, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
