#2754: Strictness analyzer fails on an implementation of foldl
-----------------------------+----------------------------------------------
Reporter: nimnul | Owner:
Type: feature request | Status: closed
Priority: normal | Milestone:
Component: Compiler | Version: 6.8.3
Severity: normal | Resolution: invalid
Keywords: | Difficulty: Unknown
Testcase: | Architecture: x86
Os: Windows |
-----------------------------+----------------------------------------------
Comment (by nimnul):
Replying to [comment:7 dons]:
> Ah, much clearer.
>
> So what we have is not a bug, but rather a feature request: you would
like the strictness analyser extended in some way such that foldl is
always equivalent to foldl'.
No no. foldl and foldl' are different functions. While foldl performs
extra graph node allocations, compared to foldl', when op is strict,
foldl' performs extra reductions if op is not strict. For tight loops like
this foldl' is better than foldl. But if op is not strict and a lot of
computations can be saved by not evaluating certain intermediate r, foldl
can be better. Am I wrong?
I don't want foldl to be always equivalent to foldl'. I only want them to
be equivalent if op is strict in r.
The problem is complex - while foldA and foldB differ only by a strictness
annotation, the reason why compiler fails to insert the annotation may be
not related to the strictness analyzer at all. It can be specializer
failure (does ghc has one?), inliner failure, missing rewrite rules in the
optimizer, anything.
And it is not necessary to fix the problem by fixing optimizer - a
workaround could be provided so one can use pragmas to achieve the result.
Now INLINE pragma doesn't work because foldA is recursive, and that's ok,
but the SPECIALIZE pragma is somewhat limited and can be improved - for
example, I cannot tell the compiler to specialize foldA by inlining its
first argument. Such specialization is not my invention - it has been used
for years in C++ to avoid indirect calls when a function object is passed
to a template function. And modern c++ compilers such as Microsoft's and
GCC can even instantiate functions accepting function pointers.
While automated instantiation and inlining is cumbersome to implement, and
both inlining/specializing everything and inlining/specializing nothing
can lead to poor performance, a developer should be able to hint - such
tuning may be beneficial for libraries. And better "self-optimizing"
libraries like Stream Fusion make life better for library users like me,
as high-performance libraries reduce the need for performance profiling
and optimizations in client code.
So there can be very different ways to improve compilation of code
fragments like foldA. And it's not just a narrow problem of programmers
trying to reimplement foldl - I believe there are other scenarios when
recursive definitions fail to optimize because they cannot be inlined.
I cannot suggest exactly what the problem is, and how is better to fix it
- I have a faint idea what happens inside of GHC optimizer. I'm merely
reporting code which is problematic for current optimizer.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2754#comment:9>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
