Советы по оптимизации

Question

int *s;
allocate memory for s[100];
void func (int *a, int *b)
{
    int i;

    for (i = 0; i < 100; i++)
    {
        s[i] = a[i] ^ b[i];
    }
}

Предположим, что этот конкретный фрагмент кода вызывается 1000 раз, и это самая трудоемкая операция в моем коде. Также предположим, что адреса a и b меняются каждый раз. 's' - это глобальная переменная, которая обновляется различными наборами значений a & b.

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

Не могли бы вы предложить, как я могу оптимизировать мой код наилучшим образом?

вопрос, который я действительно хотел задать, но я думаю, что он не был передан должным образом, например, цикл for содержит 10 таких операций XOR, число циклов равно 100 и функция вызывается 1000 раз высокий уровень доступа к памяти. Если код должен быть выполнен на одноядерном компьютере, каковы возможности для улучшения?

Answer 1

Я протестировал предложенные решения и два других.Я не смог протестировать предложение onemasse, поскольку результат, сохраненный в s [], был неверным.Я тоже не смог это исправить.Я должен был сделать некоторые изменения в коде лунной тени.Единица измерения - тактовые циклы, поэтому чем ниже, тем лучше.

Исходный код:

#define MAX 100
void inline STACKO ( struct timespec *ts, struct timespec *te ){

    int i, *s, *a, *b;

    for (i = 0; i < MAX; ++i){
        s = (int *) malloc (sizeof (int)); ++s;
        a = (int *) malloc (sizeof (int)); ++a;
        b = (int *) malloc (sizeof (int)); ++b;
    }

    srand ( 1024 );
    for (i = 0; i < MAX; ++i){
        a[i] = ( rand() % 2 );
        b[i] = ( rand() % 2 );
    }

    rdtscb_getticks ( ts ); /* start measurement */

    for (i = 0; i < MAX; i++)
        s[i] = a[i] ^ b[i];

    rdtscb_getticks ( te ); /* end measurement */

/*
    printf("\n");
    for (i = 0; i < MAX; ++i)
        printf("%d", s[i]);
    printf("\n");
*/
}

Новое предложение 1: зарегистрируйте int

С:

int i, *s, *a, *b;

Кому:

register int i, *s, *a, *b;

Новое предложение 2: Нет обозначения массива

s_end = &s[MAX];
for (s_ptr = &s[0], a_ptr = &a[0], b_ptr = &b[0]; \
   s_ptr < s_end; \
   ++s_ptr, ++a_ptr, ++b_ptr){
    *s_ptr = *a_ptr ^ *b_ptr;
}

Предложенная оптимизация лунной тени:

s_ptr = &s[0];
a_ptr = &a[0];
b_ptr = &b[0];

for (i = 0; i < (MAX/4); i++){

    s_ptr[0] = a_ptr[0] ^ b_ptr[0];
    s_ptr[1] = a_ptr[1] ^ b_ptr[1];
    s_ptr[2] = a_ptr[2] ^ b_ptr[2];
    s_ptr[3] = a_ptr[3] ^ b_ptr[3];
    s_ptr+=4; a_ptr+=4; b_ptr+=4;
}

Предложенная оптимизация лунной тени + зарегистрируйте int:

От:

int i, *s, ...

До:

register int i, *s, ...

Предложенная Кристоффером оптимизация:

#pragma omp for
for (i = 0; i < MAX; i++)
{
    s[i] = a[i] ^ b[i];
}

Результаты:

Original Code   1036.727264
New Proposal 1  611.147928
New proposal 2  450.788845
moonshadow      713.3845
moonshadow2     452.481192
Christoffer     1054.321943

Есть и другиепростой способ оптимизации полученного двоичного файла.Передача -O2 в gcc говорит о том, что вы хотите оптимизировать.Чтобы точно знать, что делает -O2, обратитесь к справочной странице gcc.

После включения -O2:

Original Code   464.233031
New Proposal 1  452.620255
New proposal 2  454.519383
moonshadow      428.651083
moonshadow2     419.317444
Christoffer     452.079057

Исходные коды доступны по адресу: http://goo.gl/ud52m

Answer 2

Не используйте переменную цикла для индексации. Разверните цикл.

for (i = 0; i < (100/4); i++)
{
  s[0] = a[0] ^ b[0];
  s[1] = a[1] ^ b[1];
  s[2] = a[2] ^ b[2];
  s[3] = a[3] ^ b[3];
  s+=4; a+=4; b+=4;
}

Узнайте, как выполнить SIMD XOR на вашей платформе.

Выполнение этих XOR в качестве явного шага потенциально более затратно, чем выполнение их в рамках другого вычисления: вам нужно читать из a и b и сохранять результат в s - если s читается снова для дальнейшего вычисления, вы сохранил бы чтение и запись для каждой итерации, а также все вызовы функций и издержки цикла, выполнив вместо этого XOR; аналогично, если a и b являются выходами некоторых других функций, вы добьетесь большего успеха, выполнив XOR в конце одной из этих функций.

Answer 3

Просто предположение здесь. Если это проблема с кешем, попробуйте следующее:

int *s;
allocate memory for s[100];
void func (int *a, int *b)
{
    int i;

    memcpy( s, a, 100 );

    for (i = 0; i < 100; i++)
    {
        s[i] = s[i] ^ b[i];
    }
}

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

Answer 4

int *s;
allocate memory for s[100];
void func (int *a, int *b)
{
    int i;

    #pragma omp for
    for (i = 0; i < 100; i++)
    {
        s[i] = a[i] ^ b[i];
    }
}

Конечно, только для ста элементов вы можете не увидеть каких-либо особых улучшений: -)