Почему хуже инициализировать двумерный массив, подобный этому?
==============================================================

Мой профессор сказал, что инициализация двумерного массива в первом случае намного дороже, чем во втором. Может кто-нибудь объяснить, что происходит под капотом, что делает это дело? Или оба средства инициализации имеют одинаковую производительность?

Как уже упоминалось @dlev, это связано с[местность ссылки](https://en.wikipedia.org/wiki/Locality_of_reference) и имеет отношение к тому, как физическое оборудование в компьютере работает.

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

Оперативная память (RAM) намного, намного медленнее, чем регистры, часто в сотни и тысячи раз. Следовательно, следует избегать чтения из памяти, если это вообще возможно. Чтобы решить эту проблему, большинство компьютеров обычно имеют специальные области памяти, называемые[кэши](https://en.wikipedia.org/wiki/CPU_cache), Задача кэша состоит в том, чтобы хранить данные, к которым недавно обращались, из памяти, так что, если к той же самой области памяти обращаются снова, значение можно извлечь из кэша (быстро), а не из основной памяти (медленно). Как правило, кэши разрабатываются таким образом, чтобы при чтении значения из памяти это значение вместе с целым рядом смежных значений помещалось в кэш. Таким образом, если вы выполняете итерацию по массиву, то после прочтения первого значения остальные значения из массива будут храниться в кэше, и к ним можно будет обращаться более эффективно.

Причина того, что ваш код работает медленнее, чем нужно, состоит в том, что он не обращается к элементам массива последовательно. В C двумерные массивы расположены в[порядок ряда строк](https://en.wikipedia.org/wiki/Row-major_order)Это означает, что память устроена как

Следовательно, если вы используете это для цикла:

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

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

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

Надеюсь это поможет!



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



Я, вероятно, буду за это опускаться, но если вы программируете на C, то «лучший» скорее всего:

memset (массив, 0, sizeof (массив));

Затем вы можете отложить всю ответственность за оптимизацию (о которой вы, очевидно, беспокоитесь) до реализации memset. Любые конкретные аппаратные преимущества могут быть сделаны там.

[http://en.wikipedia.org/wiki/Sizeof#Using\_sizeof\_with\_arrays/](https://en.wikipedia.org/wiki/Sizeof#Using_sizeof_with_arrays/)

<http://www.cplusplus.com/reference/clibrary/cstring/memset/>

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



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

Я использую[`perf`](https://perf.wiki.kernel.org/index.php/Main_Page) инструмент в пакете Ubuntu 10.10`linux-tools-common`.

Вот небольшая программа на C, которую я написал, чтобы ответить на этот вопрос:

Затем скомпилируйте две разные версии:

Обратите внимание, что я отключил оптимизацию с помощью`-O0` так что у gcc нет шансов изменить наш цикл, чтобы быть более эффективным.

Мы можем перечислить статистику производительности, доступную с`perf` при выполнении`perf list`, В этом случае нас интересуют промахи кеша, который является событием`cache-misses`.

Теперь это так же просто, как запускать каждую версию программы много раз и брать среднее значение:

И теперь мы экспериментально подтвердили, что вы на самом деле видите на два порядка больше пропусков кэша с помощью "row-minor" версия.