Лучший способ выделить память двумерному массиву в C?

Question

Каков наилучший способ выделить память two-d array в C, с обоих точек зрения: memory-management и speed?

Кроме того, что лучше использовать, two-d array (и выделить ему память) или double pointer? Может кто-нибудь объяснить подробно, что происходит внутри, почему метод лучше, чем другой?

Answer 1

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

type (*array) [X][Y] = malloc(sizeof(type[X][Y])); 

Следует избегать этого:

// BAD METHOD, not a real array 

type** lookup_table = malloc(X*sizeof(type*)); 
for(size_t i=0; i<Y; i++) 
{ 
    lookup_table[i] = malloc(Y*sizeof(type)); 
} 

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

«Плохая» версия выше имеет одно преимущество, хотя это означает, что вы хотите, чтобы отдельные размеры имели переменную длину, например, при создании таблицы поиска для строк. Затем вы должны использовать эту форму. Но если вам нужен настоящий 2D-массив, никогда не будет причины не использовать его.

---

Обратите внимание, что первая версия обычно записывается как

type (*array) [Y] = malloc(sizeof(type[X][Y])); 

, чтобы обеспечить более удобное использование: array[i][j], а не менее читаемым (*array)[i][j].

Answer 2

Учитывая фиксированный размер, вы можете просто сказать twoDimArray[100][100], который выделит его в стеке. Однако при распределении в куче (независимо от того, большой размер или размер динамический) у вас больше вариантов.

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

Второй способ - линеаризовать доступ и распределить его все одновременно; то есть выделить достаточное количество памяти для sizex * sizey, а затем проиндексировать его (positiony * sizex) + positionx; то есть подсчитывать несколько строк, а затем через некоторые столбцы. Это отлично подходит для случайного доступа и улучшает локальность кэша, потому что память смежна, но может быть неудачной, если недостаточно доступной непрерывной памяти (а преимущество локализации кеша не применимо, если вам нужно больше памяти, чем в кеше).

Answer 3

data_type (*mat)[size_2] = malloc(size_1 * size_2 * sizeof(data_type)); 

Это будет выделение непрерывной памяти для массива массивов («2d-массив»). Если вы не требуете смешного пространства, это путь. Вы уменьшите фрагментацию памяти, увеличите удобство использования кеша и избегаете слишком больших издержек из-за использования malloc.

---

_{Для некоторых (Application Specific) определение смешного}