dgkf / dgkf/R

Vector internal altreps

Open
#2 10 comments 0 reactions 1 assignee Claimed by @dgkf View on GitHub
theme-internals type-design
Dominant language
Rust
Stars
145
Forks
5
PR merge metrics
No merged PRs in 30d

Description

Since this repo seems to have gathered a bit of visibility, I just want to file an issue for what I've been experimenting with recently.

One of the impressive enhancements that R has received is the idea of internal "altreps" for vectors. This avoids allocating huge vectors for things like ranges, which can be completely described by a start, end and increment (`lobstr::obj_size(1:2) == lobstr::obj_size(1:1e12)`).

Internally within rust, I'd like to have a few altreps:
- A `Vector`:
- The typical R-style vector with all values allocated
- Any `IntoIterator`:
- This should handle cases of ranges, and could be used for some primitives if things like `seq` were built as primitives.
- This would be the representation used for performing any vectorized primitives, iterating over (possibly zipped) elements.
- Ideally, this would mean vectorized operations also produce iterator representations so that they can be materialized lazily (but this butts up against some tough lifetime management and might be a longer term goal than I care to tackle right now) ([other considerations on "views" in Jan Vitek's _R melts brains_](https://youtu.be/VdD0nHbcyk4?t=2310), which suggests a pass to fuse expressions to reduce iterations over vectors when evaluating).
- A `Subset`:
- A vector with added information about how it has been subset.
- The subset indices can be applied to produce a materialized vector or simply used for indexing to provide a mutable interface to the vector values without copying a whole vector into a new value.
- Allows for improving the performance of indexed assignment (`x[[1]][[1]][[1]] <- 3`) to avoid excessive allocations as each layer of indexing reallocates a new vector.

To sort of map out an ideal workflow in my eyes, this is how I'd like to see the evaluation of vectors:

```r
x = c(1, 2, 3) # internally represented by a rust Vec<_>
y = 4:6 # internally represented as an iterator of values in the range 4-6

# creates an internal iterator, returning a new iterator (not materialized values!)
# eg, `x.zip(y).map(|(xi, yi)| xi + yi)`
# note that y is iterated over twice in this case, both iterating over the same source
z = x + y + y

# when elements of z are needed, it is then collected into an internal Vec<_>
print(z)
```

I've been writing a series of small experiments to try to build this in a way that covers these use cases. The `Vector` and `Subset` use cases are well defined, but I'm finding the `IntoIterator` case to be a bit challenging.

I think this is an important internal concept to nail down early, so I'm taking my time to do lots of experiments.

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.