3 times faster Mersenne Twister in GCC

Правка en2, от oToToT, 2022-10-28 22:33:02

TL; DR: #include <ext/random> and use __gnu_cxx::sfmt19937 just as std::mt19937.

Hi all,

I'm here to share a thing that seems not that well-known in the whole community.

There is a SIMD-oriented Fast Mersenne Twister (SFMT) implementation in GCC's library.
As its name suggested, it's a faster MT-like PRNG implementation based on SIMD.
SFMT is not exactly MT, but it shares some similarities and is much faster than the traditional MT.
If you are interested in more details about it, you could check this paper.

I test the two codes below in the Codeforces' custom test using GNU G++20 11.2.0 (64 bit, winlibs).
The result looks good.

sfmt19937 (998 ms)
mt19937 (3416 ms)

p.s. there's also __gnu_cxx::sfmt19937_64 if you want a 64-bit PRNG.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский oToToT 2022-10-28 22:33:41 0 (published)
en2 Английский oToToT 2022-10-28 22:33:02 724
en1 Английский oToToT 2022-10-28 22:11:56 1050 Initial revision (saved to drafts)