Почему книга не в разделе "Ресурсы"? Потому что

1. классика
2. потому что не в pdf, djvu, chm а в формате html
3. первые три главы взяты на http://netlib.narod.ru
4. а дальше 67 глав сам, сам. сам...

​

• Аннотация
• Предисловие
• Введение
• Благодарности
• Часть I
  • Глава 1. Лучший оптимизатор у вас между ушей
    • Человеческий фактор в оптимизации кода
    • Что такое быстродействие
      • Когда быстро — не быстро
      Правила построения быстродействующего кода
      • Знайте, куда вы идете
      • Создайте общий план
      • Создайте набор детальных планов
      • Изучите территорию
      • Узнайте, что имеет значение
      • Всегда рассматривайте альтернативы
      • Узнайте, как выжать сок
      Где мы были, что мы видели
      • Куда мы идем
  • Глава 2. Особенный мир
    • Уникальная природа оптимизации языка ассемблера
    • Команды: по отдельности и вместе
    • Фундаментальные отличия ассемблера
      • Преобразование без потери эффективности
      • Самообеспеченность
      • знания
      Гибкий разум
      • С чего начать?
  • Глава 3. Ничего не предполагайте
    • Постижение и использование Дзен-таймера
    • Цена невежества
• Часть II. Программирование графики
  • Глава 4
  • Глава 5
  • Глава 6
  • Глава 7
  • Глава 8
  • Глава 9
  • Глава 10
  • Глава 11
  • Глава 12
  • Глава 13
  • Глава 14
  • Глава 15
  • Глава 16
  • Глава 17
  • Глава 18
  • Глава 19
  • Глава 20
  • Глава 21
  • Глава 22
  • Глава 23
  • Глава 24
  • Глава 25
  • Глава 26
  • Глава 27
  • Глава 28
  • Глава 29
  • Глава 30
  • Глава 31
  • Глава 32
  • Глава 33
  • Глава 34
  • Глава 35
  • Глава 36
  • Глава 37
  • Глава 38
  • Глава 39
  • Глава 40
  • Глава 41
  • Глава 42
  • Глава 43
  • Глава 44
  • Глава 45
  • Глава 46
  • Глава 47
  • Глава 48
  • Глава 49
  • Глава 50
  • Глава 51
  • Глава 52
  • Глава 53
  • Глава 54
  • Глава 55
  • Глава 56
  • Глава 57
  • Глава 58
  • Глава 59
  • Глава 60
  • Глава 61
  • Глава 62
  • Глава 63
  • Глава 64
  • Глава 65
  • Глава 66
  • Глава 67
  • Глава 68
  • Глава 69
  • Глава 70

 

Благодарности

Поскольку данная книга писалась много лет и многими способами, необычайно большое количество людей участвовало в ее создании тем или иным способом. Прежде всего, спасибо (еще раз) Джеффу Дантеманну (Jeff Duntemann) запустившему этот проект, выполнившему грязную работу, следившему за ходом вещей и воодушевлявшему всех. Спасибо Дэну Иловски (Dan Illowsky) не только за полезные идеи и ободрение, но и за то, что много лет назад, когдя я еще сомневался в собственных способностях, он побудил меня начать писать статьи и научил, как решать деловые вопросы. Спасибо Уиллу Фэйсти (Will Fastie) предоставившему мне первую возможность написать статью для широкой публики в давно прекратившем существование журнале PC Tech, которого нам все еще недостает, и показавшему мне насколько забавным это может быть в его еще более давно исчезнувшей, но исключительно потрясающей колонке в Creative Computing (самая приятная отдельная колонка, которую я когда-либо читал в компьютерном журнале; я имел обыкновение проверять почтовый ящик в начале месяца только для того, чтобы увидеть, что сказал Уилл). Спасибо Роберту Келлеру (Robert Keller), Эрин О'Коннор (Erin O'Connor), Лиз Оклей (Liz Oakley), Стиву Бейкеру (Steve Baker) и остальным тысячам, сделавшим PJ уникальным журналом — особенно Эрин, сделавшей больше всех, чтобы научить меня правильному использованию английского языка. (По сей день Эрин продолжает мне терпеливо объяснять, когда надо использовать слово «какой», а когда «который», несмотря на то, что восемь лет указаний по этой и связанным с ней темам не оставили никакого следа в моем мозге.) Спасибо Джону Эриксону (Jon Erickson), Тами Земел (Tami Zemel), Монике Берг (Monica Berg) и остальной части команды DDJ за превосходное, профессиональное редактирование и просто за то, что они хорошие люди. Спасибо банде Coriolis за их неустанную тяжелую работу: Джеффу Дантеманну (Jeff Duntemann) и Кейт Вейскамп (Keith Weiskamp) за редактирование и издание, Брэду Граннису (Brad Grannis), Робу Маухару (Rob Mauhar) и Ким Эофф (Kim Eoff) за иллюстрации, дизайн и верстку. Спасибо Джиму Мишелю (Jim Mischel), проделавшему потрясающую работу по проверке кода и его размещению на сопроводительном диске к этой книге. Спасибо Джеку Тсенгу (Jack Tseng), который обучил меня многим вещам, относящимся к графическим аппаратным средствам, и еще большему о том, насколько затрудняют работу различия. Спасибо Джону Кокерхэму (John Cockerham), Дэвиду Стаффорду (David Stafford), Тьерри Мэтисену (Terje Mathisen), Битману (BitMan), Крису Хеккеру (Chris Hecker), Джиму Макразу (Jim Mackraz), Мелвину Лэйфти (Melvin Laftte), Джону Навасу (John Navas), Филу Колману (Phil Coleman), Антону Трайнфелсу (Anton Truenfels), Джону Кармаку (John Carmack), Джону Майлзу (John Miles), Джону Бриджесу (John Bridges), Джиму Кенту (Jim Kent), Хэлу Харденбергу (Hal Hardenberg), Дэйву Миллеру (Dave Miller), Стиву Леви (Steve Levy), Джеку Дэвису (Jack Davis), Дуэйн Стронг (Duane Strong), Дэйев Рох (Daev Rohr), Биллу Веберу (Bill Weber), Дэну Гочнауэру (Dan Gochnauer), Патрику Миллигану (Patrick Milligan), Тому Уилсону (Tom Wilson), людям из темы ibm.pc/fast.code на Bix, и всем остальным, кто щедро делился своими идеями и предложениями. Я старался упомянуть здесь имена всех, кто помогал мне, но если ваше имя отсутствует, примите мои извинения и искреннюю благодарность — эта книга не вышла бы без вашей помощи. И, конечно я благодарю Шэй (Shay) и Эмили (Emily) за то, что они терпят мое увлечение писательством и компьютерами.

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

Майкл Абраш (mikeab@microsoft.com)
Беллвью, Вашингтон, 1997

 

Часть I

Глава 1
Лучший оптимизатор у вас между ушей

Человеческий фактор в оптимизации кода

Эта книга посвящена теме близкой и дорогой моему сердцу: написанию программного обеспечения, подводящего PC к грани возможного. С заводским программным обеспечением PC работает подобно 97-фунтовому микрокомпьютерному слабаку. Однако, уделите ему соответствующее внимание, и этот уродливый ящик cможет творить чудеса. Ключ в следующем: только на микрокомпьютерах в вашем распоряжении находится вся машина без слоев операционной системы, драйверов и прочих помех. Вы можете делать все, что пожелаете, и, если хотите, можете понять как все это действует.

Как мы вскоре увидим, подобное желание действительно необходимо.

Является ли быстродействие реальной проблемой в эру компьютеров с процессором Intel 486 и сверхбыстрых компьютеров с процессором Pentium? Делайте ставку. Сколько программ, которые вы реально используете, работают настолько быстро, что вы не хотите, чтобы они работали еще быстрее? Мы так часто используем медленное программное обеспечение, что когда компиляция и компоновка, занимающие на PC две минуты, выполняются на 486-м компьютере за 10 секунд, мы в экстазе — хотя, по правде говоря, мы не должны соглашаться ни на что, кроме мгновенного ответа.

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

Моя точка зрения проста: PC могут замечательно работать. Их нелегко уговорить, но сам процесс полезен и доставит вам массу удовольствия. В этой книге мы поговорим о том, как работают некоторые из этих чудес, и начнем...

