1# Guidelines for writing well optimized code
3Stream operations are always part of a loop. Usually the loop consists of a
4stream generation or an unfold operation followed by stream transformation
5functions (e.g. map) and then a stream elimination operation or a fold
8The default or most common stream representation used in streamly is
9`StreamD` which is a direct style (compare with CPS representation
10`StreamK`) stream representation. All the direct style operations in
11a loop "fuse" together to form a tight machine loop eliminating any
12intermediate constructors, therefore, reducing allocations and cpu cost.
13This elimination of intermediate constructors in a stream loop is known
16## Writing high performance code using streamly
18This section outlines guidelines for writing code using the available
19combinators. The guidelines for writing new combinators are provided in
22Note that there is no absolute benchmark for performance, most of
23the time even without following the guidelines you may get excellent
24performance for the task at hand. Two important points to keep in mind
27* See if you actually need more performance
28* See if the code you are optimizing is in fast path
32When your performance requirements are stringent you may want to care
33about not breaking stream fusion unnecessarily. Certain operations do
34not fuse and act as a barrier to stream fusion. If these operations are
35part of a loop, the loop won't fuse completely. In some cases these may
36be necessary but in others it may be possible to replace these with
37better fusing operations. These operations include:
39* Avoid unnecessary use of stream append operations in code that should
40 fuse. Append operations in general force CPS style breaking stream
41 fusion. Some direct style append operations can fuse but they won't
42 scale for more than a few appends.
43* Avoid unnecessary use of the stream monad if fusion is important. You
44 may use functor or applicative though.
45* Concurrent stream operations cannot fuse
46* Operations involving exception primitives like catch/throw/mask
47 on elements of the stream cannot fuse.
48* Stream loops involving FFI calls on the elements of the stream
50The haddock documentation includes a note when an operation cannot fuse.
54* Use unfolds especially when higher order operations are involved. For
55 example, `unfoldMany` can fuse completely whereas `concatMap` would
57* Use `outerProduct` in `Unfold` module instead of using the monad instance of
58 streams to fuse nested loops where performance matters. See the unfold
59 benchmarks for an example. `outerProduct` can give you C like nested loop
64To make sure fusion can occur INLINE any operations that are part of a
65stream loop but factored out as separate functions.
69Keep the fold and scan accumulators strict. You could also consider
70using mutable state in a fold accumulator if the state is large. A
71large immutable structure as an accumulator may cause optimization
72issues. See the `WordCount` example for an example of this case.
74## Writing streamly combinators
76To enable stream fusion in a direct style stream all the operations that
77are part of a loop must be inlined:
79* Use an explicit INLINE pragma on any combinator that could be part of a loop
80 to ensure they will be inlined.
81* When a higher order function consumes another function then ensure that the
82 higher order function is inlined in the same phase or before the function it
83 is consuming. Use appropriate inline phases to ensure proper inline ordering
86### Streams and Unfolds
88Stream and Unfold State. Direct style stream and unfold combinators use a
89state data type to represent the internal state of the stream/unfold generator.
91* In some cases we may have to add a `FUSE` annotation on the state type to
92 ensure that all the internal join points created by GHC are inlined with the
93 help of the `fusion-plugin`.
94* In rare cases we may need to use a strictness annotation on the state
95 to allow fusion. `parseMany` and `splitOnSeq` are such examples.
97Step function of a stream or unfold:
99* Do not introduce unnecessary states. If there is only one entry point of a
100 state then perhaps you want to collapse the state into the state from which
101 it is called. More states means more jumps and may affect code locality, and
102 efficiency of low level code (e.g. register allocation) because of
103 independent placement of the code blocks in different states.
105 In some cases we may have to go against the above guideline and introduce a
106 separate state even though it is not necessary. See the GroupConsume state in
107 foldMany for an example.
108* Keep minimum possible data in state. More variables in state may lead
109 to poor performance because the state may not fit into registers and the
110 spill may cause allocations on each iteration of the loop. Mutable state
111 may help in such cases.
112* The step function must be annotated such that it gets inlined after the main
113 combinator (`INLINE_LATE`).
115Multiple yield points or single?:
117* A single yield point is usually desirable, however, not always necessary.
118 In some cases multiple yield points may in fact be needed for fusion,
119 see `splitOnSeq` for an example. Or maybe its fusing because of a
120 direct yield instead of going through an indirect common yielding
123Recursion in step function:
125* In general, we avoid making the step function recursive. Use the
126 `Skip` constructor to remove recursion. Recursive step function can
127 introduce optimization barriers that are harder to remove by the GHC
130 However, in some cases it may be better to have a local recursive
131 loop. A recursive loop can help us avoid threading around some large
132 state values every time. Values that do not change across a loop can
133 be factored in the scope outside the loop (static argument transform),
134 this way we can create a local loop which is more efficient than
135 threading around the state in a larger loop. See the `splitOnSeq`
136 combinator as an example where we use a local recursive loop, it fuses
137 and is significantly efficient compared to using `Skip`.
139 In a local recursive loop use SPEC and annotate even the rest of the
140 loop arguments as strict where needed. We have observed that when the
141 arguments were not strict the loop does not fuse (splitOnSeq).
143### Fold and Parser drivers
145Recursive loop closing operations:
147* When writing recursive looping combinators using StreamD (e.g. foldlM' in
148 StreamD) use a strict SPEC argument in the recursive loops to ensure that
149 "Spec Constructor" optimization removes boxed arguments and reduces
152### Fold and Parser combinators
154State of a Fold or Parser:
156* The accumulator of a fold must be a strict data structure. Use the strict
157 data structures provided in `Streamly.Internal.Data` for this purpose or use
158 explicit bang annotation to make the data strict.
159* In some cases you may need a `FUSE` annotation on the state type to ensure
160 that any internal join points created by GHC are always inlined with the help
161 of the fusion-plugin.
163The step function of a Fold or Parser:
165* Never make the fold step recursive, recursion creates an optimization barrier
166 for the GHC simplifier. Use `Partial` or `Continue` constructors to avoid
169* Sometimes you may need an explicit INLINE on the step function.
171### NOINLINE, isolating the closed loop
173We want the loop iterations to be optimized and the loop stages to be fused to
174generate a tighter loop. However, it is not necessarily optimal to inline the
175whole loop itself into a parent function. For example, consider the following
176function in the `FileSystem.Handle` benchmarks:
179{-# NOINLINE readWriteAfter_Stream #-}
180readWriteAfter_Stream :: Handle -> Handle -> IO ()
181readWriteAfter_Stream inh devNull =
182 let readEx = IP.after_ (hClose inh) (S.unfold FH.read inh)
183 in S.fold (FH.write devNull) readEx
186If this is inlined into a parent benchmark group list, this leads to
187many times performance degradation. That's because inlining the loop
188into a bigger structure interferes with the optimization of the loop
189body itself and it may not fuse. Whereas it is desirable to INLINE all
190the stages of a loop, it is often not useful to inline the whole loop
191itself, in fact we may have to occasionally use a `NOINLINE` so that the
192compiler does not inline it.
194We need to be careful about NOINLINE on polymorphic functions. When
195NOINLINE is used, the function cannot be specialized causing huge
196performance degradation. To avoid that we can either make the
197function monomorphic or sometimes using `NOINLINE [0]` can do the
198trick. `NOINLINE [0]` blocks inlining in earlier phases but lets it
199specialize in the last phase, inlining in the last phase is left to
200the compiler. `INLINE [0]` may sound the same as `NOINLINE [0]`,
201however, it behaves differently because we ask the compiler to INLINE
202it compulsorily and it may not give us the desired results. The
203Data.Fold.writeLastN benchmark is one such case where `NOINLINE [0]`
204provides much better performance than `INLINE [0]`.
208It is not always useful to specialize function calls for all constructors, some
209constructors may just add to code bloat or add overhead of passing unboxed
210values in a loop. In such cases the `NoSpecConstr` annotation can be useful.
211See the `parselMx'` function in `StreamD` module.
213### StreamK operations
215StreamK uses foldr/build fusion to a very limited degree. StreamK is not the
216primary representation in streamly but is used for several operations that
217cannot scale in StreamD representation. StreamK is relatively immune to compiler
218optimizations. In some cases you may need an INLINE pragma to improve the
221### How to debug non-fusing code?
223Strip down the code to a minimal version until it starts fusing and then
224start building it up from there adding more things incrementally. At
225each stage keep checking if the code is fusing. At some point it
226won't fuse. See what we added that made the code not fuse. Go through
227the guidelines above to check if we did something that that is not
228recommended. Or raise an issue for GHC to be fixed if possible.
230# GHC Optimizations In Streamly
232There are three important levels of optimizations used in streamly:
234* CPS style stream representation (StreamK) to direct style (StreamD)
235 conversion and vice-versa using rewrite rules
236* Stream fusion using case-of-case optimization in StreamD
237* foldr/build fusion using rewrite rules in StreamK
241Inlining of functions at the right time is crucial for all these optimization
242to work. A missing inline or inline in an incorrect GHC simplifier phase can
243adversely impact performance. We use three builtin phases of GHC simplifier
244for inlining i.e. phase 0, 1 and 2. We have defined them as follows in
248#define INLINE_EARLY INLINE [2]
249#define INLINE_NORMAL INLINE [1]
250#define INLINE_LATE INLINE [0]
253We also use INLINE [3] in some cases.
255## `fromStreamD/toStreamD` Fusion
257The combinators in `Streamly.Prelude` are defined in terms of combinators in
258`Streamly.Internal.Data.Stream.StreamD` (Direct style streams) or
259`Streamly.Internal.Data.StreamK` (CPS style streams). We convert the
260stream from `StreamD` to `StreamK` representation or vice versa in some cases.
262Most operations use the StreamD representation, however, stream append
263operations and monad instances use StreamK representation because StreamD would
264not perform well in these cases. We use rewrite rules to convert from one
265representation to another when required. For this reason the combinators in
266Streamly.Prelude are written using fromStreamD/fromStreamK etc.
268In the first inlining phase (INLINE_EARLY or INLINE) we expand the combinators
269in `Streamly.Prelude` into fromStreamD/fromStreamK/toStreamD/toStreamK and
270combinators defined in StreamD or StreamK modules. Once we do that
271fromStreamD/toStreamD get exposed and we can apply rewrite rules to rewrite
272transformations like `fromStreamK . toStreamK` to `id`. A plain `INLINE`
273pragma is usually enough on combinators in `Streamly.Prelude`.
276{-# RULES "fromStreamK/toStreamK fusion"
277 forall s. toStreamK (fromStreamK s) = s #-}
280Also, we have to prevent fromStreamK and toStreamK themselves from inlining in
281this phase so that rewrite rules can be applied on them, therefore, we annotate
282these functions with `INLINE_LATE`.
286In some cases, if the operation could not fuse we want to use a fallback
287rewrite rule in the next phase. For such cases we use the INLINE_EARLY phase
288for the first rewrite and the INLINE_NORMAL phase for the fallback rules.
290The fallback rules make sure that if we could not fuse the direct style
291operations then better use the CPS style operation, because unfused direct
292style would have worse performance than the CPS style ops.
295{-# INLINE_EARLY unfoldr #-}
296unfoldr :: (Monad m, IsStream t) => (b -> Maybe (a, b)) -> b -> t m a
297unfoldr step seed = fromStreamS (S.unfoldr step seed)
298{-# RULES "unfoldr fallback to StreamK" [1]
299 forall a b. S.toStreamK (S.unfoldr a b) = K.unfoldr a b #-}
302## High Level Operation Fusion
304Since each high level combinator in `Streamly.Prelude` is wrapped in
305`fromStreamD/toStreamD` etc. the combinator fusion cannot work unless we have
306removed those and exposed consecutive operations e.g. a `map` followed by
307another `map`. Assuming that redundant `fromStreamK/toStreamK` have been
308removed in the `INLINE_EARLY` phase, we can then apply the combinator fusion
309rules in the `INLINE_NORMAL` phase. For example, we can fuse two `map`
310operations into a single `map` operation. Note that now we have exposed the
311`StreamD/StreamK` implementations of combinators and the rules would apply on
314## Inlining Higher Order Functions
316Note that partially applied functions cannot be inlined. So if we have a code
320concatMap1 src = runStream $ S.concatMap (S.replicate 3) src
323We want to ensure that `concatMap` gets inlined before `replicate` so that
324`replicate` becomes fully applied before it gets inlined. Currently ensuring
325that both of them are inlined in the same phase (`INLINE_NORMAL`) seems to be
326enough to achieve that. In general, we should try to ensure that higher order
327functions are inlined before or in the same phase as the functions they can
328consume as arguments. This means `StreamD` combinators should not be marked
329as `INLINE` or `INLINE_EARLY`, instead they should all be marked as
330`INLINE_NORMAL` because higher order functions like `concatMap`/`map`/`mapM`
331etc are marked as `INLINE_NORMAL`. `StreamD` functions in other modules like
332`Streamly.Data.Array.Foreign` should also follow the same rules.
336In StreamD combinators, inlining the inner step or loop functions too early
337i.e. in the same phase or before the outer function is inlined may block stream
338fusion opportunities. Therefore, the inner step functions and folding loops are
339marked as INLINE_LATE.
343In some cases, the `step` function in `StreamD` does not get specialized when
344inlined unless it is provided with an explicit signature or made a lambda, for
345example, in the `replicate/replicateM` combinator we need the type annotation
346on `i` to get it specialized:
349 {-# INLINE_LATE step #-}
355 return $ Yield x (i - 1)
358`-flate-specialise` also helps in this case.
360## Stream and Fold State Data Structures
362Since state is an internal data structure threaded around in the loop, it is a
363good practice to use strict unboxed fields for state data structures where
364possible. In most cases it is not necessary, but in some cases it may affect
365fusion and make a difference of 10x performance or more. For example, using
366non-strict fields can increase the code size for internal join points and
367functions created during transformations, which can affect the inlining of
368these code blocks which in turn can affect stream fusion.
370See https://gitlab.haskell.org/ghc/ghc/issues/17075 .
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list