К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 37
Текст из файла (страница 37)
ео~(ь=щ ь<в.оск з ав; ь =зтвг гхстов) Глава 2 х ~-.— * Нпп '~ ~ Мпп1р а а у += *ыпт М (мпыр + а а свьтп зтгв втер глстоятг | На системе !пге! Р-!1! 733/! 33/!00/!В! 5ЕР/2?4 время обработки блока практически не зависит от величины расстояния между потоками (свьтп зтгг), естественно, если при этом не происходит постоянного попадания в один и тот же банк, но эту проблему мы уже обсудили Гсаь разд. "Стратегня распределения данных ло РйА)т1-банкам" этой главы). Казалось бы, какие тут могут быть сюрпризы? А вот взпигпите на верхнюю кривую графика (рис. 2.31), иллюстрирующую поведение системы АМО Аг!т1оп 1400/100/100%!А КТ133/4х4.
Рис. 2.31. Демонстрация особенностей механизма буферизации на чипсете Ч!А КТ1ЭЭ. Смотрите, при узком "зазоре" между виртуальными потоками время их обработки чудовищно возрастает Оказывается, параллельная обработка данных, расположенных на расстоянии менее 512 байт друг от друга, крайне невыгодна и несет чуть ли не двукратные издержки быстродействия. Ох, уж эта система предвыборки в чипсете у!А КТ!ЗЗ! Конечно, можно просто заявить: "Используйте 1пге1, и у вас Оперативная память не будет никаких проблем", но разработчик, заботящийся о своих клиентах, не должен ограничивать свободу выбора поставщика. Нравится кому-то Ч1А? — Да ради бога! — Мы просто сместим начало каждого логического потока на 512 байт относительно предыдущего! Если количество требуемых потоков невелико, то с потерей нескольких килобайт можно и смириться, в противном случае возникнут попадания в регенерируемые банки и, как следствие, упадает производительность.
Есть ли выход? Увы, общих решений нет. Правда, можно усложнить механизм трансляции адресов, расположив потоки приблизительно следующим образом: рО, 512 + р1, р2, 512 + рЗ, тогда, при условии что потоки обрабатываются в строгой очередности, каждое обращение будет осуществляться без накладных расходов. Но что произойдет, если придется попеременно обращаться к данным потоков р1 и рЗ? Правильно — "тормоза". Чтобы их избежать, вам придется подстроить механизм трансляции адресов потоков под алгоритм их обработки или вообще отказаться от оптимизации под Ч!А. Хорошо, с минимальным расстоянием мы разобрались.
А существует ли максимально разумное расстояние между потоками? Да, существует. И равно оно, как не трудно догадаться, — ()Ч вЂ” 1)*з (на самом деле — даже ()ч — 2)*з при хаотичной обработке блоков, но грамотным планированием потоков этой проблемы легко избежать). Отсюда следует, что в один физический поток можно вместить не более чем ()Ч вЂ” 1)*з/з!геок(е!етепг) логических потоков, где гйгео((е(егпепг) — размер элементов потока. Так, для массивов, состоящих из элементов типа (пг32, максимально разумное количество логических потоков равно: (4 — 1)*2048/4 = 1,53б.
Не правда ли, это число более чем достаточно для всех — мыслимых и нечыслимых — задач? Однако при этом максимально разумное количество физических потоков равно одному. Ведь все РВАМ-банки уже задействованы и при обращении ко второму физическому потоку никто не гарантирует, что мы не попадаем в регенерируюшийся банк. Впрочем, тут все зависит от алгоритма работы с потоками. Вполне возможно добиться согласованной работы и четырех физических потоков, каждый из которых содержит по полторы тысячи логических. Но, постойте, сколько же это всего потоков получается? Шесть тысяч сто сорок чеаыре?! Трудно представить себе задачу, реально нуждающуюся в таком количестве потоков.
Даже если это вычислительный кластер какой... Хотя автору доводилось сталкиваться и с большим количеством параллельно обрабатываемых блоков данных — в системе, моделирующей движения звезд в галактиках и пытающейся тем самым поближе подобраться к загадочной "темной материи", но это уже тема другого разговора. На персональных компьютерах пока подобные процессы не моделируют.
(7В Глава 2 Обработка памяти байтами, двойными и учетверенными словами В своей повселневной практике программисты сталкившотся с самыми различными типами ланных: байтами, двойными и учетверенными словами. Какие жс из них наиболее эффективны? Среди программистов нет единого мнения на этот счет. Одни руководства рекомендуют обрабатывать большие блоки памяти двойными словами и советуют навсегда забьпкн что ~акое "байт". Другие же соблазняют команлами мультимелийной обработки данных, способными "заглатывать", по крайней мере, 64 бита (целое учетверенное слово!) за один раз. Ближе всего к истине полобралось первое утверждение, да и то с некоторыми оговорками. Рис. 2.32. Сравнительная эффективность чтении/записи больших блоков памяти байтами, двойными и учетверенными словами.
Как видно: чтение памяти лучше всего осуществлять двойными словами, а запись — либо бай ~ами, либо двойными словами. Обработка памяти учетверенными словами всегда осуществляется наименее эффективно Несложная тестовая программа (см. программу тягот,)21птепзогут,г)%ОКГ).с, исходный текст который можно найти на прилагаемом компакт-лиске) убедительно доказывает, что чтение памя~и двойными словами действительно происходит на 30 — 40% быстрее побайтового чтения (рис. 2.32). А вот чте- Оперативная память ние памяти учетверенными словами (с использованием команды моче) на РП1 733/! 33/100/1815ЕР отстает от двойных слов на добрых 25%! Правда, на АМ(3 Аг)))оп 1050/100/100/Ч1А КТ133 разрыв в производительности составляет всего 5%, но это никак не меняет сути вещей.
Чтение больших блоков памяти учетверенными словами крайне нецелесообразно. (Вот компактные блоки памяти, — другое дело, но это мы обсудим далее, — см, главу 3). Интересная ситуация складывается с записью в память. И байты, и двойные слова в этом случае оказываются одинаково эффективны! Поэтому при записи данных выбирайте такой их тип, котрый лучше подходит для описания конкретного алгоритма. Запись памяти учетверенными словами, как вы уже наверное догадались, менее выгодна.
И это действительно так! Забавно, но теперь наибольший разрыв в производительности наблюдается не на Р-П1 (как это было при чтении памяти), а на АМР Аг!))оп, который в 1,6 раза проигрывает двойными словам по скорости обработки, Обработка байтовых потоков двойными словами В некоторых случаях байтовые потоки данных могут (не без ухищрений конечно) обрабатываться непосредственно двойными словами, что значительно увеличивает производительность обрабатывающего их приложения. Рассмотрим следующий пример, шифрующий байты тривиальной операцией хоя по постоянной маске (листинг 2.21).
ьзппте а~уре)сЬае *ьгс, ьье нььм ~ьс и) ьпс ео Гог (а = 0; а < чо а++) ьзе)а)"=павЕ; Поскольку все байты обрабатываются однородно, то почему бы не попробовать обрабатывать четыре байта одной командой? В данном случае лля этого достаточно лишь "размножить" маску шифрования, скопировав ее в остальные три байта двойного слова. Правда, еще потребуется предусмотреть возможность обработки блоков, размер которых не кратен четырем (а что, может же сложиться такая ситуация?). Кстати, это очень просто! Достаточно, получив остаток от деления размера блока на четыре, зашифровать оставшийся "хвост" (если он есть) "вручную", — т.
е. по байтам. !ВО Глава г Это может выглядеть, например, так, как показано в листинге 2.22. ор11пахеб аьюр1е стуре(сиад *впс, ШО пывК, 1ло и) ьдп а; О равмиожаем байтовую маску для долучеиия двойного слова вирта пмвК = юавК (павК«8) ь(павК«18) +(дывК«24) ) // обрабатываем байты двойиьпм словами ог (а = О) а < л) а += 4) *(пвп *)вкс "= порта пывК) 5пст=4) О обрабатываем оставшийся "хвост" (если он есть! топ (а = (д ь -3)) а < л; а+ ) *5тс юапК) втс += 1) Разумеется, такой трюк применим не только к побайтовой шифровке! Оптимизации поддаются также алгоритмы копирования, инициализации, сравнения, поиска, обмена — словом все однородные способы обработки данных.
Выравнивание данных В силу конструктивных ограничений пакетный цикл обмена с памятью не может начинаться с произвольного адреса. В зависимости от типа процессора он автоматически выравнивается по границе 32, 64 и 128 байт на Кб/' Р-П/Р-П1, Ай1оп и Р-4 соответственно /см. разд. "Отображение физических РВАМ-адресов на логические" зяай главы). Задумаемся, что произойдет, если на Р-П1 мы запросим двойное слово, лежащее по адресу, равному, ну скажем, 302 Правильно! Для его чтения потребуется выполнить два пакетных цикла! В первом цикле будут загружены ячейки из интервала [[30 % 32); [30 % 32) + 32), т. е.
[О; 32), в который входит лишь половина запрошенного нами двойного слова. Для чтения другой его половины потребуется совершить еще один цикл — [32; 64). В результате — время доступа к ячейке возрастет как минимум вдвое. Оперативная память 18! Но не стоит упрекать создателей процессора Репйщп в "кретинизме"— многие процессоры, в отличии от него, вообще запрещают доступ по невыровненным адресам, генерируя при этом исключение! Однако и на процессорах Реп!)цтп таких ситуаций все же рекомендуется избегать. И вот тут самое время рассказать о широко распространенном заблуждении, связанном с выравниванием данных. Подавляющее большинство руководств по оптимизации (равно как и техническая документация от производителей процессоров) настоятельно рекомендуют всегда выравнивать данные независимо то того, по каким адресам они лежат.
На самом же деле, если запрошенные данные целиком умещаются в один пакетный цикл, то величина выравнивания не играет никакой роли! Чтение двойного слова, начинающегося с адреса Ох40001, осуществляется безо всяких задержек (по репа!гу!), поскольку оно гарантированно не пересекает пакетный цикл. Действительно: Ох20 — (Ох40001 % Ох20) = Ох!а, а Ох1Г > з(хео((0'1чОКП) (в смысле расстояние до правой границы пакетного цикла превь1шает размер читаемых данных!). Следовательно, чтение двойного слова с адреса Ох40001 вполне законно„хотя он (адрес) отнюдь и не кратен 4.
Подробный разговор о проблемах выравнивания мы отложим на потом !сч. разд. "Выравнивание данных" главы 3), поскольку он больше относится к кэшу, чем к подсистеме оперативной памяти, здесь же мы рассмотрим лишь влияние начального адреса на скорость обработки больших блоков памяти (см. исходный текст программы, находящийся в файле ~в!с~[2)зпетпогу~ а!1яп.с на прилагаемом компакт-диске). Достаточно очевидно, что ири линейной обработке памяти кратность выравнивания начального адреса играет второстепенную роль.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
