5 ms·
I find it basically impossible to reason about performance in the presence of laziness because it means performance is no longer compositional. In a regular lan
by lmm 6y ago
I find it basically impossible to reason about performance in the presence of laziness because it means performance is no longer compositional. In a regular language if I write:
def h(a) = {
val b = f(a)
g(b)
}
and this is taking too long, I can examine f and g separately; I know that h(a) will take as long to run as f(a) plus g(b) (plus a little bit). In a lazy language I have no clue.
- theCodeStig 6y agoPardon me if this is dense, but I don't see how laziness prevents you from examining f and g separately.
- imtringued 6y agoIncredibly simplified example: f generates a list of 100 expensive calculations each taking 10 seconds. g filters out every second element. Printing out the result of g(f(a)) is 2 times faster than printing just f(a). In a non lazy language f(a) and g(f(a)) would take roughly the same amount of time. In this example the expensive calculations take much longer than printing the output to the terminal. (no nitpicking please)
- jose_zap 6y agoAnd how is that more difficult to reason about? The asymptotical performance is exactly the same for strict and non-strict languages. The performance can only be at most f + g. It may take less time in a lazy language, how is that difficult to reason about, and why would you care if it runs faster?
- lmm 6y agoThe speedup is invisible in the code, and so when it stops working you can't tell whether it was meant to be working. The cornerstone of pure functional programming is that you can refactor fearlessly because of referential transparency, but if your program has invisible magic performance boosts in it then you lose that ability, because you never know when one of your refactorings will eliminate one of those performance boosts that turned out to be load-bearing. Imagine you've got a performance problem because f + g used to take x time but now takes 4x. You start trying to break down the problem, and you see that f takes 2x time and g takes 2x time. You check out the old tag where f + g takes x time and you discover that f takes 2x time and g takes 2x time. Where do you even go from there?
- jose_zap 6y agoWell, you would tackle the problem in the same way you do in a strict program. If both functions take the same time in isolation, it would make sense to review both functions performance to improve the whole. How is that difficult to reason about? How did laziness made it impossible? If anything, it can make things run faster, but if something is already slow, you just start by looking at the slowest function. You don’t even have to guess, the Haskell profiler will tell you what function that is, even with laziness involved!
- lmm 6y ago> If both functions take the same time in isolation, it would make sense to review both functions performance to improve the whole. How is that difficult to reason about? How did laziness made it impossible? Because the slowdown didn't happen in either function. f still takes the same time it used to. g still takes the same time it used to. But somehow the composition has gotten significantly slower. Both functions may be slow when run in isolation, but it's impossible to tell whether one or both is "supposed to" be slow. Profiling and looking at the slowest function can easily lead you on a wild goose chase here.
- jose_zap 6y agoIn your g(f(x)) composition example you said that g would be filtering out eveery other record, that could only make thiings faster, not slower. Could you formulate an example where the composition would be asymptotically slower only for lazy languages? As I said before, laziness is actually an optimization strategy. If anything, it can only make the composition faster than it would be in a strict language (although rarely so)
- lmm 6y ago> Could you formulate an example where the composition would be asymptotically slower only for lazy languages? No; we both know no such thing exists. The same code will always be asymptotically faster in a lazy language. The problem is that lazy languages (or at least, the one lazy language in widespread use) encourage a style of code that would be asymptotically slower if written in a strict language. In a strict language, a function is slow or fast, and a slow function is always a problem - which means performance is easy to reason about. In a lazy language, a slow function is not necessarily a problem, depending on how it's used, and so you can't understand performance without understanding the whole program. An unreliable optimisation can be worse than no optimisation at all. Worst practices should be hard. In theory an extremely vigilant development team could always write code that would be fast if executed strictly, and therefore guarantee no performance problems, but this would require an enormous manual effort since the language doesn't help you with it at all.
- willtim 6y agoAll high-level languages with optimising compilers have "non-compositional performance" as you say. The big issue with laziness is reasoning about space usage. A strict language is not immune to this however. If one builds lazy abstractions (e.g. Streams, collection views) in Scala, then one has the same problems.
- lmm 6y ago> If one builds lazy abstractions (e.g. Streams, collection views) in Scala, then one has the same problems. Sure. There's nothing to stop you using lazy values in a strict language if you want to; it's just that you get the option of using strict values as well. Whereas in Haskell you have no way of building strict constructions other than some ad-hoc annotations.
- jose_zap 6y agoThere is the -XStrict language pragma that makes everything strict.
- lmm 6y agoHmm, interesting. Is it actually a viable language for working in? (Lack of an IDE would still be an issue, as would the limitations of the record system, but I'd certainly be more interested in Haskell if strict was a first-class way of working there).
- jose_zap 6y agoYou can check the Ghcide and the (early work in progress but very usable) haskell-language-server projects. They implement the language server protocol and add ide-like functionality for Haskell to any editor that support the protocol like vscode. I totally agree that the records system is annoying.
- jose_zap 6y agoI don’t think that’s right. In a lazy language that function will also take the sum of f + g times. If anything, in a lazy language it may take less time, but never more than the sum of both. How is it that you cannot reason about the performance of each separate function?
- lmm 6y agoImagine f returns an infinite lazy list (common in Haskell). How do you reason about its performance? Fully evaluating it would take infinite time.
- jose_zap 6y agoHmm, wouldn't this be the same as an infinite loop in any programming language? How do you solve an infinite loop in python for instance? How would you solve an iterator in java producing infinite values? If anything, the performance of a lazy language would be better than a strict one in the presence of an infinite sequence, as it gives you the opportunity to stop sooner and not enter in an infinite loop. Example in haskell: main = do let a = [1..] -- infinite list print (a !! 0) -- only prints the first element and exits Example in python: def f(): a = [] b = 0 for True: a.append(b++) return a def g(): print f()[0] # Takes infinite time
- lmm 6y ago> Hmm, wouldn't this be the same as an infinite loop in any programming language? How do you solve an infinite loop in python for instance? In practice an infinite loop in Python is often an immediate error (stack overflow) at the point where it's declared. In cases like you showed it's a little fiddlier, but any execution of that code will immediately show that there's an infinite loop (e.g. any unit test of it will time out) and a stack dump taken while the program is "stuck" will show exactly where the infinite loop is (which is therefore where the error is, because an infinite loop is always an error in these languages). Which is still not an ideal situation, mind; I'm very much in favour of an Idris-style language where function termination is actually checked by the type system and there's a type-level distinction between data and codata. > How would you solve an iterator in java producing infinite values? I'd avoid ever passing around a bare iterator, ideally with a lint rule. The point isn't that it's impossible to have lazy values in other languages. It's that it's practical and idiomatic to avoid them, or at least limit them to cases where you absolutely need them.