К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 42

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 42)

2.45. Демонстрация эффективности различных алгоритмов переноса памяти (увеличено) 35000000 $ и 30000000 у 25000000 о 20000000 в (С с о15000000 ф (ООООООО Ж е 5000000 Сравнение функций гпепнпоче и МуМегпМоче аачввлаао О(а«гавлова аамввлассо СЧ СЧ (Ч СЧ (Ч (Ч (Ч (Ч (Ч СЧ С'Ъ С'Ъ Оперативная память Рис. 2.46. Сравнение функций иешиоче и мунеиноче на системе АМ0 А1))!оп 1050/100/100/ч)А КТ133 Фбетгае Вот 51ЕЕ25б*К ааГ Муиеаиоче)сваг *бес, сваг *его, 2аГ агге) 1 сваг ВСУ 1)ВСУ 51ЗВ)2 сьаг Вот г[ВЦт 5125]; сваг *р1, *р2) гоГ а,х = 12 1аГ бе1са2 бе1Га бас-згс; 1Г 1)бе11а>Вот 512Е) )) (бе1га<1)) гесига -1> р1 - ВСУ 1; р2 его! уог)а = вп а<а1ге/бе1га2 а++) ( иегсру)р1, бас, бе1Га) ) гвв Глава г пепсру (бас, р2, бе1Га); (х) р1 = ВОВ 2) р2 = всг 1) х О; е1ае р1 = ВОГ Ы р2 = ВОГ Ы х = 1) баГ += бе1Га; гегпгп О) Оптимизация функции татстр Несмотря на то, что функция пеппер не относится к числу самых популярных (так, в МБРХ (М!сговой Реу!!орет Нег)вот!( — комплект документации от М!сговой, поставляемый с ее компиляторами и доступный на сайте компании) функция ру упоминается 500 раз, а р и о е — всего 150 и 50 раз соответственно), это еще не дает оснований пренебрегать качеством ее реализации.

