Scala Programming Language
  1. Scala Programming Language
  2. SI-6932

StackOverflowError in chained Future.flatMap calls

    Details

      Description

      First, a simple reproduction of the bug:

      val promise = Promise[Int]
      List.range(0, 1000).map(i => Future(i)).foldLeft(promise.future)((f1, f2) => f2.flatMap(i => f1))
      promise.success(-1)
      

      This will throw a crazy exception with 1000 causes, the root being a StackOverflowError. Note if running this in the repl, or anywhere, you may instead get NoClassDefFoundErrors. This is because something is trying to handle the initial error deep in the stack (probably shouldn't be), which triggers a class to be loaded, which throws another StackOverflowError, which results in the NoClassDefFoundError.

      Here's the implementation of flatMap, which clearly shows the issue:

      def flatMap[S](f: T => Future[S])(implicit executor: ExecutionContext): Future[S] = {
        val p = Promise[S]()
      
        onComplete {
          case f: Failure[_] => p complete f.asInstanceOf[Failure[S]]
          case Success(v) =>
            try {
              f(v).onComplete({
                case f: Failure[_] => p complete f.asInstanceOf[Failure[S]]
                case Success(v) => p success v
              })(internalExecutor)
            } catch {
              case NonFatal(t) => p failure t
            }
        }(executor)
      
        p.future
      }
      

      The internalExecutor executes the onComplete callback in the same thread. So, when promises returned by flatMap are used as the promise to be returned by another flatMap callback function, and this is done enough times, you get a StackOverflowError.

      This is not an uncommon situation in iteratees, which use many many futures and often chain them together in very long chains (for very long streams), and both the Play core developers and Play users have found this to be an issue all over the place. Currently we fix it with a call like this:

      .flatMap(a => Future.successful(a))
      

      But I don't think this is the right solution to the problem, and it seems to come up all over the place.

      Suggested solution is to use an execution context that doesn't redeem the flatMap promise is the same thread.

        Issue Links

          Activity

          Show
          Jason Zaugg added a comment - https://github.com/scala/scala/pull/1941
          Hide
          Adriaan Moors added a comment - - edited
          Show
          Adriaan Moors added a comment - - edited for 2.9.3-RC2: https://github.com/scala/scala/pull/1962
          Hide
          Paul Chiusano added a comment -

          I've come across another way of fixing this problem, which is to build a 'trampolined Future' type that associates its flatMap calls to the right, similar the trampoline data type that Runar has written up. The interplay between the trampolining and the asynchronous computation is pretty subtle and tricky to get right, but it's only like 50 LOC. Here's a working gist illustrating the idea. There's some examples in there too, including the example that was problematic above. One advantage to it is that new tasks are only submitted to the thread pool when explicitly forked (notice that flatMap does not require an implicit ExecutorService or anything), rather than on every flatMap call, which I suspect is going to be much faster for many use cases.

          Show
          Paul Chiusano added a comment - I've come across another way of fixing this problem, which is to build a 'trampolined Future' type that associates its flatMap calls to the right, similar the trampoline data type that Runar has written up. The interplay between the trampolining and the asynchronous computation is pretty subtle and tricky to get right, but it's only like 50 LOC. Here's a working gist illustrating the idea . There's some examples in there too, including the example that was problematic above. One advantage to it is that new tasks are only submitted to the thread pool when explicitly forked (notice that flatMap does not require an implicit ExecutorService or anything), rather than on every flatMap call, which I suspect is going to be much faster for many use cases.
          Hide
          Viktor Klang added a comment -

          "One advantage to it is that new tasks are only submitted to the thread pool when explicitly forked "

          The reason we didn't go that route is that we consider that to be a disadvantage, i.e. the programmer has to make choices about execution rather than flow.

          Show
          Viktor Klang added a comment - "One advantage to it is that new tasks are only submitted to the thread pool when explicitly forked " The reason we didn't go that route is that we consider that to be a disadvantage, i.e. the programmer has to make choices about execution rather than flow.
          Hide
          Paul Chiusano added a comment -

          I thought about this some more, and I believe the degree of parallelism is identical with the approach I gave (updated version below). I am just reusing the spawned thread for the 'rest' of the computation and avoiding a needless task submit cycle. That is, if I have a f.flatMap(g), the Future produced by g must be run in sequence after f. Therefore, there is no advantage to always spawning a separate logical thread to run the Future produced by g - we would be better off just reusing the thread that f was just about to relinquish, unless g explicitly indicates it wishes to refork.

          Here's updated code, if you are interested:

          https://github.com/pchiusano/fpinscala/blob/master/answers/src/main/scala/fpinscala/iomonad/Future.scala

          It is a different library than what you have in the sense that Future does not necessarily represent a running computation. Until you call start, run, or runAsync, nothing is happening. This greatly simplifies the implementation - there are no race conditions to worry about, where a listener registers itself at the same time the promise is completing on its own.

          I'll probably port this to scalaz pretty soon so we can see how it works out there.

          Show
          Paul Chiusano added a comment - I thought about this some more, and I believe the degree of parallelism is identical with the approach I gave (updated version below). I am just reusing the spawned thread for the 'rest' of the computation and avoiding a needless task submit cycle. That is, if I have a f.flatMap(g), the Future produced by g must be run in sequence after f. Therefore, there is no advantage to always spawning a separate logical thread to run the Future produced by g - we would be better off just reusing the thread that f was just about to relinquish, unless g explicitly indicates it wishes to refork. Here's updated code, if you are interested: https://github.com/pchiusano/fpinscala/blob/master/answers/src/main/scala/fpinscala/iomonad/Future.scala It is a different library than what you have in the sense that Future does not necessarily represent a running computation. Until you call start, run, or runAsync, nothing is happening. This greatly simplifies the implementation - there are no race conditions to worry about, where a listener registers itself at the same time the promise is completing on its own. I'll probably port this to scalaz pretty soon so we can see how it works out there.

            People

            • Assignee:
              Philipp Haller
              Reporter:
              James Roper
            • Votes:
              1 Vote for this issue
              Watchers:
              9 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development