- Boost - lists.boost.org

[random] Determining interest in Pseudo-Random Functions and Counter Based Random Number Generators
by John Salmon 03 Feb '12

03 Feb '12

I am co-author of "Parallel Random Numbers, as Easy as 1, 2, 3". which recently won the best paper award at the IEEE/ACM SC'11 conference. I'm also co-author of the related Random123 library: http://deshawresearch.com/resources_random123.html My colleagues and I would like to contribute a similar library to Boost as well. This isn't just a "port" of the Random123 library. Boost's focus on C++ allows for both simplification and clarification of the ideas in the paper and the original library. I've done a preliminary draft of some code that fits nicely into the existing Boost Random library. It's incomplete, but I think there's enough for folks to look at and gauge further interest. A zip file with a boost-like layout is here: http://thesalmons.org/john/random123/prf_boost/prf_boost.zip The README from the zip file is appended. I look forward to your comments and suggestions. John Salmon -------------- README ------------------- This extension of the Boost Random library adds "Pseudo-Random Functions" (PRFs) as an alternative to conventional "Uniform Random Number Generators" and "Random Number Engines". It is an incomplete draft, intended to start a conversation. It is not ready-to-use library. The case for using PRFs in Monte Carlo and statistical simulation is given in the paper, "Parallel Random Numbers -- As Easy as 1, 2, 3", by Salmon, Moraes, Dror & Shaw, in the Proceedings of SC'11: http://dl.acm.org/citation.cfm?doid=2063405 also available at http://www.thesalmons.org/john/random123/papers/random123sc11.pdf PRFs have been known for many years, but either their advantages were unrecognized or they were thought to have poor performance with respect to conventional URNGs. The paper shows that PRFs exist with excellent statistical properties, and highly desirable space and time characteristics. Also, note that the terminology in the paper, is slightly different from that used here. In the paper they're called "Counter Based Random Number Generators". PRFs are well-known in cryptography, but the PRFs here (except for AES) are *not* cryptographically strong. Nevertheless, they have satisfied extensive tests of statistical quality and should satisfy the needs of Monte Carlo simulation and other fields that routinely use random numbers. PRFs are pure functions (functors in C++) with the property that they return "random" values, even when presented with highly regular inputs (see the paper for a discussion of how randomness is empirically established). The user of a PRF assembles the input, calls the function and obtains a "random" result which can then be used in the same way as a value obtained from a conventional URNG or Engine. In contrast, a conventional Random Number Engine has a much more limited API: the caller is restricted to seeding the engine, once and for all, and then repeatedly asking for the "next" random value. PRFs eliminate the sequential dependence inherent in conventional RNGs. With a PRF, one can compute the "n-th" value in O(1) time, without stepping through earlier values. In fact, with a PRF, the notion of an "n-th" value loses its significance. One simply obtains a random value. Eliminating sequential dependence can be especially useful for parallel, multi-threaded applications. For example, one can assemble a PRF's input from application-level data, e.g., object id, voxel number, user-supplied seed value, timestep, iteration number, etc. This kind of application data is unchanged when the application is parallelized, and is generally invariant as more or fewer threads become available. The resulting random value is thus invariant to the parallelization as well. This can be enormously helpful when correctness dictates that separate "parallel" threads should use the same "random" value, or when trying to reproduce results on different platforms with different levels of parallelism. Four PRFs are implemented: threfry, philox, ars and aes, each implemented in its own header file, e.g., boost/random/ars.hpp. The file boost/random/counter_based_urng.hpp implements the counter_based_urng adapter class, which creates a Uniform Random Number Generator from a PRF, allowing programmers to use the PRF APIs together with Boost or C++1x Random Number Distributions. The file boost/random/counter_based_engine.hpp implements the counter_based_engine adapter class, which creates a Uniform Random Number Engine from a PRF, allowing PRFs to be used with software that relies on the Uniform Random Engine concept. For better or worse, wrapping a PRF in a counter_based_engine adapter completely obscures the PRF's API and reintroduces sequential dependence. The zip file also contains a copy of the candidate Boost Endian library copied from boost sandbox. Endian-swapping is required by the AES engine on bigendian machines, and the library meets our needs. Concepts -------- All PRFs have a domain_type and a range_type and with d a "permissible" object of the domain type, the expression: prf(d) is of the range_type. In many cases, every possible value of domain_type will be "permissible", but we leave open the possibility that the prf may place restrictions on the values of domain_type that produce "random" results. The values returned by the prf should be "random", a concept that is difficult to make both precise and achievable. Roughly, for most sequences, including highly "regular" sequences, of distinct, permissible domain_type values, d1, d2, d3, ..., the sequence: prf(d1), prf(d2), prf(d3), ... is statistically indistinguishable from a sequence of independent, uniformly distributed random variables sampling the range_type. In most cases, the output of the prf will uniformly sample all possible values of the range_type, but we leave open the possibility that it may only sample a subset and that the output is only uniform over the subset. Keyable PRFs have a key_type, a corresponding constructor, and setkey() and getkey() member functions. Keyable PRFs constructed with different keys must also be statistically independent. I.e., even for highly regular sequences of distinct (key, domain) pairs: (k1, d1), (k2,d2), ... the sequence: Prf(k1)(d1), Prf(k2)(d2), ... is statistically indistinguishable from a sequence of independent random uniformly distributed samples of the range_type Keyable PRFs may also be Seedable in which case they also have seed() member functions and corresponding constructors similar to those of Random Number Engines. Seeding a PRF is equivalent to setting its key to some value corresponding to the output of sseq.generate(). A PRF has a Countable Domain if its domain_type has member functions begin(), end(), and back() with semantics identical to that of boost::array<Uint, N> for some unsigned integral type Uint and some N. It must also have member functions domain_array_min() and domain_array_max() that specify the permissible domain values. Any array, da, whose members, da[i], satisfy: prf.domain_array_min() <= da[i] <= prf.domain_array_max[] must be "permissible". A PRF has an Integer Array Range if its range_type has member functions begin(), end(), and size() with semantics identical to boost::array<RangeInt, N>, for some integral type, RangeInt and constant N. It must also have static constexpr member functions, range_array_min() and range_array_max() that specify the subset of range values sampled by the PRF. For any sequence of permissible domain value, d1, d2, ..., the integers: prf(d1)[i], prf(d2)[i] must be statistically indistinguishable from independent uniformly distributed RangeInts from range_array_min() up to and including range_array_max(). If a PRF has a Countable Domain and an Integer Array Range, then: counter_based_urng<Prf> satisfies the requirements of a Uniform Random Number Generator. If, in addition, the PRF is Seedable, Streamable and Equality Comparable, then: counter_based_engine<Prf> satisfies the requirements of a Random Number Engine. A PRF is a Pseudo-Random Bijection if it is one-to-one and onto. I.e., if it has an inverse. It is not necessary for the inverse to have a practical implementation. It is sufficient that the inverse exist mathematically. A PRF is a Pseudo-Random Permutation if it is a Bijection and its domain_type is the same as its range_type. The four implemented PRFs are CopyAssignable, EqualityComparable, Streamable, Keyable, Seedable, Pseudo-Random Permutations with Integer Array ranges and Countable domains. Hence, they satisfy the requirements of counter_based_engine and counter_based_urng. Differences from Random123 -------------------------- This code is inspired by the Random123 library, but there are significant differences. New terminology: threefry<2, uint64_t> is a "Pseudo-Random Function" (PRF). PRFs take a key_type as a constructor argument, and are bijections on their ctr_type. Thus, instead of: typedef r123::Threefry2x64 r123_t; r123_t::ctr_type c; r123_t::key_type k r123_t::ctr_type r = r123_t(c, k) You now say: typedef boost::random::threefry<2, uint64_t> prf_t; prf_t::key_type k; prf_t myprf(k); prf_t::domain_type c; prf_t::range_type r = myprf(c); // Or alternatively, (more reminiscent of Random123) prf_t::range_type r2 = prf_t(k)(c); AESNI ----- Use of AESNI is tricky because we want both compile-time and runtime control over whether AESNI is used. The compile-time control is determined by BOOST_HAS_AESNI, which we assume will be set by some config file based on compiler-specific symbols (__AES__, __x86_64__, __ICC, __GNUC__) and possible user-overrides. But even if AESNI support is compiled in, we have to detect it and fall back to a software implementation at runtime if it's not available. The check requires either an asm with GCC-compatible compilers or an intrinsic with MSVC-compatible compilers. Endianness is another complication. The AESNI implementation only works on x86_64 platforms, so it is not endian-sensitive. In fact, it *defines* how multi-byte quantities are to be interpreted. In contrast, the software implementation has to be endian-aware. The current implementation has not been tested with other endians, and hence is almost certainly broken. And finally, the AESNI intrinsics are *very* fast. We don't want to weigh them down with lots of runtime checks. With AESNI enabled, the runtime overhead should cost no more than a single conditional at the top of operator()(c). The choice between hardware and software AES is controlled by a member data field, useAESNI, of the prf class. If hw AES is compiled in, useAESNI is initialized by a runtime check of the CPU capabilities. It can be changed with a mutator method. If hw AES is not compiled in, useAESNI is initialized false and it is an error to try to set it to true. In detail/aes_impl.hpp, we implement two classes: detail::hw128 detail::sw128 with a common interface that minimally meets the needs of AES and ARS. The interface includes +=, ^= constructors from array<uintW, N>, aesenc, and aeskeygenassist primitives, etc. The crucial functions in AES and ARS are then written with a template parameter that is assumed to provide the interface. An idiom like: #if BOOST_HAS_AESNI if( useAESNI ) method<detail::hw128>(args); else #endif method<detail::sw128>(args); gives the desired compile-time and runtime control.

