Индуктивная переменная (англ. Induction variable) — переменная в циклах, последовательные значения которой образуют арифметическую прогрессию. Наиболее распространенный пример — счётчик цикла. Индуктивные переменные часто используются в индексных выражениях массивов.
Например, в следующем примере, i
и j
являются индуктивными переменными:
for ( i = 0; i < 10; i++ )
{
j = 17 * i;
}
Традиционные методы оптимизации предусматривают распознавание индуктивных переменных и удаление их из цикла.
Общий принцип оптимизации заключается в распознавании индуктивных переменных и замене их простыми вычислениями. Например, приведённый выше код может быть изменен оптимизирующим компилятором, исходя из предположения о том, что сложение с константой будет дешевле, чем умножение:
j = -17;
for ( i = 0; i < 10; i++ )
{
j = j + 17;
}
Это применение является частным случаем оптимизации снижения стоимости операций.
В некоторых случаях можно использовать эту оптимизацию, чтобы совсем удалить индуктивную переменную из кода. Например:
extern int sum;
int foo(int n)
{
int i, j;
j = 5;
for ( i = 0; i < n; i++ )
{
j += 2;
sum += j;
}
return sum;
}
Цикл в функции имеет две индуктивные переменные: i
и j
. Одну из них можно представить в виде линейной функции от другой, поэтому компилятор может оптимизировать этот код следующим образом:
extern int sum;
int foo( int n)
{
int i;
for ( i = 0; i < n; i++ )
{
sum += (5 + 2 * ( i + 1));
}
return sum;
}
Замена индуктивной переменной — преобразование, распознающее переменные, которые могут быть представлены в виде функции от индекса цикла, и заменяющее на соответствующие выражения. Это преобразование делает отношения между переменными и индексами циклов явными, что помогает другим оптимизациям компилятора. Рассмотрим пример:
int c, i;
c = 10;
for ( i = 0; i < 10; i++ )
{
c = c + 5; // c увеличивается на 5 на каждой итерации цикла
}
В соответствии с описанным выше методом получим следующее представление исходного кода:
int c, i;
c = 10;
for ( i = 0; i < 10; i++ )
{
c = 10 + 5*i; // c является функцией от индекса
}
Те же самые оптимизации могут быть применены к индуктивным переменным, которые не являются линейными функциями счётчика цикла. Например, следующий код:
j = 1;
for ( i = 0; i < 10; i++ )
{
j = j << 1;
}
может быть преобразован:
for ( i = 0; i < 10; i++ )
{
j = 1 << i+1;
}
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .