“ * application”家族真的没有向量化吗?

因此,我们习惯于对每个 R 新用户说“ apply不是矢量化的,看看帕特里克 · 伯恩斯(Patrick Burns)的《地狱之火》第四卷”,它说(我引用) :

一个常见的反射是在 application 家族中使用一个函数 向量化,它是循环隐藏 Lapplication 函数隐藏循环,但是执行 时间趋向于大致等于显式 for 循环。

事实上,快速浏览一下 apply源代码就会发现这个循环:

grep("for", capture.output(getAnywhere("apply")), value = TRUE)
## [1] "        for (i in 1L:d2) {"  "    else for (i in 1L:d2) {"

到目前为止还好,但是看看 lapply或者 vapply实际上揭示了一幅完全不同的画面:

lapply
## function (X, FUN, ...)
## {
##     FUN <- match.fun(FUN)
##     if (!is.vector(X) || is.object(X))
##        X <- as.list(X)
##     .Internal(lapply(X, FUN))
## }
## <bytecode: 0x000000000284b618>
## <environment: namespace:base>

所以很明显,这里没有隐藏 Rfor循环,而是调用了内部 C 编写的函数。

快速浏览一下 Rabbit 就会发现几乎相同的图片

此外,让我们以 colMeans函数为例,它从来没有因为没有向量化而受到指责

colMeans
# function (x, na.rm = FALSE, dims = 1L)
# {
#   if (is.data.frame(x))
#     x <- as.matrix(x)
#   if (!is.array(x) || length(dn <- dim(x)) < 2L)
#     stop("'x' must be an array of at least two dimensions")
#   if (dims < 1L || dims > length(dn) - 1L)
#     stop("invalid 'dims'")
#   n <- prod(dn[1L:dims])
#   dn <- dn[-(1L:dims)]
#   z <- if (is.complex(x))
#     .Internal(colMeans(Re(x), n, prod(dn), na.rm)) + (0+1i) *
#     .Internal(colMeans(Im(x), n, prod(dn), na.rm))
#   else .Internal(colMeans(x, n, prod(dn), na.rm))
#   if (length(dn) > 1L) {
#     dim(z) <- dn
#     dimnames(z) <- dimnames(x)[-(1L:dims)]
#   }
#   else names(z) <- dimnames(x)[[dims + 1]]
#   z
# }
# <bytecode: 0x0000000008f89d20>
#   <environment: namespace:base>

