Оптимизация программ

Вся наша жизнь — это борьба с тормозами и нехваткой времени. Каждый день мы тратим по несколько часов на оптимизацию. Каждый из нас старается оптимизировать все, что попадает под руку. А вы уверены, что вы это делаете правильно? Может быть, есть возможность что-то сделать еще лучше?

Я понимаю, что все сейчас разленились и выполняют свои обязанности спустя рукава. Лично я до такой степени привык, что за меня все делает компьютер, что даже забыл, как выглядит шариковая ручка. Недавно мне довелось писать заявление на отпуск на простой бумаге, так я долго вспоминал, как пишется буква "ю". Пришлось подглядывать, как она выглядит на клавиатуре. Это не шутка. Это прогресс, благодаря которому я все делаю на компьютере.

Даже для того, чтобы написать текст из двух строк, мы включаем свой ком­пьютер и загружаем MS Word, тратя на это драгоценное время. А может, легче было бы написать этот текст вручную? Я вас понимаю — не солидно!!!

Программисты — так это вообще "полное бесстыдство", как говорил один из моих преподавателей: "Тра-та-та". Они считают, что раз их творение (в виде исходного кода) никто не увидит, то можно писать что угодно. Так это они ошибаются. С этой точки зрения программы с открытым исходным кодом имеют большое преимущество, потому что намного чище и быстрей. Создавая код, мы ленимся его оптимизировать не только с точки зрения размера, но и с точки зрения скорости. Глядя на такие вещи, хочется ругаться непри­стойными словами, только программа от этого лучше не станет.

Хакеры далеко не ушли. Если раньше, глядя на программиста или хакера, создавался образ прокуренного, заросшего и немытого молодого человека, то сейчас это цифровое существо, залитое пивом "Балтика" по самые уши, за которое все выполняют машины. Вам медсестра в поликлинике не гово­рила, что у вас вместо крови одно только пиво льется? Я ничего против пи­ва не имею, я и сам его люблю, но надо же и меру знать.

Все это — деградация по методу MS !!! Мы берем в руки мышку и начинаем тыкать ею, где попало, забывая про клавиатуру и горячие клавиши. Я счи­таю, что надо бороться с этим. В последнее время меня самого посещает такая лень, что я убираю клавиатуру, запускаю экранную клавиатуру и начинаю работать только мышкой. Осталось только покрыть мое тело шерстью и посадить в клетку к таким же ленивым шимпанзе.

Не надо тратить большие деньги на модернизацию компьютера!!! Лучше начните изменения с себя. Давайте оптимизируем свою работу и свои тво­рения, и тогда компьютер заработает намного быстрее.

Изначально эта часть книги задумывалась как рассказ об оптимизации кода программ. Но в последствии я перенес сюда свой "труд", который можно найти на моем сайте, потому что оптимизировать надо все. Я буду говорить про теорию оптимизации, а ее законы действуют везде. По одним и тем же законам вы можете оптимизировать свой распорядок дня, чтобы успевать все сделать, и свою ОС, чтобы она работала быстрей. Но основное все же будет относиться к коду программ. Здесь будет приведено немного больше информации, чем в статье, которую можно увидеть на сайте.

Как всегда я постараюсь давать больше реальных примеров, чтобы вы смогли убедиться в том, что вам не вешают очередную лапшу на уши, и смогли применить все сказанное на практике.

Начну я с законов, которые работают не только в программировании, но и в реальной жизни. Ну, а напоследок оставлю только то, что может пригодиться при оптимизации кода.

ЗАКОН № 1

Оптимизировать можно все. Даже там, где вам кажется, что все и так работает быстро, можно сделать еще быстрее.

Это действительно так. И этот закон очень сильно проявляется в програм­мировании. Идеального кода не существует. Даже простую операцию сложения 2 + 2 тоже можно оптимизировать. Чтобы достичь максимального результата, нужно действовать последовательно и, желательно, в том порядке, в котором описано ниже.

Помните, что любую задачу можно решить хотя бы двумя способами (или больше), и ваша задача — выбрать наилучший метод, который обеспечит желаемые производительность и универсальность.

ЗАКОН № 2

Первое, с чего нужно начинать, — это с поиска самых слабых и медленных мест.

Зачем начинать оптимизацию с того, что и так работает достаточно быстро! Если вы будете оптимизировать сильные места, то можете встретить неожи­данные конфликты. Да и эффект будет минимален.

