diff options
author | Richard Eisenberg <eir@cis.upenn.edu> | 2014-12-22 13:23:11 -0500 |
---|---|---|
committer | Richard Eisenberg <eir@cis.upenn.edu> | 2014-12-22 13:23:32 -0500 |
commit | 22bb78bb02718e162130690dfb9a11d7b719cea1 (patch) | |
tree | 66f1a987eb87476db199cb8ed1612cbf562d4ffc | |
parent | 8a02c5e65c73b4b10a10198190fa815213445b73 (diff) | |
download | haskell-22bb78bb02718e162130690dfb9a11d7b719cea1.tar.gz |
Expand notes in TcFlatten
-rw-r--r-- | compiler/typecheck/TcFlatten.hs | 24 |
1 files changed, 20 insertions, 4 deletions
diff --git a/compiler/typecheck/TcFlatten.hs b/compiler/typecheck/TcFlatten.hs index 2c72c930b4..2b11f99ace 100644 --- a/compiler/typecheck/TcFlatten.hs +++ b/compiler/typecheck/TcFlatten.hs @@ -983,10 +983,26 @@ also indicated that the early reduction should not use the flat-cache, but that the later reduction should. It's possible that with more examples, we might learn that these knobs should be set differently. -Once we've got a flat rhs, we extend the flatten-cache to record the -result. Doing so can save lots of work when the same redex shows up -more than once. Note that we record the link from the redex all the -way to its *final* value, not just the single step reduction. +An example of where the early reduction appears helpful: + + type family Last x where + Last '[x] = x + Last (h ': t) = Last t + + workitem: (x ~ Last '[1,2,3,4,5,6]) + +Flattening the argument never gets us anywhere, but trying to flatten +it at every step is quadratic in the length of the list. Reducing more +eagerly makes simplifying the right-hand type linear in its length. + +At the end, once we've got a flat rhs, we extend the flatten-cache to record +the result. Doing so can save lots of work when the same redex shows up more +than once. Note that we record the link from the redex all the way to its +*final* value, not just the single step reduction. Interestingly, using the +flat-cache for the first reduction resulted in an increase in allocations +of about 3% for the four T9872x tests. However, using the flat-cache in +the later reduction is a similar gain. I (Richard E) don't currently (Dec '14) +have any knowledge as to *why* these facts are true. ************************************************************************ * * |