Оптимизация программ на ассемблере (часть 3)


Содержание

Структура программы на ассемблере

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

Каждая машинная команда состоит из двух частей:

  • операционной — определяющей, «что делать»;
  • операндной — определяющей объекты обработки, «с чем делать».

Машинная команда микропроцессора, записанная на языке ассемблера, представляет собой одну строку, имеющую следующий синтакический вид:

метка команда/директива операнд(ы) ;комментарии

При этом обязательным полем в строке является команда или директива.

Метка, команда/директива и операнды (если имеются) разделяются по крайней мере одним символом пробела или табуляции.

Если команду или директиву необходимо продолжить на следующей строке, то используется символ обратный слеш: \.

По умолчанию язык ассемблера не различает заглавные и строчные буквы в написании команд или директив.

Примеры строк кода:

Метки

Метка в языке ассемблера может содержать следующие символы:

  • все буквы латинского алфавита;
  • цифры от 0 до 9;
  • спецсимволы: _, @, $, ?.

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

Первым символом в метке должна быть буква или спецсимвол (но не цифра). Максимальная длина метки – 31 символ. Все метки, которые записываются в строке, не содержащей директиву ассемблера, должны заканчиваться двоеточием : .

Команды

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

Директивы

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

Операнды

Операнд – объект, над которым выполняется машинная команда или оператор языка программирования.
Команда может иметь один или два операнда, или вообще не иметь операндов. Число операндов неявно задается кодом команды.
Примеры:

  • Нет операндов ret ;Вернуться
  • Один операнд inc ecx ;Увеличить ecx
  • Два операнда add eax,12 ;Прибавить 12 к eax

Метка, команда (директива) и операнд не обязательно должны начинаться с какой-либо определенной позиции в строке. Однако рекомендуется записывать их в колонку для большего удобства чтения программы.

В качестве операндов могут выступать

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

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

Правила записи идентификаторов.

  • Идентификатор может состоять из одного или нескольких символов.
  • В качестве символов можно использовать буквы латинского алфавита, цифры и некоторые специальные знаки: _, ?, $, @.
  • Идентификатор не может начинаться символом цифры.
  • Длина идентификатора может быть до 255 символов.
  • Транслятор воспринимает первые 32 символа идентификатора, а остальные игнорирует.
Комментарии

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

Структура программы на ассемблере

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

Пример «ничего не делающей» программы на языке ассемблера:

В данной программе представлена всего одна команда микропроцессора. Эта команда RET . Она обеспечивает правильное окончание работы программы. В общем случае эта команда используется для выхода из процедуры.
Остальная часть программы относится к работе транслятора.
.686P — разрешены команды защищенного режима Pentium 6 (Pentium II). Данная директива выбирает поддерживаемый набор команд ассемблера, указывая модель процессора. Буква P, указанная в конце директивы, сообщает транслятору о работе процессора в защищенном режиме.
.MODEL FLAT, stdcall — плоская модель памяти. Эта модель памяти используется в операционной системе Windows. stdcall
.DATA — сегмент программы, содержащий данные.
.CODE — блок программы, содержащей код.
START — метка. В ассемблере метки играют большую роль, что не скажешь о современных языках высокого уровня.
END START — конец программы и сообщение транслятору, что начинать выполнение программы надо с метки START .
Каждый модуль должен содержать директиву END , отмечающую конец исходного кода программы. Все строки, которые следуют за директивой END , игнорируются. Если опустить директиву END , то генерируется ошибка.
Метка, указанная после директивы END , сообщает транслятору имя главного модуля, с которого начинается выполнение программы. Если программа содержит один модуль, метку после директивы END можно не указывать.

Оптимизация программ на ассемблере (часть 3)

Несмотря на все более широкое распространение языков программирования высокого уровня и интегрированных средств программирования, оптимизация программ на ассемблере остается актуальной темой дискуссий программистов. Можно упомянуть, например, форум программистов, проведенный сетью PC MagNET, который стал ареной многочисленных «дуэлей»: то один, то другой участник предлагал всем желающим решить небольшую, но интересную задачу программирования — и рассматривал присылаемые решения, ожидая, кто-же и как решит задачу наименьшей кровью, т.е. затратив минимум байтов на программу. Подобно этому, проведенная сетью BIX конференция по языку ассемблера для процессоров 80×86 и 80×88 стала трибуной немалого числа основательных рассуждений по поводу неочевидных аспектов оптимизации ассемблерных программ. Несмотря на самый общий и широкий интерес к проблеме, литература по оптимизации ассемблерных программ для процессоров 80×86 и 80×88 на удивление скудна. В 1989 году, готовясь к докладу на эту тему для конференции по развитию программного обеспечения, я просмотрел оглавления всех основных журналов по программированию и обнаружил лишь горстку статей на эту тему. С другой стороны, литература по оптимизации программ для компиляторов высокого уровня весьма обширна, и многие концепции, развитые в ней, будут полезны и при программировании на языке ассемблера. Так что говорить, что литературы совсем нет, было бы несправедливо. Ниже мы сначала рассмотрим общие методики оптимизации, а затем обсудим более серьезный вопрос — когда и что стоит оптимизировать.

В этом документе будут обсуждаться некоторые общие вопросы и концепции оптимизации. Будет разговор и о компромиссах, на которые приходится идти, оптимизируя быстродействие и размер программы. Будут рассмотрены конкретные методы, относящиеся к переходам и вызовам подпрограмм, а также метод отказа от универсальности. Ниже мы подробнее рассмотрим некоторые классические образцы «локальной» оптимизации. В том числе: оптимизацию циклов, применение таблиц управляющих параметров, а также об ориентированных на конкретные модели процессоров командах. Но важно помнить, что эти частные методики следует использовать только при определенных обстоятельствах, а именно: после того, как вы убедитесь, что применили правильные алгоритмы и структуры данных, что полностью отладили программу и что средства профилирования показали вам те самые фрагменты программы, которые ограничивают производительность. Стоит еще раз повторить мудрое изречение доктора Кнута: «Многие беды программирования проистекают от преждевременной оптимизации».

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

1. Оптимизация по быстродействию

Если вы пришли к выводу, что ваша программа работает недостаточно быстро, первое, что надо сделать, это убедится, что вы решаете задачу, пользуясь наилучшими алгоритмами и представлениями данных. Замена примитивного или неадекватного алгоритма более подходящим может ускорить выполнение вашей программы на порядок и более. Так что если вы проведете несколько дней, штудируя знаменитые книги Кнута или Седжуика (в надежде подобрать алгоритм, до которого вряд ли додумались бы сами), — будьте уверены: вы сделали выгодное вложение своего драгоценного времени. Аналогично переход от «очевидной», но простой структуры данных (такой, как связный список) к более сложной (например, бинарному дереву) может дать такие результаты, которые с лихвой окупят ваши усилия по усовершенствованию программы.

Если вы уверены, что выбрали наилучшие алгоритмы и структуры данных, следующее, на что следует обратить внимание, — это использование программой данных, хранимых в памяти. Даже самые быстрые устройства работы с дисками, используемые в персональных компьютерах, работают несравнимо медленнее, чем такие мощные вычислители, как процессоры 80386 или 80486, так что постарайтесь свести обращения к диску до возможного минимума. Ознакомьтесь со всеми имеющимися типами данных, доступными программе DOS, — расширяемой и отображаемой памятью, старшими блоками памяти и так далее — и полностью используйте возможности оперативной памяти для хранения в ней данных, с которыми работает ваша программа, чтобы время обращения к ним было минимальным. Полезно также познакомиться с техникой уплотнения данных, поскольку почти во всех случаях быстрее оказывается сначала уплотнить, а затем распаковать данные, когда в них возникает необходимость, чем по нескольку раз считывать неуплотненную информацию с диска.

Еще одной темой, заслуживающей обсуждения, является уменьшение объема вычислений в программе. Составители компиляторов пользуются забавными терминами — устранение общих подвыражений, сворачивание констант, распространение констант — для того что бы, по сути, сказать одно и то же: во время работы программы одно и то же значение ни в коем случае не должно вычисляться дважды. Вместо этого программа должна рассчитывать каждое значение лишь один раз и сохранять его для повторного использования. Еще лучше переносить вычисления со стадии исполнения на стадию ассемблирования, всякий раз, когда это позволяют ограниченные математические «способности» MASM, TASM или OPTASM. Совершенно аналогично вам, возможно, удастся существенно повысить быстродействие программы, преобразовав вычисления в обращения к таблицам, которые заранее генерируются и сохраняются отдельной программой.

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

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

— Уменьшение количества передач управления в программе: за счет преобразования подпрограмм в макрокоманды для непосредственного включения в исполняемый код; за счет преобразования условных переходов так, чтобы условие перехода оказывалось истинным относительно реже, чем условие для его отсутствия; перемещение условий общего характера к началу разветвленной последовательности переходов; преобразование вызовов, сразу за которыми следует возврат в программу, в переходы («сращивание хвостов» и «устранение рекурсивных хвостов») и так далее.

— Оптимизация циклов, в том числе перемещение вычислений неизменяющихся величин за пределы циклов, разворачивание циклов и «соединение» отдельных циклов, выполняемых одно и то же число раз, в единый цикл («сжатие цикла»).

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

— Использование специфических для данного процессора инструкций: инструкции засылки в стек непосредственного значения или умножения числа на непосредственный операнд, которые имеются в процессорах 80186, 80188, 80286, 80386 и 80486. Другие примеры — двухсловные строковые инструкции, команды перемножения 32-разрядных чисел и деления 64-разрядного на 32-разрядное число, которые реализованы в процессорах 80386 и 80486. Ваша программа должна, разумеется, вначале определять с каких типом процессора она работает.

В процессорах 80×86, но не 80×88, вам, возможно, также удастся увеличить скорость исполнения программы на несколько процентов за счет выравнивания расположения данных и меток, на которые происходит передача управления, относительно некоторых границ. Процессоры 8088 и 80188 — с 8-разрядной шиной и им без разницы на какую границу выровнены данные, поэтому выравнивание можно отключить или установить на границу байта (1 байт, 8 бит); процессоры 8086, 80186 и 80286 — с 16-разрядной шиной и им «удобнее» работать с данными, выровненными на границу слова (2 байта, 16 бит); процессор 80386 — с 32-разрядной шиной, поэтому он предпочитает выравнивание на границу двойного слова (4 байта, 32 бита); из-за устройства его внутренней кэш-памяти процессору 80486, то же с 32-разрядной шиной, легче работать, если произведено выравнивание на границу параграфа (16 байт, 96 бит).

