Суммирование массивов с использованием 2 переменных в цикле (и выполнение цикла N / 2 раза) дает более быстрое время выполнения, чем просто одна. Зачем?

Question

У меня есть массив размера РАЗМЕР. Я добавляю его элементы двумя способами.
1. Взять 2 переменные в цикле, запустить одну из индексов 0, а другую из SIZE-1, пока они не пересекутся.
2. Взять 1 переменную и запустить ее от 0 до РАЗМЕРА-1.
Почему первый метод работает значительно быстрее, чем второй.

Я запускаю его в GCC.
Единственное отличие, которое я вижу, это количество сравнений.

Использование 2 переменных

long sum2ptr(int* x, long n) {
    long sum = 0;
    for (int i = 0, j = n-1; i < j; i++, j--) {
        sum += x[i];
        sum += x[j];
    }
    return sum;
}

Это выводит 0,43

Использование 1 переменной

long sum1ptr(int* x, long n) {
    long sum = 0;
    for (int i = 0; i < n; i++)
        sum += x[i];
    return sum;
}  

Это выводит 0,50

Общий код

int main(void)
{
    long SIZE = 100000000;
    double start, time = 0;
    int *a = (int*)malloc(SIZE * sizeof(int));

    for (int i = 0; i < SIZE; i++) 
        a[i] = ((i * 2) + 3) % SIZE;

    start = clock();
    sum2ptr(a, SIZE);//called sum1ptr() on second run.
    time += (clock() - start) / CLOCKS_PER_SEC;

    printf("%lf", time);
    return 0;
}

Я ожидал незначительной разницы между ними. Какова реальная причина такой разницы?

Answer 1

Время выполнения зависит от количества выполненных инструкций. Инструкции предназначены для доступа к памяти (a [i]), суммирования (sum + = a [i]) и управления циклами (I ++, ветвь).

Если количество итераций уменьшается, управление циклами и время выполнения соответственно уменьшаются. То, что вы рассматриваете, является частным случаем классического метода оптимизации кода, называемого «развертывание цикла».

Вот модифицированная версия вашего кода.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


#define profile(x, fn, n) {\
    start = clock(); \
    sum = 0; \
    fn(x, n); \
    time = (clock() - start) / CLOCKS_PER_SEC; \
}

#define sum2ptr(x, n) {\
    for (int i = 0, j = n-1; i < j; i++, j--) { \
        sum += x[i]; \
        sum += x[j]; \
    } \
}


#define sum1ptr(x, n) {\
    for (int i = 0; i < n; i++) \
    sum += x[i]; \
}

#define sum3ptr(x, n) {\
    for (int i = 0; i < n; i+=4){               \
    sum += x[i]; \
    sum += x[i+1]; \
    sum += x[i+2]; \
    sum += x[i+3]; \
  } \
}

#define SIZE 100000000

int main(void)
{
    double start, time = 0;
    int sum = 0;
    int *a = (int*)malloc(SIZE * sizeof(int));

    for (int i = 0; i < SIZE; i++) 
        a[i] = ((i * 2) + 3) % SIZE;

    profile(a, sum1ptr, SIZE);
    printf("%lf (regular)\n", time);
    profile(a, sum2ptr, SIZE);
    printf("%lf (unrolled twice)\n", time);
    profile(a, sum3ptr, SIZE);
    printf("%lf (unrolled 4)\n", time);

    return 0;
}

Я добавил третий цикл, «развернутый» четыре раза (более классическим способом).

Скомпилировано с gcc -O вот результаты.

0.030777 (regular)
0.016292 (unrolled twice)
0.008050 (unrolled 4)

Как видите, развертывание очень эффективно. Результаты даже лучше, чем у вас, из-за оптимизации (-O). Без флагов оптимизации получаем

0.222738 (regular)
0.174113 (unrolled twice)
0.164410 (unrolled 4)

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

Answer 2

sum1ptr посмотрите на все индексы, это не относится к sum2ptr , когда n нечетно, поэтому, конечно, они не вычисляют одно и то же значение

Если я немного изменю твой код для печати используемых индексов:

#include <stdio.h>

#define sum2ptr(n) {\
    for (int i = 0, j = n-1; i < j; i++, j--) { \
        printf("sum2 %d %d\n", i, j); \
    } \
}

#define sum1ptr(n) {\
    for (int i = 0; i < n; i++) \
      printf("sum1 %d\n", i); \
} 


int main()
{
  sum2ptr(3)
  sum1ptr(3)

  return 0;
}

Исполнение:

sum2 0 2
sum1 0
sum1 1
sum1 2

sum2 не смотрите на индекс 1.

Если вы получаете доступ к 2 записям в каждом повороте, размер должен быть четным числом. Если вы посмотрите на 3 записи каждый ход, размер должен быть кратен 3 и т. Д.

---

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

Если я скомпилирую в O2 на raspberrypi pi , немного изменив ваш код, чтобы иметь возможность выбирать регистр в зависимости от наличия аргумента ( argc равно 1 или 2), результат:

pi@raspberrypi:/tmp $ ./a.out 
sum1  0.000011
pi@raspberrypi:/tmp $ ./a.out 
sum1  0.000009
pi@raspberrypi:/tmp $ ./a.out 
sum1  0.000009
pi@raspberrypi:/tmp $ ./a.out 
sum1  0.000013
pi@raspberrypi:/tmp $ ./a.out 
sum1  0.000014
pi@raspberrypi:/tmp $ ./a.out 
sum1  0.000008
pi@raspberrypi:/tmp $ ./a.out 
sum1  0.000012
pi@raspberrypi:/tmp $ ./a.out 
sum1  0.000007
pi@raspberrypi:/tmp $ ./a.out  1
sum2  0.000011
pi@raspberrypi:/tmp $ ./a.out  1
sum2  0.000007
pi@raspberrypi:/tmp $ ./a.out  1
sum2  0.000009
pi@raspberrypi:/tmp $ ./a.out  1
sum2  0.000008
pi@raspberrypi:/tmp $ ./a.out  1
sum2  0.000008
pi@raspberrypi:/tmp $ ./a.out  1
sum2  0.000010
pi@raspberrypi:/tmp $ ./a.out  1
sum2  0.000009

разница времен под точностью