[Bug c/46186] Clang creates code running 1600 times faster than gcc's

[dominiq at lps dot ens.fr]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46186

--- Comment #21 from Dominique d'Humieres <dominiq at lps dot ens.fr> 
2010-10-26 21:06:48 UTC ---
> I guess you mean LLVM instead of clang,

Yes, if you prefer. I was referring to the command I used.

> F (6, a * a * a * a * a + 2 * a * a * a + 5 * a)

you probably mean

F (6, sum +=a * a * a * a * a + 2 * a * a * a + 5 * a)

> It's a bit more complicated than that, in that you can't just compute 
> (b*(b-1)-a*(a-1)) mod 2^n, then divide by 2, as that will lose the top 
> bit.  (I haven't checked exactly what the generated code is doing here.)

This is right if you do the multiply before the division. However b or b-1 can
be divided exactly by 2, so you have to do (b/2)*(b-1) if b is even and
b*((b-1)/2) if b is odd. The same result applies for the sum of square and
cubes, although you may be one more trick if 2*b+1 wrap and can be divided
exactly by 3.

I have tested the following variant


[macbook] f90/bug% cat pr46186_db.c
#include <stdio.h>

#define len 1000000000L

unsigned long f(unsigned long a, unsigned long b) __attribute__((noinline));

int main()
{    
    unsigned long res;
    res = f(2, 2*len);
/*    printf("%lu\n", res); */
    return 0;
}

unsigned long f(unsigned long a, unsigned long b)
{
    unsigned long sum = 0, sum0 = 0, sum2 = 0, sum5 = 0;
    for (; a < b; a++)
      {
    sum0 += 2;
        sum += a;
    sum2 += a*a;
    sum5 += a*a*a*a*a + 2*a*a*a +5*a;
      }
    printf("%lu\n", sum0);
    printf("%lu\n", sum);
    printf("%lu\n", sum2);
    printf("%lu\n", sum5);
    return sum;
}
 which gives

[macbook] f90/bug% gcc46 -Ofast -ftree-vectorizer-verbose=2 pr46186_db.c

pr46186_db.c:18: note: LOOP VECTORIZED.
pr46186_db.c:15: note: vectorized 1 loops in function.
[macbook] f90/bug% time a.out
3999999996
1999999998999999999
10262176583330622975
11833798674328980984
18.114u 0.012s 0:18.15 99.8%    0+0k 0+0io 0pf+0w
[macbook] f90/bug% clang -O pr46186_db.c
[macbook] f90/bug% time a.out
3999999996
1999999998999999999
10262176583330622975
11833798674328980984
0.000u 0.000s 0:00.00 0.0%    0+0k 0+0io 0pf+0w

So the wrapping seems properly handled for the loop replacement.

Now I have also tested the following variant


[macbook] f90/bug% cat pr46186_db_1.c
#include <stdio.h>

#define len 1000000000L

unsigned long f(unsigned long a, unsigned long b) __attribute__((noinline));

int main()
{    
    unsigned long res;
    res = f(2, 2*len);
/*    printf("%lu\n", res); */
    return 0;
}

unsigned long f(unsigned long a, unsigned long b)
{
    unsigned long sum = 0, sum0 = 0, sum2 = 0, sum5 = 0;
    unsigned long a2;
    for (; a < b; a++)
      {
    sum0 += 2;
        sum += a;
    a2 = a*a;
    sum2 += a2;
    sum5 += a*(a2*(a2 + 2) +5);
      }
    printf("%lu\n", sum0);
    printf("%lu\n", sum);
    printf("%lu\n", sum2);
    printf("%lu\n", sum5);
    return sum;
}

and the timings are

[macbook] f90/bug% gcc46 -Ofast -ftree-vectorizer-verbose=2 pr46186_db_1.c

pr46186_db_1.c:19: note: LOOP VECTORIZED.
pr46186_db_1.c:15: note: vectorized 1 loops in function.
[macbook] f90/bug% time a.out
3999999996
1999999998999999999
10262176583330622975
11833798674328980984
12.227u 0.016s 0:12.36 98.9%    0+0k 0+0io 0pf+0w  <== was 18.114u 0.012s
0:18.15 without
hand optimization
[macbook] f90/bug% clang -O pr46186_db_1.c
[macbook] f90/bug% time a.out
3999999996
1999999998999999999
10262176583330622975
11833798674328980984
0.000u 0.000s 0:00.00 0.0%    0+0k 0+0io 0pf+0w

So clearly gcc is missing some generic optimizations in products.