[llvm-bugs] [Bug 123649] Poor performance for Romberg's method

[LLVM Bugs via llvm-bugs]

Issue	123649
Summary	Poor performance for Romberg's method
Labels	new issue
Assignees
Reporter	thesamesam

    This is a companion bug of a GCC bug I've just filed (https://gcc.gnu.org/PR118570).

This was reported on IRC by `trn` who observed that with GCC, this testcase completes much quicker at -O2 than at -O3. For Clang, it always has the bad-case performance that we currently see with GCC -O3.

```c
#include <stdio.h>
#include <math.h>

#define MAX_STEPS 10
#define I_OP sin

static double
romberg(a, b, acc)
double a;
double b;
double acc;
{
  long i, j, k, ep;
  double R1[MAX_STEPS], R2[MAX_STEPS];
  double *Rp = &R1[0], *Rc = &R2[0];
  double h = b - a;
  double c, n_k;
  double *rt;
  Rp[0] = (I_OP(a) + I_OP(b)) * h * 0.5;

  for (i = 1; i < MAX_STEPS; ++i) {
      h = h / 2.0;
      c = 0;
      ep = 1 << (i - 1);

      for (j = 1; j <= ep; ++j)
        c = c + I_OP(a + (2 * j - 1) * h);

      Rc[0] = h * c + 0.5 * Rp[0];

      for (j = 1; j <= i; ++j) {
        n_k = 1;
        for (k = 0; k < j; ++k)
          n_k *= 4;
        Rc[j] = (n_k * Rc[j - 1] - Rp[j - 1]) / (n_k - 1);
      }

      if (i > 1 && fabs(Rp[i - 1] - Rc[i]) < acc)
        return Rc[i];

      rt = Rp;
      Rp = Rc;
      Rc = rt;
  }

  return Rp[MAX_STEPS - 1];
}

int
main()
{
  double a = 0.0;
  double b = 3.14159265358979323846264338327950288419716939937510;
  double c = 2.71828182845904523536028747135266249775724709369995;
  double acc = 1e-6;
  long l;
  double x = 0.001;

  for (l = 0; l <= 2500000; l++)
    x = x + romberg(a, b, acc) * romberg(a, c, acc);
  printf("%.15lf\n", x);

  return 0;
}
```

```
$ clang -O2 rom3.c -o rom3 -lm && time ./rom3
rom3.c:33:1: warning: a function definition without a prototype is deprecated in all versions of C and is not supported in C23 [-Wdeprecated-non-prototype]
   33 | romberg(a, b, acc)
      | ^
1 warning generated.
9558673.398323269560933

real    0m2.550s
user    0m2.508s
sys     0m0.014s

$ clang -O3 rom3.c -o rom3 -lm && time ./rom3
rom3.c:33:1: warning: a function definition without a prototype is deprecated in all versions of C and is not supported in C23 [-Wdeprecated-non-prototype]
   33 | romberg(a, b, acc)
      | ^
1 warning generated.
9558673.398323269560933

real    0m2.499s
user    0m2.461s
sys     0m0.015s

$ gcc -O2 rom3.c -o rom3 -lm && time ./rom3
rom3.c: In function ‘romberg’:
rom3.c:33:1: warning: old-style function definition [-Wold-style-definition]
   33 | romberg(a, b, acc)
      | ^~~~~~~
9558673.398323269560933

real    0m0.018s
user    0m0.003s
sys     0m0.014s
```

_______________________________________________
llvm-bugs mailing list
llvm-bugs@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs