q-dex q-dex

Как оптимизировать программу?

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

Работа с данными

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

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

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

  1. //pascal
  2. Const n=10;
  3. I:integer;
  4. var buff, P:^integer;
  5. Begin
  6. GetMem(buff, n*2); //выделение памяти
  7. For i:=0 to n-1 do
  8. Begin
  9. P:=Ptr(LongInt(buff)+i); //адрес i-го элемента
  10. P^:=I; //заполнение
  11. End;
  12. Dispose(buff); //освобождение памяти
  13. End;
  1. //c++
  2. int *buff = new int[cnt]; // Выделение памяти для массива
  3. for (int i = 0; i < cnt; i++) {
  4. // Заполнение массива
  5. buff[i] = i;
  6. }
  7. delete [] buff; // очистка буфера

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

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

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

  1. //Pascal
  2. Type
  3. PStack=^TStack; //указатель
  4. TStack=record
  5. Data:integer;//данные
  6. Next:PStack;//ссылка на следующий элемент
  7. End;
  1. //c++
  2. struct List
  3. {
  4. int x; //данные
  5. List *Next; //ссылка на следующий элемент
  6. };

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

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

  1. //Pascal
  2. Type
  3. PTree=^TTree; //указатель
  4. TTree=record
  5. Data: integer;//данные
  6. Left, Right:PTree;//ссылка на следующий элемент
  7. End;
  1. //c++
  2. struct Tree
  3. {
  4. int x; //данные
  5. Tree *Left, *Right; //ссылка на следующий элемент
  6. };

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

Математика

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

В группу методов без потери точности отнесем: математические преобразования, использование таблиц значений и использование технических особенностей арифметико-логического устройства (АЛУ).

Каждая математическая операция требует времени на выполнение, а значит, уменьшив число таких операций, можно сократить время расчетов. Например, можно вынести общий множитель за скобки: a*x+a*y => a*(x+y); вместо двух умножений произведется только одно. Однако следует помнить, что разные операции затрачивают разное количество времени на выполнение. В зависимости от конкретного устройства это время может варьироваться. Однако есть и общие правила, зная которые можно приблизительной оценить эффективность преобразований:

  1. Умножение и деление всегда выполняется дольше, чем сложение, вычитание и сдвиги.
  2. Операции с плавающей точкой всегда выполняются дольше, чем целочисленные.
  3. Тригонометрические и логарифмические функции содержат в себе десятки операций сложения и умножения.

Учитывая эти правила можно, например, сделать вывод, что a+a работает быстрее, чем a*2, а 15.0*x медленнее, чем 15*x. Хотя умножение заменять сложением не всегда рационально, обычно это имеет смысл при умножении на 2, 3, 4 и 5, дальнейшее увеличение числа слагаемых, скорее всего, замедлит вашу программу. Допустимое количество сложений лучше узнать опытным путем, так как для разных АЛУ этот число будет отличаться.

Отдельно следует отметить операции сдвига. В языке PASCAL сдвиг влево X SHL N, сдвиг вправо X SHR N, в C++ сдвиг влево X << N, сдвиг вправо X >> N. Эти операции сдвигают цифры бинарной записи числа X на N разрядов влево (вправо). Например, для двоичного числа 1101 сдвиг влево на 1 равен 11010, а вправо 110. Интересны эти операции тем, что являются эквивалентом умножения (для сдвига влево) и деления (для сдвига вправо) на 2^N, а скорость их выполнения сопоставима со скоростью сложения. Так, например, вместо A*16 можно записать A shl 4, или вместо B div 32 - B shr 5.

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

  1. //pascal
  2. var SinAr: array [0..359] of Real;
  3. i:integer;
  4. begin
  5. for i:=0 to 359 do
  6. SinAr[i]:=Sin(i*pi/180);
  7. end.
  1. //c++
  2. float SinAr[360];
  3. int i;
  4. for (i=0; i<360; i++)
  5. SinAr[i]=sin(i*pi/180);

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

Что касается использования технических особенностей устройств, то тут надо отметить, что некоторая электроника (например, процессоры Intel и AMD) имеет набор инструкций значительно сокращающих время вычислений. К примеру, вместо того чтобы выполнять две операции деления и получения остатка от деления A:=X div 5; B:=X mod 5; можно воспользоваться одной инструкцией ассемблера IDIV (или DIV), которая сразу вернет и результат деления и остаток:

  1. MOV AX, X
  2. IDIV 5
  3. MOV A, AX
  4. MOV B, DX

Помимо этого процессоры Intel и AMD имеют наборы инструкций MMX, 3DNow! и SSE, которые позволяют выполнять одну математическую операцию сразу над группой чисел (вектором), что может ускорить выполнение в 3-4 раза. Детально разбирать эти наборы инструкций в рамках данной публикации мы не будем, приведем только пример скалярного умножения N-мерных векторов на языке PASCAL и аналогичную процедуру на ассэмблере с использованием MMX:

  1. const n = 50;
  2. type vec = array [1..n*4] of word;
  3. var a,b:vec;
  4. function vprod(const a, b: vec): dword;
  5. var
  6. i: Integer;
  7. R:dword;
  8. begin
  9. R := 0;
  10. for i := 1 to n*4 do
  11. R := R + a[i] * b[i];
  12. result:=R;
  13. end;
  14. function vprod_mmx (const a, b: vec): dword; assembler;
  15. var
  16. muls: record l, h: dword end;
  17. asm
  18. xor ebx, ebx
  19. mov ecx, n
  20. mov esi, a
  21. mov edi, b
  22. xor eax, eax
  23. @@l:
  24. movq mm0, [esi]
  25. pmaddwd mm0, [edi]
  26. lea esi, [esi+8]
  27. movq muls, mm0
  28. lea edi, [edi+8]
  29. add eax, muls.l
  30. add eax, muls.h
  31. dec ecx
  32. jne @@l
  33. emms
  34. end;

