- Boost - lists.boost.org

[Multiprecision] Benchmarking
by Phil Endecott 15 Jun '12

15 Jun '12

Dear All, I have attempted to evaluate the proposed multiprecision library by applying it to the "Dealaunay Flip" function for 32-bit integer coordinates, as this is one of the few things that I've ever implemented that needed more than 64-bit integers: inline bool delaunay_test(int32_t ax, int32_t ay, int32_t bx, int32_t by, int32_t cx, int32_t cy, int32_t dx, int32_t dy) { // Test whether the quadrilateral ABCD's diagonal AC should be flipped to BD. // This is the Cline & Renka method. // Flip if the sum of the angles ABC and CDA is greater than 180 degrees. // Equivalently, flip if sin(ABC + CDA) < 0. // Trig identity: cos(ABC) * sin(CDA) + sin(ABC) * cos(CDA) < 0 // We can use scalar and vector products to find sin and cos, and simplify // to the following code. // Numerical robustness is important. This code addresses it by performing // exact calculations with large integer types. i64 ax64 = ax, ay64 = ay, bx64 = bx, by64 = by, cx64 = cx, cy64 = cy, dx64 = dx, dy64 = dy; i64 cos_abc = (ax64-bx64)*(cx64-bx64) + (ay64-by64)*(cy64-by64); i64 cos_cda = (cx64-dx64)*(ax64-dx64) + (cy64-dy64)*(ay64-dy64); if (cos_abc >= 0 && cos_cda >= 0) return false; if (cos_abc < 0 && cos_cda < 0) return true; i64 sin_abc = (ax64-bx64)*(cy64-by64) - (cx64-bx64)*(ay64-by64); i64 sin_cda = (cx64-dx64)*(ay64-dy64) - (ax64-dx64)*(cy64-dy64); i128 sin_sum = static_cast<i128>(sin_abc)*cos_cda + static_cast<i128>(cos_abc)*sin_cda; return sin_sum < 0; } As you can see, with 32-bit inputs, the first set of computations yield 64-bit results and about half of calls terminate at this stage. Otherwise a calculation yielding a 128-bit result is carried out. In practice, the results of the subtractions are typically small and the 128-bit value rarely has more than 64 significant bits. I have compared the following types used for i64 and i128 in the code above: (1) int64_t and int64_t (which gives WRONG ANSWERS, but is useful for comparison) (2) int64_t and my own "quick and dirty" int128_t. (3) cpp_int. (4) int64_t and cpp_int. (5) cpp_int without expression templates. (6) int64_t and cpp_int without expression templates. (7) int64_t and mp_int128_t. (8) mpz_int. (9) int64_t and mpz_int. Mean times per function call are as follows: (1) 39.3 ns (2) 61.9 ns (3) 513 ns (4) 103 ns (5) 446 ns (6) 102 ns (7) 102 ns (8) 2500 ns (9) 680 ns (AMD Athlon(tm) II X2 250e Processor @ 3 GHz; g++ 4.6.1.) Note that: - GMP is slowest, despite oft-repeated claims about its good performance. - Expression templates make the code slower. - Even the fastest Boost.Multiprecision type, mp_int128_t, is significantly slower than my own quick hack. This is all a bit disappointing. Perhaps the problem is that I'm dealing only with 128 bits and the intended application is for much larger values? I am reminded of my experience with xint last year. See e.g. this thread: http://thread.gmane.org/gmane.comp.lib.boost.devel/215565 The current proposal seems much better - xint was hundreds of times slower than my ad-hoc code - but I still find it discouraging. I suspect that the performance difference may be attributable to the use of sign-magnitude representation; as a result, the implementation is full of sign-testing like this: template <unsigned MinBits, bool Signed, class Allocator> inline void eval_subtract(cpp_int_backend<MinBits, Signed, Allocator>& result, const signed_limb_type& o) { if(o) { if(o < 0) eval_add(result, static_cast<limb_type>(-o)); else eval_subtract(result, static_cast<limb_type>(o)); } } I think I understand the motivation for sign-magnitude for variable-length representation, but I don't see any benefit in the case of e.g. mp_int128_t. I also wonder about the work involved in e.g. a 64 x 64 -> 128-bit multiplication. Here is my version, based on 32x32->64 multiplies: inline int128_t mult_64x64_to_128(int64_t a, int64_t b) { // Make life simple by dealing only with positive numbers: bool neg = false; if (a<0) { neg = !neg; a = -a; } if (b<0) { neg = !neg; b = -b; } // Divide input into 32-bit halves: uint32_t ah = a >> 32; uint32_t al = a & 0xffffffff; uint32_t bh = b >> 32; uint32_t bl = b & 0xffffffff; // Long multiplication, with 64-bit temporaries: // ah al // * bh bl // ---------------- // al*bl (t1) // + ah*bl (t2) // + al*bh (t3) // + ah*bh (t4) // ---------------- uint64_t t1 = static_cast<uint64_t>(al)*bl; uint64_t t2 = static_cast<uint64_t>(ah)*bl; uint64_t t3 = static_cast<uint64_t>(al)*bh; uint64_t t4 = static_cast<uint64_t>(ah)*bh; int128_t r(t1); r.high = t4; r += int128_t(t2) << 32; r += int128_t(t3) << 32; if (neg) r = -r; return r; } So I need 4 32x32->64 multiplies to perform 1 64x64->128 multiply. But we can't write this: int64_t a, b ...; int128_t r = a * b; because here a*b is a 64x64->64 multiply; instead we have to write something like r = static_cast<int128_t>(a)*b; so that our operator* overload is found; but this operator* doesn't know that its int128_t argument is actually a promoted int64_t, and it has to do an 128x64->128 or 128x128->128 multiply, requiring 8 or 16 32x32->64 multiplies. The only chance of avoiding the extra work is if the compiler can do constant-propagation, but I have my doubts about that. Any thoughts? My test code is here: http://chezphil.org/tmp/boost_mp_review.tbz2 $ make $ cat nn100000.dat | benchmark (Note that this needs a fix to the resize() issue reported earlier in order to get accurate answers, but that doesn't much alter the execution time.) Regards, Phil.

