r - 在 R 中，为什么 sum 与其他方法(例如 cumsum)相比如此慢？

Question

我正在尝试实现一个需要非常快的函数，主要是因为它一遍又一遍地处理巨大的数据帧。

R 总是让我感到困惑，为什么它有时有点慢，为什么有时又慢得离谱。 (不幸的是，它永远不会快。)

不管怎样，我一直认为，如果可能的话，当以某种方式插入 apply、sapply 或 lapply 时，而不是放入循环中，事情可以运行得更快。我最近遇到一个例子，它让我觉得幕后还有更多的事情发生，如果我理解它，可能会对我 future 的优化有很大帮助。

以下是我在相对强大的 Ubuntu Linux 机器上运行的一些计算:

system.time(sapply(1:1e5, sum))
user  system elapsed
35.130   0.000  35.128


system.time(sapply(1:1e5, cumsum))
user  system elapsed
0.110   0.000   0.108

是的，您正确地读取了这些数字:cumsum(它创建累积和的数组)比仅仅提供简单的总和要快几个数量级。 (如果其他人可以在他们的计算机上验证这些结果，那就太好了!)

我不明白这是怎么可能的，除非实现有很大不同。假设它们确实有很大不同，我想知道以什么方式，这样我就可以在寻找速度时寻找某些要避免的函数。 (对于核心函数，我不知道如何查看它们的源代码。仅输入不带任何括号的函数名称的标准方法不适用于核心函数。)

非常感谢!

Answer 1

或多或少遵循instructions for using operf我用单行 sapply(1:1e5, sum) 创建了一个文件并运行

$ operf ~/bin/R-3-1-branch/bin/R -f sum.R
$ opreport -l ~/bin/R-3-1-branch/lib/libR.so |less

制作

CPU: Intel Sandy Bridge microarchitecture, speed 2.401e+06 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (No unit mask) count 100000
samples  %        image name               symbol name
835882   93.0929  libR.so                  RunGenCollect
27731     3.0884  libR.so                  SortNodes
9323      1.0383  libR.so                  AgeNodeAndChildren
2038      0.2270  libR.so                  CheckFinalizers
1593      0.1774  libR.so                  Rf_allocVector3
1222      0.1361  libR.so                  duplicate1
...

等等。大部分时间都花在垃圾收集器上(RunGenCollect——运行分代垃圾收集器)。于是我就跑了

$ R -d gdb R
(gdb) run
> sapply(1:1e5, sum)
^C
(gdb) break RunGenCollect
(gdb) continue
Continuing.

Breakpoint 1, RunGenCollect (size_needed=50000) at /home/mtmorgan/src/R-3-1-branch/src/main/memory.c:1504
1504        bad_sexp_type_seen = 0;
(gdb) where

产生的

#0  RunGenCollect (size_needed=50000) at /home/mtmorgan/src/R-3-1-branch/src/main/memory.c:1504
#1  0x00007ffff789d354 in R_gc_internal (size_needed=50000) at /home/mtmorgan/src/R-3-1-branch/src/main/memory.c:2825
#2  0x00007ffff789e99b in Rf_allocVector3 (type=13, length=100000, allocator=0x0) at /home/mtmorgan/src/R-3-1-branch/src/main/memory.c:2563
#3  0x00007ffff788e1a5 in Rf_allocVector (type=13, length=100000) at /home/mtmorgan/src/R-3-1-branch/src/include/Rinlinedfuns.h:189
#4  0x00007ffff7831787 in duplicate1 (s=0x7ffff3b0b010, deep=TRUE) at /home/mtmorgan/src/R-3-1-branch/src/main/duplicate.c:335
#5  0x00007ffff783371a in duplicate_child (s=0x7ffff3b0b010, deep=TRUE) at /home/mtmorgan/src/R-3-1-branch/src/main/duplicate.c:199
#6  0x00007ffff783357a in duplicate_list (s=0x2c98b30, deep=TRUE) at /home/mtmorgan/src/R-3-1-branch/src/main/duplicate.c:261
#7  0x00007ffff7830fc2 in duplicate1 (s=0x2c98b30, deep=TRUE) at /home/mtmorgan/src/R-3-1-branch/src/main/duplicate.c:308
#8  0x00007ffff783371a in duplicate_child (s=0x2c98b30, deep=TRUE) at /home/mtmorgan/src/R-3-1-branch/src/main/duplicate.c:199
#9  0x00007ffff783357a in duplicate_list (s=0x2c98a88, deep=TRUE) at /home/mtmorgan/src/R-3-1-branch/src/main/duplicate.c:261
#10 0x00007ffff7830fc2 in duplicate1 (s=0x2c98a88, deep=TRUE) at /home/mtmorgan/src/R-3-1-branch/src/main/duplicate.c:308
#11 0x00007ffff7830c7f in Rf_duplicate (s=0x2c98a88) at /home/mtmorgan/src/R-3-1-branch/src/main/duplicate.c:132
#12 0x00007ffff79257f4 in do_summary (call=0x2c98a88, op=0x6259a0, args=0x303cf88, env=0x2c97f48) at /home/mtmorgan/src/R-3-1-branch/src/main/summary.c:462
...

这里的相关行是第 462 行

(gdb) up 12
#12 0x00007ffff79257f4 in do_summary (call=0x2c98a88, op=0x6259a0, args=0x303cf88, env=0x2c97f48) at /home/mtmorgan/src/R-3-1-branch/src/main/summary.c:462
462     PROTECT(call2 = duplicate(call));
(gdb) list
457     return ans;
458     }
459 
460     /* match to foo(..., na.rm=FALSE) */
461     PROTECT(args = fixup_NaRm(args));
462     PROTECT(call2 = duplicate(call));
463     SETCDR(call2, args);
464 
465     if (DispatchGroup("Summary", call2, op, args, env, &ans)) {
466     UNPROTECT(2);

调用正在重复

(gdb) call Rf_PrintValue(call)
FUN(1:100000[[5339L]], ...)

对于循环的每次迭代，触发垃圾收集。对于 cumsum，不执行类似的代码。这种情况已经持续了很长一段时间，但原因并非 100% 明显

$ svn annotate ~/src/R-3-1-branch/src/main/summary.c |less
...
 42643     ripley     /* match to foo(..., na.rm=FALSE) */
 42643     ripley     PROTECT(args = fixup_NaRm(args));
 42643     ripley     PROTECT(call2 = duplicate(call));
 42643     ripley     SETCDR(call2, args)
...
$ svn log -r42643
------------------------------------------------------------------------
r42643 | ripley | 2007-08-25 23:09:50 -0700 (Sat, 25 Aug 2007) | 1 line

make the rest of the group generics primitive
------------------------------------------------------------------------

在 R-devel 上讨论这个问题会很有趣。邮件列表。并不是 sum 特别慢，而是对垃圾收集器的调用占据了执行时间。

嗯，仔细一想，发现

sapply(1:1e5, function(x) sum(x))

与cumsum在同一个范围内运行。我认为这是因为原始版本中第 462 行的 duplicate 正在制作 1e5 元素的副本，以准备选择第 i 个元素进行求和。相反，在 function(x) sum(x) 中，向量已经是子集，因此仅重复第 i 个元素。复制原始向量还解释了为什么 1e5 元素比 1e4 元素慢得多，以及为什么 as.list(1:1e5) 性能相对较高(实际上仅复制列表元素，或者甚至可能不复制)那)。调用 sum 期间的重复与它属于 (S3) Summary 组泛型这一事实有关，请参阅 ?"group generic".