C Динамический вопрос распределения скорости

Question

Я использую этот код для динамического создания 2d-массива:

char **FileTables;
int rows = 1000;
int i;

FileTables = (char**)malloc(rows * sizeof(char));
for (i = 0; i < rows; i++) {
    FileTables[i] = (char*)malloc(256 * sizeof(char));
}

Проблема с 1000 строками, и может быть больше, для выделения всей памяти может потребоваться несколько секунд.Есть ли какой-нибудь более быстрый / лучший способ сделать это?

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

char **FileTables;
int rows = 1000;
int i;

FileTables = malloc(rows * sizeof(char*));
FileTables[0] = malloc(rows * 256 * sizeof(char));
for (i = 0; i < rows; i++) {
    FileTables[i] = FileTables[0] + i * 256;
}

И..

char (*FileTables)[256];
int rows = 1000;

FileTables = malloc(rows * sizeof(*FileTables));

(И да, я исправил ненужный кастинг)

Answer 1

Вы можете обойтись всего двумя выделениями и некоторой арифметикой указателей:

int rows = 1000;
int cols = 256;
char *data;
char **FileTables;
int i;

data = malloc(rows * cols);
FileTables = malloc(rows * sizeof(char*));
for (i = 0; i < rows; i++) {
    FileTables[i] = data + i * cols;
}

Также обратите внимание, что я исправил ошибку в malloc(rows * sizeof(char)) (sizeof(char) должно быть sizeof(char*), поскольку вы выделяете массив из указателей на char).

Answer 2

До тех пор, пока число столбцов является постоянным или если вы используете C99, вы можете обойтись без единого malloc, не выполняя некрасивую арифметику адресации строк / столбцов самостоятельно:

char (*FileTables)[256] = malloc(rows * sizeof *FileTables);

Answer 3

Если массив всегда имеет размер row & times; 256, тогда вы можете рассмотреть одномерный массив malloc(row * 256) и получить к нему быстрый доступ:

char get(unsigned i, unsigned j, char * array) { return array[j + 256 * i]; }
void set(char value, unsigned i, unsigned j, char * array) { array[j + 256 * i] = value; }

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

Answer 4

Я не верю, что вы получите где-то около секунд Увеличение количества строк до 10 миллионов все еще занимает меньше секунды на моей машине.

Однако, если вы хотите минимизировать распределение, вам нужен только один.

FileTables = (char**) malloc(rows * (sizeof(char *) + 256*sizeof(char)));
FileTables[0] = (char *) &FileTables[rows];
for (i = 1; i < rows; i++) {
    FileTables[i] = FileTables[i-1] + 256 * sizeof (char);
}
free(FileTables);

Более эффективный способ сделать это - избежать второго уровня косвенности.

typedef char chars[256];

int main(int argc, char** argv) {
    chars* FileTables;
    int rows = 100000000;
    int i;

    FileTables = (chars*) malloc(rows * sizeof (chars));
    free(FileTables);

    return (EXIT_SUCCESS);
}

Это позволяет избежать поиска по указателю, так как C может вычислить остальное.

Answer 5

char **FileTables; 
int rows = 1000; 
int i; 

FileTables = (char**)malloc(rows * sizeof(char *)); 
char *data = (char *)malloc(256 * 1000 * sizeof(char));
for (i = 0; i < rows; ++i) { 
    FileTables[i] = data;
    data += 256 * sizeof(char);
}

Должно быть лучшим решением.

Answer 6

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

Советы по ускорению распределения:

1. Делать меньше ассигнований
2. Делать меньшие выделения

Как видите, если вам нужно выделить 10М, эти советы скоро станут противоречивыми. Чтобы определить правильный баланс между меньшими и меньшими распределениями, необходимо выполнить профилирование.

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

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

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

Answer 7

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

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

В противном случае настоящая «медленная» часть malloc фактически получает память из ОС (с помощью sbrk () или mmap ()), и большинство реализаций malloc одновременно собирают большой кусок и возвращают его меньшими частями Таким образом, здесь нет 1000 вызовов для размещения 1 КБ, возможно, существует 60 вызовов для выделения 16 КБ. Запуск программы в режиме strace или аналогичной может дать вам представление о том, сколько медленных системных вызовов действительно выполняется. Вы можете реализовать подобное поведение самостоятельно, сделав один вызов для выделения 256 КБ и разделив его на более мелкие куски. Вы можете попытаться выделить большой кусок памяти, а затем сразу же освободить его () - и надеяться, что библиотека malloc удерживает эту память и больше не возвращается к ОС.