Trying to speedup GHC compile times...Help!

Fri Jul 2 14:38:22 UTC 2021

Somewhat off-topic: does GHC no longer use "the rapier"? I thought the
InScopeSet was needed to check that we can safely skip on extending the
substitution as you go under binders when the binder is not in the
InScopeSet (naively you would always have to rename binders, and thus
extend the substitution, in order to avoid capture as you go under
binders). i.e. the IntMap is not just used to generate new variable names,
but to ensure the compiler does less work in the form of doing fewer
substitutions.

On Fri, 2 Jul 2021 at 16:12, Simon Peyton Jones via ghc-devs <
ghc-devs at haskell.org> wrote:

> There are lot of places where it would be pretty tiresome to plumb a
> unique supply guaranteed unique from every other.   I think the current
> setup works pretty well – but I bet we can squeeze cycles out of its
> implementation.
>
>
>
> Simon
>
>
>
> *From:* Richard Eisenberg <lists at richarde.dev>
> *Sent:* 02 July 2021 14:26
> *To:* Simon Peyton Jones <simonpj at microsoft.com>
> *Cc:* Young, Jeff <jeff.young at tweag.io>; ghc-devs at haskell.org
> *Subject:* Re: Trying to speedup GHC compile times...Help!
>
>
>
> One piece I'm curious about, reading this thread: why do we have so many
> IntMaps and operations on them? Name lookup is a fundamental operation a
> compiler must do, and that would use an IntMap: good. But maybe there are
> other IntMaps used that are less necessary. A key example: whenever we do
> substitution, we track an InScopeSet, which is really just an IntMap. This
> InScopeSet remembers the name of all variables in scope, useful when we
> need to create a new variable name (this is done by uniqAway). Yet perhaps
> the tracking of these in-scope variables is very expensive and comprises
> much of the IntMap time. Might it be better just to always work in a monad
> capable of giving fresh names? We actually don't even need a monad, if
> that's too annoying. Instead, we could just pass around an infinite list of
> fresh uniques. This would still be clutterful, but if it grants us a big
> speed improvement, the clutter might be worth it.
>
>
>
> The high-level piece here is that there may be good things that come from
> understanding where these IntMaps arise.
>
>
>
> Richard
>
>
>
> On Jul 2, 2021, at 4:08 AM, Simon Peyton Jones via ghc-devs <
> ghc-devs at haskell.org> wrote:
>
>
>
> Jeff
>
>
>
> Great stuff!  Welcome.
>
>
>
> I strongly urge you to keep a constantly-update status wiki page, which
> lists the ideas you are working on, and points to relevant resources and
> tickets.  An email thread like this is a good way to gather ideas, but NOT
> a good way to organise and track them.
>
>
>
> Looking carefully at profiles is a good plan.  That’s the hard data!
>
>
>
> I think that some careful investigation of IntMap (at least the bits that
> GHC uses heavily) would be a good idea.  Clearly we spend a lot of time in
> these maps, so speedups here will yield a lot of benefit.  Look at the
> heavy hitters from the profile, stare at the Core code and see if it’s s
> good as it can be.
>
>
>
> For example, Sebastian discovered a strange infelicity in IntMap.lookup,
> which I’ve documented in a new ticket
>
> https://gitlab.haskell.org/ghc/ghc/-/issues/20069
> <https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2F-%2Fissues%2F20069&data=04%7C01%7Csimonpj%40microsoft.com%7Cd477d24fb159472b77ab08d93d5cfbb7%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637608293368167086%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=dSEa4md56IpyMGRPHW%2BVjWtZQGDi7vpVgmOCukyHTIU%3D&reserved=0>
>
>
>
> I think it’d also be worth measuring how unbalanced our IntMap trees get.
> See
>
>    https://gitlab.haskell.org/ghc/ghc/-/issues/19820
> <https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2F-%2Fissues%2F19820&data=04%7C01%7Csimonpj%40microsoft.com%7Cd477d24fb159472b77ab08d93d5cfbb7%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637608293368167086%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=5rgCmwBbb4mZ9NWoT7RtzRPFFND4e13k2XWeQkwgM%2FY%3D&reserved=0>
>
> The speculation there is that we are getting very unbalanced trees.  So
> measure it!  If it’s true, we could improve matters by using a different
> IntMap; or maybe by scrambling the key a bit --- see the ticket.
>
>
>
> Simon
>
>
>
> *From:* ghc-devs <ghc-devs-bounces at haskell.org> *On Behalf Of *Young, Jeff
> *Sent:* 02 July 2021 02:36
> *To:* ghc-devs at haskell.org
> *Subject:* Trying to speedup GHC compile times...Help!
>
>
>
> Hi ghc devs,
>
>
>
> I'm a long-time Haskeller but am just getting into GHC development. I
> started a 12 week internship at Tweag I/O under Richard Eisenberg this week
> with the singular goal to speedup GHC compile times. I'm specifically
> looking to contribute to ghc issues 18541
> <https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2F-%2Fissues%2F18541&data=04%7C01%7Csimonpj%40microsoft.com%7Cd477d24fb159472b77ab08d93d5cfbb7%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637608293368177079%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=az67TZRzofQayj%2BGsc0aYUibVff1Z%2Fs0%2Bvvt4oD6yaM%3D&reserved=0>
> and 18535
> <https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2F-%2Fissues%2F18535&data=04%7C01%7Csimonpj%40microsoft.com%7Cd477d24fb159472b77ab08d93d5cfbb7%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637608293368177079%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=zVUtIY1ux%2BRfHBUsI2BoHM3hOK9O8p0W90F7qqk7TeA%3D&reserved=0>.
> So I thought I would reach out to the community to get some direction on
> issues/features/problems to tackle in the pursuit of faster compilation
> times. This is a full time internship and so I think there is a real
> opportunity to nail down a deliverable for the community, but I want to get
> some guidance from the experts (you fine people!) before going down a
> rabbit hole.
>
>
>
> To be specific I'm looking for lingering items such as:
>
>   1. It would be great if we had <thing-here> but no one has time.
>
>   2. Primop foo is half complete but is the right type for
> <common-use-case-which-is-currently-just-a-list>.
>
>   3. Swap <some-type> to an array-like type *non-incrementally*, that is,
> establish a patch that rips out the previous type and replaces it with the
> array-like across the entire compiler, rather than module-by-module.
>
>
>
> Point 2 is a specific reference to MR 3571
> <https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgitlab.haskell.org%2Fghc%2Fghc%2F-%2Fmerge_requests%2F3571&data=04%7C01%7Csimonpj%40microsoft.com%7Cd477d24fb159472b77ab08d93d5cfbb7%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637608293368187075%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=YnhnkOZXRoYFA18EvNUh4t5lUbPrp4rLpOVrtlNMnI8%3D&reserved=0>
>  but I'm unsure of the status and etiquette around MRs, and I'm unsure
> exactly how fulfilling the todos at the end of that MR would aid in faster
> compilation times (and if there is evidence to that effect somewhere).
>
>
>
> Thanks for the help!
>
>
>
> - Jeff
>
>
>
>
>
>
>
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
> <https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmail.haskell.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fghc-devs&data=04%7C01%7Csimonpj%40microsoft.com%7Cd477d24fb159472b77ab08d93d5cfbb7%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637608293368187075%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=bCmRr98NfDWWsZXU1WbOFdm0ScDqoj11UR%2Fc%2BzQ1dNs%3D&reserved=0>
>
>
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20210702/40dab15d/attachment.html>