runif的性能表现

Question

我正在为一个特定问题设计自定义的Bootstrap算法，并且由于需要大量重复，因此我非常关心性能。在这方面，我有一些关于如何正确使用runif的问题。我知道我可以自己运行基准测试，但C++优化往往很困难，而且我也想了解任何差异的原因。

第一个问题：

第一个代码块是否比第二个更快？

for (int i = 0; i < n_boot; i++) {
  new_random = runif(n);  //new_random is pre-allocated in class
  // do something with the random numbers
}

---

for (int i = 0; i < n_boot; i++) {
  NumericVector new_random = runif(n);
  // do something with the random numbers
}

这大概取决于runif是填充左侧还是分配并传递新的NumericVector。

第二个问题：

如果两个版本都分配一个新的向量，是否可以通过在标量模式下逐个生成随机数来改善性能？

如果你想知道，内存分配占用了我处理时间的相当一部分。通过优化其他不必要的内存分配，我已经将运行时间缩短了30％，所以这确实很重要。

- Erik

---

你应该在codereview上尝试这个问题 http://codereview.stackexchange.com/ - Sharky

@Sharky 在代码审查中，对于这个问题唯一合理的答案是“进行基准测试！”。由于它是示例代码，所以这个问题本身很可能会被关闭。我认为 Erik 从基准测试中获益更多，而不是从代码审查中获益。顺便说一下，Erik：根据我的经验，这些代码片段的性能没有任何区别。 - Simon Forsberg

你完全没有理解到每天结束时的每次绘图都是针对 R 的 C API 的标量绘图，因此循环发生的位置在性能方面基本上是不相关的。Rcpp Sugar 使使用更加容易。 - Dirk Eddelbuettel

@DirkEddelbuettel 不，我没有错过那个点。我知道循环并不重要，我也不想优化实际生成随机数所用的时间。我想避免的是对NumericVector进行不必要的内存分配。也许问题表述得不够清楚。问题归结为是否有一种方法可以直接将新的随机数写入我已经分配的向量中，而不需要分配和初始化一个新的向量。 - Erik

个人资料。个人资料。个人资料。 - Dirk Eddelbuettel

@DirkEddelbuettel 好的，我本来就要这么做。但无论结果如何，我仍然想要理解为什么。 - Erik

Answer 1

我设置了以下的struct，试图准确地表示您的情况并促进基准测试:

#include <Rcpp.h>
// [[Rcpp::plugins(cpp11)]]

struct runif_test {

  size_t runs;
  size_t each;

  runif_test(size_t runs, size_t each)
  : runs(runs), each(each)
  {}
  // Your first code block
  void pre_init() {
    Rcpp::NumericVector v = no_init();
    for (size_t i = 0; i < runs; i++) {
      v = Rcpp::runif(each);
    }
  }
  // Your second code block
  void post_init() {
    for (size_t i = 0; i < runs; i++) {
      Rcpp::NumericVector v = Rcpp::runif(each);
    }
  }
  // Generate 1 draw at a time  
  void gen_runif() {
    Rcpp::NumericVector v = no_init();
    for (size_t i = 0; i < runs; i++) {
      std::generate_n(v.begin(), each, []() -> double {
        return Rcpp::as<double>(Rcpp::runif(1));
      });
    }
  }
  // Reduce overhead of pre-allocated vector
  inline Rcpp::NumericVector no_init() {
    return Rcpp::NumericVector(Rcpp::no_init_vector(each));
  } 
};

---

我对以下导出函数进行了基准测试:

// [[Rcpp::export]]
void do_pre(size_t runs, size_t each) {
  runif_test obj(runs, each);
  obj.pre_init();
}

// [[Rcpp::export]]
void do_post(size_t runs, size_t each) {
  runif_test obj(runs, each);
  obj.post_init();
}

// [[Rcpp::export]]
void do_gen(size_t runs, size_t each) {
  runif_test obj(runs, each);
  obj.gen_runif();
}

---

这是我得到的结果：

R>  microbenchmark::microbenchmark(
    do_pre(100, 10e4)
    ,do_post(100, 10e4)
    ,do_gen(100, 10e4)
    ,times=100L)
Unit: milliseconds
                 expr      min       lq      mean   median        uq       max neval
  do_pre(100, 100000) 109.9187 125.0477  145.9918 136.3749  152.9609  337.6143   100
 do_post(100, 100000) 103.1705 117.1109  132.9389 130.4482  142.7319  204.0951   100
  do_gen(100, 100000) 810.5234 911.3586 1005.9438 986.8348 1062.7715 1501.2933   100

