Следует ли избегать практики распределения памяти, которая приводит к одному вызову malloc?
Интересно, является ли хорошей практикой выделение памяти для всех данных, связанных со структурой? Итак, предположим, что у нас есть следующая структура, предназначенная для хранения массивов float-массивов:
#include <stdlib.h>
typedef struct Arrays {
int n;
int* l;
double** data;
} Arrays;
Можно инициализировать пример следующим образом:
Arrays* UsualInitialization(int n) {
// Constructs an array A of length n containing the arrays A[i] = [1,2,...,i]
Arrays* A = (Arrays*) malloc(sizeof(Arrays*));
A->n = n;
A->l = (int*) malloc(n * sizeof(int));
A->data = (double**) malloc(n * sizeof(double*));
for (int i = 0; i < n; i++) {
A->l[i] = i + 1;
A->data[i] = (double*) malloc((i + 1) * sizeof(double));
for (int j = 0; j < i + 1; j++)
A->data[i][j] = j + 1;
}
return A;
}
Каждому указателю соответствует соответствующий вызов malloc. Но мы также можем сделать что-то вроде этого:
Arrays* BlockInitialization(int n) {
// Constructs an array A of length n containing the arrays A[i] = [1,2,...,i]
Arrays* A = (Arrays*) malloc(sizeof(Arrays) +
n * sizeof(int) +
n * sizeof(double*) +
(n * (n+1) / 2) * sizeof(double)
);
A->n = n;
A->l = (int*) (A + 1);
A->data = (double**) (A->l + n);
A->data[0] = (double*) (A->data + n);
for (int i = 0; i < n; i++) {
A->l[i] = i + 1;
for (int j = 0; j < i + 1; j++)
A->data[i][j] = j + 1;
if (i < n - 1)
A->data[i+1] = A->data[i] + i + 1;
}
return A;
}
Здесь есть один вызов malloc, а все остальные указатели получаются из первого путем арифметики указателей и приведения типов. Я полагаю, что в некоторых случаях это может быть более эффективно, поскольку вся выделенная память находится в одном блоке.
Итак, я хотел бы спросить: приводит ли эта практика к неопределенному поведению? Влияет ли это на производительность (в некоторых случаях)? Делает ли это код более непонятным?
Ниже я оставляю метод печати и метод main, которые показывают, что обе инициализации дают одинаковый результат (по крайней мере, на моей машине).
void PrintArrays(Arrays* A) {
printf("Variable contains %d arrays: \n", A->n);
for (int i = 0; i < A->n; i++) {
printf("Array %d (of length %d): [", i, A->l[i]);
for (int j = 0; j < A->l[i]; j++) {
printf("%f", A->data[i][j]);
if (j < A->l[i] - 1) printf(", ");
}
printf("] \n");
}
}
int main() {
Arrays* A = BlockInitialization(10);
PrintArrays(A);
Arrays* B = UsualInitialization(10);
PrintArrays(B);
return 0;
}
Я бы устранил ненужное приведение типов и уменьшил связь: Arrays* a = malloc(sizeof *a + sizeof a->l + sizeof a->data + (sizeof *a->data) * count). Но в конечном итоге выбор может определяться тем, останутся ли эти данные связанными на протяжении всей их жизни и сможете ли вы отслеживать, какие Arrays имеют комбинированные распределения, чтобы можно было вызвать соответствующие free(). И не забудьте учесть выравнивание — возможно, с оберткой будет безопаснее — struct ArrayWithData { Arrays a; int l, double data[]; }
Если Arrays — ваш собственный тип, и вы всегда хотите выделять как блок, то, возможно, вам нужно переосмыслить, какие члены являются указателями (и вспомнить вариант гибкого члена массива).
@TobySpeight Вы имеете в виду, что, возможно, мне следует объявить данные как double[] и использовать переменную l, чтобы указать «начало» A[i] в данных? При этом я не могу использовать гибкие члены массива. Я не вижу преимуществ обертки :(
Обертка полезна только в том случае, если структура Arrays не находится под вашим контролем (например, если она определена используемой вами библиотекой). Если вы можете изменить Arrays, вам не нужна оболочка — просто замените члены указателя на обычные члены объекта данных.
@TobySpeight Кстати, ты написал sizeof *a + sizeof a->l +..., а должно ли быть sizeof *a + n * sizeof *a->l + n * sizeof *a->data + count * sizeof *a->data? Насколько я понимаю, sizeof *a выделяет память для одного int, одного int* и одного double**. Затем нам нужны дополнительные значения a->l[i], значения a->data[i] и значения a->data[i][j].
Одно распределение почти всегда лучше, чем многие из них. Аллокации довольно дороги (и не масштабируются). Если вы не измените размер подмассивов и не получите преимуществ от типов double*, то использование неровных массивов, как вы, не принесет никакой пользы. Кроме того, если ваш реальный код использует такие размеры подмассивов, вы можете выполнить дальнейшую оптимизацию. Нет необходимости даже хранить индексы старт-стоп, поскольку 1+2+3+...+n = n*(n+1)/2. В этом случае вы можете просто написать typedef struct Arrays { int n; double* data; } (и, возможно, использовать гибкие члены массива).
Ой, извините, я пропустил, что l указывает на n элементы.
Ответы 2
Итак, я хотел бы спросить: приводит ли эта практика к неопределенному поведению?
Нет, если вы все сделаете правильно.
Единственная очевидная проблема здесь заключается в том, что для нечетных n конечные указатели и двойные значения могут быть смещены. Вам нужно использовать alignof, чтобы выяснить, сколько отступов необходимо между последовательными элементами.
Влияет ли это на производительность (в некоторых случаях)?
Да, это может значительно улучшить производительность на платформах, которые используют удобное для кэша расположение памяти.
Вероятно, будет еще лучше, если вы потеряете все указатели, удалите массив 1d и сгладите массив 2d, а также предоставите простые средства доступа для получения/индексации массивов.
Даже кажущиеся избыточными вычисления смещения обычно выполняются быстрее, чем множественные разыменования связанных указателей. (Кроме того, удаление указателей делает данные еще более компактными и удобными для кэширования).
Минимальная версия просто
struct LowerTriangular
{
int order;
double data[];
};
и в качестве бонуса это еще и избавит вас от необходимости управлять выравниванием.
Делает ли это код более непонятным?
Да, но если скрытый бит инкапсулирован в две функции (распределитель и освободитель), вы можете его хорошо прокомментировать, тщательно протестировать, а затем забыть о нем.
Спасибо, объяснение очень понятное.
В зависимости от платформы не только странные n могут вызывать смещение, и не только указателей и двойников. В худшем теоретическом случае все эти приведения могут быть смещены для всех значений n.
Хороший момент: каждый размер (и смещение) необходимо округлять до выравнивания следующего типа.
Прежде чем искать оптимизацию, сосредоточьтесь на правильной функциональности.
В стремлении ОП оптимизировать был создан неправильный код:
Arrays* A = (Arrays*) malloc(sizeof(Arrays*)); // Bad - why the size of a pointer?
При выделении вместо использования ненужного приведения и определения размера для типа (что было неправильно выше) отбросьте приведение и размер к объекту, на который ссылаются:
Arrays* A = malloc(sizeof A[0]);
// or
Arrays* A = malloc(sizeof *A);
Внезапное распределение не смогло обеспечить согласованность. Вычисление OP не учитывало потенциальные потребности в выравнивании.
// Bad
sizeof(Arrays) + n * sizeof(int) + n * sizeof(double*) + (n * (n+1) / 2) * sizeof(double)
Если реализация поддерживает массивы переменной длины и n > 0, сформируйте указатель на struct всех выделений, чтобы легко получить заполнение и выравнивание всех массивов.
// Constructs an array A of length n containing the arrays A[i] = [1,2,...,i]
Arrays* BlockInitialization_alt(int n) {
assert(n > 0);
struct {
Arrays A;
int l[n];
double *data[n];
double d[n * ((size_t)n+1) / 2];
} *all = malloc(sizeof all[0]);
if (all == NULL) {
return NULL;
}
Arrays* A = &all->A;
A->n = n;
A->l = &all->l;
A->data = &all->data;
double *d = &all->d;
for (int i = 0; i < n; i++) {
A->l[i] = i + 1;
A->data[i] = d;
for (int j = 0; j < i + 1; j++)
A->data[i][j] = j + 1;
}
d += i + 1;
}
return A;
}
Впервые я вижу объявление структуры внутри функции. Каковы последствия? Например, требуется ли больше времени объявить эту структуру внутри функции или выполнить вычисления заполнения самостоятельно?
@ RB1995 Обратите внимание, что all является указателем на struct. Поскольку struct содержит массивы переменной длины, его размер варьируется в зависимости от вызова функции. "дополнение вычислений самостоятельно?" подвержен ошибкам и не будет быстрее.
Да, all — это указатель, я понимаю эту часть. Мой вопрос на самом деле о том, что происходит за кулисами. Что происходит, когда вы определяете структуру внутри функции? Извините, если это очень простой вопрос, я только изучаю C. На самом деле первоначальный вопрос был о лучшем понимании языка. Если у вас есть ссылка, чтобы узнать больше, это было бы здорово!
Это определенно делает код более непонятным. :-) Также сложно понять, какие указатели должны быть
freeв конце. При выделении двумерного массива двойных значений я ожидаю, что последующие вычисления займут гораздо больше времени, чем выделение памяти. Так это действительно горячая точка?