- Boost - lists.preview.boost.org

[Random] Proposal: Faster RANLUX engines
by Christoph Conrads 10 Sep '19

10 Sep '19

Boost.Random and the C++11 standard library ship with a 24- and a 48-bit RANLUX pseudo-random number generator (PRNG). I propose to add 32- and 64-bit RANLUX PRNGs because they are at least 40% faster. Additionally, the 32-bit RANLUX PRNG can be implemented as follows: #include <boost/cstdint.hpp> #include <boost/random.hpp> namespace br = boost::random; typedef br::subtract_with_carry_engine<boost::uint32_t,32,3,17> ranlux32_base; typedef br::discard_block_engine<ranlux32_base, 389, 16> ranlux32; There is C++98 benchmark code at the end of this e-mail requiring only Boost and a C++ compiler. Below I will briefly discuss the theory behind RANLUX PRNGs, where the new generators are coming from, and why the 64-bit RANLUX PRNG requires (a few lines of) new code. Drawing from RANLUX PRNGs is a two-step process. In the first step a value is drawn from a "subtract-with-borrow" (SWB) generator implementing b-bit modular arithmetic [1]. Then, values are generously discarded yielding uniformly distributed values (uniform in a dynamical systems model) [2]. The RANLUX PRNGs using 24- and 48-bit arithmetic always gave me an itch so I looked into the motivation behind this. It turns out [3] that this restriction arose likely from a) computational limitations in the 1990s and b) Lüscher's interest in the generation of floating-point numbers (single-precision floating-point numbers have 24-bit significand). SWB PRNGs come in two flavors (Type I, Type II) and they make use of three parameters called base b, short lag s, and long lag r. Using modern prime factorization methods, one can quickly come up with the 32-bit PRNG above, a Type I SWB generator with b=2^32, r=17, and s=3. This one can be implemented as shown above. To generate 64-bit values, one should use a Type II SWB with b=2^64, r=62, and s=5 (all other 64-bit generators with b=2^64 and r < 100 will be awfully slow). What distinguishes the different types of SWBs is the recurrence for the computation of variates. For Type I it is x_n := (x_{n-s} - x_{n-r} + c_n) mod b, where c_n is a carry bit. For Type II it is x_n := (x_{n-r} - x_{n-s} + c_n) mod b. (Observe the order of long lang and short lag in these formulas.) Type II SWBs are not difficult to implement but it requires either a modification of `subtract_with_carry_engine` or a new class. Let me know what you think about this proposal. Christoph Conrads [1] G. Marsaglia, A. Zaman: "A New Class of Random Number Generators". 1991. URL: https://www.jstor.org/stable/2959748 [2] Martin Lüscher: "A Portable High-Quality Random Number Generator for Lattice Field Theory Simulations". 1994. URL: https://arxiv.org/abs/hep-lat/9309020 [3] Christoph Conrads: "Faster RANLUX Pseudo-Random Number Generators". 2019. URL: https://christoph-conrads.name/faster-ranlux-pseudo-random-number-generators // Build with: // c++ -Wextra -Wall -std=c++98 -pedantic benchmark.cpp -O3 \ // -march=native -DNDEBUG -lboost_chrono -lboost_system #include <boost/chrono.hpp> #include <boost/cstdint.hpp> #include <boost/random.hpp> #include <cassert> #include <cstdio> #include <limits> #include <string> namespace chrono = boost::chrono; typedef chrono::milliseconds milliseconds; typedef chrono::process_cpu_clock my_clock; namespace br = boost::random; typedef br::subtract_with_carry_engine<boost::uint32_t,32,3,17> ranlux32_base; typedef br::discard_block_engine<ranlux32_base, 389, 16> ranlux32; struct dummy_engine { typedef boost::uint32_t result_type; static result_type max() { return std::numeric_limits<result_type>::max(); } static result_type min() { return std::numeric_limits<result_type>::min(); } result_type operator() (); result_type state_; }; dummy_engine::result_type dummy_engine::operator() () { return state_++; } std::string get_name(const dummy_engine&) { return "dummy-prng"; } std::string get_name(const br::ranlux24&) { return "ranlux24"; } std::string get_name(const br::ranlux48&) { return "ranlux48"; } std::string get_name(const ranlux32&) { return "ranlux32";} template<typename Generator> typename Generator::result_type draw(Generator& gen) __attribute__((noinline)); template<typename Generator> typename Generator::result_type draw(Generator& gen) { return gen(); } template<typename Generator> void run(boost::uintmax_t num_draws) { assert(Generator::min() == 0); unsigned w = Generator::max() == std::numeric_limits<boost::uint64_t>::max()?8u: Generator::max() == (UINTMAX_C(1)<<48) - 1u ?6u: Generator::max() == std::numeric_limits<boost::uint32_t>::max()?4u: Generator::max() == (UINTMAX_C(1)<<24) - 1u ?3u: Generator::max() == std::numeric_limits<boost::uint16_t>::max()?2u: Generator::max() == std::numeric_limits<boost::uint8_t>::max() ?1u: 0u ; Generator gen; my_clock::time_point t_0 = my_clock::now(); for(uintmax_t i = 0; i < num_draws; ++i) draw(gen); my_clock::time_point t_1 = my_clock::now(); milliseconds t_ms = chrono::duration_cast<milliseconds>(t_1 - t_0); double bytes_per_sec = w * num_draws * 1000u/double(t_ms.count()); std::string name = get_name(gen); boost::uint16_t dummy = boost::uint16_t(gen()); std::printf( "%-26s | %10lu | %20.2e | %hu\n", name.c_str(), t_ms.count(), bytes_per_sec, dummy ); } int main() { boost::uintmax_t num_draws = UINTMAX_C(100000000); run<dummy_engine>(num_draws); run<br::ranlux24>(num_draws); run<ranlux32>(num_draws); run<br::ranlux48>(num_draws); }

