为什么有些逻辑运算符如此之慢？

Question

虽然试图优化我的代码,我发现了一些logical操作进行比较,以类似的操作时,比我预想的要慢integer或numeric.

于是我就到重写基本布尔运算符!,&,|,xor如下:

my.not <- function(x) as.logical(1L - as.integer(x))
my.and <- function(e1, e2) as.logical(as.integer(e1) * as.integer(e2))
my.or  <- function(e1, e2) as.logical(as.integer(e1) + as.integer(e2))
my.xor <- function(e1, e2) as.logical(as.integer(e1) + as.integer(e2) == 1L)

测试一切是否按预期工作:

a <- sample(c(TRUE, FALSE), 1e6, TRUE)
b <- sample(c(TRUE, FALSE), 1e6, TRUE)

identical(!a, my.not(a))             # TRUE
identical(a & b, my.and(a, b))       # TRUE
identical(a | b, my.or(a, b))        # TRUE
identical(xor(a, b), my.xor(a, b))   # TRUE

现在基准测试:

library(microbenchmark)
microbenchmark(!a, my.not(a),
               a & b, my.and(a, b),
               a | b, my.or(a, b),
               xor(a, b), my.xor(a, b))

# Unit: milliseconds
#          expr       min        lq    median         uq       max neval
#            !a  1.237437  1.459042  1.463259   1.492671  17.28209   100
#     my.not(a)  6.018455  6.263176  6.414515  15.291194  70.16313   100
#         a & b 32.318530 32.667525 32.769014  32.973878  50.55528   100
#  my.and(a, b)  8.010022  8.592776  8.750786  18.145590  78.38736   100
#         a | b 32.030545 32.383769 32.506937  32.820720 102.43609   100
#   my.or(a, b) 12.089538 12.434793 12.663695  22.046841  32.19095   100
#     xor(a, b) 94.892791 95.480200 96.072202 106.104000 164.19937   100
#  my.xor(a, b) 13.337110 13.708025 14.048350  24.485478  29.75883   100

看看结果,!运营商是唯一一个看起来比我自己做得体面的人.其他三个慢几倍.Primitive功能有点尴尬.我甚至期望良好实现的布尔运算符应该比整数运算快得多(我如何实现自己的函数.)

问题:为什么？执行不好？或者,也许原始功能正在做一些好东西(如错误检查,特殊情况下),我的功能都没有？

Answer 1

稍微看一下C实现,逻辑和数学运算以不同的方式实现它们的循环.逻辑运算就像(在logic.c:327中)

library(inline)