...сейчас.

 

Что такое быстродействие

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

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

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

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


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

Когда быстро — не быстро

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

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

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

 

Введение

На что была похожа работа с Джоном Кармаком над Quake? Мне казалось, что меня привязали к ракете и запустили в сердце урагана. Похоже весь мир наблюдал, ожидая сможет ли id Software превзойти Doom; любые фрагменты электронной почты или бесед с посетителями распространялись в Интернете уже через несколько часов. А тем временем мы вкладывали, все что у нас было в технологии Quake. Часто, приходя утром я находил Джона работающим над новой идеей, настолько интригующей, что он не мог тратить время на сон, пока не попробовал ее. Ближе к концу, когда я большую часть времени тратил на ускорение работы программы, я проводил день в трансе, составляя оптимизированный ассемблерный код, выходил из офиса в сверкающую техасскую жару, и кое-как ехал по шоссе домой, стараясь не врезаться в пикапы, проносящиеся с обоих сторон мимо меня. Дома я проваливался в прерывистый сон ,чтобы проснувшись на следующий день, повторить все сначала. Все происходило настолько быстро, и под таким давлением, что иногда я удивляюсь, как любой из нас смог выдержать это не сгорев полностью.
В то же самое время, конечно, это было чрезвычайно захватывающе. Идеи Джона были блестящи и не кончались. Законченная версия Quake установила новый стандарт для Интернета и технологий трехмерных игр с видом от первого лица. К счастью, id отличается просвещенным подходом к совместному использованию информации, и мне позволили написать о технологиях Quake — и о том, как они работают, и о том, как они развивались. В течение двух лет, пока я работал с id, я написал ряд статей о Quake в Dr. Dobb's Sourcebook, а также детальный обзор для конференции разработчиков компьютерных игр (Computer Game Developers Conference) 1997 года. Вы найдете эти материалы в последней части книги. Они представляют редкий взгляд на разработку и внутреннюю работу современного программного обеспечения, и надеюсь, что от чтения вы получите столько же удовольствия, сколько я получил от разработки программы и написания статей.
Остальная часть книги содержит почти все, что я написал о графике и производительности программ в течение последнего десятилетия. Большая часть этого материала применима и сегодня, и охватывает почти все основные темы. Сюда включена большая часть второго издания книги «Zen of Graphics Programming» (остальные материалы содержатся на компакт-диске), вся книга «Zen of Code Optimization», и даже моя книга 1989 года, «Zen of Assembly Language», с ее счетчиком циклов процессора 8088, имеющим много полезных применений, включена на CD-ROM. Добавьте к этому более 20 000 слов о Quake, и вы получите большинство того, что я узнал за последнее десятилетие, в единой, аккуратной упаковке.
Я восхищен возможностью получить весь этот материал в едином печатном издании, поскольку за последние десять лет мои статьи помогли многим людям, но намного больше тех, кто хотел бы прочесть их, но не смог найти. Очень трудно собрать материалы по программированию, печатавшиеся на протяжении долгого времени (особенно, если это колонка в журнале), и я хотел поблагодарить издательство Coriolis Group и моего хорошего друга Джеффа Дантемана (Jeff Duntemann) (без которого не существовала бы не только эта книга, но и вся моя писательская карьера) за помощь в сборе материалов.
Я также хотел поблагодарить Джона Эриксона (Jon Ericson), редактора Dr. Dobb's, за ободрение и хорошее настроение и за то, что он предоставил место в журнале, где я писал о трехмерной графике в реальном времени то, что хотел. Я до сих пор удивляюсь, как мне во время работы над Quake удавалось находить время, чтобы каждые два месяца писать колонку для журнала. Эти материалы могли бы никогда не появиться, если бы Джон не сделал мою работу столь легкой и приятной.
Я также хочу поблагодарить Криса Хеккера (Chris Hecker) и Дженифер Пахлка (Jennifer Pahlka) с конференции разработчиков компьютерных игр, без чьей помощи, подталкивания и редкого заслуженного ворчания, я бы никогда не написал доклад для CGDC, который в результате стал наиболее всесторонним кратким обзором технологий Quake, из тех, что были написаны, и который приведен в этой книге.
Мне почти нечего больше сказать, чего не сказано где-нибудь в другом месте этой книги, в одном из предисловий к предыдущим книгам или в одной из многих глав. Как вы увидите во время чтения, это было настоящее десятилетие микрокомпьютерного программирования, и мне повезло не только участвовать в нем, но и написать часть его хроники.
Пусть следующее десятилетие будет таким же захватывающим!

 

Предисловие

Я начал программировать в школе на компьютере Apple II, и почти все мои ранние работы были сделаны для платформы Apple. После получения образования быстро стало очевидно, что работа на рынке Apple в конце восьмидесятых годов приведет к финансовым проблемам. Поэтому я был вынужден очень быстро перейти к среде Intel PC.
Все то, что я за несколько лет узнал об Apple, мне требовалось за несколько месяцев изучить заново, применительно к PC.
Для меня самой большой выгодой от зарабатывания денег программированием была возможность покупать все желаемые книги и журналы. Я купил их много. Я очутился на абсолютно новой для меня территории, и поэтому читал все, что попадало в мои руки. Анонсы, передовицы и даже рекламные объявления содержали информацию, поглощаемую мной.
Джон Ромеро познакомил меня со статьями Майкла Абраша. Хороший материал. Аппаратные средства машинной графики. Оптимизация кода. Знания и мудрость для честолюбивого разработчика. Кроме того, они легко читались. В течение долгого времени моим личным приключением был поиск первой книги Майкла «Zen of the Assembly Language». Я высматривал ее в каждом посещенном мною книжном магазине, но никак не мог найти. Мне пришлось обходиться найденными статьями.
Благодаря им я узнал тайны видеоконтроллера EGA и создал несколько собственных искусных трюков. Некоторые из них легли в основу серии игр Commander Keen, с которой начиналась id Software.
Годом или двумя позже, после Wolfenstein-3D, я впервые столкнулся с Майклом (в виртуальном смысле). Я был обозревателем на M&T Online — BBS, запущенной издателями Dr. Dobb's до начала Интернет-бума, — когда увидел несколько сообщений от него. Мы торговали электронной почтой, и пару месяцев, пока разработка Doom не заняла все мое время, играли роль команды гуру на форуме посвященном графике.
После того, как началось шествие Doom, друг Майкла на его новой работе помог нам снова связаться друг с другом, и я наконец получил шанс встретиться с Майклом лично.
В тот день я охрип, объясняя Майклу и заинтересованной группе его коллег все тонкости Doom. После этого каждые несколько дней я получал от Майкла электронные письма с просьбой уточнить один из моих пунктов, или с обсуждением различных аспектов будущего компьютерной графики.
В конечном счете я тоже задал вопрос — я предложил ему работу в id. «Только подумайте: возможность не отчитываться ни перед кем, писать код целый день, начать с чистого листа бумаги. Шанс для программиста сделать правильную вещь.» Это не сработало. Я был упорен, и примерно годом позже наконец уговорил его снизойти и посмотреть на id. Тогда я работал над Quake.
Переход от Doom к Quake был огромным шагом. Я знал, где хочу оказаться в конце, но не представлял полностью путь к намеченной цели. Я перепробовал огромное количество подходов, и даже ошибки многому научили меня. Должно быть, мой энтузиазм оказался заразным, поскольку Майкл принял предложение работать вместе.
Последовали героические дни программирования. Было написано несколько сотен тысяч строк кода. И переписано. И переписано. И переписано.
Оглядываясь назад, я испытываю недовольство различными аспектами Quake, но редкий человек не признает сразу технический триумф этой игры. Мы приковали внимание. Несомненно, через год я найду новые перспективы, которые заставят Quake съежиться и выглядеть неуклюжим, но в настоящее время он прекрасно выглядит и чертовски хорош для меня.
Я был очень счастлив предоставить Майклу возможность описать многие из технологий Quake в цикле журнальных статей. Мы многое узнали и, надеюсь, сумеем чему-нибудь научить.
Когда люди, не являющиеся программистами, слышат о статьях Майкла или о том, что я предоставил исходный код, я наталкиваюсь на недоуменный взгляд: «Зачем вы делаете это?».
Им этого не понять.
Программирование — это не игра с нулевым итогом. Если вы обучаете чему-то других программистов, ваши знания не уменьшаются. Я счастлив предоставить свои работы для общего пользования, поскольку делаю это из любви к программированию. Феррари — это только взятка, честно!
Эта книга содержит многие статьи, которые помогли мне начать мою карьеру программиста. Я надеюсь, что мой вклад в содержание последующих статей предоставит такие же начальные ступени для других.

