How does promise linking work?


#1

Hi there,
I have a really hard time understanding how promise linking works. I have written a question StackOverflow: https://stackoverflow.com/questions/52557676/how-does-promise-linking-work-in-scala-and-why-is-it-necessary

Maybe someone could try to answer the question on StackOverflow.
From the code base of 2.13.xx (which is really hard to understand, at least I have found the big comment in 2.12.xx) I just see that in all the …With calls and flatMap it creates a link and somehow moves the callbacks but I don’t get how it removes the references to memory from the closures since the closures would have to be called to release their references?


#2

In reality what promise linking improves is only reduction of chains lengths, by allowing all promises in a chain to link to single promise, so garbage collector can reclaim them sooner.

The problem with Scala 2.11 was that compiler closed over too many variables (unnecessarily) and that sometimes caused massive memory leaks. Scala 2.12 has different encoding of functions and compiler was improved when it comes to closures.

More details here: https://groups.google.com/forum/#!topic/scala-internals/RtsPUliPNQA


#3

This sounds like it does not have to implemented anymore with Scala 2.12? Why is it implemented in Scala 2.13? https://github.com/scala/scala/blob/2.13.x/src/library/scala/concurrent/impl/Promise.scala

Can you maybe explain with a small example how the closures are kept longer in memory?
From my understanding, the futures on which flatMap is called get a callback closure which then calls completeWith on a promise with the result of the passed function.
The passed callback closure holds a reference to a big array which has to be kept in memory (because of the reference).
The closure is called as soon as the future on which flatMap is called is completed. Now the reference should be let go since we only need the result of the passed function to flatMap which is then passed to completeWith.

f0 flatMap ( referenceToBigArray; myCallWhichReturnsAFuture() )

f0 is completed. The closure is called now. referenceToBigArray is discarded since it is not used after the expression referenceToBigArray. myCallWhichReturnsAFuture is called and a new promise is created:

p completeWith (myCallWhichReturnsAFuture())
p future

So the referenceToBigArray has to be kept in memory until f0 completes. I don’t see how it could be released earlier. Is it kept in memory since the closure is only released when the current future is released?

What is the root future/promise where all callbacks of the chain are moved to?


#4

As I’ve said, the problem is that Scala 2.11 compiler closes over the function T => Future[S] unnecessarily in the inner Future.onComplete. Viktor Klang wrongly attributed the improvements to his promise linking rather that to fixed lambda encoding in Scala 2.12.

To see the problem you need to disassemble (using javap -c) some classes from Scala 2.11 library. Download and unpack https://downloads.lightbend.com/scala/2.11.12/scala-2.11.12.tgz . After looking at scala/concurrent/Future.class and it’s inner classes you’ll see that:

  • closure passed to onComplete at line 251 closes over parameter f: T => Future[S] and local variable val p = new DefaultPromise[S]()
  • closure passed to onComplete at line 256 closes over previous closure to be able to access promise p, but that also means it closes over parameter f because previous closure closes over it

Workaround for that compiler bug is here: https://github.com/tarsa/FuturesFix/blob/ce7030153557370095441ad470c8c003d5751fe1/src/main/scala/futures/fixed/concurrent/Future.scala

There’s a function factory method that avoid unnecessarily closing over unwanted variables (i.e. it closes over only the provided parameter):

  private def feedPromise[S](promise: Promise[S]) =
    promise.complete(_: Try[S])

I’m using it then in flatMap in a way that avoids mentioned unwanted closure:

  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 feedPromise(p) catch { case NonFatal(t) => p failure t }
    }
    p.future
  }

Now let’s return to see in which cases promise linking can help. Consider following loop:

val start = Promise()
var previous = start
while (true) {
  val current = Promise()
  current.completeWith(previous.future)
  previous = current
}

Above code effectively build infinite chain of promises. Without promise linking we’ll end up with infinite chain of callbacks. With promise linking we’ll end up with infinite chain of promise links. But together with promise linking there’s additional heuristics that tries to shorten paths whenever possible. At any iteration of the loop except first, promise previous is a link to some previous promise. When linking additional promise (current) it is possible to follow the promise links up to a promise that is not a link (it’s called a root promise). Then instead of linking to immediate predecessor we can link to root. Heuristics also relinks all promises on the path to root, not only the current promise, to make all paths as short as possible. Unfortunately this heuristics doesn’t reliably compress all paths in all cases so relinking is done all the time, hoping for good enough real world guarantees.

A much less contrived example is for comprehension on Futures (or equivalent flatMap/ map/ filter sequence). If we have N flatMaps in a row (and no promise linking) then we need to keep N + 1 Promises in memory. With promise relinking we can reduce the number of reachable (by GC) Promises to 2 or 3. But in practice the gain is small - usually for comprehensions on Future’s aren’t super long. Every Promise takes maybe a dozen or few dozens of bytes, so even if there are 20 Promises in a chain inside for-comprehension then it translates to maybe a kilobyte of saved memory.

In general, I think that the whole promise relinking looks like over-engineering catered at very special use cases. Promise relinking heuristic does not give 100% guarantee that all paths will be compressed so every weird use case like ACPS needs to be tested against promise relinking heuristic to find out whether it’s sufficient.


#5

Thanks for the detailed reply.

I am just wondering if the linking can only be done if the promises have the exact same result?!
So, we only benefit from it when we have a chain of multiple promises which all have the same result?
If in your example current.completeWith(previous.future) would look like:

current.completeWith(previous.future flatMap { do something else on each iteration and return a future })

Now each promise of each iteration would have to wait for the callback to be called since the previous future is always changed.
Would the linking compression still work here?

If not, then promise linking is what I assumed in my question on StackOverflow and really seems to be a useless feature.
The benchmark example looks rather artifical, too since how often would you call it recursively n times only to complete it with the final Future.Successful(n)?

I am just wondering because I’ve read that it comes from Twitter util and they even have a Promise.become method for this:
https://twitter.github.io/util/docs/com/twitter/util/Promise.html


#6

Yes.

Yes.

Additionally, linked promises must not be a function of one another (i.e. no function application is allowed) - even identity function. That’s because function bodies are not inspected, of course. So you’re left with chains of linked promises that are completed at exactly the same time.

I looked into the library and completeWith doesn’t actually use linking (so my example is bad). transformWith uses it and by extension a lot of other functions, but not completeWith. So it seems that even coming up with a contrived example of deep promise linking is non-trivial :slight_smile:

Common example of promise linking is multi-step for-comprehension on Futures (when backed by stdlib’s Promise). But for-comprehensions are never long enough (IMHO) to make any measurable difference (with regard to memory usage) when using promise linking. I’m not sure about performance, though. You can try to benchmark it, sometimes having promise linking enabled in transformWith aond sometimes having it disabled.


#7

Thanks for your answer. Yes, I know from the source code of impl/Promise.scala in 2.13.xx that flatMap, transformWith and recoverWith use this optimization (all combinators which wait on another future returned by the passed callback.

Wow, I would never have thought that it does only work for exact same promises.
There must be really big for comprehensions somewhere when even Twitter uses this “feature”.