К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 74
Текст из файла (страница 74)
наилучшая дистанция предвыборки зачастую изменяется в процессе выполнения цикла. Особенно это характерно для разветвленных циклов, обрабатывающих неоднородные данные. К тому же динамический алгоритм определения дистанции предвыборки автоматически адаптируется под новые, еше незнакомые ему модели процессоров, в то время как статический анализ бессилен предвидеть их характеристики (Никто случайно не знает вычислительную скорость Р-7?) Статическое определение.
В программах, рассчитанных на долговременное использование, статическое определение дистанции предвыборки нецелесообразно. Никто не знает: какими будут процессоры через несколько лет, да и в настоящее время их характеристики подвержены значительному разбросу. Если у Се(егоп-800 отношение частоты системной шины к частоте ядра равно 1;8, то у Репйцт-4 1300 оно лиц~ь чуть-чуть не дотягивает 1:3. ВследТ, «-Т„ ствие этого соотношение ' у них будет очень различным, и дистан- Т, ция предвыборки, оптимальная для процессора Се!егоп, окажется слишком малой для Р-4, которому придется простаивать, "томительно" ожидания загрузки очередной порции данных, в результате чею переход с Се!егоп на Р-4 практически не увеличит производительности такой программы.
Поэтому дистанцию предвыборки всегда планируйте с приличным запасом, по крайней мере, на 3 — 4 итерации больше необходимою минимума. Минимально необходимая дистанция предвыборки упрощенно вычисляется так: Кзш (причем имеется ярко выраженная тенденция увеличения длины кэш-строк производителями процессоров). Среднее время выполнения одной инструкции — вообще абстрактная величина, вроде среднего дохода граждан. Наряду с командами, по трое схолящими с конвейера за один такт, некоторые (между прочим, достаточно многие) инструкции требуют десятков, а то и сотен тактов для своего выполнения! (В частности, целочисленное деление — не самая редкая операция, правда? — занимает от 50 до 70 тактов.) Таким образом, статическое планирование предвыборки в чем-то сродни гаданию на кофейной гуще.
Но почему бы действительно не погадать? Фирма 1пге1 приводит следующую эвристическую формулу, явно оговаривая ее ограниченность: (3.4) Полсчет количества инструкций в цикле М„„, — очень интересный момент. Даже реализуя критические циклы на ассемблере (что для сегодняшнего дня вообще-то редкость), программист не может быть абсолютно уверен, что транслятор не "впихнул" туда чего-нибудь по собственной инициативе (например, ряд команд всг для выравнивания). Что же тогла говорить о языках высокого уровня! Количество инструкций достоверно определяется лишь ручным их подсчетом в ассемблерном листинге (большинство компиляторов такие листинги генерировать умеют), однако, во-первых, это утомительное занятие придется проводить при всяком изменении текста программы. Во-вторых, если в цикле вызываются внешние функции (например, АР1-функции операционной системы), потребуется либо раздобыть исходные тексты ОС, либо дизассемблировать соответствующую функцию (но исходные тексты в большинстве случаев недоступны, а дизассемблером далеко не каждый умеет пользоваться в должной мере).
Наконец, в-третьих, полученный таким трудом результат все равно окажется неверным и ничуть не уступающим в точности "киданию кости". К счастью, интервал оптимальной дистанции предвыборки очень широк— даже увеличение минимального значения на порядок (!) в большинстве случаев снижает производительность не более чем на 10 — 15% (а на многократно выполняющихся циклах — и того меньше).
Поэтому, если скорость выполнения кода некритична, то динамическое определение листанции предвыборки допустимо заменить статическим планированием, увеличив предвычисленный результат в несколько раз. Хорошая идея — разрешить пользователю задавать листанцию предвыборки опционально. Чтобы не загромождать интерфейс и не смущать неопытных пользователей, эти настойки можно упрятать в реестр. 376 Глава 3 Увеличение эффективности предвыборки Предотвращение "холостого" хода.
Сдвиг предвыборки на несколько итераций приводит к возникновению "холостого" хода, т. е. неэффективному исполнению первых рЫ-проходов цикла, ввиду отсутствия запрашиваемых данных в каше и вытекающей отсюда необходимостью ожидания их за)рузки из медленной основной памяти. Если цикл исполняется многократно (скажем, сто или даже сто тысяч раз), накладные расходы настолько невелики, что вряд ли кому придет в голову брать их в расчет. Если же цикл исполняется несколько десятков раз, то время его выполнения практически не сказывается на производительности системы, и им можно вновь пренебречь.
Однако если такой цикл вызывается неоднократно (скажем, из другого цикла), то потери от "холостого" хода окажутся весьма внушительными. Рассмотрим следующий пример (листинг 3.23). гот )а = 0) а < ю ат+) гот )ь = а) ь < вьоск зтгв) ь =втер зггв) У,' Лля переноса примере на процессор Кб)йььтоп О заманите ниееслепупгтла инструнцию на ртетеось ртегеьсьпте )р)е))Ьтгткр Згге))) ссирпьагтап (а)а!)Ь))г Поскольку дистанция предвыборки цикла ь равна единице, то первый проход цикла всегда исполняется неэффективно — "вхолостую", при небольшом значении вьсск зггв и внушительном в с этим трудно смириться! А при дистанции предвыборки, сравнимой с количеством итераций цикла ь, ее эффективность и вовсе стремится к нулю.
Точно такая же ситуация наблюдается и на Р-4, механизм аппаратной предвыборки которого не настолько интеллектуален, чтобы справиться с вложенными циклами. Как же, не сильно усложнив алгоритм, увеличить его производительность? Да очень просто — достаточно лишь в последней итерации цикла ь осуществить предвыборку следующей обрабатываемой ячейки. В данном случае ею будет ячейка р)е+т) )о). 377 Кзш Оптимизированный вариант кода может выглядеть, например, так, как в листинге 3.24. го< ]а = О; а < И) а++) го< [ь = О; ь <вьсск яггк; ь+=яткя яггк) [ 11 [ь==[яьоск я1ге-ятер-я1ге)) рсегессьоса ]р[а+1][О)); е1ае ргегегсьаьа [р[а] [ьаятер яггк] ) 1 сокро<аггее [р[а] [Ы ) ' Однако использование ветвлений в теле цикла не самым лучшим образом сказывается на его производительности, поэтому условный переход следует выкинуть, переписав код, например, так, как показано в листинге 3.25.
го< [а = О) а < и) а++) го< [ь = О; ь <[вьзск яггк-яткр я[як]; ье=яткр ятгк) ргегеосьага [р[а][ь+яткр я[як))) соараьасгоа [р[а][ь])г ) реегаьовага [р [а+1] [О) ); о<еригаеаоа [р[а] [Ь]) ) После модернизации программы останется не устраненным всего лишь один "холостой" проход, возникаюший при первом выполнении цикла ь (точнее, не устраненными останутся ря[[ проходов), что даже при небольшом в практически не сказывается на производительности. Уменьшение количества инструкций нредвыборки. Все предыдушие рассуждения молчаливо опирались на предположение, что шаг цикла равен размеру З7В Глава 3 кэш-линейки, а в реальной жизни так бывает далеко не всегда. Наглядной демонстрацией тому следует пример из листинга 3.26, е 'Еах"(ВЯК 'ЖС Е:ежк"'."Р(ти Зава Капяаск)У~"Х:, ттРРХ,' 'б'*Степа'~'~."'",~ .',:.:.~"'.,е~;,'.'~е'.',.,'л.".:.'-.,~~1мв~,;-;."',": ьпс р(н): ()Оеттпе ссярпхаозоп (х) ххх+-(х)*схббб( ахх+=р(х]; тот (а = О( а < Б( аа=етхео (тпб)! ртетессьпса (р(а + 32*3])) соярссасвоп (а); Рис.
3.47. Влияние лишних запросов предвыборки на производительность. За 100% приятно копирование памяти штатной функцией п(е(асру Поскольку каждый элемент массива р занимает всего лишь 8 байт, а размер кэш-линеек процессора в зависимости от модели составляет от 32 до 128 байт, то в большинстве итераций цикла команда предвыборки будет выполняться "вхолостую", т. к. запрошенные данные уже находятся в кэше, и загружать их из оперативной памяти не требуется.
В такой ситуации коман- Кэш ( й 2 гос (а = О( а < в) аз=32) (р(а + 32*3))) о)( рсееессвоса сосросас1оо сотрооаеаоо (а+4): соериоаоьоо (аав)) соаросас1оо (а(.12) ( соариоа11оо (аа16) ( соаоооа11оо (аа20)( (а+24)( сотросас1оо соарооаоьоо (а+28)) Однако этот прием не лишен недостатков: во-первых, многократное дублирование тела цикла приводит к значительному увеличению объема исполняемого кода с вытекающим отсюда риском попросту не уместиться в кэш. Во-вторых, величину шага (а, значит, и размер кэш-линеек) допустимо выбирать лишь на этапе создания программы и поменять ее "на лету" практически не возможно.
Чем плоха "жесткая" прошивка? Дело в том, что, попав на процессор с иной длиной кэш-линий, программа будет исполняться недостаточно эффективно. Ориентироваться на размер в 32 байта — это расчитывать на процессоры уходящего дня, но, с лругой стороны, писать свой код под !28 байт — все равно, что "бежать впереди паровоза". Рабочие станции на основе Р-4 вытеснят Р-1П не раньше, чем через несколько лет, но и тогда да предвыборки ведет себя аналогично инструкции вор, однако накладные расходы на ее выполнение отнюдь не равны нулю! Чрезмерное засорение цикла предвыборкой (оиегрге/е(с7пп8) не то, что не ускоряет, а даже замедляет его работу. В частности, пример (см.
листинг 3.26) при исключении пред- выборки исполняется на !Π— 15% (рис. 3.47) быстрее! (Следует также учесть накладные расходы на передачу аргументов функции предвыборки.) Решение проблемы заключается в разворачивании цикла с подгонкой величины его шага к размеру кэш-линий. Это снизит накладные расходы на выполнение цикла и удалит все лишние предвыборки, в результате чего скорость выполнения кода значительно возрастет. Так, оптимизация предыду(цего примера увеличивает скорость его выполнения на 80%, т. е. более чем в три раза (листинг 3.27).
(Полный исходный текст программы читатель найдет в файле ))8гс)(131.сас!зе)(сас!)е ргеГегс)) араго!!.с, который находится на прилагаемом компакт-диске.) ЗВ(З Глава 3 доля процессоров с 32(64)-байтными кэш-линейками будет весьма велика. Похоже, ничего не остается, как реализовать все критичные к быстродействию функции в нескольких вариантах и по ходу выполнения программы выбирать олпу из них. Но почему бы не вставить в цикл тривиальный условный оператор, наприМср, Чтп-тО Врпдс: 1Г;(а а рааретея Слева 11яа Згза( == О( рпетепсв(аарас(? Во-первых, деление — крайне медленная операция и поэтому такой прием снизит производительность цикла на столько, что ее и "домкратом не поднимешь".
Во-вторых, даже если исхитриться и заменить деление битовыми операциями (или ввести в цикл дополнительный счетчик), накладные расходы будут по-прежнему довольно велики. Лучше уж остановить свой выбор на 32-байтных кэш-линейках, махнув рукой гпока) на оптимизацию пол Р-4 и более старшие процессоры, которые и без того быстры, а вот их младшим братьям требуется поддержка. "Мясной рулет" предвыборки ня инструкциях. До сих пор мы рассматривали случаи предвыборки лишь одной кэш-линейки за каждую итерацию цикла, но если параллельно обрабатывается несколько блоков памяти, расположенных в различных местах, одной операцией предвыборки уже не обойтись.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
