Является ли законным для компилятора ухудшить временную сложность программы? Является ли это наблюдаемым поведением?

Ответ 1

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

Стандарт С++ дает только гарантию сложности только для некоторых его библиотечных функций и говорит (17.5.1.4 [structure.specifications]):

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

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

Ответ 2

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

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

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

Ответ 3

5.1.2.3 в стандарте C говорит

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

Стандарт С++ имеет аналогичную формулировку в 1.9 [intro.execution]

Оба стандарта имеют одно и то же определение наблюдаемого поведения:

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

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

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

Ответ 4

Другие отметили, что стандарт не ограничивает работу C-среды выполнения, а только ее наблюдаемое поведение. Нет причин, по которым вы не можете интерпретировать или скомпилировать CIT, например.

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