Является ли инициализация 2D-массива в программе c ненужной тратой времени?

Question

Я пишу программу на C, которая должна использовать 2D-массив для хранения ранее обработанных данных для последующего использования.

Размер этого двумерного массива 33х33; matrix[33][33].

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

Дополнительно:

Я инициализирую эту матрицу как глобальный параметр, подобный этому:

int map[33][33];

1. В одной из функций A мне нужно сохранить все данные 33x33 в эту матрицу.
2. В другой функции B я получу небольшую матрицу 3x3 из карты [33] [33] для моего следующего шага обработки.

Выше 2 шагов будут повторяться около 8000 раз. Итак, повлияет ли это на эффективность работы программы?

Или, у меня есть другое предположение, что программа работает медленнее из-за того, что недавно в программу было добавлено несколько операторов ветвления if-else.

Answer 1

Немного упрощенно, в C есть три типа переменных: статические, автоматические и динамические.

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

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

Динамические переменные выделяются с помощью malloc, и вы должны инициализировать их самостоятельно, и это снова занимает немного времени.

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

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

Однако, поскольку 33 * 33 - это довольно небольшое число, либо элементы матрицы очень велики, либо компьютер работает очень медленно, либо 33 больше, чем у меня.

Answer 2

Как ты это делал раньше? Единственная проблема, о которой я могу подумать, заключается в том, что извлечение подматрицы 3x3 из целочисленной матрицы 33x33 будет вызывать проблемы с кэшированием при каждом извлечении подматрицы.

На большинстве современных машин размер кэша составляет 64 байта. Этого достаточно для 8 элементов матрицы. Таким образом, для каждой дополнительной строки подматрицы 3x3 вы будете выполнять новую выборку из кэширования. Если матрица забивается очень регулярно, то матрица, вероятно, будет находиться в основном в кеше уровня 2 (или, возможно, даже уровне 1, если он достаточно большой), но если вы выполняете много других вычислений данных между каждой выборкой подматрицы, тогда будет получать 3 дорогих кешлайна каждый раз, когда вы будете получать субматрицу.

Однако даже в этом случае маловероятно, что вы увидите ОГРОМНУЮ разницу в производительности. Как указывалось в другом месте, нам нужно увидеть код до и после, чтобы можно было угадать, почему производительность ухудшилась ...

Answer 3

Как ваша предыдущая версия программы сохраняла данные, если не в матрице? Как вы могли читать подматрицу, если у вас не было большой матрицы?

Многие ответы говорят о времени, потраченном на инициализацию . Но я не думаю, что это был вопрос. В любом случае, на современных процессорах инициализация такого небольшого массива занимает всего несколько микросекунд. И это делается только один раз, при запуске программы.

Если вам нужно извлечь подматрицу из любой позиции, вероятно, нет более быстрого метода, чем использование статического 2D-массива. Однако, в зависимости от архитектуры процессора, доступ к массиву может быть быстрее, если измерения массива (или только последнее измерение) имеют степень 2 (например, 32, 64 и т. Д.), Поскольку это позволит использовать сдвиг вместо умножения.

Если доступ к подматрицам не перекрывается (т. Е. Вы будете обращаться только к индексам 0, 3, 6 и т. Д.), То использование 3-мерного или 4-мерного массива может ускорить доступ

  int  map[11][11][3][3];

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

Answer 4

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

Answer 5

Ну, я бы этого не ожидал (что-то подобное должно занять гораздо меньше секунды), но простой способ узнать это - просто поместить оператор print в начало main ().

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

РЕДАКТИРОВАТЬ Один из способов получить более четкое представление о том, что занимает так много времени, - это использовать отладчик, например GDB , или профилировщик, например GProf

Answer 6

Нет, во время выполнения нет разницы между инициализацией массива один раз (каким-либо методом) и не инициализацией его.

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

Answer 7

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

mystery_type *matrix;

matrix = malloc(33 * 33 * sizeof *matrix);

Answer 8

теоретически с использованием N-го размерного массива не должно быть разницы в производительности, поскольку все они преобразуются в непрерывное резервирование памяти компилятором.

int _1D [1089]; int _2D [33] [33]; int _3D [3] [11] [33];

должен давать аналогичную скорость выделения / освобождения.