<html>
<head>
<base href="https://bugs.llvm.org/">
</head>
<body><table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Bug ID</th>
<td><a class="bz_bug_link
bz_status_NEW "
title="NEW - Structure elements have O(n^2) compile time slowdown"
href="https://bugs.llvm.org/show_bug.cgi?id=35585">35585</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>Structure elements have O(n^2) compile time slowdown
</td>
</tr>
<tr>
<th>Product</th>
<td>clang
</td>
</tr>
<tr>
<th>Version</th>
<td>unspecified
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>Windows NT
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>enhancement
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>-New Bugs
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedclangbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>wsnyder@wsnyder.org
</td>
</tr>
<tr>
<th>CC</th>
<td>llvm-bugs@lists.llvm.org
</td>
</tr></table>
<p>
<div>
<pre>This matches a similar confirmed GCC bug, please get the testcase from there:
<a href="https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83309">https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83309</a>
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.</pre>
</div>
</p>
<hr>
<span>You are receiving this mail because:</span>
<ul>
<li>You are on the CC list for the bug.</li>
</ul>
</body>
</html>