Джон Кармак id Software​

 

Правила построения быстродействующего кода

Давайте рассмотрим следующие правила создания быстродействующего программного обеспечения:

• Знайте, куда вы идете (поймите цель создания программы).
• Создайте общий план (твердо держите в уме общий проект программы, чтобы различные части программы и структуры данных хорошо работали вместе).
• Создайте набор детальных планов (разработайте алгоритмы для каждой отдельной части общего проекта).
• Изучите территорию (получите точное понимание, как компьютер выполняет каждую из задач).
• Узнайте, что имеет значение (определите части программы производительность которых имеет значение и не тратьте время впустую оптимизируя все остальное).
• Всегда рассматривайте альтернативы (не зацикливайтесь на единственном подходе; разнообразие — это лучший путь, если вы умны и достаточно изобретательны).
• Узнайте, как выжать сок (когда это имеет значение, оптимизируйте код настолько хорошо, насколько сможете).

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

Знайте, куда вы идете

Если мы собираемся создавать быстродействующий код, сначала нам следует узнать, что этот код будет делать. Для примера давайте напишем программу, которая будет вычислять 16-разрядную контрольную сумму для файла. Другими словами, программа прибавляет каждый байт указанного файла к 16-разрядной сумме предыдущих байтов. Эта контрольная сумма может использоваться, чтобы удостовериться, что файл не был поврежден при передаче по модему или, что троянский вирус не записал свой код в файл. Мы будем только лишь печатать значение контрольной суммы, и сосредоточимся не на его применении, а на вычислении этого значения с максимально возможной скоростью.

Создайте общий план

Как мы будем вычислять значение контрольной суммы для указанного файла? Логичный подход состоит в том, чтобы получить имя файла, открыть указанный файл, прочитать все байты из файла, сложить их и напечатать результат. Большинство этих действий очевидно; единственная хитрая часть заключается в чтении и сложении байтов.

Создайте набор детальных планов

Фактически, мы создадим только один детальный план, поскольку только одна часть программы требует размышлений — та часть, которая читает и суммирует байты. Каков лучший способ сделать это?

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

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

Звучит хотошо, не так ли? Пример 1.1 показывает реализацию этого подхода. В нем используется функция read() языка С для чтения единственного байта, затем прочитанный байт прибавляется к значению контрольной суммы и цикл повторяется снова, пока не будет достигнут конец файла. Код компактен, прост для написания и замечательно выполняется — с одной небольшой помехой:
Он работает медленно.
ПРИМЕР 1.1 (L1-1.C)

Код (C):

1. /*
2. * Программа вычисляет 16-разрядную контрольную сумму
3. * всех байтов указанного файла. Получает байты по одному
4. * через функцию read(), позволяя DOS выполнять буферизацию
5. * всех данных.
6. */
7. #include <stdio.h>
8. #include <fcntl.h>
9.  
10. main(int argc, char *argv[]) {
11.     int Handle;
12.     unsigned char Byte;
13.     unsigned int Checksum;
14.     int ReadLength;
15.  
16.     if (argc != 2) {
17.         printf("usage: checksum filename\n");
18.         exit(1);
19.     }
20.     if ((Handle = open(argv[1], O_RDONLY | O_BINARY)) == -1) {
21.         printf("Can't open file: %s\n", argv[1]);
22.         exit(1);
23.     }
24.  
25.     /* Инициализация значения контрольной суммы */
26.     Checksum = 0;
27.  
28.     /* Прибавляем каждый байт к контрольной сумме */
29.     while ((ReadLength = read(Handle, &Byte, sizeof(Byte))) > 0) {
30.         Checksum += (unsigned int) Byte;
31.     }
32.     if (ReadLength == -1) {
33.         printf("Error reading file %s\n", argv[1]);
34.         exit(1);
35.     }
36.  
37.     /* Печать результата */
38.     printf("The checksum is: %u\n", Checksum);
39.     exit(0);
40. }

В таблице 1.1 показано время, необходимое примеру 1.1 для вычисления контрольной суммы файла со словарем синонимов редактора WordPerfect версии 4.2, TH.WP (размером 362 293 байт), на обычном компьютере IBM PC AT с тактовой частотой процессора 10 МГц. Время выполнения приводится для примера 1.1, компилируемого компиляторами Borland и Microsoft, как с оптимизацией, так и без. Все четыре времени примерно одинаковы, и все четыре слишком велики, чтобы считаться приемлемыми. Пример 1.1 требует более двух с половиной минут на вычисление контрольной суммы одного файла!
Пример 1.2 и пример 1.3 представляют написанный с использованием С и ассемблера эквивалент примера 1.1, а пример 1.6 и пример 1.7 представляют написанный с использованием С и ассемблера эквивалент примера 1.5.

Эти примеры поясняют, что надеяться, будто оптимизирующий компилятор сделает ваши программы быстрыми — это безумие. Пример 1.1 плохо спроектирован и никакая оптимизация компилятора не компенсирует этот недочет. В качестве точки отсчета рассмотрим пример 1.2 и пример 1.3, которые вместе являются эквивалентом примера 1.1, за исключением того, что цикл вычисления контрольной суммы написан целиком на ассемблере. Как видно из таблицы 1.1, реализация на языке ассемблера действительно быстрее, чем любая из версий на С, но увеличение скорости составляет всего 10 процентов и программа все равно выполняется недопустимо медленно.

Таблица 1.1. Время вычисления контрольной суммы файла WordPrefect

Пример	Borland без оптимизации​	Microsof без оптимизации​	Borland с оптимизацией​	Microsoft с оптимизацией​	Ассемблер	Соотношение, достигнутое оптимизацией​
1	166,9	166,8	167,0	165,8	155,1	1,08
4	13,5	13,6	13,5	13,5		1,01
5	4,7	5,5	3,8	3,4	2,7	2,04
Соотношение, достигнутое улучшением проекта​	35,51	30,33	43,95	48,76	57,44

Примечание. Время выполнения (в секундах) для примеров из этой главы измерялось, когда скомпилированные примеры обрабатывали файл словаря синонимов из WordPrefect 4.2 TH.WP (размером 362 293 байт). Примеры компилировались для модели памяти small компиляторами Borland и Microsoft с включенной и выключенной оптимизацией. Время измерялось программой TIMER компании Paradigm Systems на клоне IBM PC AT с центральным процессором, работающим на частоте 10 МГц, одним тактом ожидания и жестким диском со временем доступа 28 мс и выключенным кэшированием.
ПРИМЕР 1.2 (L1-2.C)

Код (C):

1. /*
2. * Программа вычисляет 16-разрядную контрольную сумму
3. * потока байтов из заданного файла. Фрагмент на ассемблере
4. * получает байты по одному через прямой вызов DOS.
5. */
6.  
7. #include <stdio.h>
8. #include <fcntl.h>
9.  
10. main(int argc, char *argv[]) {
11.     int Handle;
12.     unsigned char Byte;
13.     unsigned int Checksum;
14.     int ReadLength;
15.  
16.     if (argc != 2) {
17.         printf("usage: checksum filename\n");
18.         exit(1);
19.     }
20.     if ((Handle = open(argv[1], O_RDONLY | O_BINARY)) == -1) {
21.         printf("Can't open file: %s\n", argv[1]);
22.         exit(1);
23.     }
24.     if (!ChecksumFile(Handle, &Checksum)) {
25.         printf("Error reading file %s\n", argv[1]);
26.         exit(1);
27.     }
28.  
29.     /* Печать результата */
30.     printf("The checksum is: %u\n", Checksum);
31.     exit(0);
32. }

ПРИМЕР 1.3 (L1-3.ASM)

