[cfe-dev] Runtime of FormatTest.MemoizationTests

[David Blaikie via cfe-dev]

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/20170830/4d381189/attachment.html>