Use a more efficient representation than [DynFlag]

In compiler/typecheck/TcRnMonad.lhs, if I replace the existing definitions with

traceOptIf _ _ = return ()
traceOptTcRn _ _ = return ()
dumpTcRn _ = return ()

then we see an improvement in nofib's "Compile Times" sections:

-1 s.d.		-----	-8.5%
+1 s.d.		-----	+1.8%
Average		-----	-3.5%

By using some sort of bitmap representation, we ought to see a modest compile time improvement from all the checks that the trace functions make, as well as various other checks that are made (do we need to warn about missing sigs, are overlapping instances allowed, etc).

The tricky bit is designing it so that it is hard to shoot yourself in the foot. Lexer.x already has a bitmap (genericsBit, ffiBit etc) but the mapping of feature to bit number is done by hand, which isn't ideal. Perhaps this is even important enough to deserve a language extension?

Trac metadata

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

changed milestone to %6.10 branch

changed weight to 5

added Tbug Trac import labels

Trac metadata

Trac field	Value
Architecture	Unknown → Unknown/Multiple

Trac metadata

Trac field	Value
Operating system	Unknown → Unknown/Multiple

changed milestone to %6.12 branch

Trac metadata

Trac field	Value
TypeOfFailure	- → CompileTimePerformance

changed milestone to %6.12.3

removed milestone

changed weight to 3

Trac metadata

Trac field	Value
Priority	normal → low

With plain HEAD, and HEAD with bitmap.dpatch, running

time ghc -v0 --make -O Setup.hs

in a Cabal tree (which thus also builds most of Cabal) I get:

Run 1
    HEAD:           111.38 user 1.39 system 1:52.88 elapsed
    Bitmap:         109.01 user 1.38 system 1:50.41 elapsed
Run 2
    HEAD:           112.18 user 1.32 system 1:53.55 elapsed
    Bitmap:         110.58 user 1.38 system 1:51.98 elapsed
Run 3
    HEAD:           97.51 user 1.23 system 1:38.75 elapsed
    Bitmap:         110.95 user 1.26 system 1:52.24 elapsed
Run 4
    HEAD:           111.60 user 1.33 system 1:52.92 elapsed
    Bitmap:         109.93 user 1.30 system 1:51.31 elapsed
Run 5
    HEAD:           111.63 user 1.66 system 1:53.31 elapsed
    Bitmap:         88.90 user 1.19 system 1:30.41 elapsed
Run 6
    HEAD:           95.12 user 1.26 system 1:36.47 elapsed
    Bitmap:         111.27 user 1.48 system 1:52.88 elapsed
Run 7
    HEAD:           112.18 user 1.35 system 1:53.66 elapsed
    Bitmap:         109.51 user 1.27 system 1:50.85 elapsed
Run 8
    HEAD:           112.51 user 1.16 system 1:53.74 elapsed
    Bitmap:         110.33 user 1.26 system 1:51.71 elapsed
Run 9
    HEAD:           111.69 user 1.36 system 1:53.37 elapsed
    Bitmap:         109.26 user 1.40 system 1:50.65 elapsed
Run 10
    HEAD:           114.77 user 1.38 system 1:56.24 elapsed
    Bitmap:         110.08 user 1.47 system 1:51.54 elapsed

so with the patch it takes 109-110 rather than 111-112s (although occasionally a build is much quicker).

So not a huge performance increase, but it removes one of the slivers, and it would be nice to get the dopt noise out of profiles. I think some sort of extension (or generic program?) that makes bitmaps from enumerations would be generally useful.

Attached file bitmap.dpatch (download).

I don't think we should apply the patch, incidentally. It would be a maintenance nightmare.

Replying to [ticket:2159#comment:45436 igloo]:

I don't think we should apply the patch, incidentally. It would be a maintenance nightmare.

That's what I thought too when I saw it. Have you tried just using an IntMap?

changed milestone to %7.0.2

changed milestone to %7.2.1

changed milestone to %7.4.1

changed milestone to %7.6.1

changed weight to 0

Trac metadata

Trac field	Value
Priority	low → lowest

changed milestone to %7.6.2

changed milestone to %7.10.1

Moving to 7.10.1.

removed milestone

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

changed milestone to %8.0.1

Milestone renamed

closed

Unless I am mistaken this has already been implemented. DynFlags now represents dump flags, extension flags, and general flags as IntSets, using the Enum instances of the respective types to map each flag to a bit. I'm not entirely sure when this change was made but it was quite a while ago.

Trac metadata

Trac field	Value
Resolution	Unresolved → ResolvedFixed

Heh, I was just looking at this too.

I imagine a bit array representation as in "bitmap.dpatch" would be a lot faster though. Especially if you added RULES to inline the case of checking for a known flag.

Well the bit array was 4x faster than IntSet in my unscientific test. And it would probably be a bit faster still when the option to test is known and can be inlined. But there could be little left to gain after the switch to IntSet.

A pretty easy experiment to do, if we had an easy way to benchmark compiler performance...

Great! Bring it on!

According to a statistical profiling run that I did some time ago GHC spends about 0.3% of its total time in the module libraries/containers/Data/IntSet/Base.hs. I don't know how much of that 0.3% is from DynFlag-checking versus other users of IntSet (another one is UnVarSet, whatever that is).

Unfortunately, reliably measuring a speedup that is expected to be at most ~0.25% is itself a somewhat nontrivial project.

added Plow label