<html>
<head>
<base href="http://llvm.org/bugs/" />
</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 --- - non-modularized headers in modular build leads to quadratic compile time due to long redecl chains"
href="http://llvm.org/bugs/show_bug.cgi?id=21264">21264</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>non-modularized headers in modular build leads to quadratic compile time due to long redecl chains
</td>
</tr>
<tr>
<th>Product</th>
<td>clang
</td>
</tr>
<tr>
<th>Version</th>
<td>trunk
</td>
</tr>
<tr>
<th>Hardware</th>
<td>PC
</td>
</tr>
<tr>
<th>OS</th>
<td>Linux
</td>
</tr>
<tr>
<th>Status</th>
<td>NEW
</td>
</tr>
<tr>
<th>Severity</th>
<td>normal
</td>
</tr>
<tr>
<th>Priority</th>
<td>P
</td>
</tr>
<tr>
<th>Component</th>
<td>Modules
</td>
</tr>
<tr>
<th>Assignee</th>
<td>unassignedclangbugs@nondot.org
</td>
</tr>
<tr>
<th>Reporter</th>
<td>richard-llvm@metafoo.co.uk
</td>
</tr>
<tr>
<th>CC</th>
<td>chandlerc@gmail.com, dgregor@apple.com, llvmbugs@cs.uiuc.edu
</td>
</tr>
<tr>
<th>Classification</th>
<td>Unclassified
</td>
</tr></table>
<p>
<div>
<pre>If we import O(N) modules, each of which does this:
#include "non-modular-header.h"
// ... more stuff ...
then every declaration in "non-modular-header.h" has O(N) declarations in its
redecl chain, and getCanonicalDecl() calls on a most-recent declaration take
O(N) time. This appears to be the biggest performance problem in builds with
lots of modules right now.
This is also a problem for non-modular builds, but is less severe since it's
rare to get a long redeclaration chain.
Proposed fix: remove the current PrevPtr from redeclarable Decls, and replace
it with:
-- in a non-canonical redeclarable Decl, a pointer to the canonical decl
-- in a canonical redeclarable Decl with no redeclarations, null
-- in a canonical redeclarable Decl with only one redeclaration, a pointer to
that redeclaration
-- in a canonical redeclarable Decl with two or more redecls (a fairly rare
case), a pointer to an array of pointers to those Decls.
We have 3 spare bits in the bottom of this pointer; we can use them to store
the index of the declaration in the redecl table (this also covers storing
whether the declaration is canonical). To cover longer chains, we can store
(say) log_2(index) rather than index; that lets us perform getPreviousDecl() in
log_2(N) time rather than N time, for N up to ~256. In the rare case that we go
beyond that, we can store a Decl->index hash map along with the array, to make
the getPreviousDecl() performance constant-time.
One final concern is storing the generation number and external AST source
pointer for the canonical declaration in the case where modules is enabled.
These can also be added to the array of pointers, but we'll need to use that
representation even when there is only one redeclaration in the modules case.</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>