[cfe-dev] Runtime of FormatTest.MemoizationTests

[Daniel Jasper via cfe-dev]

Yeah, just disabling the test entirely seems fine. We just need to figure
out that this is broken on some of the bots.

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/cc42a354/attachment.html>