X Международная студенческая научная конференция Студенческий научный форум - 2018

ВВЕДЕНИЕ

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

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

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

Архитектурный дизайн системы особенно сильно влияет на её производительность. Однако выбор алгоритма влияет на эффективность больше, чем любой другой элемент дизайна. Более сложные алгоритмы и структуры данных могут хорошо оперировать с большим количеством элементов, в то время как простые алгоритмы подходят для небольших объёмов данных – накладные расходы на инициализацию более сложного алгоритма могут перевесить выгоду от его использования [1, c.5].

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

Цель данной работы – изучить теоретические основы оптимизации программного кода.

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

Рассмотреть термин «оптимизация кода» и связанные с ним понятия.

Изучить виды и подход к оптимизации кода.

Познакомиться с методиками оптимизации кода.

ТЕРМИН «ОПТИМИЗАЦИЯ КОДА» И СВЯЗАННЫЕ С НИМ ПОНЯТИЯ

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

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

Кроме того, не существует универсального решения, которое подходило бы ко всем случаям, поэтому приходится использовать альтернативные решения, для оптимизации только ключевых параметров. Как правило, необходимые ресурсы для достижения требуемого результата, то есть получения полностью оптимальной программы, которую невозможно дальше улучшить, превышают выгоду, которую можно получить, затрачивая эти ресурсы. Именно поэтому оптимальные программы не создают просто потому, что некоторый процесс оптимизации может закончиться раньше. Как показывает практика, в большинстве случаев даже при этом достигаются значительные улучшения [2, c.153].

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

Каждый этап от проектирования до оптимизации кода допускает существенное повышение производительности программного обеспечения [3, c. 576].

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

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

Оптимизация в основном фокусируется на одиночном или повторном времени выполнения, использовании памяти, дискового пространства, пропускной способности или некотором другом ресурсе. Это обычно требует компромиссов (tradeoff) – один параметр оптимизируется за счёт других. Например, увеличение размера программного кэша чего-либо улучшает производительность времени выполнения, но также увеличивает потребление памяти. Другие распространённые компромиссы включают прозрачность кода и его выразительность, почти всегда ценой деоптимизации. Сложные специализированные алгоритмы требуют больше усилий по отладке и увеличивают вероятность ошибок.

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

ВИДЫ ОПТИМИЗАЦИИ ПРОГРАММНОГО КОДА

Оптимизация кода может проводиться, как и вручную, программистом, так и автоматизировано. В последнем случае оптимизатор может быть, как отдельным программным средством, так и быть встроенным в компилятор [4, c.3].

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

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

При оптимизации кода вручную существует проблема: нужно знать не только, каким образом проводить оптимизацию, но и в каком месте её применить. Обычно из-за разных факторов (медленные операции ввода, разница в скорости работы человека-оператора и машины и т.д.) лишь 10% кода занимают целых 90% времени выполнения. Так как на оптимизацию придется расходовать дополнительное время, то вместо попыток оптимизации всей программы лучше будет оптимизировать эти "критичные" ко времени выполнения 10%. Такой фрагмент кода называют узким местом или «бутылочным горлышком» (bottleneck), и для его определения используют специальные программы - профайлеры, которые позволяют замерять время работы различных частей программы [4, c.5].

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

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

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

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

• До создания полностью работоспособной программы найти узкие места в коде почти невозможно. Очень трудно догадаться, на какой участок кода приходится 50% времени выполнения, поэтому, оптимизируя код по мере написания, тратиться много времени на оптимизацию кода, который не нуждается в ней. А на оптимизацию по-настоящему важных участков времени не остается.

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

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

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

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

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

ПОДХОД К ОПТИМИЗАЦИИ ПРОГРАММНОГО КОДА

Рассматривая целесообразность оптимизации кода, надо придерживаться следующего алгоритма [3, c.591]:

Написать хороший и понятный код, поддающийся легкому изменению

Если производительность не устраивает:

Сохранить работоспособную версию кода, чтобы позднее можно было вернуться к «последнему нормальному состоянию»

Оценить производительность системы с целью нахождения горячих точек

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

Оптимизировать узкое место, определенное на этапе (с)

Оценить каждое улучшение.

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

Повторить процесс, начиная с п.2.

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

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

МЕТОДИКИ ОПТИМИЗАЦИИ КОДА

Не существует настолько общих методик, что бы можно было их применить для каждого кода. Однако ряд видов оптимизации кода можно, приспособить к конкретной задаче [6, c.79].

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

4.1 Логические выражения

Рассмотрим эффективное использование логических выражений.

• Прекращение проверки сразу же после получения ответа

Например, выражение

if ( 5 < y && y < z )

Если y окажется меньше 5, то вторую проверку выполнять не нужно.

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

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

if ( 5 < y ) {

if ( y < z ) ... }

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

evenNumber = false;

for (int i=0; i< count; i++){

if ((input[i] % 2) ==0){

evenNumber = true;}

}

Этот способ не оптимален. Лучше было бы прекращать проверку после обнаружения первого четного числа.

Пример оптимизированного кода представлен в таблице 4.1:

Таблица – 4.1 Оптимизированный цикл, выполняющий поиск числа

	Пример 1	Пример 2
Код	evenNumber = false; for (int i=0; i< count; i++) { if ((input[i] % 2) ==0) { evenNumber = true; break; } }	evenNumber = false; int i=0; while ((i < count) && (evenNumber ==false)) { if ((input[i] % 2)==0) { i++; evenNumber = true; } }

• Упорядочение проверок по частоте

Для повышения производительности рекомендуется размещать ветви, вероятность выбора которых является наибольшей, ближе к началу. В том случае будет меньше тратиться времени выбор требуемого варианта. Этот принцип относится к блокам case и цепочкам оператора if [3, c.596].

• Сравнение быстродействия похожих структур логики

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

• Замена сложных выражений на обращение к таблице

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

Пример оптимизированного кода представлен в таблице 4.2:

Таблица – 4.2 Обращение к таблице

	Исходный код	Определение таблицы AnswerTable
