Data.Vector.Generic.length not fusible #306
Milestone
Comments
gksato
added a commit
to gksato/vector
that referenced
this issue
Jun 3, 2020
This change makes fusible 'Data.Vector.Generic.length', which currently can be inlined but doesn't fuse well. Before this revision, 'length' uses non-fusible 'stream''. This revision replaces 'stream'' with fusible 'stream', and at the same time substitute the mutually-recursive occurrences of 'length' with 'basicLength'. Rationale: The current definition was introduced in the commit a811a86. Prior to that commit, 'length' could not even be inlined, because GHC elected it to be a loop-breaker due to the cyclic references among 'stream', 'clone', 'length', and 'unsafeCopy'. This failure of inlining was reported as haskell#97. The commit a811a86 resolved this by replacing 'stream' with 'stream'' in the definition of 'length'. The function 'stream' refers to 'clone' in its fusion rule, but 'stream'' doesn't possess any rule. This cuts open the cycle of references and makes 'length' inlinable. However, since 'stream'' doesn't possess any rule, defining 'length' = 'Bundle.length' . 'stream'' is all the same as setting 'length' = 'basicLength'. This prevents any stream fusion from happening. This commit resolves this problem by resetting 'length' back to be 'Bundle.length' . 'stream', and instead replacing cyclic occurrence of 'length' with 'basicLength' (Just *inlined the simplification result of the definition*). Now 'length' is both inlinable and fusible. Fixes: haskell#306 See also: haskell#97
Merged
gksato
added a commit
to gksato/vector
that referenced
this issue
Jun 20, 2020
This change makes fusible 'Data.Vector.Generic.length', which currently can be inlined but doesn't fuse well. Before this revision, 'length' uses non-fusible 'stream''. This revision replaces 'stream'' with fusible 'stream', and at the same time substitute the mutually-recursive occurrences of 'length' with 'basicLength'. Rationale: The current definition was introduced in the commit a811a86. Prior to that commit, 'length' could not even be inlined with older GHCs, which elected 'length' to be a loop-breaker due to the cyclic references among 'clone', 'unsafeCopy', 'length' and 'stream': * 'clone' refers to 'length' and 'unsafeCopy' in its definition; * 'unsafeCopy' refers to 'length' in its definition; * 'length' referred to 'stream' in its definition; * 'stream' refers to none of the above in its definition, but the rule 'New.unstream/stream' rewrites @'New.unstream' ('stream' v)@ with @'clone' v@. This failure of inlining was reported as haskell#97. To be precise, this cycle of references is immaterial with newer GHCs like GHC 8.8.3. Since 'New.unstream' does not occur in the definitions of 'clone', 'unsafeCopy', and 'length', indefinite inlining will not happen anyway. GHC 8.8.3 seems to detect this immateriality of the referencial loop in question and refrains from setting 'length' as a loop-breaker, even with acdcff3 (the parent commit of a811a86). However with older GHCs, including GHC 8.0.2, regarded the cyclic references fatal and marked 'length' as a loop-breaker. Note that GHC 8.0.2 was current at the time a811a86 was introduced. The commit a811a86 resolved this by replacing 'stream' with 'stream'' in the definition of 'length'. The function 'stream' refers to 'clone' in its fusion rule, but 'stream'' doesn't possess any rule. This cut open the cycle of references and made 'length' inlinable. However, since 'stream'' doesn't possess any rule, defining 'length' = 'Bundle.length' . 'stream'' is all the same as setting 'length' = 'basicLength'. This prevents any stream fusion from happening. This commit resolves this problem by resetting 'length' back to be @'Bundle.length' . 'stream'@, and instead replacing cyclic occurrence of 'length' with 'basicLength' (Just *inlined the simplification result of the definition*). Now 'length' is both inlinable and fusible, even with older GHCs. Fixes: haskell#306 See also: haskell#97 haskell#111 haskell#155
Shimuuar
pushed a commit
that referenced
this issue
Jun 21, 2020
This change makes fusible 'Data.Vector.Generic.length', which currently can be inlined but doesn't fuse well. Before this revision, 'length' uses non-fusible 'stream''. This revision replaces 'stream'' with fusible 'stream', and at the same time substitute the mutually-recursive occurrences of 'length' with 'basicLength'. Rationale: The current definition was introduced in the commit a811a86. Prior to that commit, 'length' could not even be inlined with older GHCs, which elected 'length' to be a loop-breaker due to the cyclic references among 'clone', 'unsafeCopy', 'length' and 'stream': * 'clone' refers to 'length' and 'unsafeCopy' in its definition; * 'unsafeCopy' refers to 'length' in its definition; * 'length' referred to 'stream' in its definition; * 'stream' refers to none of the above in its definition, but the rule 'New.unstream/stream' rewrites @'New.unstream' ('stream' v)@ with @'clone' v@. This failure of inlining was reported as #97. To be precise, this cycle of references is immaterial with newer GHCs like GHC 8.8.3. Since 'New.unstream' does not occur in the definitions of 'clone', 'unsafeCopy', and 'length', indefinite inlining will not happen anyway. GHC 8.8.3 seems to detect this immateriality of the referencial loop in question and refrains from setting 'length' as a loop-breaker, even with acdcff3 (the parent commit of a811a86). However with older GHCs, including GHC 8.0.2, regarded the cyclic references fatal and marked 'length' as a loop-breaker. Note that GHC 8.0.2 was current at the time a811a86 was introduced. The commit a811a86 resolved this by replacing 'stream' with 'stream'' in the definition of 'length'. The function 'stream' refers to 'clone' in its fusion rule, but 'stream'' doesn't possess any rule. This cut open the cycle of references and made 'length' inlinable. However, since 'stream'' doesn't possess any rule, defining 'length' = 'Bundle.length' . 'stream'' is all the same as setting 'length' = 'basicLength'. This prevents any stream fusion from happening. This commit resolves this problem by resetting 'length' back to be @'Bundle.length' . 'stream'@, and instead replacing cyclic occurrence of 'length' with 'basicLength' (Just *inlined the simplification result of the definition*). Now 'length' is both inlinable and fusible, even with older GHCs. Fixes: #306 See also: #97 #111 #155
lehins
pushed a commit
that referenced
this issue
Jan 16, 2021
This change makes fusible 'Data.Vector.Generic.length', which currently can be inlined but doesn't fuse well. Before this revision, 'length' uses non-fusible 'stream''. This revision replaces 'stream'' with fusible 'stream', and at the same time substitute the mutually-recursive occurrences of 'length' with 'basicLength'. Rationale: The current definition was introduced in the commit a811a86. Prior to that commit, 'length' could not even be inlined with older GHCs, which elected 'length' to be a loop-breaker due to the cyclic references among 'clone', 'unsafeCopy', 'length' and 'stream': * 'clone' refers to 'length' and 'unsafeCopy' in its definition; * 'unsafeCopy' refers to 'length' in its definition; * 'length' referred to 'stream' in its definition; * 'stream' refers to none of the above in its definition, but the rule 'New.unstream/stream' rewrites @'New.unstream' ('stream' v)@ with @'clone' v@. This failure of inlining was reported as #97. To be precise, this cycle of references is immaterial with newer GHCs like GHC 8.8.3. Since 'New.unstream' does not occur in the definitions of 'clone', 'unsafeCopy', and 'length', indefinite inlining will not happen anyway. GHC 8.8.3 seems to detect this immateriality of the referencial loop in question and refrains from setting 'length' as a loop-breaker, even with acdcff3 (the parent commit of a811a86). However with older GHCs, including GHC 8.0.2, regarded the cyclic references fatal and marked 'length' as a loop-breaker. Note that GHC 8.0.2 was current at the time a811a86 was introduced. The commit a811a86 resolved this by replacing 'stream' with 'stream'' in the definition of 'length'. The function 'stream' refers to 'clone' in its fusion rule, but 'stream'' doesn't possess any rule. This cut open the cycle of references and made 'length' inlinable. However, since 'stream'' doesn't possess any rule, defining 'length' = 'Bundle.length' . 'stream'' is all the same as setting 'length' = 'basicLength'. This prevents any stream fusion from happening. This commit resolves this problem by resetting 'length' back to be @'Bundle.length' . 'stream'@, and instead replacing cyclic occurrence of 'length' with 'basicLength' (Just *inlined the simplification result of the definition*). Now 'length' is both inlinable and fusible, even with older GHCs. Fixes: #306 See also: #97 #111 #155
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Unfortunately, the function
Data.Vector.Generic.lengthis not currently covered by stream fusion. This is becauselengthis defined in terms ofData.Vector.Generic.stream', which does not admit fusion rules at all.As a result, the following simple code:
https://gist.github.com/gksato/417030a1f19f1f376dcb2fabaf66c10a#file-test-hs
does require a big allocation:
https://gist.github.com/gksato/417030a1f19f1f376dcb2fabaf66c10a#file-testbefore-ddump-simpl
I'm soon gonna submit a pull request to fix this!
The text was updated successfully, but these errors were encountered: