C: что лучше?Malloc массив указателей на структуры или массив структур?

Question

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

//pointer based:
struct myStructure ** tmp = malloc(sizeof(struct myStructure *) * N);
tmp[0] = malloc(sizeof(struct myStructure));
tmp[0]->whatever = true;

//or structure in the array:
struct myStructure * tmp = malloc(sizeof(struct myStructure) * N);
tmp[0].whatever = true

Есть ли какие-либо преимущества по сравнению с одной или другой?Я чувствую, что использование второй формы - лучшая практика, потому что в итоге вы получаете меньше небольших вызовов malloc, но могут быть случаи, когда вы можете использовать только первый метод.* Спасибо!

Answer 1

В общем, я бы использовал второй способ, поскольку, если вы используете все слоты, он:

• использует немного меньше памяти (в N раз больше указателя);
• фрагментов меньше кучи;
• избегает N обращений к malloc / free (=> это быстрее и проще для выделения / освобождения);
• позволяет избежать двойного косвенного обращения при доступекаждая структура (очень небольшое улучшение).

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

Answer 2

Обычно второй лучше [IMO] - он, вероятно, будет дешевле [как памяти, так и времени], и, безусловно, будет проще поддерживать его.

Однако в некоторых случаях, второй подход может потерпеть неудачу - когда первый будет успешным.Это может произойти из-за фрагментации памяти - для всех ваших структур достаточно памяти, она просто не находится в «одном месте» в вашей памяти.

Answer 3

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

• Первый массив гораздо проще: расти и уменьшаться на основе ихактуальная потребность в системе.Вырастить первый массив указателей довольно просто - каждый элемент имеет длину четыре или восемь байтов, поэтому удвоение размера массива не будет стоить слишком много.

  Второй массивфактические структуры могут быть значительно больше (в sizeof struct foo раза больше числа элементов), и даже при небольшом увеличении массива может не хватить памяти, если у realloc(3) недостаточно свободного места для работы.

• Первый массив дает вам возможность ссылаться на объекты в системе «ручками» и переупорядочивать их память в соответствии с требованиями.Вы можете размещать лежащие в основе объекты в виде листов размером и повторно сжимать объекты в направлении почти заполненных плит - что позволит вам позже возвращать страницы в операционную систему для другого использования.Другие объекты в системе должны были бы пройти через другой уровень косвенности, чтобы добраться до объектов, на которые есть ссылки, но эти объекты клиента («ссылки»?) Не должны обновлять свои указатели при перемещении объектов.

• Время жизни объектов в первом массиве «разъединено» - некоторые из этих объектов могут жить очень долго, а другие - всего миллисекунды.Во втором массиве весь массив имеет одинаковое время жизни.Вы можете добавить дополнительную структуру данных во второй массив, чтобы управлять тем, какие объекты являются живыми, а какие нет, или добавить новые поля в структурах, чтобы указать, какие объекты являются живыми и мертвыми, но оба подхода требуют больше работы.С первым массивом, если указатель не является NULL, тогда объект является живым.

Оба подхода имеют свои преимущества.Выберите подходящий для работы под рукой.

Answer 4

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

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

С точки зрения скорости выделения, malloc (), очевидно, требует времени для запуска, поэтому один malloc () обычно будет быстрее.

С точки зрения размера памяти, malloc () обычно имеет некоторые накладные расходы при каждом выделении. И, очевидно, указатели являются дополнительной платой. Таким образом, если вы выделите 1000 16-байтовых структур, вы можете получить 16 байт на структуру в служебных данных malloc и 8-байтовый указатель, всего 40 016 байт. Одно выделение займет всего 8 016 байт.

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

С точки зрения фрагментации памяти, это зависит. Если у вас достаточно большие структуры (значительная часть общего объема ОЗУ), то вы можете оказаться в ситуации, когда не хватает непрерывной свободной памяти для выделения одного большого массива, но достаточно для выделения массива указателей и отдельные структуры. (Например, если у вас есть 32-разрядная программа в операционной системе, которая ограничивает вас до 2 ГБ памяти, и ваш распределитель памяти выделил что-то еще на полпути через память, то вы не можете сделать одно выделение 1,5 ГБ, но вы могли бы сделать 15 100MB выделений). Такой сценарий встречается редко, потому что люди обычно не работают с такими большими данными.