Почему Мерсенн твистер быстрее, чем линейный конгруэнтный генератор?
Я тестировал с помощью стандартной библиотеки gcc С++ Mersenne twister. Он превосходит как линейный конгруэнтный генератор, так и C rand, что, скорее всего, является LCG. Документация по ускорению также, похоже, дает аналогичный результат, но в большей степени поддерживает Mersenne twister. Кто-нибудь может это объяснить?
#include <cstdlib>
#include <iostream>
#include <chrono>
#include <random>
class Timer
{
private:
std::chrono::high_resolution_clock::time_point start_time;
std::chrono::high_resolution_clock::time_point stop_time;
public:
void start()
{
start_time = std::chrono::high_resolution_clock::now();
}
void stop()
{
stop_time = std::chrono::high_resolution_clock::now();
}
double measure()
{
using namespace std::chrono;
return duration_cast<microseconds>
(stop_time - start_time).count() / 1000000.0;
}
};
template<typename T>
class Random
{
private:
T generator;
public:
Random()
: generator
(std::chrono::high_resolution_clock::now().time_since_epoch().count())
{
}
int generate_integer(int begin, int end)
{
return std::uniform_int_distribution<int>(begin, end - 1)(generator);
}
};
int main()
{
constexpr int n = 300000000;
Random<std::minstd_rand> mr;
Random<std::mt19937> mt;
Timer t;
for (int j = 0; j < 3; ++j)
{
t.start();
for (int i = 0; i < n; ++i)
{
static_cast<volatile void>(mr.generate_integer(0, 10));
}
t.stop();
std::cout << "minstd " << t.measure() << std::endl;
t.start();
for (int i = 0; i < n; ++i)
{
static_cast<volatile void>(mt.generate_integer(0, 10));
}
t.stop();
std::cout << "mersenne " << t.measure() << std::endl;
t.start();
for (int i = 0; i < n; ++i)
{
static_cast<volatile void>(std::rand() % 10);
}
t.stop();
std::cout << "rand " << t.measure() << std::endl;
}
}
результат
minstd 4.70876
mersenne 1.55853
rand 4.11873
minstd 4.53199
mersenne 1.55928
rand 4.15159
minstd 4.5374
mersenne 1.55667
rand 4.13715
Ответы
Ответ 1
Алгоритм Mersenne Twister не такой сложный, как кажется. Или, точнее, почти вся сложная часть выполняется недостаточно часто, чтобы серьезно повлиять на среднюю среднюю скорость.
Если вы посмотрите на реализацию псевдокода в Википедии, подавляющее большинство вызовов выполняют только вторую половину функции extract_number(); остальная часть кода без инициализации (в основном в функции twist()) работает только в одном вызове в 625 (в наиболее распространенной версии). Часть, которая запускается каждый раз, очень проста, всего лишь несколько смен и другие побитовые операции, которые можно ожидать очень быстро на большинстве процессоров. Тест в начале extract_number() почти всегда является ложным и поэтому может быть легко оптимизирован с помощью предсказания ветвления.
Сравните это с линейным конгруэнтным алгоритмом, в котором каждый вызов выполняет целочисленное умножение (дорогое) и модульное деление (очень дорогое, если вы не обманываете, используя силу 2 модуля, что влияет на качество ваших случайных чисел). Арифметика, участвующая в алгоритмах LC и MT, настолько отличается, что меня не удивляет, если их относительная производительность варьируется от одной системы к другой, но я не испытываю никаких проблем с тем, что MT работает быстрее, по крайней мере, в некоторых случаях.
(Если вы внимательно посмотрите на алгоритм MT, на первый взгляд появляется несколько операций по модулю для каждой итерации в twist(), но они находятся в формах, которые легко оптимизировать.)
Что касается простого старого rand(), его реализация сильно варьируется и не должна быть последовательной в разных системах. Многие реализации используют 16-разрядную арифметику и, естественно, будут быстрее, чем 32 или 64-битные алгоритмы.
Ответ 2
Вероятно, это потому, что rand обращается к локальному хранилищу потоков для извлечения его состояния.
Я попробовал это с помощью сообщества Visual Studio 2015 и получил результаты, похожие на OP. Рассматривая источник для rand, предоставляемый компилятором VS2012, rand() обращается к локальному хранилищу потоков, чтобы получить предыдущее значение, которое затем передается по математике LCRG для генерации следующего.
Использование моей собственной версии rand без локального доступа к хранилищу дает мне время быстрее - примерно 0,25 по шкале OP.
Ответ 3
Я не могу воспроизвести ваши результаты, когда я попробую, rand появляется намного быстрее
[email protected] ~/cpp/test5 $ g++ -std=c++11 main.cpp -o main
[email protected] ~/cpp/test5 $ ./main
minstd 18.168
mersenne 20.7626
rand 3.13027
minstd 17.8153
mersenne 20.8395
rand 3.19297
minstd 18.0667
mersenne 20.7672
rand 3.13617
Изменить: когда я делаю это с -O3, rand все еще быстрее
[email protected] ~/cpp/test5 $ g++ -std=c++11 -O3 main.cpp -o main
[email protected] ~/cpp/test5 $ ./main
minstd 7.74432
mersenne 8.54915
rand 3.04077
minstd 7.73824
mersenne 8.5711
rand 3.03335
minstd 7.74818
mersenne 8.55403
rand 3.03481
Я думаю, что это, вероятно, зависит от ОС/компилятора/конфигурации?
Может быть, в Windows, вызов std:: rand() неявно должен извлечь время из ОС или что-то, чтобы засеять его, или что-то вроде этого? (Редактирование: я не уверен, что я понимаю результаты повышения, хотя, и я сомневаюсь, что результаты повышения будут отражать такую проблему)
Моя ОС и компилятор:
[email protected] ~/cpp/test5 $ cat /etc/issue
Linux Mint 17.1 Rebecca \n \l
[email protected] ~/cpp/test5 $ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.8/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 4.8.4-2ubuntu1~14.04' --with-bugurl=file:///usr/share/doc/gcc-4.8/README.Bugs --enable-languages=c,c++,java,go,d,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.8 --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.8 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --disable-libmudflap --enable-plugin --with-system-zlib --disable-browser-plugin --enable-java-awt=gtk --enable-gtk-cairo --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-4.8-amd64/jre --enable-java-home --with-jvm-root-dir=/usr/lib/jvm/java-1.5.0-gcj-4.8-amd64 --with-jvm-jar-dir=/usr/lib/jvm-exports/java-1.5.0-gcj-4.8-amd64 --with-arch-directory=amd64 --with-ecj-jar=/usr/share/java/eclipse-ecj.jar --enable-objc-gc --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.8.4 (Ubuntu 4.8.4-2ubuntu1~14.04)
Изменить: я сделал это снова с помощью "-fwhole-program", не сильно изменился:
[email protected] ~/cpp/test5 $ g++ -std=c++11 -fwhole-program -O3 main.cpp -o main
[email protected] ~/cpp/test5 $ ./main
minstd 8.15607
mersenne 8.03688
rand 2.9622
minstd 8.17983
mersenne 7.99626
rand 2.90655
minstd 8.16007
mersenne 7.99331
rand 2.90902
