C ++: Loop Optimization и Loop Unwinding (Зацикливать или не зацикливать)

    char CheckForWinner() {

//returns the token of the player that satisfies one of the winning requirements
if (Square[0][0] == Square[0][1] && Square[0][0] == Square[0][2] ) { //If all three tokens in the first row are the same
return Square[0][0]; //Return the token
} else if (Square[1][0] == Square[1][1] && Square[1][0] == Square[1][2] ) { //Check the next row
return Square[1][0]; //Return the token
} else if (Square[2][0] == Square[2][1] && Square[2][0] == Square[2][2] ) {
return Square[2][0];
} else if (Square[0][0] == Square[1][0] && Square[0][0] == Square[2][0] ) { //If no rows satisfy conditions, check columns
return Square[0][0]; //Return the token
} else if (Square[0][1] == Square[1][1] && Square[0][1] == Square[2][1] ) {
return Square[0][1];
} else if (Square[0][2] == Square[1][2] && Square[0][2] == Square[2][2] ) {
return Square[0][2];
} else if (Square[0][0] == Square[1][1] && Square[0][0] == Square[2][2] ) { //finally, check diagonals
return Square[0][0];
} else if (Square[0][2] == Square[1][1] && Square[0][2] == Square[2][0] ) {
return Square[0][2];
}

return ' ';
}

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

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

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

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

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

С другой стороны, если вы переписываете цикл для устранения ненужного сброса буфера при каждой итерации:

for ( int i = 1; i <= 100; i++ )
cout << i << "\n";

[На случай, если вы этого не поняли: std::endl вставляет новую строку в поток а также промывает поток. В большинстве случаев (возможно, включая этот) очистка буфера не нужна, вероятно, нецелесообразна. Удаление может улучшить скорость много—улучшение в 8: 1 или 10: 1 является довольно распространенным явлением.]

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

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

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

Редактировать 2: Глядя на конкретный вопрос, я думаю, я бы сделал эту работу по-другому. Вместо того, чтобы хранить плату TTT как двумерный массив, я бы сохранил ее в виде пары растровых изображений, одно для X и другое для O. Это позволяет вам проверить всю выигрышную комбинацию в одном действии вместо трех отдельных сравнений. Поскольку каждая строка имеет 3 бита, возможно, проще всего использовать восьмеричное значение для констант:

static const std::array<short, 8> winners = {
/* rows */      0007, 0070, 0700,
/* columns */   0111, 0222, 0444,
/* diagonals */ 0124, 0421
};

В этом случае я почти наверняка использовал бы циклы:

char CheckForWinner(short X, short O) {
// `winners` definition from above goes here.

for (int i=0; i<winners.size(); i++) {
if (X & winners[i] == winners[i])
return 'X';
if (O & winners[i] == winners[i])
return 'O';
}
return ' ';
}

Большой вопрос здесь заключается в том, действительно ли вы хотите передавать платы X и O по отдельности или имеет смысл передавать массив из двух шортов. Очевидным преимуществом использования массива будет более легкий доступ к противоположной плате. Например, чтобы проверить, разрешено ли перемещение на одной доске, нужно проверить, установлен ли этот бит на другой доске. С доски хранятся в массиве, вы можете передать n указав доску, куда вы хотите сделать ход, и используйте 1-n чтобы получить другую доску, где вы проверите, установлен ли этот бит.

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

char square[3][3] = {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '};
char player = 'x';
unsigned progress[2];

const unsigned lines[3][3] = {
0x10010010,
0x10001000,
0x10000101,

0x01010000,
0x01001011,
0x01000100,

0x00110001,
0x00101000,
0x00100110
};

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

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

Как только у вас есть 3 фигуры в одной строке, линия заполнена, и вы выигрываете, поэтому просто продолжайте добавлять строки, пока не нажмете 3. Вы можете распознать 3 по двум последовательным 1 битам, поэтому p & (p >> 1) будет ненулевым:

void make_move(int y, int x)
{
square[y][x] = player;
unsigned p = (progress[player & 1] += lines[y][x]);
if (p & (p >> 1))
{
printf("player %c has won!\n", player);
exit(0);
}
else
{
player = 'x' + 'o' - player;
}
}

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

Это правда, что даже самый простой цикл for добавит несколько служебных команд. Но в вашем случае сложность вызова ввода-вывода перевесит эти инструкции в 10-100 раз.

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

// Process digits starting fom the last one.
wchar_t carry_bit = 0;
while (curr_digit_offs >= 0)
{
wchar_t ch = fpb[curr_digit_offs];
fpb[curr_digit_offs--] = g_RawScan_MultiplyBy2[ch & 15] + carry_bit;
carry_bit = (ch >= L'5') ? TRUE : FALSE;
}

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

В каждом конкретном случае необходима отдельная оценка.