Тут же я вспоминаю пример из своей собственной жизни. Где-то в 1996 году меня посетила одна невероятная идея — написать собственную игру в стиле Doom . Я не собирался ее делать коммерческой, а хотел только потренировать свои мозги на сообразительность. Четыре месяца невероятного труда, и нечто похожее на движок уже было готово. Я создал один голый уровень, по которому можно было перемещаться, и с чувством гордости побежал по коридорам.

Никаких монстров, дверей и атрибутики на нем не было, а тормоза ощущались достаточно значительные. Тут я представил себе, что будет, если добавить монстров и атрибуты, да еще и наделить все это AI ... Вот тут чувство собственного достоинства поникло. Кому нужен движок, который при разрешении 320x200 (тогда это было круто!) в голом виде тормозит со страшной силой? Вот именно...

Понятное дело, что мой виртуальный мир нужно было оптимизировать. Целый месяц я бился над кодом и вылизывал каждый оператор моего движ­ка. Результат — мир стал прорисовываться на 10% быстрей, но тормозить не перестал. И тут я увидел самое слабое место — вывод на экран. Мой движок просчитывал сцены достаточно быстро, а пробоиной был именно вывод изображения. Тогда еще не было шины AGP , и я использовал простую PCI-видеокарту от S3 с 1 Мбайт памяти. Пара часов колдовства, и я выжал из PCI все возможное. Откомпилировав движок, я снова загрузился в свой виртуальный мир. Одно нажатие клавиши "вперед", и я очутился у противо­положной стены. Никаких тормозов, сумасшедшая скорость просчета и мо­ментальный вывод на экран.

Как видите, моя ошибка была в том, что вначале я неправильно определил слабое место своего движка. Я месяц потратил на оптимизацию математики, и что в результате? Мизерные 10% прироста производительности. Но когда я реально нашел слабое звено, то смог повысить этот параметр в несколько раз.

Именно поэтому я говорю, что надо начинать оптимизировать только со слабых мест. Если вы ускорите работу самого слабого звена вашей программы, то, может быть, и не понадобится ускорять другие места. Вы можете потратить дни и месяцы на оптимизацию сильных сторон и увеличить производительность только на 10% (что может оказаться недостаточным), или несколько часов на совершенствование слабой части и получить улучшение в 10 раз!

Слабые места компьютера

Меня поражают люди, которые гонятся за мегагерцами процессора и сидят на доисторической видеокарте от S3, жестком диске на 5400 оборотов и с 32 Мбайт памяти. Посмотрите в корпус своего компьютера и оцените его содержимое. Если вы увидели, что памяти у вас не более 64 Мбайт, то встаньте и громко произнесите: "Уважаемый DIMM , команда выбрала вас. Вы сегодня самое слабое звено и должны покинуть мой компьютер". После этого покупаете себе 128, а лучше 256, а еще лучше 512 Мбайт памяти и наслаждаетесь ускорением работы Visual C++, Photoshop и других "тяжелых" программ.

В данном случае наращивание сотни мегагерц у процессора даст меньший прирост в скорости. Если вы используете "тяжелые" приложения при нехватке памяти, то процессор начинает тратить слишком много времени на загрузку и выгрузку данных в файл подкачки. Ну, а если в вашем компьютере достаточно оперативной памяти, то процессор уже занимается только расчетами и не расходует драгоценное время на лишние загрузки/выгрузки.

То же самое с видеоадаптером. Если видеокарта у вас слабенькая, то процессор будет просчитывать сцены быстрей, чем они будут выводиться на экран.

Поэтому наращивание тактовой частоты процессора грозит простоями и минимальным приростом производительности. Хорошая видеокарта наоборот способна не только быстрее выводить данные, но и освободить центральный процессор от некоторых расчетов.

ЗАКОН № 3

Следующим шагом вы должны разобрать по косточкам все операции и выяснить, где они регулярно повторяются. Начинать оптимизацию нужно именно с них.

Опять начнем рассмотрение этого закона с программирования. Допустим, что у вас есть следующий код (приведена просто логика, а не реальная программа):

1. А:=А*2;

2. Б:=1;

3. X:=X+Б;

4. Б:=Б+1;

5. Если Б<100, то перейти на шаг 3.

Любой программист скажет, что здесь слабым местом является первая строка, потому что там используется умножение. Это действительно так. Умножение всегда выполняется дольше, и если заменить его на сложение (A:=A+A) или еще лучше на сдвиг, то вы выиграете пару тактов процессорного времени. Но это только пару тактов, и для процессора это будет незаметно.

Теперь посмотрите еще раз на наш код. Больше ничего не видите? А я вижу. В этом коде используется цикл: "Пока Б<100, будет выполняться опера­ция Х:=Х+Б". Это значит, что процессору придется выполнить 100 перехо­дов с шага 5 на шаг 3. А это уже не мало. Как можно здесь что-то оптимизировать? Очень легко. В этом месте у нас выполняются две строки: 3 и 4. А что, если мы внутри цикла размножим их 2 раза:

1. Б:=1;

2. X:=X+Б;

3. Б:=Б+1;

4. X:=X+Б ;

5. Б:=Б+1;

6. Если Б<50, то перейти на шаг 3.

Здесь мы видоизменили цикл. Вторую и третью операции мы повторили два раза. Это значит, что за один проход нового цикла выполняются два раза строки 3 и 4, и только после этого произойдет переход на строку 3 для повторения операции. Такой цикл уже нужно повторить только 50 раз (потому что за один проход выполняется два действия). Это значит, что мы сэконо­мили 50 операций переходов. Неплохо? А это уже несколько сотен тактов процессорного времени.

А что, если внутри цикла написать строки 2 и 3 десять раз. Это значит, что за один проход цикла строки 2 и 3 будут вычисляться 10 раз, и мне понадо­бится повторить такой цикл только 10 раз, чтобы получить в результате 100. А это уже экономия 90 операций переходов.

Недостаток этого подхода — увеличился код нашей программы, зато повы­силась скорость и очень значительно. Этот способ очень хорош, но им не стоит злоупотреблять. С одной стороны, увеличивается скорость, а с другой — увеличивается размер. А большой размер — это враг любой программы. Поэтому надо находить золотую середину.

В любом деле главное — разумная достаточность. Чем больше вы увеличиваете код ради оптимизации скорости, тем меньше результирующий эффект от оптимизации.

В жизни таких примеров намного больше. Любую циклическую операцию можно оптимизировать. Хотите пример? Пожалуйста. Допустим, у вашего провайдера Интернета есть несколько телефонов доступа. Вы каждый день перезваниваете на каждый из них в ожидании найти свободный. Начинающий тут же скажет, что провайдер обязан оптимизировать свои пулы моде­мов в один, чтобы не надо было трезвонить по всем номерам сразу. Но опытный пользователь должен знать, что не у каждого есть хорошая связь с любой телефонной станцией города. Поэтому провайдеры держат пулы на разных станциях, чтобы вы могли выбрать тот, с которым связь лучше. Поставьте программу-дозвонщик (таких сейчас полно в Интернете), которая сама будет перебирать номера телефонов.

А теперь другой пример — вам на 1 час досталась карточка какого-то нового провайдера. Заносить ее в программу дозвона не имеет смысла, потому что вы можете больше никогда не позвонить ему. Из-за этой одноразовой операции вам придется перенастраивать свой дозвонщик сначала на нового провайдера, потом обратно, а выигрыш практически нулевой, потому что пока вы меняете настройки, уже можно было дозвониться стандартными средствами Windows. Отсюда сразу же напрашивается вывод — нужно пра­вильно выбирать средства для выполнения необходимых задач.

ЗАКОН № 4

(Этот закон — расширение предыдущего.)

Оптимизировать одноразовые операции — это только потеря времени. Сто раз подумай, прежде чем начать мучиться с редкими операциями.

