C: Выделите память впереди или на каждый запрос?

Question

У меня к вам простой (вероятно) вопрос. При создании собственной реализации динамического массива в C, лучше ли выделять память вперед (предположим, для 10 элементов), когда массив близок к достижению своей текущей максимальной способности, или перераспределять память каждый раз, когда изменяется число элементов?

Я имею в виду: за производительность, элегантность или все, что вам приходит в голову.

Answer 1

Обычный выбор - умножить текущий размер на фиксированное число, большее единицы (обычно 1,5-й, как и 2), что амортизирует O (n) общих затрат на выделение и копирование.

Обратите внимание, что нет гарантии, что вы можете увеличить размер массива на месте, поэтому вам, возможно, придется скопировать все существующие элементы в новое место (realloc() сделает это автоматически для вас, но вам все равно придется оплатить стоимость).

Answer 2

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

array = realloc(array, old_size * 2);

Answer 3

Как правило, лучше предварительно выделить в «начальном» фиксированном размере, а когда вам не хватит места, перераспределить на основе фактора роста.

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

Начальный размер должен быть числом, основанным на типичном использовании. Типичное использование является важным фактором, который помогает вам выбрать размер, так что вы: A) не тратите пространство, выбирая слишком большой начальный размер, и B) не используете начальный размер, слишком маленький для того, чтобы было много перераспределений будет необходимо, пока целевой размер не будет достигнут.

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

Что касается фактора роста, то коэффициент роста х1,5 или х2 является обычным явлением. Это то, что вы можете измерить, используя статистику теста, как с начальным размером.

Еще одна вещь, которую следует учитывать, это то, что вам нужно быть осторожным при управлении ссылками на динамически изменяемые данные, поскольку realloc () будет перемещать данные в памяти при необходимости. Это означает, что если вы сохранили адрес первого элемента динамически изменяемого размера массива, этот адрес может быть недействительным после вызова realloc. Это может управляться API-оболочкой вокруг вашего пользовательского типа данных, которая раздает индексы вместо адресов памяти и может при необходимости преобразовать индекс в текущий адрес элемента.

Answer 4

Вы можете определить структуру следующим образом:

/** Dynamic array */
typedef struct __darray {
        int* array;            /** Array */
        int size;               /** Array size */
        int cap;                /** Capacity */
} darray;

Размер <= емкость. </p>

Когда вы динамически добавляете новый элемент теста, если ваш размер> емкость. Если это правда, выполнить перераспределение памяти. Формула (взятая из реализации ArrayList из JDK):

(jobs here...)
[your_darray]->capacity+=[your_darray]->capacity*3/2+1;
[your_darray]->array=(int*)realloc([your_darray]->array,capacity*sizeof(int));
(jobs here...)

Если вы удаляете (достаточно) элементов из вашего динамического массива, не забудьте снова сжать «int *».

Answer 5

Выделение памяти в куче всегда дорого. Делать это поэлементно не рекомендуется.

Answer 6

Более поздней стратегией выделения памяти был Slab Allocator , принятый Solaris и Linux. Memcached также использует распределитель плит, как описано в этой записи FAQ .

Answer 7

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