[cfe-dev] Runtime of FormatTest.MemoizationTests

[Raphael Isemann via cfe-dev]

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