Performance of pattern checker on OptCoercions

[Simon Peyton Jones]

Yes; but we should jolly well figure out a way to do better for guards.  These guards are no more than patterns really!

Simon

From: Richard Eisenberg [mailto:eir at cis.upenn.edu]
Sent: 11 December 2015 15:59
To: George Karachalias <george.karachalias at gmail.com>
Cc: Ben Gamari <ben at well-typed.com>; Simon Peyton Jones <simonpj at microsoft.com>; GHC developers <ghc-devs at haskell.org>
Subject: Re: Performance of pattern checker on OptCoercions

If I understand correctly, you're saying that the problem is due to my use of guards, not anything with fancy types. If that's correct, then this sort of thing might be a trap anyone could stumble into. (The code in OptCoercion is fairly routine for Haskell.) It seems like disabling checking guards by default may be best, but I'd love a flag (not with -Wall) to enable it optionally.

Richard

On Dec 11, 2015, at 6:27 AM, George Karachalias <george.karachalias at gmail.com<mailto:george.karachalias at gmail.com>> wrote:


Hello Ben,

On Fri, Dec 11, 2015 at 11:58 AM, Ben Gamari <ben at well-typed.com<mailto:ben at well-typed.com>> wrote:

Hi George,

Richard has encountered a bit of a performance cliff when merging his
no-kinds work. In particular OptCoercions now results in multiple
gigabytes of memory consumption during compilation due to the pattern
checker. The problem seems to be the opt_trans_rule binding, which has
numerous equations, each of which has patterns of various complexities
and guards. Might this be another case where disabling the pattern
checker is unavoidable?

I am afraid so. I have just responded to the ticket about it. The essence is the
difference between `f` and `g` below:
f x = case x of
  []      -> ...
  (_:_) -> ...

g y | []      <- y = ...
      | (_:_) <- y = ...

`f` will generate an empty uncovered set while g will generate:
uncovered =
  { x |> { x ~ [], x ~ (_:_) }
  , x |> { x ~ (_:_), x ~ [] } }

which is also semantically empty but this cannot be detected until we call the
term oracle on it to see the inconsistency. Since pattern guards can pattern match
against any variable whilst case expressions match a single expression (`x` above)
I can not make the check treat them the same.
>From what I see, until now the pattern guards in opt_trans_co involved mostly
pattern matching with Maybe which has only two constructors. I can easily assume
that this is the reason we did not have such a problem until now. So many guards
are already a challenge for the pattern match checker but maybe changing this (by
this I mean to not use pattern guards on types with many constructors because this
is the most expensive thing for the whole check) is enough to make GHC bootstrap.

I hope this helps, I am really confident that this is the cause of the problem.
Nevertheless, I will look into it more to see if I can find another source.

George
--
things you own end up owning you

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20151211/dab35dde/attachment.html>