From 77398b678aba45ba25932a39b7e8a7a31d0dd6f3 Mon Sep 17 00:00:00 2001 From: Sylvain Henry Date: Sun, 9 Aug 2020 01:20:49 +0200 Subject: Avoid allocations in `splitAtList` (#18535) As suspected by @simonpj in #18535, avoiding allocations in `GHC.Utils.Misc.splitAtList` when there are no leftover arguments is beneficial for performance: On CI validate-x86_64-linux-deb9-hadrian: T12227 -7% T12545 -12.3% T5030 -10% T9872a -2% T9872b -2.1% T9872c -2.5% Metric Decrease: T12227 T12545 T5030 T9872a T9872b T9872c --- compiler/GHC/Utils/Misc.hs | 13 ++++++++----- 1 file changed, 8 insertions(+), 5 deletions(-) (limited to 'compiler') diff --git a/compiler/GHC/Utils/Misc.hs b/compiler/GHC/Utils/Misc.hs index e0ef6abd0a..1d827e7902 100644 --- a/compiler/GHC/Utils/Misc.hs +++ b/compiler/GHC/Utils/Misc.hs @@ -774,12 +774,15 @@ dropList _ xs@[] = xs dropList (_:xs) (_:ys) = dropList xs ys +-- | Given two lists xs=x0..xn and ys=y0..ym, return `splitAt n ys`. splitAtList :: [b] -> [a] -> ([a], [a]) -splitAtList [] xs = ([], xs) -splitAtList _ xs@[] = (xs, xs) -splitAtList (_:xs) (y:ys) = (y:ys', ys'') - where - (ys', ys'') = splitAtList xs ys +splitAtList xs ys = go 0 xs ys + where + -- we are careful to avoid allocating when there are no leftover + -- arguments: in this case we can return "ys" directly (cf #18535) + go _ _ [] = (ys, []) -- len(ys) <= len(xs) + go n [] bs = (take n ys, bs) -- = splitAt n ys + go n (_:as) (_:bs) = go (n+1) as bs -- drop from the end of a list dropTail :: Int -> [a] -> [a] -- cgit v1.2.1