Код	if ( ( a && !c ) || ( a && b && c ) ) { answer = 1; } else if ( ( b && !a ) || ( a && c && !b ) ) { answer = 2; } else if ( c && !a && !b ) { answer = 3; } else { answer = 0; }	static int AnswerTable[ 2 ][ 2 ][ 2 ] = { // !b!c !bc b!c bc 0, 3, 2, 2, // !a 1, 2, 1, 1 // a }; ... answer = AnswerTable[ a ][ b ][ c ];

4.2 Использование выражение

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

• Алгебраические тождества

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

not a and not b

not (a or b)

Выбор второго выражение вместо первого, экономит одну операцию not [7, c 34].

Избавление от одной операции not, не приведет к заметным результатам, но тем не менее этот принцип значительно полезен. Джон Бентли отмечает, что в одной программе проверялось условие sqrt(x) < sqrt(y) (Bentley, 1982). Так как sqrt(x) меньше sqrt(y), только когда x меньше, чем y, исходную проверку можно заменить на x < y. С учетом дороговизны метода sqrt(), можно сказать, что достигнута существенная экономии.

• Снижение стоимости операции

Как уже было сказано, снижение стоимости операций подразумевает замену дорогой операции более дешевой. Вот некоторые возможные варианты:

замена умножения сложением;

замена возведения в степень умножением;

замена тригонометрических функций их эквивалентами;

замена типа long long на long или int (следите при этом за аспектами производительности, связанными с применением целых чисел естественной и неестественной длины);

замена чисел с плавающей запятой числами с фиксированной точкой или целые числа;

замена чисел с плавающей запятой с удвоенной точностью числами с одинарной точностью;

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

• Инициализация во время компиляции

Если при вызове метода, передается ему в качестве единственного аргумента именованная константа или непосредственное значение, лучше заранее вычислить нужное значение, присвоить его константе и избежать вызова метода. Это же справедливо и для других операций [3, c.618].

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

Таблица – 4.3 Инициализация во время компиляции

	Исходный код	Оптимизированный код
Код	static int Log2(int x) { return (int)(Math.Log(x) / Math.Log(2)); }	const double LOG2 = 0.69314718; static int Log2(int x) { return (int)(Math.Log(x) / LOG2); }
Время выполнения	9800 тактов	6500 тактов

• Недостатки системных методов

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

Пример метода, определяющего примерное значение двоичного логарифма с использованием оператора сдвига вправо:

unsigned int Log2( unsigned int x ) {

unsigned int i = 0;

while ( ( x = ( x >> 1 ) ) != 0 ) {

i++; }

return i ; }

• Использование констант корректного типа

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

Чуть ниже в таблице 4.4 указаны различия во времени инициализации переменных.

Таблица – 4.4 Использование констант корректного типа

	Исходный код	Оптимизированный код
Код	double x; int i; for (int j=0; j< 10000; j++) { x = (double)5; i = (int)3.14; }	double x; int i; for (int j=0; j< 10000; j++) { x = 3.14; i = 5; }
Время выполнения	80 тактов	63 тактов

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

Пример представлен в таблице 4.5.

Таблица – 4.5 Предварительное вычисление результатов

	Исходный код	Оптимизированный код
Код	int a=100; int b=11; double c= 12.2; double answer = a / (1 + (c / 12) - Math.Pow(1 + (c / 12), -b)) / (c / 12) * (28 - (c / 12));	int a=100; int b=11; double c= 5; double d = c / 12; double answer = a / (1 + d - Math.Pow(1 +d, -b)) / d * (28 - d);
Время выполнения	78 тактов	тактов

4.3 Циклы

Горячие точки часто следует искать именно внутри циклов, так как они выполняются многократно. Методики, описываемые ниже, помогут ускорить выполнение циклов [7, c.19].

• Размыкание цикла

Если во время выполнения цикла решение не изменяется, можно разомкнуть (unswitch) цикл, приняв решение вне цикла. Обычно для этого нужно вывернуть цикл наизнанку, то есть поместить циклы в условный оператор, а не условный оператор внутрь цикла. Замыканием (switching) цикла называют принятие решения внутри цикла при каждой его итерации [3, c.602].

Пример представлен в таблице 4.6.

Таблица – 4.6 Размыкание цикла

	Исходный код	Оптимизированный код
Код	for (int i = 0; i < 100000; i++) { if (sum == sumN) { a += array[i]; } else { b += array[i]; } }	if (sum == sumN) { for (int i = 0; i < 100000; i++) { a += array[i]; } } else { for (int i = 0; i < 100000; i++) { b += array[i]; } }
Время выполнения	1050 тактов	800 тактов

• Объединение циклов

Бывает так, что циклы работают с один набором элементов, тогда их можно объединить (jamming). Выгода заключается в устранении затрат, связанных с выполнением дополнительно цикла [3, c.603].

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

Пример представлен в таблице 4.7 размер массивов 10000.

Таблица – 4.7 Объединение циклов

	Исходный код	Оптимизированный код	Неправильно оптимизированный код
Код	for (int i = 0; i < a.Length; i++) { a[i] = i; } for (int i = 0; i < a.Length; i++) { b[i] = i; }	for (int i = 0; i < a.Length; i++) { a[i] = i; b[i] = i; }	for (int i = 0; i < a.Length; i++) { a[i] = i; for (int j = 0; j < a.Length; j++) { b[j] = j; } }
Время выполнения	167 тактов	99 тактов	864494 тактов

• Развертывание цикла

Целью развертывания (unrolling) цикла является сокращение затрат, связанных с его выполнением.

Пример представлен в таблице 4.8 размер массива 10000.

Таблица – 4.8 Развертывание цикла

	Исходный код	Оптимизированный код
Код	for (int i=0; i

Код для цитирования: Скопировать