Difference in behaviour of Future.find

[Philippus]

Hi, it looks like the behaviour of Future.find changed in scala 2.13 when one of the futures in the sequence passed to find never completes.
I'm not completely sure if the behaviour is intentional, but it was surprising to me.

import scala.concurrent.{ Await, Future }
import scala.concurrent.duration._
implicit val ec: scala.concurrent.ExecutionContext = scala.concurrent.ExecutionContext.global

val futures = Seq(Future.never, Future.successful(true))
val a = Future.find(futures)({ _.isInstanceOf[Boolean] })
Await.result(a, 5.seconds).contains(true)

In scala 2.12.8 the result is res0: Boolean = true
In scala 2.13.1 the result is java.util.concurrent.TimeoutException: Future timed out after [5 seconds]
Reversing the sequence will result in res0: Boolean = true in both scala versions.

[Jasper-M]

I don't even understand how the 2.12 version does return a result.

def find[T](futures: scala.collection.immutable.Iterable[Future[T]])(p: T => Boolean)(implicit executor: ExecutionContext): Future[Option[T]] = {
  def searchNext(i: Iterator[Future[T]]): Future[Option[T]] =
    if (!i.hasNext) successful[Option[T]](None)
    else {
      i.next().transformWith {
        case Success(r) if p(r) => successful(Some(r))
        case other => searchNext(i)
      }
    }
  searchNext(futures.iterator)
}

And Future.never.transformWith(f) always return Future.never without evaluating f...

[Philippus]

2.12 has a different implementation.

[Jasper-M]

Aha, I don't know how I managed to not see that one.

2.12 has 2 implementations and we were calling the deprecated one.
If you change this line

val futures = collection.immutable.Seq(Future.never, Future.successful(true))

then you see the same behavior as in 2.13.

[som-snytt]

That was an interesting opportunity to review the well-reviewed SIP-14 improvements PR, and also to re-read the blog.

I suspect the change is a result of "prefer transform/transformWith over onComplete" (not a direct quote).

There's also a sentiment of "don't bloat the API" (direct quote). What's expected here is findFirstCompletedOf, which would be a reasonable addition on the basis of not "easy to implement yourself" using existing combinators.

I seem to remember a stackoverflow question asking for it, too.

I wonder if this means no one has used the new find in five years.

[SethTisue]

of interest to @viktorklang...?

[viktorklang]

@SethTisue @som-snytt I think a Task-like construct would be the correct place to add a feature like this (since you want to cancel tasks, rather than Futures).

[SethTisue]

The Scaladoc for Future.find says that it returns the "first" Future that qualifies. That's a bit ambiguous, since "first" could mean "first in the Iterable" or "first in time". But I think the former interpretation is reasonable and what I would expect, based on what the find in the collections API does. So I think the 2.13 behavior is fine.

[Jasper-M]

The Scaladoc for Future.find says that it returns the "first" Future that qualifies. That's a bit ambiguous, since "first" could mean "first in the Iterable" or "first in time". But I think the former interpretation is reasonable and what I would expect, based on what the find in the collections API does. So I think the 2.13 behavior is fine.

Coming back to this, IMHO the former interpretation would be more reasonable if the parameter to find is a Seq, since their iteration order is defined. Whereas Iterable's iteration order is undefined. So "first in the Iterable" actually means "first I happen to come across in this specific iteration of the Iterable". That's the best you can do for any random Iterable[A], but here you have an operation that's specifically designed for Iterable[Future[A]].

[SethTisue]

this came up again at #12325. the 2.13 semantics are now established, I don't think we're free to change them at this point. (if this had been reported against a 2.13 prerelease, we could have had a different discussion, perhaps.)

[matepek]

Just some thoughts regarding to the interpretation of "first". I assume we all started learning single threaded algorithms before multithreaded ones (where we have to consider the parallel universes too).

At that time the "first in the Iterable" was the same as "first in time" and maybe this equivalence made these algorithms interesting.

In case of multithreading the interpretation makes a difference and my gut tells me (and the task I was facing) that time is more interesting than the ordering.

I'm not saying that the "find" should be rewritten but if there is no "first in time" algorithm then users will improvise.

[SethTisue]

iiuc @viktorklang is arguing that "first in time" isn't worth doing unless you can also cancel the others, but I would need further convincing on that point.

[SethTisue]

note that binary compatibility constraints forbid us from adding a new "first in time" method to the Scala 2 stdlib, but perhaps it could happen over at https://github.com/scala/scala-library-next

[Jasper-M]

"first in time" isn't worth doing unless you can also cancel the others

That's a fine design principle to have, but firstCompletedOf already has "first in time" semantics.

And it's not at all clear from the docs that both methods have a different interpretation of "first".