оптимизировать 2D массив в C ++

Question

Я имею дело с 2D-массивом со следующими характеристиками:

const int cols = 500; 
const int rows = 100; 
int arr[rows][cols];

Чтобы получить некоторую работу, я обращаюсь к массиву arr следующим образом:

for(int k = 0; k < T; ++k) { // for each trainee
  myscore[k] = 0;
  for(int i = 0; i < cols; ++i) { // for each sample  
    for(int j = 0; j < rows; ++j) { // for each expert
      myscore[k] += delta(i, anotherArray[k][i], arr[j][i]);
    }   
  }
}

Так что я беспокоюсь о массиве 'arr', а не о другом. Мне нужно сделать это более удобным для кэша, а также повысить скорость. Я думал, возможно, перенести массив, но я не был уверен, как это сделать. Моя реализация работает только для квадратных матриц. Как бы я сделал это для неквадратных матриц?

Кроме того, повысит ли производительность отображение двумерного массива в одномерный массив? Если так, то как бы я это сделал? Наконец, любой другой совет о том, как еще я могу оптимизировать это ... У меня закончились идеи, но я знаю, что arr [j] [i] - это место, где мне нужно вносить изменения, потому что я получаю доступ к столбцам с помощью столбцы, а не строки за строками, так что кеш совсем не подходит.

Спасибо, Христо

Answer 1

Да, 1d должен быть быстрее, чем 2d. Массивы C и C ++ всегда 1d (внутренне). Когда вы звоните что-то вроде

array[row][col]

компилятор фактически вычисляет

col + row * maxcols

и использует это в качестве фактического индекса 1d массива. Вы могли бы также сделать это самостоятельно. Циклический переход по всему массиву будет намного быстрее, а произвольный доступ будет таким же быстрым, как и в 2d массиве.

Answer 2

Общее транспонирование матрицы на месте очень сложно, но если вы можете перенести его в другой массив, тогда все довольно просто.

const int cols = 500; 
const int rows = 100; 

int arr[rows][cols];
// fill arr[][]

int arrT[cols][rows];
for (int r = 0; r < rows; r++) {
   for (int c = 0; c < cols; c++) {
      arrT[c][r] = arr[r][c];
   }
}

Конечно, в зависимости от того, как вы получаете arr[][], вы можете просто вместо этого заполнить arrT[][].

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

for(int k = 0; k < T; ++k) { // for each trainee
  myscore[k] = 0;
  for(int j = 0; j < rows; ++j) { // for each expert
    for(int i = 0; i < cols; ++i) { // for each sample  
      myscore[k] += delta(i, anotherArray[k][i], arr[j][i]);
    }   
  }
}

Answer 3

  for(int i = 0; i < N; ++i) { // for each sample  
    for(int j = 0; j < E[i]; ++j) { // for each expert
      ... arr[j][i] ... // each ++j causes a large stride => poor caching
    }   
  }

транспонировать петли:

  for(int j = 0; j < E[i]; ++j) { // for each expert
    for(int i = 0; i < N; ++i) { // for each sample  
      ... arr[j][i] ... // each ++i looks to the next word in memory => good
    }   
  }

Конечно, не видя всего остального в программе, я не могу сказать, вызовет ли это проблему. Если delta не имеет побочных эффектов, с вами все будет в порядке.

Answer 4

Вы хотите, чтобы доступ к памяти был смежным. В вашем случае просто поменяйте местами I и j при доступе к обр.