[Bug middle-end/21430] New: Quadratic behavior with constant initializers

[kazu at cs dot umass dot edu]

Consider:

#define B1(C,D)                                                         \
  B0(C##0,D##0) B0(C##1,D##0) B0(C##2,D##0) B0(C##3,D##0) B0(C##4,D##0) \
  B0(C##5,D##0) B0(C##6,D##0) B0(C##7,D##0) B0(C##8,D##0) B0(C##9,D##0)

#define B2(C,D)                                                         \
  B1(C##0,D##0) B1(C##1,D##0) B1(C##2,D##0) B1(C##3,D##0) B1(C##4,D##0) \
  B1(C##5,D##0) B1(C##6,D##0) B1(C##7,D##0) B1(C##8,D##0) B1(C##9,D##0)

#define B3(C,D)                                                         \
  B2(C##0,D##0) B2(C##1,D##0) B2(C##2,D##0) B2(C##3,D##0) B2(C##4,D##0) \
  B2(C##5,D##0) B2(C##6,D##0) B2(C##7,D##0) B2(C##8,D##0) B2(C##9,D##0)

#define B4(C,D)                                                         \
  B3(C##0,D##0) B3(C##1,D##0) B3(C##2,D##0) B3(C##3,D##0) B3(C##4,D##0) \
  B3(C##5,D##0) B3(C##6,D##0) B3(C##7,D##0) B3(C##8,D##0) B3(C##9,D##0)

#define B0(C,D) C,
const int a[] = { B4(1,1) 0 };
#undef B0

void bar (int);

void
foo (void)
{
#define B0(C,D) bar(a[C-D]);
  B4(1,1);
#undef B0
}

Change B4(1,1) to B3(1,1), B2(1,1), etc.  You'll get quadratic behavior.

On my machine,

B1    10 elements  0.097s
B2   100 elements  0.094s
B3  1000 elements  1.373s
B4 10000 elements 41.816s

I'm pretty sure the quadratic behavior comes from the ARRAY_REF case of
expand_expr_real_1.

-- 
           Summary: Quadratic behavior with constant initializers
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Keywords: compile-time-hog
          Severity: normal
          Priority: P2
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: kazu at cs dot umass dot edu
                CC: gcc-bugs at gcc dot gnu dot org


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