切片（原始）向量的更快方法？
Faster way to slice a (raw) vector?
问题
我正在寻找一种快速（最好是恒定时间）的方法来在 R 中对长原始向量进行大切片。例如：
obj <- raw(2^32)
obj[seq_len(2^31 - 1)]
即使使用 ALTREP，基础 R 也需要很长时间。
system.time(obj[seq_len(2^31 - 1)])
#> user system elapsed
#> 19.470 38.853 148.288
为什么？
因为我正在尝试 speed up storr in order speed up drake. I want storr to save long raw vectors more quickly. writeBin() is super fast, but it still cannot handle vectors more than 2^31 - 1 bytes long. So I want to save the data in manageable chunks as . This almost works, but creating the chunks is too slow，它在内存中复制了太多数据。
想法
让我们创建一个函数
slice_raw <- function(obj, from, to) {
# ???
}
本质上等同于
obj[seq(from, to, by = 1L)]
并且在时间和内存上都是 O(1)。理论上，我们需要做的就是
- 将
obj 传递给 C 函数。
- 创建指向
obj 第一个字节的新指针。
- 增加指向切片开始的新指针。
- 在具有适当长度（小于 2^31 字节）的新指针处创建一个
RAWSXP。
- Return
RAWSXP.
我有 C 语言背景，但我很难完全控制 R's internals. I would like to access the C pointers inside SEXPs so I can do basic pointer arithmetic 并从未修饰的 C 指针创建已知长度的 R 向量。我在 R's C internals 上找到的资源似乎没有解释如何包装或解包指针。为此，我们需要 Rcpp 吗？
下面的草图说明了我正在尝试做的事情。
library(inline)
sig <- c(
x = "raw", # Long raw vector with more than 2^31 - 1 bytes.
start = "integer", # Should probably be R_xlen_t.
bytes = "integer" # <= 2^31 - 1. Ideally coercible to R_xlen_t.
)
body <- "
Rbyte* result; // Just a reference. Want to avoid copying data.
result = RAW(x) + start; // Trying to do ordinary pointer arithmetic.
return asRaw(result); // Want to return a raw vector of length `bytes`.
"
slice_raw <- cfunction(sig = sig, body = body)
编辑：更多潜在的解决方法
感谢德克激发了我对这一问题的思考。对于足够小的数据，我们可以使用 fst 来保存单列数据框，其中列是我们真正关心的原始向量。这种使用 fst 比 writeBin()
更快
library(fst)
wrapper <- data.frame(actual_data = raw(2^31 - 1))
system.time(write_fst(wrapper, tempfile()))
#> user system elapsed
#> 0.362 0.019 0.103
system.time(writeBin(wrapper$actual_data, tempfile()))
#> user system elapsed
#> 0.314 1.340 1.689
由 reprex package (v0.3.0)
于 2019-06-16 创建
遗憾的是，很难创建包含 2^31 行或更多行的数据框。一种技巧是首先将原始向量转换为矩阵，我们避免了通常的整数溢出，因为 (2^31 - 1)^2 字节是几个艾字节。
library(fst)
x <- raw(2^32)
m <- matrix(x, nrow = 2^16, ncol = 2^16)
system.time(write_fst(as.data.frame(m), tempfile()))
#> user system elapsed
#> 8.776 1.459 9.519
由 reprex package (v0.3.0)
于 2019-06-16 创建
我们依然让saveRDS()落入尘埃，但我们不再打败writeBin()。从数据框到矩阵的转换很慢，我不确定它是否可以很好地扩展。
library(fst)
x <- raw(2^30)
m <- matrix(x, nrow = 2^15, ncol = 2^15)
system.time(write_fst(as.data.frame(m), tempfile()))
#> user system elapsed
#> 1.998 0.408 2.409
system.time(writeBin(as.raw(m), tempfile()))
#> user system elapsed
#> 0.329 0.839 1.397
由 reprex package (v0.3.0)
于 2019-06-16 创建
如果像 Dirk 所建议的那样，我们可以使用 R_xlen_t 来索引数据框的行，我们或许可以避免任何转换。
虽然目前 data.frame 的长向量列的支持不是很好，但您仍然可以使用 fst 序列化长原始向量：
# method for writing a raw vector to disk
write_raw <- function(x, path, compress = 50) {
# create a list and add required attributes
y <- list(X = x)
attributes(y) <- c(attributes(y), class = "data.frame")
# serialize and compress to disk
fst::write_fst(y, path, compress)
}
# create raw vector of length >2^31
x <- rep(as.raw(0:255), 2^23 + 10)
# write raw vector
write_raw(x, "raw_vector.fst", 100)
使用此方案，无需将向量拆分为多个部分（正如您已经指出的那样，这会显着降低序列化速度）。原始向量可以是re-read，没有任何复制或切片：
# method for reading a raw vector from disk
read_raw <- function(path) {
# read from disk
z <- fst::read_fst(path)
z$X
}
z <- read_raw("raw_vector.fst")
fst::hash_fst(x) == fst::hash_fst(z)
#> [1] TRUE TRUE
（请注意，目前您需要第一个开发版本才能阅读并支持长向量）
在您的设置中，您将始终将完整的原始向量作为一个整体序列化到磁盘（就像 saveRDS() 一样）。因为您不需要随机访问存储的向量，meta-data存储在 fst 文件中有点矫枉过正。您还可以测试使用 compress_fst() 压缩原始向量然后使用 saveRDS(raw_vec, compress = FALSE).
存储结果的设置
这种设置的优点是压缩器可以使用更大的块进行压缩，从而提高压缩率（效果可能很显着）。使用更大的块也可以加快压缩速度。
另一方面，缺点是在写入磁盘期间不像 write_fst() 那样压缩，因此这种效果可能会减慢序列化速度。而且您不再有随机访问权限，但您实际上并不需要它。
如果您实施 two-step 过程（首先压缩数据，然后将其序列化），如果用户愿意，您将能够允许使用不同的压缩器（例如速度较慢的压缩器具有非常高的性能）慢速磁盘的压缩率）。
有同样的挑战。这是完成任务的小 Rcpp 函数
Rcpp::RawVector raw_slice(
const Rcpp::RawVector &x,
const R_xlen_t offset,
const R_xlen_t size) {
Rcpp::RawVector result = Rcpp::no_init(size);
memcpy ( &result[0], &x[offset - 1], size );
return result;
}
问题
我正在寻找一种快速（最好是恒定时间）的方法来在 R 中对长原始向量进行大切片。例如：
obj <- raw(2^32)
obj[seq_len(2^31 - 1)]
即使使用 ALTREP，基础 R 也需要很长时间。
system.time(obj[seq_len(2^31 - 1)])
#> user system elapsed
#> 19.470 38.853 148.288
为什么？
因为我正在尝试 speed up storr in order speed up drake. I want storr to save long raw vectors more quickly. writeBin() is super fast, but it still cannot handle vectors more than 2^31 - 1 bytes long. So I want to save the data in manageable chunks as
想法
让我们创建一个函数
slice_raw <- function(obj, from, to) {
# ???
}
本质上等同于
obj[seq(from, to, by = 1L)]
并且在时间和内存上都是 O(1)。理论上，我们需要做的就是
- 将
obj传递给 C 函数。 - 创建指向
obj第一个字节的新指针。 - 增加指向切片开始的新指针。
- 在具有适当长度（小于 2^31 字节）的新指针处创建一个
RAWSXP。 - Return
RAWSXP.
我有 C 语言背景，但我很难完全控制 R's internals. I would like to access the C pointers inside SEXPs so I can do basic pointer arithmetic 并从未修饰的 C 指针创建已知长度的 R 向量。我在 R's C internals 上找到的资源似乎没有解释如何包装或解包指针。为此，我们需要 Rcpp 吗？
下面的草图说明了我正在尝试做的事情。
library(inline)
sig <- c(
x = "raw", # Long raw vector with more than 2^31 - 1 bytes.
start = "integer", # Should probably be R_xlen_t.
bytes = "integer" # <= 2^31 - 1. Ideally coercible to R_xlen_t.
)
body <- "
Rbyte* result; // Just a reference. Want to avoid copying data.
result = RAW(x) + start; // Trying to do ordinary pointer arithmetic.
return asRaw(result); // Want to return a raw vector of length `bytes`.
"
slice_raw <- cfunction(sig = sig, body = body)
编辑：更多潜在的解决方法
感谢德克激发了我对这一问题的思考。对于足够小的数据，我们可以使用 fst 来保存单列数据框，其中列是我们真正关心的原始向量。这种使用 fst 比 writeBin()
library(fst)
wrapper <- data.frame(actual_data = raw(2^31 - 1))
system.time(write_fst(wrapper, tempfile()))
#> user system elapsed
#> 0.362 0.019 0.103
system.time(writeBin(wrapper$actual_data, tempfile()))
#> user system elapsed
#> 0.314 1.340 1.689
由 reprex package (v0.3.0)
于 2019-06-16 创建遗憾的是，很难创建包含 2^31 行或更多行的数据框。一种技巧是首先将原始向量转换为矩阵，我们避免了通常的整数溢出，因为 (2^31 - 1)^2 字节是几个艾字节。
library(fst)
x <- raw(2^32)
m <- matrix(x, nrow = 2^16, ncol = 2^16)
system.time(write_fst(as.data.frame(m), tempfile()))
#> user system elapsed
#> 8.776 1.459 9.519
由 reprex package (v0.3.0)
于 2019-06-16 创建我们依然让saveRDS()落入尘埃，但我们不再打败writeBin()。从数据框到矩阵的转换很慢，我不确定它是否可以很好地扩展。
library(fst)
x <- raw(2^30)
m <- matrix(x, nrow = 2^15, ncol = 2^15)
system.time(write_fst(as.data.frame(m), tempfile()))
#> user system elapsed
#> 1.998 0.408 2.409
system.time(writeBin(as.raw(m), tempfile()))
#> user system elapsed
#> 0.329 0.839 1.397
由 reprex package (v0.3.0)
于 2019-06-16 创建如果像 Dirk 所建议的那样，我们可以使用 R_xlen_t 来索引数据框的行，我们或许可以避免任何转换。
虽然目前 data.frame 的长向量列的支持不是很好，但您仍然可以使用 fst 序列化长原始向量：
# method for writing a raw vector to disk
write_raw <- function(x, path, compress = 50) {
# create a list and add required attributes
y <- list(X = x)
attributes(y) <- c(attributes(y), class = "data.frame")
# serialize and compress to disk
fst::write_fst(y, path, compress)
}
# create raw vector of length >2^31
x <- rep(as.raw(0:255), 2^23 + 10)
# write raw vector
write_raw(x, "raw_vector.fst", 100)
使用此方案，无需将向量拆分为多个部分（正如您已经指出的那样，这会显着降低序列化速度）。原始向量可以是re-read，没有任何复制或切片：
# method for reading a raw vector from disk
read_raw <- function(path) {
# read from disk
z <- fst::read_fst(path)
z$X
}
z <- read_raw("raw_vector.fst")
fst::hash_fst(x) == fst::hash_fst(z)
#> [1] TRUE TRUE
（请注意，目前您需要第一个开发版本才能阅读并支持长向量）
在您的设置中，您将始终将完整的原始向量作为一个整体序列化到磁盘（就像 saveRDS() 一样）。因为您不需要随机访问存储的向量，meta-data存储在 fst 文件中有点矫枉过正。您还可以测试使用 compress_fst() 压缩原始向量然后使用 saveRDS(raw_vec, compress = FALSE).
这种设置的优点是压缩器可以使用更大的块进行压缩，从而提高压缩率（效果可能很显着）。使用更大的块也可以加快压缩速度。
另一方面，缺点是在写入磁盘期间不像 write_fst() 那样压缩，因此这种效果可能会减慢序列化速度。而且您不再有随机访问权限，但您实际上并不需要它。
如果您实施 two-step 过程（首先压缩数据，然后将其序列化），如果用户愿意，您将能够允许使用不同的压缩器（例如速度较慢的压缩器具有非常高的性能）慢速磁盘的压缩率）。
有同样的挑战。这是完成任务的小 Rcpp 函数
Rcpp::RawVector raw_slice(
const Rcpp::RawVector &x,
const R_xlen_t offset,
const R_xlen_t size) {
Rcpp::RawVector result = Rcpp::no_init(size);
memcpy ( &result[0], &x[offset - 1], size );
return result;
}