www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 7844] New: for-loop end-condition optimization

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7844

           Summary: for-loop end-condition optimization
           Product: D
           Version: D2
          Platform: All
        OS/Version: Linux
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: minas_mina1990 hotmail.co.uk



I have recently made a program that finds the sum of all primes (they are 11)
that truncable from left to right and from right to left.

I compiled it with -O -release -inline -noboundscheck
The results were:
real    0m1.659s
user    0m1.652s
sys    0m0.000s

I made a few changes to make it compile as C code, and compiled in gcc with -O5
-lm -std=c99. The results:
real    0m0.764s
user    0m0.760s
sys    0m0.004s

There's ~900 ms difference here, which is big.

The problem is in a function I used, "isPrime(ulong)"

/// returns true if n is a prime number
bool isPrime(ulong n)
{
    // 0 and 1 aren't primes
    if( n < 2 ) return false;

    if( n % 2 == 0 && n != 2)
        return false; // an even number can't be a prime (except 2)

    // check only if it's odd
    for(ulong i = 2; i <= cast (ulong)sqrt(cast(double)n+1); ++i)
        if( n % i == 0 )
            return false;

    return true;
}

As you can see, in the for loop, sqrt() is called in every iteration and that's
what makes it slower. When changed to:
ulong limit = cast (ulong)sqrt(cast(double)n+1)
for(ulong i = 2; i <= limit; ++i)

It performs in 400ms!!!

Somehow the C version manages to do that sort of optimizations. I expect DMD to
do it as well, as it makes the code A LOT faster.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 06 2012
parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=7844


timon.gehr gmx.ch changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |timon.gehr gmx.ch
            Summary|for-loop end-condition      |implement loop invariant
                   |optimization                |code motion for pure
                   |                            |functions



This optimization is called loop invariant code motion.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 06 2012