Оптимизация для скорости - 4 размерных поиска массива в C

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

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

Единственное, что вы можете сделать, это поработать над местностью: прочтите этот , он должен вдохновить вас.

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

Удачи

Вы могли бы немного выжать, развернув петлю в каком-нибудь варианте устройства Даффса.

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

У меня есть пара предложений:

unsigned int lookup_array[26][26][26][26]; /* lookup_array is a global variable */

unsigned int get_i_score(unsigned int *input, len) {
register unsigned int i, score = 0;
unsigned int *a=input;
unsigned int *b=input+1;
unsigned int *c=input+2;
unsigned int *d=input+3;

for(i = 0; i < (len - 3); i++, a++, b++, c++, d++) 
    score += lookup_array[*a][*b][*c][*d];

return(score)
}

Или попробуйте

for(i = 0; i < (len - 3); i++, a=b, b=c, c=d, d++) 
    score += lookup_array[*a][*b][*c][*d];

Кроме того, учитывая, что есть только 26 значений, почему вы помещаете входной массив с точки зрения беззнаковых целых чисел? Если бы это был char * input , вы бы использовали 1/4 объема памяти и, следовательно, 1/4 пропускной способности памяти. Очевидно, что типы от a до d должны совпадать. Точно так же, если значения оценки не должны быть беззнаковыми целыми числами, уменьшите массив, используя символы или uint16_t.

, если lookup_array в основном нули, его можно по умолчанию заменить поиском по хеш-таблице на меньшем массиве. Встроенная функция поиска может вычислить смещение 4-х измерений ([5,6,7,8] = (4 * 26 * 26 * 26) + (5 * 26 * 26) + (6 * 26) +7 = 73847). хеш-ключ может быть просто несколькими младшими битами смещения (в зависимости от того, насколько разреженным будет массив). если смещение существует в хеш-таблице, используйте значение, если его нет, то 0 ...

цикл также можно развернуть, используя что-то вроде этого, если вход имеет произвольную длину. требуется только len доступов к вводу (вместо len * 4 в исходном цикле).

register int j, x1, x2, x3, x4;
register unsigned int *p;

p = input;
x1 = *p++;
x2 = *p++;
x3 = *p++;

for (j = (len - 3) / 20; j--; ) {
  x4 = *p++;
  score += lookup_array[x1][x2][x3][x4];
  x1 = *p++;
  score += lookup_array[x2][x3][x4][x1];
  x2 = *p++;
  score += lookup_array[x3][x4][x1][x2];
  x3 = *p++;
  score += lookup_array[x4][x1][x2][x3];

  x4 = *p++;
  score += lookup_array[x1][x2][x3][x4];
  x1 = *p++;
  score += lookup_array[x2][x3][x4][x1];
  x2 = *p++;
  score += lookup_array[x3][x4][x1][x2];
  x3 = *p++;
  score += lookup_array[x4][x1][x2][x3];

  x4 = *p++;
  score += lookup_array[x1][x2][x3][x4];
  x1 = *p++;
  score += lookup_array[x2][x3][x4][x1];
  x2 = *p++;
  score += lookup_array[x3][x4][x1][x2];
  x3 = *p++;
  score += lookup_array[x4][x1][x2][x3];

  x4 = *p++;
  score += lookup_array[x1][x2][x3][x4];
  x1 = *p++;
  score += lookup_array[x2][x3][x4][x1];
  x2 = *p++;
  score += lookup_array[x3][x4][x1][x2];
  x3 = *p++;
  score += lookup_array[x4][x1][x2][x3];

  x4 = *p++;
  score += lookup_array[x1][x2][x3][x4];
  x1 = *p++;
  score += lookup_array[x2][x3][x4][x1];
  x2 = *p++;
  score += lookup_array[x3][x4][x1][x2];
  x3 = *p++;
  score += lookup_array[x4][x1][x2][x3];

  /* that's 20 iterations, add more if you like */
}

for (j = (len - 3) % 20; j--; ) {
  x4 = *p++;
  score += lookup_array[x1][x2][x3][x4];
  x1 = x2;
  x2 = x3;
  x3 = x4;
}

Если вы конвертируете его в плоский массив размером 26 * 26 * 26 * 26, вам нужно будет найти только массив input один раз за цикл:

unsigned int get_i_score(unsigned int *input)
{
    unsigned int i = len - 3, score = 0, index;

    index = input[i] * 26 * 26 +
            input[i + 1] * 26 +
            input[i + 2];

    while (--i)
    {
        index += input[i] * 26 * 26 * 26;
        score += lookup_array[index];
        index /= 26 ;
    }

    return score;
}

Дополнительные затраты - это умножение и деление. Окажется ли он быстрее на практике - вам придется проверить.

(Кстати, ключевое слово register часто игнорируется современными компиляторами - обычно лучше оставить распределение регистров на усмотрение оптимизатора).

Возможно, вы сможете исключить доступ к массиву input , используя локальные переменные.

unsigned int lookup_array[26][26][26][26]; /* lookup_array is a global variable */

unsigned int get_i_score(unsigned int *input, unsigned int len) {
    unsigned int i, score, a, b, c, d;

    score = 0;
    a = input[i + 0];
    b = input[i + 1];
    c = input[i + 2];
    d = input[i + 3];
    for (i = len - 3; i-- > 0; ) {
        d = c, c = b, b = a, a = input[i];
        score += lookup_array[a][b][c][d];
    }

    return score;
}

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

Несколько предложений по улучшению производительности:

• Распараллеливание. Это очень простое сокращение, которое можно запрограммировать в OpenMP или MPI.
• Упорядочить данные для улучшения локальности. Попробуйте, например, сначала сортировать input.
• Используйте инструкции потоковой обработки, если компилятор еще не делает этого.

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

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

Помните, что массивы C / C ++ хранятся в строчном порядке . Не забывайте хранить свои данные так, чтобы адреса, на которые есть ссылки во времени, постоянно находились в памяти. Например, может иметь смысл хранить подрезультаты во временном массиве. Тогда вы сможете обработать ровно один ряд элементов, расположенных последовательно. Таким образом, кэш процессора всегда будет содержать строку во время итераций, и потребуется меньше операций с памятью. Однако вам может потребоваться модульность функции lookup_array. Может быть, даже разделить его на четыре (по количеству измерений в вашем массиве).

Многоместные массивы часто ограничивают компилятор одной или несколькими операциями умножения. Это может быть медленным на некоторых процессорах. Обычным обходным решением является преобразование N-мерного массива в массив указателей на элементы (N-1) размерности. С 4-мерным массивом это довольно раздражает (26 указателей на 26*26 указателей на 26*26*26 строк...) Я предлагаю попробовать и сравнить результат. Не гарантирую, что это быстрее: компиляторы довольно умны в оптимизации доступа к массиву, а цепочка косвенных обращений имеет большую вероятность аннулировать кэш.

Пока

Сильно ли меняется содержимое массива? Возможно, было бы быстрее предварительно рассчитать оценку, а затем изменять ее каждый раз при изменении массива? Подобно тому, как вы можете материализовать представление в SQL с помощью триггеров.