Руководство по стилю программирования и конструированию по
 Скачать 7.6 Mb.
|
|
ГЛАВА 25 Стратегии оптимизации кода 575 Если объем и быстродействие программы действительно важны, разработайте архитектуру так, чтобы она позволя- ла добиться намеченных показателей, а затем задайте для отдельных подсистем, функций и классов целевые показа- тели использования ресурсов. Преимущества такого подхода таковы. 쐽 Задание отдельных целевых показателей использования ресурсов делает про- изводительность системы предсказуемой. Если каждая функция соответствует целевым показателям, вся система будет обладать нужной производительнос- тью. Вы можете уже на ранних этапах определить проблемные подсистемы и перепроектировать их или оптимизировать их код. 쐽 Простое задание явных целей повышает вероятность их достижения. Програм- мисты стремятся к достижению целей, если знают, каковы они; чем определен- нее цели, тем легче к ним стремиться. 쐽 Вы можете поставить цели, которые непосредственно не направлены на повышение эффективности, но способствуют этому в долгосрочной перспективе. Эффективность часто лучше всего рассматривать в контексте других аспектов. Так, простота внесения изменений может создать лучшие условия для достижения высокой эффективности, чем явное определение эф- фективности как одной из целей. Если проект отличается высокой степенью модульности и простотой изменения, менее эффективные компоненты мож- но с легкостью заменить на более эффективные. Проекты классов и методов Проектирование классов и методов предоставляет еще одну возможность повышения производительности ПО. Одним из способов повышения производительности на этом уровне является выбор типа данных или алгоритма, от чего обычно зависит и объем используемой памяти, и быстрота выполне- ния кода. Именно на этом уровне вы можете выбрать быст- рую сортировку вместо пузырьковой или двоичный поиск вместо линейного. Взаимодействие программы с ОС Если ваша программа работает с внешними файлами, дина- мической памятью или устройствами вывода, она скорее всего взаимодействует с ОС. Низкая производительность в этом случае может объясняться большим объемом или мед- ленным выполнением методов ОС. Вы можете даже не знать, что программа взаимодействует с ОС: иногда вызовы сис- темных методов генерируются компилятором или содержатся в коде библиотек. Компиляция кода Хорошие компиляторы преобразуют ясный высокоуровневый код в оптимизиро- ванный машинный код. Иногда правильный выбор компилятора позволяет вооб- ще забыть о дальнейшей оптимизации кода. Перекрестная ссылка О том, как программисты стремятся к до- стижению поставленных целей, см. подраздел «Задание целей» раздела 20.2. Перекрестная ссылка О типах данных и алгоритмах см. кни- ги, указанные в разделе «Допол- нительные ресурсы» в конце главы. Перекрестная ссылка О страте- гиях борьбы со слишком мед- ленными или объемными мето- дами ОС на уровне кода см. главу 26. 576 ЧАСТЬ V Усовершенствование кода В главе 26 вы найдете многочисленные примеры ситуаций, когда код, сгенерирован- ный компилятором, оказывается эффективнее кода, оптимизированного вручную. Оборудование Иногда самым выгодным и эффективным способом повышения производитель- ности программы является покупка нового оборудования. Конечно, если программа предназначен для сотнен или тысяч компьютеров по всей стране, этот вариант нереалистичен. Но если вы разрабатываете специализированное ПО для нескольких пользователей, обновление оборудования на самом деле может оказаться самым дешевым вариантом. Это позволит сократить расходы, связанные с улучшением производительности ПО и проблемами, которые могут из-за этого улучшения воз- никнуть при сопровождении. Кроме того, это повысит производительность всех программ, выполняемых на новых системах. Оптимизация кода Оптимизацией кода (code tuning), которой посвящена оставшаяся часть этой главы, называют изменение корректного кода, направленное на повышение его эффек- тивности. «Оптимизация» подразумевает внесение небольших изменений, затра- гивающих один класс, один метод, а чаще всего — несколько строк кода. Крупно- масштабные изменения проекта или другие высокоуровневые способы повыше- ния производительности оптимизацией не считаются. Каждый из уровней от проектирования системы до оптимизации кода допускает существенное повышение производительности ПО. Джон Бентли утверждает, что в некоторых случаях формула общего повышения производительности системы имеет мультипликативный характер (Bentley, 1982). Так как каждый из шести уровней допускает десятикратный рост производительности, значит, что теоретически про- изводительность программы может быть повышена в миллион раз. Хотя для этого необходимо, чтобы результаты, получаемые на каждом из уровней, были незави- симы от других уровней (что наблюдается редко), этот потенциал вдохновляет. 25.2. Введение в оптимизацию кода Чем соблазняет оптимизация кода? Это не самый эффективный способ повыше- ния производительности: улучшение архитектуры программы, перепроектирование классов и выбор более эффективного алгоритма обычно приводят к более впе- чатляющим результатам. Кроме того, это не самый легкий способ повысить про- изводительность: легче купить новое оборудование или компилятор с улучшен- ным модулем оптимизации. Наконец, это не самый дешевый способ повысить производительность: на оптимизацию кода вручную изначально уходит много вре- мени, а потом оптимизированный код труднее сопровождать. Оптимизация кода привлекательна по ряду причин. Прежде всего она бросает вызов законам природы. Нет ничего радостнее, чем ускорить выполнение метода в 10 раз путем изменения всего лишь нескольких его строк. Кроме того, овладение мастерством написания эффективного кода — признак превращения в серьезного программиста. В теннисе вы не получаете очков за то, как берете мяч, но все же должны освоить правильный способ делать это. Вы не ГЛАВА 25 Стратегии оптимизации кода 577 можете просто наклониться и взять его рукой. Если вы не хотите показаться но- вичком, вы ударяете по нему ракеткой, пока он не подпрыгнет до пояса, и тогда вы его ловите. Более трех ударов мяча о землю — серьезная оплошность. Несмот- ря на кажущуюся незначительность, способ подбора мяча считается в культуре теннисистов отличительным признаком. Компактность вашего кода также обыч- но не волнует никого, кроме вас и других программистов. Тем не менее в про- граммисткой культуре способность создавать компактный и эффективный код слу- жит подтверждением вашего класса. Увы, эффективный код не всегда является «лучшим». Этот вопрос мы и обсудим ниже. Принцип Парето Принцип Парето, известный также как «правило 80/20», гласит, что 80% резуль- тата можно получить, приложив 20% усилий. Относящийся не только к програм- мированию, этот принцип очень точно характеризует оптимизацию программ. Барри Бом сообщает, что на 20% методов программы приходятся 80% времени ее выполнения (Boehm, 1987b). В классической работе «An Empi- rical Study of Fortran Programs» Дональд Кнут указал, что менее 4% кода обыч- но соответствуют более чем 50% времени выполнения программы (Knuth, 1971). Кнут обнаружил это неожиданное отношение при помощи инструмента профи- лирования, поддерживающего подсчет строк. Следствие очевидно: вам нужно найти в коде «горячие точки» и сосредоточиться на оптимизации процентов, использу- емых более всего. Профилируя свою программу подсчета строк, Кнут обнаружил, что половину времени она проводила в двух циклах. Он изменил несколько строк кода и удвоил скорость профайлера менее чем за час. Джон Бентли описывает случай, когда программа из 1000 строк проводила 80% времени в 5-строчном методе вычисления квадратного корня. Утроив быстродей- ствие этого метода, он удвоил быстродействие программы (Bentley, 1988). Опи- раясь на принцип Парето, можно дать еще один совет: напишите большую часть кода на интерпретируемом языке (скажем, на Python), а потом перепишите про- блемные фрагменты на более быстром компилируемом языке, таком как C. Бентли также сообщает о случае, когда группа обнаружила, что ОС половину вре- мени проводит в одном небольшом цикле. Переписав цикл на микрокоде, разра- ботчики ускорили его выполнение в 10 раз, но производительность системы ос- талась прежней — они переписали цикл бездействия системы! Разработчики языка ALGOL — прародителя большинства современных языков, сыгравшего одну из самых главных ролей в истории программирования, — руко- водствовались принципом «Лучшее — враг хорошего». Стремление к совершен- ству может мешать завершению работы. Доведите работу до конца и только по- том совершенствуйтесь. Часть, которую нужно довести до совершенства, обычно невелика. 578 ЧАСТЬ V Усовершенствование кода Бабушкины сказки С оптимизацией кода связано множество заблуждений. Сокращение числа строк высокоуровневого кода повышает быстродей- ствие или уменьшает объем итогового машинного кода — НЕВЕРНО! Многие убеждены в том, что, если сократить какой-то фрагмент до одной или двух строк, он будет максимально эффективным. Рассмотрим код инициализации мас- сива из 10 элементов: for i = 1 to 10 a[ i ] = i end for Как вы думаете, он выполнится быстрее или медленнее, чем эти 10 строк, решаю- щих ту же задачу? a[ 1 ] = 1 a[ 2 ] = 2 a[ 3 ] = 3 a[ 4 ] = 4 a[ 5 ] = 5 a[ 6 ] = 6 a[ 7 ] = 7 a[ 8 ] = 8 a[ 9 ] = 9 a[ 10 ] = 10 Если вы придерживаетесь старой догмы «меньшее число строк выполняется быс- трее», вы скажете, что первый фрагмент быстрее. Однако тесты на Microsoft Visual Basic и Java показали, что второй фрагмент минимум на 60% быстрее первого. Время Время выполнения выполнения последовательного Экономия Соотношение Язык цикла for кода времени быстродействия Visual Basic 8,47 3,16 63% 2,5:1 Java 12,6 3,23 74% 4:1 Примечания: (1) Временные показатели в этой и следующих таблицах данной главы ука- зываются в секундах, а их сравнение имеет смысл только в пределах конкретных строк каждой из таблиц. Действительные показатели будут зависеть от компилятора, парамет- ров компилятора и среды, в которой выполняется тестирование. (2) Большинство резуль- татов сравнительного тестирования основано на выполнении фрагментов кода от несколь- ких тысяч до многих миллионов раз, что призвано устранить колебания результатов. (3) Конкретные марки и версии компиляторов не указываются. Показатели производитель- ности во многом зависят от марки и версии компилятора. (4) Сравнение результатов те- стирования фрагментов, написанных на разных языках, имеет смысл не всегда, так как компиляторы разных языков не всегда позволяют задать одинаковые параметры генери- рования кода. (5) Фрагменты, написанные на интерпретируемых языках (PHP и Python), в большинстве случаев тестировались с использованием более чем в 100 раз меньшего числа тестов, чем фрагменты, написанные на других языках. (6) Некоторые из показателей «эко- номии времени» не совсем точны из-за округления «времени выполнения кода до опти- мизации» и «времени выполнения оптимизированного кода». ГЛАВА 25 Стратегии оптимизации кода 579 Разумеется, это не значит, что увеличение числа строк высокоуровневого кода всегда приводит к повышению быстродействия или сокращению объема програм- мы. Это означает, что независимо от эстетической привлекательности компакт- ного кода ничего определенного о связи между числом строк кода на высокоуров- невом языке и объемом и быстродействием итоговой программы сказать нельзя. Одни операции, вероятно, выполняются быстрее или компактнее других — НЕВЕРНО! Если речь идет о производительности, не может быть никаких «ве- роятно». Без измерения производительности вы никак не сможете точно узнать, помогли ваши изменения программе или навредили. Правила игры изменяются при каждом изменении языка, компилятора, версии компилятора, библиотек, вер- сий библиотек, процессора, объема памяти, цвета рубашки, которую вы надели (ладно, это шутка), и т. д. Результаты, полученные на одном компьютере с одним набором инструментов, вполне могут оказаться противоположными на другом ком- пьютере с другим набором инструментов. Исходя из этого, можно назвать несколько причин, по которым производитель- ность не следует повышать путем оптимизации кода. Если программа должна быть портируемой, помните: методики, повышающие производительность в одной среде, могут снижать ее в других. Если вы решите изменить или модернизировать ком- пилятор, возможно, новый компилятор будет автоматически выполнять те виды оптимизации, что вы выполнили вручную, и все ваши усилия окажутся бесполез- ными. Хуже того: оптимизировав код, вы можете помешать компилятору выпол- нить более эффективные виды оптимизации, ориентированные на простой код. Оптимизируя код, вы обрекаете себя на перепрофилирование каждого оптими- зированного фрагмента при каждом изменении марки компилятора, его версии, версий библиотек и т. д. Если вы не будете перепрофилировать код, оптимизация, бывшая выгодной, после изменения среды сборки программы вполне может стать невыгодной. Оптимизацию следует выполнять по мере написания кода — НЕВЕРНО! Кое-кто утверждает, что если вы буде- те стремиться написать самый быстрый и компактный код при работе над каждым методом, то итоговая программа бу- дет быстрой и компактной. Однако на самом деле это ме- шает увидеть за деревьями лес, и программисты, чрезмер- но поглощенные микрооптимизацией, начинают упускать из виду по-настоящему важные глобальные виды оптимизации. Основные недо- статки этого подхода рассмотрены ниже. 쐽 До создания полностью работоспособной программы найти узкие места в коде почти невозможно. Программисты очень плохо угадывают, на какие 4% кода приходятся 50% времени выполнения, поэтому, оптимизируя код по мере его написания, они будут тратить примерно 96% времени на оптимизацию кода, который не нуждается в оптимизации. На оптимизацию по-настоящему важ- ных 4% кода времени у них уже не останется. 쐽 В тех редких случаях, когда узкие места определяются правильно, разработ- чики уделяют им слишком большое внимание, и критически важными стано- вятся уже другие узкие места. Результат очевиден: все то же снижение произ- Возможности небольшого повы- шения эффективности следует игнорировать, скажем, в 97% случаев: необдуманная оптими- зация — корень всего зла. Дональд Кнут (Donald Knuth) 580 ЧАСТЬ V Усовершенствование кода водительности. Если оптимизация выполняется после создания полной систе- мы, разработчики могут определить все проблемные области и их относитель- ную важность, что способствует эффективному распределению времени. 쐽 Концентрация на оптимизации во время первоначальной разработки отвле- кает от достижения других целей. Разработчики погружаются в анализ алго- ритмов и сокровенные дискуссии, от которых пользователям ни тепло, ни хо- лодно. Корректность, сокрытие информации, удобочитаемость и т. д. стано- вятся вторичными целями, хотя потом улучшить их сложнее, чем производи- тельность. Работа над повышением производительности после создания пол- ной программы обычно затрагивает менее 5% кода. Что легче: повысить про- изводительность 5% кода или улучшить удобочитаемость всего кода? Короче говоря, главный недостаток преждевременной оптимизации — отсутствие перспективы. Это сказывается на быстродействии итогового кода, других, еще более важных атрибутах производительности и качестве программы, ну а расплачиваться за это в итоге приходится пользователям. Если время, сэкономленное благодаря реализации наиболее простой программы, посвятить ее последующей оптимиза- ции, итоговая программа непременно будет работать быстрее, чем программа, разработанная с использованием неорганизованного подхода к оптимизации (Stevens, 1981). Иногда оптимизация программы после ее написания не позволяет достичь нуж- ных показателей производительности, из-за чего приходится вносить крупные изменения в завершенный код. Можете утешить себя тем, что в этих случаях оп- тимизация небольших фрагментов все равно не привела бы к нужным результа- там. Проблема в таких ситуациях объясняется не низким качеством кода, а неадек- ватной архитектурой программы. Если оптимизацию нужно выполнять до создания полной программы, сведите риск к минимуму, интегрировав в процесс оптимизации перспективу. Один из спосо- бов сделать это — задать целевые показатели объема и быстродействия отдель- ных функций и провести оптимизацию кода по мере его написания, направлен- ную на достижение этих показателей. Определив такие цели в спецификации, вы сможете следить сразу и за лесом, и за конкретными деревьями. Быстродействие программы не менее важно, чем ее корректность — НЕВЕРНО! Едва ли можно представить ситуацию, когда программу прежде всего нужно сделать быстрой или компактной и только потом корректной. Дже- ральд Вайнберг рассказывает историю о программисте, ко- торого вызвали в Детройт, чтобы он помог отладить нера- ботоспособную программу. Через несколько дней разработчики пришли к выво- ду, что ситуация безнадежна. На пути домой он обдумывал проблему и внезапно понял ее суть. К концу полета у него уже был набросок нового кода. В течение нескольких дней программист тестировал код и уже собирался вернуться в Детройт, но тут получил телеграмму, в которой утверждалось, что работа над проектом прекращена из-за невозмож- ности написания программы. И все же он снова прилетел в Детройт и убедил руководителей в том, что проект можно было довести до конца. Дополнительные сведения Опи- сания других занимательных и поучительных случаев можно найти в книге Джеральда Вай- нберга «Psychology of Computer Programming» (Weinberg, 1998). ГЛАВА 25 Стратегии оптимизации кода 581 Далее он должен был убедить в этом участников проекта. Они выслушали его, и когда он закончил, создатель старой системы спросил: — И как быстро выполняется ваша программа? — Ну, в среднем она обрабатывает каждый набор введенных данных примерно за 10 секунд. — Ага! Но моей программе для этого требуется только 1 секунда. Ветеран откинулся назад, удовлетворенный тем, что он приструнил выскочку. Другие программисты, похоже, согласились с ним, но новичок не смутился. — Да, но ваша программа не работает. Если бы моя не обязана была работать, я мог бы сделать так, чтобы она обрабатывала ввод почти мгновенно. В некоторых проектах быстродействие или компактность кода действительно имеет большое значение. Однако таких проектов немного — гораздо меньше, чем ка- жется большинству людей, — и их число постоянно сокращается. В этих проек- тах проблемы с производительностью нужно решать путем предварительного проектирования. В остальных случаях ранняя оптимизация представляет серьез- ную угрозу для общего качества ПО, включая производительность. Когда выполнять оптимизацию? Создайте высококачественный проект. Следите за правиль- ностью программы. Сделайте ее модульной и изменяемой, чтобы позднее над ней было легко работать. Написав кор- ректную программу, оцените ее производительность. Если программа громоздка, сделайте ее быстрой и компактной. Не оптимизируйте ее, пока не убедитесь, что это на самом деле нужно. Несколько лет назад я работал над программой на C++, ко- торая должна была генерировать графики, помогающие ана- лизировать данные об инвестициях. Написав код расчета первого графика, мы провели тестирование, показавшее, что программа отображает график пример- но за 45 минут, что, конечно, было неприемлемо. Чтобы решить, что с этим де- лать, мы провели собрание группы. На собрании один из разработчиков выкрик- нул в сердцах: «Если мы хотим иметь хоть какой-то шанс выпустить приемлемый продукт, мы должны начать переписывать весь код на ассемблере прямо сейчас». Я ответил, что мне так не кажется — что около 50% времени выполнения скорее всего приходятся на 4% кода. Было бы лучше исправить эти 4% в конце работы над проектом. После еще некоторых споров наш руководитель поручил мне по- работать над производительностью программы (что мне и было нужно: «О, нет! Только не бросай меня в тот терновый куст!» 1 ). Как часто бывает, я очень быстро нашел в коде пару ослепительных узких мест. Внеся несколько изменений, я снизил время рисования с 45 минут до менее чем 30 секунд. Гораздо меньше 1% кода соответствовало 90% времени выполнения. Правила оптимизации Джексо- на: Правило 1. Не делайте это- го. Правило 2 (только для экс- пертов). Не делайте этого пока — до тех пор, пока вы не по- лучите совершенно ясное не- оптимизированное решение. М. А. Джексон (M. A. Jackson) 1 Часто цитируемая фраза из негритянской сказки про Братца Кролика и Братца Волка в изло- жении У. Фолкнера. — Прим. перев. 582 ЧАСТЬ V Усовершенствование кода Ну, а к моменту выпуска ПО нам удалось сократить время рисования почти до 1 секунды. Оптимизация кода компилятором Современные компиляторы могут оптимизировать код куда эффективнее, чем вам кажется. В случае, который я описал выше, мой компилятор выполнил оптимиза- цию вложенного цикла так эффективно, что я едва ли получил бы лучшие резуль- таты, переписав код. Покупая компилятор, сравните производительность каждо- го компилятора с использованием своей программы. Каждый компилятор имеет свои плюсы и минусы, и одни компиляторы лучше подходят для вашей програм- мы, чем другие. Оптимизирующие компиляторы лучше оптимизируют простой код. Если вы жон- глируете индексами циклов и делаете другие «хитрые» вещи, компилятору будет труднее выполнить свою работу, от чего пострадает ваша программа. В подразде- ле «Размещение одного оператора на строке» раздела 31.5 вы найдете пример про- стого кода, который после оптимизации компилятором оказался на 11% быстрее, чем аналогичный «хитрый» код. Хороший оптимизирующий компилятор может повысить быстродействие кода на 40 и более процентов, тогда как многие из методик, описанных в следующей гла- ве, — только на 15–30%. Так почему ж просто не написать ясный код и не позво- лить компилятору выполнить свою работу? Вот результаты нескольких тестов, показывающие, насколько успешно компиляторы оптимизировали метод встав- ки-сортировки: Время выполне- Время выполне- ния кода, оптими- ния кода без зированного Экономия Соотношение Язык оптимизации компилятором времени быстродействия Компилятор C++ 1 2,21 1,05 52% 2:1 Компилятор C++ 2 2,78 1,15 59% 2,5:1 Компилятор C++ 3 2,43 1,25 49% 2:1 Компилятор C# 1,55 1,55 0% 1:1 Visual Basic 1,78 1,78 0% 1:1 Java VM 1 2,77 2,77 0% 1:1 Java VM 2 1,39 1,38 <1% 1:1 Java VM 3 2,63 2,63 0% 1:1 Единственное различие между версиями метода заключалось в том, что при пер- вой компиляции оптимизация была отключена, а при второй включена. Очевид- но, что одни компиляторы выполняют оптимизацию лучше, чем другие, а неко- торые изначально генерируют максимально эффективный код без его оптимиза- ции. Некоторые виртуальные машины Java (Java Virtual Machine, JVM) также бо- лее эффективны, чем другие. Эффективность вашего компилятора или вашей JVM может быть другой; оцените ее сами. |