{"id":1783,"date":"2018-05-26T02:49:46","date_gmt":"2018-05-25T16:49:46","guid":{"rendered":"http:\/\/brnz.org\/hbr\/?p=1783"},"modified":"2018-05-26T16:39:07","modified_gmt":"2018-05-26T06:39:07","slug":"modern-c-randomness","status":"publish","type":"post","link":"https:\/\/brnz.org\/hbr\/?p=1783","title":{"rendered":"Modern C++ Randomness"},"content":{"rendered":"<p>This thread happened&#8230;<\/p>\n<blockquote class=\"twitter-tweet\" data-lang=\"en\">\n<p dir=\"ltr\" lang=\"en\">Choose:<\/p>\n<p>\u2014 Elan Ruskin (@despair) <a href=\"https:\/\/twitter.com\/despair\/status\/999455422078533632?ref_src=twsrc%5Etfw\">May 24, 2018<\/a><\/p><\/blockquote>\n<p><script async src=\"https:\/\/platform.twitter.com\/widgets.js\" charset=\"utf-8\"><\/script><\/p>\n<blockquote class=\"twitter-tweet\" data-conversation=\"none\" data-lang=\"en\">\n<p dir=\"ltr\" lang=\"en\">What is the type of x?<\/p>\n<p>\u2014 Jonathan Adamczewski (@twoscomplement) <a href=\"https:\/\/twitter.com\/twoscomplement\/status\/999470205892935680?ref_src=twsrc%5Etfw\">May 24, 2018<\/a><\/p><\/blockquote>\n<p><script async src=\"https:\/\/platform.twitter.com\/widgets.js\" charset=\"utf-8\"><\/script><\/p>\n<blockquote class=\"twitter-tweet\" data-conversation=\"none\" data-lang=\"en\">\n<p dir=\"ltr\" lang=\"en\">std::optional&lt;std::any&gt;<\/p>\n<p>\u2014 Andreas Fredriksson (@deplinenoise) <a href=\"https:\/\/twitter.com\/deplinenoise\/status\/999473697181257733?ref_src=twsrc%5Etfw\">May 24, 2018<\/a><\/p><\/blockquote>\n<p><script async src=\"https:\/\/platform.twitter.com\/widgets.js\" charset=\"utf-8\"><\/script><\/p>\n<blockquote class=\"twitter-tweet\" data-conversation=\"none\" data-lang=\"en\">\n<p dir=\"ltr\" lang=\"en\">I&#8217;ll see your C++17, and raise you C89:<a href=\"https:\/\/twitter.com\/hashtag\/define?src=hash&amp;ref_src=twsrc%5Etfw\">#define<\/a> x rand()<\/p>\n<p>\u2014 Jonathan Adamczewski (@twoscomplement) <a href=\"https:\/\/twitter.com\/twoscomplement\/status\/999498135868080131?ref_src=twsrc%5Etfw\">May 24, 2018<\/a><\/p><\/blockquote>\n<p><script async src=\"https:\/\/platform.twitter.com\/widgets.js\" charset=\"utf-8\"><\/script><\/p>\n<blockquote class=\"twitter-tweet\" data-conversation=\"none\" data-lang=\"en\">\n<p dir=\"ltr\" lang=\"en\">auto x = []() { return rand(); }<\/p>\n<p>\u2014 Andreas Fredriksson (@deplinenoise) <a href=\"https:\/\/twitter.com\/deplinenoise\/status\/999774861416280066?ref_src=twsrc%5Etfw\">May 24, 2018<\/a><\/p><\/blockquote>\n<p><script async src=\"https:\/\/platform.twitter.com\/widgets.js\" charset=\"utf-8\"><\/script><\/p>\n<blockquote class=\"twitter-tweet\" data-conversation=\"none\" data-lang=\"en\">\n<p dir=\"ltr\" lang=\"en\">tsk tsk&#8230; that&#8217;s not mordern enough: auto x = []() { std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution&lt;&gt; dis(0, 32767); return dis(gen); } &lt;&#8212; FIXED IT FOR YOU!<\/p>\n<p>\u2014 Bobby Anguelov (@BobbyAnguelov) <a href=\"https:\/\/twitter.com\/BobbyAnguelov\/status\/999776095389052931?ref_src=twsrc%5Etfw\">May 24, 2018<\/a><\/p><\/blockquote>\n<p><script async src=\"https:\/\/platform.twitter.com\/widgets.js\" charset=\"utf-8\"><\/script><\/p>\n<blockquote class=\"twitter-tweet\" data-conversation=\"none\" data-lang=\"en\">\n<p dir=\"ltr\" lang=\"en\">So, rand() assembles to &#8216;jmp rand&#8217;. That abomination on the other hand.. My eyes! <a href=\"https:\/\/t.co\/ujNkLrzavs\">https:\/\/t.co\/ujNkLrzavs<\/a><\/p>\n<p>\u2014 Andreas Fredriksson (@deplinenoise) <a href=\"https:\/\/twitter.com\/deplinenoise\/status\/999794353890447360?ref_src=twsrc%5Etfw\">May 24, 2018<\/a><\/p><\/blockquote>\n<p><script async src=\"https:\/\/platform.twitter.com\/widgets.js\" charset=\"utf-8\"><\/script><\/p>\n<p>So I did a little digging to satisfy my own curiosity about the &#8220;modern C++&#8221; version, and have learned a few things that I didn&#8217;t know previously&#8230;<\/p>\n<p>(this is a manual unrolled twitter thread that starts <a href=\"https:\/\/twitter.com\/twoscomplement\/status\/999917287564963840\">here<\/a>, with slight modifications)<\/p>\n<p>Nearly all of this I gleaned from the invaluable <a class=\"twitter-timeline-link\" dir=\"ltr\" title=\"http:\/\/cppreference.com\" href=\"https:\/\/t.co\/1w6eVNCFEY\" target=\"_blank\" rel=\"nofollow noopener\" data-expanded-url=\"http:\/\/cppreference.com\"><span class=\"invisible\">http:\/\/<\/span><span class=\"js-display-url\">cppreference.com<\/span><span class=\"tco-ellipsis\"><span class=\"invisible\">\u00a0<\/span><\/span><\/a> and <a class=\"twitter-timeline-link\" dir=\"ltr\" title=\"http:\/\/godbolt.org\" href=\"https:\/\/t.co\/sReG1pcECt\" target=\"_blank\" rel=\"nofollow noopener\" data-expanded-url=\"http:\/\/godbolt.org\"><span class=\"invisible\">http:\/\/<\/span><span class=\"js-display-url\">godbolt.org<\/span><span class=\"tco-ellipsis\"><span class=\"invisible\">\u00a0<\/span><\/span><\/a>. Comments about implementation refer specifically to the gcc-8.1 C++ standard library, examined using Compiler Explorer and the <span style=\"font-family: 'andale mono', monospace;\">-E<\/span> command line option.<\/p>\n<p><span style=\"font-family: 'andale mono', monospace;\">std::random_device<\/span> is a platform-specific source of entropy.<\/p>\n<p><span style=\"font-family: 'andale mono', monospace;\">std: mt19937<\/span> is a parameterized typedef of <span style=\"font-family: 'andale mono', monospace;\">std::mersenne_twister_engine<\/span><\/p>\n<p>specifically:<br \/>\n<span style=\"font-family: 'andale mono', monospace;\">std::mersenne_twister_engine&lt;uint_fast32_t, 32, 624, 397, 31, 0x9908b0df, 11, 0xffffffff, 7, 0x9d2c5680, 15, 0xefc60000, 18, 1812433253&gt;<\/span><br \/>\n(What do those number mean? I don&#8217;t know.)<\/p>\n<p>And <span style=\"font-family: 'andale mono', monospace;\">std::uniform_int_distribution<\/span> produces uniformly distributed random numbers over a specified range, from a provided generator.<\/p>\n<p>The default constructor for <span style=\"font-family: 'andale mono', monospace;\">std::random_device<\/span> takes an implementation-defined argument, with a default value.<\/p>\n<p>The meaning of the argument is implementation-defined &#8211; but the type is not:\u00a0<span style=\"font-family: 'andale mono', monospace;\">std::string<\/span>. (I&#8217;m not sure why a dynamically modifiable string object was the right choice to be the configuration parameter for an entropy generator.)<\/p>\n<p>There are out-of-line private functions for much of this implementation of <span style=\"font-family: 'andale mono', monospace;\">std::random_device<\/span>. The constructor that calls the out-of-line init function is itself inline &#8211; so the construction and destruction of the default <span style=\"font-family: 'andale mono', monospace;\">std::string<\/span> param is also generated inline.<\/p>\n<p>Also, peeking inside <span style=\"font-family: 'andale mono', monospace;\">std::random_generator<\/span>, there is a union with two members:<\/p>\n<p><span style=\"font-family: 'andale mono', monospace;\">void* _M_file<\/span>, which I guess would be used to store a file handle for \/dev\/urandom or similar.<\/p>\n<p><span style=\"font-family: 'andale mono', monospace;\">std::mt19937 _M_mt<\/span>, which is a &#8230; parameterized <span style=\"font-family: 'andale mono', monospace;\">std::mersenne_twister_engine<\/span> object.<\/p>\n<p>So it seems reasonable to me that if you can&#8217;t get entropy* from outside your program, generate your own approximation. It looks like it is possible that the entropy for the <span style=\"font-family: 'andale mono', monospace;\">std::mersenne_twister_engine<\/span> will be provided by a <span style=\"font-family: 'andale mono', monospace;\">std::mersenne_twister_engine<\/span>.<\/p>\n<p>Unlike <span style=\"font-family: 'andale mono', monospace;\">std::random_device<\/span>, which has its implementation out of line, <span style=\"font-family: 'andale mono', monospace;\">std::mersenne_twister_engine<\/span>&#8216;s implementation seems to be all inline. It is unclear what benefits this brings, but it results in a few hundred additional instructions generated.<\/p>\n<p>And then there&#8217;s <span style=\"font-family: 'andale mono', monospace;\">std::uniform_int_distribution<\/span>, which seems mostly unsurprising. It is again fully inline, which (from a cursory eyeballing) may allow a sufficiently insightful compiler to avoid a couple of branches and function calls.<\/p>\n<p>The code that got me started on this was presented in jest &#8211; but (<span style=\"font-family: 'andale mono', monospace;\">std::random_device<\/span> + <span style=\"font-family: 'andale mono', monospace;\">std::mt19937<\/span> + <span style=\"font-family: 'andale mono', monospace;\">std::uniform_int_distribution<\/span>) is a commonly recommended pattern for generating random numbers using these modern C++ library features.<\/p>\n<p>My takeaways:<br \/>\n<span style=\"font-family: 'andale mono', monospace;\">std::random_device<\/span> is potentially very expensive to use &#8211; and doesn&#8217;t provide strong cross-platform guarantees about the randomness it provides. It is configured with an <span style=\"font-family: 'andale mono', monospace;\">std::string<\/span> &#8211; the meaning of which is platform dependent. I am not compelled to use this type.<\/p>\n<p><span style=\"font-family: 'andale mono', monospace;\">std::mt19937<\/span> adds a sizeable chunk of codegen via its inline implementation &#8211; and there are better options than Mersenne Twister.<\/p>\n<p>Bottom line: I&#8217;m probably going to stick with <span style=\"font-family: 'andale mono', monospace;\">rand()<\/span>, and if I need something a little fancier, <a class=\"twitter-timeline-link\" dir=\"ltr\" title=\"http:\/\/www.pcg-random.org\/\" href=\"https:\/\/t.co\/0l9ePQ8rWX\" target=\"_blank\" rel=\"nofollow noopener\" data-expanded-url=\"http:\/\/www.pcg-random.org\/\"><span class=\"invisible\">http:\/\/www.<\/span><span class=\"js-display-url\">pcg-random.org<\/span><span class=\"invisible\">\/<\/span><\/a>\u00a0or one of the other suggestions provided as replies to the twitter thread.<\/p>\n<p>Addition: <a href=\"https:\/\/gist.github.com\/twoscomplement\/de1c21324ba84704086eb37995582d46\">the code I was able to gather, representing some relevant parts<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>This thread happened&#8230; Choose: \u2014 Elan Ruskin (@despair) May 24, 2018 What is the type of x? \u2014 Jonathan Adamczewski (@twoscomplement) May 24, 2018 std::optional&lt;std::any&gt; \u2014 Andreas Fredriksson (@deplinenoise) May 24, 2018 I&#8217;ll see your C++17, and raise you C89:#define x rand() \u2014 Jonathan Adamczewski (@twoscomplement) May 24, 2018 auto x = []() { return &hellip; <a href=\"https:\/\/brnz.org\/hbr\/?p=1783\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Modern C++ Randomness&#8221;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[5,26],"tags":[],"_links":{"self":[{"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=\/wp\/v2\/posts\/1783"}],"collection":[{"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1783"}],"version-history":[{"count":31,"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=\/wp\/v2\/posts\/1783\/revisions"}],"predecessor-version":[{"id":1814,"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=\/wp\/v2\/posts\/1783\/revisions\/1814"}],"wp:attachment":[{"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1783"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1783"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1783"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}