Если же все остальное успеха не принесло, а вы пишите некую штучную, специальную программу, а не программный пакет, предназначенный для продажи на массовом рынке, проблему быстродействия, может быть, проще «решить» аппаратным путем. При существующих сегодня ценах часто оказывается намного выгоднее заказать новый, более мощный компьютер для работы с вашей специализированной программой, чем тратить время на мучения, связанные с переделкой программы, ее оптимизацией и последующей отладкой заново. К сожалению, безоглядное и некритическое принятие этого подхода такими производителями программных изделий, как Microsoft, Borland и Lotus, привело к рождению громоздких монстров, подобных таким как Windows 3.0 и 3.1, Programmer’s Workbench, Microsoft C 6.0, и Microsoft C++ 7.0, Borland C++ 3.0 и Borland C++ 3.1, Borland Pascal 7.0, а также и Lotus 1-2-3 3/G, — но это уже тема другого разговора.

Почти все, что облегчает чтение программы и содействует ее сопровождению, обычно повышает и быстродействие.

2. Оптимизация по размеру

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

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

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

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

Если вы сделали все, что я рекомендовал выше, а вам по-прежнему не хватает памяти, то попробуйте поискать удачи еще на нескольких путях. Вы можете перекомпилировать свою программу в относительно независимые модули, которые могут поодиночке считываться в память как оверлеи. Вы можете закодировать функционирование вашей программы в таблицах, «управляющих» ее исполнением. Вы можете прибегнуть к методике «прошитого» кода или псевдокода и представить логику вашей программы с использованием гораздо меньшего объема памяти за счет некоторого снижения быстродействия. Можно, наконец, прибегнуть к тяжелой артиллерии современной компьютерной технологии и использовать стандартный интерпретатор или компилятор «малого языка», который в свою очередь будет служить виртуальной машиной для прикладной программы. Quick BASIC, Excel и Brief — самые привычные примеры применения соответственно стратегии прошитого кода, псевдокода и малого языка.

В конечном счете, если вы пишете специализированную прикладную программу, преодолеть проблемы памяти возможно (снова) удастся объединенным программно-аппаратным путем. Среди многих возможностей есть такие: использование более высоких версий операционной системы, таких как DOS 5.0 или OS/2 2.0 для расширения объема рабочей памяти (в пределах первых 640 Кбайт); установка еще одной платы расширения памяти, переход к компьютерам на процессорах 80386 и 80486, которые поддерживают большую память по сравнению с использовавшейся вами машиной на процессоре 8086, 8088, 80186, 80188 или 80286; и/или запуск вашей программы под управлением расширителя DOS.

Оптимизация размера программы — это совсем не то же самое, что оптимизация ее быстродействия.

3. А стоит ли оптимизировать?

Оптимизация кодов на любом языке всегда требует идти на компромиссы, среди которых такие, как:

  • Сокращение потребного объема памяти за счет снижения быстродействия;
  • Повышение быстродействия за счет ухудшения возможностей сопровождения и доступности текста программы для чтения;
  • Сокращение времени исполнения программы за счет увеличения времени ее разработки.

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

В процессорах 80×86 и 80×88 команда MOV занимает 2 байта и требует 2 тактов центрального процессора, тогда как команда XCHG занимает 1 байт, но требует 3 тактов. Пока все кажется ясным: надо выбирать между скоростью и памятью. Но реальное время исполнения команды существенно зависит от контекста, размера очереди команд центрального процессора, размера и характеристик кэш-памяти системы и так далее, тогда как даже число циклов, требуемых для исполнения инструкций, меняется от одной модели центрального процессора к другой. Как оказывается, практически невозможно предсказать скорость исполнения нетривиальной последовательности инструкций в процессоре фирмы Intel, особенно в последних моделях 80386 и 80486, в которых более интенсивно используется конвейерная обработка, — вам придется составлять различные возможные комбинации инструкций, запускать их и экспериментально определять время их исполнения.

Аналогично баланс между временем исполнения программы и временем ее разработки и баланс между возможностями сопровождения программы и ее быстродействием редко бывают столь однозначны, как нам бы хотелось, а долговременные последствия ошибочных решений могут быть весьма неприятными. Вообще же, занимаясь оптимизацией, важнее всего понимать, когда ее делать, а когда лучше оставить все как было. Процитируем Дональда Кнута: «Многие беды программирования проистекают от преждевременной оптимизации». Прежде чем думать о настройке своей программы, убедитесь, что она правильная и полная, что вы используете верный алгоритм для решения поставленной задачи и что вы составили самый ясный, самый простой, самый структурированный код, который только был возможен.

Если программа удовлетворяет всем этим критериям, то, на самом деле, ее объем и скорость исполнения в большинстве случаев будут вполне приемлемыми без каких-либо дальнейших усовершенствований. Одно только использование ассемблера само по себе приводит к увеличению скорости исполнения программы в 2-3 раза и примерно к такому же уменьшению размера по сравнению с аналогичной программой на языке высокого уровня. И еще: если что-то упрощает чтение программы и ее сопровождение, то обычно это же одновременно приводит к увеличению скорости исполнения; здесь можно назвать отказ от макаронных кодов со многими ненужными переходами и вызовами подпрограмм (которые являются тяжелой работой для процессоров с архитектурой 80×86 или 80×88, поскольку они сбрасывают очередь команд), а также предпочтение простых прямолинейных машинных команд аналогичным сложным.

Тем не менее, вашей наиглавнейшей заботой должны быть ощущения потенциального пользователя при работе с вашей программой: насколько производительной покажется программа ему? Прислушаемся к словам Майкла Эбраша: «Всякая оптимизация, ощущаемая пользователем, заслуживает того, чтобы ее сделать». И наоборот, если в массах пользователей о вашей программе складывается мнение, как о тупой и неуклюжей, то очень вероятно, что она не будет должным образом оценена. Примером может служить судьба пакета ToolBook. Следовательно, должно казаться, что ваша программа мгновенно откликается на действия пользователя, даже тогда, когда она занята длительными вычислениями или операциями с диском. Она должна поддерживать экран дисплея в «живом» состоянии, заполняя его чем-нибудь вроде циферблатов, термометров, и позволять пользователю безопасно прерывать длительные операции в любое время, если его намерения изменились и он решил заняться чем-нибудь еще.


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

В своей превосходной книге «Пишем эффективные программы» Джон Бентли рассказывает кошмарную историю из жизни фирмы Bell Labs — историю, которую мы все и всегда должны помнить:

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

Я совсем не хочу тыкать пальцем в мистера Высоцкого: в своей жизни я совершил множество промахов куда как серьезнее, но (поскольку я не работаю в Bell Labs) эти промахи, к счастью, не были увековечены в книге Джона Бентли. Однако этот случай из жизни Высоцкого — хороший пример того, как время и энергия могут быть растрачены в пустую на святое дело оптимизации и как рано или поздно проявляется отказ от методичного исполнения всех основных процедур профилирования и контроля в процессе оптимизации.

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

4. Отказ от универсальности

Операции умножения и деления требуют немалых усилий от почти любого центрального процессора, поскольку должны быть реализованы (аппаратно или программно) через сдвиги и сложения или сдвиги и вычитания соответственно. Старинные 4-разрядные и 8-разрядные процессоры не содержали машинных команд для умножения или деления, так что эти операции приходилось реализовывать при помощи длинных подпрограмм, где явным образом выполнялись сдвиги и сложения или вычитания. Первые 16-разрядные процессоры, такие, как 8086, 8088 и 68000, действительно позволяли производить операции умножения и деления аппаратными средствами, но соответствующие процедуры были невероятно медленными: в процессорах 8086 и 8088, к примеру, для деления 32-разрядного числа на 16-разрядное требовалось примерно 150 тактов.

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

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

В процессорах 8086 и 8088 эта программа может быть преобразована в более «быструю» последовательность сдвигов:

или даже в такую:

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

Но не торопитесь — даже эта простая оптимизация не так тривиальна, как кажется! Очередь команд в процессорах семейства 80×86 и 80×88, конкретная модель процессора, которая используется в вашем компьютере, и наличие или отсутствие кэш-памяти могут в совокупности сыграть самые причудливые шутки. В некоторых случаях и на некоторых моделях центрального процессора иногда стоит использовать эту команду в варианте «сдвиг на указанное в CL число позиций»:

Илон Маск рекомендует:  Предопределённые константы interbase

А в процессорах 80186, 80188, 80286, 80386 и 80486 имеется вариант «сдвиг на число позиций, заданное непосредственным операндом», что еще удобнее:

Если вам требуется умножать на степень двойки числа длиной больше 16 разрядов, для организации операций над двумя и более регистрами используется флажок переноса. Например, для умножения 32-разрядного числа в DX:AX на 4 можно записать:

Творчески сочетая сдвиги и сложения, можно организовать быстрое умножение на почти любое конкретное значение. Следующий фрагмент производит умножение значения в регистре AX на 10:

Использование отказа от универсальности для деления несколько более ограничено. Деление на степень двойки, конечно, очень просто. Вы просто сдвигаете число вправо, следя лишь за выбором подходящей команды сдвига для желаемого типа деления (со знаком или без знака). Нахождение же остатка от деления на степень двойки для чисел без знака еще проще. Для этого надо просто выполнить одну команду операции логического И над операндом и непосредственным значением, которое, в свою очередь, должно быть представлено в виде уменьшенного на единицу значения делителя. Для чисел со знаком тут дела обстоят не так просто, так как знак остатка от деления должен быть равен знаку делителя и не зависит от знака делимого. Реализация этих операций потребует обязательного присутствия условных переходов, а это уже плохо. Например, для выполнения деления без знака на 4 содержимого регистра AX можно написать:

а для процессоров 80186, 80188, 80286, 80386 и 80486 можно вместо этого использовать команду:

Нахождение остатка от деления числа без знака на 4 производится следующим образом:

не правда ли слишком просто!

Деление со знаком на 4 обеспечит, например, последовательность:

или для процессоров 80186, 80188, 80286, 80386 и 80486:

Единственная разница между командой логического (без знака) сдвига SHR и командой арифметического (со знаком) сдвига SAR состоит в том, что SHR копирует старший, знаковый разряд в следующий, а затем заменяет знаковый разряд нулем, тогда как SAR , после копирования знакового разряда в следующий, оставляет его значение неизменным.

