Memoization сохраняет результаты дорогостоящих вычислений и возвращает кешированный результат, а не непрерывно пересчитывает его.
Вот пример:
def doSomeExpensiveCalculation(self, input):
if input not in self.cache:
self.cache[input] = result
return self.cache[input]
Более полное описание можно найти в записи wikipedia в memoization .
Время выполнения зависит от количества выполненных инструкций. Инструкции предназначены для доступа к памяти (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)
Различия уменьшаются, и, вероятно, это то, что вы добавили, но вы не должны измерять производительность без оптимизации кода.
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
разница времен меньше точности