7 10

Use macro varargs within BOOST_NOEXCEPT_IF
by Daryle Walker 03 Feb '12

03 Feb '12

I was going to ask about adding a BOOST_NOEXCEPT, but I just checked that the trunk already has it: //---#ifdef BOOST_NO_NOEXCEPT# define BOOST_NOEXCEPT# define BOOST_NOEXCEPT_IF(Predicate)# define BOOST_NOEXCEPT_EXPR(Expression) false#else# define BOOST_NOEXCEPT noexcept# define BOOST_NOEXCEPT_IF(Predicate) noexcept((Predicate))# define BOOST_NOEXCEPT_EXPR(Expression) noexcept((Expression))#endif//--- If the compiler supports varargs in macros, should we have: //===# define BOOST_NOEXCEPT_IF(...) noexcept(__VA_ARGS__)# define BOOST_NOEXCEPT_EXPR(...) noexcept(__VA_ARGS__)//=== (I think that's the right syntax.) instead so comma expressions can be used within a noexcept without the extra parentheses? But I doubt that it makes a difference here, since anything within the noexcept must be interpretable as a single expression. (I think it does for decltype, though. Extra parentheses turn a value type into a reference type(?).) Daryle W.

1 0

[metagraph]
by Kitten, Nicholas 03 Feb '12

