локальность данных для реализации 2d массива в c / Stack Overflow
Давным-давно, вдохновленный «Числовыми рецептами в Си», я начал использовать следующую конструкцию для хранения матриц (2D-массивов).
double **allocate_matrix(int NumRows, int NumCol)
{
double **x;
int i;
x = (double **)malloc(NumRows * sizeof(double *));
for (i = 0; i < NumRows; ++i) x[i] = (double *)calloc(NumCol, sizeof(double));
return x;
}
double **x = allocate_matrix(1000,2000);
x[m][n] = ...;
Но недавно заметил, что многие люди реализуют матрицы следующим образом
double *x = (double *)malloc(NumRows * NumCols * sizeof(double));
x[NumCol * m + n] = ...;
С точки зрения локальности второй метод кажется идеальным, но он имеет отличную читабельность … Итак, я начал задаваться вопросом, является ли мой первый метод хранения вспомогательного массива или **double действительно плохие указатели или компилятор в конечном итоге оптимизирует его так, что он будет более или менее эквивалентен по производительности второму методу? Я подозреваю, потому что я думаю, что в первом методе два перехода сделаны при доступе к значению, x[m] а потом x[m][n] и есть вероятность, что каждый раз, когда процессор будет загружаться первым x массив, а затем x[m] массив.
постскриптум не беспокойтесь о дополнительной памяти для хранения **doubleдля больших матриц это всего лишь небольшой процент.
P.P.S. так как многие люди не очень хорошо поняли мой вопрос, я постараюсь изменить его: правильно ли я понимаю, что первый метод является своего рода адским местом, когда каждый раз x[m][n] первый доступ x массив будет загружен в кэш процессора, а затем x[m] массив будет загружен, таким образом, делая каждый доступ со скоростью общения с оперативной памятью. Или я ошибаюсь, и первый метод тоже подходит с точки зрения локальности данных?
Решение
Для распределения в стиле C вы можете получить лучшее из обоих миров:
double **allocate_matrix(int NumRows, int NumCol)
{
double **x;
int i;
x = (double **)malloc(NumRows * sizeof(double *));
x[0] = (double *)calloc(NumRows * NumCol, sizeof(double)); // <<< single contiguous memory allocation for entire array
for (i = 1; i < NumRows; ++i) x[i] = x[i - 1] + NumCols;
return x;
}
Таким образом, вы получаете локальность данных и связанные с ней преимущества доступа к кешу / памяти, и вы можете рассматривать массив как double ** или сплющенный 2D-массив (array[i * NumCols + j]взаимозаменяемо. У тебя тоже меньше calloc/free звонки (2 против NumRows + 1).
Другие решения
Не нужно угадывать, будет ли компилятор оптимизировать первый метод. Просто используйте второй метод, который вы знать быстрый и использует класс-оболочку, который реализует, например, эти методы:
double& operator(int x, int y);
double const& operator(int x, int y) const;
… и получить доступ к вашим объектам, как это:
arr(2, 3) = 5;
В качестве альтернативы, если вы можете нести немного большую сложность кода в классе (ах) обертки, вы можете реализовать класс, к которому можно обращаться с более традиционным arr[2][3] = 5; синтаксис. Это реализовано независимым от измерения способом в библиотеке Boost.MultiArray, но вы также можете сделать свою собственную простую реализацию, используя прокси-класс.
Замечания: Учитывая ваше использование стиля C (жестко запрограммированный неуниверсальный тип «double», простые указатели, объявления переменных начала функции и malloc), вам, вероятно, потребуется больше узнать о конструкциях C ++, прежде чем вы сможете реализовать любой из упомянутых мной вариантов.
Два метода совершенно разные.
- В то время как первый метод упрощает прямой доступ к значениям, добавляя еще одно косвенное
double**массив, следовательно, вам нужно 1 + N mallocs), … - второй метод гарантирует, что ВСЕ значения хранятся непрерывно и требуют только одного malloc.
Я бы сказал, что второй метод всегда лучше. Malloc — дорогостоящая операция, а непрерывная память — огромный плюс, в зависимости от приложения.
В C ++ вы бы просто реализовали это так:
std::vector<double> matrix(NumRows * NumCols);
matrix[y * numCols + x] = value; // Access
и если вас беспокоит необходимость самостоятельно вычислять индекс, добавьте оболочку, которая реализует operator(int x, int y) к этому.
Вы также правы, что первый метод более дорог при доступе к значениям. Потому что вам нужно два поиска памяти, как вы описали x[m] а потом x[m][n], Компилятор не сможет «оптимизировать это». Первый массив, в зависимости от его размера, будет кэширован, и производительность может быть не такой уж плохой. Во втором случае вам понадобится дополнительное умножение для прямого доступа.
В первом методе, который вы используете, double* в главном массиве указывать на логические столбцы (массивы размера NumCol).
Итак, если вы напишите что-то вроде ниже, вы получите преимущества локальности данных в некотором смысле (псевдокод):
foreach(row in rows):
foreach(elem in row):
//Do something
Если вы попробовали то же самое со вторым методом, и если доступ к элементу был выполнен так, как вы указали (т.е. x[NumCol*m + n]), вы все равно получите такое же преимущество. Это потому, что вы относитесь к массиву в основном порядке строк. Если вы пытались использовать тот же псевдокод при доступе к элементам в мажорном столбце, я предполагаю, что вы получите ошибки кэша, учитывая, что размер массива достаточно велик.
В дополнение к этому второй метод обладает дополнительным желательным свойством быть единым непрерывным блоком памяти, что дополнительно повышает производительность, даже когда вы проходите через несколько строк (в отличие от первого метода).
Итак, в заключение, второй метод должен быть намного лучше с точки зрения производительности.
Если NumCol является константой времени компиляции, или если вы используете GCC с включенными языковыми расширениями, то вы можете сделать:
double (*x)[NumCol] = (double (*)[NumCol]) malloc(NumRows * sizeof (double[NumCol]));
а затем использовать x как двумерный массив, и компилятор выполнит для вас арифметику индексации. Предостережение заключается в том, что, если NumCol не является константой времени компиляции, ISO C ++ не позволит вам сделать это, и если вы используете расширения языка GCC, вы не сможете перенести свой код на другой компилятор.