1 0

Interest in circular span?
by Bjorn Reese 10 Sep '19

10 Sep '19

I am working on a circular queue library that contains a non-owning circular span, a fixed-sized circular array, and a dynamically resizable circular vector. Would you be interested in adding such a library to Boost? The design is inspired by Boost.CircularBuffer, std::span, and P0059R4 std::experimental::ring_span. The code can be found at: https://github.com/breese/trial.circular The documentation can be found at: https://github.com/breese/trial.circular/tree/develop/doc circular::span can be used to implement the P0059R4 ring_span, as shown in one of the example: https://github.com/breese/trial.circular/blob/develop/example/p0059/ring_sp… circular::span can also be used to implement most parts of boost::circular_buffer; all except insertions and erasure at arbitrary positions.

7 10

[Intrusive] Movable intrusive container elements?
by Phil Endecott 09 Sep '19

09 Sep '19

Dear Experts, Is it possible to make intrusive container elements movable? Here's the scenario. Say I have struct Thing { int id, string name }; and I want a container of those indexed by both the id and the name. Using Boost.Intrusive I can add two hooks to the struct and have two intrusive::sets, one using id as the key and the other using name. All good. But say my ids are a contiguous range of integers starting at zero. It would be much better to store the Things in a vector (or similar), indexed by the id, and use Intrusive only for the name index. Or if my ids are not contiguous, I might still prefer to keep the things in a vector sorted by id and do id lookup by binary search (i.e. a flat_set). In both cases, the issue is that when the vector expands or is sorted the elements are moved, and this will invalidate the pointers used for the name index. Is is possible to fix this using move constructors and move assignment for the hooks? I.e. those operations could adjust the pointers pointing to the element's old location to point to its new location. (This has some similarities to how auto-unlink hooks already fix pointers to remove the being-deleted item.) Maybe there is some complication that makes this impossible. Or maybe this is already possible?? Any thoughts anyone? Regards, Phil.

2 2

Requesting opinions on CECS (C/C++ Error Control) library for possible boost implementation.
by Terablade 08 Sep '19

08 Sep '19

Hi all. Recently I focused on completing and releasing a public a C/C++ library for C/C++ Error Control System. I've exposed the library to public via two articles in Linked In, and especially in the "C++ Developers Groups" were I got some positive feedback (a few comments and likes). A "Senior Architect at Apple" left the following comment: "Man that’s error traceability for a lot of readability". This made me wonder if this library deserves to be exposed more to C/C++ developers, and led me to think of boost library. Personally I'm testing the library by integrating it in different projects, and I'm quite happy from the outcome. With very few code (increased readability) and a specific design approach for capturing and handling possible errors, it does provide a lot of customized error traceability - a feature which for me is quite important on complex projects and especially when multiple libraries mix up and need integrated error tracking through all of them. Reading the boost guidelines I joined this mailing list to request review and opinions.As my free time is a a bit limited to convert and test the library to be supported by boost, I'd like some comments and review first.Do you believe that CECS could be a useful util for Boost? Should I go for it? The two articles in that group (requires membership) is at:https://www.linkedin.com/feed/update/urn:li:activity:6568218380594098176… articles are also in my profile:https://www.linkedin.com/pulse/cecs-cc-error-control-system-vasilei… I have also released the library on github:https://github.com/terablade2001/CECS I'd like to note that the library has been favored till now by 7 accounts in github (8 including me) which, for me, is also a positive feedback. Thanks for your time,V. Pothos