Начнем с анализа штатных библиотек вашего компилятора. В большинстве случаев сравнение блоков памяти осуществляется приблизительно так (листинг 2.33). гога * сбес1 пеессру (еогб * беас, сопаГ ъо1б * агс, гпс с, ппагдпеб соппс) хь11е ( соппг еа (*((сьаг *) (бега (сваг *) беаг + 1) - 1) * ((сваг ") (агс = (сваг *) агс е 1) — 1) ) ! (сваг) с ) соппс †; геспгп(соипГ 2 беас : ВОЬЬ)) Фи! Медленное побайтное сравнение безо всяких попыток оптимизации! Правда в комплект поставки У1вца! С++ входит и ассемблерная реализация той же самой функции (нщите ее в каталоге ~ЯКА,1пге1). Ну-ка, посмотрим, Оперативная память гоо что там (по соображениям экономии места исходный текст не приводится); ага, если оба указателя кратны четырем, сравнение ведется двойными словами (что намного быстрее) и лишь в противном случае — по байтам.

Гуд!? А вот и нс гуд! Кратность начальных адресов — это условие вовсе не обязательное для 32-разрядного сравнения (строго говоря, процессоры серии 80х86 вообще не требуют осуществлять выравнивания, просто небрежное отношение с нсвыровненными адресами может несколько снизить быстродействие— подробнее см. разд. зйыравнивание данных" этой главы). Если три младших бита обоих указателей одинаковы, функция может выровнять их и самостоятельно, просто сместившись на один, два или три байта "вперед". Впрочем, эти рассуждения все равно беспредметны, поскольку в режиме оптимизации по скорости (ключ юг) М!сгозой Ч[зца[ С++ отказывается от использования ряда библиотечных функций и заменяет их шгппяс (см.

"ргайша шгг[пгйс[у[[![взх[з!" в документации по компилятору). Забавно, но разработчики компилятора, по-видимому, сочли, что выполнять множество проверок и "тянуть" за собой несколько вариантов реализации функции сравнения будет нерационально (?) и потому они ограничились одним универсальным решением — тривиальным побайтовым сравнением. Неудивительно, что после такой "оптимизации" быстродействие функции ьесер значительно ухудшилось.

Чтобы запретить компилятору "самовольничать", — используйте ргарша бзпсгюп с указанием имени функции, например, так: Фрхьд ь т сеьоп~иь серь В частности, на Р-Ш это ускорит выполнение функции приблизительно на 36%о! Правда, на Айт[оп разница в производительности будет существо меньше — порядка 10%. Кстати, в защиту М!сгозой можно сказать, что ее реализация функции еье р на 20 — 30% быстрее, чем у Вот!апд С++ 5.5. Но и это еше не предел! Для функции ер (как и для большинства остальных функций, работающих с памятью) актуальна проблема оптимального чередования ПВАМ- банков Гсм.

разд. "Стратегия распределения данных по ГгВАМ-банкам" этой главы). Если оба сравниваемых блока начинаются с различных страниц одного и того же банка, то время доступа к памяти существенно замедляется. Поэтому мы должны уметь отслеживать такую ситуацию, при необходимости увеличивая один из указателей на длину РВАМ-страницы.

Это повысит скорость выполнения функции приблизительно на 40% на Р-1П и на целых 60 — 70% на АМ[3 А1[з!оп (да-да, практически в три раза!). Правда, тут есть одно "но". Память должна обрабатываться не байтами, а двойными словами, в противном случае прирост производительности составит всего лишь 5% для Р-П[ и немногим менее 30% для АМР Айз[оп (рис. 2.47). Хорошо, а если адреса сравниваемых блоков к нам поступают "извне" и скорректировать их невозможно? Существуют два пути: смириться с низкой производительностью или сравнивать не сами блоки памяти, а их контрольную сумму. Конечно, теоретически не исключено, что контрольные суммы Глава 2 210 различных блоков памяти "волшебным" образом совпадут, но в подавляюшем большинстве случаев эта вероятность настолько мала, что ей вполне можно пренебречь.

рис. 2 ат. демонстрация эффективности различных алгоритмов сравнения блоков памяти К тому же, считать контрольную сумму всего блока абсолютно не обязательно — вполне достаточно ограничиться одной ПКАМ-страницей (можно в принципе и меньшей величиной, главное, чтобы переключения между страницами одного банка происходили не слишком часто). За счет сокращения количества параллельно обрабатываемых потоков данных с двух до одного хэш-алгоритм работает намного быстрее штатной функции сравнения памяти, обгоняя ее на 35% и 55% на Р-Ш и АМО Агл)ол соответственно. Хэш-алгорим — это алгорити сравнения, базирующийся на хэшировании (проверке контрольной суммы). Правда, при оптимальном чередовании банков памяти хэш-алгоритм все же проигрывает функции, сравнивающей память двойными словами.

Причем, Оперативная память если на Р-1П хэш-алгоритм отстает от нее всего на !%, то на АМР А1!)!оп разрыв в производительности достигает целых 10%! Таким образом, хэш-алгоритм целесообразно использовать только при неоптимальном чередовании РВАМ-банков. Впрочем, категоричность этого утверждения смягчает одна оговорка. Если мы сократим длину хэшируемого блока до величины пакетного цикла обмена, на Р-111 мы получим практически б0%-ный выигрыш в производительности, обогнав самый быстрый алгоритм двойных слов более чем на 20%! Ценой же за зто станет постоянное переключение РВАМ-страниц и, как следствие, потеря возможности противостоять неблагоприятному чередованию банков памяти. Однако такой значительный прирост скорости стоит того! Увы, этот эффект имеет место лишь на 1пге! и не переносим на АМР/ЛА.

С другой стороны, процессорам Репбшп принадлежит более половины компьютерного рынка и оснований для отказа от предложенного трюка, в обшем-то, нет. Тем более что даже на АМР Айт!оп он !хэш-алгоритм) работает значительно быстрее штатной функции сравнения памяти. Один из возможных вариантов его реализации будет выглядеть так, как показано в листинге 2.34.

( ( 1 т ! ( с 2 ц гн е!'. бог(а=О)а<веоск 5155;а<=Орам РО 51ее) сгс 1=0) сгс 2=0) бог(Ь = О) Ь < ОВВМ РО 51ЕЕ; Ь Ь= зггеот(1пс)) // Внимание) Это очень слабый алгоритм подсчета СВС // и его мозно использовать только для демонстрации сгс 1 += *(гпс*)((гпс)р1+а+Ь)) бог(Ь = 0; Ь < ОВРН Рс 51ЕЕ; Ь += еггеоб(гпс)) сгс 2 ь= *(1пс*) ((гпс) р2+а+Ь)) 11 (сгс 1 (= сгс 2) Ьгеахо // Если СВС не совпадаыт, следовательно, // блоки паыяти различны. // При необходимости можно вызвать // в еысир(р1+а, р2 а, вьоск 5125-а) // лля уточнения результата Глава г ггг Особое замечание по функциями %1п32 АР1 В %)п32 АР1 входит множество функций для работы с блоками памяти, среди которых присутствуют и прямые эквиваленты штатных функций языка С: СоруМевогу (ЭКВИВаЛЕНт вору), Мо Мев у (ЭКВИВЯЛЕНт ве о е) И 5111Мевогу (эквивалент веввег).

Возникает вопрос: чем лучше пользоваться — функциями операционной системы или функциями самого языка? Ответ: компания М1сгояо11 намеренно заблокировала возможность использования функций ядра операционной системы, включив в заголовочные файлы %1)з)ВАВЕ.Н и %1ХИТ.Н следующий код (листинги 2.35, 2.36): ))беогпе Моиеиевогу КГ1моиемевогу ИеГ1пе Соруневогу КГ1Сорумевогу ))беГЬпе Г111мевогу кг1г111мезюгу ))бетгпе ЯегоМевогу КГ15егоиевогу ))бег1пе кг1едиа1мезюгу)оевггпаггоп,Яоигсе,ьепдго) )!вевспр моевг1паг).оп), )яоигсе),().епдгю )) ))бетгпе КГ1моиемевогу )Оезс1пасгоп, Яоигсе, Ьепдсь) зюавоие ) )Оевс1пас1оп), )Яоигсе), (Ьепдсш ) Фбетгпе КГ1ооруневсгу)Оевс1пасгоп,зоигсе,ьепдзь) вевсрумоевз1пас1оп), )Яоигсе), )Ьепдсь)) ))бет1пе кг1гг11мепюгу )Оевз1пас1оп, Ьепдсо, Г111) в)еапес))оезГЬпаг1оп),)Г111),)Ьепдсю ) Фбетгпе КГ1яегомевогу)Оевс1паг1оп,ьепдсь) вепзес ( )Ое*сгпас1оп), О, )Ьепдсь) ) ВОт ЭтО НОМЕР! ОКаЗЫВаЕтСЯ, ФУНКЦИИ СЕМЕйетВа хххмевогу ПРЕДСтаВЛЯЮт СО- бой макропереходники к штатным функциям языка! Причем, это отнюдь не корпоративная тайна, а вполне документированная особенность, косвенно подтверждаемая Р)аг1опп ЯЗК.