Выбор правильной команды сдвига для быстрого деления очень важен, особенно, если вы имеете дело с адресами. Если вы случайно использовали арифметическое деление (со знаком) вместо деления без знака, которое предполагали сделать, последствия этого иногда проявляются сразу же — а иногда и нет; образовавшаяся «блоха» может до поры притаиться и укусить вас позже, когда какое-нибудь изменение размера или порядка компоновки прикладных программ выпустит ее на волю. (Между прочим не забывайте, что мнемоническое обозначение SHL и SAL транслируются в одну и ту же машинную команду и не без причины, не так ли?)

Деление на степени двойки со сдвигами может быть выполнено с помощью флага переноса, и оно ничуть не более сложно, чем умножение. Например, для выполнения деления со знаком на 8 значения в регистрах DX:AX можно использовать последовательность:

Но, в отличие от операции умножения, использование сдвигов для более быстрого деления или нахождения остатков от деления на произвольные величины, такие как 3 или 10, а не на степени двойки на удивление хлопотно. Если вы решите покорпеть над написанием программы быстрого деления на 10, в которой используется метод, аналогичный приведенному выше методу умножения на 10, то вскоре обнаружите, что полученная программа — длинная, работает медленно, и, более того, — вы уже сделали 90% работы, необходимой для составления обобщенной программы деления, использующей сдвиги и вычитания. Обычно целесообразнее вместо этого обдумать всю ситуацию заново и преобразовать алгоритм или структуру данных так, чтобы избежать деления на «неудобные» числа.

Прежде чем оставить эту тему и двигаться дальше, я должен упомянуть одну изящную оптимизацию, авторство которой приписывают Марку Збиковскому, одному из авторов версий 2.x и 3.x системы MS-DOS. Приведенный ниже фрагмент делит без знаковое значение в регистре AX на 512:

Теперь, когда вы увидели этот нетривиальный прием, у вас наверняка возникло множество идей о том, как организовать умножение или деление без знаковых чисел на относительно большие степени двойки: 256, 512 и так далее, при помощи последовательностей команд XCHG или MOV .

5. Оптимизация переходов и вызовов подпрограмм

Макаронные программы, изобилующие ветвлениями и переходами во всех направлениях, нежелательны во всех смыслах, а при работе с процессорами серий 80×86 и 80×88 — особенно. Можете считать это утверждение напутствием, цель которого — побудить программистов на ассемблере и тех, кто занимается оптимизацией компиляторов, должным образом структурировать программы. Тут есть свои проблемы, но прежде, чем обсуждать оптимизацию переходов и вызовов, давайте обсудим некоторые особенности процессоров фирмы Intel.

Быстродействие этих процессоров в значительной мере определяется их архитектурой, основанной на простой конвейерной схеме, содержащей три компоненты: шинный интерфейс (BIU — Bus Interface Unit), очередь упреждающей выборки и исполнительный модуль (EU — Execution Unit). Когда шина памяти находится в нерабочем состоянии (например, при выполнении команды из многих циклов, операнды которой находятся в регистрах), шинный интерфейс извлекает байты команд из памяти и помещает их в очередь упреждающей выборки, последовательно продвигаясь дальше от текущего положения командного счетчика центрального процессора. Когда исполнительный модуль завершает выполнение очередной команды, он в первую очередь ищет следующую команду в очереди упреждающей выборки: если она там действительно имеется, то к ее расшифровке можно приступать сразу же, не обращаясь лишний раз к памяти.

Как же при такой реализации конвейерной обработки происходят переходы и вызовы подпрограмм? Всякий раз, когда исполнительный модуль расшифровывает команду перехода или вызова, он аннулирует текущее содержимое очереди упреждающей выборки и устанавливает новое содержимое счетчика команд. После этого шинный интерфейс должен снова выбирать байты команд, теперь уже начиная с нового адреса, и заносить их в очередь. Исполнительный модуль в это время вынужден «простаивать» до тех пор, пока не будет восстановлена полная команда. Кроме того, все обращения к памяти, которые требуются для исполнения команды перехода по новому адресу, также оказывают влияние на выборку следующих команд из памяти. Может пройти немалое время, прежде чем шина снова заполнит очередь упреждающей выборки так, чтобы исполнительный модуль мог работать с максимальной скоростью. Ситуацию усложняет то, что размер очереди командных байтов разный для разных моделей центральных процессоров. Он составляет всего 4 байта в ранних моделях и 32 байта в компьютерах последних моделей. Это один из факторов, делающий крайне сложным предсказание времен исполнения для конкретных последовательностей команд исходя из количества тактов и длин в байтах. Кроме того, состояние очереди команд для различных типов центральных процессоров зависит и от «выравнивания» команд. Шинный интерфейс должен выбирать команды в соответствии с разрядностью адресной и информационной частей шины. Поэтому производительность очереди команд может существенно ухудшиться из-за неудачных адресов вызовов или переходов. Например, в процессоре 8086 с 16-разрядной шиной памяти выборка из памяти всегда происходит по 16 битов за один раз, так что если команда, на которую передается управление при переходе или вызове подпрограммы начинается с нечетного адреса, половина первого обращения к памяти пропадает впустую.

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

Процессоры 8088 и 80188 имеют 8-разрядную внешнюю шину, так что они абсолютно нечувствительны к выравниванию. Если потенциальными потребителями вашей программы являются пользователи компьютеров на процессорах 8088 или 80188, к выравниванию прибегать не стоит, поскольку оно лишь потребует дополнительной памяти, но не увеличит производительность.

В то же время, если программе предстоит работать главным образом на компьютерах с процессорами 8086, 80186 или 80286, следует произвести выравнивание в границах WORD, а если она рассчитана на процессоры 80386 или 80486 — используйте выравнивание в границах DWORD. (Для процессора 80486, в котором есть внутренняя кэш-память, лучше, когда позиции лежат на 16-байтовых границах, но тратить в среднем по 8 лишних байт на каждую метку мне кажется непозволительной роскошью.)

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

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

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

Оптимизация программ на ассемблере (часть 3)

Это в наше-то время говорить об оптимизации программ? Бросьте! Не лучше ли сосредоточиться на изучении классов MFC или технологии .NET? Современные компьютеры так мощны, что даже Windows XP оказывается бессильна затормозить их!

Нынешние программисты к оптимизации относятся более чем скептически. Позволю себе привести несколько типичных высказываний:

» …я применяю относительно медленный и жадный до памяти язык Perl, поскольку на нем я фантастически продуктивен. В наше время быстрых процессоров и огромной памяти эффективность — другой зверь. Большую часть времени я ограничен вводом/выводом и не могу читать данные с диска или из сети так быстро, чтобы нагрузить процессор. Раньше, когда контекст был другим, я писал очень быстрые и маленькие программы на C. Это было важно. Теперь же важнее быстро писать, поскольку оптимизация может привести к столь малому росту быстродействия, что он просто не заметен «, — говорит Robert White;