Код (C):

1. ; Процедура на ассемблере, вычисляющая 16-разрядную контрольную
2. ; сумму открытого файла, дескриптор которого передается как
3. ; параметр. Сохраняет результат в указанной переменной. Возвращает
4. ; 1 при успешном завершении и 0 - при ошибке.
5. ;
6. ; Формат вызова:
7. ;  int ChecksumFile(unsigned int Handle, unsigned int *Checksum);
8. ;
9. ; где:
10. ;  Handle   = дескриптор открытого файла, для которого
11. ;             вычисляется контрольная сумма
12. ;  Checksum = указатель на переменную типа unsigned int
13. ;             в которой будет сохранена контрольная сумма
14. ;
15. ; Структура для параметров:
16. ;
17. Parms      struc
18.                dw    ?       ; сохраненный BP
19.                dw    ?       ; адрес возврата
20. Handle         dw    ?
21. Checksum       dw    ?
22. Parms      ends
23. ;
24.                .model small
25.                .data
26. TempWord label word
27. TempByte       db    ?       ; здесь сохраняется каждый
28.                              ; прочитанный DOS байт
29.                db    0       ; старший байт TempWord
30.                              ; всегда равен 0 для
31.                              ; 16-разрядного сложения
32. ;
33.                .code
34.                public _ChecksumFile
35. _ChecksumFile  proc near
36.                push  bp
37.                mov   bp,sp
38.                push  si      ; сохраняем регистровые
39.                              ; переменные С
40.                mov   bx,[bp+Handle] ; получаем дескриптор файла
41.                sub   si,si   ; помещаем 0 в аккумулятор
42.                              ; контрольной суммы
43.                mov   cx,1    ; запрашиваем один байт
44.                              ; при каждом вызове read
45.                mov   dx,offset TempByte ; DX указывает на байт
46.                              ; в котором DOS должна сохранять
47.                              ; каждый прочитаный байт
48. ChecksumLoop:
49.                mov   ah,3fh  ; функция DOS для чтения из файла
50.                int   21h
51.                jc    ErrorEnd ; возникла ошибка
52.                and   ax,ax   ; байт прочитан?
53.                jz    Success ; нет - достигнут конец файла,
54.                              ; завершаем работу
55.                add   si,[TempWord] ; добавляем байт к общей
56.                                    ; контрольной сумме
57.                jmp   ChecksumLoop
58. ErrorEnd:
59.                sub   ax,ax   ; ошибка
60.                jmp   short Done
61. Success:
62.                mov   bx,[bp+Checksum] ; указатель на переменную
63.                                       ; для контрольной суммы
64.                mov   [bx],si ; сохраняем контрольную сумму
65.                mov   ax,1    ; успешное завершение
66. ;
67. Done:
68.                pop   si      ; восстанавливаем регистровые
69.                              ; переменные С
70.                pop   bp
71.                ret
72. _ChecksumFile  endp
73.                end

Урок ясен: оптимизация делает код быстрее, но без надлежащего проекта оптимизация всего лишь создаст быстрый медленный код.

Хорошо, тогда как же мы можем улучшить проект? Прежде, чем заняться улучшением, мы должны понять, что неправильно в текущем проекте.

Изучите территорию

Почему же пример 1.1 работает так медленно? Говоря кратко: из-за накладных расходов. Библиотека С реализует функцию read() посредством вызова DOS для чтения указанного количества байтов. (Я обнаружил это, просмотрев выполнение кода с помощью отладчика, а вы можете приобрести исходные коды библиотек у Borland и Microsoft.) Это означает, что пример 1.1 (так же как и пример 1.3) вызывает функцию DOS при обработке каждого байта — а функция DOS, особенно данная, влечет большие накладные расходы.

Для начинающих скажу, что функции DOS вызываются через прерывания, а прерывания — это одни из самых медленных команд в процессорах семейства x86. Кроме того, DOS должна выполнить внутренние установки и переход к требуемой функции, на что тратится много тактов процессора. Затем DOS ищет собственные внутренние буферы, чтобы проверить, прочитан ли уже требуемый байт, и, если нет, то читает его с диска, сохраняет байт в указанном месте и выполняет возврат. Все это занимает очень много времени — гораздо больше, чем вся оставшаяся часть главного цикла в примере 1.1. Короче говоря, пример 1.1 тратит почти все время на выполнение функции read(), и большая часть этого времени поглощается где-то в недрах DOS.

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

Как можно ускорить работу примера 1.1? Должно быть ясно, что нам следует каким-либо образом избежать вызова DOS при обработке каждого байта файла, что означает одновременное чтение нескольких байт, помещение данных в буфер и их постепенную выдачу по одному байту за раз для обработки. Черт возьми, — ведь это описание особенностей потокового ввода/вывода языка С, посредством которого программа на С читает файл по частям, буферизует прочитанные данные внутри и затем, по мере поступления запросов от приложения, выдает эти байты, беря их из памяти, вместо того, чтобы вызывать DOS. Давайте применим потоковый ввод/вывод и посмотрим что получится.

Пример 1.4 аналогичен примеру 1.1, но использует для доступа к файлу, контрольная сумма которого вычисляется, функции fopen() и getc() (вместо open() и read()). Результаты блестяще подтверждают теорию и позволяют утвердить новый проект. Как показано в таблице 1.1, пример 1.4 работает на порядок быстрее, чем даже написанная на ассемблере версия примера 1.1, несмотря на то, что код примера 1.1 и код примера 1.4 выглядят практически одинаково. Случайному читателю read() и getc() могут показаться слегка различными, но полностью взаимозаменяемыми, однако различие в производительности этих двух примеров такое же, как различие производительности обычного PC с процессором, работающим на тактовой частоте 4,77 МГц и компьютером с 386 процессором, работающим на тактовой частоте 16 МГц.

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

В данном случае это означает понимать как DOS и библиотеки доступа к файлам в C/C++ выполняют свою работу. Другими словами, изучите территорию!
ПРИМЕР 1.4 (L1-4.C)

Код (C):

1. /*
2. * Программа для вычисления 16-разрядной контрольной суммы
3. * потока байт из указанного файла. Получает файлы по одному
4. * через getc(), позволя С выполнять буферизацию данных.
5. */
6. #include <stdio.h>
7.  
8. main(int argc, char *argv[]) {
9.     FILE *CheckFile;
10.     int Byte;
11.     unsigned int Checksum;
12.  
13.     if ( argc != 2 ) {
14.         printf("usage: checksum filename\n");
15.         exit(1);
16.     }
17.     if ( (CheckFile = fopen(argv[1], "rb")) == NULL ) {
18.         printf("Can't open file: %s\n", argv[1]);
19.         exit(1);
20.     }
21.  
22.     /* Инициализация контрольной суммы */
23.     Checksum = 0;
24.  
25.     /* Прибавляем каждый байт к контрольной сумме */
26.     while ( (Byte = getc(CheckFile)) != EOF ) {
27.         Checksum += (unsigned int) Byte;
28.     }
29.  
30.     /* Выводим результат */
31.     printf("The checksum is: %u\n", Checksum);
32.     exit(0);
33. }

Узнайте, что имеет значение

В предыдущем разделе была сказана особенно интересная фраза: критические по времени части вашего кода. Критические по времени части кода — это те части, скорость выполнения кода которых оказывает существенное влияние на быстродействие вашей программы в целом. Под «существенным» я подразумеваю не ускорение выполнения кода на 100 или 200 процентов, или вообще, каое-либо конкретное число, а скорее уменьшение времени отклика или повышение удобства работы с программой с точки зрения пользователя.

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

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

Всегда рассматривайте альтернативы

Пример 1.4 хорош, но давайте посмотрим, существует ли другой — возможно менее очевидный — способ достичь того же результата еще быстрее. Для начала подумаем, почему пример 1.4 настолько лучше примера 1.1. Также как и read(), getc() для чтения из файла вызывает DOS; увеличение скорости в примере 1.4 достигается потому, что getc() получает от DOS сразу много байт, а затем управляет этими байтами для нас. Это быстрее, чем чтение по одному байту за раз с использованием read() — но нет причины думать, что это быстрее, чем если бы наша программа сама читала блок данных и управляла им. Проще — да, но не быстрее.