8 15

help
by Bertolino, Keith D. 15 Jun '12

15 Jun '12

unsubscribe

1 0

[multiprecision review] Possible use of uninitialised value
by Phil Endecott 14 Jun '12

14 Jun '12

Dear All, I decided to try to evaluate the proposed Boost.Multiprecision on the code that I wrote recently when looking at the proposed Delaunay Triangulation / Voronoi Diagram code. Specifically, this function: inline bool delaunay_test(int32_t ax, int32_t ay, int32_t bx, int32_t by, int32_t cx, int32_t cy, int32_t dx, int32_t dy) { // Test whether the quadrilateral ABCD's diagonal AC should be flipped to BD. // This is the Cline & Renka method. // Flip if the sum of the angles ABC and CDA is greater than 180 degrees. // Equivalently, flip if sin(ABC + CDA) < 0. // Trig identity: cos(ABC) * sin(CDA) + sin(ABC) * cos(CDA) < 0 // We can use scalar and vector products to find sin and cos, and simplify // to the following code. // Numerical robustness is important. This code addresses it by performing // exact calculations with large integer types. i64 ax64 = ax, ay64 = ay, bx64 = bx, by64 = by, cx64 = cx, cy64 = cy, dx64 = dx, dy64 = dy; i64 cos_abc = (ax64-bx64)*(cx64-bx64) + (ay64-by64)*(cy64-by64); i64 cos_cda = (cx64-dx64)*(ax64-dx64) + (cy64-dy64)*(ay64-dy64); if (cos_abc >= 0 && cos_cda >= 0) return false; if (cos_abc < 0 && cos_cda < 0) return true; i64 sin_abc = (ax64-bx64)*(cy64-by64) - (cx64-bx64)*(ay64-by64); i64 sin_cda = (cx64-dx64)*(ay64-dy64) - (ax64-dx64)*(cy64-dy64); i128 sin_sum = static_cast<i128>(sin_abc)*cos_cda + static_cast<i128>(cos_abc)*sin_cda; return sin_sum < 0; } Here i64 and i128 are typedefs for appropriate 64- and 128-bit signed integer types. when I try to use boost::multiprecision::cpp_int, I get answers that are only mostly correct. Specifically, sometimes the very first call gives the wrong answer. It is dependent on the number of iterations of my benchmark loop and other factors. valgrind reports the following: ==15713== Conditional jump or move depends on uninitialised value(s) ==15713== at 0x8053B0C: boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>::mp_number<boost::multiprecision::detail::plus, boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::multiply_immediates, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, void, void>, boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::multiply_immediates, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, void, void>, void, void>(boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::plus, boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::multiply_immediates, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, void, void>, boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::multiply_immediates, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u, true, std::allocator<unsigned int> >, true>, void, void>, void, void> const&) (in /home/phil/boost_mp_review/benchmark) As expected, the error is impenetrable. Can anyone guess what is going on? (I seem to get the right answers and no valgrind errors with the fixed-size and no-expression-templates types.) Regards, Phil.

2 3

[mpi] MPI_IN_PLACE equivalent
by Alain O Miniussi 14 Jun '12

14 Jun '12

Some collective mpi operations allow the user to re-use the input buffer as the output buffer (MPI_IN_PLACE). I did not find that functionality in boost::mpi and filed a ticket (https://svn.boost.org/trac/boost/ticket/6704) along with a patch for a possible implementation for all_reduce and the associated testing. What is the best way to get some input regarding that proposed patch ? (the ticket itself has been untouched for 3 months now) Best regards, -- Alain Miniussi Responsable Tech. Centre de Calcul Haute Performance Observatoire de la Côte d'Azur - BP 4229 - 06304 Nice Cedex 4 tel: +33 4 92 00 30 09 https://crimson.oca.eu

1 0

[multiprecision review] EOF not declared, and noexcept errors
by Phil Endecott 14 Jun '12

14 Jun '12

Dear All, I'm trying to do some simple tests with the proposed Boost.Multiprecision, but anything that includes e.g. boost/multiprecision/cpp_int.hpp gives errors like this: /big_number/boost/multiprecision/mp_number.hpp:1730:11: error: ‘EOF’ was not declared in this scope /big_number/boost/multiprecision/rational_adapter.hpp:208:45: error: expected ‘;’ at end of member declaration /big_number/boost/multiprecision/rational_adapter.hpp:208:47: error: ‘noexcept’ does not name a type My guess is that the EOF error may be a missing include, while the latter two errors may be something that's missing in the relatively old Boost installation on this test machine. Can anyone suggest what I need to do? Regards, Phil.

4 4

Cannot access structure elements using iterator to list containing shared_ptr<struct>
by Manjunath BJ 14 Jun '12

14 Jun '12

> > Hi, >> I would like to have a list(STL) of shared_ptr. The shared_ptr >> would hold the pointer to the structure "packet_holder" >> . >> > struct packet { > >> int c; >> union{ >> struct pkt_header header; >> struct ip_header ip_hd; >> }type; >> > }packet_holder; >> >> > list<boost::shared_ptr<packet_holder> > pkt_list; > boost::shared_ptr<packet_holder> pkt(new packet_holder); > pkt_list.push_pack(pkt); > > Having defined this, I would like to use iterator to iterate > through the list. > list<boost::shared_ptr<packet_holder> >::iterator it; > for(it = list.begin();it != list.end();it++) > But I am not able to access the inner details of the struct > "packet_holder" using the iterator. > it->type.header is not accessible. > > Can anyone please suggest me where exactly I might be wrong. > > -- >> With Regards, >> Manjunath BJ >> > > > > -- > With Regards, > Manjunath BJ > -- With Regards, Manjunath BJ

2 2

[test] max_digits10 code breaks regression testing for many older platforms
by David Deakins 13 Jun '12

13 Jun '12

Paul, I noticed that the change to set_precision in Boost.Test (rev 78908) seems to have broken regression testing on the trunk for all of the platforms that don't have max_digits10 in their standard library (even for non-math-related tests). Is there any way to restrict this new code to only platforms that can support it? Thanks, -Dave

1 0

Boost mpi, serialization and shared_ptr
by Max Moorkamp 13 Jun '12

13 Jun '12

Hi, I have started to parallelize one of my applications using MPI and I am running into trouble with serializing classes that contain shared_ptr member to be send through MPI. Below is a minimal case that demonstrates my problem. #include <boost/serialization/serialization.hpp> #include <boost/shared_ptr.hpp> #include <boost/mpi.hpp> #include <boost/serialization/shared_ptr.hpp> #include <boost/serialization/export.hpp> class Base { private: friend class boost::serialization::access; template<class Archive> void serialize(Archive & ar, const unsigned int version) { } public: Base() { } virtual ~Base() { } }; class Derived: public Base { private: double b; boost::shared_ptr<Base> MemberPointer; friend class boost::serialization::access; template<class Archive> void serialize(Archive & ar, const unsigned int version) { ar & boost::serialization::base_object<Base>(*this); ar & MemberPointer; ar & b; } public: Derived() { } virtual ~Derived() { } }; //BOOST_CLASS_EXPORT(Base) BOOST_CLASS_EXPORT(Derived) int main(int argc, char *argv[]) { boost::mpi::environment env(argc, argv); boost::mpi::communicator world; boost::shared_ptr<Base> Pointer(new Derived()); boost::mpi::broadcast(world, Pointer, 0); } I want to broadcast the derived class that has a member that is a shared_ptr. When I compile this code with gcc-4.6, intel or clang all compilers complain, this is the output from gcc-4.6 In file included from Hacks/serialization_mpi.cpp:11:0: /usr/local/include/boost/serialization/shared_ptr.hpp: In function ‘void boost::serialization::load(Archive&, boost::shared_ptr<U>&, unsigned int) [with Archive = boost::mpi::packed_skeleton_iarchive, T = Base]’: /usr/local/include/boost/serialization/split_free.hpp:58:9: instantiated from ‘static void boost::serialization::free_loader<Archive, T>::invoke(Archive&, T&, unsigned int) [with Archive = boost::mpi::packed_skeleton_iarchive, T = boost::shared_ptr<Base>]’ /usr/local/include/boost/serialization/split_free.hpp:74:5: instantiated from ‘void boost::serialization::split_free(Archive&, T&, unsigned int) [with Archive = boost::mpi::packed_skeleton_iarchive, T = boost::shared_ptr<Base>]’ /usr/local/include/boost/serialization/shared_ptr.hpp:171:5: instantiated from ‘void boost::serialization::serialize(Archive&, boost::shared_ptr<U>&, unsigned int) [with Archive = boost::mpi::packed_skeleton_iarchive, T = Base]’ /usr/local/include/boost/serialization/serialization.hpp:128:9: instantiated from ‘void boost::serialization::serialize_adl(Archive&, T&, unsigned int) [with Archive = boost::mpi::packed_skeleton_iarchive, T = boost::shared_ptr<Base>]’ /usr/local/include/boost/archive/detail/iserializer.hpp:188:5: instantiated from ‘void boost::archive::detail::iserializer<Archive, T>::load_object_data(boost::archive::detail::basic_iarchive&, void*, unsigned int) const [with Archive = boost::mpi::packed_skeleton_iarchive, T = boost::shared_ptr<Base>]’ Hacks/serialization_mpi.cpp:64:3: instantiated from here /usr/local/include/boost/serialization/shared_ptr.hpp:133:9: error: ‘class boost::mpi::packed_skeleton_iarchive’ has no member named ‘append’ /usr/local/include/boost/serialization/shared_ptr.hpp:139:5: error: ‘class boost::mpi::packed_skeleton_iarchive’ has no member named ‘reset’ If I remove the shared_ptr member, it compiles and runs. If I remove BOOST_CLASS_EXPORT(Derived) it compiles, but when running it I get terminate called after throwing an instance of 'boost::archive::archive_exception' what(): unregistered class - derived class not registered or exported Is this a bug or am I doing something wrong? A google search shows an old discussion (2007) that concludes that this problem is fixed in boost 1.45. I see this happening with both 1.48 and 1.49. Any help is appreciated. Regards Max

3 6

[Nowide] Formal Review Request
by Artyom Beilis 13 Jun '12

13 Jun '12

Hello, I'd like to ask to add Boost.Nowide to review queue: Boost.Nowide is a library implemented by Artyom Beilis that make cross platform Unicode aware programming easier. The library provides an implementation of standard C and C++ library functions, such that their inputs are UTF-8 aware on Windows without requiring to use Wide API. Sources: http://cppcms.com/files/nowide/ Docs: http://cppcms.com/files/nowide/html/ Git: git://cppcms.git.sourceforge.net/gitroot/cppcms/nowide Thank You Very Much! Artyom Beilis P.S.: Previous mail was sent accidentally to boost.users list, sorry. -------------- CppCMS - C++ Web Framework: http://cppcms.com/ CppDB - C++ SQL Connectivity: http://cppcms.com/sql/cppdb/

3 4

[pool] Broken documentation
by Klaim - Joël Lamotte 12 Jun '12

12 Jun '12

Hi, http://www.boost.org/doc/libs/1_49_0/libs/pool/doc/html/boost_pool/pool/poo… In this page all images are broken for me. Joel Lamotte

3 3