Почему некоторые из логических операторов настолько медленны?

При попытке оптимизировать мой код я обнаружил, что некоторые операции 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. Я даже ожидаю, что хорошо реализованные логические операторы должны быть намного быстрее, чем операции с целыми числами (как я реализовал свои собственные функции.)

Вопрос: Почему? Плохая реализация? Или, может быть, примитивные функции делают некоторые хорошие вещи (например, проверку ошибок, особые случаи), что мои функции не являются?

Ответ 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 Patched (2013-03-13 r62579); текущий R-девел, казалось, был на 10% быстрее.

Ответ 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 - то есть больше накладных расходов.

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

ПРИЗНАКИ

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

Не скорость

Конечно, при всем том, что вы говорите, ваши функции предлагают щекотку увеличения! Если вы знаете, что вам не нужно беспокоиться о НС и подобных, и вы не заботитесь о структуре, то почему бы просто не использовать их!

Ответ 3

Кроме того, не забывайте, что в R логики хранятся как целые числа в памяти. Поэтому имеет смысл не иметь большого улучшения скорости.

> a=rep(TRUE,1000)
> b=rep(1L,1000)
> c=rep(1,1000)
> class(a)
[1] "logical"
> class(b)
[1] "integer"
> class(c)
[1] "numeric"
> object.size(a)
4040 bytes
> object.size(b)
4040 bytes
> object.size(c)
8040 bytes