Rcpp内の単一の "for"ループの予期しないパフォーマンス

Question

誰かがRcppを使って書かれた単純なforループの幾分奇妙な動作を説明することができます（コードは以下です）。マイクロベンチマークの出力に基づいて、for_iterationのアルゴリズムの複雑さは定数であり、そのコードに基づいて真ではないようです。比較のために、関数for_double_iterationをテストしました。その動作はコードの複雑さと一貫しています。このコードはUbuntu 16.04とCPU Intel Core i3-6100で実行されましたが、Windows 7とCPU 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に置き換えられています。

はコンパイラフラグ-O2で、あなたはアセンブリ出力（ガス）を取得し、godboltのチェックの有無：

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

おっと...全くループがありません！