[cfe-dev] Runtime of FormatTest.MemoizationTests

[David Blaikie via cfe-dev]

On Thu, Aug 31, 2017 at 8:33 AM Daniel Jasper <djasper at google.com> wrote:

> Yeah, just disabling the test entirely seems fine.
>

r312268


> We just need to figure out that this is broken on some of the bots.
>

I didn't quite understand this ^ statement. Could you clarify/rephrase?

- Dave


>
> On Wed, Aug 30, 2017 at 7:16 PM, David Blaikie <dblaikie at gmail.com> wrote:
>
>> Daniel - any ideas on ways this test could be improved/fixed in the face
>> of ENABLE_EXPENSIVE_CHECKS?
>>
>> 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)
>>
>>
>> On Wed, Aug 30, 2017 at 5:24 AM Raphael Isemann <teemperor at gmail.com>
>> wrote:
>>
>>> Hi David,
>>>
>>> yes, expensive checks were enabled on this build. I ran callgrind over
>>> it (which took a few days...) and got this out:
>>> https://teemperor.de/pub/ClangFormatTestProfile.html
>>>
>>> So in OptimizingLineFormatter::analyzeSolutionSpace we use a
>>> std::priority_queue for dijkstra's algorithm. And it seems every time
>>> we iterate and modify this queue. the debug code from glibcxx is
>>> scanning the whole queue for integrity. Meaning that this algorithm is
>>> now somewhere above quadratic runtime in this build mode.
>>>
>>> We could rewrite this to not use a priority_queue, but that seems
>>> overkill just for fixing this test's runtime. I'm open for ideas :)
>>>
>>> - Raphael
>>>
>>>
>>>
>>> 2017-08-23 16:46 GMT+02:00 David Blaikie <dblaikie at gmail.com>:
>>> > Ah, I noticed a really long runtime for this only when enabling
>>> expensive
>>> > checks. Are expensive checks enabled on the buildbot you're looking
>>> into?
>>> >
>>> > Specifically it wasn't llvm's expensive checks, but the glibcxx
>>> standard
>>> > library expensive checks.
>>> >
>>> > I didn't debug it any further, but I'm guessing that flag might make
>>> some
>>> > standard library ops not meet the required algorithmic complexities or
>>> > otherwise add. lot of overhead.
>>> >
>>> > Itd be worth looking into exactly which checks are dominating (a
>>> profile
>>> > would hopefully show it up - though possibly shrinking the test case a
>>> bit
>>> > before profiling would be good - since the overhead of profiling on
>>> top of
>>> > the 15min runtime would be quite a lot (I tried and gave up/got bored
>>> before
>>> > it finished))
>>> >
>>> >
>>> > On Wed., 23 Aug. 2017, 4:52 am Raphael Isemann via cfe-dev
>>> > <cfe-dev at lists.llvm.org> wrote:
>>> >>
>>> >> Hello everyone,
>>> >>
>>> >> On our CI infrastructure I noticed that nearly all the run time of the
>>> >> test suite is spent on running the FormatTest.MemoizationTests. The
>>> >> test seems to take around 15 minutes to pass which is more than all
>>> >> other tests combined. I also see that there is a comment in this test
>>> >> that states that "This test takes VERY long when memoization is
>>> >> broken." [1].
>>> >>
>>> >> I'm not sure if the test is supposed to take so long or if broken
>>> >> memoization is causing this delay. There doesn't seem to be any bug
>>> >> report open for this on bugzilla either.
>>> >>
>>> >> Anyone has the same problem on their CI infrastructure?
>>> >>
>>> >> - Raphael
>>> >>
>>> >>
>>> >> [1]
>>> >>
>>> https://github.com/llvm-mirror/clang/blob/823b3849ec3e121d0f9043dfdd6e66546bcf0907/unittests/Format/FormatTest.cpp#L3308
>>> >> _______________________________________________
>>> >> cfe-dev mailing list
>>> >> cfe-dev at lists.llvm.org
>>> >> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20170831/93eafa5a/attachment.html>