Интересно, является ли хорошей практикой выделение памяти для всех данных, связанных со структурой? Итак, предположим, что у нас есть следующая структура, предназначенная для хранения массивов 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;
}
🤔 А знаете ли вы, что...
C является одним из самых влиятельных языков программирования в истории.
Итак, я хотел бы спросить: приводит ли эта практика к неопределенному поведению?
Нет, если вы все сделаете правильно.
Единственная очевидная проблема здесь заключается в том, что для нечетных n конечные указатели и двойные значения могут быть смещены. Вам нужно использовать alignof, чтобы выяснить, сколько отступов необходимо между последовательными элементами.
Влияет ли это на производительность (в некоторых случаях)?
Да, это может значительно улучшить производительность на платформах, которые используют удобное для кэша расположение памяти.
Вероятно, будет еще лучше, если вы потеряете все указатели, удалите массив 1d и сгладите массив 2d, а также предоставите простые средства доступа для получения/индексации массивов.
Даже кажущиеся избыточными вычисления смещения обычно выполняются быстрее, чем множественные разыменования связанных указателей. (Кроме того, удаление указателей делает данные еще более компактными и удобными для кэширования).
Минимальная версия просто
struct LowerTriangular
{
int order;
double data[];
};
и в качестве бонуса это еще и избавит вас от необходимости управлять выравниванием.
Делает ли это код более непонятным?
Да, но если скрытый бит инкапсулирован в две функции (распределитель и освободитель), вы можете его хорошо прокомментировать, тщательно протестировать, а затем забыть о нем.
Прежде чем искать оптимизацию, сосредоточьтесь на правильной функциональности.
В стремлении ОП оптимизировать был создан неправильный код:
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;
}