Hi all, is there an easy-to read introductory paper on reasoning about performance in Haskell? Stuff like big-Oh space and time complexity of a function. What I'm mostly after is how to organize complexity reasoning given non-strict evaluation. In that situation, a function's complexity depends on what subexpressions of the parameters have already been evaluated, so you get rather complicated conditional formulae, and you also need to somehow express what parts of a passed-in parameter may get evaluated under what conditions. Is there even a good notation for that kind of stuff? Is there advice on how to organize the code to make performance formulae manageable? Example: Performance of length xs Turns out it is the number of items in xs, plus whatever you need to evaluate the list spine, as far as the list spine elements have not yet been evaluated (but you do not need to evaluate the list items). I have no idea how to even write that down. What notation to use so one can formally reason about it. Any pointers? Regards, Jo
If you're comfortable with imperative data structures, then you can go for
Okasaki's book:
http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/05216635...
Which developed from his Ph.D thesis available here:
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
People say both are very similar in their contents, but I can't say for
sure. I've read the first two chapters and found them to be enlightening.
On 4 December 2015 at 13:19, Joachim Durchholz
Hi all,
is there an easy-to read introductory paper on reasoning about performance in Haskell? Stuff like big-Oh space and time complexity of a function.
What I'm mostly after is how to organize complexity reasoning given non-strict evaluation. In that situation, a function's complexity depends on what subexpressions of the parameters have already been evaluated, so you get rather complicated conditional formulae, and you also need to somehow express what parts of a passed-in parameter may get evaluated under what conditions. Is there even a good notation for that kind of stuff? Is there advice on how to organize the code to make performance formulae manageable?
Example: Performance of length xs Turns out it is the number of items in xs, plus whatever you need to evaluate the list spine, as far as the list spine elements have not yet been evaluated (but you do not need to evaluate the list items). I have no idea how to even write that down. What notation to use so one can formally reason about it.
Any pointers?
Regards, Jo _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
-- Regards Sumit Sahrawat
Am 04.12.2015 um 09:01 schrieb Sumit Sahrawat, Maths & Computing, IIT (BHU):
If you're comfortable with imperative data structures, then you can go for Okasaki's book: http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/05216635... Which developed from his Ph.D thesis available here: http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
People say both are very similar in their contents, but I can't say for sure. I've read the first two chapters and found them to be enlightening.
I read the book, Okasaki is very enlightening but does not talk about how to deal with partially preevaluated data structures. Regards, Jo
Indeed. I find laziness and the non-composable nature of space complexity in Haskell to be a much harder beast to deal with than immutability. There is an *excellent* introduction to the basics of lazy evaluation in Graham Hutton's book /Programming in Haskell/ (chapter 12), but I don't know of any good references beyond that basic level. Let us know if you find some! Dimitri On 12/4/15 5:35 AM, Joachim Durchholz wrote:
Am 04.12.2015 um 09:01 schrieb Sumit Sahrawat, Maths & Computing, IIT (BHU):
If you're comfortable with imperative data structures, then you can go for Okasaki's book: http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/05216635...
Which developed from his Ph.D thesis available here: http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
People say both are very similar in their contents, but I can't say for sure. I've read the first two chapters and found them to be enlightening.
I read the book, Okasaki is very enlightening but does not talk about how to deal with partially preevaluated data structures.
Regards, Jo _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
For lazy evaluation, this is the best resource I've found:
https://hackhands.com/guide-lazy-evaluation-haskell
On 5 December 2015 at 06:31, Dimitri DeFigueiredo
Indeed. I find laziness and the non-composable nature of space complexity in Haskell to be a much harder beast to deal with than immutability.
There is an *excellent* introduction to the basics of lazy evaluation in Graham Hutton's book *Programming in Haskell* (chapter 12), but I don't know of any good references beyond that basic level. Let us know if you find some!
Dimitri
On 12/4/15 5:35 AM, Joachim Durchholz wrote:
Am 04.12.2015 um 09:01 schrieb Sumit Sahrawat, Maths & Computing, IIT (BHU):
If you're comfortable with imperative data structures, then you can go for Okasaki's book:
http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/05216635... Which developed from his Ph.D thesis available here: http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
People say both are very similar in their contents, but I can't say for sure. I've read the first two chapters and found them to be enlightening.
I read the book, Okasaki is very enlightening but does not talk about how to deal with partially preevaluated data structures.
Regards, Jo _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
-- Regards Sumit Sahrawat
Am 05.12.2015 um 02:01 schrieb Dimitri DeFigueiredo:
Indeed. I find laziness and the non-composable nature of space complexity in Haskell to be a much harder beast to deal with than immutability.
I can imagine. Immutability can be dealt with by applying a few principles in the key points, and everything will work out; space complexity is riddled with exceptions. OTOH space and time complexity are non-composable (well, not trivially composable anyway) even in a strict language. As software grows larger, people start doing all kinds of deferred evaluation strategies, and the problems crop up - with the added complication that the software is already so large that the root cause of some complexity problem is hidden behind lots of tiny details. So, I currently believe that Haskell is just showcasing the problem early. This is worth something, but I guess not for that majority of programmers who're doing business logic for websites, or for those just learning to code in Haskell and tripping over space complexity.
There is an *excellent* introduction to the basics of lazy evaluation in Graham Hutton's book /Programming in Haskell/ (chapter 12), but I don't know of any good references beyond that basic level. Let us know if you find some!
Sumit gave a link to backhands.com which has turned out to be pretty deep and accessible. Unfortunately, that link still does not offer a systematic approach to keeping tabs about complexity. So... the main question is still open. I hope somebody can shed insight about how to attack this. What do people do if they find their Haskell code to perform badly - do they all resort to ad-hockery, or is there a systematic approach that will either give insight what to change where? Even an approach that may fail is better than just ad hoc I think, as long as it succeeds often enough to be useful. Regards, Jo
Dear Joachim, you probably already know the basics of lazy evaluation, but to fix conventions, allow me to plug a tutorial of mine: https://hackhands.com/guide-lazy-evaluation-haskell/ As you mentioned, reasoning about time usage is not entirely straightforward, since expressions may be evaluated partially. Chris Okasaki's thesis/book does treat this problem in chapter 6, in order to clarify what amortization means in a language with persistent data structures, and why lazy evaluation is very useful for that. The main idea is that to each constructor of a data structure, we assign a cost, which is a number of "debits". Whenever we evaluate a constructor to WHNF, we have to pay the number of debits assigned to it. Then, the debits that we have paid so far will always be an upper bound on the time that we have spent evaluating the expression so far. For instance, the `length` function creates an integer whose assigned number of debits is twice the sum of the debits of each constructor in the input list. For more details, see also http://apfelmus.nfshost.com/articles/debit-method.html Ultimately, the point of the debit method is to reflect the time needed for evaluation of an expression (a notion from operational semantics) in the value that this expression represents (a notion from denotational semantics). Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com Joachim Durchholz wrote:
Hi all,
is there an easy-to read introductory paper on reasoning about performance in Haskell? Stuff like big-Oh space and time complexity of a function.
What I'm mostly after is how to organize complexity reasoning given non-strict evaluation. In that situation, a function's complexity depends on what subexpressions of the parameters have already been evaluated, so you get rather complicated conditional formulae, and you also need to somehow express what parts of a passed-in parameter may get evaluated under what conditions. Is there even a good notation for that kind of stuff? Is there advice on how to organize the code to make performance formulae manageable?
Example: Performance of length xs Turns out it is the number of items in xs, plus whatever you need to evaluate the list spine, as far as the list spine elements have not yet been evaluated (but you do not need to evaluate the list items). I have no idea how to even write that down. What notation to use so one can formally reason about it.
Any pointers?
Regards, Jo
participants (4)
-
Dimitri DeFigueiredo -
Heinrich Apfelmus -
Joachim Durchholz -
Sumit Sahrawat, Maths & Computing, IIT (BHU)