Runtime of FormatTest.MemoizationTests

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


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))

Hi David,

yes, expensive checks were enabled on this build. I ran callgrind over
it (which took a few days...) and got this out:

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 :slight_smile:

- Raphael

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)

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

Yeah, just disabling the test entirely seems fine.


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