git.iko.soy/streamly
on 22bfa72 help sign in
streamly/design/inlining.md
123 lines 5.1 kB history raw
1## INLINE Phases
3A missing inline or inline in an incorrect GHC simplifier phase can adversely
4impact performance. We use three builtin phases of GHC simplifier for inlining
5i.e. phase 0, 1 and 2. We have defined them as follows in `inline.h`:
7```
8#define INLINE_EARLY INLINE [2]
9#define INLINE_NORMAL INLINE [1]
10#define INLINE_LATE INLINE [0]
11```
13## Low Level `fromStreamD/toStreamD` Fusion
15The combinators in `Streamly.Prelude` are defined in terms of combinators in
16`Streamly.Internal.Data.Stream.StreamD` (Direct style streams) or `Streamly.Internal.Data.Stream.StreamK`
17(CPS style streams). We convert the stream from `StreamD` to `StreamK`
18representation or vice versa in some cases.
20In the first inlining phase (INLINE_EARLY or INLINE) we expand
21the combinators in `Streamly.Prelude` into
22fromStreamD/fromStreamK/toStreamD/toStreamK and combinators defined in StreamD
23or StreamK modules. Once we do that fromStreamD/toStreamD get exposed and we
24can apply rewrite rules to rewrite transformations like `fromStreamK .
25toStreamK` to `id`. A plain `INLINE` pragma is usually enough on combinators in
26`Streamly.Prelude`.
28```
29{-# RULES "fromStreamK/toStreamK fusion"
30 forall s. toStreamK (fromStreamK s) = s #-}
31```
33Also, we have to prevent fromStreamK and toStreamK themselves from inlining in
34this phase so that rewrite rules can be applied on them, therefore, we annotate
35these functions with `INLINE_LATE`.
37## Fallback Rules
39In some cases, if the operation could not fuse we want to use a fallback
40rewrite rule in the next phase. For such cases we use the INLINE_EARLY phase
41for the first rewrite and the INLINE_NORMAL phase for the fallback rules.
43The fallback rules make sure that if we could not fuse the direct style
44operations then better use the CPS style operation, because unfused direct
45style would have worse performance than the CPS style ops.
47```
48{-# INLINE_EARLY unfoldr #-}
49unfoldr :: (Monad m, IsStream t) => (b -> Maybe (a, b)) -> b -> t m a
50unfoldr step seed = fromStreamS (S.unfoldr step seed)
51{-# RULES "unfoldr fallback to StreamK" [1]
52 forall a b. S.toStreamK (S.unfoldr a b) = K.unfoldr a b #-}
53```
55## High Level Operation Fusion
57Since each high level combinator in `Streamly.Prelude` is wrapped in
58`fromStreamD/toStreamD` etc. the combinator fusion cannot work unless we have
59removed those and exposed consecutive operations e.g. a `map` followed by
60another `map`. Assuming that redundant `fromStreamK/toStreamK` have been
61removed in the `INLINE_EARLY` phase, we can then apply the combinator fusion
62rules in the `INLINE_NORMAL` phase. For example, we can fuse two `map`
63operations into a single `map` operation. Note that now we have exposed the
64`StreamD/StreamK` implementations of combinators and the rules would apply on
65those.
67## Inlining Higher Order Functions
69Note that partially applied functions cannot be inlined. So if we have a code
70like this:
72```
73concatMap1 src = runStream $ S.concatMap (S.replicate 3) src
74```
76We want to ensure that `concatMap` gets inlined before `replicate` so that
77`replicate` becomes fully applied before it gets inlined. Currently ensuring
78that both of them are inlined in the same phase (`INLINE_NORMAL`) seems to be
79enough to achieve that. In general, we should try to ensure that higher order
80functions are inlined before or in the same phase as the functions they can
81consume as arguments. This means `StreamD` combinators should not be marked
82as `INLINE` or `INLINE_EARLY`, instead they should all be marked as
83`INLINE_NORMAL` because higher order funcitons like `concatMap`/`map`/`mapM`
84etc are marked as `INLINE_NORMAL`. `StreamD` functions in other modules like
85`Streamly.Memory.Array` should also follow the same rules.
87## Stream Fusion
89In StreamD combinators, inlining the inner step or loop functions too early
90i.e. in the same pahse or before the outer function is inlined may block stream
91fusion opportunities. Therefore, the inner step functions and folding loops are
92marked as INLINE_LATE.
94## Specialization
96In some cases, the `step` function in `StreamD` does not get specialized when
97inlined unless it is provided with an explicit signature or made a lambda, for
98example, in the `replicate/replicateM` combinator we need the type annotation
99on `i` to get it specialized:
101```
102 {-# INLINE_LATE step #-}
103 step _ (i :: Int) =
104 if i <= 0
105 then return Stop
106 else do
107 x <- action
108 return $ Yield x (i - 1)
109```
111`-flate-specialise` also helps in this case.
113## Stream and Fold State Data Structures
115Since state is an internal data structure threaded around in the loop, it is a
116good practice to use strict unboxed fields for state data structures where
117possible. In most cases it is not necessary, but in some cases it may affect
118fusion and make a difference of 10x performance or more. For example, using
119non-strict fields can increase the code size for internal join points and
120functions created during transformations, which can affect the inlining of
121these code blocks which in turn can affect stream fusion.
123See https://gitlab.haskell.org/ghc/ghc/issues/17075 .