Can the multiplication of chars/digits be made more performant? <p>I have following code where a sum is calculated, based on a very large series.</p> <p>The series <code>char *a</code> is a char array, which contains digits only (0..9).</p> <p>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.</p> <p>A small reproduction code. Not the actual code, and more simplified.</p> <pre><code>int top = 999999999; char *a; a = (char*) calloc(top+1, sizeof(char)); // ... fill a with initial values ... for (int i=0; i&lt;10; ++i) { unsigned long long int sum = 0; for (m = 1, k = top; m &lt; 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 ... } </code></pre> <p><strong>I have already tried following:</strong></p> <ol> <li><p>Optimizing the code with <code>-O3</code> (gcc compiler). The compiler line is now:</p> <pre><code>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 </code></pre></li> <li><p>Using of <a href="https://gcc.gnu.org/wiki/openmp">GNU openMP</a> to split the for-loop to multiple cores</p> <pre><code>unsigned long long int halfway = (top&gt;&gt;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 &lt; halfway; ++m) { sum += a[m] * a[digits-m]; } </code></pre> <p>Result: Much, much faster, but requires more cores, and I still would like to make it faster.</p></li> <li><p>Casting <code>a[m]</code> to <code>unsigned long long int</code> before multiplication</p> <pre><code>sum += (unsigned long long int)a[m] * a[k]; </code></pre> <p>Result: A small performance boost.</p></li> <li><p>Using a multiplication lookup table, because an array-lookup is faster than the actual multiplication.</p> <pre><code>sum += multiply_lookup[a[m]][a[k]]; // a[m]*a[k]; </code></pre> <p>Result: A small performance boost.</p></li> <li><p>I have tried to find a mathematical solution to reduce operations, but it seems like nothing can be optimized, mathematically seen.</p></li> </ol> <p><strong>I have following idea for optimization:</strong></p> <p>I <a href="http://computer-programming-forum.com/46-asm/5d298759ca2e2d44.htm">have read</a> that the multiplication of floats (asm <code>fmul</code>) is much faster than the multiplication of integers (asm <code>mul</code>). Just changing <code>int</code> to <code>float</code> 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.</p> <p>However, if you have additional ideas how to optimize it, I am glad to hear them.</p> <p><strong>Update</strong> Some additional information:</p> <ul> <li>The series grows by 1 element after each loop.</li> <li>While the series grows, <code>top</code> gets increased.</li> <li>When <code>top</code> is reaching the array limit, <code>a</code> will get increased by 100000 bytes using <code>realloc()</code>.</li> <li>Platform: Debian Linux Jessie x64, on an Intel(R) Xeon(R) CPU X3440 @ 2.53GHz</li> </ul> <p><strong>Additional off-topic question:</strong> Do you know the mathematical name of this sum, where the pairs of elements of the series are multiplied from outside to inside?</p>