{"action":"created","issue":{"url":"https://api.github.com/repos/functional-streams-for-scala/fs2/issues/768","repository_url":"https://api.github.com/repos/functional-streams-for-scala/fs2","labels_url":"https://api.github.com/repos/functional-streams-for-scala/fs2/issues/768/labels{/name}","comments_url":"https://api.github.com/repos/functional-streams-for-scala/fs2/issues/768/comments","events_url":"https://api.github.com/repos/functional-streams-for-scala/fs2/issues/768/events","html_url":"https://github.com/functional-streams-for-scala/fs2/issues/768","id":190386382,"number":768,"title":"Performance Megathread","user":{"login":"djspiewak","id":752,"avatar_url":"https://avatars.githubusercontent.com/u/752?v=3","gravatar_id":"","url":"https://api.github.com/users/djspiewak","html_url":"https://github.com/djspiewak","followers_url":"https://api.github.com/users/djspiewak/followers","following_url":"https://api.github.com/users/djspiewak/following{/other_user}","gists_url":"https://api.github.com/users/djspiewak/gists{/gist_id}","starred_url":"https://api.github.com/users/djspiewak/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/djspiewak/subscriptions","organizations_url":"https://api.github.com/users/djspiewak/orgs","repos_url":"https://api.github.com/users/djspiewak/repos","events_url":"https://api.github.com/users/djspiewak/events{/privacy}","received_events_url":"https://api.github.com/users/djspiewak/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":14,"created_at":"2016-11-18T18:15:44Z","updated_at":"2016-11-23T05:56:15Z","closed_at":null,"body":"So @rossabaker has been doing [a lot of benchmarking](https://github.com/rossabaker/benchmarks) lately, with some very minor assistance from myself, and we've been working to analyze the results.  We're still lacking a good concurrency benchmark (though I have an idea that I think is reasonable), but we have semi-realistic benchmarks for most of the rest.\r\n\r\nYou can run the benchmarks yourself by cloning the project and running `sbt jmh:run`.  Suffice it to say: fs2 is slow (sort of).\r\n\r\nStream benchmarking is complex, so an assertion like that really isn't, in and of itself, justifiable.  But we can break things down more precisely:\r\n\r\n- fs2's per-chunk overhead (measured by the `Sum` benchmarks) is extraordinarily high.  It appears to be about 10x the per-chunk overhead of scalaz-stream\r\n- fs2's chunking is excellent, but it's entirely possible that the chunking is less applicable than broadly thought, given fs2's performance on some of the IO-dependent benchmarks (where scalaz-stream generally beats it).  The Fahrenheit example from the `README` is a good exemplar of this issue.\r\n  + Putting more emphasis on combinators that encourage chunk-level transformations rather than element-level (e.g. `mapChunks` vs `map`) might help this from an API design standpoint.  This is a long and subjective discussion though.\r\n- Monix utterly destroys both fs2 and scalaz-stream on anything that isn't super hilariously heavily chunked, at which point fs2 can edge out an advantage.  And by \"utterly destroys\" I mean \"1500x faster\".  Literally.\r\n  + First off, this isn't comparing apples-to-apples, since Monix's resource management is far less than robust, and its backpressure support is secondary, whereas fs2 puts both of those features front-and-center (likely to the detriment of straight-line performance).\r\n  + Second, Monix is a push model.  I don't have proof of this yet, but I'm relatively certain that primary-push models are always going to out-perform primary-pull models if only due to eagerness and front-loading cache lines.  Please note that this doesn't mean I'm advocating for primary-push – I'm not – I'm just pointing out that it might give an inherent performance advantage.\r\n- Coming up with realistic benchmarks is hard.\r\n\r\nFocusing in on the per-chunk overhead, I've been spending a fair bit of time with `StreamCore` recently, as well as staring at profiler reports.  A couple things jumped out at me:\r\n\r\n- There are a bajillion intermediate function calls, most of them megamorphic, which serve as indirection in the interpretation of a single chunk.  This is bad.  This defeats everything the JVM wants to do with optimization.  It's actually possible that this alone is the source of the majority of the problems.\r\n- Under some workloads, `AbstractFunction1.<init>` is a major hot spot in terms of method time.  That's insane, because the time spent in `<init>` is dwarfed by the amortized time spent by the GC cleaning up all those instances.  I think it's fairly safe to say at this point that fs2 is allocating far too many function values on a per-chunk basis.\r\n- Heap pressure seems fairly steady over time, but early on in a run it can be quite extreme.  I *believe* (without evidence other than a general graph!) that this is HotSpot's escape analysis kicking in.  Given the number of short-lived objects that fs2 creates and discards while interpreting a single chunk, it shouldn't be unexpected that escape analysis would have a significant impact.  These things still aren't free though.\r\n- `Free#step` is almost always the most-invoked function.\r\n  + As a quick-fix type thing, it's relatively trivial to restructure this function to perform incrementally better (at least on the JVM) by removing the pattern match and using subtype polymorphic dispatch.  There are only two cases, one of which is default, so we should get good mileage out of the bimorphic PIC.  Given the traffic this function gets, I imagine this would actually be a measurable improvement.\r\n  + As a less-quick fix, we might want to consider either a) attempting to ensure the stream interpreter biases toward strictly right-associative binds, or b) experimenting with revising `Free#flatMap` to reassociate binds on construction (thus amortizing the cost).  The second one is unlikely to be a huge boost, but it's worth measuring.\r\n- `StreamCore.step` is *the* hot spot, which really shouldn't be unexpected.  Specifically, the `Stack` fold inside of `step`.  Anything we can do to make this faster, less indirect, or more compact would probably produce measurable results.\r\n\r\nData is still coming in.  Ideas still flowing.  I'm going to do some more in-depth profiling over the weekend to see if I can suss out a clearer picture from all the indirection.  But I figured that, at this point, we have enough that it's worth sharing so other people can chime in.  The biggest tl;dr really is that fs2's per-chunk overhead is so incredibly high that it entirely washes out the benefits of chunking on many workloads (jury's out on \"many\" vs \"most\").  This per-chunk overhead, relative to scalaz-stream, almost certainly comes from the highly indirect and multi-tier algebraic encoding.\r\n\r\nBoth for reasons of making the codebase less insane and impenetrable, and to improve performance, I think we should seriously explore more direct encodings.  Remember that two major things have changed in scalac since @pchiusano did his initial work on this: GADT support improved considerably in 2.11.8 (and incrementally again in 2.12), and SI-2712 was addressed.  Those two changes alone likely open up several avenues which were impossible in the early days.  Additionally, there are some inner-class skolem techniques which were not explored even at the time, which may be applicable here.  In any case, I feel I'm on pretty firm ground saying that the current encoding is causing problems.\r\n\r\n---\r\n\r\nFor those who just want to look at some profiles, you can dig through traces using Java MissionControl (`jmc` in JDK 8.0).  Here's [a tarball from a quick run](https://www.dropbox.com/s/ji0mfab3zmga1ty/fs2-profiles.tar.bz2?raw=1) on my machine."},"comment":{"url":"https://api.github.com/repos/functional-streams-for-scala/fs2/issues/comments/262439542","html_url":"https://github.com/functional-streams-for-scala/fs2/issues/768#issuecomment-262439542","issue_url":"https://api.github.com/repos/functional-streams-for-scala/fs2/issues/768","id":262439542,"user":{"login":"pchlupacek","id":678560,"avatar_url":"https://avatars.githubusercontent.com/u/678560?v=3","gravatar_id":"","url":"https://api.github.com/users/pchlupacek","html_url":"https://github.com/pchlupacek","followers_url":"https://api.github.com/users/pchlupacek/followers","following_url":"https://api.github.com/users/pchlupacek/following{/other_user}","gists_url":"https://api.github.com/users/pchlupacek/gists{/gist_id}","starred_url":"https://api.github.com/users/pchlupacek/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pchlupacek/subscriptions","organizations_url":"https://api.github.com/users/pchlupacek/orgs","repos_url":"https://api.github.com/users/pchlupacek/repos","events_url":"https://api.github.com/users/pchlupacek/events{/privacy}","received_events_url":"https://api.github.com/users/pchlupacek/received_events","type":"User","site_admin":false},"created_at":"2016-11-23T05:56:15Z","updated_at":"2016-11-23T05:56:15Z","body":"@mpilquist not completely sure if this is right step, but any ideas if adding more pipes is degrading performance in any predictable pattern? I would love to see overhead of each nested Pulls. That perhaps can give us the cost of each Pull vs cost of StreamCore.  \r\n\r\nI am just thinking of following \r\n\r\nStream.iterate\r\n\r\nStream.iterate.take(1m)\r\nStream.iterate.take(1m).take(1m)\r\nStream.iterate.take(1m).take(1m).take(1m)\r\n\r\nPerhaps running these can give us glue where we lost the most of resources. \r\n\r\n\r\n"}}
{"actor":{"display_login":"pchlupacek"}}