google-research / google-research/dex-lang

Modify arrays in-place whenever possible

Open
#418 0 comments 2 reactions 0 assignees View on GitHub
backend / optimization
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.