Разрешено ли оптимизатору C++ переупорядочивать вызовы clock()?

Question

Издание C++ Programming Language 4th edition, стр. 225, гласит: Компилятор может переупорядочить код для повышения производительности, если результат идентичен результату простого порядка выполнения. Некоторые компиляторы, например Visual C++ в режиме выпуска, переупорядочивают этот код:

#include <time.h>
...
auto t0 = clock();
auto r  = veryLongComputation();
auto t1 = clock();

std::cout << r << "  time: " << t1-t0 << endl;

в эту форму:

auto t0 = clock();
auto t1 = clock();
auto r  = veryLongComputation();

std::cout << r << "  time: " << t1-t0 << endl;

что гарантирует результат, отличный от исходного кода (ноль против времени, указанного выше нуля). Смотрите мой другой вопрос для подробного примера. Соответствует ли это поведение стандарту C++?

Answer 1

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

Поскольку абстрактная машина C++ формально не ограничена конечными скоростями, она может выполняться veryLongComputation() в нулевое время. Само время выполнения не определяется как наблюдаемый эффект. Реальные реализации могут соответствовать этому.

Имейте в виду, многое из этого ответа зависит от стандарта C++, не накладывающего ограничений на компиляторы.

Answer 2

Ну, есть то, что называется Subclause 5.1.2.3 of the C Standard [ISO/IEC 9899:2011] в котором говорится:

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

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

Более того - реорганизация действительно влияет на результат вычислений, но если вы посмотрите на это с точки зрения компилятора - она ​​живет в int main() мир и при выполнении измерений времени - он высматривает, просит ядро ​​дать ему текущее время и возвращается в основной мир, где фактическое время внешнего мира на самом деле не имеет значения. Функция clock() сама по себе не влияет на программу, а переменные и поведение программы не влияют на функцию clock().

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

Это, однако, не меняет того факта, что описанное поведение очень неприятно.

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

Рассмотрим следующий код, взятый с этого сайта:

void GetData(char *MFAddr) {
    char pwd[64];
    if (GetPasswordFromUser(pwd, sizeof(pwd))) {
        if (ConnectToMainframe(MFAddr, pwd)) {
              // Interaction with mainframe
        }
    }
    memset(pwd, 0, sizeof(pwd));
}

При нормальной компиляции все в порядке, но если применяется оптимизация, вызов memset будет оптимизирован, что может привести к серьезным ошибкам безопасности. Почему это оптимизировано? Это очень просто; компилятор снова думает по-своему main() мир и считает memset мертвым хранилищем, так как переменная pwd впоследствии не используется и не повлияет на саму программу.

Answer 3

Да, это законно - если компилятор может видеть весь код, который происходит между clock() звонки.

Answer 4

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

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

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

Answer 5

По крайней мере, по моим прочтениям, нет, это не разрешено. Требование от стандарта (§1.9/14):

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

Степень, до которой компилятор может свободно переупорядочивать, определяется правилом "как если" (§1.9/1):

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

Это оставляет вопрос о том, является ли рассматриваемое поведение (выход, написанный cout) официально наблюдаемое поведение. Короткий ответ: да, это (§1.9/8):

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

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

Однако, если вы хотите предпринять дополнительные шаги для обеспечения правильного поведения, вы можете воспользоваться еще одним положением (также §1.9 / 8):

- Доступ к изменчивым объектам оценивается строго по правилам абстрактной машины.

Чтобы воспользоваться этим, вы должны немного изменить свой код, чтобы он стал чем-то вроде:

auto volatile t0 = clock();
auto volatile r  = veryLongComputation();
auto volatile t1 = clock();

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

Answer 6

Давайте предположим, что последовательность находится в цикле, а veryLongComputation () случайно генерирует исключение. Тогда сколько t0s и t1s будет вычислено? Предварительно ли он рассчитывает случайные величины и переупорядочивает их на основе предварительного расчета - иногда переупорядочивает, а иногда нет?

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

Или, возможно, время контролирует шлифовку зеркала телескопа Хаббла. лол

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

ИМО.

Answer 7

Это, конечно, недопустимо, поскольку, как вы заметили, оно меняет наблюдаемое поведение (другой вывод) программы (я не буду вдаваться в гипотетический случай, когда veryLongComputation() может не потреблять измеримое время - учитывая имя функции, вероятно, не так. Но даже если бы это было так, это бы не имело значения). Вы не ожидаете, что это возможно изменить порядок fopen а также fwrite, не могли бы вы.

И то и другое t0 а также t1 используются в выводе t1-t0, Следовательно, выражения инициализатора для обоих t0 а также t1 должны быть выполнены, и при этом должны следовать всем стандартным правилам. Результат функции используется, поэтому невозможно оптимизировать вызов функции, хотя это напрямую не зависит от t1 или наоборот, так что можно наивно полагать, что это законно, почему бы и нет. Может быть, после инициализации t1, который не зависит от расчета?
Косвенно, однако, результат t1 Конечно, зависит от побочных эффектов veryLongComputation() (в частности, вычисление требует времени, если не больше), что является одной из причин, по которой существует такая вещь, как "точка последовательности".

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

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

Теперь интересный вопрос: почему компилятор делает это в любом случае? Я могу думать о двух возможностях. Возможно, ваш код запускает эвристику типа "выглядит как эталонный тест", и компилятор пытается обмануть, кто знает. Это будет не в первый раз (например, SPEC2000/179.art или SunSpider для двух исторических примеров). Другая возможность была бы, что где-то внутри veryLongComputation() вы случайно вызываете неопределенное поведение. В этом случае поведение компилятора будет даже допустимым.