git.iko.soy/streamly
on master help sign in
streamly/docs/User/HowTo/optimizing.md
98 lines 4.8 kB history raw
1# Optimization Guide
3## Performance Optimizations
5A "closed loop" is any streamly code that generates a stream using
6unfold (or conceptually any stream generation combinator) and ends
7up eliminating it with a fold (conceptually any stream elimination
8combinator). It is essentially a loop processing multiple elements in
9a stream sequence, just like a `for` or `while` loop in imperative
10programming.
12Closed loops are generated in a modular fashion by stream generation,
13transformation and elimination combinators in streamly. Combinators
14transfer data to the next stream pipeline stage using data constructors.
15These data constructors are eliminated by the compiler using `stream
16fusion` optimizations, generating a very efficient loop.
18However, stream fusion optimization depends on proper inlining of the
19combinators involved. The fusion-plugin package mentioned earlier
20fills gaps for several optimizations that GHC does not perform
21automatically. It automatically inlines the internal definitions
22that involve the constructors we want to eliminate. In some cases
23fusion-plugin may not help and programmer may have to annotate the code
24manually for complete fusion. In this section we mention some of the
25cases where programmer annotation may help in stream fusion.
27Remember, you need to worry about performance only where it matters, try
28to optimize the fast path and not everything blindly.
30### INLINE annotations
32It may help to add INLINE annotations on any intermediate functions
33involved in a closed loop. In some cases you may have to add an inline
34phase as well as described below.
36Usually GHC has three inline phases - the first phase is pahse-2, the
37second phase is phase-1 and the last one is phase-0.
39#### Early INLINE
41Generally, you only have to inline the combinators or functions
42participating in a loop and not the whole loop itself. But sometimes
43you may want to inline the whole loop itself inside a larger
44function. In most cases you can just add an INLINE pragma on
45the function containing the loop. But you may need some special
46considerations in some (not common) cases.
48In some cases you may have to use INLINE[2] instead of INLINE which
49means inline the function early in phase-2. This may sometimes be
50needed on the because the performance of several combinators in streamly
51depends on getting inlined in phase-2 and if you use a plain `INLINE`
52annotation GHC may decide to delay the inlining in some cases. This is
53not very common but may be needed sometimes. Perhaps GHC can be fixed or
54we can resolve this using fusion-plugin in future.
56#### Delayed INLINE
58When a function is passed to a higher order function e.g. a function
59passed to `concatMap` or `unfoldMany` then we want the function to be
60inlined after the higher order is inlined so that proper fusion of the
61higher order function can occur. For such cases we usually add INLINE[1]
62on the function being passed to instruct GHC not to inline it too early.
64### Strictness annotations
66* Strictness annotations on data, specially the data used as accumulator in
67 folds and scans, can help in improving performance.
68* Strictness annotations on function arguments can help the compiler unbox
69 constructors in certain cases, improving performance.
70* Sometimes using `-XStrict` extension can help improve performance, if so you
71 may be missing some strictness annotations. `-XStrict` can be used as an aid
72 to detect missing annotations, using it blindly may regress performance.
74### Use tail recursion
76Do not use a strict `foldr` or lazy `foldl` unless you know what you are
77doing. Use lazy `foldr` for lazily transforming the stream and strict
78`foldl` for reducing the stream. If you are manually writing recursive
79code, try to use tail recursion where possible.
81## Build times and space considerations
83Haskell, being a pure functional language, confers special powers on
84GHC. It allows GHC to do whole program optimization. In a closed loop
85all the components of the loop are inlined and GHC fuses them together,
86performs many optimizing transformations and churns out an optimized
87fused loop code. Let's call it whole-loop-optimization.
89To be able to fuse the loop by whole-loop-optimization all the parts of the
90loop must be operated on by GHC at the same time to fuse them together. The
91amount of time and memory required to do so depends on the size of the loop.
92Huge loops can take a lot of time and memory. We have seen GHC take 4-5 GB of
93memory when a lot of combinators are used in a single module.
95If a module takes too much time and space we can break it into multiple
96modules moving some non-inlined parts in another module. There is
97another advantage of breaking large modules, it can take advantage of
98parallel compilation if they do not depend on each other.