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

Question

在比较检查列表是否包含R中的另一个列表时,比较两个函数的效率,我偶然发现了一个有趣的结果.排序大大提高了duplicated矢量大时的效率.这是一个惊喜,因为我从未注意到我自己的工作使用时有相当大的差异duplicated.事实上,对于我每天工作的尺寸,没有区别.注意:

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,...)).然后使用@joran建议的函数pryr::show_c_source(.Internal(duplicated(x)))和变通方法(show_c_source目前正在给出问题..请参阅'show_c_source()'borken？),我们看到duplicated调用do_duplicated.最后,心脏的duplicated显露(它开始于行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)

我并不完全理解所有代码,但似乎排序无关紧要.我们在任何一种情况下循环遍历整个向量(排序与非排序)并最终调用各种散列函数,这不应取决于向量是否排序.我最初的想法是某种分支预测正在进行(见这个问题),但从更新到这个答案,似乎这些事情不再重要.

这是怎么回事？？

编辑

随着向量的大小和重复数量的增加,差距似乎也在增加.

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

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

为了测试这一点，让我们使用原始帖子的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