Как оптимизировать слои косвенности указателя

Question

Я пытаюсь оптимизировать подобные вещи в тяжелых вычислительных приложениях:

скажи, что у меня есть

 double d[500][500][500][500];

и следующее довольно дорого по крайней мере с точки зрения компилятора

double d[x][y][j][k]

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

В моем примере

У меня есть что-то вроде этого:

double n=0;
for (int i=0; i < someNumber; i++)
{
    n+=d[x][i][j][k] /*(some other math calculations)*/;
}

Поэтому я попытался оптимизировать его, поместив в отдельную функцию

void func( double*** const restrict dMatrix )
{
  /* and do some calculations herel*/

}

мало помогло: (

Есть предложения по его оптимизации?

}

Редактировать

Я не могу переписать код, чтобы сделать массив одномерным. Я должен работать с этим многомерным зверем: (

Answer 1

Я подозреваю, что проблема не в расчете смещения, а в фактическом доступе к памяти. Когда вы объявляете 4-мерный массив и получаете доступ к элементам со смежными индексами на любом уровне, кроме последнего, адреса памяти на самом деле довольно далеко друг от друга, и это приводит к большим потерям кэша и значительному замедлению.

Answer 2

Компилятор C наверняка знает, когда память непрерывна. Вам не нужно это говорить.

Answer 3

Обратите внимание, что это много (около 466 ГБ, если моя математика верна) данных, и остерегайтесь проблем с подкачкой и доступом к кешу. Если вы на самом деле не используете 500 ^ 4 элементов, вам нужно профилировать свое приложение, чтобы увидеть, что это действительно «косвенность», которая стоит вам с точки зрения производительности.

Answer 4

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

Answer 5

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

Вероятно, вы можете ускорить его, уменьшив количество пропусков кеша. a[0][?][?][?], вероятно, далеко от a[1][?][?][?].

Answer 6

Как сказал , раскрутите , ваш массив составляет около половины терабайта. Вам нужен достаточно большой диск и достаточно большой файл подкачки. Тогда вам, вероятно, также понадобится чрезвычайно большой объем оперативной памяти. Наконец, размер вашего кэша также имеет значение, поэтому порядок доступа к элементам будет иметь огромное значение. Расчет адреса будет в шуме.

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

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

Кстати, я надеюсь, что вы работаете на 64-битной машине. 32-битный адрес может иметь доступ только к 4 ГБ.

Answer 7

То, что вы могли сделать, чтобы ускорить процесс, это использовать инкрементные указатели для ускорения доступа к массиву.

Итак, используя простой массив.

char aString[500];
for (int i=0; i<500; i++)
    aString[i] = 0;     // Array access is really a multiply!

становится

char aString[500];
char *aStringPtr;
for (aStringPtr= &aString[0] ; aStringPtr<&aString[0]+500; aStringPtr++)
    *aStringPtr = 0;

Это примерно в два раза быстрее, чем в первом примере.