» …а стоит ли тратить усилия на оптимизацию и чего этим можно достичь? Дело в том, что чем сильнее вы будете адаптировать вашу программу к заданной архитектуре, тем, с одной стороны, вы достигнете лучших результатов, а, с другой стороны, ваша программа не будет хорошо работать на других платформах. Более того, «глубокая» оптимизация может потребовать значительных усилий. Все это требует от пользователя точного понимания чего он хочет добиться и какой ценой «, — пишет в своей книге «Оптимизация программ под архитектуру CONVEX C» М. П. Крутиков;

  • » Честно говоря, я сам большой любитель “вылизывания” кода с целью минимизации используемой памяти и повышения быстродействия программ. Наверное, это рудименты времен работы на ЭВМ с оперативной памятью в 32 Кбайт. С тем большей уверенностью я отношу “эффективность” лишь на четвертое место в критериях качества программ «, — признается Алексей Малинин — автор цикла статей по программированию на Visual Basic в журнале «Компьютер Пресс».
  • С приведенными выше тезисами, действительно, невозможно не согласиться. Тем не менее, не стоит бросаться и в другую крайность. Начертавший на своем знамени лозунг «на эффективность — плевать» добьется только того, что плевать (причем дружно) станут не в эффективность, а в него самого. Не стоит переоценивать аппаратные мощности! И сегодня существуют задачи, которым не хватает производительности даже самых современных процессоров. Взять хотя бы моделирование различных физических процессов реального мира, обработку видео-, аудио- и графических изображений, распознавание текста… Да что угодно, вплоть до элементарного сжатия данных архиватором a la Super Win Zip!

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

    Цель — определяет средства . Вот из этого, на протяжении всей книги, мы и будем исходить. Ко всем оптимизирующим алгоритмам будут предъявляется следующие жесткие требования:

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

    оптимизация не должна увеличивать трудоемкость разработки (в т. ч. и тестирования) приложения более чем на 10%—15%, а в идеале, все критические алгоритмы желательно реализовать в виде отдельной библиотеки, использование которой не увеличивает трудоемкости разработки вообще;

    оптимизирующий алгоритм должен давать выигрыш не менее чем на 20%—25% в скорости выполнения. Приемы оптимизации, дающие выигрыш менее 20% в настоящей книге не рассматриваются вообще, т. к. в данном случае «овчинка выделки не стоит». Напротив, основной интерес представляют алгоритмы, увеличивающие производительность от двух до десяти (а то и более!) раз и при этом не требующие от программиста сколь ни будь значительных усилий. И такие алгоритмы, пускай это покажется удивительным, в природе все-таки есть!

  • оптимизация должна допускать безболезненное внесение изменений.
    Достаточно многие техники оптимизации «умерщвляют» программу, поскольку даже незначительная модификация оптимизированного кода «срубает» всю оптимизацию на корню. И пускай все переменные аккуратно распределены по регистрам, пускай тщательно распараллелен микрокод и задействованы все функциональные устройства процессора, пускай скорость работы программы не увеличить и на такт, а ее размер не сократить и на байт! Все это не в силах компенсировать утрату гибкости и жизнеспособности программы. Поэтому, мы будем говорить о тех, и только тех приемах оптимизации, которые безболезненно переносят даже кардинальную перестройку структуры программы. Во всяком случае, грамотную перестройку. (Понятное дело, что «кривые» руки угробят что угодно — против лома нет приема).
  • Согласитесь, что такая постановка вопроса очень многое меняет. Теперь никто не сможет заявить, что, дескать, лучше прикупить более мощный процессор, чем тратить усилия на оптимизацию. Ключевой момент предлагаемой концепции состоит в том, что никаких усилий на оптимизацию тратить как раз не надо . Ну… почти не надо, — как минимум вам придется прочесть эту книжку, а это какие ни какие, а все-таки усилия . Другой вопрос, что данная книга предлагает более или менее универсальные и вполне законченные решения, не требующие индивидуальной подгонки под каждую решаемую задачу.

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

    И в заключении позвольте привести еще одну цитату:

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

    Это мысли об эффективности в то время, когда я пытаюсь решить проблему. Мне кажется, что гораздо логичнее концентрироваться полностью на проблеме, решить ее, а затем творчески запрограммировать, затем, если решение медленное (что затрудняет работу с ним), то. «

    О чем и для кого предназначена эта книга

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

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

    В не меньшей степени «Техника оптимизации» будет интересна и лицам, занимающимся сборкой и настройкой компьютеров, поскольку подробно описывает устройство «железа» и разбирает «узкие места» распространенных моделей комплектующих.

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

    Материал книги в основном ориентирован на микропроцессоры AMD Athlon и Intel Pentium-II, Pentium-III и Pentium-4, но местами описываются и более ранние процессоры.

    Семь китов оптимизации или
    Жизненный цикл оптимизации


    Часто программист (даже высококвалифицированный!), обнаружив профилировщиком «узкие» места в программе, автоматически принимает решение о переносе соответствующих функций на ассемблер. А напрасно! Как мы еще убедимся (см. Часть III. » Смертельная схватка: ассемблер VS-компилятор «), разница в производительности между ручной и машинной оптимизацией в подавляющем большинстве случаев крайне мала. Очень может статься так, что улучшать уже будет нечего, — за исключением мелких, «косметических» огрехов, результат работы компилятора идеален и никакие старания не увеличат производительность, более чем на 3%—5%. Печально, если это обстоятельство выясняется лишь после переноса одной или нескольких таких функций на ассемблер. Потрачено время, затрачены силы… и все это впустую. Обидно, да?

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

    Назовем ряд правил оптимизации.

    Правило I

    Прежде, чем оптимизировать код, обязательно следует иметь надежно работающий не оптимизированный вариант или «. put all your eggs in one basket, after making sure that you’ve built a really *good* basket» («…прежде, чем класть все яйца в одну корзину — убедись, что ты построил действительно хорошую корзину «). Таким образом прежде, чем приступать к оптимизации программы, убедись, что программа вообще-то работает.

    Создание оптимизированного кода «на ходу», по мере написания программы, невозможно! Такова уж специфика планирования команд — внесение даже малейших изменений в алгоритм практически всегда оборачивается кардинальными переделками кода. Потому, приступайте к оптимизации только после тренировки на «кошках», — языке высокого уровня. Это поможет пояснить все неясности и «темные» места алгоритма. К тому же, при появлении ошибок в программе подозрение всегда падает именно на оптимизированные участки кода (оптимизированный код за редкими исключениями крайне ненагляден и чрезвычайно трудно читаем, потому его отладка — дело непростое), — вот тут-то и спасает «отлаженная кошка». Если после замены оптимизированного кода на не оптимизированный ошибки исчезнут, значит, и в самом деле виноват оптимизированный код. Ну, а если нет, то ищите их где-нибудь в другом месте.

    Правило II

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

    Правило III

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

    Правило IV

    Прежде, чем порываться переписывать программу на ассемблер, изучите ассемблерный листинг компилятора на предмет оценки его совершенства. Возможно, в неудовлетворительной производительности кода виноват не компилятор, а непосредственно сам процессор или подсистема памяти, например. Особенно это касается наукоемких приложений, жадных до математических расчетов и графических пакетов, нуждающихся в больших объемах памяти. Наивно думать, что перенос программы на ассемблер увеличит пропускную способность памяти или, скажем, заставит процессор вычислять синус угла быстрее. Получив ассемблерный листинг откомпилированной программы (для Microsoft Visual C++, например, это осуществляется посредством ключа /FA), бегло просмотрите его глазами на предмет поиска явных ляпов и откровенно глупых конструкций наподобие: MOV EAX, [EBX]\MOV [EBX], EAX. Обычно гораздо проще не писать ассемблерную реализацию с чистого листа, а вычищать уже сгенерированный компилятором код. Это требует гораздо меньше времени, а результат дает ничуть не худший.

    Правило V

    Если ассемблерный листинг, выданный компилятором, идеален, но программа без видимых причин все равно исполняется медленно, не отчаивайтесь, а загрузите ее в дизассемблер. Как уже отмечалось выше, оптимизаторы крайне неаккуратно подходят к выравниванию переходов и кладут их куда "глюк" на душу положит. Наибольшая производительность достигается при выравнивании переходов по адресам, кратным шестнадцати, и будет уж совсем хорошо, если все тело цикла целиком поместится в одну кэш-линейку (т. е. 32 байта). Впрочем, мы отвлеклись. Техника оптимизации машинного кода — тема совершенно другого разговора. Обратитесь к документации, распространяемой производителями процессоров — Intel и AMD.

    Правило VI

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

    Правило VII

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

    Единственная предметная область, не только оправдывающая, но, прямо скажем, провоцирующая ассемблерные извращения, это — защита программ, но это уже тема совсем другого разговора…

    Распространенные заблуждения

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

    Заблуждение I

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

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

    Заблуждение II

    Перенос программы на ассемблер только в исключительных случаях увеличивает ее эффективность. При трансляции качественного исходного кода, оптимизирующие компиляторы отстают от идеальной ручной оптимизации не более чем на 10%—20%. Конечно, это весьма ощутимая величина, но все же не настолько, чтобы оправдать трудоемкость программирования на чистом ассемблере!

    Подробнее о сравнении качества машинной и ручной оптимизации см. Часть III. " Смертельная схватка: ассемблер VS-компилятор ".

    Заблуждение III

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

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

    Илон Маск рекомендует:  Atof, atoi, atol преобразовать в плавающее

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

    Тем не менее, современные процессоры с одной стороны достаточно умны и самостоятельно оптимизируют переданный им на выполнение код. С другой стороны оптимального кода для всех процессоров, все равно не существует и архитектурные особенности процессоров P-II, P-4, AMD K6 и Athlon отличаются друг от друга столь разительно, что все позывы к ручной оптимизации гибнут прямо на корю.

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

    Заблуждение IV

    Как гласит народная мудрость "Хорошо там, — где нас нет". Сам я, правда, ничего не оптимизирую под PowerPC, но хорошо знаком с людьми, разрабатывающими под него оптимизирующие компиляторы. И могу сказать, что они далеко не в восторге от его "закидонов", коих у него, поверьте уж, предостаточно.

    Да, семейству процессоров x86 присущи многие проблемы и ограничения. Но это ничуть не оправдывает программистов, пишущих "уродливый" код, и палец о палец не ударяющих, чтобы хоть как-то его улучшить.

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

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

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

    Сегодня эти мощности вызывают улыбку. Но традиции оптимизации кода сохранились. Как известно, сколько ни наращивай размер диска и объем ОЗУ, все равно будет мало. Потому написанные «неряшливо» приложения, медленные и ресурсоемкие, проигрывают конкурентную борьбу аналогам, даже если они красивы и удобны.

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

    Основные принципы оптимизации

    Оптимизация стоит на трех «китах» — естественность, производительность, затраченное время. Давайте разберемся подробнее, что они означают.

    1. Естественность. Код должен быть аккуратным, модульным и легко читабельным. Каждый модуль должен естественно встраиваться в программу. Код должен легко поддаваться редактированию, интегрированию или удалению отдельных функций или возможности без необходимости вносить серьезные изменения в другие части программы.
    2. Производительность. В результате оптимизации вы должны получить прирост производительности программного продукта. Как правило, удачно оптимизированная программа увеличивает быстродействие минимум на 20-30% в сравнение с исходным вариантом.
    3. Время. Оптимизация и последующая отладка должны занимать небольшой период времени. Оптимальными считаются сроки, не превышающие 10 – 15 % времени, затраченного на написание самого программного продукта. Иначе это будет нерентабельно.

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

    Стоит ли применять Ассемблер

    Многие разработчики искренне считают, что критические секции (некоторые называют их «узкими» местами программы) кода удобнее писать на ассемблере, так как он обеспечивает самый быстрый доступ к данным и устройствам.

    Многочисленные сравнения результатов оптимизации кода на языке высокого уровня и применения ассемблерных вставок показывают, что в первом случае после компиляции программа будет работать чуть медленнее, чем при использовании ассемблера. Обычно эти цифры измеряются от 2% до 7%. Максимум – разница составляет 20%. Стоит ли ради получения столь малого эффекта тратить время и силы на написание ассемблерной версии? На наш взгляд лучше уделить больше внимания работе с кодом, который написан на ЯП высокого уровня, и оптимизировать работу алгоритма.

    Как правильно оптимизировать

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

    Начало оптимизации

    Первое, что необходимо сделать, это выявить «узкие места» программы. Нет смысла трогать тот кусок программы, где и без вас все работает прекрасно. Здесь вы вряд ли что-то выиграете при оптимизации. В первую очередь, стоит обратить внимание на блоки кода, которые регулярно или часто повторяются в процессе работы – циклы и подпрограммы.

    Пример: Если оптимизировать работу цикла хотя бы на 2% за одну итерацию, а число его повторов будет 1000 раз, в итоге мы получаем: 2% × 1000 = 2000%, вполне ощутимый результат при работе кода.

    Участки кода, которые не оптимизируются

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

    Также вы не сумеете добиться достойных результатов в случае обращения к внешним устройствам и другим программным системам. До и после таких фрагментов можно что-то ускорить. Но там, где задержка может возникать по причине взаимодействия с внешними данными, лучше предусмотрите заглушку типа «Подождите, операция может занять несколько минут».

    Еще раз об ассемблере

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

    Оптимизировать или нет?

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

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

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

    Методы оптимизации программ

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

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

    Пишите аккуратный код. Не забывайте о комментариях. Так вы поможете и себе, и другим разработчикам, понять, что в программе нужно, а что – уже не актуально. Эти общие советы помогают и при отладке, и при поиске багов. В общем, не будьте неряшливым «говнокодером», и ваши программы будут работать быстро и без проблем.

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

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

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

    Настройка окружения

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

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

    Также обратите внимание на саму операционную систему и мощность «железа». Может быть они вообще не предназначены для работы программного продукта, который вы пытаетесь запустить и ускорить? А, может, устарели и потому «тормозят»?


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

    Избавляемся от ненужного функционала

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

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

    Мемоизация

    Меморизация (от англ. Memoization) означает запоминание. Фактически это простое сохранение результата выполнения определенной функции, которое поможет избежать ее повторного выполнения. Применяя меморизацию, вы сможете повысить производительность программы.

    Работает это очень просто. Перед тем, как функция будет выполняться, проверяется условие – исполнялась ли она ранее. По итогам можно получить два варианта:

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

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

    Кеширование

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

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

    Распараллеливание программ

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

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

    «Ленивые» вычисления

    Ленивые (Lazy evaluation) или отложенные вычисления – стратегия, которую применяют в некоторых системах счисления. Суть метода заключается в том, что все расчеты откладываются до тех пор, пока не будет затребован их результат.

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

    Метод приближения

    Приближение или аппроксимаация (от лат. proxima — ближайшая или приближе́ние) – метод замены строгого алгоритма на наиболее подходящие приближенные значения, что влечет за собой определенную потерю точности вычислений. Снижение точности экономит память и повышает скорость. Для того чтобы не использовать длинную арифметику, можно воспользоваться обычными float’ами. Но пользоваться таким методом нужно крайне осторожно, не всегда снижение точности допустимо.

    Использование сторонних языков

    Иногда написанная программа может медленно работать из-за того, что много времени занимает проверка описанных типов, что занимает дополнительное время. Чтобы избежать этого эффекта, можно применять фрагменты кода или модули, написанные на других языках. Но делать это нужно крайне осторожно. Все эти «лишние» проверки защищают вас от багов и «дыр» в безопасности, связанных, в том числе, с буферизацией. Потому хорошо подумайте, действительно ли экономия времени столь существенна? И если придете к выводу, что здесь это – лучшее решение, обязательно проведите особо внимательное тестирование.

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

    Существует еще очень много методов оптимизации, как общеизвестных, так и личных находок программистов. Мы постарались рассказать, что такое оптимизация, и познакомить вас с самыми популярными методами. А как вы ускоряете работу своих приложений? Делитесь в комментариях.

    Оптимизация ассемблерных программ арифметических операций

    Ответ

    Операция деления самая сложная в математике и, как следствие, в аппаратной и программной реализациях. Как пример этому очень много вопросов на форумах программистов – «сваливается» программа деления, «деление на ноль – почему? Я делал все правильно, как учили, делил слово на байт!» и т.п. Очень часто дают советы типа: «такое деление в целых числах выполнять не целесообразно, всегда будет ноль в ответе, переходите на FPU». А на самом деле выполнить нормальное деление при указанных условиях можно!
    Практически на все подобные вопросы найдете ответы в подразделах книги 2.6 и 2.7 «Масштабирование операции деления» и «Особые случаи масштабирования операции деления» соответственно.
    В книге приводятся типовые варианты программ деления, которые можно использовать как шаблоны. Как всегда много практических примеров.
    Основное правило для программиста при реализации операции деления - частное не должно выходить за установленные разработчиком аппаратной части (в нашем случае Intel-ом) рамки в машинных целых числах:
    для байта – -128 или +127;
    для слова – - 32768 или + 32767;
    для двойного слова – - 2 141 483 648 или + 2 141 483 647
    для квадрослова – - 9 223 372 036 854 775 808 или + 9 223 372 036 854 775 807.
    В этом смысле так и хочется подвергнуть критике пиаровское словоблудие в мануале Intel о делении слова на байт, двойного слова на слово, квадрослова на двойное слово и т.п. Но здесь этим заниматься не будем.
    Intel так организовал аппаратное деление, что требует числитель располагать в расширенном аккумуляторе:
    для байта это регистры AH:AL
    для слова DX:AX
    для двойного слова EDX:EAX
    для квадрослова RDX:RAX
    (Здесь: аккумулятор AL, AX, EAX, RAX; расширение аккумулятора - AH, DX, EDX, RDX.) При этом во всех битах расширителя аккумулятора должен быть знак числителя! Для облегчения программистам выполнять это условие Intel предусмотрел специальные команды копирования знака аккумулятора во все биты расширения:
    CBW (Convert Byte to Word) преобразовать байт в слово;
    CWD (Convert Doubleword to Quadword) преобразовать слово в двойное слово;
    CDQ (Convert Doubleword to Quadword) преобразовать двойное слово в квадрослово;
    CQO (Convert Quadword to OWord ) преобразовать квадрослово в восемь слов (OctavWord). Команды расширения обязательно должны применяться при программировании знакового деления. Их место в программе – перед командой IDIV. Если применяется беззнаковое деление (команда DIV) обязательно необходимо в расшерение загрузить ноль.
    Если эти условия выдерживать – команды IDIV и DIV будут выполняться безупречно во всем диапазоне изменения числителя одинарного формата (от 800…00h до 7FF…FFh), и во всем диапазоне изменения знаменателя независимо от значения числителя от 800…00h до 7FF…FFh, кроме 0h, естественно, и даже при 01h. При этом, возможны специфические случаи, когда
    истинные числитель и знаменатель не равны каждый независимо друг от друга нулю, при этом истинное частное, естественно, не равно нулю; для этого же случая машинные числитель и знаменатель независимо друг от друга не равны нулю, а машинное частное – равно нулю. Такой случай возникает тогда, когда машинный числитель в одинарной (первоначальной, нерасширенной) разрядности по абсолютной величине меньше машинного значения (одинарной разрядности) знаменателя. В любой позиционной системе счисления если 50/700 , то целая часть частного равно нулю. Дробная часть – 5/70, или 50 в остатке. Intel не дает возможности получать дробную часть частного, частное в аппаратном решении у него – одинарной разрядности и только старшая часть. (Вспомните, при умножении аппаратная часть дает программный доступ к полному произведению удвоенной разрядности!). Легко проверить (в книге это показано), что при полнодиапазонном изменениях числителя и знаменателя, независимо друг от друга, под частное необходимо, в идеальном случае, выделять удвоенную разрядность. А Intel в аппаратуре выделяет только старшую часть одинарной разрядности!
    Учитывая все сказанное становится понятным почему появляется «деление на ноль» и нецелесообразность выполнять некоторые операции деления в целых числах.
    Если заранее известно, что машинное значение знаменателя никогда не достигнет своего самого наименьшего значения 000…01h для положительных чисел или 0FF…FFh для отрицательных чисел, то можно повысить точность или даже реанимировать операцию деления за счет левого сдвига расширенного числителя на строго определенное число разрядов. В книге приводится методика расчета числа разрядов для повышения точности.
    Примеры.
    Здесь http://www.cyberforum.ru/assembler/thread398874.html участник форума попросил помочь вычислить значение выражения

    Частное должно быть в AX, в DX – остаток. Имеем: AX = 0, DX = 0003

    Для отрицательного значения А (пусть оно будет А=-3) основное тело программы будет (пример 2):

    Перед выполнением собственно операции деления в аккумуляторе машинный числитель c учетом представления отрицательных чисел в дополнительном коде AX = FFFD h = (-0003h) = (-3)d. В регистре BX машинное значение делителя BX=000Ah =10d. При делении в позиционной системе счисления (-0003)h на 000Аh или (-3)d на 10d мы получим 0 целых в регистре AX и остаток в регистре DX=FFFDh.
    Нетрудно заметить, что при реализации исходного выражения в программах, написанных как показано выше, при любых значениях А перед операцией деления машинный числитель всегда будет меньше машинного знаменателя. Это означает, что ответ всегда будет равен 0! То есть программа при реализации в целых числах не имеет смысла. Следовательно, сделаем вывод, необходим FPU!
    Не будем торопиться. Методика, предложенная в книге, весьма эффективна! Применим ее для рассматриваемого примера. Пусть А=-3, разрядность N=16.
    Выполним масштабирование:
    масштаб А=3 в целочисленной арифметике

    коэффициент выравнивания масштаба 1-цы при ее сложении с Y1

    масштаб знаменателя, то есть Y2=(Y1+1)=10

    предварительная оценка масштаба частного Y3 = A/Y2, то есть результата

    (в книге предварительные масштабы помечаются звездочкой);

    фактический масштаб результата

    запас по точности при выполнении деления

    Основное тело программы будет иметь вид (пример 3):

    Выполнение этой программы дает следующий результат:
    частное в АХ – B334h;
    остаток в DX – C000h;
    истинное значение частного с учетом представления отрицательных чисел в дополнительном коде будет равно

    Пусть А=3, разрядность данных также 16.
    Выполним масштабирование:
    масштаб А-3 в целочисленной арифметике

    коэффициент выравнивания масштаба 1-цы при ее сложении с Y1

    масштаб знаменателя, то есть Y2=(Y1+1)=10

    предварительная оценка масштаба частного Y3 = A/Y2 , то есть результата

    фактический масштаб результата

    запас по точности при выполнении деления

    Основное тело программы будет иметь вид (пример 4):

    Выполнение этой программы дает следующий результат:
    частное в АХ – 9999h
    остаток в DX - 6000h
    Истинное значение частного будет равно

    Если выполнять вычисления с разрядностью N=8, то для А=3 основное тело программы будет иметь вид:

    Частное будет в AL =99h.
    Истинное значение частного в этом случае равно:

    Очевидно, что комментарии здесь излишни.
    Более интересным был бы пример программы, которая вычисляет значение функции

    допустим в интервале изменения аргумента Х от -6 до +6.
    Рассмотрим этот пример на следующем занятии.
    Напомню, что конечная дробь в одной позиционной системе счисления не обязательно будет конечной в другой. Конечная в десятичной системе счисления дробь 0,3d - в двоичной будет периодической 0,0(1001)b = 0,25+0,003125 + …. = 0,28125 + …. .
    В книге обнаружена еще неточность. На стр. 103 на восьмой строке снизу неправильная ссылка на рисунок: есть «рис. 2.29, ……», должно быть – «рис. 2.25, ….»
    В прилагаемых файлах:
    деление.pdf – скан соответствующего раздела книги;
    Pr4.doc – полный текст программы пяти примеров, рассмотренных выше с комментариями. Программа написана под MS DOS. Текст программы написан в виндовском Блокноте.
    Вложение 242121
    Вложение 242119
    Желаю всем успехов!

    Оптимизация программ на ассемблере (часть 3)

    Итак, в сегодняшней статье мы доработаем нашу программу, добавив в нее задержку в 1 секунду. Кроме этого мы познакомимся с основными отладочными инструментами, которые поставляются вместе с MPLAB. Это поможет нам до конца разобраться во внутренней работе МК.

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

    Эта программа не сильно отличается от той, которую мы писали в прошлый раз, однако не стоит расстраиваться. Разбираться во внутренней работе МК лучше на примере простых программ. Итак, приступим. Первое, что мы изменили в нашей программе, это добавили строчки:

    Первая строкой мы подключаем к нашему проекту файл p16f877.inc. Он находится в папке Microchip\MPASM Suite. Чтобы посмотреть содержимое этого файла нажимаем Project -> Add Files to Project… Должно появиться такое окошко:

    Указываем тип файлов Header Files и выбираем файл P16F877.INC. Видим, что файл появился в менеджере проектов:

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

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

    Было не совсем понятно, откуда вообще взялось число H'3F72'. В данной программе мы немного изменим эту строчку:

    Однако если заменить эти имена константами и произвести над ними логическую операцию “AND”, то у нас как раз и получится число H'3F72'. Единственная разница лишь в том, что новая запись стала нагляднее. Поехали дальше:

    В прошлый раз для формирования задержки мы использовали одну переменную. В этот раз мы будем использовать целых три – DelH, DelM, DelL с адресами 0x20, 0x21, 0x22 соответственно. Это позволит увеличить длительность задержки между миганиями светодиодов до 1 секунды. Идем дальше:

    Для понимания этих строчек придется сделать маленькое отступление. В самой первой статье я уже Вам рассказывал про организацию памяти. Как Вы помните, все инструкции программы у нас хранятся в памяти программ МК, и каждая инструкция занимает 14 бит. Предлагаю на примере разобраться, что же конкретно записано в этих битах. Допустим, вы написали команду clrf PORTB, которая, как вы уже знаете, очищает содержимое регистра PORTB. Так вот, компилятор переводит эту команду в машинное слово вида:

    14-разрядный код

    Первые семь бит этой команды хранят адрес регистра, который нужно отчистить. Максимальный адрес, который можно в него записать это 0x7F. Теперь, я думаю, стало понятно, почему у нас все четыре банка памяти не превышают этого размера. Вслед за адресом регистра у нас идет код команды, который также занимает семь бит. Для операции clrf, например, код команды имеет вид B’0000011’. На этом примере я описал структуру так называемых байт ориентированных команд. Такие команды производят действия над целым байтом данных. Однако у нашего контроллера есть несколько бит ориентированные команд (например, bsf или bcf), а также команды управления и операции с константами, причем их представление в машинном виде будет немного отличается от разобранного в примере выше.

    Итак, после того, как компилятор перевел ассемблерные инструкции в машинный код их нужно записать в память программ. Однако перед этим нужно указать, с какой именно ячейки памяти мы хотим начать запись нашей программы. Как раз для этого мы в начале и пишем ORG 0x00, тем самым указывая компилятору, что запись всех последующих команд нужно начинать с нулевого адреса, куда и будет записана команда goto Start. Дальше снова стоит команда ORG 0x05, а за ней команда clrf INTCON (метка Start: в памяти не записывается, помните?). Тем самым по адресу 0x05 записывается команда clrf INTCON. Чтобы наглядно увидеть, как располагаются команды в памяти, скомпилируйте проект и нажмите View->Disassembly Listing. Появится такое окошко:

    В первом столбце располагаются адрес ячейки, в которой хранится команда. Дальше идет представление команды в шестнадцатеричной системе счисления. Ну а потом реальная команда, которая там хранится. Посмотрите внимательнее. Мы писали команду goto Start, а компилятор изменил ее на goto 0x5. То есть компилятор автоматически заменил метку Start на физический адрес 0x5, в которой записана команда clrf INTCON. Тут нет ничего сложного. Единственное о чем осталось упомянуть – это счетчик команд PC (program counter). Счетчик команд – это 13-разрядный регистр, который хранит адрес выполняемой инструкции в памяти программ.

    Младший регистр (8-битный) счетчика команд находится по адресу 0x2 (PCL). Он доступен как для записи, так и для чтения. А вот старший регистр (5-битный) для записи и чтения недоступен. Чтобы его изменить, нужно воспользоваться дополнительным регистром PCLATH, который находится по адресу 0x0A. При каждом старте микроконтроллера регистр PC очищается, поэтому выполнение инструкций всегда начинается с нулевого адреса. Микроконтроллер загружает на выполнение инструкцию, адрес которой находится в регистре PC, а после ее выполнения содержимое регистра PC инкрементируется и загружается следующая инструкция. Другими словами регистр PC просто указывает МК по какому адресу нужно загрузить инструкцию на выполнение. Все просто. Поехали дальше:

    Илон Маск рекомендует:  Что такое код getimagesize

    Здесь Вам уже все знакомо. Единственное добавилось три команды nop. Пока опустим объяснения, для чего они нужны. Идем дальше:

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

    Этот цикл очень сильно напоминает тот, который мы использовали в прошлый раз. Единственная разница в том, что наш однобайтный таймер обратного отсчета превратился в трехбайтный. Принцип его работы почти такой же. Пока содержимое регистра DelL не станет равно нулю, мы будем крутиться в цикле Delay_L, при этом за каждый проход содержимое DelL будет декрементироваться. После этого мы перейдем в цикл Delay_M, в котором проверке подвергнется регистр DelM. А так как он не равен нулю, то мы опять перескочим на начало цикла Delay_L, и все начнется сначала. После нескольких таких витков содержимое регистра DelM станет равно нулю, мы попадем в цикл Delay_H, где будем проверять на ноль значение регистра DelH. И уж когда оно станет равно нулю, мы наконец-то увеличим значение порта PORTB и вернемся к началу цикла Loop. Все.

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

    С работой программы мы разобрались, теперь давайте познакомимся и отладочными средствами, предусмотренными в среде MPLAB. Для начала включим симулятор. Нажимаем Debugger -> Select Tools -> MPLAB SIM. Справа вверху появится панель вида:

    Нажимаем F6 (Reset) или желтую кнопку на панели справа, тем самым сбрасываем микроконтроллер. Посмотрите на код. Напротив команды goto Start должна появиться зеленая стрелка, которая показывает, какая инструкция готова на выполнение. Теперь нажимаем View -> File Registers. Должно появиться такое окошко:


    Это как раз представление нашей карты памяти данных, которую я рисовал на первом уроке, только выглядит она немного по-другому. Все регистры, значение которых изменяется после выполнения команды, будут подсвечиваться красным светом. С помощью карты памяти очень просто отслеживать состояние регистров, в процессе работы микроконтроллера. Щелкаем кнопку F7. Наш микроконтроллер выполнил команду goto Start, а зеленая стрелка перескочила на команду clrf INTCON. А теперь посмотрите в File Registers. Регистр по адресу 0x2 высветился красным светом, а его значение изменилось и стало равно 0x5. Если Вы помните, это как раз наш счетчик команд. То есть теперь мы будем выполнять инструкции, начиная с адреса 0x5.

    Поначалу очень непривычно пользоваться окном File Registers. Однако это не единственный инструмент, которым можно воспользоваться. Нажимаем View -> Watch. Появится вот такое окошко:

    Здесь мы можем добавлять только интересующие нас регистры общего или специального назначения, и следить только за их работой. Кстати, здесь можно понаблюдать за содержимым аккумулятора. Для этого нужно добавить SFR регистр WREG. Советую какое-то время понаблюдать за состоянием регистров в процессе работы МК, чтобы немного привыкнуть.

    Ну и напоследок давайте познакомимся еще с одним важным инструментом. Нажимаем Debugger -> StopWatch. Появится вот такое окошко:

    С помощью этого инструмента мы будем измерять задержку. Но для начала давайте установим BreakPoint'ы. Для этого два раза щелкаем по строчке clrf PORTB и incf PORTB. Слева должна появиться белая буква B в красном кружке. Именно время задержки между ними нам нужно измерить.

    Теперь нажимаем кнопку Play на панели симулятора, или щелкаем F9. В этом режиме будет происходить симуляция работы МК на компьютере, а остановится этот процесс тогда, когда мы доберемся до нашего первого BreakPoint'а. Посмотрите на окошко StopWatch. Его значения изменились:

    Теперь нажимаем Zero. Этим мы сбрасываем наш секундомер в ноль. И снова жмем F9. Микроконтроллер начал работать дальше, и остановится он только когда доберется до второго BreakPoint’а. В этот момент время задержки будут составлять ровно 1 секунду (взгляните на значение в колонке Time). Теперь пришло время объяснить, зачем я везде вставлял команды nop. Дело в том, что если вы их уберете, то задержка между миганием светодиодов будет меньше одной секунды. Конечно, это не так критично, особенно в работе нашей программы, однако это очень простой способ точной корректировки задержки, который очень часто применяется.

    Способы увеличения быстродействия программ

    Современные ЭВМ обладают очень большой мощностью. Скорость работы процессора (ЦП) современных ЭВМ измеряется гигагерцами, объём оперативной памяти гигабайтами, а современные интерфейсы устройств обеспечивают скорость обмена данными порядка, как минимум, нескольких сотен мегабайт в секунду [1]. Производительность, которая ещё несколько лет назад казалась «сказочной» в настоящее время стала нормой жизни.

    Однако параллельно росту мощности ЭВМ увеличивается и ресурсоёмкость приложений. У приложений совершенствуется функционал, интерфейс, возрастает объём обрабатываемых данных и как следствие системные требования. Поэтому вопрос об увеличении быстродействия приложений не теряет своей актуальности.

    Общие вопросы быстродействия программ.

    Быстродействие программ (ПО) зависит от многих факторов, но основными из них являются два:

    • Соотношение между реальными системными требованиями ПО и существующей аппаратной конфигурацией ЭВМ;
    • Алгоритмы работы ПО.

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

    1. Увеличивается производительность hardware, а вовсе не быстродействие ПО;
    2. Производительность hardware ограничена возможностями существующих в данный момент элементной базы и инженерных решений в данной области;
    3. Большие финансовые затраты на модернизацию и настройку по причине высокой стоимости комплектующих ЭВМ и услуг специалистов требуемой квалификации.

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

    1. Обеспечить работу нового ПО на уже существующем оборудовании;
    2. Разработать масштабируемое ПО;
    3. Значительно уменьшить финансовые и трудовые затраты при внедрении.

    Вместе с тем и у этого пути имеется ряд недостатков:

    1. Значительно усложняется процесс разработки ПО, так как более «быстрые» алгоритмы сложнее более «медленных» (на пример алгоритм бинарного поиска сложнее, чем алгоритм линейного поиска) [2];
    2. Реализация более сложных алгоритмов, как правило, требует привлечения специалистов более высокой квалификации;
    3. В случае работы с большими объёмами данных или выполнении задач требующих больших и сложных вычислений, ресурсоёмкость ПО всё равно остаются достаточно высокой. Несмотря, на какие либо способы увеличения быстродействия.

    Таким образом, в общем случае обеспечение быстродействия ПО является комплексной задачей.

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

    Программная инженерия предоставляет несколько способов увеличения быстродействия программ. Рассмотрим их на примере языков программирования Delphi и Assembler.

    Увеличение быстродействия программ.

    Как было показано в предыдущем параграфе, можно увеличить быстродействие ПО соответствующим образом реализовав его алгоритмы. Количественным показателем быстродействия алгоритма (а, следовательно, и ПО) является время его выполнения, измеренное по специальной методике, так называемого профилирования [2]. Таким образом, в общем случае выбор наиболее «быстрых» алгоритмов сводится к измерению времени их выполнения и сравнении полученных результатов между собой. Такой способ анализа быстродействия является наиболее объективным [2]. На протяжении многих лет программистами был накоплен большой опыт профилирования, который позволяет сделать определённые выводы относительно возможности оптимизации быстродействия ПО ещё на стадии написания.

    Эти выводы были обобщены и представлены в виде определённых рекомендаций [2, 4]. Если программист будет следовать данным рекомендациям, то написанная программа вероятнее всего будет обладать большим быстродействием, чем в случае их игнорирования. Однако следует ещё раз подчеркнуть, что достоверные сведения о быстродействии может дать только профилирование. Это обусловлено тем, что быстродействие алгоритма определяет в первую очередь его конкретная реализация. Кроме того необходимо ещё раз отметить, что в отношении увеличения быстродействия ПО программная инженерия не всесильна (см. предыдущий параграф).

    В чём же состоят выше упомянутые рекомендации? Их краткое содержание применительно к языку программирования Delphi приведено ниже.

    1. При написании кода программ рекомендуется избегать процедур, состоящих из сотен строк. Практически всегда в них можно выделить блоки, которые лучше оформить в виде отдельной процедуры. Возможно, позже вы ей даже воспользуетесь где-то в другом месте. Не говоря уже о том, что это повышает понимание программы и вами, и другими программистами. К тому же так проще искать «узкие» места в программе.
    2. Использование оператора case (switch) вместо многократных if… then… else (if… else). Во втором варианте компилятор будет выполнять проверку условия столько раз, сколько у вас вариантов. В первом проверка выполняется лишь однажды.
    3. Некоторые действия могут быть довольно продолжительными, поэтому рекомендуется выносить за рамки цикла всё, что можно выполнить вне его, чтобы избежать большого числа повторений внутри цикла.
    4. В циклах типа for нужно стараться, чтобы значение счетчика уменьшалось до нуля, а не наоборот — начиналось с нуля. Это связано с особенностями процессора. Сравнение с нулём выполняется гораздо быстрее, чем с другим числом.
    5. Пользоваться типом Variant только при необходимости. Операции над этим типом сложнее, чем, например, над Integer или String.
    6. Не злоупотреблять «программированием на компонентах». В частности не использовать компонент TTreeView для хранения древовидных структур данных — он работает очень медленно и предназначен только для визуального отображения. В случае работы со структурами данных лучше использовать алгоритмы, созданные самостоятельно на основе фундаментальных.
    7. Сохранение и загрузка свойств компонентов с помощью методов ReadComponent и WriteComponent работает довольно медленно, поэтому по возможности рекомендуется сохранять и восстанавливать состояние программы между сеансами при помощи других способов.
    8. Заменить простой в реализации алгоритм на более сложный, но с большим быстродействием. Например, если заранее известно, что в списке для поиска будет много элементов, лучше его отсортировать и применять бинарный поиск вместо линейного.
    9. В критических с точки зрения быстродействия местах программы делать вставки на ассемблере. Команды ассемблера напрямую транслируются в машинный код. Таким образом, в отличие от высокоуровневых языков при компиляции отсутствует проблема синхронизации и ряд других негативных обстоятельств.

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

    Особо следует отметить, что рекомендации 3 и 4 применяются не только для языков высокого уровня, но и для ассемблера. Помимо вышеуказанных для увеличения быстродействия программ написанных на ассемблере, в том числе и вставок, существуют следующие рекомендации [3]:

    1. Замещение универсальных инструкций на учитывающие конкретную ситуацию, например, замена умножения на степень двойки на команды сдвига (отказ от универсальности).
    2. Уменьшение количества передач управления в программе: за счет преобразования подпрограмм в макрокоманды для непосредственного включения в машинный код; за счет преобразования условных переходов так, чтобы условие перехода оказывалось истинным значительно реже, чем условие для его отсутствия; перемещение условий общего характера к началу разветвленной последовательности переходов; преобразование вызовов, сразу за которыми следует возврат в программу, в переходы («сращивание хвостов» и «устранение рекурсивных хвостов») и т.д.
    3. Максимальное использование всех доступных регистров за счет хранения в них рабочих значений всякий раз, когда это возможно, чтобы минимизировать число обращений к памяти, упаковка множественных значений или флагов в регистры и устранение излишних продвижений стека (особенно на входах и выходах подпрограмм).
    4. Использование специфических для данного процессора инструкций, например, инструкции засылки в стек непосредственного значения, которая имеется в процессоре 80286 и более поздних. Другие примеры – двухсловные строковые инструкции, команды перемножения 32-разрядных чисел, деление 64-разрядного на 32-разрядное число и умножение на непосредственное значение, которые реализованы в процессорах 80386 и 80486. Программа должна, разумеется, вначале определить, с каким типом процессора она работает!

    Заключение.

    Методы оптимизации быстродействия, рассмотренные в этой статье, были выработаны и проверены не одним поколением программистов и уже стали классическими. В то же время информационные технологии, в частности технологии программирования, постоянно развиваются. Появляются новые технологии, старые – модернизируются или уходят в прошлое. Растёт производительность аппаратной части ЭВМ и параллельно с этим растёт сложность и ресурсоёмкость выполняемых ими задач.

    Поэтому вопрос оптимизации быстродействия сейчас актуален также как и много лет назад. Более того он будет также актуален и в будущем.

    Список литературы и источников.

    1. Быстро и легко. Сборка, диагностика, оптимизация и апгрейд современного компьютера/ под ред. Печникова В.Н. Учебное пособие – М.: Лучшие книги, 2005;
    2. Бакнелл Д. Фундаментальные алгоритмы и структуры данных в Delphi. М.: ООО «ДиаСофтЮП»; СПб.: Питер, 2006;
    3. Дункан Р. Оптимизация программ на ассемблере./ Дункан Р.//PC Magazine/Russian Edition №1/1992;
    4. Список пропускных способностей интерфейсов передачи данных;
    5. Гапанович А. Как сделать свою программу быстрой./Компьютерра Online.

    Использование языка Ассемблера для оптимизации программ

    В случае использования мощного ПК вы наверняка обнаружили, что после уменьшения числа спрайтов до 200 темп вывода кадров (FPS) достигает величины кадровой развертки (70 Гц).

    Если этот результат получен для программы, которую не предполагается запускать на слабых машинах, то ее оптимизацию следует считать законченной и можно сформулировать такой постулат: «При отображении картинки на экран не следует стремиться к частоте вывода кадров, большей частоты кадровой развертки». Но с одной стороны, игра — это не только отображение спрайтов на экран. При ее создании необходимо предусмотреть использование части вычислительной мощи процессора также на физическую модель и логику взаимодействия объектов. С другой стороны, разрешение 320x200 точек было характерно для ПК моделей 286 и 386 с тактовой частотой 8—40 МГц, но сейчас более адекватным следует считать разрешение 800x600 или 1024x768 точек. Однако с таким разрешением мы работать не будем, так как использовать в этом случае Борланд Паскаль довольно неудобно из-за сегментированной модели памяти реального режима. При высоком экранном разрешении целесообразно выбрать защищенный режим, к чему мы еще вернемся в последних статьях цикла, а пока продолжим работу с разрешением 320x200 точек.

    Прежде всего, следует сказать, что язык Ассемблера не очень подходит для написания крупных программ. При использовании языка высокого уровня ПО получается компактнее, понятнее и содержит меньше ошибок, поэтому целесообразно переписать на языке Ассемблера лишь некоторые критичные по времени исполнения фрагменты. Какова их доля? Предполагается, что она колеблется от 1—5 до 10—15% от общей длины текста. При выборе этих фрагментов следует придерживаться второго правила, гласящего: «В оптимизации нуждается только тот фрагмент программного текста, который занимает значительную долю времени выполнения». Как найти такие фрагменты? Это можно сделать несколькими способами: с помощью профайлера, путем проведения анализа вложенности циклов, последовательно отключая модули и наблюдая, как это скажется на времени выполнения программы. Работу с профайлером мы рассматривать не будем, а воспользуемся двумя другими методами, тем более что они прекрасно дополняют друг друга. С одной стороны, оценка на основе анализа текста может дать лишь рекомендации, которые нужно проверить, а с другой, далеко не все модули можно отключить без потери работоспособности программы.

    Итак, начнем с анализа. Оценим, какие части программы выполняются чаще всего, — возможно, ими окажутся циклы с наибольшей вложенностью. Например, в нашей программе есть основной игровой цикл, выполняемый при отрисовке каждого кадра. Значит, все, что лежит за его пределами, можно не рассматривать. А внутри самого цикла вложений не так уж и много: вывод в буфер фона спрайтов и текста, а также переброска данных из буфера на экран и их синхронизация. В первую очередь наиболее глубокий цикл существует при выводе спрайта: внутри основного игрового выполняется цикл по спрайтам, а внутри него — вложенный цикл вывода точек по горизонтали и вертикали. Если иметь 200 спрайтов размером 20x20 точек, то можно получить 80 тыс. повторений на каждый кадр основного игрового цикла. Во вторую очередь идет вывод текста: отображение строки происходит посимвольно, а для показа символа опять же используется вложенный цикл. Таким образом, вложенность здесь такая же, как и при выводе спрайтов, только сами циклы короче, поэтому при 10—30 символах размером 8x8 точек цикл повторяется 700—2000 раз. Казалось бы, не так уж много, но современные суперскалярные процессоры, способные выполнять несколько команд за один такт, очень плохо переносят вызовы процедур, поэтому следует запомнить еще одно правило: «Не нужно размещать вызов процедуры или функции во вложенном цикле, а лучше перенести внутрь цикла фрагмент программного текста из процедуры». Иногда это может дать выигрыш в несколько раз. Мы не будем сейчас следовать этому принципу, а лучше минимизируем количество выводимого в кадре текста — тогда о его оптимизации можно не заботиться.

    Теперь все рассмотрено, и список циклов глубокой вложенности исчерпан. Однако при переброске фона в буфер или изображения на экран приходится последовательно копировать 64 000 точек. Это также цикл, хотя он и скрыт внутри процедуры move. Значит, анализ привел нас к необходимости минимизировать количество выводимого текста, для чего мы уберем с экрана слова «Демонстрационная программа» и оптимизируем процедуры BackBufferToScreen, PutSprite, ScreenBufferToScreen.

    Переходим к следующему этапу: отключим «ненужные» процедуры. В основном игровом цикле оставим только вызов процедур PutText и ScreenBufferToScreen (иначе мы не увидим на экране величины FPS), а все остальное временно «закомментируем». Запустим урезанную программу и запомним для дальнейшего сравнения величину FPS.

    Сначала перепишем Screen BufferToScreen на языке Ассемблера (листинг 1). Здесь воспользуемся командой rep movsX (где X может быть b, w или d — при этом соответственно команда за один раз копирует по одному, два или четыре байта). Она служит для копирования одной области памяти в другую. Процедура move использует команду rep movsb. Копировать по 4 байта за один раз могут только процессоры, начиная с 386-го, о которых Борланд Паскаль ничего не знает. Команда rep movsd на встроенном Ассемблере Борланд Паскаля будет выглядеть так: db $66 rep movsw. Еще одна тонкость, связанная с использованием языка Ассемблера в Борланд Паскале: все статические переменные хранятся в сегменте данных, адресуемом через регистр ds. Поэтому, если необходимо переопределить последний, то его содержимое следует запомнить, а затем восстановить. Кроме того, изменение ds следует провести как можно позже, ведь после нее обращение к статическим переменным программы будет уже невозможным.

    Затем восстановим переброску фона, вновь запустим программу и запомним FPS. Аналогично перепишем BackBufferToScreen и снова измерим FPS. Если в вашем ПК установлен современный процессор (Pentium II, Celeron и выше), то вас ждет разочарование, — практически ничего не изменится. Это связано с влиянием кэш-памяти, в которую целиком помещаются оба буфера. Как только мы подключим вывод спрайтов, кэш-память переполнится, и наше усовершенствование не будет незамеченным.

    Далее приступим к оптимизации PutSprite. Измерим FPS до и после изменений, показанных в листинге 1. Приведенный вариант, конечно, не идеален. Например, при наличии процессора Celeron, Pentium II или Pentium III замена loop @l2 на последовательность команд

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

    Если в ПК установлен быстрый процессор (обеспечивающий FPS > 140), спрайты через некоторое время могут остановиться. Это связано с тем, что вычисленная величина приращения координат стала меньше 1/2 и была округлена до 0. Восстановите кадровую синхронизацию — оптимизация закончена!

    Есть способ добиться правильного движения спрайтов и при высоких FPS: перейти от целых координат к дробным. Этот же подход позволит обеспечить и различную скорость движения разных спрайтов. Кстати, «дробные» не обязательно означают «с плавающей точкой». Можно воспользоваться и представлением чисел с фиксированной точкой. Таких чисел стандартного типа нет, но их легко получить из целых. Например, мы знаем, что диапазон изменения координат не превышает 0—320 и для его показа достаточно 9-разрядных чисел (или 10-разрядных, если число со знаком). Давайте считать, что единица соответствует 1/64 размера пиксела, тогда старшие 10 разрядов будут представлять целую часть координаты на экране, а младшие 6 — дробную. Чтобы перейти от целых чисел к числам с фиксированной точкой, достаточно при определении координат и приращений умножить числа на 64, а при использовании — разделить их на 64. Изменения в модуле Sprites и в основной программе даны в листинге 2. Вместо деления или умножения на число, являющееся степенью два, можно применить сдвиг, что будет более быстрой операцией.

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

    Elit-Knigi.ru

    Привет, Гость

    Правообладателям
    Для удаления авторских файлов, пишите по адреcу: abuse@elit-knigi.ru

    

    Самые активные релизы за неделю

    Магда Ю.С. - Ассемблер. Разработка и оптимизация Windows-приложений (+исх.)

    Скачать Magnet-ссылка (альтернативная ссылка для скачивания файла)
    Теги руководство, 2003
    Описание

    Ассемблер. Разработка и оптимизация Windows-приложений (+исх.)

    Автор: Магда Ю.С.
    Жанр: Руководство
    Издательство: БХВ-Петербург
    ISBN: 5-94157-324-3
    Язык: Русский
    Формат: DjVu
    Качество: Отсканированные страницы
    Количество страниц: 546
    Описание: Книга "Ассемблер. Разработка и оптимизация Windows-приложений" является подробным руководством по программированию на ассемблере в операционной среде Windows. При этом автор рассматривает применение ассемблера в двух аспектах: в качестве самостоятельного средства разработки полнофункциональных Windows-приложений и как встроенного инструмента в составе языков высокого уровня.
    Книга будет полезна программистам, как работающим с языками высокого уровня, так и пишущим на ассемблере.
    Подробно раскрывая все возможности ассемблера как языка программирования автор особое внимание уделил и возможной оптимизации программ на языках высокого уровня при использовании вставок и модулей, разработанных на ассемблере. Для демонстрации этого выбраны наиболее популярные средства разработки — Microsoft Visual С++.NET и Borland Delphi 7. Материал книги включает много примеров с анализом программного кода. Все примеры программ работоспособны и построены так, чтобы их можно легко адаптировать или модифицировать для дальнейшего использования.
    При печатном издании книги к ней прилагался компакт диск с записанными исходными текстами программ (содержимое такого компакт-диска приведено в файле source). Примеры размещены в каталогах CHAPTER_2 - CHAPTER_6. Помимо исходных текстов, каталоги, относящиеся к главе 3 и 6, содержат файлы проектов для MS Visual C++.NET и Delphi 7. В каждом таком каталоге имеется текстовый файл, в котором приводится описание содержимого каталога.

    Введение
    Структура книги
    Глава 1. Разработка высокоэффективного программного кода
    1.1. Оптимизация алгоритма разрабатываемой программы
    1.2. Оптимизация с учетом аппаратных средств компьютера
    1.3. Оптимизация с использованием средств языка высокого уровня
    1.4. Оптимизация с использованием языка низкого уровня ассемблера
    1.5. Оптимизация с учетом специфических особенностей процессора
    1.6. Ассемблер и оптимизация программ в деталях
    1.7. Использование ассемблера для разработки Windows-приложений
    Глава 2. Основы программирования на языке ассемблера
    2.1. Использование процедур в языке ассемблера
    2.2. Реализация математических вычислений на языке ассемблера
    2.3. Обработка строк и массивов данных
    Глава 3. Интерфейс с языками высокого уровня
    3.1. Конструкции высокого уровня на языке ассемблера
    3.2. Общие принципы построения интерфейсов с языками высокого уровня
    3.3. Использование процедур на ассемблере в языках высокого уровня
    3.4. Сравнительный анализ программного кода на ассемблере и С++
    Глава 4. Программирование приложений в Windows на языке ассемблера: первые шаги
    Глава 5. Программирование на ассемблере в Windows:от простого к сложному
    5.1. Графический интерфейс Windows
    5.2. Вывод текста на экран: дополнительные возможности
    5.3. Работа со шрифтами
    5.4. Рисование геометрических фигур
    5.5. Обработка сообщений мыши
    5.6. Ввод данных с клавиатуры
    5.7. Элементы управления Windows и их применение в программах на ассемблере
    5.8. Использование элементов управления
    5.9. Диалоговые окна и их использование
    5.10. Применение библиотек динамической компоновки (DLL)
    Глава 6. Встроенный ассемблер языков высокого уровня: принципы использования
    6.1. Применение встроенного ассемблера Delphi 7
    6.2. Директивы встроенного ассемблера
    6.3. Выражения во встроенном ассемблере
    6.4. Использование меток во встроенном ассемблере
    6.5. Примеры использования встроенного ассемблера в Delphi-приложениях
    6.6. Ассемблерные процедуры в Delphi 7
    6.7. Обработка строк во встроенном ассемблере
    6.8. Применение встроенного ассемблера в Microsoft Visual С++ .NET
    Заключение
    Приложение 1. Инструкции процессоров 80x86
    Приложение 2. Описание CD
    Список литературы
    Предметный указатель

    42. Оптимизация по быстродействию в Ассемблер

    42. Оптимизация по быстродействию в Ассемблер

    Приведем некоторые из самых общих процедур этой категории.

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

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

    2. Оптимизация циклов, в том числе сдвиг вычислений неизменяющихся величин за границы циклов, разворачивание циклов и «соединение» отдельных циклов, выполняемых одно и то же количество раз, в единый цикл («сжатие цикла»).

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

    4. Применение специфических для этого процессора инструкций, например, инструкции засылки в стек прямого значения или умножения числа на непосредственный операнд, имеющийся в процессорах 80186, 80188, 80286, 80386 и 80486. Также примером могут быть двухсловные строковые инструкции, команды перемножения 32-разрядных чисел и деления 64-разрядного на 32-разрядное число, которые проводятся в процессорах 80386 и 80486. Программа должна, конечно, первоначально определять, с каким типом процессора она работает.

    В процессорах 80 x 86, но не 80 x 88, возможно, удастся повысить скорость действия программы на несколько процентов в результате выравнивания расположения данных и меток, на которые осуществляется передача управления, относительно определенных границ.

    Процессоры 8088 и 80188 имеют 8-разрядную шину, и для них не имеет значения, на какую границу выровнены данные, поэтому выравнивание можно не применять или установить на границу байта (1 байт, 8 бит); процессоры 8086, 80186 и 80286 обладают 16-разрядной шиной, и им проще действовать с данными, выровненными на границу слова (2 байта, 16 бит); процессор 80386, для которого свойственна 32-разрядная шина, использует выравнивание на границу двойного слова (4 байта, 32 бита); из-за особенностей своей внутренней кэш-памяти процессору 80486, тоже с 32-разрядной шиной, проще работать, если осуществляется выравнивание на границу параграфа (16 байт, 96 бит).

    Понравилась статья? Поделиться с друзьями:
    Кодинг, CSS и SQL