980934 - Huge performance hit from mozilla::SplayTree::checkCoherency in DEBUG builds

Status: RESOLVED FIXED

(Core :: MFBT, defect)

Description

[Julian Seward [:jseward]]

mfbt/SplayTree.h appears to add a splay tree implementation.  In debug
builds, SplayTree::find, SplayTree::insert and SplayTree::remove call
SplayTree::checkCoherency in order to sanity check the resulting tree.
Unfortunately that walks the entire tree and so transforms what is
presumably an O(log N) or better operation to O(N) cost.  This makes
m-c extremely slow in debug mode, to the point of being unusable,
under some circumstances.

Non-debug builds do not show any of these perf problems.

I discovered this when running a debug build of Firefox with the SPS
unwinder and the new LUL unwind library.  The profiles show a lot of
cost in SplayTree::checkCoherency, with 50+ deep nested recursive
calls.  It is not easy to see where this frenzy of recursion
originates from, but one source I did see is
mozilla::OverflowChangedTracker(nsIFrame*).

Comment 1

[Nathan Froyd [:froydnj]]

Trying out debug {mochi,ref,crash}tests with the consistency check removed to see if it makes a big difference:

https://tbpl.mozilla.org/?tree=Try&rev=3efc309445f6

Comment 2

[Nathan Froyd [:froydnj]]

I also tried with a somewhat newer tree, to be able to compare the try run with inbound more reasonably:

https://tbpl.mozilla.org/?tree=Try&rev=05b1e98f1131

mochitest-1 appears to be outside the noise threshold--somewhere between 10-20% faster.  Everything else
looks like it is in the noise.

(Which isn't to say, of course, that we shouldn't fix the issue so developers could use debug builds more productively on their machines...)

Comment 3

[Andrew McCreight (out of office until 8/21) [:mccr8]]

FWIW, I'm locally working on some code that uses a SplayTree with around 45000 elements in it, and checkCoherency was making it unusably slow, causing my browser to hang for tens of seconds.

Comment 4

[Julian Seward [:jseward]]

This problem is a bit bad because the worst case performance hit
can be huge, as Andrew and I observed independently, even if, as
Nathan observes, the average hit across {mochi,ref,crash}tests
isn't too bad.

A splay tree should be one of those things where, once we've done
some simple unit tests on it, we're pretty much sure it works and
there's no point in endlessly rewalking complete trees when used
"for real" in Gecko.  Is there some way we can just unit-test it
and rely on that to be adequate?

Comment 5

[Nicholas Nethercote [inactive]]

> Is there some way we can just unit-test it and rely on that to be adequate?

Yes, this is the right way to do it. Someone just needs to write mfbt/tests/TestSplayTree.cpp. There are plenty of other tests in mfbt/tests/ to serve as examples.

Comment 6

[Nicholas Nethercote [inactive]]

Attachment: (part 1) - Add mfbt/tests/TestSplayTree.cpp

Comment 7

[Nicholas Nethercote [inactive]]

Attachment: (part 2) - MFBT: Remove the excessively frequent coherency checks from SplayTree

Comment 8

[Nicholas Nethercote [inactive]]

CC'ing mattwoodrow because he is (I think?) the original author of MFBT's SplayTree.

Comment 9

[Matt Woodrow (:mattwoodrow)]

I just adapted it from the SplayTree in js/src/ds/, but this seems like a good change.

Comment 10

[Nicholas Nethercote [inactive]]

> I just adapted it from the SplayTree in js/src/ds/

Ah, so it was you who was responsible for the duplication :(

Comment 11

[Nathan Froyd [:froydnj]]

Comment on attachment 8464487 [details] [diff] [review]
(part 1) - Add mfbt/tests/TestSplayTree.cpp

Review of attachment 8464487 [details] [diff] [review]:
-----------------------------------------------------------------

Hooray!  r=me with the below problem fixed.

::: mfbt/SplayTree.h
@@ +171,5 @@
>  
> +  // For testing purposes only.
> +  void checkCoherency()
> +  {
> +    checkCoherency(mRoot, nullptr);

checkCoherency's body is currently #ifdef DEBUG *and* uses plain MOZ_ASSERT, rather than MOZ_RELEASE_ASSERT, so the test will do nothing in release builds.

Comment 12

[Nicholas Nethercote [inactive]]

> checkCoherency's body is currently #ifdef DEBUG *and* uses plain MOZ_ASSERT,
> rather than MOZ_RELEASE_ASSERT, so the test will do nothing in release
> builds.

Good catch. I'll remove the #ifdef DEBUG and convert them all to MOZ_RELEASE_ASSERT.

Comment 13

[Nicholas Nethercote [inactive]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/af07b6b9ff30
https://hg.mozilla.org/integration/mozilla-inbound/rev/6eded676da83

Comment 14

[Nicholas Nethercote [inactive]]

This landed ages ago. Not sure why it wasn't marked as landing on mozilla-central or auto-closed. So I'll close it now.