Почему G CC может выполнять оптимизацию обмена l oop только тогда, когда размер int является константой времени компиляции? - PullRequest
Новая
       68

Почему G CC может выполнять оптимизацию обмена l oop только тогда, когда размер int является константой времени компиляции?

2 голосов
/ 03 апреля 2020

Когда я компилирую этот фрагмент (с -Ofast -fnest-loop-optimize), g cc генерирует сборку, которая пересекает массив в исходном порядке.

Однако, если я раскомментирую строку // n = 32767 и назначу any число до n, оно меняет порядок индекса на x[i * n + j]. Обход памяти в последовательном главном порядке строк гораздо более удобен для кэширования, чем смещение столбцов. 

float matrix_sum_column_major(float* x, int n) {
    // n = 32767;
    float sum = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            sum += x[j * n + i];
    return sum;
}

На Godbolt

Почему G CC или clang не могут l oop обмениваться с переменной времени выполнения int size? Реальный код обычно не имеет явно объявленного размера.

PD: я пробовал это с разными версиями g cc и clang-9, и похоже, что это происходит в обеих.
PD2: Даже если я сделаю x локальной переменной malloc внутри функции это все еще происходит.

1 Ответ

2 голосов
/ 12 апреля 2020

Компиляторы обычно сосредотачивают свои усилия (и должны концентрировать свои усилия) на местах, где конструкции , которые, вероятно, будут использоваться программистами, заинтересованными в эффективности , могут быть заменены другими конструкциями , которые легко доказываются как эквивалентен во всех случаях, которые должны иметь значение . Если n является константой, компилятор может определить точный набор индексов массива, который будет использоваться в l oop, а затем выяснить, как обрабатывать все эти индексы. Если n не является константой, компилятор может определить, что если n положительно, код будет использовать все индексы от 0 до n*n-1, но это, вероятно, потребует гораздо больших усилий. Авторы clang и, возможно, смогли бы сделать такое определение в этом случае, если бы они достаточно старались, но они, вероятно, думали, что усилия не стоили.

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

...