Loop optimization

[bearophile]

kai:

> I was evaluating using D for some numerical stuff.

For that evaluation you probably have to use the LDC compiler, that is able to optimize better.


> 	void main (string[] args)
> 	{
> 		double [] foo = new double [cast(int)1e6];
> 		for (int i=0;i<1e3;i++)
> 		{
> 			for (int j=0;j<1e6-1;j++)
> 			{
> 				foo[j]=foo[j]+foo[j+1];
> 			}
> 		}
> 	}

Using floating point for indexes and lengths is not a good practice. In D large numbers are written like 1_000_000.
Use -release too.

 
> Any ideas? Am I somehow not hitting a vital compiler optimization?

DMD compiler doesn't perform many optimizations, especially on floating point computations.
But the bigger problem in your code is that you are performing operations on NaNs (that's the default initalization of FP values in D), and operations on NaNs are usually quite slower.


Your code in C:

#include "stdio.h"
#include "stdlib.h"
#define N 1000000

int main() {
    double *foo = calloc(N, sizeof(double)); // malloc suffices here
    int i, j;
    for (j = 0; j < N; j++)
        foo[j] = 1.0;

    for (i = 0; i < 1000; i++)
        for (j = 0; j < N-1; j++)
            foo[j] = foo[j] + foo[j + 1];

    printf("%f", foo[N-1]);
    return 0;
}

/*
gcc -O3 -s -Wall test.c -o test
Timings, outer loop=1_000 times: 7.72

------------------

gcc -Wall -O3 -fomit-frame-pointer -msse3 -march=native test.c -o test
(Running on a VirtualBox)
Timings, outer loop=1_000 times: 7.69 s
Just the inner loop:
.L7:
    fldl    8(%edx)
    fadd    %st, %st(1)
    fxch    %st(1)
    fstpl   (%edx)
    addl    $8, %edx
    cmpl    %ecx, %edx
    jne .L7
*/

--------------------

Your code in D1:

version (Tango)
    import tango.stdc.stdio: printf;
else
    import std.c.stdio: printf;

void main() {
    const int N = 1_000_000;
    double[] foo = new double[N];
    foo[] = 1.0;

    for (int i = 0; i < 1_000; i++)
        for (int j = 0; j < N-1; j++)
            foo[j] = foo[j] + foo[j + 1];

    printf("%f", foo[N-1]);
}


/*
dmd -O -release -inline test.d
(Not running on a VirtualBox)
Timings, outer loop=1_000 times: 9.35 s
Just the inner loop:
L34:    fld qword ptr 8[EDX*8][ECX]
        fadd    qword ptr [EDX*8][ECX]
        fstp    qword ptr [EDX*8][ECX]
        inc EDX
        cmp EDX,0F423Fh
        jb  L34

-----------------------

ldc -O3 -release -inline test.d
(Running on a VirtualBox)
Timings, outer loop=1_000 times: 7.87 s
Just the inner loop:
.LBB1_2:
    movsd   (%eax,%ecx,8), %xmm0
    addsd   8(%eax,%ecx,8), %xmm0
    movsd   %xmm0, (%eax,%ecx,8)
    incl    %ecx
    cmpl    $999999, %ecx
    jne .LBB1_2

-----------------------

ldc -unroll-allow-partial -O3 -release -inline test.d
(Running on a VirtualBox)
Timings, outer loop=1_000 times: 7.75 s
Just the inner loop:
.LBB1_2:
    movsd   (%eax,%ecx,8), %xmm0
    addsd   8(%eax,%ecx,8), %xmm0
    movsd   %xmm0, (%eax,%ecx,8)
    movsd   8(%eax,%ecx,8), %xmm0
    addsd   16(%eax,%ecx,8), %xmm0
    movsd   %xmm0, 8(%eax,%ecx,8)
    movsd   16(%eax,%ecx,8), %xmm0
    addsd   24(%eax,%ecx,8), %xmm0
    movsd   %xmm0, 16(%eax,%ecx,8)
    movsd   24(%eax,%ecx,8), %xmm0
    addsd   32(%eax,%ecx,8), %xmm0
    movsd   %xmm0, 24(%eax,%ecx,8)
    movsd   32(%eax,%ecx,8), %xmm0
    addsd   40(%eax,%ecx,8), %xmm0
    movsd   %xmm0, 32(%eax,%ecx,8)
    movsd   40(%eax,%ecx,8), %xmm0
    addsd   48(%eax,%ecx,8), %xmm0
    movsd   %xmm0, 40(%eax,%ecx,8)
    movsd   48(%eax,%ecx,8), %xmm0
    addsd   56(%eax,%ecx,8), %xmm0
    movsd   %xmm0, 48(%eax,%ecx,8)
    movsd   56(%eax,%ecx,8), %xmm0
    addsd   64(%eax,%ecx,8), %xmm0
    movsd   %xmm0, 56(%eax,%ecx,8)
    movsd   64(%eax,%ecx,8), %xmm0
    addsd   72(%eax,%ecx,8), %xmm0
    movsd   %xmm0, 64(%eax,%ecx,8)
    addl    $9, %ecx
    cmpl    $999999, %ecx
    jne .LBB1_2
*/

As you see the code generated by ldc is about as good as the one generated by gcc. There are of course other ways to optimize this code...

Bye,
bearophile