# 02-rectangles.R -- x[i, j, k] and m[i, j] on a simulated store. ASCII only.
#
# 1000 x 800 x 60 doubles in chunks of 100 x 100 x 10, and a 4000 x 3000
# matrix in chunks of 256 x 256. Nothing is allocated: values are computed
# from position, and each fetch call sleeps 50 ms (BOOK_LATENCY).
here <- function() {
f <- sub("^--file=", "", grep("^--file=", commandArgs(FALSE), value = TRUE))
if (length(f)) dirname(f[1]) else "scripts"
}
source(file.path(here(), "_bench.R"))
x <- synthetic(c(1000, 800, 60), c(100, 100, 10))
m <- synthetic(c(4000, 3000), c(256, 256))
a <- bench("block: x[1:250, 1:250, 1:15]", x, x[1:250, 1:250, 1:15])
bench("strided slice: x[seq(1, 1000, 50), , 30]", x, x[seq(1, 1000, 50), , 30])
p <- bench("series at one cell: x[500, 400, ]", x, x[500, 400, ])
bench("matrix window: m[1001:1600, 1001:1400]", m, m[1001:1600, 1001:1400])
e <- bench("the workaround: altarr_extract(x, 500, 400, )", x,
altarr_extract(x, 500, 400, ))
stopifnot(identical(p, e), identical(dim(a), c(250L, 250L, 15L)),
a[250, 250, 15] == 249 + 249 * 1000 + 14 * 800000)
finish()2 The gap: rectangles
There are three ways through R’s subsetting code, and an ALTREP array is treated differently on each.
| You write | R calls | The array sees | Can it plan? |
|---|---|---|---|
x[i] |
VectorSubset() |
Extract_subset, every index at once |
yes |
x[cbind(i, j, k)] |
VectorSubset() after mat2indsub() |
Extract_subset, every index at once |
yes |
x[i, j, k], m[i, j] |
ArraySubset(), MatrixSubset() |
Elt, one element at a time |
no |
In the third row R has done the hard part already. ArraySubset() and MatrixSubset() turn each subscript (negative, logical, character, missing) into a vector of positive positions, one per dimension. That list is the hyperslab. R then walks every output cell and asks the object for that one element.
The patch offers the list to the object first. If the object’s class has an Extract_array_subset method and it returns the values, R skips the walk. Otherwise nothing changes.
2.1 The example
A simulated store, so that the only thing measured is how R asks: 48 million doubles in 480 chunks, never allocated, and a 12 million cell matrix. Each fetch call takes 50 ms however many chunks it carries, the way one round of concurrent requests does.
| Read | Values | Chunks | Fetch calls, stock | Fetch calls, patched | Seconds, stock | Seconds, patched | Faster by | Same values |
|---|---|---|---|---|---|---|---|---|
| block: x[1:250, 1:250, 1:15] | 937,500 | 18 | 18 | 1 | 1.00 | 0.09 | 10.6x | yes |
| strided slice: x[seq(1, 1000, 50), , 30] | 16,000 | 80 | 80 | 1 | 4.14 | 0.15 | 27.6x | yes |
| series at one cell: x[500, 400, ] | 60 | 6 | 6 | 1 | 0.31 | 0.06 | 5.3x | yes |
| matrix window: m[1001:1600, 1001:1400] | 240,000 | 12 | 12 | 1 | 0.63 | 0.06 | 10.1x | yes |
| the workaround: altarr_extract(x, 500, 400, ) | 60 | 6 | 1 | 1 | 0.05 | 0.05 | 1.0x | yes |
The chunk counts match across builds: the patch does not change what is read, only how it is asked for. On stock R the store hears from R once per chunk, in series, in between a great many single-element calls:
| Read | Element calls, stock | Element calls, patched |
|---|---|---|
| block: x[1:250, 1:250, 1:15] | 937,500 | 0 |
| strided slice: x[seq(1, 1000, 50), , 30] | 16,000 | 0 |
| series at one cell: x[500, 400, ] | 60 | 0 |
| matrix window: m[1001:1600, 1001:1400] | 240,000 | 0 |
| the workaround: altarr_extract(x, 500, 400, ) | 0 | 0 |
The last row is the workaround that exists today. altarr_extract() does the planned read on any R, and it is the same speed in both builds. But it is a function you have to know about and call. Code written for arrays calls [.
2.2 Why the element loop cannot be rescued from the inside
A class can make Elt fast for a cached chunk, and altarr does. What it cannot do from inside Elt is know what is coming. The first element of a 250 x 250 x 15 block looks the same as a lone x[1, 1, 1]. Guessing (read ahead on a miss) fetches chunks nobody wanted when the guess is wrong. R knows the whole request. The method is how it says so.