Оперативная память г№з ПРИ ВНИМатЕЛЬНОМ ИЗУЧЕНИИ ОПИСаНИЯ ФУНКЦИИ Моееиеспогу МЫ ОбиаРУжИМ слсдуюшее: И1пбоеа Итс Кеяп1геа еега1оп 3.1 ог 1агег. икпбоеаскечоьгеа игпбоеа 95 ог 1агег. Кьпбоеа СК: Опапррогьеб. Неабегс Оес1агеб 1п егпьаае.ь. Ну И ЧтО ЗДЕСЬ ОСОбЕННОГО? А ВОт ЧтО: СтрОКа тирогг Ьььгагу ОтСутСтВуЕт! Следовательно, функция м м гу целиком реализована во включаемом файле %!ХВАТКЕ.Н, о чем М)сгозой нас и предупреждает. Но это еше не конец истории. Скорее, только ее начало.

Давайте, воспользовавшись утилитой Г)(ЗМВь(1)Ч, посмотрим на список функций, экспортируемых "ядреной" библиотекой операционной системы— файлом КЕК)~1ЕЕ32.Е)ЕЕ. Вопреки логике и здравому смыслу мы обнаружим СЛЕДУЮ(ЦЕЕ: кг1гг11мепогу (гогиагбеб го итсьь.кг1Р111меиогу) КГ1иогеиепогу (тогеагдед Го ИТОЬЬ.КГ1Могеиеиогу) АГ10 ьпб (Гог агбед Го ИтОЬЬ.АГЬОпегпд) кг1кегомесогу (тогиагдеб го итсьь.кгткегомеиогу) 598 255 599 256 600 253 601 256 Выходит, что функции Агтмогеметогу, АЬ1Р111метогу и кгькегомесаогу системы все-таки есть! Причем„это не просто "заглушки", все тело которых состоит из одного оператора гпгп, а вполне работоспособные функции.

Характеристики

Список файлов книги