1 0

[GSOC19] Congrats to all students and mentors
by Damian Vicino 06 Sep '19

06 Sep '19

Hi, GSOC finished for 2019. We had 11 students this year and all of them survived the summer and contributed a lot of good stuff. Hopefully, most of it will be merged in the next few weeks. Thanks to all students and mentors, and to Boost community for supporting the program. Special thanks to David Bellot that worked as org admin and dealed with the logistics in addition to mentor. Cheers, Damian

2 1

[bimap] Maintaining library
by Edward Diener 04 Sep '19

04 Sep '19

Could someone please take a look at bimap in order to maintain the library. I have had a simple PR since last December, simply to remove executable permissions from some files, which has been ignored and no one appears to be maintaining the library.

1 0

boost::asio::deadline_timer and boost::asio::io_service
by JH 02 Sep '19

02 Sep '19

Hi, I use a single thread to run 3 classes using boost::asio::deadline_timer, the timers are managed by boost::asio::io_service. I deliberately use a single thread to avoid mutex, I believe those 3 timers are called exclusively by boost::asio::io_service in a single thread, there won't be race condition to share the objects among them, is it correct? Thank you. Kind regards, - jupiter

2 7

Re: [boost] A solution to return dynamic strings without heap allocation. Any interest?
by Bjorn Reese 01 Sep '19

01 Sep '19

On 8/29/19 3:24 PM, Roberto Hinz via Boost wrote: > auto result = csw.finish(); > if (result.truncated) { > // ... I suggest that you change the return type of finish() to contain the number of element written instead of the truncated boolean. This would make outbuf extensible to binary data as well where you cannot rely on a terminating zero to tell you how much data has been written. The return type could also have begin()/end() member functions, which makes it directly usable with STL algorithms. In that case it would also make sense to have data()/size().

2 3

Re: [boost] [Boost-users] License Issue with boost_intrusive
by Michael Caisse 27 Aug '19

27 Aug '19

Copying to dev ML. On 8/22/19 12:05, Gerald Wiltse via Boost-users wrote: > During an annual third-party audit of our source code, boost intrusive > was flagged as containing unlicensed code. Specifically, there are > several pieces of code in this file which are explicitly attributed to > external parties on external websites, which still exist and show no > license. > > https://github.com/boostorg/intrusive/blob/develop/include/boost/intrusive/… > > https://github.com/boostorg/intrusive/blob/develop/include/boost/intrusive/… > > > Original sources: > http://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-b… > http://www.flipcode.com/archives/Fast_log_Function.shtml > > I don't claim to be a license expert. I've read a lot over the years, > but this is the first time that I've actually been between an attorney > and a codebase having to figure out practical implications of a scenario > like this. > > I first want to make sure that Boost committee is aware of this situation. > > Second, I would like to know what the official conclusion would be from > the Boost Committee about the license implications in cases like these. > Maybe it has come up before and is well established. On the surface, the > implications seems ambiguous to me when: DEVELOPER_A takes unlicensed > code off the internet, prefixes it with a comment that says "Thanks to > DEVELOPER_B ", then prefixes the whole file with a file-level copyright > notice that says "COPYRIGHT DEVELOPER_A", and then says it's > distributed under BSL-1.0 license, and then the boost team > re-distributes the source code. > > Internally at my company, there was little discussion about it. There > is no room for ambiguity, so the directive from management was to delete > the file from our SCM system completely and ensure it never is included > in our products. VERY fortunately, deleting it doesn't seem to have > broken our builds. In future cases like this, that's really not what we > want to be doing with your OSS libraries for obvious reasons. So, I'd > like to know if there's any chance this situation changes in a future > version of Boost (I.E., the code be removed/re-written with clean-room > approach, etc). > > Regards, > Jerry > > Gerald R. Wiltse > jerrywiltse(a)gmail.com <mailto:jerrywiltse@gmail.com> > > > _______________________________________________ > Boost-users mailing list > Boost-users(a)lists.boost.org > https://lists.boost.org/mailman/listinfo.cgi/boost-users >

8 8

Set deadline_timer expired_at realtime clock 0 minute and repeat
by JH 27 Aug '19

27 Aug '19

Hi, How can I set deadline_timer expired at real clock absolute time at 0 minute, then repeat every minute? So it should expired at: 13:40:00, 13:41:00, 13:42:00 and so on? Thank you. Kind regards, - jupiter

2 7