summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorThomas Miedema <thomasmiedema@gmail.com>2015-08-05 10:31:46 +0200
committerThomas Miedema <thomasmiedema@gmail.com>2015-08-12 16:21:26 +0200
commitf903949beee3a4e0a925003b5553066c9f513c11 (patch)
tree3b633ad21554210d50b472af0b053841e1ddeb1b
parent85bf76a8f8015ed6adb65095d53d8af933080354 (diff)
downloadhaskell-f903949beee3a4e0a925003b5553066c9f513c11.tar.gz
Pretty: improving the space/time performance of vcat, hsep, hcat (#10735)
After 5d57087e314bd484dbe14958f9b422be3ac6641a ("Pretty: fix a broken invariant"), T3294 showed 50% more max_bytes_used (#3294). After this commit, max_bytes_used is back to what it was before, and the test passes again. This is a backport of a bug fix by Benedikt Huber (#2393), from commit 1e50748beaa4bd2281d323b18ea51c786bba04a1 in the pretty library. From https://mail.haskell.org/pipermail/libraries/2008-June/009991.html: vcat (hsep,cat) is implemented in an unneccessarily strict way. We only get some output after all of vcat's arguments are evaluated and checked against being Empty. This can be improved by only checking the right argument of foldr against being Empty, and then applying an Empty-filter on the resulting Doc. Space improvement is obvious. The microbenchmark (code.haskell.org/~bhuber/Text/PrettyPrint/ HughesPJPerfCheck.hs) suggests that the improvements in time are remarkable too.
-rw-r--r--compiler/utils/Pretty.hs19
1 files changed, 16 insertions, 3 deletions
diff --git a/compiler/utils/Pretty.hs b/compiler/utils/Pretty.hs
index 29a7b84168..4aae2c8c53 100644
--- a/compiler/utils/Pretty.hs
+++ b/compiler/utils/Pretty.hs
@@ -529,15 +529,15 @@ reduceDoc p = p
-- | List version of '<>'.
hcat :: [Doc] -> Doc
-hcat = foldr (<>) empty
+hcat = reduceAB . foldr (beside_' False) empty
-- | List version of '<+>'.
hsep :: [Doc] -> Doc
-hsep = foldr (<+>) empty
+hsep = reduceAB . foldr (beside_' True) empty
-- | List version of '$$'.
vcat :: [Doc] -> Doc
-vcat = foldr ($$) empty
+vcat = reduceAB . foldr (above_' False) empty
-- | Nest (or indent) a document by a given number of positions
-- (which may also be negative). 'nest' satisfies the laws:
@@ -584,6 +584,19 @@ mkUnion :: Doc -> Doc -> Doc
mkUnion Empty _ = Empty
mkUnion p q = p `union_` q
+beside_' :: Bool -> Doc -> Doc -> Doc
+beside_' _ p Empty = p
+beside_' g p q = Beside p g q
+
+above_' :: Bool -> Doc -> Doc -> Doc
+above_' _ p Empty = p
+above_' g p q = Above p g q
+
+reduceAB :: Doc -> Doc
+reduceAB (Above Empty _ q) = q
+reduceAB (Beside Empty _ q) = q
+reduceAB doc = doc
+
nilAbove_ :: RDoc -> RDoc
nilAbove_ = NilAbove