Неожиданная производительность одного цикла «для» в Rcpp

Question

Может ли кто-нибудь объяснить мне несколько странное поведение простого цикла, написанного с использованием Rcpp (код ниже). На основе вывода микрообъектов кажется, что алгоритмическая сложность for_iteration является постоянной, которая не соответствует действительности на основе ее кода. Для сравнения я протестировал функцию for_double_iteration, и ее поведение согласуется с ее сложностью кода. Этот код был запущен на Ubuntu 16.04 и процессоре Intel Core i3-6100, но тот же результат был получен в Windows 7 и процессоре Intel Core i5-2300.

Вот код:

library(Rcpp) 
library(microbenchmark) 
sourceCpp(code=' 
    #include <Rcpp.h> 

    // [[Rcpp::export]] 
    int for_iteration(const int n) { 
    int j = 0; 
    for (int i = 0; i < n; i++) { 
     j++; 
    } 
    return (j); 
    } 

    // [[Rcpp::export]] 
    int for_double_iteration(const int n) { 
    int j = 0, k = 0; 
    for (int i = 0; i < n; i++) { 
     for (k = 0; k < i; k++) { 
     j++; 
     } 
    } 
    return (j); 
    }' 
) 

Вот тесты:

> microbenchmark(for_iteration(10^5), 
       for_iteration(10^6), 
       for_iteration(10^7), 
       for_iteration(10^8), 
       for_iteration(10^9), 
       times=1000, unit="us") 
Unit: microseconds 
       expr min lq  mean median  uq  max neval 
for_iteration(10^5) 1.254 1.379 1.552229 1.4305 1.5255 9.197 1000 
for_iteration(10^6) 1.268 1.379 1.724993 1.4300 1.5410 123.822 1000 
for_iteration(10^7) 1.274 1.377 3.687182 1.4240 1.5075 2126.909 1000 
for_iteration(10^8) 1.253 1.387 1.546345 1.4360 1.5320 9.527 1000 
for_iteration(10^9) 1.265 1.386 1.568382 1.4300 1.5230 20.307 1000 

> microbenchmark(for_double_iteration(10^2), 
       for_double_iteration(10^3), 
       for_double_iteration(10^4), 
       for_double_iteration(10^5), 
       for_double_iteration(10^6), 
       times=1000, unit="us") 
Unit: microseconds 
         expr  min  lq  mean median  uq  max neval 
for_double_iteration(10^2) 0.921 1.0230 1.516304 1.1100 1.4335 23.308 1000 
for_double_iteration(10^3) 1.722 1.7970 2.491999 1.8915 2.2270 49.772 1000 
for_double_iteration(10^4) 9.022 9.1165 9.947209 9.2050 9.6925 55.841 1000 
for_double_iteration(10^5) 82.170 82.2700 86.240153 82.3590 82.9070 1959.903 1000 
for_double_iteration(10^6) 813.723 814.4450 834.870686 826.4625 828.2280 1178.062 1000 

Answer 1

Моя догадка верна, то она оптимизирована, и заменены j = n.

Есть чек на godbolt, с компилятором флагом -O2, вы получите выход сборки (газ):

for_iteration(int): 
     test edi, edi 
     mov  eax, 0 
     cmovns eax, edi 
     ret 

... К сожалению, нет никакого цикла вообще !!