[llvm-bugs] [Bug 35585] New: Structure elements have O(n^2) compile time slowdown

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=35585

            Bug ID: 35585
           Summary: Structure elements have O(n^2) compile time slowdown
           Product: clang
           Version: unspecified
          Hardware: PC
                OS: Windows NT
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: -New Bugs
          Assignee: unassignedclangbugs at nondot.org
          Reporter: wsnyder at wsnyder.org
                CC: llvm-bugs at lists.llvm.org

This matches a similar confirmed GCC bug, please get the testcase from there:

   https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83309

A program with >10K structure elements was taking hours to compile. The
attached program was used to make programs with different numbers of elements,
and the following was observed with clang 3.8:

0.04 seconds to compile class with total of 2000 ints
0.15 seconds to compile class with total of 4000 ints
0.26 seconds to compile class with total of 6000 ints
0.40 seconds to compile class with total of 8000 ints
0.57 seconds to compile class with total of 10000 ints

Which seems close to O(n^2).

The same is observed with a "typedef int"'ed type, but all times are
approximately 4 times longer:

0.14 seconds to compile class with total of 2000 typedef'ed ints
0.45 seconds to compile class with total of 4000 typedef'ed ints
0.93 seconds to compile class with total of 6000 typedef'ed ints
1.63 seconds to compile class with total of 8000 typedef'ed ints
2.48 seconds to compile class with total of 10000 typedef'ed ints

If instead of having 2000 integers in a class, the program instead has 20
unique structures each with 100 members (the same 2000 total declarations), the
time is goes way down, as one would expect. This does show however the problem
is not related to file or total structure size. Not surprisingly, if enough
structures are used, a similar problem arises with a O(num_structures^2)
slowdown.

0.02 seconds to compile class with total of 2000 from 20 structs of 100
typedef'ed ints
0.02 seconds to compile class with total of 4000 from 40 structs of 100
typedef'ed ints
0.07 seconds to compile class with total of 6000 from 60 structs of 100
typedef'ed ints
0.10 seconds to compile class with total of 8000 from 80 structs of 100
typedef'ed ints
0.14 seconds to compile class with total of 10000 from 100 structs of 100
typedef'ed ints

This slowdown does not occur for function-local variables, which seem properly
O(n).

Thanks.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20171209/a0bcd471/attachment.html>