Взгляните: каждый вызов getc() требует поместить параметр в стек, выполнить вызов библиотечной функции С, получить параметр (в коде библиотеки С), просмотреть информацию о требуемом потоке, получить из буфера следующий байт потока и вернуться из вызванного кода. Это требует значительных расходов времени, особенно если сравнить с простым управлением указателем на буфер и перебором данных в буфере внутри одного цикла.

Есть четыре причины, по которым многие программисты не стали бы улучшать пример 1.4:

1. Код уже достаточно быстрый.
2. Код работает, и некоторые люди довольны кодом, который работает, даже несмотря на то, что его медлительность раздражает.
3. Библиотека С написана на оптимизированном ассемблере и, вероятно, будет быстрее, чем любой код, который может написать средний программист для выполнения почти той же функции.
4. Библиотека С удобна для буферизации данных файла и будет лишним самостоятельно реализовать эту возможность.

Я игнорирую первую причину и потому, что вопрос быстродействия снимается, если код достаточно быстр, и потому, что в данный момент приложение не выполняется достаточно быстро — 13 секунд это долго. (Остановитесь и подождите 13 секунд, когда вы заняты интенсивной работой, и вы поймете насколько это долго.)

Вторая причина — признак посредственного программиста. Узнайте, когда вопросы оптимизации имеют значение, и затем выполните оптимизацию.

Третья причина часто ошибочна. Библиотечные функции С не всегда пишутся на ассемблере и не всегда хорошо оптимизированы. (Фактически, они часто написаны для переносимости и не имеют никакого отношения к оптимизации.) Более того, они являются функциями общего назначения и часто могут проигрывать в производительности не слишком хорошо написанному, но хорошо приспособленному к конкретной задаче коду. Взгляните на пример 1.5, который использует внутреннюю буферизацию для единовременной обработки блока байтов. Из таблицы 1.1 видно, что пример 1.5 работает от 2,5 до 4 раз быстрее, чем пример 1.4 (и в 49 раз быстрее, чем пример 1.1!) хотя в нем вообще не используется ассемблер.Конечно, вы можете успешно применять специальный код на С вместо вызова библиотечных функций С — если вы полностью понимаете как работает библиотечная функция С и точно знаете потребности вашего приложения. Иначе вы закончите переписыванием библиотечных функций С на С, что абсолютно бессмысленно.
ПРИМЕР 1.5 (L1-5.C)

Код (C):

1. /*
2. * Программа вычисления 16-разрядной контрольной суммы
3. * потока байт из заданного файла. Сама выполняет внутреннюю
4. * буферизацию, вместо того, чтобы возлагать эту работу
5. * на библиотеку С или DOS.
6. */
7. #include <stdio.h>
8. #include <fcntl.h>
9. #include <alloc.h>   /* alloc.h  для Borland,
10.                         malloc.h для Microsoft  */
11.  
12. #define BUFFER_SIZE  0x8000   /* Буфер данных объемом 32K */
13. main(int argc, char *argv[]) {
14.     int Handle;
15.     unsigned int Checksum;
16.     unsigned char *WorkingBuffer, *WorkingPtr;
17.     int WorkingLength, LengthCount;
18.  
19.     if (argc != 2) {
20.         printf("usage: checksum filename\n");
21.         exit(1);
22.     }
23.     if ((Handle = open(argv[1], O_RDONLY | O_BINARY)) == -1) {
24.         printf("Can't open file: %s\n", argv[1]);
25.         exit(1);
26.     }
27.  
28.     /* Выделяем память для буфера данных */
29.     if ((WorkingBuffer = malloc(BUFFER_SIZE)) == NULL) {
30.         printf("Can't get enough memory\n");
31.         exit(1);
32.     }
33. /* Инициализируем контрольную сумму */
34.     Checksum = 0;
35.  
36.     /* Обрабатываем файл блоками по BUFFER_SIZE байт */
37.     do {
38.         if ((WorkingLength = read(Handle, WorkingBuffer,
39.              BUFFER_SIZE)) == -1) {
40.             printf("Error reading file %s\n", argv[1]);
41.             exit(1);
42.         }
43.         /* Вычисляем контрольную сумму блока */
44.         WorkingPtr = WorkingBuffer;
45.         LengthCount = WorkingLength;
46.         while (LengthCount--) {
47.             /* Добавляем каждый байт к контрольной сумме */
48.             Checksum += (unsigned int) *WorkingPtr++;
49.         }
50.     } while ( WorkingLength );
51.  
52.     /* Выводим результат */
53.     printf("The checksum is: %u\n", Checksum);
54.     exit(0);
55. }

Это подводит нас к четвертой причине: отказ от реализации внутреннего буфера, подобно примеру 1.5, из-за трудности программирования такого подхода. Действительно, гораздо легче позволить выполнять всю работу библиотечным функциям С, но реализация внутренней буферизации это не все трудности. Ключевым моментом здесь является обработка данных в повторно запускаемых блоках (restartable blocks). Это означает чтение блока данных, обработку данных, пока они не закончатся, приостановку обработки, пока читается следующий блок данных, и продолжение работы, как будто ничего не произошло.

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

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

 

Узнайте, как выжать сок

Я уже несколько раз говорил, что пока проект окончательно не утвержден, оптимизация бессмысленна. Однако, когда время пришло, оптимизация действительно может дать значительный результат. В таблице 1.1 видно, что оптимизация примера 1.5, выполненная компилятором Microsoft C, дает 60-процентный рост производительности. Более того, версия примера 1.5, написанная с использованием ассемблера, которая привдена в примерах 1.6 и 1.7, работает на 26 процентов быстрее, чем самая быстрая оптимизированная компилятором версия примера 1.5. Это значительные усовершенствования, оправдывающие затраченные усилия — только так можно получить максимум от проекта.
ПРИМЕР 1.6 (L1-6.C)

Код (C):

1. /* Программа вычисления 16-разрядной контрольной суммы
2. * потока байт из заданного файла. Сама выполняет внутреннюю
3. * буферизацию, вместо того, чтобы возлагать эту работу
4. * на библиотеку С или DOS. Критические по времени участки
5. * кода написаны на оптимизированном ассемблере. */
6. #include <stdio.h>
7. #include <fcntl.h>
8. #include <alloc.h>
9. /* alloc.h для Borland, malloc.h для Microsoft */
10. #define BUFFER_SIZE 0x8000 /* Буфер данных объемом 32K */
11. main(int argc, char *argv[])
12. {
13.  int Handle; unsigned int Checksum;
14. unsigned char *WorkingBuffer;
15. int WorkingLength;
16. if (argc != 2)
17. { printf("usage: checksum filename\n");
18. exit(1); }
19. if ((Handle = open(argv[1], O_RDONLY | O_BINARY)) == -1)
20. {
21.  printf("Can't open file: %s\n", argv[1]); exit(1); }
22. /* Выделяем память для буфера данных */
23. if ((WorkingBuffer = malloc(BUFFER_SIZE)) == NULL)
24. { printf("Can't get enough memory\n");
25. exit(1); }
26. /* Инициализируем контрольную сумму */
27. Checksum = 0; /* Обрабатываем файл блоками по 32 Кбайт */
28. do { if ((WorkingLength = read(Handle, WorkingBuffer, BUFFER_SIZE)) == -1 )
29. { printf("Error reading file %s\n", argv[1]);
30. exit(1); }
31. /* Вычисляем контрольную сумму блока, если есть данные */
32. if (WorkingLength) ChecksumChunk(WorkingBuffer, WorkingLength, &Checksum); }
33. while ( WorkingLength ); /* Выводим результат */
34. printf("The checksum is: %u\n", Checksum);
35. exit(0); }

ПРИМЕР 1.7 (L1-7.ASM)

Код (ASM):

