Quora uses cookies to improve your experience. Read more

When did you realize the power of lazy evaluation in terms of performance?

ad by ClickCease

Competitor clicking on your Google Ads campaign?
1 of 5 PPC clicks is useless. Protect your ads automatically from competitor and bot click fraud.
Free Trial at clickcease.com
2 Answers
Edward Kmett
Edward Kmett, Haskell Programmer
Answered 260w ago · Author has 70 answers and 543.6k answer views
For me if I'm forced to choose precisely one moment, it was reading Chris Okasaki's Purely Functional Data Structures. He makes a very compelling case for how laziness can be used to get surprisingly good asymptotics. He successfully achieves asymptotics that are consistently better than I expected going into the book.

If I'm allowed to expand upon that answer, then it was really a series of revelations, not any one moment, more a case of mounting evidence.

When I read Cons Should Not Cons Its Arguments by Friedman and Wise, I was able to get a sense of how useful laziness could be, but not of any asymptotic benefit.

The first time I realized there were asymptotic benefits to non-strictness over strictness was reading Pure vs. Impure Lisp by Pippenger. He goes through and shows how purity can cost you a [math]log[/math] factor, but his proof relies on the absence of mutation. That said, call-by-need has a limited form of mutation in the form of thunk evaluation and replacement, so his proof doesn't hold. In fact laziness provides immediate counter-examples for some of his cases. Can it handle all of them? We don't know. Algorithms like Tarjan's Union-Find seem hard to phrase in the non-strict vocabulary, so I suspect not, but I've been able to make headway on similar seeming insurmountable algorithms, so who knows.

Reading Trouble Shared is Trouble Halved by Bird and Hinze convinced me we could use laziness to deal with memoization without extra side-effects as well.

By that point I had most of what I needed to make the case. The real nail in the coffin for me was realizing that things like take 10 . sort get better asymptotics than its constituent parts due to laziness, which means I can get both code reuse and improved asymptotics out of laziness.

Since then I've been working on deamortization and dynamization schemes that let me execute more code without suffering an asymptotic impact for making code lazy.

Finally, while I was already sold by the point I watched it, Don Stewart made a compelling case for laziness in the kinds of large financial models and systems he builds over at Standard Chartered on The Haskell Cast, if you don't want to just take my word for it.

9k Views · View 82 Upvoters · Answer requested by Tikhon Jelvis
Bob Ippolito
Bob Ippolito, CTO at Fig, Mission Bit board member, founder of Mochi Media. Python, JavaScript, Erlang and Haskell hacker.
I don't have a lot to add to Edward Kmett's excellent answer, but I first became interested in lazy evaluation with Python 2.2's generators. I didn't truly appreciate it until I learned Haskell much later.

I thought it was great that I could write transforms that worked with streams without having to materialize the entire data structure for each intermediate step. I used them (and later, the itertools module) probably far more than I should've. The experience eventually left a bad taste in my mouth when I realized how inefficient they were for general purpose use in Python. One specific example of that is we had a large Trac instance at Mochi Media (circa 2009), which composed a large stack of stream filters (generators) with the Genshi templating language. To generate ~600k of HTML ~6.7M function calls were involved! Since function calls are relatively slow in Python, this would take a few seconds. This could be done a bit better in Python 3.3 with PEP 380 (yield from), but that was too little too late for me.

I started warming up to lazy evaluation again after reading Chris Okasaki's Purely Functional Data Structures in order to better understand how to build data structures in Erlang. Lazy evaluation in this setting allowed optimizations that would require mutability otherwise. I was sold when I learned Haskell a few years later, especially considering how GHC is able to perform compile time optimizations such as fusion and deforestation thus eliminating the overhead that is present in languages like Python. In addition to that, Haskell doesn't need awkward yield syntax, you get laziness by default pretty much everywhere… and when you need strict evaluation, you can have that too.
1.6k Views · View 3 Upvoters

Related Questions

Related Questions