Низкоуровневое программирование для Дzenствующих
| Вид материала | Документы |
- Низкоуровневое программирование, 108.99kb.
- Курс является базовым как для изучения других математических дисциплин, так и для более, 36.89kb.
- 1 Обобщенное программирование. Обобщенное программирование это еще одна парадигма программирования,, 55.18kb.
- Введение в линейное программирование линейное программирование (ЛП), 139.72kb.
- Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 63.23kb.
- Аттестационное тестирование в сфере профессионального образования, 72.49kb.
- Лекции по дисциплине «Социальное моделирование и программирование», 44.69kb.
- Программа дисциплины Линейное программирование Семестр, 17.93kb.
- Программа дисциплины "Программирование" для направления, 488.76kb.
- Рабочая программа по дисциплине Программирование на языке высокого уровня для специальности, 182.97kb.
Часть 1
Профилировка программ
Профилировкой здесь и на протяжении всей книги мы будем называть измерение производительности как всей программы в целом, так и отдельных ее фрагментов, с целью нахождения "горячих" точек (Hot Spots), — тех участков программы, на выполнение которых расходуется наибольшее количество времени.
Согласно правилу "10/90", десять процентов кода "съедают" девяносто процентов производительности системы (равно как и десять процентов людей выпивают девяносто процентов всего пива). Если время, потраченное на выполнение каждой машинной инструкции, изобразить графически в порядке возрастания их линейных адресов, на полученной диаграмме мы обнаружим несколько высоченных пиков, горделиво возвышающихся над практически пустой равниной, усеянной множеством низеньких холмиков (пример показан далее на рисунке разд. " Практический сеанс профилировки с VTune в десяти шагах") Вот эти самые пики — "горячие" точки и есть.
Почему "температура" различных участков программы столь неодинакова? Причина в том, что подавляющее большинство вычислительных алгоритмов так или иначе сводятся к циклам, — т. е. многократным повторениям одного фрагмента кода, причем зачастую циклы обрабатываются не последовательно, а образуют более или менее глубокие иерархии, организованные по типу "матрешки". В результате, львиную долю всего времени выполнения, программа проводит в циклах с наибольшим уровнем вложения, и именно их оптимизация дает наилучший прирост производительности!
Громоздкие и тормозные, но редко вызываемые функции оптимизировать нет ни какой нужды, — это практически не увеличит быстродействия приложения (ну разве что только в том случае, если они совсем уж будут "криво" написаны).
Когда же алгоритм программы прост, а ее исходный текст свободно умещается в сотню–другую строк, то "горячие" точки нетрудно обнаружить и визуальным просмотром листинга. Но с увеличением объема кода это становится все сложнее и сложнее. В программе, состоящей из тысяч сложно взаимодействующих друг с другом функций (часть из которых это функции внешних библиотек и API — Application Programming Interface, интерфейс прикладного программирования — операционной системы) далеко не так очевидно: какая же именно из них в наибольшей степени ответственна за низкую производительность приложения. Естественный выход — прибегнуть к помощи специализированных программных средств.
Профилировщик (так же называемый "профайлером") — основной инструмент оптимизатора программ. Оптимизация "в слепую" редко дает хороший результат. Помните пословицу "самый медленный верблюд определяет скорость каравана"? Программный код ведет себя полностью аналогичным образом, и производительность приложения определяется самым узким его участком. Бывает, что виновницей оказывается одна–единственная машинная инструкция (например, инструкция деления, многократно выполняющаяся в глубоко вложенном цикле). Программист, затратив воистину титанические усилия на улучшение остального кода, окажется премного удивлен, что производительность приложения едва ли возросла процентов на десять–пятнадцать.
Правило номер один: ликвидация не самых "горячих" точек программы, практически не увеличивает ее быстродействия. Действительно, сколько не подгоняй второго сзади верблюда — от этого караван быстрее идти не будет (случай, когда предпоследней верблюд тормозит последнего — это уже тема другого разговора, требующего глубоких знаний техники профилировки, а потому и не рассматриваемая в настоящей книге).
Цели и задачи профилировки
Основная цель профилировки — исследовать характер поведения приложения во всех его точках. Под "точкой" в зависимости от степени детализации может подразумеваться как отдельная машинная команда, так целая конструкция языка высокого уровня (например: функция, цикл или одна–единственная строка исходного текста).
Большинство современных профилировщиков поддерживают следующий набор базовых операций:
- определение общего времени исполнения каждой точки программы (total [spots] timing);
- определение удельного времени исполнения каждой точки программы ([spots] timing);
- определение причины и/или источника конфликтов и пенальти (penalty information);
- определение количества вызовов той или иной точки программы ([spots] count);
- определение степени покрытия программы ([spots] covering).
Общее время исполнения
Сведения о времени, которое приложение тратит на выполнение каждой точки программы, позволяют выявить его наиболее "горячие" участки. Правда, здесь необходимо сделать одно уточнение. Непосредственный замер покажет, что, по крайней мере, 99,99% всего времени выполнения профилируемая программа проводит внутри функции main, но ведь очевидно, что "горячей" является отнюдь не сама main, а вызываемые ею функции! Чтобы не вызывать у программистов недоумения, профилировщики обычно вычитают время, потраченное на выполнение дочерних функций, из общего времени выполнения каждой функции программы.
Рассмотрим, например, результат профилировки некоторого приложения профилировщиком profile.exe, входящего в комплект поставки компилятора Microsoft Visual C++.
| Листинг 1.1. Пример профилировки приложения профилировщиком profile.exe Func Func+Child Hit Time % Time % Count Function --------------------------------------------------------- 350,192 95,9 360,982 98,9 10000 _do_pswd (pswd_x.obj) 5,700 1,6 5,700 1,6 10000 _CalculateCRC (pswd_x.obj) 5,090 1,4 10,790 3,0 10000 _CheckCRC (pswd_x.obj) 2,841 0,8 363,824 99,6 1 _gen_pswd (pswd_x.obj) 1,226 0,3 365,148 100,0 1 _main (pswd_x.obj) 0,098 0,0 0,098 0,0 1 _print_dot (pswd_x.obj) |
В средней колонке ( Func+Child Time) приводится полное время исполнения каждой функции, львиная доля которого принадлежит функции main (ну этого и следовало ожидать), за ней с минимальным отрывом следует gen_pswd со своими 99,6%, далее идет do_pswd — 98,9% и, сильно отставая от нее, где-то там на отшибе плетется CheckCRC, оттягивая на себя всего лишь 3,0%. А функцией CalculateCRC, с ее робким показателем 1,6%, на первый взгляд можно и вовсе пренебречь! Итак, судя по всему, мы имеем три "горячих" точки: main, gen_pswd и do_pswd (рис. 1.1).
 |
| рис 1.1 Диаграмма, иллюстрирующая общее время выполнения каждой из функций. На первый взгляд, здесь три "горячих" точки, но на самом деле это не так |
Впрочем, функцию main можно откинуть сразу. Она, понятное дело, ни в чем не "виновата". Остаются функции gen_pswd и do_pswd. Если бы это были абсолютно независимые функции, то "горячих" точек было бы и впрямь две, но в нашем случае это не так. И, если из полного времени выполнения функции gen_pswd, вычесть время выполнения ее дочерней функции do_pswd у "матери" останется всего лишь… 0,7%. Да! Меньше процента времени выполнения!
Обратимся к крайней левой колонке (листинг 1.1) таблицы профилировщика (Funct Time), чтобы подтвердить наши предположения. Действительно, в программе присутствует всего лишь одна "горячая" точка — do_pswd, и только ее оптимизация способна существенно увеличить быстродействие приложения (рис. 1.2).
| |
| рис 1.2 Диаграмма, иллюстрирующая чистое время работы каждой из функций (т. е. с вычетом времени дочерних функций). Как видно, в программе есть одна, но чрезвычайно "горячая" точка |
Хорошо, будем считать, что наиболее "горячая" функция определена и теперь мы горим желанием ее оптимизировать. А для этого недурно бы узнать картину распределения "температуры" внутри самой функции. К сожалению, профилировщик profile.exe (и другие подобные ему) не сможет ничем нам помочь, поскольку его разрешающая способность ограничивается именно функциями.
Но, на наше счастье существуют и более "продвинутые" профилировщики, уверенно различающие отдельные строки и даже машинные команды! К таким профилировщикам в частности относится VTune от Intel. Давайте запустим его и заглянем внутрь функции do_pswd (подробнее о технике работы с VTune см. "Практический сеанс профилировки с VTune").
| Листинг 1.2. Карта распределения "температуры" внутри функции do_pswd, полученная с помощью профилировщика VTune Line Clock ticks Source temperature 105 729 while((++pswd[p])>'z'){ ***********************>>> 106 14 pswd[p] = '!'; ************** 107 1 y = y | y << 8; * 108 2 x -= k; ** 109 k = k << 8; * 110 3 k += 0x59; *** 111 2 p++; ** 112 1 } * |
Вот теперь совсем другое дело — сразу видно, что целесообразно оптимизировать, а что и без того уже "вылизано" по самые помидоры. "Горячие" точки главным образом сосредоточены вокруг конструкции pswd[p], — она очень медленно выполняется. Почему? Исходный текст не дает непосредственного ответа на поставленный вопрос и потому совсем не ясно: что конкретно следует сделать для понижения "температуры" "горячих" точек.
Приходится спускаться на уровень "голых" машинных команд (благо профилировщик VTune это позволяет). Вот, например, во что компилятор превратил безобидный на вид оператор присвоения pswd[p] = '!'
| Листинг 1.3. Исследование температуры машинных команд внутри конструкции pswd[p] = '!' Line Instructions Cycles Count temperature 107 mov edx, DWORD PTR [ebp+0ch] 143 11 ******************* 107 загрузить в регистр EDX указатель pswd 107 add edx, DWORD PTR [ebp-4] 22 11 ***** 107 сложить EDX с переменной p 107 mov BYTE PTR [edx], 021h 33 11 ******* 107 по полученному смещению записать значение 0х21 ('!') |
Смотрите! В одной строке исходного текста происходит целых три обращения к памяти! Сначала указатель pswd загружается в регистр EDX, затем он суммируется с переменной p, которая так же расположена в памяти, и лишь затем по рассчитанному смещению в память благополучно записывается константа '!' (021h).
Тем не менее, все равно остается не ясно, почему загрузка указателя pswd занимает столько времени? Может быть, кто-то постоянно вытесняет указатель pswd из кэша, заставляя процессор обращаться к медленной оперативной памяти? Так ведь нет! Программа работает с небольшим количеством переменных, заведомо умещающихся в кэше второго уровня.
(продолжение следует)
| Здравствуйте дорогие читатели рассылки. Видимо этот выпуск будет первым, в котором мы обойдёмся без юморных фенечек. Хотя не совсем. Сегодня я приговорил уйму хороших новостей для вас. И просто уверен, что они поднимут ваше настроение и Дух. Продолжаю цитировать Александра Сергеевича (который Саня, но не программист), хотя по душе ближе Лермонтов. А вообще-то сейчас я где-то мыслями в Киеве на сцене романа Булгакова «Белая Гвардия» у истоков 20 века. Там сейчас зима, руки мёрзнут над клавиатурой, говоря о том, что на улице отопительный сезон, а у нас ещё не затопили. Писать статьи стало неуютно. Лето красное прошло. Совсем недавно HI-TECH познакомился ещё с одним Александром (нет, не Пушкин, но Программист :)), в лице которого для нас предстал журнал argc&argv. Было очень приятно, что в СНГ есть ещё один журнал для программистов. Сейчас таких журналов всего два: RSDN и argc&argv. Ещё приятнее для меня, как для жителя Украины было то, что это Киевский журнал, с замечательным уровнем (я уже успел посмотреть четыре номера, и оказался приятно удивлён). Если вы – житель Украины, то без проблем сможете подписаться на него в любом отделении почты. Для России – процесс сложнее, но, видимо, так же возможен. Сам факт, что такой журнал всё-таки существует – уже чудо. Было бы странно, если бы HI-TECH, а так же WASM не выступили с инициативой поддержать его. Ибо в нашей действительности (я имею ввиду не только Украину) иметь журнал (издательство, либо иную подобную организацию) невероятно сложно, а особенно в Украине, где к печатной продукции налоговые органы относятся мягко сказать с пристрастием. И сегодня у меня две радостные новости: «В Украине есть хороший журнал для профессиональных программистов», и вторая новость: «Часть статей для WASM.RU будут предварительно печататься в этом издании». Более подробнее о argc&argv я расскажу в следующем номере рассылки. А сегодня вы прочитаете две статьи из этого журнала, которые опубликованы в 4 номере за июль-август. Новости действительно хорошие, но не последние. Совсем недавно в HI-TECH завелись МЫЩЪЫ c Хвостом. Это пернатое создание известно нашему программисту как Крис Касперски. Хотя Крис давно уже знаком с предводителем HI-TECH Serrgio, он оказался в наших рядах не так давно. Хаос WASM взмылся ввысь!!! Такого оживления я не припоминаю с прошлого года. И у меня есть ещё одна радостная новость: «WASM.RU готовит множество статей и книг Криса (МЫЩА) для публикации на сайте». Ещё одна радостная по истине новость, и для меня вдвойне, ибо я давно хотел получить правильную информацию о кеше процессора (ох как этот вопрос мучил на форуме WASM.RU): Недавно Крис выпустил книгу по «Оптимизации». В следующей рассылке я обещаю разместить несколько глав из этого труда, которые предоставил Крис. Но можете поверить Edmondу и TheSvin, что книга просто отличная – считайте это рекламой!!! Вы видимо думаете, что хорошие новости на этом закончились? Никак нет!!! Просто замечательная новость для тех, кто проводит свои будни за любимым отладчиком SoftIce. Теперь в каждом топике WASM.FORUM об этом отладчике следует поствить автоответчик с фразой: «Читай Книгу BrokenSword, которая УЖЕ вышла шестым томом в серии кодокопатель». Ниже наш дорогой автор даёт сжатое описание своей книге. И ещё одна просто СУПЕР новость. Володя закончил работу над замечательной статьёй про упаковщики. Её вторая часть (гигантская) появится на следующей неделе в нашей рассылке. |