Тонкости оптимизации. Кратко для новичков
Ранее на страницах Компьютерной газеты (см. КГ № 30 от 9 августа 2010 г.) появилось сообщение о том, что независимая группа специалистов в сфере информационных технологий SASecurity gr. проводит эксперимент «Тонкости оптимизации».
Темы, затрагиваемые этим экспериментом, довольно сложны для понимания даже многих опытных программистов. Поэтому, прежде чем поделиться с читателями полученными результатами, хотелось бы сделать реверанс в сторону тех из них, кто, возможно, не обладает достаточной подготовкой для понимания сути и результатов эксперимента, но хотели бы немного разобраться в происходящем.
Рассматривать все требуемые вопросы будем на основе документации по процессорам фирмы Intel. Следует понимать, что все процессоры устроены сходным образом, по крайней мере, если речь идет о процессорах, работающих внутри персональных компьютеров.
Рассказ будет предельно упрощенным и ни в коем случае не претендует на полноту изложения.
Что такое программирование?
Любая компьютерная программа представляет собой описание действий и порядка их выполнения, позволяющих программе решать поставленные перед ней задачи: ввод исходных данных, их хранение, перемещение и обработку, а также вывод результатов этой обработки.
Для написания программ были придуманы десятки различных языков программирования (ЯП). Наиболее простыми и широко используемыми являются ЯП высокого уровня (ЯВУ). Записанная на ЯВУ программа представляет собой текст, оформленный по правилам этого языка. Для выполнения такой программы требуется представить ее в формате, понятном для процессора: в виде набора чисел (байтов), которые обозначают те или иные элементарные операции. Одной команде ЯВУ, как правило, соответствует несколько (а иногда и очень много) элементарных операций. Эти операции еще называются словосочетанием «инструкции процессора».
При запуске программы упомянутые наборы чисел загружаются в оперативную память по определенному адресу. После этого процессор начинает выполнение закодированных числами команд. То, какая команда будет выполняться следующей, определяется содержимым специального регистра (ячейки) процессора, хранящего адрес этой команды. В простейшем случае после считывания очередной команды из памяти адрес в этом регистре изменяется так, чтобы быть равным адресу следующей команды.
Ветвления
Если ограничить процесс выполнения программы только упомянутым в предыдущем абзаце способом обработки команд, то окажется невозможным написание программы, выполняющей какие-либо разумные действия. На самом деле, если присмотреться как следует, можно заметить, что любая настоящая программа ведет себя по-разному в зависимости от получаемых ею входных данных.
Другими словами, нам нужно в зависимости от каких-либо условий выполнять те или иные последовательности операций. Для этого нам потребуются 2 возможности: проверки условия на истинность и изменения значения в адресном регистре процессора. Действительно, если мы сможем изменить содержимое этого регистра, следующая команда будет считываться начиная с другого адреса. Соответственно, связав изменение адреса с результатом проверки условия, мы можем получить возможность свободно перемещаться по программе, выполняя лишь те действия, которые нам нужны для конкретного набора входных данных. Такая возможность реализуется в процессорах как элементарная операция – инструкция условного перехода.
Как частный случай отметим возможность изменения адресного регистра независимо от каких бы то ни было условий. В этом случае переход называется безусловным и для него также предусмотрена специальная инструкция.
Циклы
Нередко требуется повторить выполнение одной или нескольких инструкций многократно. Понятно, что можно просто записать эти инструкции столько раз, сколько повторений требуется для работы программы. Но, во-первых, каждая инструкция требует для себя места в памяти, то есть программа может серьезно увеличиться в размерах, а во-вторых, не всегда точное количество повторений известно во время написания программы: часто оно определяется в момент ее выполнения.
Имея возможность осуществлять переход по произвольному адресу внутри программы, мы можем после последней инструкции из повторяющегося фрагмента записать команду перехода к первой инструкции этого фрагмента. В этом случае одна или несколько инструкций будут выполняться многократно – получим так называемый цикл. Инструкции, которые многократно выполняются в цикле, называют телом цикла.
Изменяя условие, по которому происходит возврат к началу тела цикла, мы можем варьировать количество повторений, то есть достигаем нашей цели. Главное, о чем следует помнить: в правильно написанной программе любой цикл когда-нибудь должен завершиться.
В большинстве Windows-программ присутствует цикл, который является «сердцем» программы – цикл обработки сообщений. При наступлении каких-либо событий, которые могут быть интересны программе, операционная система отправляет ей соответствующие сообщения. Работа программы при этом сводится к постоянному повторению следующей последовательности действий:
1. Дождаться поступления сообщения.
2. Получить информацию о сообщении.
3. Выполнить соответствующие сообщению действия (обработать сообщение).
4. Перейти к шагу 1.
Выход из цикла обработки сообщений происходит (в общем случае) при получении специального сообщения.
Подпрограммы
Любая сложная задача может быть разбита на более мелкие, так называемые подзадачи. Например, вывод числа на экран можно представить в виде такого набора подзадач:
1. Преобразование числового значения в набор символов.
2. Подготовка к отображению информации.
3. Загрузка изображения для каждого из символов и его вывод.
Приведенные в примере подзадачи, в свою очередь, могут быть разбиты на еще более мелкие подзадачи. Это разбиение продолжается до тех пор, пока не удастся представить все подзадачи через элементарные операции.
Некоторые подзадачи, получаемые при таком разбиении, оказываются удобными для использования в качестве составных частей других задач. Например, подзадача 3 в приведенном примере может быть полезна при выводе не только числа, но и вообще произвольного текста. Удобно было бы написать решение такой подзадачи однажды, а затем использовать его уже готовым каждый раз, когда это необходимо. В этом и заключается процесс создания подпрограммы, или процедуры.
Итак, у нас есть фрагмент кода, решающий некоторую подзадачу, – процедура. Мы хотим использовать этот фрагмент как часть решения некоторой большой задачи. В этом случае в какой-то момент мы просто изменяем содержимое адресного регистра процессора так, чтобы выполнение продолжилось с первой инструкции подпрограммы. Но! После того как процедура выполнена, мы должны вернуться к месту, откуда она была вызвана. А таких мест в программе может быть много.
Именно поэтому перед тем, как передать управление подпрограмме, мы должны сохранить адрес той инструкции, с которой следует продолжить выполнение по возвращении из подпрограммы. А подпрограмма, соответственно, должна завершать свое выполнение, помещая ранее сохраненное значение в адресный регистр.
Оптимизация
Под оптимизацией чаще всего понимают процесс изменения программы или ее отдельных частей таким образом, чтобы они, выполняя те же самые действия, потребляли меньшее количество ресурсов компьютера. Как правило, рассматриваются 2 таких ресурса: время процессора и память. Соответственно, наиболее часто программы оптимизируют по потреблению памяти и по скорости выполнения (по количеству потребляемого процессорного времени).
Вернемся к вызову подпрограмм. Обратите внимание: для того чтобы корректно продолжить выполнения основной программы после решения подзадачи, нам приходится сохранять адрес возврата, то есть использовать дополнительную память. Более того, операции сохранения этого адреса и считывания сохраненного значения требуют дополнительных затрат времени. Как, впрочем, и 2 перехода: при вызове подпрограммы и при возврате из нее, – которых не было бы, если бы мы записали ее код подпрограммы прямо внутри основной программы, то есть обошлись бы без вызова.
Очевидное решение – отказ от использования подпрограмм. Не очень удобно, но зато эффективно. Но! При этом вероятность допущения ошибок программистом резко возрастает, поскольку тогда ему приходится иметь дело с большими объемами разношерстного кода.
К счастью, разработчики процессоров не остались в стороне от этой проблемы. В современных процессорах на аппаратном уровне используются самые разнообразные приемы для ускорения всех видов операций.
Конвейерная обработка
На самом деле, говоря, что за инструкциями процессора стоят элементарные операции, я немного приврал. Дело в том, что выполнение любой инструкции процессором – это тоже весьма сложный процесс: нужно не просто считать код инструкции из памяти, но и привести в действие соответствующие узлы, входящие в состав процессора.
Выполнение одной инструкции состоит условно из таких этапов: считывание инструкции из памяти, декодирование инструкции (анализ ее кода и подготовка к работе соответствующих узлов), считывание операндов (тех данных, над которыми выполняется операция), выполнение операции, запись результата. Список, разумеется, приближенный.
Идея оптимизации до смешного проста. Над разными этапами выполнения инструкции «трудятся» различные узлы процессора. Поэтому в «классическом» случае получается, что во время, например, выполнения инструкции узел, отвечающий за декодирование, простаивает. А что если не ждать, пока инструкция пройдет через все этапы, а начинать расшифровку следующей инструкции, как только освободится декодирующий узел?
Аналогично поступаем и со всеми остальными этапами обработки инструкции. Получается своеобразный конвейер: пока один рабочий работает над очередной деталью, другой уже готовит следующую. Эффективность такого подхода доказал в свое время на практике еще дядюшка Генри Форд :-). В этом, собственно говоря, и заключается конвейерная обработка инструкций.
Кэширование
Еще один аппаратно реализуемый способ ускорить процесс выполнения программ. Вспомните: перед тем как начнется непосредственно выполнение инструкции, процессор должен загрузить ее из оперативной памяти. То же самое происходит и с обрабатываемыми данными. Оперативная память (оперативное запоминающее устройство, ОЗУ) – отдельное устройство, взаимодействие с которым намного медленнее, чем взаимодействие, например, с регистрами процессора, которые являются частью самого процессора.
Для того чтобы сэкономить время на доступе к оперативной памяти, используется кэширование. Суть этого метода заключается в следующем: между процессором и ОЗУ (а фактически – в самом процессоре) размещается так называемая кэш-память. Она работает намного быстрее, чем ОЗУ, но имеет значительно меньший объем. Когда при обработке очередной инструкции выясняется, что требуется обратиться к какой-либо ячейке ОЗУ, может возникнуть одна из двух ситуаций:
1. Данные из этого участка оперативной памяти уже есть в кэше – доступ к ним происходит быстро.
2. Запрашиваемых данных в кэше нет – выполняется считывание данных из ОЗУ, то есть медленно.
В случае с программой, которая также хранится в памяти и подвергается считыванию, в кэш помещается обычно тот ее фрагмент, который вероятнее всего будет выполнен в ближайшее время. В простейшем случае – это команды, которые расположены последовательно, одна за другой. Тогда получается, что некоторое количество инструкций выполняется значительно быстрее, пока не потребуется выполнение инструкции, которой в кэше нет. В этот момент в кэш подгружается фрагмент, начинающийся со следующей инструкции, и выполнение программы снова продолжается с использованием кэшированной копии кода.
Предсказание переходов
Только что мы рассмотрели кратко кэширование кода программы. Теперь представьте себе: в какой-то момент мы совершаем условный или безусловный переход. Шансы, что инструкция, которой мы при этом передаем управление, находится в кэше, ничтожно малы. Значит, переходы замедляют выполнение программы.
Производители процессоров и здесь предусмотрели оптимизацию. Действительно, безусловный переход выполняется всегда, то есть во время выполнения этой инструкции мы уже знаем, какая инструкция будет выполняться следующей, а значит, можем загружать в кэш новый блок из оперативной памяти, начинающийся с инструкции, к которой мы совершаем переход.
С условными переходами все несколько сложнее и интереснее. Но рассмотрение этого вопроса я оставлю до следующего раза.
Промежуточные итоги
Таким образом, в этот раз мы кратко рассмотрели основные приемы оптимизации программ, применяемые разработчиками процессоров на аппаратном уровне. Искренне надеюсь, что у вас сложилось хотя бы общее представление о том, как это работает.
Если все же вопросы остались… Ну, во-первых, вы можете воспользоваться поиском в Интернете для того чтобы разобраться со всем тем, что оказалось непонятным. А во-вторых, вы можете написать мне по адресу q@sa-sec.org, и я постараюсь ответить на ваши вопросы.
Дмитрий Оношко
Темы, затрагиваемые этим экспериментом, довольно сложны для понимания даже многих опытных программистов. Поэтому, прежде чем поделиться с читателями полученными результатами, хотелось бы сделать реверанс в сторону тех из них, кто, возможно, не обладает достаточной подготовкой для понимания сути и результатов эксперимента, но хотели бы немного разобраться в происходящем.
Рассматривать все требуемые вопросы будем на основе документации по процессорам фирмы Intel. Следует понимать, что все процессоры устроены сходным образом, по крайней мере, если речь идет о процессорах, работающих внутри персональных компьютеров.
Рассказ будет предельно упрощенным и ни в коем случае не претендует на полноту изложения.
Что такое программирование?
Любая компьютерная программа представляет собой описание действий и порядка их выполнения, позволяющих программе решать поставленные перед ней задачи: ввод исходных данных, их хранение, перемещение и обработку, а также вывод результатов этой обработки.
Для написания программ были придуманы десятки различных языков программирования (ЯП). Наиболее простыми и широко используемыми являются ЯП высокого уровня (ЯВУ). Записанная на ЯВУ программа представляет собой текст, оформленный по правилам этого языка. Для выполнения такой программы требуется представить ее в формате, понятном для процессора: в виде набора чисел (байтов), которые обозначают те или иные элементарные операции. Одной команде ЯВУ, как правило, соответствует несколько (а иногда и очень много) элементарных операций. Эти операции еще называются словосочетанием «инструкции процессора».
При запуске программы упомянутые наборы чисел загружаются в оперативную память по определенному адресу. После этого процессор начинает выполнение закодированных числами команд. То, какая команда будет выполняться следующей, определяется содержимым специального регистра (ячейки) процессора, хранящего адрес этой команды. В простейшем случае после считывания очередной команды из памяти адрес в этом регистре изменяется так, чтобы быть равным адресу следующей команды.
Ветвления
Если ограничить процесс выполнения программы только упомянутым в предыдущем абзаце способом обработки команд, то окажется невозможным написание программы, выполняющей какие-либо разумные действия. На самом деле, если присмотреться как следует, можно заметить, что любая настоящая программа ведет себя по-разному в зависимости от получаемых ею входных данных.
Другими словами, нам нужно в зависимости от каких-либо условий выполнять те или иные последовательности операций. Для этого нам потребуются 2 возможности: проверки условия на истинность и изменения значения в адресном регистре процессора. Действительно, если мы сможем изменить содержимое этого регистра, следующая команда будет считываться начиная с другого адреса. Соответственно, связав изменение адреса с результатом проверки условия, мы можем получить возможность свободно перемещаться по программе, выполняя лишь те действия, которые нам нужны для конкретного набора входных данных. Такая возможность реализуется в процессорах как элементарная операция – инструкция условного перехода.
Как частный случай отметим возможность изменения адресного регистра независимо от каких бы то ни было условий. В этом случае переход называется безусловным и для него также предусмотрена специальная инструкция.
Циклы
Нередко требуется повторить выполнение одной или нескольких инструкций многократно. Понятно, что можно просто записать эти инструкции столько раз, сколько повторений требуется для работы программы. Но, во-первых, каждая инструкция требует для себя места в памяти, то есть программа может серьезно увеличиться в размерах, а во-вторых, не всегда точное количество повторений известно во время написания программы: часто оно определяется в момент ее выполнения.
Имея возможность осуществлять переход по произвольному адресу внутри программы, мы можем после последней инструкции из повторяющегося фрагмента записать команду перехода к первой инструкции этого фрагмента. В этом случае одна или несколько инструкций будут выполняться многократно – получим так называемый цикл. Инструкции, которые многократно выполняются в цикле, называют телом цикла.
Изменяя условие, по которому происходит возврат к началу тела цикла, мы можем варьировать количество повторений, то есть достигаем нашей цели. Главное, о чем следует помнить: в правильно написанной программе любой цикл когда-нибудь должен завершиться.
В большинстве Windows-программ присутствует цикл, который является «сердцем» программы – цикл обработки сообщений. При наступлении каких-либо событий, которые могут быть интересны программе, операционная система отправляет ей соответствующие сообщения. Работа программы при этом сводится к постоянному повторению следующей последовательности действий:
1. Дождаться поступления сообщения.
2. Получить информацию о сообщении.
3. Выполнить соответствующие сообщению действия (обработать сообщение).
4. Перейти к шагу 1.
Выход из цикла обработки сообщений происходит (в общем случае) при получении специального сообщения.
Подпрограммы
Любая сложная задача может быть разбита на более мелкие, так называемые подзадачи. Например, вывод числа на экран можно представить в виде такого набора подзадач:
1. Преобразование числового значения в набор символов.
2. Подготовка к отображению информации.
3. Загрузка изображения для каждого из символов и его вывод.
Приведенные в примере подзадачи, в свою очередь, могут быть разбиты на еще более мелкие подзадачи. Это разбиение продолжается до тех пор, пока не удастся представить все подзадачи через элементарные операции.
Некоторые подзадачи, получаемые при таком разбиении, оказываются удобными для использования в качестве составных частей других задач. Например, подзадача 3 в приведенном примере может быть полезна при выводе не только числа, но и вообще произвольного текста. Удобно было бы написать решение такой подзадачи однажды, а затем использовать его уже готовым каждый раз, когда это необходимо. В этом и заключается процесс создания подпрограммы, или процедуры.
Итак, у нас есть фрагмент кода, решающий некоторую подзадачу, – процедура. Мы хотим использовать этот фрагмент как часть решения некоторой большой задачи. В этом случае в какой-то момент мы просто изменяем содержимое адресного регистра процессора так, чтобы выполнение продолжилось с первой инструкции подпрограммы. Но! После того как процедура выполнена, мы должны вернуться к месту, откуда она была вызвана. А таких мест в программе может быть много.
Именно поэтому перед тем, как передать управление подпрограмме, мы должны сохранить адрес той инструкции, с которой следует продолжить выполнение по возвращении из подпрограммы. А подпрограмма, соответственно, должна завершать свое выполнение, помещая ранее сохраненное значение в адресный регистр.
Оптимизация
Под оптимизацией чаще всего понимают процесс изменения программы или ее отдельных частей таким образом, чтобы они, выполняя те же самые действия, потребляли меньшее количество ресурсов компьютера. Как правило, рассматриваются 2 таких ресурса: время процессора и память. Соответственно, наиболее часто программы оптимизируют по потреблению памяти и по скорости выполнения (по количеству потребляемого процессорного времени).
Вернемся к вызову подпрограмм. Обратите внимание: для того чтобы корректно продолжить выполнения основной программы после решения подзадачи, нам приходится сохранять адрес возврата, то есть использовать дополнительную память. Более того, операции сохранения этого адреса и считывания сохраненного значения требуют дополнительных затрат времени. Как, впрочем, и 2 перехода: при вызове подпрограммы и при возврате из нее, – которых не было бы, если бы мы записали ее код подпрограммы прямо внутри основной программы, то есть обошлись бы без вызова.
Очевидное решение – отказ от использования подпрограмм. Не очень удобно, но зато эффективно. Но! При этом вероятность допущения ошибок программистом резко возрастает, поскольку тогда ему приходится иметь дело с большими объемами разношерстного кода.
К счастью, разработчики процессоров не остались в стороне от этой проблемы. В современных процессорах на аппаратном уровне используются самые разнообразные приемы для ускорения всех видов операций.
Конвейерная обработка
На самом деле, говоря, что за инструкциями процессора стоят элементарные операции, я немного приврал. Дело в том, что выполнение любой инструкции процессором – это тоже весьма сложный процесс: нужно не просто считать код инструкции из памяти, но и привести в действие соответствующие узлы, входящие в состав процессора.
Выполнение одной инструкции состоит условно из таких этапов: считывание инструкции из памяти, декодирование инструкции (анализ ее кода и подготовка к работе соответствующих узлов), считывание операндов (тех данных, над которыми выполняется операция), выполнение операции, запись результата. Список, разумеется, приближенный.
Идея оптимизации до смешного проста. Над разными этапами выполнения инструкции «трудятся» различные узлы процессора. Поэтому в «классическом» случае получается, что во время, например, выполнения инструкции узел, отвечающий за декодирование, простаивает. А что если не ждать, пока инструкция пройдет через все этапы, а начинать расшифровку следующей инструкции, как только освободится декодирующий узел?
Аналогично поступаем и со всеми остальными этапами обработки инструкции. Получается своеобразный конвейер: пока один рабочий работает над очередной деталью, другой уже готовит следующую. Эффективность такого подхода доказал в свое время на практике еще дядюшка Генри Форд :-). В этом, собственно говоря, и заключается конвейерная обработка инструкций.
Кэширование
Еще один аппаратно реализуемый способ ускорить процесс выполнения программ. Вспомните: перед тем как начнется непосредственно выполнение инструкции, процессор должен загрузить ее из оперативной памяти. То же самое происходит и с обрабатываемыми данными. Оперативная память (оперативное запоминающее устройство, ОЗУ) – отдельное устройство, взаимодействие с которым намного медленнее, чем взаимодействие, например, с регистрами процессора, которые являются частью самого процессора.
Для того чтобы сэкономить время на доступе к оперативной памяти, используется кэширование. Суть этого метода заключается в следующем: между процессором и ОЗУ (а фактически – в самом процессоре) размещается так называемая кэш-память. Она работает намного быстрее, чем ОЗУ, но имеет значительно меньший объем. Когда при обработке очередной инструкции выясняется, что требуется обратиться к какой-либо ячейке ОЗУ, может возникнуть одна из двух ситуаций:
1. Данные из этого участка оперативной памяти уже есть в кэше – доступ к ним происходит быстро.
2. Запрашиваемых данных в кэше нет – выполняется считывание данных из ОЗУ, то есть медленно.
В случае с программой, которая также хранится в памяти и подвергается считыванию, в кэш помещается обычно тот ее фрагмент, который вероятнее всего будет выполнен в ближайшее время. В простейшем случае – это команды, которые расположены последовательно, одна за другой. Тогда получается, что некоторое количество инструкций выполняется значительно быстрее, пока не потребуется выполнение инструкции, которой в кэше нет. В этот момент в кэш подгружается фрагмент, начинающийся со следующей инструкции, и выполнение программы снова продолжается с использованием кэшированной копии кода.
Предсказание переходов
Только что мы рассмотрели кратко кэширование кода программы. Теперь представьте себе: в какой-то момент мы совершаем условный или безусловный переход. Шансы, что инструкция, которой мы при этом передаем управление, находится в кэше, ничтожно малы. Значит, переходы замедляют выполнение программы.
Производители процессоров и здесь предусмотрели оптимизацию. Действительно, безусловный переход выполняется всегда, то есть во время выполнения этой инструкции мы уже знаем, какая инструкция будет выполняться следующей, а значит, можем загружать в кэш новый блок из оперативной памяти, начинающийся с инструкции, к которой мы совершаем переход.
С условными переходами все несколько сложнее и интереснее. Но рассмотрение этого вопроса я оставлю до следующего раза.
Промежуточные итоги
Таким образом, в этот раз мы кратко рассмотрели основные приемы оптимизации программ, применяемые разработчиками процессоров на аппаратном уровне. Искренне надеюсь, что у вас сложилось хотя бы общее представление о том, как это работает.
Если все же вопросы остались… Ну, во-первых, вы можете воспользоваться поиском в Интернете для того чтобы разобраться со всем тем, что оказалось непонятным. А во-вторых, вы можете написать мне по адресу q@sa-sec.org, и я постараюсь ответить на ваши вопросы.
Дмитрий Оношко
Компьютерная газета. Статья была опубликована в номере 36 за 2010 год в рубрике программирование
