<div dir="ltr"><br><br><div class="gmail_quote"><div dir="ltr">On Thu, Aug 31, 2017 at 8:33 AM Daniel Jasper <<a href="mailto:djasper@google.com">djasper@google.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Yeah, just disabling the test entirely seems fine.</div></blockquote><div><br>r312268<br> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"> We just need to figure out that this is broken on some of the bots.</div></blockquote><div><br></div><div>I didn't quite understand this ^ statement. Could you clarify/rephrase?<br><br>- Dave</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Aug 30, 2017 at 7:16 PM, David Blaikie <span dir="ltr"><<a href="mailto:dblaikie@gmail.com" target="_blank">dblaikie@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Daniel - any ideas on ways this test could be improved/fixed in the face of ENABLE_EXPENSIVE_CHECKS?<br><br>Should the test just be skipped entirely? Or maybe there's a way to make the code passably efficient even in the face of glibcxx checks? (Not sure if there's a way to disable the checks/certify that the content is valid, etc - if it's easy for us to prove that from the surrounding code)<div><div class="m_-3968677780394089070h5"><br><br><div class="gmail_quote"><div dir="ltr">On Wed, Aug 30, 2017 at 5:24 AM Raphael Isemann <<a href="mailto:teemperor@gmail.com" target="_blank">teemperor@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi David,<br>
<br>
yes, expensive checks were enabled on this build. I ran callgrind over<br>
it (which took a few days...) and got this out:<br>
<a href="https://teemperor.de/pub/ClangFormatTestProfile.html" rel="noreferrer" target="_blank">https://teemperor.de/pub/ClangFormatTestProfile.html</a><br>
<br>
So in OptimizingLineFormatter::analyzeSolutionSpace we use a<br>
std::priority_queue for dijkstra's algorithm. And it seems every time<br>
we iterate and modify this queue. the debug code from glibcxx is<br>
scanning the whole queue for integrity. Meaning that this algorithm is<br>
now somewhere above quadratic runtime in this build mode.<br>
<br>
We could rewrite this to not use a priority_queue, but that seems<br>
overkill just for fixing this test's runtime. I'm open for ideas :)<br>
<br>
- Raphael<br>
<br>
<br>
<br>
2017-08-23 16:46 GMT+02:00 David Blaikie <<a href="mailto:dblaikie@gmail.com" target="_blank">dblaikie@gmail.com</a>>:<br>
> Ah, I noticed a really long runtime for this only when enabling expensive<br>
> checks. Are expensive checks enabled on the buildbot you're looking into?<br>
><br>
> Specifically it wasn't llvm's expensive checks, but the glibcxx standard<br>
> library expensive checks.<br>
><br>
> I didn't debug it any further, but I'm guessing that flag might make some<br>
> standard library ops not meet the required algorithmic complexities or<br>
> otherwise add. lot of overhead.<br>
><br>
> Itd be worth looking into exactly which checks are dominating (a profile<br>
> would hopefully show it up - though possibly shrinking the test case a bit<br>
> before profiling would be good - since the overhead of profiling on top of<br>
> the 15min runtime would be quite a lot (I tried and gave up/got bored before<br>
> it finished))<br>
><br>
><br>
> On Wed., 23 Aug. 2017, 4:52 am Raphael Isemann via cfe-dev<br>
> <<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a>> wrote:<br>
>><br>
>> Hello everyone,<br>
>><br>
>> On our CI infrastructure I noticed that nearly all the run time of the<br>
>> test suite is spent on running the FormatTest.MemoizationTests. The<br>
>> test seems to take around 15 minutes to pass which is more than all<br>
>> other tests combined. I also see that there is a comment in this test<br>
>> that states that "This test takes VERY long when memoization is<br>
>> broken." [1].<br>
>><br>
>> I'm not sure if the test is supposed to take so long or if broken<br>
>> memoization is causing this delay. There doesn't seem to be any bug<br>
>> report open for this on bugzilla either.<br>
>><br>
>> Anyone has the same problem on their CI infrastructure?<br>
>><br>
>> - Raphael<br>
>><br>
>><br>
>> [1]<br>
>> <a href="https://github.com/llvm-mirror/clang/blob/823b3849ec3e121d0f9043dfdd6e66546bcf0907/unittests/Format/FormatTest.cpp#L3308" rel="noreferrer" target="_blank">https://github.com/llvm-mirror/clang/blob/823b3849ec3e121d0f9043dfdd6e66546bcf0907/unittests/Format/FormatTest.cpp#L3308</a><br>
>> _______________________________________________<br>
>> cfe-dev mailing list<br>
>> <a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a><br>
>> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a><br>
</blockquote></div></div></div></div>
</blockquote></div><br></div>
</blockquote></div></div>