1. ; Процедура на ассемблере для вычисления 16-разрядной
2. ; контрольной суммы блока, размером от 1 байта до 64 Кбайт.
3. ; Добавляет вычисленную контрольную сумму к переданной
4. ; контрольной сумме.
5. ; ; Формат вызова:
6. ; void ChecksumChunk(unsigned char *Buffer,
7. ; unsigned int BufferLength, unsigned int *Checksum)
8. ; ; ; где:
9. ; Buffer = указатель на начало блока байт, контрольная сумма ; которого должна быть вычислена
10. ; BufferLength = количество байт в блоке (0 означает 64K, а не 0)
11. ; Checksum = указатель на переменную типа unsigned int
12. ; в которую будет помещена контрольная сумма
13. ; ; Структура параметров:
14. ; Parms struc dw ?
15. ; сохраненный
16. BP dw ? ; адрес возврата
17. Buffer dw ?
18. BufferLength dw ?
19. Checksum dw ?
20. Parms ends ;
21. .model small
22. .code
23. public _ChecksumChunk
24. _ChecksumChunk proc near
25. push bp
26. mov bp,sp
27. push si ; сохраняем регистровую переменную С ;
28. cld ; LODSB будет увеличивать SI
29. mov si,[bp+Buffer] ; указатель на буфер
30. mov cx,[bp+BufferLength] ; получаем длину буфера
31. mov bx,[bp+Checksum] ; указатель на переменную с
32. ; контрольной суммой
33. mov dx,[bx] ; получаем текущее значение
34. ; контрольной суммы
35. sub ah,ah ; чтобы после LODSB в AX
36. ; было 16-разрядное значение
37. ChecksumLoop: lodsb ; получаем следующий байт
38. add dx,ax ; прибавляем его к контрольной сумме
39. loop ChecksumLoop ; повторяем для всех байтов в блоке
40. mov [bx],dx ; сохраняем новую контрольную сумму ;
41. pop si ; восстанавливаем регистровую
42. ; переменную С
43. pop bp
44. ret
45. _ChecksumChunkendp end

Обратите внимание, что в таблице 1.1 оптимизация дает весьма незначительный прирост производительности, за исключением примера 1.5, проект которого был значительно переработан. Время выполнения других версий в основном зависит от времени, которое тратится DOS или библиотекой С, и оптимизация написанного вами кода почти не приносит результатов. Кроме того, сравните двухкратный рост производительности, полученный в результатае оптимизации, с более чем 50-кратным ростом произволительности, полученным при переработке проекта программы.
Между прочим, даже время выполнения примеров 1.6 и 1.7 зависит от времени доступа к диску в DOS. Если для диска разрешено кэширование и файл, контрольная сумма которого вычисляется, уже находится в кэше, версия на ассемблере работает в три раза быстрее, чем версия на С. Другими словами, внутренняя природа нашего приложения ограничивает прирост быстродействия, которого можно достичь используя ассемблер. В приложениях, которые более интенсивно используют центральный процессор и меньше привязаны к диску, особенно в тех приложениях, где можно эффективно применять команды работы со строками и/или развернутые циклы, код на ассемблере будет более быстрым по сравнению с кодом на С, чем в нашем конкретном случае.
Не попадите в зависимость от оптимизирующего компилятора или языка ассемблера — лучший оптимизатор находится у вас между ушей.


Все это можно сказать одной фразой: знайте, куда вы идете, изучите территорию и знайте, что имеет значение.

Где мы были, что мы видели

Что мы узнали? Не позволяйте коду, написанному другими людьми, — даже DOS, — делать за вас работу, скорость выполнения которой важна, по крайней мере, если вы точно не знаете что именно делаает код и насколько хорошо.
Оптимизация имеет значение только после того, как вы выполнили всю работу, относящуюся к проекту программы. Рассмотрите отношения в последнем столбце таблицы 1.1, показывающие, что оптимизация приложения, вычисляющего контрольную сумму, без эффективного проекта оказалась практически бесполезной. Оптимизация не является панацеей. Таблица 1.1 показывает двухкратный выигрыш от оптимизации и более чем 50-кратный выигрыш от изменения проекта программы. В свете этих данных продолжительные дебаты о том, какой компилятор С лучше оптимизирует код, уже не выглядят столь важными, разве не так? Ваши органические оптимизаторы значат гораздо больше, чем оптимизатор вашего компилятора, а место для ассемблера находится в тех, обычно небольших, участках кода, где быстродействие действительно имеет значение.

Куда мы идем

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

 

Глава 2
Особенный мир

Уникальная природа оптимизации языка ассемблера

Как я показал в предыдущей главе, оптимизация ни в коем случае не означает «погружение в ассемблер». Фактически, при настройке быстродействия кода на языке высокого уровня ассемблер должен использоваться редко, и только после того, как вы будете уверены, что глупо выбранный или ужасно реализованный алгоритм не поглотит ваши усилия. Конечно, если вы вообще используете ассемблер, будьте уверены, что вы используете его правильно. Потенциальная возможность создания медленно выполняемого кода на ассемблере плохо понимается большинством людей, но она очень велика, особенно в руках неосведомленных.
Действительно, значительный выигрыш от оптимизации возможен только на уровне ассемблера, и это является ответом на набор особенностей, которые коренным образом отличаются от основных принципов оптимизации в С/C++ или Паскале. В этой книге я буду снова и снова говорить об оптимизации на уровне ассемблера, и я думаю, что вам поможет точное понимание специфичных для ассемблера особенностей оптимизации.
Как обычно, лучший способ разобраться — это изучение реального примера.

 

Команды: по отдельности и вместе

Некоторое время назад я работал над критической процедурой на ассемблере, пытаясь заставить ее работать настолько быстро, насколько это возможно. Задачей процедуры было конструирование ниббла из отдельных разрядов, читаемых из различных байтов, циклический сдвиг и комбинирование разрядов, чтобы, в конечном счете, они были аккуратно выровнены в разрядах 3 – 0 одного байта. (Если вы любопытны, цель состояла в том, чтобы получить 16-цветный пиксель из разрядов, разбросанных по четырем байтам.) Я исследовал процедуру строка за строкой, сохранял такт здесь и такт там, пока код не показался действительно оптимизированным. Когда я закончил работу, ключевая часть кода выглядела примерно так:

Код (ASM):

1. LoopTop:
2.       lodsb            ; получаем следующий байт,
3.                        ; из которого будем извлекать бит
4.       and   al,ah      ; выделяем требуемый бит
5.       rol   al,cl      ; сдвигаем бит в требуемую позицию
6.       or    bl,al      ; добавляем бит к результату
7.       dec   cx         ; следующий бит должен быть помещен
8.                        ; в результате на 1 позицию правее
9.       dec   dx         ; уменьшаем счетчик битов
10.       jnz   LoopTop    ; обрабатываем следующий бит, если он есть

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



Я заменил код на следующий:

Код (ASM):

1. LoopTop:
2.       lodsb            ; получаем следующий байт,
3.                        ; из которого будем извлекать бит
4.       and   al,ah      ; выделяем требуемый бит
5.       or    bl,al      ; помещаем бит в результат
6.       rol   bl,1       ; освобождаем место для следующего бита
7.       dec   dx         ; уменьшаем счетчик битов
8.       jnz   LoopTop    ; обрабатываем следующий бит, если он есть
9.       rol   bl,cl      ; помещаем полученный результат
10.                        ; в требуемые разряды байта

В результате дорогостоящий циклический сдвиг на несколько разрядов был вынесен за пределы цикла и исполнялся только один раз, а не четыре. Хотя на вид код почти не отличается от оригинала и фактически содержит то же самое количество команд, быстродействие процедуры в целом увеличилось от этого единственного изменения на 10 процентов. (Кстати, на этом оптимизация не закончилась; я исключил команды DEC и JNZ развернув четыре итерации цикла, — но это история для другой главы.)
Особенность в следующем: чтобы писать действительно превосходные программы на ассемблере вы должны знать, что именно делают различные команды, и какие команды выполняются быстрее всего... но это не все. Вы должны учиться смотреть на задачи программирования с различных точек зрения, чтобы помещать эти быстрые команды туда, где они будут работать наиболее эффективно.

 

Фундаментальные отличия ассемблера

