<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, Oct 19, 2016 at 9:08 AM, Richard Smith <span dir="ltr"><<a href="mailto:richard@metafoo.co.uk" target="_blank">richard@metafoo.co.uk</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto"><span class="gmail-"><div><div class="gmail_extra"><div class="gmail_quote">On 19 Oct 2016 2:44 am, "Andy Gibbs" <<a href="mailto:andyg1001@hotmail.co.uk" target="_blank">andyg1001@hotmail.co.uk</a>> wrote:<br type="attribution"><blockquote class="gmail-m_706754946998866335quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi,<br>
<br>
I have observed a massive performance regression when upgrading from clang 3.7<br>
to 3.9.  I have also checked that current tip-of-trunk seems to have this<br>
regression too.<br>
<br>
I have managed to isolate the patch at which the regression appeared as<br>
r248431 on 23rd Sept 2015.<br>
<br>
I have attached a simple test-case that demonstrates the problem rather<br>
effectively.<br>
<br>
Prior to r248431, this code would compile in under 20 seconds, consuming<br>
approx. 400Mb of memory.  GCC, for comparison, takes longer at around 50<br>
seconds on my machine but consumes only ~250Mb.<br>
<br>
Following patch r248431 and all the way up to tip-of-trunk, clang is<br>
terminated by the OOM handler due excessive memory usage in excess of 7<br>
Gigabytes!!!<br>
<br>
This seems a little unreasonable -- the test-code in question is a little<br>
pathological maybe but is designed to exploit template memoisation, so the<br>
excessive memory usage would imply to me that this memoisation is no longer<br>
working.<br></blockquote></div></div></div><div><br></div></span><div>That's not the problem. The issue is that this:</div><div><br></div><div>(sizeof...(Is) + Is)...<br></div><div><br></div><div>substitutes into the sizeof... subexpression once for each element of Is, which massively amplifies any change in the behaviour of sizeof...</div><div><br></div><div>r248431 changes our behaviour such that sizeof... now scans its parameter's expansion looking for unexpanded packs (which can appear if it's used inside an alias template), making the instantiation of that fragment quadratic in the size of the pack Is.</div><div><br></div><div>I'll take a look and see if we can handle this a bit better.</div></div></blockquote><div><br></div><div>As of r284653, the performance and memory usage for simple sizeof... expansions should be a lot better. But your approach is still O(N^2 log N) when compiled with Clang. You can remove a factor of N by passing around the size of the pack instead of recomputing it:</div><div><br></div><div><div>template <unsigned Size, typename List, bool Odd></div><div>struct PartialVariadicIndicesSequence;</div><div><br></div><div>template <unsigned Size, unsigned... Is></div><div>struct PartialVariadicIndicesSequence<Size, VariadicIndices<Is...>, false> {</div><div>  using Type = VariadicIndices<Is..., Size + Is ...>;</div><div>};</div><div><br></div><div>template <unsigned Size, unsigned... Is></div><div>struct PartialVariadicIndicesSequence<Size, VariadicIndices<Is...>, true> {</div><div>  using Type = VariadicIndices<Is..., Size + Is ..., Size * 2>;</div><div>};</div><div><br></div><div>template <unsigned N></div><div>struct MakeVariadicIndicesImpl : PartialVariadicIndicesSequence<</div><div>    N / 2,</div><div>    typename MakeVariadicIndicesImpl<N / 2>::Type,</div><div>    ((N % 2) != 0)</div><div>  > { };</div></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto"><span class="gmail-"><div><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail-m_706754946998866335quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Is anyone else able to confirm my findings?  If so, I will raise this as a bug<br>
report.  Richard, I have copied you as the author of the patch in question<br>
(hope you don't mind!).<br>
<br>
Cheers,<br>
Andy<br>
<br>
</blockquote></div><br></div></div></span></div>
</blockquote></div><br></div></div>