or1 <- cfunction(c(x="logical", y="logical"), "
    int nx = LENGTH(x), ny = LENGTH(y), n = nx > ny ? nx : ny;
    SEXP ans = PROTECT(allocVector(LGLSXP, n));
    int x1, y1;
    for (int i = 0; i < n; i++) {
        x1 = LOGICAL(x)[i % nx];
        y1 = LOGICAL(y)[i % ny];
        if ((x1 != NA_LOGICAL && x1) || (y1 != NA_LOGICAL && y1))
            LOGICAL(ans)[i] = 1;
        else if (x1 == 0 && y1 == 0)
            LOGICAL(ans)[i] = 0;
        else
            LOGICAL(ans)[i] = NA_LOGICAL;
    }
    UNPROTECT(1);
    return ans;
")

%每次迭代都有两个模运算符.相比之下,算术运算(在Itermacros.h:54中)就是这样的

or2 <- cfunction(c(x="logical", y="logical"), "
    int nx = LENGTH(x), ny = LENGTH(y), n = nx > ny ? nx : ny;
    SEXP ans = PROTECT(allocVector(LGLSXP, n));
    int x1, y1, ix=0, iy=0;
    for (int i = 0; i < n; i++) {
        x1 = LOGICAL(x)[ix];
        y1 = LOGICAL(x)[iy];
        if (x1 == 0 || y1 == 0)
            LOGICAL(ans)[i] = 0;
        else if (x1 == NA_LOGICAL || y1 == NA_LOGICAL)
            LOGICAL(ans)[i] = NA_LOGICAL;
        else
            LOGICAL(ans)[i] = 1;

        if (++ix == nx) ix = 0;
        if (++iy == ny) iy = 0;
    }
    UNPROTECT(1);
    return ans;
")

进行两次身份测试.这是一个跳过NA测试的版本

or3 <- cfunction(c(x="logical", y="logical"), "
    int nx = LENGTH(x), ny = LENGTH(y), n = nx > ny ? nx : ny;
    SEXP ans = PROTECT(allocVector(LGLSXP, n));
    int x1, y1, ix=0, iy=0;
    for (int i = 0; i < n; ++i) {
        x1 = LOGICAL(x)[ix];
        y1 = LOGICAL(y)[iy];
        LOGICAL(ans)[i] = (x1 || y1);
        if (++ix == nx) ix = 0;
        if (++iy == ny) iy = 0;
    }
    UNPROTECT(1);
    return ans;
")

然后是一个避免LOGICAL宏的版本

or4 <- cfunction(c(x="logical", y="logical"), "
    int nx = LENGTH(x), ny = LENGTH(y), n = nx > ny ? nx : ny;
    SEXP ans = PROTECT(allocVector(LGLSXP, n));
    int *xp = LOGICAL(x), *yp = LOGICAL(y), *ansp = LOGICAL(ans);
    for (int i = 0, ix = 0, iy = 0; i < n; ++i)
    {
        *ansp++ = xp[ix] || yp[iy];
        ix = (++ix == nx) ? 0 : ix;
        iy = (++iy == ny) ? 0 : iy;
    }
    UNPROTECT(1);
    return ans;
")

这是一些时间安排

microbenchmark(my.or(a, b), a|b, or1(a, b), or2(a, b), or3(a, b), or4(a, b))
Unit: milliseconds
        expr       min        lq    median       uq      max neval
 my.or(a, b)  8.002435  8.100143 10.082254 11.56076 12.05393   100
       a | b 23.194829 23.404483 23.860382 24.30020 24.96712   100
   or1(a, b) 17.323696 17.659705 18.069139 18.42815 19.57483   100
   or2(a, b) 13.040063 13.197042 13.692152 14.09390 14.59378   100
   or3(a, b)  9.982705 10.037387 10.578464 10.96945 11.48969   100
   or4(a, b)  5.544096  5.592754  6.106694  6.30091  6.94995   100

区别a|b和or1反映了这里未实现的内容,如属性和维度以及对象的特殊处理.从or1以or2反映的回收方式的不同成本; 我很惊讶这里有不同之处.从or2到or3是NA安全的成本.有一点很难知道or4在基本R实现中是否会看到额外的加速- 用户C代码LOGICAL()是一个宏,但在基础R中它是一个内联函数调用.

代码是用-O2标志和编译的

> system("clang++ --version")
Ubuntu clang version 3.0-6ubuntu3 (tags/RELEASE_30/final) (based on LLVM 3.0)
Target: x86_64-pc-linux-gnu
Thread model: posix

my.or独立的R会议之间的时间并不是特别一致,有时会花费更长的时间; 我不知道为什么.上面的时间是R版本2.15.3补丁(2013-03-13 r62579); 目前的R-devel似乎快10%左右.

Answer 2

虽然我非常喜欢你的方法并喜欢速度提升,但遗憾的是,当e1 e2结构比矢量更复杂时,它们会失去能力.

> dim(a) <- c(1e2, 1e4)
> dim(b) <- c(1e2, 1e4)
> 
> identical(!a, my.not(a))            
[1] FALSE
> identical(a & b, my.and(a, b))       
[1] FALSE
> identical(a | b, my.or(a, b))        
[1] FALSE
> identical(xor(a, b), my.xor(a, b))   
[1] FALSE

结构/尺寸

逻辑函数保留了结构和属性,这是昂贵的,但是有价值的.

T <- TRUE; F <- FALSE
A <- matrix(c(T, F, T, F), ncol=2)
B <- matrix(c(T, F, F, T), ncol=2)

> A & B
      [,1]  [,2]
[1,]  TRUE FALSE
[2,] FALSE FALSE

> my.and(A, B)
[1]  TRUE FALSE FALSE FALSE

NA处理

此外,正如评论中所指出的,NA还需要考虑s - 即更多的开销.

a <- c(T, F, NA, T)
b <- c(F, NA, T, T)
>     identical(!a, my.not(a))    
[1] TRUE
>     identical(a & b, my.and(a, b))       
[1] FALSE
>     identical(a | b, my.or(a, b))        
[1] FALSE
>     identical(xor(a, b), my.xor(a, b))   
[1] TRUE

ATTRIBUTES

a <- c(T, F, NA, T)
b <- c(F, NA, T, T)

names(a) <- names(b) <- LETTERS[23:26]

> a & b
    W     X     Y     Z 
FALSE FALSE    NA  TRUE 

> my.and(a, b)
[1] FALSE    NA    NA  TRUE

不是速度

当然,尽管如此,你的功能还是增加了!如果你知道你不必担心NAs和喜欢的东西,而你不关心结构,那么为什么不用它们呢!