Полгодика назад я прочитал рассказ в Интернете "Записки жены программиста" (http://www.exler.ru/novels/wife.htm). Очень даже некислый и жиз­ненный рассказ. Когда я его читал, у меня было ощущение, что его написала моя жена. Слава "Красной Шапочке", что она на такую подлость не способна. Так вот там была такая ситуация.

Очаровательная девушка выходит замуж за программиста, и им надо разослать приглашения на свадьбу. Вместо того, чтобы просто набрать их, программист кричит, что он крутой, и пишет специальную программу. Ее разработка заняла один день, и столько же — отладка.

Главная ошибка — неправильная оптимизация своего труда. Легче подготовить шаблон в любом текстовом редакторе, а потом только менять фамилии приглашенных на это траурное событие (это я сужу по себе). Но даже если нет текстового редактора, писать программу действительно нет смысла. Затраты большие, а пользоваться ей будете только один раз. Здесь действительно легче будет даже напечатать на пишущей машинке.

Получается, что одноразовые операции оптимизировать просто бессмысленно. Затраты в этом случае себя не окупают, поэтому не стоит тратить свои нервы на этот бессмысленный труд.

В самом начале этого раздела я раскритиковал вас как человека, который ленится хоть что-нибудь делать. Так вот, именно здесь вы можете проявлять свою врожденную леность в полном объеме. В данном случае крутым считается не тот, кто целый день промучился и ничего не добился, а тот, кто выполнил свою работу быстрее и эффективнее. И эти две вещи путать нельзя.

ЗАКОН № 5

Нужно знать "внутренности" компьютера и принципы его работы. Чем лучше вы знаете, каким образом компьютер будет выполнять ваш код, тем лучше вы сможете его оптимизировать.

Этот закон относится только к программированию. Тут трудно привести полный набор готовых решений, но некоторые приемы я постараюсь описать.

1. Старайтесь поменьше использовать вычисления с плавающей запятой. Любые операции с целыми числами выполняются в несколько раз быстрее.
2. Операции умножения и тем более деления так же выполняются достаточно долго. Если вам нужно умножить какое-то число на 3, то для про­цессора будет легче три раза сложить одно и то же число, чем выполнить умножение.
   А как же тогда экономить на делении? Вот тут нужно знать математику. У процессора есть такая операция, как сдвиг. Вы должны знать, что про­цессор думает в двоичной системе, и числа в компьютере хранятся именно в ней. Например, число 198 для процессора будет выглядеть как 11000110. Теперь посмотрим, как работают операции сдвига.
   Сдвиг вправо — если сдвинуть число 11000110 вправо на одну позицию, то последняя цифра исчезнет и останется только 01100011. Теперь введите это число в калькулятор и переведите его в десятичную систему. Ваш результат должен быть 99. Как видите — это ровно половина числа 198.
   Вывод: при сдвиге числа вправо на одну позицию вы делите его на 2.
   Сдвиг влево — возьмем то же самое число 11000110. Если сдвинуть его влево на одну позицию, то с правой стороны освободится место, которое заполняется нулем — 1 10001100. Теперь переведите это число в десятич­ную систему. Должно получится 396. Что оно вам напоминает? Это 198, умноженное на 2.
   Вывод: при сдвиге числа влево вы умножаете его на 2.
   Так что используйте сдвиги везде, где возможно, потому что эти операции работают в несколько раз быстрее умножения и деления (и даже сложения и вычитания).
3. При создании функций (процедур) не обременяйте их большим количеством входных параметров. Перед каждым вызовом функции (процедуры) ее параметры прячутся в стек, а после выхода извлекаются оттуда. Чем больше параметров, тем значительнее расходы на общение со стеком.
   Тут же нужно сказать, что вы должны действовать аккуратно и с самими параметрами. Не вздумайте пересылать процедурам переменные, которые могут содержать данные большого объема в чистом виде. Лучше передать адрес ячейки памяти, где хранятся данные, а внутри процедуры работать с этим адресом. Вот представьте себе ситуацию, когда вам нужно передать текст размером в один том "Войны и мира"... Перед входом в процедуру программа попытается вогнать все это в стек. Если вы не увидите его переполнение, то задержка точно будет значительная.
4. В самых критических ситуациях (например, вывод на экран) можно воспользоваться языком Assembler. Даже встроенный в C++ или Delphi ассемблер намного быстрее штатных функций языка. Ну, а если скорость в каком-то месте уж слишком критична, то ассемблерный код можно вынести в отдельный модуль. Там его нужно откомпилировать с помощью компиляторов TASM или MASM и подключить к своей программе.
   Ассемблер — достаточно быстрая и компактная вещь, но писать достаточно большой проект только на нем очень сложно. Поэтому я не советую им увлекаться, и использовать его только в самых критических по скорости местах.

ЗАКОН № 6

Для сложных расчетов можно подготовить таблицы с заранее определенными результатами и потом использовать эти таблицы в реальном режиме времени.

Когда появился первый Doom, игровой мир поразился качеству графики и скорости работы. Это действительно был шедевр программистской мысли, потому что компьютеры того времени не могли рассчитывать трехмерную графику в реальном времени. В те годы еще даже и не думали о 3D-ускорителях, и видеокарты занимались только отображением информации и не выполняли никаких дополнительных расчетов.

Как же тогда программистам игры Doom удалось создать трехмерный мир? Секрет прост, как и все в этом мире. Игра не просчитывала сцены, все сложные математические расчеты были произведены заранее и занесены в отдельную базу (таблицу), которая запускалась при старте программы. Конечно же, занести все возможные результаты нереально, поэтому база хранила основные результаты. Когда нужно было получить значение, которого не было в заранее рассчитанной таблице, то бралось наиболее близкое число. Таким образом, Doom получил отличную производительность и достаточное качество 3D-картинки.

С выходом программы Quake игровой мир опять поразился качеству освещения и теней в сценах ее виртуального мира. Расчет света — очень сложная задача, не говоря уже о тенях. Как же тогда программисты игры смогли добиться такого качества сцен и в то же время высокой скорости работы игры? Ответ опять будет таким же — за счет таблиц с заранее рассчитанными значениями.

Через некоторое время игровая индустрия поразилась еще больше. Когда вышел Quake 3, в котором освещение рассчитывалось в реальном времени, то его мир казался исскуственным, и даже Half-Life , который вышел позже и на движке старого Quake , выглядел намного естественнее и привычнее. Это получилось в результате того, что мощности компьютера не хватило для полных расчетов в реальном времени, а округления и погрешности пошли не на пользу игровому окружению.

И при всем при этом Quake всегда был легендарным и останется подлинным шедевром от настоящих хакеров.

ЗАКОН № 7

Лишних проверок не бывает.

Чаще всего оптимизация может привести к нестабильности исполняемого кода, потому что для увеличения производительности некоторые убирают ненужные на первый взгляд проверки. Запомните, что ненужных проверок не бывает! Если вы думаете, что какая-то нестандартная ситуация может и не возникнуть, то она не возникнет только у вас. У пользователя, который будет эксплуатировать вашу программу, может возникнуть все, что угодно. Он непременно нажмет на то, на что не нужно, или введет неправильные данные.

Обязательно делайте проверки всего того, что вводит пользователь. Делайте это сразу же, и не ждите, когда введенные данные понадобятся.

По возможности не выполняйте проверки в цикле, а выносите все за его пределы. Любые лишние операторы if внутри цикла очень сильно влияют на производительность.

Циклы — это слабое место любой программы, поэтому оптимизацию надо начинать именно с них. Внутри циклических операций не должно выполняться ничего лишнего — ведь это будет повторено много раз!

ЗАКОН № 8

Не переусердствуйте с оптимизацией. Слишком большие затраты на ускорение выполнения кода могут свести на нет приложенные усилия. Ставьте перед собой реальные цели и задачи.

Если у вас не получилось оптимизировать ваш код до необходимой степени, то нет смысла продолжать долгие попытки и мучения. Возможно, будет легче найти совершенно другой способ решения проблемы.

Не всегда получается добиться идеала, потому что оптимизация скорости и оптимизация качества — часто противоположные вещи. Лучше всего это заметно на примере программирования графики. Чтобы сцена (например, в компьютерных играх) выводилась на экран быстрее, можно сделать приближенные, но быстрые расчеты. Но тогда изображение получается невысокого качества. Поэтому очень часто приходится выбирать что-то одно.

В графических редакторах жертвуют скоростью, потому что тут не требуются расчеты в реальном времени. А вот в играх поступаться приходится качеством, иначе играть будет невозможно.

Итог

Если вы прочитали этот раздел внимательно, то можете считать, что с азбукой оптимизации вы уже знакомы. Но это только основы, и тут есть куда развиваться. Я бы мог рассказать больше, но не вижу особого смысла, потому что оптимизация — это процесс творческий, и в каждой конкретной ситуации к нему можно подойти с разных сторон. И все же те законы, которые мы сегодня рассмотрели, действуют в 99,9% случаев.

Если вы хотите познать теорию оптимизации в программировании более глубоко, то вам нужно больше изучать принципы работы процессора и операционных систем. Главное, что законы вы уже знаете, а остальное придет со временем.

• Copyright | © LIMN ™ | logotip  | 2010 |
Visual C++ | 
• Valid
CSS | Valid XHTML Strict