VirtusLab / avocADO

Safe compile-time parallelization of for-comprehensions for Scala 3
https://virtuslab.github.io/avocADO/docs/index.html
Apache License 2.0
88 stars 5 forks source link

Provide a more aggressive version of parallelization #9

Open KacperFKorban opened 2 years ago

KacperFKorban commented 2 years ago

Currently avocADO parallelizes the following comprehension:

for {
  a <- doStuff1
  b <- doStuff2(a)
  c <- doStuff3
} yield combine(a, b, c)

to sth conceptually like:

for {
  a <- doStuff1
  (b, c) <- doStuff2(a).zip(doStuff3)
} yield combine(a, b, c)

The reasoning behind it is that if one wants to parallelize comprehensions that have the effect monad abstracted away, the concrete monad at the end might use a sequential state. In that case, there can't be any parallelization done, because that would affect the end result of the program. In such cases, it should still be possible to use ado, but just provide a different AvocADO instance (with a sequential implementation of zip).

Though for use cases that are more concrete, like programs based on god monads (ZIO etc.), a more aggressive parallelization should be available. One that can also reshuffle (change the order of) the expressions.

Concretely, it should be possible to convert our example (with a more aggressive strategy) to sth conceptually like:

for {
  (a, c) <- doStuff1.zip(doStuff3)
  b <- doStuff2(a)
} yield combine(a, b, c)
KacperFKorban commented 2 years ago

a problematic comprehension might be:

for {
  a <- doStuff
  a <- doStuff1(a)
  c <- doStuff2
  a <- doStuff
} yield combine(a, c)

The most obvious desugaring of this comprehension will be wrong since the as will be shadowing each other (possibly in incorrect order). We use symbols though, so maybe we just need to be smart about the order of bindings picked.