тест производительности между двумя направлениями двумерного массива

Question

Этот код (A) выполняется намного быстрее (в 10 раз), чем второй:

for(int w=0; w<width; w++) {
        for(int h=1; h<height; h++) {
            image[h][w] = (1-a)*image[h][w] + a*image[h-1][w];
        }
    }

Второй:

for(int h=0; h<height; h++) {
        for(int w=1; w<width; w++) {
            image[h][w] = (1-a)*image[h][w] + a*image[h][w-1];
        }
    }

Почему это? это то же самое, что пройти по всем пикселям изображения в горизонтальном или вертикальном направлении.

Есть ли способ ускорить второй?

Заранее спасибо.

Answer 1

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

Вышесказанное объясняет, что вторая версия быстрее первой, и это именно то, что происходит на моей коробке:

aix@aix:~$ time ./ver1
real    0m29.421s

aix@aix:~$ time ./ver2
real    0m2.198s

Вот код, который я использую для выделения массива:

  double a = 0.5;
  int width = 2048;
  int height = 2048;
  double* data = new double[height * width];
  double** image = new double*[height];
  for (int i = 0; i < height; i++) {
    image[i] = data + i * width;
  }

Версия 1 раз следующий цикл:

  for (int iter = 0; iter < 100; iter++) {
    for(int w=0; w<width; w++) {
      for(int h=1; h<height; h++) {
        image[h][w] = (1-a)*image[h][w] + a*image[h-1][w];
      }
    }
  }

Цикл версии 2:

  for (int iter = 0; iter < 100; iter++) {
    for(int h=0; h<height; h++) {
      for(int w=1; w<width; w++) {
        image[h][w] = (1-a)*image[h][w] + a*image[h][w-1];
      }
    }
  }

Скомпилировано с g++ 4.4.3 с -O3 и запущено на коробке Xeon некоторого описания (64-битная Ubuntu).

Если вы все еще на 100% уверены, что видите эффект , противоположный , должно быть что-то принципиально иное в том, что вы делаете, по сравнению с тем, что я делаю. Это может помочь, если вы сообщите нам размеры вашего изображения и как именно оно будет выделено (для того, чтобы помочь установить структуру памяти).

Answer 2

Экс прав насчет места ссылки.Чтобы быть более точным, это из-за иерархии памяти.

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

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

Для малого N все это заканчивается в кэше, и это не 'не имеет большого значения о направлении.При достаточно большом N не весь массив может уместиться в самую быструю (и наименьшую) часть кэша, поэтому строка кэша, содержащая элемент i, может быть отброшена перед доступом к i + M * N и должна быть перезагружена перед доступом к i+ 1.

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