google-research / google-research/dex-lang
Modify arrays in-place whenever possible
- Dominant language
- Haskell
- Stars
- 1.7k
- Forks
- 116
- PR merge metrics
- No merged PRs in 30d
Description
I've recently read the [Perceus paper](https://www.microsoft.com/en-us/research/uploads/prod/2020/11/perceus-tr-v1.pdf) and it has inspired me to propose this optimization for Dex.
Basically, we should write a reasonably good life-time analysis so that we can reuse the storage for an array we're processing to hold the output of a `for` loop. That is a program such as the following:
```
a = for i. expensiveFunction i # expensive, so don't inline
b = for i. expensiveFunction a.i
# a is never used again, i.e. it's dead
```
should only allocate the storage for the `a` array, which should get reused for `b`.
Note that the same should happen even if `a` is not a scalar array, and we should detect a situation where e.g. only a subset of record fields are updated. For example, the following piece of code should only write to the array storing the `y` fields of the records, while the storage of `x`s should get reused for `b` without any modifications:
```
a = for i. {x=ordinal i, y=2}
b = for i. setAt #y 4 a.i
```
Contributor guide
Research direction
Start by reading the linked Perceus paper and tracing Dex's implementation of `for` loops and array storage. Done means the example reuses `a`'s storage for `b`, including non-scalar arrays, and preserves untouched record-field storage in the second example.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- compilers, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100