r - 为什么 R 的重复数据在排序数据上表现更好？

Question

在Check if list contains another list in R的答案中比较两个函数的效率，我偶然发现了一个有趣的结果。当向量很大时，排序大大提高了重复的效率。这让我感到惊讶，因为我从来没有注意到我自己使用重复的工作有很大的不同。事实上，对于我每天使用的尺寸来说，没有什么区别。观察:

set.seed(1007)
s1 <- sample(10^2, 10^3, replace = TRUE)
s1_sort <- sort(s1)
library(microbenchmark)
microbenchmark(dp=duplicated(s1), dp_sort=duplicated(s1_sort), times=1000)
Unit: microseconds
   expr    min      lq     mean  median      uq      max neval cld
     dp 16.459 16.9425 22.06371 17.2965 22.5050 1541.137  1000   a
dp_sort 17.007 17.5005 25.54953 17.8200 23.3655 1549.198  1000   a

如您所见，向量排序时的时间没有明显差异。然而，对于非常大的向量，结果有很大不同。观察:

s2 <- sample(10^6, 10^7, replace = TRUE)
s2_sort <- sort(s2)
microbenchmark(dp=duplicated(s2), dp_sort=duplicated(s2_sort), times=100)
Unit: milliseconds
   expr      min       lq     mean   median       uq       max neval cld
     dp 816.6883 847.9231 869.6829 861.8210 882.3978 1019.6339   100   b
dp_sort 287.6779 305.4779 322.8830 315.1198 324.9249  449.1734   100  a 

几乎快了 3 倍!!!这让我陷入了兔子洞，它从这里开始:r-source.../duplicated.R 。从这里我们可以看到，duplicated 调用了 .Internal(duplicated(x,...))。然后使用函数 pryr::show_c_source(.Internal(duplicated(x))) 和 workaround由 @joran 建议(show_c_source 目前出现问题。请参阅 Is 'show_c_source()' borken? )，我们看到 duplicated 调用了 do_duplicated 。最后，heart显示了重复的内容(从第 667 行开始，到第 988 行结束)。看起来整个向量被循环，然后发生一些散列:

724     /* count unique entries */
725     k = 0;
726     for (i = 0; i < n; i++)
727         if (LOGICAL(dup)[i] == 0)
728             k++;

776     /* Build a hash table, ignoring information on duplication */
777     static void DoHashing(SEXP table, HashData *d)

我不完全理解所有代码，但似乎排序并不重要。无论哪种情况(排序与非排序)，我们都会循环遍历整个向量，并最终调用各种哈希函数，这不应该取决于向量是否排序。我最初的想法是正在进行某种分支预测(参见 this question )，但是从更新到 this answer ，看来这些事情应该已经不重要了。

这是怎么回事？

编辑

随着向量大小和重复项数量的增加，差距似乎会增加。

set.seed(496)
s3 <- sample(10^6, 10^8, replace = TRUE)
s3_sort <- sort(s3)
microbenchmark(dp=duplicated(s3), dp_sort=duplicated(s3_sort), times = 10)
Unit: seconds
   expr       min        lq      mean    median        uq       max neval cld
     dp 12.149932 12.175665 12.848843 12.495599 12.719861 15.589190    10   b
dp_sort  2.395636  2.401837  2.706674  2.551375  2.677556  4.373653    10  a 

正如@alexis_laz指出的，如果没有重复项，排序的影响就会大大降低。

s4 <- sample(10^8)
s4_sort <- sort(s4)
microbenchmark(dp=duplicated(s4), dp_sort=duplicated(s4_sort), times = 10)
Unit: seconds
   expr      min       lq     mean   median       uq       max neval cld
     dp 8.013995 8.130565 8.593626 8.197501 8.438703 10.639452    10   b
dp_sort 6.135788 6.158140 6.751101 6.256739 7.241381  8.913507    10  a 

Answer 1

主要因素是 CPU 缓存未命中率，并且随着大小的增加，页面错误的代价也会更高。通过引用简单的哈希表来检查重复。如果被查询的哈希表部分已经在高速内存缓存中，那么这些查找会快得多。对于小向量，相应的哈希表将完全适合高速内存缓存，因此访问顺序并不重要，这就是您在第一个基准测试中看到的。

对于较大的向量，在任何给定时间只有哈希表的某些 block 适合缓存。如果重复项是连续的，则查找所需的哈希表部分将已经在缓存中以供后续查找。这就是为什么性能会随着较大向量的重复次数而提高。对于非常大的向量，哈希表甚至可能无法完全适合可用的物理内存并被分页到磁盘，从而使差异更加明显。

为了测试这一点，让我们使用原始帖子的 s2 向量及其排序版本，同时也测试仅使重复项彼此相邻但未排序。

# samples as in original post
s2 <- sample(10^6, 10^7, replace = TRUE)
s2_sort <- sort(s2)

# in the same order as s2, but with duplicates brought together
u2 <- unique(s2)
t2 <- rle(s2_sort)
s2_chunked <- rep(u2,times=t2$length[match(u2,t2$values)])

我们还考虑仅按哈希值排序。我将近似 R 中的哈希编码，但我们在这里处理的是双倍大小的值，而不是能够使用无符号长整型，因此我们将无法使用按位运算。

# in the order of hash value
K <- ceiling(log2(length(s2)*2))
M <- 2^K
h <- ((3141592653 * s2) %% 2^32)/2^(32-K)
ho <- order(h)
s2_hashordered <- s2[ho]

我们期望看到的是，s2_sort 和 s2_chunked 的性能相似，s2_hashordered 的性能甚至更好。在每种情况下，我们都尝试最大限度地减少缓存未命中。

microbenchmark(
 duplicated(s2), 
 duplicated(s2_sort), 
 duplicated(s2_chunked),
 duplicated(s2_hashordered),
 times=10)

Unit: milliseconds
                       expr      min       lq     mean   median       uq      max neval cld
             duplicated(s2) 664.5652 677.9340 690.0001 692.3104 703.8312 711.1538    10   c
        duplicated(s2_sort) 245.6511 251.3861 268.7433 276.2330 279.2518 284.6589    10  b 
     duplicated(s2_chunked) 240.0688 243.0151 255.3857 248.1327 276.3141 283.4298    10  b 
 duplicated(s2_hashordered) 166.8814 169.9423 185.9345 185.1822 202.7478 209.0383    10 a