Loop optimization

[Lars T. Kyllingstad]

On Fri, 14 May 2010 02:38:40 +0000, kai wrote:

> Hello,
> 
> I was evaluating using D for some numerical stuff. However I was
> surprised to find that looping & array indexing was not very speedy
> compared to alternatives (gcc et al). I was using the DMD2 compiler on
> mac and windows, with -O -release. Here is a boiled down test case:
> 
> 	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];
> 			}
> 		}
> 	}
> 
> Any ideas? Am I somehow not hitting a vital compiler optimization?
> Thanks for your help.

Two suggestions:


1. Have you tried the -noboundscheck compiler switch?  Unlike C, D checks
that you do not try to read/write beyond the end of an array, but you can
turn those checks off with said switch.


2. Can you use vector operations?  If the example you gave is
representative of your specific problem, then you can't because you are
adding overlapping parts of the array.  But if you are doing operations on
separate arrays, then array operations will be *much* faster.

    http://www.digitalmars.com/d/2.0/arrays.html#array-operations

As an example, compare the run time of the following code with the example
you gave:

    void main ()
    {
        double[] foo = new double [cast(int)1e6];
        double[] slice1 = foo[0 .. 999_998];
        double[] slice2 = foo[1 .. 999_999];

        for (int i=0;i<1e3;i++)
        {
            // BAD, BAD, BAD.  DON'T DO THIS even though
            // it's pretty awesome:
            slice1[] += slice2[];
        }
    }

Note that this is very bad code, since slice1 and slice2 are overlapping
arrays, and there is no guarantee as to which order the array elements are
computed -- it may even occur in parallel.  It was just an example of the
speed gains you may expect from designing your code with array operations
in mind.

-Lars