Действительно ли настолько трудно писать хороший ассемблерный код для PC? Да! Благодаря исключительно причудливой природе семейства процессоров x86, ассемблер фундаментально отличается от других языков и бесспорно труднее для работы. С другой стороны, потенциальные возможности ассемблера гораздо больше, чем у других языков программирования.
Чтобы понять причины этого, рассмотрим, как пишутся программы. Программист изучает требования к приложению, разрабатывает решение на каком-либо уровне абстракции, и затем воплощает этот проект в коде. Без надлежащей проработки, преобразование при переходе от концепции к реализации может катастрофически уменьшить быстродействие. Например, программист, который пишет процедуру поиска в списке из 100 000 отсортированных элементов, и использует линейный поиск вместо двоичного, получит обескураживающе медленную программу.

Преобразование без потери эффективности

Независимо от того, насколько хорошо реализован утвержденный проект, языки высокого уровня, подобные C/C++ и Паскалю неизбежно добавляют приводящее к потере эффективности преобразование, как показано на рис. 2.1.

Рис. 2.1. Приводящее к потере эффективности преобразование в языке высокого уровня​

Процесс преобразования проекта в исполняемый код с применением языка высокого уровня включает два преобразования: первое выполняется программистом, создающим исходный код, а другое выполняется компилятором, превращающим исходный код в команды машинного языка. Следовательно, машинный код, генерируемый компилятором, обычно не столь оптимально соответствует требованиям оригинального проекта.
Языки высокого уровня предоставляют искусственные среды, которые относительно хорошо приспособлены для человека с навыками программирования и облегчают переход от проекта к реализации. Цена такой простоты реализации — значительная потеря эффективности при преобразовании исходного кода в машинный язык. Это особенно верно для реального и 16-разрядного защищенного режима в семействе процессоров x86 с его специализированными командами адресации к памяти и сегментной архитектурой памяти, не слишком хорошо соответствующих дизайну компиляторов. Даже 32-разрядный режим в процессоре 386 и его преемниках с более мощными режимами адресации, предлагает меньше регистров, чем хотелось бы компилятору.
С другой стороны, ассемблер является просто ориентированным на пользователя представлением машинного языка. В результате ассемблер предоставляет более сложную среду программирования — голое оборудование и системное программное обеспечение, — но правильно сконструированные программы на ассемблере не проходят через понижающие эффективность преобразования, что показано на рис. 2.2.

Рис. 2.2. Правильно сконструированные программы на ассемблере не теряют эффективности при преобразовании​

При создании программы на ассемблере требуется только одно преобразование, и оно полностью находится под контролем программиста. Ассемблер не выполняет преобразований при переходе от исходного кода к машинному языку; вместо этого он заменяет инструкции ассемблера на команды машинного языка один к одному. В результате у программиста появляется возможность создать код на машинном языке, который в точности соответствует потребностям каждой задачи, выполняемой приложением.
Ключевой фигурой, конечно, является программист, поскольку в ассемблере программист должен по существу полностью самостоятельно выполнить преобразование от спецификации приложения до машинного языка. (Ассемблер просто выполняет прямой перевод языка ассемблера в машинный язык.)

Самообеспеченность

Первая часть оптимизации языка ассемблера — вы сами. Ассемблер — это всего лишь инструмент, позволяющий проектировать программы на машинном языке, не думая в шестнадцатеричных кодах. Поэтому те, кто программирует на ассемблере — в отличие от всех других программистов, — должны полностью отвечать за качество их кода. Поскольку ассемблер не предоставляет никакой помощи, кроме генерации машинного языка, программист, использующий ассемблер должен уметь напрямую кодировать любую конструкцию программирования и управлять PC на самом низком уровне — операционной системы, BIOS и даже оборудования, если необходимо. Языки высокого уровня решают большинство этих задач незаметно для программиста, но в ассемблере все это справедливая — и необходимая — игра, которая подводит нас к другому аспекту оптимизации ассемблера: знанию.

Знание

В мире PC у вас никогда не будет достаточно знаний, и каждый кусочек, который вы добавите в свою копилку, будет делать ваши программы лучше. Очень важно полное знакомство с различными API операционной системы и интерфейсами BIOS; поскольку эти интерфейсы хорошо документированы и достаточно просты, мой совет — возьмите одну или две хороших книги и заставьте себя прочитать их. Также требуется знакомство с аппаратным обеспечением PC. Эта тема охватывает множество вещей — видеокарты, клавиатура, последовательные и параллельные порты, таймер и каналы DMA, организация памяти, и многое другое. Большинство аппаратного обеспечения хорошо документировано и статьи о программировании основных компонентов оборудования встречаются в литературе достаточно часто, так что эти знания при желании тоже легко получить.
Самый важный и наиболее трудный для изучения элемент аппаратного обеспечения — центральный процессор. Семейство центральных процессоров x86 имеет сложный, нерегулярный набор команд и, в отличие от большинства других процессоров, не является ни простым, ни хорошо приспособленным для быстродействующего кода. Более того, ассемблер настолько сложен для изучения, что в большинстве статей и книг приводят ассемблерный код, который просто кое-как работает, вместо кода, который подводит процессор к грани возможного. Фактически, поскольку большинство статей и книг написаны для начинающих программировать на ассемблере, доступно очень мало информации о том, как создавать высококачественный ассемблерный код для процессоров семейства x86. В результате знание об эффективном программировании наиболее трудно получить. Значительная часть этой книги посвящена поискам такого знания.
Хочу предупредить: независимо от того, как много вы знаете о программировании на ассемблере для PC, всегда есть много того, что еще предстоит узнать.

 

Гибкий разум

Так неужели оптимизация ассемблера оборачивается бесконечным сбором знаний? Едва ли. Знания — это необходимый фундамент, на котором вы будете строить. Давайте уделим немного времени, и исследуем цели хорошего программирования на ассемблере, чтобы силы, потраченные на оптимизацию ассемблерного кода, не пропали впустую.
При создании быстродействующих ассемблерных программ есть две возможных цели: учитывая требования приложения, сведите к минимуму либо число тактов процессора, за которое выполняется код, либо количество байтов в программе, либо и то и другое в какой-либо комбинации. Мы рассмотрим способы достижения обоих целей, но чаще будем сосредотачиваться на уменьшении количества тактов процессора, а не на экономии байтов. Обычно у PC больше памяти, чем лошадиных сил процессора. Фактически, вы обнаружите, что часто возможно двух- или трехкратное увеличение быстродействия компактного ассемблерного кода, если для сохранения тактов процессора вы готовы пожертвовать несколькими байтами. Иногда, из-за жестких требований к объему занимаемой памяти данную технику использовать нежелательно, — но это почти всегда возможно.
Вы можете заметить, что мой короткий список целей для создания быстродействующего кода на ассемблере не включает традиционные цели, такие как простота поддержки и скорость разработки. Это действительно важные соображения для людей и компаний, которые разрабатывают и распространяют программное обеспечение. С другой стороны, люди, которые покупают программное обеспечение, заботятся о том насколько хорошо оно работает, а не о том, как оно разрабатывается или как осуществляется поддержка. В наши дни разработчики так много времени посвящают обсуждению таких общепризнанно важных вопросов, как управляемость кода и возможность его повторного использования, управление исходным кодом, выбор среды разработки и т.д., что они часто забывают правило номер 1: с точки зрения пользователя важнее всего быстродействие.
Если хотите, комментируйте ваш код, тщательно проектируйте его и пишите не являющиеся критическими по времени части на языке высокого уровня, — но когда вы пишете части, которые взаимодействуют с пользователем и/или непосредственно влияют на время отклика, быстродействие должно быть вашей главной целью, а ассемблер — путь к достижению этой цели.
Описанные ранее знания абсолютно необходимы для достижения любой из целей программирования на ассемблере. Но эти знания не могут за вас встретить необходимость написать код, который соответствует требованиям приложения и работает настолько эффективно, насколько это возможно в среде PC. Знание делает это возможным, но происходит это благодаря вашим навыкам программирования. Именно эта интуитивная, мгновенная интеграция спецификаций программы и моря фактов о PC является сердцем оптимизации ассемблера Дзен-класса.
Как и для любого Дзен, достижение Дзен языка ассемблера является скорее вопросом процесса изучения, чем того, что вы учите. Вам придется найти собственный путь изучения, хотя с помощью этой книги я укажу вам отправную точку пути. Предоставленные мной искусные примеры и факты помогут вам приобрести необходимый опыт, но продолжать путь вам придется самостоятельно. Каждая созданная вами программа расширяет ваши горизонты и увеличивает количество доступных альтернатив, когда вы в следующий раз встретитесь с проблемой. Способность вашего разума находить удивительные новые и лучшие пути для воплощения концепции в превосходном коде — гибкость разума, — это основа хорошего ассемблерного кода, и развить это мастерство можно только трудом.
Никогда не надо недооценивать важность гибкого разума. Хороший ассемблерный код лучше, чем хороший код, созданный компилятором. Многие люди хотят, чтобы вы думали иначе, но они ошибаются. Это не подразумевает, что языки высокого уровня бесполезны, я далек от этого. Язык высокого уровня — лучший выбор для большинства программистов и для большей части кода почти всех приложений. Но когда необходим самый лучший код — самый быстрый или самый короткий, — создать его вам позволит только ассемблер.
Простая логика диктует, что никакой компилятор не может так много знать о назначении фрагмента кода или так хорошо приспосабливаться к его потребностям, как человек, который этот код пишет. Обладая большей информацией и большей приспосабливаемостью, программист на ассемблере может создавать лучший код, чем компилятор, тем более что компилятор ограничен рамками языка высокого уровня и процессом преобразования из языка высокого уровня в машинный язык. Следовательно, тщательно оптимизированный ассемблер, это не только выбранный язык, но и единственный выбор для кода, — обычно занимающего от 1 до 10 процентов общего объема кода программы, и состоящего из небольших, хорошо описанных процедур, — который определяет общее быстродействие программы, и единственный выбор для кода, который должен быть настолько компактен, насколько это возможно. Не имеет смысла бесплодно тратить силы и время на написание оптимизированного ассемблерного кода для обычных, не критических по времени частей ваших программ — вместо этого сосредоточьте усилия на циклах и аналогичных фрагментах; но в тех областях, где необходимо превосходное качество кода, никакие замены не допускаются.
Заметьте, я сказал, что программист на ассемблере может создавать код лучший, чем код компилятора, но я не сказал, что он будет его создавать. Действительно, хороший ассемблерный код лучше, чем хороший код компилятора, но плохой ассемблерный код часто значительно хуже, чем плохой код компилятора. Поскольку программист, использующий ассемблер, имеет полный контроль над программой, у него есть неограниченная возможность впустую тратить такты процессора и байты памяти. Меч является обоюдоострым, и хороший ассемблерный код требует больше, а не меньше, предусмотрительности и планирования, чем хороший код, написанный на языке высокого уровня.
Суть всего сказанного в следующем: хорошее программирование на ассемблере достижимо в контексте твердой общей структуры, уникальной для каждой программы, и гибкого разума, являющегося ключом к созданию этой структуры и скрепляющего все части вместе.

