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