Измените стратегию malloc для 2D Array, чтобы malloc преуспел

Question

Недавно мы получили сообщение о том, что наше приложение иногда не запускается. Я отследил код проблемы до этого:

struct ARRAY2D
{
   long[] col;
}

int numRows = 800000;
int numCols = 300;
array = (ARRAY2D*) malloc(numRows * numCols * sizeof(long))

Это выделение 800 Мб может потерпеть неудачу, если у пользователя недостаточно большого свободного блока. Как лучше изменить способ выделения памяти?

Имейте в виду, что у меня есть большой объем кода, который обращается к этому объекту, например: array [row] .col [colNum], поэтому мне нужно что-то, что требует minor или в первую очередь найти и заменить edit кода доступа к массиву.

Answer 1

Будет ли много значений по умолчанию в вашем ARRAY2D? Если да, вам нужен разреженный массив. минимальное изменение будет использовать unordered_map (или hash_map или map):

static const int numRows = 800000;
static const int numCols = 300;

struct ARRAY2D {
  long col[numCols];
  // initialize a column to zero; not necessary.
  ARRAY2D() { memset(col, 0, sizeof(col)); }
};


// no need to malloc
std::unordered_map<int, ARRAY2D> array;
...
// accessing is same as before ...
array[1204].col[212] = 4423;
printf("%d", array[1204].col[115]);
...
// no need to free.

Если индексы строк всегда непрерывны, но намного меньше, чем numRows, вместо этого используйте std::vector.

std::vector<ARRAY2D> array;
...
// resize to the approach value.
array.resize(2000);
...
// accessing is same as before ...
array[1204].col[212] = 4423;
printf("%d", array[1204].col[115]);
...
// no need to free.

Answer 2

Вы можете выделить меньшие куски памяти отдельно, вместо одного огромного блока.

long** array = NULL;  
array = (long**) malloc(numCols * sizeof(long*));  
for (int i = 0; i < numCols; i++)  
   array[i] = (long*)  malloc(numRows * sizeof(long));

Как правило, выделение памяти может завершиться ошибкой , каждое выделение. Однако, скажем, статистически, из-за фрагментации памяти 1007 * выделение одного большого блока памяти имеет более высокий шанс сбоя чаще, чем выделение N числа меньших блоков. Хотя и приведенное выше решение может вызвать проблемы, поскольку оно немного похоже на меч с двумя лезвиями, поскольку может привести к дальнейшей фрагментации памяти.

Другими словами, в целом нет идеального ответа, и решение зависит от деталей системы и приложения.

Поскольку из комментариев представляется, что библиотека C ++ является возможной, тогда решение основано на std::vector (т.е. универсальный вектор векторов в C ++ ) или с использованием Boost.MultiArray

Answer 3

Я написал простой пример, как я бы выделил массив большими кусками:

#include <stdlib.h>
#include <stdio.h>

struct ARRAY2D {
  long *col;
  char free;
};

struct ARRAY2D *ARRAY2D_malloc( int numRows, int numCols ){
  struct ARRAY2D *rows = malloc( numRows * sizeof(struct ARRAY2D) );
  if( rows ){
    for( int i=0,b=numRows; i<numRows; i+=b ){
      char *mem;
      while( b && !(mem = malloc(b*numCols*sizeof(rows[0].col[0]))) ) b--;
      if( b<1 ){
        while( --i >= 0 ) if(rows[i].free) free(rows[i].col);
        free(rows); rows=NULL; break;
      }
      for( int j=i; j<i+b && j<numRows; j++ ){
        rows[j].free=(j==i);
        rows[j].col = (void*)mem; mem += numCols*sizeof(rows[0].col[0]);
      }
    }
  }
  return rows;
}

int main(void){
  int numRows = 8000000;
  int numCols = 300;
  struct ARRAY2D *array = ARRAY2D_malloc( numRows, numCols );
  if( array ){
    printf( "array[numRows-1].col[numCols-1]=%li\n", array[numRows-1].col[numCols-1]=3 );
  }
  else{
    puts("not enough memory");
  }
}

b - количество строк, выделенных за один шаг. Уменьшение b на единицу - простая стратегия, когда нет больших блоков свободной памяти.

Answer 4

В вашем коде есть синтаксические ошибки: у вас отсутствует точка с запятой, а long[] col; недопустим C или C ++.

Дано:

struct ARRAY2D
{
   long *col;
};
ARRAY2D *array;
int numRows = 800000;
int numCols = 300;
array = (ARRAY2D*) malloc(numRows * numCols * sizeof(long));

вы потенциально выделяете неправильный объем памяти: sizeof(long) следует заменить на sizeof *array или sizeof(ARRAY2D).

Предполагая, что вы получили правильную сумму, вы можете индексировать array как: array[i], для i в диапазоне [0, numRows*numCols). Вы не выделили памяти для col членов любого из array[i], поэтому вы не можете индексировать в col любого из них. Поэтому вы используете array[row].col[colNum] неправильно, учитывая схему размещения, которую вы опубликовали.

Возможно, это поможет, если вы разместите какой-нибудь реальный код, который работает.