---

R>  microbenchmark::microbenchmark(
    do_pre(100, 10e5)
    ,do_post(100, 10e5)
    ,times=100L)
Unit: seconds
                  expr      min       lq     mean   median       uq      max neval
  do_pre(100, 1000000) 1.355160 1.614972 1.740807 1.723704 1.815953 2.408465   100
 do_post(100, 1000000) 1.198667 1.342794 1.443391 1.429150 1.519976 2.042511   100

---

所以，假设我正确理解并准确表达了你的第二个问题，

如果两个版本都分配一个新向量，我能否通过在标量模式下逐个生成随机数来改进呢？

使用我的gen_runif()成员函数，我认为我们可以自信地说，这不是最佳方法 - 比另外两个函数慢约7.5倍。

更重要的是，回答您的第一个问题，似乎直接将新的NumericVector初始化并赋值给Rcpp::runif(n)的输出速度要快一些。我并不是C++专家，但我认为第二种方法（将其分配给新的本地对象）比第一种方法更快，因为采用了复制省略。在第二种情况下，看起来好像创建了两个对象-位于=左侧的对象v和位于=右侧的（临时？rvalue？）对象，它是Rcpp::runif()结果。但实际上，编译器很可能会优化掉这个不必要的步骤-我认为这在我链接的文章中有所解释：

这至少是我对结果的解释。希望更熟练该语言的人能够确认/否定/纠正这个结论。

- nrussell

---

谢谢您的详细解释。虽然它不是最优的，但我不知道有 no_init 选项。 - Erik

@Erik，我担心你可能仍在瞄准错误的目标。但是既然你对应该更快有如此坚定的信念，也许你想提供另一种实现方式？ - Dirk Eddelbuettel

@DirkEddelbuettel，“not optimal”并不是对Rcpp实现的批评，而是指pre_init函数使用no_init()选项。我现在非常满意使用基本上就是do_post的内容。顺便说一句，感谢Rcpp包，它对我目前正在开发的R软件包（fbroc）非常有用。 - Erik

Answer 2

在@nrussell的回答中，我会添加一些实现细节...

用源代码，Luke！在这里肯定适用，因此让我们来看看Rcpp::runif的实现这里:

inline NumericVector runif( int n, double min, double max ){
    if (!R_FINITE(min) || !R_FINITE(max) || max < min) return NumericVector( n, R_NaN ) ;
    if( min == max ) return NumericVector( n, min ) ;
    return NumericVector( n, stats::UnifGenerator( min, max ) ) ;
}

我们看到一个有趣的NumericVector构造函数被调用，并使用了一个stats::UnifGenerator对象。该类的定义在这里：

    class UnifGenerator__0__1 : public ::Rcpp::Generator<double> {
    public:

        UnifGenerator__0__1() {}

        inline double operator()() const {
            double u;
            do {u = unif_rand();} while (u <= 0 || u >= 1);
            return u;
        }
    } ;

因此，这个类只是一个函数对象 - 它实现了operator()，因此该类的对象可以被“调用”。

最后，相关的NumericVector构造函数在这里：

template <typename U>
Vector( const int& size, const U& u) {
    RCPP_DEBUG_2( "Vector<%d>( const int& size, const U& u )", RTYPE, size )
    Storage::set__( Rf_allocVector( RTYPE, size) ) ;
    fill_or_generate( u ) ;
}

而那个fill_or_generate函数最终会被调用到这里：此处：

template <typename T>
inline void fill_or_generate__impl( const T& gen, traits::true_type) {
    iterator first = begin() ;
    iterator last = end() ;
    while( first != last ) *first++ = gen() ;
}

我们可以看到，提供了一个（带模板的）生成器函数来填充向量，并使用gen对象的对应operator()来填充向量--也就是说，在这种情况下，stats::UnifGenerator对象。那么问题来了，这个调用该如何组合起来呢？

NumericVector x = runif(10);

我总是因为某些原因忘记这一点，但我认为这基本上是从runif(10)调用的结果中复制构造x，但这一点也被@nrussell详细阐述了。但是，我的理解是：

1. runif生成长度为10的NumericVector，其中包含runif元素 - 将其称为临时右侧对象tmp,
2. 将x复制构造为与上述tmp相同。

我相信编译器将能够省略该复制构造过程，使得x实际上是直接从runif(10)的结果构造的，因此应该是高效的（至少在任何合理的优化级别下），但我可能是错误的....

- Kevin Ushey

---

感谢您的回答。将实现细节提供出来，将有助于未来的工作。 - Erik