tdauth / scala-futures-promises Goto Github PK

See https://groups.google.com/forum/#!topic/finaglers/ovDL2UFKoDw

get is blocking.
Use transformWith/flatMap.
Other than that the whole implementation does not make any sense.

• Inherit the field type rather than keeping a field.
• Use @tailrec for the CAS-based implementation.
• Optimize empty promises with something like NOOP.
• TODO Check out all Twitter Util optimizations.

In Haskell it is

-- Primitive set of (promise/future) features, specified in terms of a constructor class.
-- Inspired by Scala FP (= Scala's futures and promises).
class Base t where
  newB :: IO (t a)
  getB :: t a -> IO (Maybe a)
  tryCompleteB :: t a -> IO (Maybe a) -> IO Bool
  onCompleteB :: t a -> (Maybe a -> IO ()) -> IO ()

Rename our Prim trait to Base and all the methods.

Add a manual implementation based on STM (see Sulzmann's work).
We could use https://nbronson.github.io/scala-stm/index.html

See https://github.com/anschwar/FutureSTM for a reference implementation.
Basically, only the locks have to be replaced by transactions.

It can use the creation of a promise and a future together with Executor.submit.
However, the executor information should be kept in the future, so pass it as construction parameter.

The primitive trait defines basic methods for the implementations.

See https://github.com/scalameter/scalameter-examples/tree/master/basic-with-separate-config

Add benchmark runs to TravisCI configuration.

Show how our API can implement the remaining methods.

They should not directly derived from the Scala FP implementation, so they can be used with any implementation.

Just use the trait Future[T] as parameter and provide a single object.

Is the BrokenPromise exception even possible in Scala. We cannot delete the promise explicitly?

There is a data race bug in the firstN and firstNSucc implementations. Make sure that the vector element is added BEFORE the promise is completed. Therefore, do not check if c == n but if the vector's size == n!

Maybe we could use a threadsafe vector like in the C++ implementation and two atomic counters.
Remove the unnecessary done variable.
Look at: https://www.scala-lang.org/api/2.12.1/scala/collection/parallel/immutable/ParVector.html
And for performance at: https://docs.scala-lang.org/overviews/collections/performance-characteristics.html

Add basic unit tests as well.

This is the code from the current Scala FP implementation:

final 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)
  }

This looks like searchNext is called once in the beginning for the first future. It registers a callback which waits for the completion and then continues to register a callback for the next future, if the current one does not match the predicate. If this is the case, it does not prefer futures which complete first but futures which are first in the collection.
Therefore, it cannot be used to implement firstSucc.

Publish them online (in this repostiroy) and link them in the README.md file.

We want to compare the performance of our derived combinators with the performance of the existing combinators from Scala FP.

First, we need real world use cases which might be hard to find.

• https://stackoverflow.com/questions/13381134/what-are-the-use-cases-of-scala-concurrent-promise
• https://www.playframework.com/documentation/2.0/ScalaAsync

Maybe usage of the playframework? Akka based HTTP server?
If we use Akka, we cannot easily compare the performance.

If there is no real world examples, at least compare the performance by executing binary trees similiar to https://github.com/tdauth/cpp-futures-promises/blob/master/src/performance/performance_combinators.cpp

• onSuccess
• onFailure
• followedBy
• followedByWith

just add them to AbstractFutureTest.

Promise linking can fix this problem.

The old test AbstractRecursiveThenWithMemoryTest did not pass the correct index in thenWith.
Therefore, it run in an endless loop.
Fix it.

Java's CompletableFuture does not seem to have something like flatMap.
How can we reproduce this test with Java's implementation?

Util.firstN and Util.firstNSucc should use a concurrent vector instead of a manual lock.
At least use synchronized instead of a manual lock: https://stackoverflow.com/questions/34877487/how-to-use-synchronized-in-scala

Some unit tests fail sometimes (not always), for example the successful test of firstNWithFirst.
Fix them all.

Use the current benchmarks and add more if necessary.
We can submit one callback at a time or all together (current implementation).
Besides, we can use promise linking to optimize tryCompleteWith and move all callbacks to the root promise.

https://github.com/twitter/util

Compare:

• Scala FP
• Twitter Util
• PrimMVar
• PrimCAS
• PrimSTM

Find all benchmarks in Twitter Util and Scala FP and link them here as inspiration/comparison.

Try to detect data races automatically with some tool: https://stackoverflow.com/questions/52467008/what-tools-can-i-use-to-detect-data-races-in-scala-programs

We have mentioned in the C++ paper: "Method firstSucc imposes the condition that the first successful future shall be chosen. Instead of tryComplete we employ trySuccess. If both fail, we rely on the
following assumption. The promise will be deleted and then the resulting future fails.
This is a standard assumption found in C++17 and Folly."

This cannot be expected in Scala since it has a garbage collection. Therefore, make sure that firstSucc fails with the final exception if both futures fail to prevent starvation.

https://github.com/scala/scala-async

https://docs.scala-lang.org/sips/async.html

Add it as dependency.
Compare it to the for-comprehensions and to our API.

The package is called tdauth but does not appear as folder in the filesystem.
Add the folder.

We use the two traits Prim[T] and FP[T] which combined will result in a future and promise implementation.
We need unit tests to cover all functionality.
We need benchmarks:

• binary tree for all combinators which take two or more futures
• followedBy.followedBy.followedBy ....
• onComplete multiple times
• tryComplete multiple times on list of uncompleted promises

We don't need an exception throwing get.
Just use Either or Scala's Try.