7% allocation regression in Haddock performance tests

changed weight to 5

I’m trying to make perf.haskell.org rerun these commits with d55a9b4f cherrypicked, and will report back. This should narrow it down.

How about we just delete those 3 haddock performance tests?

From https://mail.haskell.org/pipermail/ghc-devs/2015-July/009434.html:

Simon Peyton Jones wrote: Could it be creeping up because Haddock is doing more than before? Ie not just because GHC is being bad?

Yes, it very much could be. Haddock is a moving target so it's not too weird that the numbers change. I want to say that the perf test should just be removed but it's still useful: if you're GHC hacking and not changing Haddock and numbers go awry then it serves its purpose.

OK, so I won't lose sleep over it!

Trac metadata

Trac field	Value
Related	- → #10482 (closed)

assigned to @trac-niteria

And we have a winner: The culprit is changeset:0497ee50 as can be seen on https://perf.haskell.org/ghc/#revision/0497ee50

So Simon is not only freed of any fault, but yet again had a the right intuition about what regressions are worth investigating.

Assigning this to niteria.

@nomeata: Thanks for running these. I think I had to disable haddock before ./validate because it was broken and that's how this snuck in. I will take a look this week (but unfortunately not tomorrow).

Thanks so much Joachim. I'm mighty relieved!

I'll revert Bartosz's patch for now, to keep Phab happy.

mentioned in commit 70a45893

This appears to be ordering related. Meaning that when things are ordered differently we do different kind of work and it costs more.

When I changed Ord UnitId from my original diff to

instance Ord UnitId where
  nm1 `compare` nm2 =
    -- do the same work, but return the old ordering
    if stableUnitIdCmp nm1 nm2 == LT
      then getKey (getUnique nm1) `compare` getKey (getUnique nm2) 
           -- this was enough to stop GHC from being smart and optimize it out
      else getUnique nm1 `compare` getUnique nm2

The difference went from 7% to 0.21%. I will try to narrow this down to functions that are ordering sensitive and see if I can make them stable.

@thomie, Note that the Haddock perf test is really a GHC perf test, because most of the work that Haddock does is loading source files and typechecking them using the GHC API.

It appears that checkFamInstConsistency is sensitive to Module ordering. Making it a noop also reduces allocations by 9%.

So what's happening in checkFamInstConsistency is suboptimal in multiple ways:

The algorithm itself is quadratic. It checks every module against every other module. It appears to me that the same thing can be done in a linear way by maintaining a consistent env of family instances so far and fold adding there when possible or reporting an error.
checkFamInstConsistency in Haddock appears to be called for every module (Haddock is equivalent to --make, right?) which is redundant and in principle could be done at the very end once.
determining what pairs to compare uses Set ModulePair. After my change Ord ModulePair is linear. The size of the set is quadratic. Furthermore the Ord ModulePair doesn't cache its canonicalization.
given these there still appear to be better and worse orders for the ModulePairs. I don't really know why.

When typechecking a particular module M, checkFamInstConsistency does indeed need to check that the imported family instances are consistent; and that requires checking any instance for F imported from I1 with all instances of F imported from some other module I2.

(Multiple instances all imported from I1 have already been checked, when compiling I1.)

I don't understand Haddock's use-case to know why the algorithm is behaving so badly, but I bet there is some low-hanging fruit.

mentioned in commit 12306294

mentioned in commit 348f2dbb

closed

Trac metadata

Trac field	Value
Resolution	Unresolved → ResolvedFixed

added compiler perf label

added Pnormal label

removed the relation with #10482 (closed)

mentioned in issue #10482 (closed)

Trac field	Value
Version	8.0.1
Type	Task
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

7% allocation regression in Haddock performance tests

Child items ...

Activity