diff options
| author | Sylvain Henry <sylvain@haskus.fr> | 2020-08-09 01:20:49 +0200 |
|---|---|---|
| committer | Marge Bot <ben+marge-bot@smart-cactus.org> | 2020-08-09 21:18:34 -0400 |
| commit | 77398b678aba45ba25932a39b7e8a7a31d0dd6f3 (patch) | |
| tree | 99dbc535e3649643db228f118462342db2cf0954 | |
| parent | c8873b52f6a16202c3cb839e988c1406b8f67cfe (diff) | |
| download | haskell-77398b678aba45ba25932a39b7e8a7a31d0dd6f3.tar.gz | |
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
| -rw-r--r-- | compiler/GHC/Utils/Misc.hs | 13 |
1 files changed, 8 insertions, 5 deletions
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] |