03 Feb '12

Hi Gordon (and whoever else is involved), What's the current status of metagraph / mpl_graph? I've been using msm::mpl_graph for error-checking/scheduling in a compile-time filter graph framework (similar to state machines, but focus is on data flow), and I'd certainly like to see more. As is, I've already implemented a topological sort based on the BFS which doesn't yield errors on cyclic graphs (which I'd be happy to contribute if you don't already have one), and I have some thoughts on improvement. I saw the BoostCon slides and the current state of the sandbox, and I was wondering if there's more code lurking out there somewhere, unchecked-in. Anyway, the single biggest flaw I see with the current BFS and DFS (and the BGL models they're based on) is that there is no way for the user to specify a termination condition in the base algorithm. It seems silly that an algorithm called "Search" can't end without traversing the whole connected component! Indeed, if there were simply an optional predicate determining whether a candidate vertex should be added to the stack/queue, I wouldn't have needed to write a separate algorithm for topo sort. The other thing is that not all of the listed visitor operations are called in the current implementations. Adding things like "initialize_vertex" and "non_tree_edge" to BFS is an easy fix. Thanks, Nick Kitten Software Engineer Center for Video Understanding Excellence ObjectVideo, Inc. http://www.objectvideo.com

3 6

[range] Performance benchmarks?
by Beman Dawes 02 Feb '12

02 Feb '12

A question came up in a long bikeshed discussion on a C++ committee mailing list as to the performance of range based interface versus a begin/end iterator interface (I.E. traditional STL interface) to the same algorithms. Out of curiosity, I checked the Boost.Range docs, but didn't see any performance measurements. It might encourage potential users to take the leap if the Boost.Range "Introduction" page made some mention of performance implications for use of the Boost library. The intro gives a "Push the even values from a map in reverse order into the container target" example: // Assume that is_even is a predicate that has been implemented elsewhere... push_back(target, my_map | map_values | filtered(is_even()) | reversed); Are there any benchmarks available for this? What does the straight STL version of the code look like? --Beman

5 8

[1.49] No description about Boost.Heap in Library Documentation page
by Michel Morin 02 Feb '12

02 Feb '12

There is no description about Boost.Heap at http://www.boost.org/doc/libs/1_49_0_beta1/ Ditto for "trunk/boost/libs/libraries.htm" Regards, Michel

3 3

[1.49.0] New libraries in 1.49.0?
by Beman Dawes 02 Feb '12

02 Feb '12

What are the new libraries in 1.49.0? --Thanks, --Beman

5 8

[interprocess] utf8 file names in memory mapped files
by Thorsten Ottosen 01 Feb '12

01 Feb '12

Hi Ion, It would be great if we could support utf8 encoded file names on windows too. I guess all it requires is a utility function that converts from utf8 to utf16 on windows. Such a function is avaiable in the windows API, and I can supply it. kind regards Thorsten

3 6

[1.49.0] Beta 1 release candidates available
by Beman Dawes 01 Feb '12

01 Feb '12

Release candidate files for 1.49.0 beta 1 are available at http://boost.cowic.de/rc/ As always, the release managers would appreciate it if you download the candidate of your choice and give building it a try. Please report both success and failure, and anything else that is noteworthy. This helps ensure the candidates build OK before we push them out to SourceForge. Thanks, --The release managers --PS: I downloaded the 7z version, and it build without errors on Win7/VC++ Express 2010 sp1

19 32

[1.49.0] Branches/release open for bug fixes and documentation updates
by Beman Dawes 01 Feb '12

01 Feb '12

branches/release is now open for bug fixes and doc updates, without need to ask for a release manager's permission. It will remain open until Monday, February 13th. The final release is scheduled for February 20th. The hope is that this somewhat longer beta period will allow time to fix more bugs that surface during the beta period. --Beman

4 4

[local_function] ready
by Lorenzo Caminiti 01 Feb '12

01 Feb '12

Hello all, I have finished making the modifications requested by the Boost.Local(Function) review. The code is now in the sandbox ready to be moved into trunk. Can I get write access to the trunk? 1) Boost.LocalFunction New: This library allows to program functions locally, directly within the scope where they are needed. https://svn.boost.org/svn/boost/sandbox/local_function/libs/local_function/… 2) Boost.ScopeExit Improved APIs (variadic macros, this_, void, and C++11 closures) while keeping full backward compatibility. https://svn.boost.org/svn/boost/sandbox/local_function/libs/scope_exit/doc/… 3) Boost.Utility/IdentityType New: Macro to wrap type expressions within round parenthesis so they can be passed to macros even when they contain commas. https://svn.boost.org/svn/boost/sandbox/local_function/libs/utility/identit… 4) Boost.Functional/OverloadedFunction New: Overload different functions into a single function object. https://svn.boost.org/svn/boost/sandbox/local_function/libs/functional/over… All source files: https://svn.boost.org/svn/boost/sandbox/local_function/ Thanks. --Lorenzo

2 1