runif 的性能
Performance of runif
我正在研究针对特定问题的自定义 bootstrap 算法,因为我需要大量的重复,所以我很关心性能。对此,我对如何正确使用运行if有一些疑问。我知道我可以 运行 自己进行基准测试,但 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
}
这可能归结为 运行if 是否填充左侧或者是否分配并传递一个新的 NumericVector。
第二个问题:
如果两个版本都分配一个新向量,我可以通过在标量模式下一次生成一个随机数来改进吗?
如果您想知道,内存分配占用了我处理时间的相当大一部分。通过优化其他不必要的内存分配,我已经将 运行 时间减少了 30%,所以这很重要。
我设置了以下 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
所以,假设我解释/准确地表达了你的第二个问题,
If both versions allocate a new vector, can I improve things by
generating one random number at a time in scalar mode?
使用我的 gen_runif()
成员函数,我想我们可以自信地说这不是最佳方法 - ~ 比其他两个函数慢 7.5 倍。
更重要的是,为了解决您的第一个问题,似乎仅初始化并将新的 NumericVector
分配给 Rcpp::runif(n)
的输出会更快一些。我当然不是 C++ 专家,但我相信第二种方法(分配给一个新的本地对象)比第一种更快,因为 copy elision。在第二种情况下,它 看起来 好像正在创建两个对象 - =
、v
左侧的对象和一个(临时?右值) ?) =
右侧的对象,这是 Rcpp::runif()
的结果。但实际上,编译器很可能会优化这个不必要的步骤 - 我认为我链接的文章中的这段话对此进行了解释:
When a nameless temporary, not bound to any references, would be moved
or copied into an object of the same type ... the copy/move is omitted. When that temporary is
constructed, it is constructed directly in the storage where it would
otherwise be moved or copied to.
至少,我是这样解释结果的。希望更精通该语言的人可以确认/否认/纠正这个结论。
在@nrussell 的回答中添加一些实现细节...
使用源码,路克!肯定适用于这里,下面看Rcpp::runif
的实现 here:
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 ) ) ;
}
我们看到正在使用 stats::UnifGenerator
对象调用 NumericVector
的一个有趣的构造函数。 class 的定义是 here:
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;
}
} ;
因此,class 只是一个函子——它实现了 operator()
,因此 class 的对象可以是 'called'.
最后,关联的 NumericVector
构造函数是 here:
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
函数最终会调度 here:
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 也详细阐述了这一点.但是,我的理解:
runif
生成长度为 10 的 NumericVector
和 runif
个元素——将此临时右侧对象称为 tmp
、
x
被复制构造为与上述 tmp
. 相同
我相信编译器将能够省略复制构造,因此 x
实际上是直接从 runif(10)
的结果构造的,因此应该是高效的(至少,在任何情况下)合理的优化级别),但我可能是错的....
我正在研究针对特定问题的自定义 bootstrap 算法,因为我需要大量的重复,所以我很关心性能。对此,我对如何正确使用运行if有一些疑问。我知道我可以 运行 自己进行基准测试,但 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
}
这可能归结为 运行if 是否填充左侧或者是否分配并传递一个新的 NumericVector。
第二个问题:
如果两个版本都分配一个新向量,我可以通过在标量模式下一次生成一个随机数来改进吗?
如果您想知道,内存分配占用了我处理时间的相当大一部分。通过优化其他不必要的内存分配,我已经将 运行 时间减少了 30%,所以这很重要。
我设置了以下 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
所以,假设我解释/准确地表达了你的第二个问题,
If both versions allocate a new vector, can I improve things by generating one random number at a time in scalar mode?
使用我的 gen_runif()
成员函数,我想我们可以自信地说这不是最佳方法 - ~ 比其他两个函数慢 7.5 倍。
更重要的是,为了解决您的第一个问题,似乎仅初始化并将新的 NumericVector
分配给 Rcpp::runif(n)
的输出会更快一些。我当然不是 C++ 专家,但我相信第二种方法(分配给一个新的本地对象)比第一种更快,因为 copy elision。在第二种情况下,它 看起来 好像正在创建两个对象 - =
、v
左侧的对象和一个(临时?右值) ?) =
右侧的对象,这是 Rcpp::runif()
的结果。但实际上,编译器很可能会优化这个不必要的步骤 - 我认为我链接的文章中的这段话对此进行了解释:
When a nameless temporary, not bound to any references, would be moved or copied into an object of the same type ... the copy/move is omitted. When that temporary is constructed, it is constructed directly in the storage where it would otherwise be moved or copied to.
至少,我是这样解释结果的。希望更精通该语言的人可以确认/否认/纠正这个结论。
在@nrussell 的回答中添加一些实现细节...
使用源码,路克!肯定适用于这里,下面看Rcpp::runif
的实现 here:
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 ) ) ;
}
我们看到正在使用 stats::UnifGenerator
对象调用 NumericVector
的一个有趣的构造函数。 class 的定义是 here:
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;
}
} ;
因此,class 只是一个函子——它实现了 operator()
,因此 class 的对象可以是 'called'.
最后,关联的 NumericVector
构造函数是 here:
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
函数最终会调度 here:
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 也详细阐述了这一点.但是,我的理解:
runif
生成长度为 10 的NumericVector
和runif
个元素——将此临时右侧对象称为tmp
、x
被复制构造为与上述tmp
. 相同
我相信编译器将能够省略复制构造,因此 x
实际上是直接从 runif(10)
的结果构造的,因此应该是高效的(至少,在任何情况下)合理的优化级别),但我可能是错的....