Инициализация массива C ++ за постоянное время

Question

char buffer[1000] = {0};

Инициализирует все 1000 элементов на 0. Это постоянное время?Если нет, то почему?

Похоже, что компилятор может оптимизировать это до O (1), основываясь на следующих фактах:

1. Массив имеет фиксированный размер и известен во время компиляции
2. Массив расположен в стеке, что означает, что, предположительно, исполняемый файл может содержать эти данные в сегменте данных исполняемого файла (в Windows) как кусок данных, который уже заполнен нулями.

Обратите внимание, что ответы могут быть общими для любого компилятора, но меня особенно интересуют ответы, протестированные на компиляторе MSVC (любая версия) в Windows.

Бонусные баллы: ссылки на любые статьи,официальные документы и т. д. об этих деталях будут с благодарностью.

Answer 1

Если это внутри функции, нет, это не постоянное время.

Ваше второе предположение неверно:

"Массив расположен в стеке, что означает, что, предположительно, исполняемый файл может содержать эти данные в сегменте данных исполняемого файла (в Windows) в виде фрагмента данных, который уже заполнен нулями."

Стек еще не заполнен нулями. Он заполнен остатками мусора от предыдущих вызовов функций.

Так что это невозможно сделать в O(1), потому что его придется обнулить.

Answer 2

Это может быть O (1) только как глобальная переменная. Если это локальная переменная (в стеке), то это O (n), где n - размер массива.

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

РЕДАКТИРОВАТЬ: Дани прав, я должен исправить свое утверждение: если это глобальный массив, он инициализируется при запуске программы. И это тоже O (n).

Answer 3

Это никогда не будет постоянным временем, глобальным или нет.Это правда, что компилятор инициализирует это, но операционная система должна загрузить весь файл в память, что занимает O(n) время.

Answer 4

Массив расположен в стеке, что означает, что, предположительно, исполняемый файл может содержать эти данные в сегменте данных исполняемого файла (в Windows) как кусок данных, который уже заполнен нулями.

Что если вы вернетесь в функцию, которая определяет массив?Глобальный сегмент DATA должен иметь копию этого массива для каждого вызова функции, чтобы каждая функция имела собственный массив для работы.Компилятор должен запустить ваш код, чтобы решить, будет ли максимальное количество рекурсий.

Кроме того, что происходит, когда в вашей программе несколько потоков, и каждый вызывает foo?Внезапно вы поделились данными в DATA, которые должны быть заблокированы.Блокировка может вызвать больше проблем с производительностью, чем избавиться от инициализации.

Я бы не слишком беспокоился об этом.Большинство платформ имеют достаточно эффективные способы заполнения памяти нулем.Если вы не профилируете это и не обнаружите проблему, не переживайте.

Answer 5

Как уже отмечали другие, предположение 2 неверно.Переменные стека выделяются во время выполнения за O (1), но обычно не инициализируются, если вы не выполняете отладочную сборку.

PUSH ebp
MOV  ebp, esp
SUB  esp, 10
// function body code goes here

Здесь указатель стека 'esp' уменьшается на 10освободить место для некоторых локальных переменных функции.Они не инициализированы ... для этого потребуется цикл.

Эта статья кажется достаточно дружелюбной.

Answer 6

Если это глобальная статика, то здесь «константой» является ноль - инициализация выполняется в COMPILE TIME.