C / C ++ оптимизировать структуры данных, массив массивов или просто массив

Question

Работа с программой, которая использует 16-байтовые матрицы 4 × 4 с одним байтом:

unsigned char matrix[4][4];

и несколько 256-байтовых 16 × 16 однобайтовых матриц:

unsigned char bigMatrix[16][16];

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

Улучшится ли производительность, если я вместо этого использую массив, т.е.

unsigned char matrix[16];
unsigned char matrix[256];

и доступ к элементам с помощью некоторых переменных для извлечения элементов, т.е.

matrix[variableA*variableB + i];

где переменная A * переменная B + i должна пересчитываться каждый раз, когда я хочу получить доступ к элементу.

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

Answer 1

Это не имеет значения. Данные располагаются одинаково в любом случае, и к ним также обращаются одинаково. Я был бы удивлен, если бы он не генерировал точно такую ​​же сборку, даже.

Однако при 256-байтовой таблице вы вряд ли получите ошибки кэша в любом случае. Кэш-память L1 ЦП обычно составляет от 32 до 128 КБ, поэтому я сомневаюсь, что в любом случае вы получаете много ошибок в кэше.

Answer 2

Джалф в основном прав. Кэш-память первого уровня разделена на порции, размер порций зависит от процессора, но составляет порядка 32 байтов. Таким образом, если бы вы шагали по памяти по байтам за раз, вы бы получали пропуск кеша через каждые 32 байта (или любой другой размер фрагмента). Теперь чип Intel довольно умен и способен обнаруживать последовательные операции чтения и предварительной выборки данных, уменьшая последствия пропуска кэша.

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

Матрица 16x16, однако, не помещается в строку кэша. Таким образом, если вы пропустите столбцы обработки массива, вы получите много пропусков кэша. Вычисление индекса, как сказал Джальф, не имеет большого значения, так как соотношение между процессором и памятью велико (т. Е. Вы можете выполнять большую работу с процессором при каждом промахе кэша).

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

  0   1   2 .... 15
 16  17  18 .... 31
....
240 241 242 .... 255

где число - это смещение памяти от начала матрицы, упорядочить так:

 0 16 32 ... 240
 1 17 33 ... 241
 ...
15 31 47 ... 255

Answer 3

Несмотря на то, что скомпилированный код будет вести себя одинаково быстро, существует некоторая проблема проектирования: повторное использование кода индексации может быть максимально увеличено.

Лучший способ сделать это, imho, заключить его в контейнер, который знает, как перебрать его элементы самым быстрым способом. Они получили название для этого: «внутренний итератор», как упоминалось в паттерне GoF Design Patterns «Итератор».

Краткий пример:

 template< int N >
 struct CNxN { 
     typedef int t_row[N];
     typedef t_row t_matrix[N];
     t_matrix m_Contents; 

     template< typename Functor >
     void each( Functor & f ) {
         for( int col = 0; col != N; ++col )
             for( int row = 0; row != N; ++row )
                 f( m_Contents[row][col] );
     }
 };

 // client code
 CNxN<3> matrix = { { {1,1,1},{1,1,1},{1,1,1} } };

 struct sum { 
      long result; 
      sum():result(0){} 
      void operator()( int i ){ result +=i; } 
 };
 matrix.each( sum );
 assert(sum.result==0); 
 assert(has_performed_in_the_fastest_possible_way);//;)

Answer 4

Вы говорите, что variableA*variableB+i необходимо пересчитывать каждый раз, когда вы получаете доступ к элементу, хорошо, что это происходит в любом случае, даже при использовании многомерных массивов. Единственное отличие состоит в том, что в многомерных массивах компилятор генерирует этот код, поэтому вы его не видите, а в одномерном массиве вы видите код в исходном коде.

Answer 5

Очень часто из-за манипуляций с данными меня заставляют циклически обрабатывать столбцы [...]

У вас не может быть обоих способов: циклический цикл или столбец приведут к ошибкам кэша, если матрица «достаточно большая» (см. Skizz 'answer ). Оптимизируйте для типа цикла, который выполняется чаще.

Если потребление памяти не является проблемой, вы можете также рассмотреть вопрос о сохранении как матрицы, так и ее транспонирования.

Answer 6

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

Answer 7

Большой линейный массив может быть немного быстрее, если вы делаете последовательный доступ к массиву, потому что вы сохраняете операцию умножения для каждого индекса. Если вы зацикливаетесь на столбцы, то вы получаете последовательный доступ; по крайней мере, в записи [row] [col], которая была «стандартной» для всех, с кем я когда-либо разговаривал.

Я сомневаюсь, что ваш 256-элементный массив вызовет пропадание кеша на современном оборудовании, но я готов ошибиться. Что говорит Кэггринд?