Cache conversion to a map for dep_mods
Needs RevisionPublic

Authored by niteria on May 15 2017, 10:24 AM.

Details

Summary

For MultiLayerModules test we were recreating the
map a lot in calculateAvails.
Not doing that is a 26.1% improvement.

On my other test case it's -15% time and -31% allocations.

Test Plan

./validate

niteria created this revision.May 15 2017, 10:24 AM
niteria added inline comments.
compiler/main/HscTypes.hs
2303

I actually don't know the answer to this question, but this preserves current behavior.

ezyang added inline comments.May 15 2017, 7:41 PM
compiler/main/HscTypes.hs
2281

Sigh. I guess the reason is we need to preserve order?

dfeuer requested changes to this revision.May 15 2017, 9:54 PM
dfeuer added a subscriber: dfeuer.

I think you can probably do even better with a slightly different map representation in DepMods. In particular, since IsBootInterface = Bool,

ModuleNameEnv (ModuleName, IsBootInterface) ~=
  { nonBootInterfaceModules :: ModuleNameEnv ModuleName
  , bootInterfaceModules :: ModuleNameEnv ModuleName }

This eliminates all the pair constructors, and makes partitioning the boot modules from the rest absolutely free.

This revision now requires changes to proceed.May 15 2017, 9:54 PM
dfeuer added inline comments.May 15 2017, 10:04 PM
compiler/main/HscTypes.hs
973

Is there a reason to use map fst rather than the more obviously efficient mapFst?

2301

Is there a reason to use foldl' here directly rather than addListToUFM?

2313

`sortBy (compare on` fst)`` seems more direct. If you take my advice about the map representation, you can maintain the same sorting behavior by merging the two sorted lists; if you are *only* sorting for determinism, you can just append the sorted lists.

2319

Redundant do.

simonmar added inline comments.May 16 2017, 5:29 AM
compiler/main/HscTypes.hs
2282–2284

So we need a comment to explain the rationale for this representation. Otherwise, someone is going to come along later and remove the list because you can get it from the ModuleNameEnv, or vice versa :)

2288

Are the lists guaranteed sorted or something? Shouldn't we use equality on the ModuleNameEnv instead?

I think you can probably do even better with a slightly different map representation in DepMods. In particular, since IsBootInterface = Bool,

ModuleNameEnv (ModuleName, IsBootInterface) ~=
  { nonBootInterfaceModules :: ModuleNameEnv ModuleName
  , bootInterfaceModules :: ModuleNameEnv ModuleName }

This eliminates all the pair constructors, and makes partitioning the boot modules from the rest absolutely free.

That's a good point, but what motivated this change was that creating the map from scratch in RnNames.calculateAvails became a bottleneck.
As such if I change the representation here, I'd also need to change the representation of imp_dep_mods (and eps_is_boot as well, probably), otherwise I'd just move the cost of creating the tuples there, most likely undoing the benefit I get with this change.

Partitioning didn't show up as a bottleneck. Notice that we partition the list, so keeping the maps separate doesn't help as much. We'd either need to maintain 2 lists or pay for sorting in the function that does the partition.

I'm open to trying out changing the representation of imp_dep_mods and eps_is_boot, there is a trade-off here tough.
We'd need to do 2 lookups instead of 1 in some places and insertion becomes awkward as well (we need to maintain the maps being disjoint).
Perhaps we can get the benefits of not allocating the tuples by just unpacking: data ModuleNameWithIsBoot = ModuleNameWithIsBoot {-# UNPACK #-} !ModuleName {-# UNPACK #-} !IsBootInterface.

compiler/main/HscTypes.hs
2281

You guessed it :)

2288

Consistent order follows from the invariants:

dm_list = modDepsElts dm_map

I assume comparing a list is faster, mainly because there's less internal structure.

2301

No reason, other than that's how it was done before the refactor.

2313

Yeah, sorting is only about restoring determinism.

bgamari requested changes to this revision.May 16 2017, 9:20 AM

Indeed this needs a comment at least.

austin resigned from this revision.Nov 9 2017, 11:38 AM