啊?它也只是调用 .Internal(colMeans(...,我们也可以在 兔子洞中找到它。那么这和 .Internal(lapply(..有什么不同呢?

实际上,一个快速的基准测试表明,对于大数据集,sapply的性能并不比 colMeans差,而且比 for循环好得多

m <- as.data.frame(matrix(1:1e7, ncol = 1e5))
system.time(colMeans(m))
# user  system elapsed
# 1.69    0.03    1.73
system.time(sapply(m, mean))
# user  system elapsed
# 1.50    0.03    1.60
system.time(apply(m, 2, mean))
# user  system elapsed
# 3.84    0.03    3.90
system.time(for(i in 1:ncol(m)) mean(m[, i]))
# user  system elapsed
# 13.78    0.01   13.93

换句话说,说 lapplyvapply 实际上是矢量化的(与 apply相比,apply是一个 for循环,也调用 lapply)是否正确? 帕特里克 · 伯恩斯到底想说什么?

10935 次浏览

首先,在您的示例中,您对“ data.frame”进行测试,这对于 colMeansapply"[.data.frame"是不公平的,因为它们有开销:

system.time(as.matrix(m))  #called by `colMeans` and `apply`
#   user  system elapsed
#   1.03    0.00    1.05
system.time(for(i in 1:ncol(m)) m[, i])  #in the `for` loop
#   user  system elapsed
#  12.93    0.01   13.07

在矩阵中,情况略有不同:

mm = as.matrix(m)
system.time(colMeans(mm))
#   user  system elapsed
#   0.01    0.00    0.01
system.time(apply(mm, 2, mean))
#   user  system elapsed
#   1.48    0.03    1.53
system.time(for(i in 1:ncol(mm)) mean(mm[, i]))
#   user  system elapsed
#   1.22    0.00    1.21

回到问题的主要部分,lapply/mapply/etc 和直接的 R 循环之间的主要区别在于循环是在哪里完成的。正如 Roland 指出的,C 和 R 循环都需要在每次迭代中计算一个 R 函数,这是代价最高的。真正快速的 C 函数是那些在 C 中做所有事情的函数,所以,我想,这应该是“向量化”的含义吧?

一个例子,我们可以在每个“列表”元素中找到平均值:

(编辑: 2016年5月11日: 我认为找到“均值”的例子并不能很好地解释迭代计算 R 函数和编译代码之间的差异,(1)由于 R 的均值算法在简单 sum(x) / length(x)上的“数值”上的特殊性,(2)在“列表”上用 length(x) >> lengths(x)进行测试应该更有意义。因此,将“ mean”示例移到末尾,替换为另一个。)

作为一个简单的例子,我们可以考虑“列表”中每个 length == 1元素的对立面:

tmp.c文件中:

#include <R.h>
#define USE_RINTERNALS
#include <Rinternals.h>
#include <Rdefines.h>


/* call a C function inside another */
double oppC(double x) { return(ISNAN(x) ? NA_REAL : -x); }
SEXP sapply_oppC(SEXP x)
{
SEXP ans = PROTECT(allocVector(REALSXP, LENGTH(x)));
for(int i = 0; i < LENGTH(x); i++)
REAL(ans)[i] = oppC(REAL(VECTOR_ELT(x, i))[0]);


UNPROTECT(1);
return(ans);
}


/* call an R function inside a C function;
* will be used with 'f' as a closure and as a builtin */
SEXP sapply_oppR(SEXP x, SEXP f)
{
SEXP call = PROTECT(allocVector(LANGSXP, 2));
SETCAR(call, install(CHAR(STRING_ELT(f, 0))));


SEXP ans = PROTECT(allocVector(REALSXP, LENGTH(x)));
for(int i = 0; i < LENGTH(x); i++) {
SETCADR(call, VECTOR_ELT(x, i));
REAL(ans)[i] = REAL(eval(call, R_GlobalEnv))[0];
}


UNPROTECT(2);
return(ans);
}

在 R 面:

system("R CMD SHLIB /home/~/tmp.c")
dyn.load("/home/~/tmp.so")

数据:

set.seed(007)
myls = rep_len(as.list(c(NA, runif(3))), 1e7)


#a closure wrapper of `-`
oppR = function(x) -x


for_oppR = compiler::cmpfun(function(x, f)
{
f = match.fun(f)
ans = numeric(length(x))
for(i in seq_along(x)) ans[[i]] = f(x[[i]])
return(ans)
})

基准:

#call a C function iteratively
system.time({ sapplyC =  .Call("sapply_oppC", myls) })
#   user  system elapsed
#  0.048   0.000   0.047


#evaluate an R closure iteratively
system.time({ sapplyRC =  .Call("sapply_oppR", myls, "oppR") })
#   user  system elapsed
#  3.348   0.000   3.358


#evaluate an R builtin iteratively
system.time({ sapplyRCprim =  .Call("sapply_oppR", myls, "-") })
#   user  system elapsed
#  0.652   0.000   0.653


#loop with a R closure
system.time({ forR = for_oppR(myls, "oppR") })
#   user  system elapsed
#  4.396   0.000   4.409


#loop with an R builtin
system.time({ forRprim = for_oppR(myls, "-") })
#   user  system elapsed
#  1.908   0.000   1.913


#for reference and testing
system.time({ sapplyR = unlist(lapply(myls, oppR)) })
#   user  system elapsed
#  7.080   0.068   7.170
system.time({ sapplyRprim = unlist(lapply(myls, `-`)) })
#   user  system elapsed
#  3.524   0.064   3.598


all.equal(sapplyR, sapplyRprim)
#[1] TRUE
all.equal(sapplyR, sapplyC)
#[1] TRUE
all.equal(sapplyR, sapplyRC)
#[1] TRUE
all.equal(sapplyR, sapplyRCprim)
#[1] TRUE
all.equal(sapplyR, forR)
#[1] TRUE
all.equal(sapplyR, forRprim)
#[1] TRUE

(遵循最初的均值发现的例子) :

#all computations in C
all_C = inline::cfunction(sig = c(R_ls = "list"), body = '
SEXP tmp, ans;
PROTECT(ans = allocVector(REALSXP, LENGTH(R_ls)));


double *ptmp, *pans = REAL(ans);


for(int i = 0; i < LENGTH(R_ls); i++) {
pans[i] = 0.0;


PROTECT(tmp = coerceVector(VECTOR_ELT(R_ls, i), REALSXP));
ptmp = REAL(tmp);


for(int j = 0; j < LENGTH(tmp); j++) pans[i] += ptmp[j];


pans[i] /= LENGTH(tmp);


UNPROTECT(1);
}


UNPROTECT(1);
return(ans);
')


#a very simple `lapply(x, mean)`
C_and_R = inline::cfunction(sig = c(R_ls = "list"), body = '
SEXP call, ans, ret;


PROTECT(call = allocList(2));
SET_TYPEOF(call, LANGSXP);
SETCAR(call, install("mean"));


PROTECT(ans = allocVector(VECSXP, LENGTH(R_ls)));
PROTECT(ret = allocVector(REALSXP, LENGTH(ans)));


for(int i = 0; i < LENGTH(R_ls); i++) {
SETCADR(call, VECTOR_ELT(R_ls, i));
SET_VECTOR_ELT(ans, i, eval(call, R_GlobalEnv));
}


double *pret = REAL(ret);
for(int i = 0; i < LENGTH(ans); i++) pret[i] = REAL(VECTOR_ELT(ans, i))[0];


UNPROTECT(3);
return(ret);
')


R_lapply = function(x) unlist(lapply(x, mean))


R_loop = function(x)
{
ans = numeric(length(x))
for(i in seq_along(x)) ans[i] = mean(x[[i]])
return(ans)
}


R_loopcmp = compiler::cmpfun(R_loop)




set.seed(007); myls = replicate(1e4, runif(1e3), simplify = FALSE)
all.equal(all_C(myls), C_and_R(myls))
#[1] TRUE
all.equal(all_C(myls), R_lapply(myls))
#[1] TRUE
all.equal(all_C(myls), R_loop(myls))
#[1] TRUE
all.equal(all_C(myls), R_loopcmp(myls))
#[1] TRUE


microbenchmark::microbenchmark(all_C(myls),
C_and_R(myls),
R_lapply(myls),
R_loop(myls),
R_loopcmp(myls),
times = 15)
#Unit: milliseconds
#            expr       min        lq    median        uq      max neval
#     all_C(myls)  37.29183  38.19107  38.69359  39.58083  41.3861    15
#   C_and_R(myls) 117.21457 123.22044 124.58148 130.85513 169.6822    15
#  R_lapply(myls)  98.48009 103.80717 106.55519 109.54890 116.3150    15
#    R_loop(myls) 122.40367 130.85061 132.61378 138.53664 178.5128    15
# R_loopcmp(myls) 105.63228 111.38340 112.16781 115.68909 128.1976    15

对我来说,向量化主要是让代码更容易编写和理解。

向量化函数的目标是消除与 For 循环相关的簿记:

means <- numeric(length(mtcars))
for (i in seq_along(mtcars)) {
means[i] <- mean(mtcars[[i]])
}
sds <- numeric(length(mtcars))
for (i in seq_along(mtcars)) {
sds[i] <- sd(mtcars[[i]])
}

你可以写:

means <- vapply(mtcars, mean, numeric(1))
sds   <- vapply(mtcars, sd, numeric(1))

这样可以更容易地看到什么是相同的(输入数据) ,什么是不同的(应用的函数)。

向量化的第二个优点是 for 循环通常是用 C 而不是 R 编写的。这对性能有很大的好处,但我不认为这是向量化的关键特性。矢量化从根本上说是保存你的大脑,而不是保存计算机工作。

因此,为了总结出一些很棒的答案/评论,并提供一些背景知识: R 有4种类型的循环(从非向量化到向量化的顺序)

  1. 在每次迭代中重复调用 R 函数的 Rfor循环(没有矢量化)
  2. 在每次迭代中重复调用 R 函数的 C 循环(没有矢量化)
  3. 只调用 R 函数一次的 C 循环(有点像矢量图)
  4. 一个纯 C 循环,它根本不调用 任何R 函数,而是使用自己的编译函数(矢量化)

所以 *apply家族是第二种类型,除了 apply是第一种类型

您可以从其 源代码中的注释中理解这一点

/* 。内部(lapplication (X,FUN)) */

/* 这是一个特殊的。内部的,未计算的参数也是如此
所以 X 和 FUN 是承诺。 FUN 必须 未被评估以便在例如 bquote 中使用。 */

这意味着 lapplys C 代码接受来自 R 的未计算函数,然后在 C 代码本身中计算它。这基本上就是 lapplys.Internal调用之间的区别

.Internal(lapply(X, FUN))

它有一个包含 R 函数的 FUN参数

以及 colMeans .Internal调用,其中 没有具有 FUN参数

.Internal(colMeans(Re(x), n, prod(dn), na.rm))

lapply不同,colMeans知道 没错需要使用什么函数,因此它在 C 代码内部计算平均值。

您可以清楚地看到在 lapply C 代码中的每个迭代中 R 函数的求值过程

 for(R_xlen_t i = 0; i < n; i++) {
if (realIndx) REAL(ind)[0] = (double)(i + 1);
else INTEGER(ind)[0] = (int)(i + 1);
tmp = eval(R_fcall, rho);   // <----------------------------- here it is
if (MAYBE_REFERENCED(tmp)) tmp = lazy_duplicate(tmp);
SET_VECTOR_ELT(ans, i, tmp);
}

总而言之,lapply没有向量化,尽管它比普通的 R for循环有两个可能的优点

  1. 在循环中访问和赋值在 C 语言中似乎更快(比如在 lapplying 函数中)虽然差别似乎很大,但我们仍然停留在微秒级别,代价高昂的是每次迭代中 R 函数的估值。举个简单的例子:

    ffR = function(x)  {
    ans = vector("list", length(x))
    for(i in seq_along(x)) ans[[i]] = x[[i]]
    ans
    }
    
    
    ffC = inline::cfunction(sig = c(R_x = "data.frame"), body = '
    SEXP ans;
    PROTECT(ans = allocVector(VECSXP, LENGTH(R_x)));
    for(int i = 0; i < LENGTH(R_x); i++)
    SET_VECTOR_ELT(ans, i, VECTOR_ELT(R_x, i));
    UNPROTECT(1);
    return(ans);
    ')
    
    
    set.seed(007)
    myls = replicate(1e3, runif(1e3), simplify = FALSE)
    mydf = as.data.frame(myls)
    
    
    all.equal(ffR(myls), ffC(myls))
    #[1] TRUE
    all.equal(ffR(mydf), ffC(mydf))
    #[1] TRUE
    
    
    microbenchmark::microbenchmark(ffR(myls), ffC(myls),
    ffR(mydf), ffC(mydf),
    times = 30)
    #Unit: microseconds
    #      expr       min        lq    median        uq       max neval
    # ffR(myls)  3933.764  3975.076  4073.540  5121.045 32956.580    30
    # ffC(myls)    12.553    12.934    16.695    18.210    19.481    30
    # ffR(mydf) 14799.340 15095.677 15661.889 16129.689 18439.908    30
    # ffC(mydf)    12.599    13.068    15.835    18.402    20.509    30
    
  2. As mentioned by @Roland, it runs a compiled C loop rather an interpreted R loop


Though when vectorizing your code, there are some things you need to take into account.

  1. If your data set (let's call it df) is of class data.frame, some vectorized functions (such as colMeans, colSums, rowSums, etc.) will have to convert it to a matrix first, simply because this is how they were designed. This means that for a big df this can create a huge overhead. While lapply won't have to do this as it extracts the actual vectors out of df (as data.frame is just a list of vectors) and thus, if you have not so many columns but many rows, lapply(df, mean) can sometimes be better option than colMeans(df).
  2. Another thing to remember is that R has a great variety of different function types, such as .Primitive, and generic (S3, S4) see here for some additional information. The generic function have to do a method dispatch which sometimes a costly operation. For example, mean is generic S3 function while sum is Primitive. Thus some times lapply(df, sum) could be very efficient compared colSums from the reasons listed above

我同意帕特里克•伯恩斯(Patrick Burns)的观点,即它更像是 循环隐藏,而不是 代码矢量化。原因如下:

考虑一下 C代码片段:

for (int i=0; i<n; i++)
c[i] = a[i] + b[i]

我们想做的事情很清楚。但是 怎么做的任务是执行或如何可以执行并不是真正的。默认情况下,循环是一个串行构造。它没有告诉我们事情是否可以并行完成,或者如何并行完成。

最明显的方法是代码在 顺序方式顺序方式中运行。将 a[i]b[i]加载到寄存器上,添加它们,将结果存储在 c[i]中,并对每个 i执行此操作。

然而,现代的处理器有 载体指令集,当执行相同的操作时,它能够在 同样的指令期间在 数据向量数据向量上操作(例如,如上所示添加两个向量)。根据处理器/架构的不同,可以在同一条指令下添加(比如说)来自 ab的四个数字,而不是一次添加一个。

我们希望利用 单指令流多数据流并执行 数据级并行性数据级并行性,例如,一次加载4个东西,一次添加4个东西,一次存储4个东西。这是 code vectorisation

请注意,这不同于代码并行化——其中并发执行多个计算。

如果编译器能够识别这样的代码块,并且 自然而然地向量化它们,那就太好了,这是一项艰巨的任务。< em > 自动代码向量化是计算机科学中一个具有挑战性的研究课题。但是随着时间的推移,编译器在这方面已经做得更好了。您可以检查 GNU-gcc 给你自动矢量化功能。对于 LLVM-clang 给你也是如此。你也可以在最后一个链接中找到一些与 gccICC(Intel C++编译器)相比较的基准。

例如,gcc(我在 v4.9上)在 -O2级别优化时不会自动向量化代码。因此,如果我们要执行上面所示的代码,它将按顺序运行。下面是两个长度为5亿的整数向量相加的计时。

我们要么需要添加标志 -ftree-vectorize或改变优化水平 -O3。(请注意,-O3也执行 其他额外的优化)。标志 -fopt-info-vec很有用,因为它通知循环何时成功向量化)。

# compiling with -O2, -ftree-vectorize and  -fopt-info-vec
# test.c:32:5: note: loop vectorized
# test.c:32:5: note: loop versioned for vectorization because of possible aliasing
# test.c:32:5: note: loop peeled for vectorization to enhance alignment

这告诉我们函数是向量化的。下面是长度为5亿的整数向量的非向量化版本和向量化版本的计时比较:

x = sample(100L, 500e6L, TRUE)
y = sample(100L, 500e6L, TRUE)
z = vector("integer", 500e6L) # result vector


# non-vectorised, -O2
system.time(.Call("Csum", x, y, z))
#    user  system elapsed
#   1.830   0.009   1.852


# vectorised using flags shown above at -O2
system.time(.Call("Csum", x, y, z))
#    user  system elapsed
#   0.361   0.001   0.362


# both results are checked for identicalness, returns TRUE

可以安全地跳过此部分,而不会失去连续性。

编译器并不总是有足够的信息来向量化。我们可以使用 并行编程的 OpenMP 规范,它还提供了一个 Simd编译器指令来指示编译器向量化代码。必须确保没有内存重叠、竞态条件等等。当手动向量化代码时,否则会导致不正确的结果。

#pragma omp simd
for (i=0; i<n; i++)
c[i] = a[i] + b[i]

通过这样做,我们特别要求编译器无论如何都要向量化它。我们需要使用编译时间标志 -fopenmp来激活 OpenMP 扩展。通过这样做:

# timing with -O2 + OpenMP with simd
x = sample(100L, 500e6L, TRUE)
y = sample(100L, 500e6L, TRUE)
z = vector("integer", 500e6L) # result vector
system.time(.Call("Cvecsum", x, y, z))
#    user  system elapsed
#   0.360   0.001   0.360

太棒了!这是用 gcc v6.2.0和 llvm clang v3.9.0(都是通过自制的 MacOS 10.12.3安装的)测试的,这两个版本都支持 OpenMP 4.0。


从这个意义上说,即使 维基百科阵列编程提到操作整个数组的语言通常称之为 矢量化操作,它实际上是 循环隐藏 IMO (除非它实际上是向量化的)。

在 R 的情况下,甚至 C 中的 rowSums()colSums()代码也不利用 代码矢量化 IIUC; 它只是 C 中的一个循环。在 apply()的情况下,它在 R 中,因此所有这些都是 循环隐藏

简而言之,通过以下方法包装一个 R 函数:

只是在 C中编写一个 循环! = 向量化代码。
只是在 R中编写一个 循环! = 向量化代码。

例如,Intel Math Kernel Library (MKL) 实现了函数的向量化形式。

高温


参考文献:

  1. 作者: James Reinders,英特尔公司(这个回答主要是为了总结这个精彩的演讲)