flash: Parallel evaluation
- Dominant language
- Rust
- Stars
- 45
- Forks
- 3
- PR merge metrics
- No merged PRs in 30d
Description
Let's add parallelism to the flash evaluator. There are two forms of parallelism I am thinking of:
1. Concurrent execution *for pipes specifically*. There is a problem with the current implementation of pipes for inter-instruction communication: because everything executes serially, pipes can easily fill up. In the program `foo | bar`, if `foo` produces a lot of output, it will deadlock because `bar` is not yet running to consume that data. So we have to do something to make steps in these pipelines run concurrently.
2. General data-flow parallelism. Imagine the program `foo > foo.txt ; bar > bar.txt ; qux foo.txt bar.txt`. The `foo` and `bar` commands should be able to run in parallel, and `qux` should run when they're both done. At least at some elevated optimization level, if not by default.
The first is required to make pipes work in general; the second would be nice to have just as another fun optimization that real shells cannot do.
I think we should implement both (in the short and long term, respectively.) Here are some proposed approaches:
1. Stick with serial execution, but execute _every instruction that produces a pipe as output_ asynchronously. Instructions that read from pipes as input work normally. This is probably pretty easy to do for `ExecInstr` but hard to do for built-in FlatGFA ops.
2. Switch to a data-flow-style, parallel-by-default evaluator. You mark all resources as "ready" or "not ready," and mark every instruction as "waiting," "running," or "done." Repeat until all instructions are done: look for instructions whose inputs are ready and launch them. Asynchronously, whenever any instruction finishes, mark its outputs as done. Pipes are marked as done as soon as the instruction launches.
The latter seems complicated but exciting. It should probably be an alternative mode that exists alongside the serial evaluator.
Contributor guide
No contributing guide indexed for this repository
Research direction
The issue names no files or tests. Start at the flash evaluator's serial execution path, especially ExecInstr and the built-in FlatGFA operations, and compare pipe handling with the proposed instruction and resource states. Done means pipe-heavy pipelines no longer deadlock, while independent commands can run concurrently in an alternative parallel evaluator mode.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- backend
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100