dgkf / dgkf/R

Heuristics for materializing vectors

Open
#130 1 comment 0 reactions 0 assignees View on GitHub
meta-discussion theme-internals
Dominant language
Rust
Stars
145
Forks
5
PR merge metrics
No merged PRs in 30d

Description

The feature of this language to have altreps deeply embedded into the language will allow all sorts of optimizations and avoidance of memory allocation, which is great.
However, I think we also need to be aware that it can sometimes be hurtful.

Let's say we have the (admittedly nonsensical) code below, where the size of the underlying vector on which we have a view far exceeds the size of the view.

```r
f <- function() {
x <- rnorm(1000000)
x[1:10]
}

a <- f()
```

If we would represent `a` with an altrep view onto the vector generated by `rnorm(1_000_000)`, this would keep a very large vector in memory even though we only need the first 10 elements.

Besides memory, altreps can also make access to vector elements more expensive.
Consider the (also nonsensical) example below:
```r
b <- rnorm(1000000)
b <- b[|b| > 1][1:100] # Creates a RepType::Subset(vec![...], Subsets(vec![Subset::Mask, Subset::Range]))
```

Accessing elements of the (altrep) `b` is more expensive than accessing an materialized version of `b`.
To really know when we should materialize altreps, we would need some sort of compilation, where we can look ahead and see how (often) the altrep is used to determine whether we should materialize it.

So for now, I think we need some reasonably heuristic to determine when we materialize an altrep.
My suggestion would be that we always materialize an altrep when it is bound to a variable.
The idea behind this heuristic is that:

* The materialized view is (in most cases) the most efficient view (in terms of memory and access-cost) on a vector.
* Binding an altrep to a variable is an indicator that it is data that will be accessed multiple times.

Probably, we also want a way for the user to opt-out of materialization on assignment, e.g. a primitive `view()`

```r
x <- rnorm(1000)
x <- view(x[1:100]) # x is an altrep
x <- x[1:100]# x is materialized
```

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.