dart-lang / dart-lang/language

Light-weight concurrency

Open
#1,950 1 comment 11 reactions 0 assignees View on GitHub
feature
Dominant language
TeX
Stars
2.9k
Forks
239
Avg merge
2d 18h
Merged PRs (30d)
14

Description

One of the things that's tricky to do today in Dart is efficiently shard self-contained work. For example, generating a list has to be done in parallel, there's no way to compute the various values of the list in parallel, even if the values don't depend on each other.

Imagine if, instead, one could do something like:

```dart
const int key = 0x1234;
List results = List.generateParallel(0x1000, (int value) => value ^ key);
```

We would need a language mechanism which guarantees that a closure is "self-contained". (This has a similar "infectious" nature as `const` contexts, in that a "self-contained" block can call other self-contained code safely, but not code that isn't self-contained.)

There are different ways we could define "self-contained". One way is "accesses no mutable state". Thus code would only be "self-contained" if it could execute in isolation based only on constants (such as `key` in the example above) and parameters (such as `value` in the example above), and return a newly created value.

This would allow for its use in APIs like `generateParallel` above, but I believe we could go further.

Consider instead the case where we define "self-contained" as "does not mutate non-self-contained values", allowing one to _read_ from values in shared objects, though never mutating them. Add some feature to launch self-contained code in parallel and combine the results somehow, and define these features as synchronous. We could so something like:

```dart
class Node {
Node(this.value, [ this.a, this.b ]);

int value;
final Node? a, b;

Node? search(int query) {
if (value == query)
return this;
if (a == null)
return b?.search(query);
if (b == null)
return a!.search(query);
return a!.search(query) ?? b!.search(query); // magic here
}
}

void main() {
Node root = Node(1, Node(2, Node(3, Node(4), Node(5)), Node(6, Node(7, Node(8), Node(9)), Node(10))), Node(11));
print(root.search(5)?.value);
}
```

...except the line marked "magic here" could execute both arms in parallel, thus walking the tree more efficiently than is possible today.

There's lots of details to iron out here. We would probably want explicit syntax to opt a method into this, so that the analyzer could verify that self-contained code is really self-contained. We'd need a way to guarantee that `a` and `b` and `search` in the example above are not virtual, and `a` and `b` would need to be actual instances of `Node`, not merely objects that implement that interface, since the code only works if we can guarantee that `search` really is self-contained so nothing can get mutated during the call `main` makes to `root.search`. We'd need some way for the system to interrupt work once a reply is available (e.g. in the example above, if the search in the `a` branch returns a value before the `b` branch, and that value is non-null, then the `b` side can be terminated and the results discarded).

We'd also need to check if the overhead of spinning up a bunch of Isolates (or using some from a pool), sending them the data to process, and then collating the results, is sufficiently high that this proposal even makes sense.

Contributor guide

Open the contributing guide

Research direction

The issue contains no named files, tests, or entry points; start by reviewing the proposal's examples and its open design questions around self-contained code, parallel execution, isolation, and cancellation. Done would require a settled, specified language and runtime design rather than a small code change.

Written by the indexing model from the issue text.

Assessment

Tech stack
dart
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.