С чего начать?

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

 

Глава 3
Ничего не предполагайте

Постижение и использование Дзен-таймера

Когда вы погрузитесь в написание оптимизированного кода для PC, то станете слегка одержимы поиском подходов, которые позволят выжать из компьютера еще большую скорость. В процессе вы будете делать ошибки, и это хорошо — пока вы видите эти ошибки и учитесь на них.
Приведу поучительную историю. Несколько лет назад я наткнулся на статью о языке ассемблера процессоров 8088 названную «Оптимизируйте для скорости». Оптимизация — не то слово, которое можно необдкуманно использовать. Девятое издание Нового университетского словаря Вебстера определяет слово «оптимизировать» следующим образом: «делать настолько совершенным, эффективным, функциональным насколько это возможно», что конечно оставляет небольшую лазейку для ошибок. Автор статьи взял небольшую, хорошо описанную процедуру на языке ассемблера процессора 8088, которая состояла примерно из 30 команд и преобразовывала 8-разрядное значение в 16-разрядное дублируя каждый бит, и попытался усовершенствовать ее.
Автор «Оптимизации» тщательно настраивал код, исследуя альтернативные варианты размещения команд и подсчитывая такты процессора, пока не создал вариант, который, по его подсчетам, должен был выполняться на 50 процентов быстрее, чем первоначальная процедура. Короче говоря, он использовал всю имеющуюся у него в наличии информацию, чтобы улучшить код и сэкономил много циклов. Фактически, у оптимизированной версии процедуры была лишь одна небольшая проблема...
Она работала медленнее, чем первоначальная версия!

 

Цена невежества

Сколь прилежен не был автор, он совершил основной грех программирования на языке ассемблера x86: предположил, что доступная ему информация и правильная и полная. Хотя время выполнения инструкций, указанное Intel для своих процессоров действительно правильно, эта информация неполная; другая, и зачастую более важная, часть быстродействия кода — это время выборки команды, тема к которой я вернусь в следующих главах.
Если бы автор потратил время на измерение реального быстродействия своего кода, он не стал бы рисковать своей репутацией и предлагать более медленный вариант. Кроме того, если бы он измерил быстродействие кода и увидел, что он выполняется неожиданно медленно, любопытство могло бы подтолкнуть его к дальнейшим экспериментам, и таким образом в его копилку знаний добавилась бы надежная и проверенная информация о центральном процессоре.
Здесь вы видите важный принцип оптимизации ассемблера: после создания наилучшего из возможных вариантов кода, проверьте его в действии и убедитесь, что он действительно работает так, как вы думали. Если код ведет себя не так как ожидалось, из этого тоже можно извлечь пользу — решение загадок это путь к знанию. Ручаюсь, что таким образом вы узнаете гораздо больше, чем из любого руководства или учебника по ассемблеру.
Ничего не предполагайте. Я не могу подчеркнуть это достаточно настоятельно — если вы заботитесь о быстродействии, старайтесь улучшать код, а затем измеряйте улучшение. Если вы не измеряете быстродействие, то вы всего лишь предполагаете, а раз вы предполагаете, то, скорее всего, вы не сможете написать первоклассный код.
Невежество об истинном быстродействии может обойтись очень дорого. Когда я писал видеоигры, то тратил целые дни, пытаясь выжать максимум быстродействия из своих графических драйверов. Я переписывал целые блоки кода только для того, чтобы сохранить несколько тактов, манипулировал регистрами и полагался на обманчиво быстрые сдвиги и сложения с операндами в регистрах процессора. Во время написания последней игры я обнаружил, что программа выполняется значительно быстрее, если для вычислений вместо сдвигов и сложений применяются таблицы просмотра. Согласно моему подсчету тактов такой вариант не должен был работать быстрее, но он работал. По правде говоря, как это часто бывает, во всем опять оказалась виновата выборка команд. В моем случае выборка команд сдвигов и сложений занимала в четыре раза больше времени, чем их исполнение.
Невежество может также привести к пустой трате значительных усилий. Я вспоминаю дебаты в колонке писем одного компьютерного журнала, посвященные тому, насколько быстро можно выводить текст в видеоадаптере CGA без возникновения видимых помех. Как и в истории, которой начиналась эта глава, авторы письма считали каждый такт в своих циклах синхронизации. И точно также они не приняли во внимание очередь предвыборки. Фактически, они также пренебрегли эффектами состояний ожидания видеоадаптера, и обсуждаемый код был намного медленне, чем их оценки. Необходимым испытанием, конечно, является запуск кода, чтобы увидеть прекратились ли помехи, поскольку единственной истинной мерой быстродействия кодя является наблюдение его в действии.

 

Аннотация

Никто не сделал больше, чтобы победить ограничения производительности PC чем Майкл Абраш, и в эту новую книгу было собрано практически все, что он когда-либо написал относительно создания быстродействующих программ, и графики в реальном масштабе времени, включая его легендарную книгу «Zen of Assembly Language». Книги «Zen of Code Optimization» и «Zen of Graphics Programming» приведены здесь в полном объеме, а также добавлен новый материал по графической технологии используемой в программе Quake. Вы узнаете о настройке производительности кода для процессоров Intel, включая особенности использования регистров, конвейера команд, и механизма предсказания переходов. В собрании работ Майкла вы найдете теорию и практику качественной двухмерной и трехмерной анимации в реальном масштабе времени, использующей современные механизмы подобные BSP–деревьям. Никакая другая книга не охватывает вопросы производительности кода и графики в реальном масштабе времени с такой глубиной, как Программирование Графики. Черная книга Майкла Абраша.