I have following code where a sum is calculated, based on a very large series.
The series char *a
is a char array, which contains digits only (0..9).
I wanted to ask if there is any possibility to make the code faster. It is currently a bottle neck in a distributed computing application.
A small reproduction code. Not the actual code, and more simplified.
int top = 999999999;
char *a;
a = (char*) calloc(top+1, sizeof(char));
// ... fill a with initial values ...
for (int i=0; i<10; ++i) {
unsigned long long int sum = 0;
for (m = 1, k = top; m < k; ++m, --k) {
// Here is the bottle neck!!
sum += a[m]*a[k];
}
printf("%d\n", sum);
// ... Add something at the end of a, and increase top ...
}
I have already tried following:
Optimizing the code with
-O3
(gcc compiler). The compiler line is now:gcc -c -Wall -fopenmp -Wno-unused-function -O3 -std=c99 -g0 -march=native -pipe -D_FILE_OFFSET_BITS=64 -m64 -fwhole-program -fprefetch-loop-arrays -funsafe-loop-optimizations -Wunsafe-loop-optimizations -fselective-scheduling -fselective-scheduling2 -fsel-sched-pipelining -fsel-sched-pipelining-outer-loops -fgcse-sm -fgcse-lm -fgcse-las -fmodulo-sched -fgcse-after-reload -fsee -DLIBDIVIDE_USE_SSE2 -DLIBDIVIDE_USE_SSE4_1 xxx.c -o xxx.o
Using of GNU openMP to split the for-loop to multiple cores
unsigned long long int halfway = (top>>1) + 1; // = top/2 + 1 // digits is defined as top+1 #pragma omp parallel // firstprivate/*shared*/(a, digits, halfway) for (unsigned long long int m = 1; m < halfway; ++m) { sum += a[m] * a[digits-m]; }
Result: Much, much faster, but requires more cores, and I still would like to make it faster.
Casting
a[m]
tounsigned long long int
before multiplicationsum += (unsigned long long int)a[m] * a[k];
Result: A small performance boost.
Using a multiplication lookup table, because an array-lookup is faster than the actual multiplication.
sum += multiply_lookup[a[m]][a[k]]; // a[m]*a[k];
Result: A small performance boost.
I have tried to find a mathematical solution to reduce operations, but it seems like nothing can be optimized, mathematically seen.
I have following idea for optimization:
I have read that the multiplication of floats (asm fmul
) is much faster than the multiplication of integers (asm mul
). Just changing int
to float
doesn't help -- but I think the code might become much more performant if the work is done using MMX or SSE instruction sets, or if the work is done by the FPU. Although I have some assembler knowledge, I have no knowledge about these topics.
However, if you have additional ideas how to optimize it, I am glad to hear them.
Update Some additional information:
- The series grows by 1 element after each loop.
- While the series grows,
top
gets increased. - When
top
is reaching the array limit,a
will get increased by 100000 bytes usingrealloc()
. - Platform: Debian Linux Jessie x64, on an Intel(R) Xeon(R) CPU X3440 @ 2.53GHz
Additional off-topic question: Do you know the mathematical name of this sum, where the pairs of elements of the series are multiplied from outside to inside?