Касательно технических особенностей также хочется отметить разрядность АЛУ. Разрядность показывает какого объема данные могут быть обработаны за такт (исключения составляют команды MMX, 3DNow! и SSE). Соответственно если вы используете переменные, размер которых больше разрядности АЛУ, то это приведет к тому, что вместо одной операции сложения устройству придется выполнить большее количество действий. Например, если вы используете 8-и битный ATMega8 и складываете переменные типа WORD (16 бит), то чипу придется сначала сложить младшие 8 бит, затем старшие 8 бит, а затем прибавить к старшим бит переполнения, вместо одного действия потребовалось три. Следовательно, нужно выбирать переменные минимально возможного размера, это также позволит в некоторых случаях получить значительный прирост производительности. Помимо этого большинство современных процессоров и микроконтроллеров имеют вычислительные конвейеры, позволяющие выполнять несколько атомарных операций одновременно. Однако из-за операций ветвления или специфической последовательности команд могут возникнуть ступоры конвейера, что значительно замедлит выполнение программы. Современные компиляторы в большинстве своем оптимизируют код под архитектуру процессоров. Однако для тонкой оптимизации может быть полезным подробное изучение архитектуры и оптимизация кода под конкретный конвейер.

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

В том случае, когда выполнить сокращение по общим правилам не выходит, можно прибегнуть к усреднению. Рассмотрим пример: a/(x+2)+b/(x+4); слагаемые имеют разные делители, вынести их не получится. Однако можно взять среднее между двумя делителями: x+3; в результате получим (a+b)/(x+3). Стало меньше на одно сложение и одно деление, погрешности в таких случаях редко превышают 20%, а обычно бывают не более 5%.

Другим вариантом упрощения может быть замена числа с плавающей точкой числом с фиксированной точкой. Например, в переменной типа WORD старшие 8 бит можно отвести на целую часть, а младшие на дробную. Тогда вместо r:=2; будет w:=2 shl 8 (сдвигаем двойку в старшие 8 бит). Операция сложения не изменится, а умножение будет выглядеть следующим образом w:=w1*w2 shr 8. Получение целой части: i:=w shr 8; дробной: r:=(w mod 256)/256; переход от плавающей точки к фиксированной: w:=round(r*256); обратно: r:=w/256. Все вышесказанное можно применить и к 32-х битным числам, тогда можно использовать и 16 бит на дробную часть. Конечно, такой подход приведет к потере точности, но даст ощутимый прирост при работе с дробными числами.

Циклы

Как правило, действия внутри циклов выполняются большое количество раз и именно циклы значительно замедляют выполнение программ, поэтому грамотная оптимизация циклов очень важна. В первую очередь нужно понимать, что каждый раз после (или до) выполнения тела цикла запускается проверка условий, которая забирает на себя часть времени, а цикл for еще и увеличивает значение счетчика (еще одна лишняя операция). Поэтому очень полезным может оказаться упрощение таких условий или произведение расчетов величин до цикла, например вместо for i:=1 to k*2+1 do; можно сделать: m:=2*k+1; for i:=1 to m do. Другой пример: while ((a<20) and (a+3<8)) do; заменим на: while (a<5) do.

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

  1. //плохо
  2. For i:=1 to 512 do
  3. SendByte();
  4. //хорошо
  5. For i:=1 to 128 do
  6. Begin
  7. SendByte();
  8. SendByte();
  9. SendByte();
  10. SendByte();
  11. End;

Полезным может оказаться вынесение из цикла тех действий, которые достаточно выполнить один раз. Пример:

  1. //плохо
  2. For x:=1 to 800 do
  3. For y:=1 to 480 do
  4. begin
  5. r:=x*x;
  6. if (y-240<r) then SomeOp;
  7. OtherOp;
  8. end;
  9. //хорошо
  10. For x:=1 to 800 do
  11. begin
  12. r:=x*x;
  13. For y:=1 to 480 do
  14. begin
  15. if (y-240<r) then SomeOp;
  16. OtherOp;
  17. end;
  18. end;

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

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

  1. //плохо
  2. For i:=1 to 5
  3. For j:=1 to 32 do
  4. SendByte();
  5. //хорошо
  6. For i:=1 to 160 do
  7. SendByte();

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

Еще несколько нюансов

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

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

Заключение

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

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


537

Регистрационная форма

логин
фамилия
имя
отчество
e-mail
пароль
еще раз
пол

Сколько углов у фигуры?

Q-DEX, авторы: Кураев С.В. Саруханян С.К. © 2016г.-2019г.