July 2009 - Boost - lists.preview.boost.org

sorting floats by casting to integer
by Steven Ross 27 Jul '09

27 Jul '09

I've been investigating why float_sort is so much faster than std::sort on x86 processors, and why sorting integers is so much faster than float_sort, and came to the conclusion that floating-point comparisons are extremely slow on x86. Based upon that, I've written a different sorting approach that copies the input array of floats, casting them to integers, and sorts them as integers, dealing with the negative floats sorting in reverse order issue, completely eliminating floating-point comparisons. It takes O(n) additional memory, and is somewhat less general, as a different approach is required for key plus data sorting (as non-float data can't be safely cast this way), but it obtains integer-sorting speeds. On some problems it is as much as 120X as fast as std::sort. I doubt average results will be quite that good, but they could easily be well over 10X as fast. Does this sound like it's appropriate for Boost? If so, I'll add it to my proposed Boost.Algorithm.Sorting library, which is complete, aside from this issue. Example source (not templated yet): #define DATATYPE float #define CAST_TYPE int inline void float_as_integer_sort(std::vector<DATATYPE> &input) { if(input.size() < 2) return; std::vector<CAST_TYPE> cast_vec; cast_vec.resize(input.size()); unsigned neg_index = 0; int pos_index = input.size() - 1; //Casting to integer and presorting into negative and positive for(unsigned u = 0; u < input.size(); ++u) { int cast_val = float_mem_cast<DATATYPE, CAST_TYPE>(input[u]); if(cast_val < 0) cast_vec[neg_index++] = cast_val; else cast_vec[pos_index--] = cast_val; } assert((pos_index + 1) == neg_index); //Sort the negatives integer_sort(&(cast_vec[0]), &(cast_vec[neg_index])); //Then the positives integer_sort(&(cast_vec[neg_index]), &(cast_vec[0]) + cast_vec.size()); //casting back negatives for(unsigned u = 0; u < neg_index; ++u) std::memcpy(&(input[neg_index - u - 1]), &(cast_vec[u]), sizeof(DATATYPE)); //Then positives for(unsigned u = neg_index; u < cast_vec.size(); ++u) std::memcpy(&(input[u]), &(cast_vec[u]), sizeof(DATATYPE)); }

9 24

boost trunk issues
by Sean Farrow 25 Jul '09

25 Jul '09

Hi: is There an issue updating the boost trunk, When trying to update, I get the error: Error OPTIONS of 'http://svn.boost.org/svn/boost/trunk': 200 OK (http://svn.boost.org) I've done an svn cleanup. Any help appreciated. Sean.

4 3

[pool][Ticket #2359]Performance impact of bug fix
by Peter Hurley 25 Jul '09

25 Jul '09

The bug fix implemented for this ticket has a significant (approx 25~35%) performance impact when using fast_pool_allocator for the shared_ptr<> allocator, as in, static fast_pool_allocator<T> pool; shared_ptr<T> a(T,Tdestroyer,pool); Background: Although http://svn.boost.org/trac/boost/ticket/2359 has an extensive analysis and discussion of the problem, the key issue was that static non-local fast_pool_allocators did *not* force the prior construction of the underlying singleton_pool instance (class template static data members have unordered initialization). The fix implemented was to call singleton_pool<...>::is_from(0); in the ctors of fast_pool_allocate to enforce the proper construction order (for global ctors). Of course, this fix effects all scope & lifetime fast_pool_allocators. Problem: However, is_from() performs other, non-trivial work as well. From singleton_pool.hpp, template <...> struct singleton_pool { . . static bool is_from(void * const ptr) { pool_type & p = singleton::instance(); details::pool::guard<Mutex> g(p); return p.p.is_from(ptr); } Although the impact at startup is neglible, the copy ctor of fast_pool_allocator is called during the construction -and- the destruction of *every* shared_ptr<T> a(P,D,A). (Because the shared_ptr needs to rebind the allocator from <T> to sp_counted_impl_pda<P,D,A> ). The net effect is that the pool is locked and accessed *twice* every time a shared_ptr is constructed or destructed. Because of the locking overhead, even in a single-threaded environment, shared_ptr<T> a(P,D,fast_pool_allocator<T> > does not out-perform shared_ptr<T> a(P,D)! This situation is especially painful in a contentious MP environment. One solution (although by-no-means exhaustive) would be to only perform the bare minimum necessary to force prior construction of the singleton_pool instance. For example, in boost/pool/singleton_pool.hpp, template <...> struct singleton_pool { . . static void force_construction() { singleton::instance(); } and in boost/pool/pool_alloc.hpp fast_pool_allocator() { singleton_pool<fast_pool_allocator_tag, sizeof(T), UserAllocator, Mutex, NextSize>::force_construction(); } template <typename U> fast_pool_allocator( const fast_pool_allocator<U, UserAllocator, Mutex, NextSize> &) { singleton_pool<fast_pool_allocator_tag, sizeof(T), UserAllocator, Mutex, NextSize>::force_construction(); } Regards, Peter Hurley PS - Also, casual profiling (gcc,x86,windows) seems to indicate that using boost::detail::spinlock as the default lock from <boost/smart_ptr/detail/spinlock.hpp> would yield add'l performance benefits over details::pool::default_mutex. Faster yet would be a native locked_compare_exchange spinlock similar to the atomic_conditional_increment() implemented in the <sp_counted_base_***.hpp> headers...

1 0

Random numbers question
by Anant Rao 25 Jul '09

25 Jul '09

Hi, I'm using Mersenne Twister algo to generate random numbers on Windows and Linux using the same code. Boost ver 1.39. Here's the simple code I have: boost::mt19937 rng(43); boost::uniform_01<boost::mt19937> zeroone(rng); float randomNumber = zeroone(); If I run it multiple times, I get the same result on the same OS, as expected. However, the random numebrs are different between Windows and Linux. Is this the expected behavior? Is there anything I can do to get the same random numbers on Windowd and Linux? Thanks a lot, Anant

2 3

Request for Review - Boost Algorithm
by Marshall Clow 24 Jul '09

24 Jul '09

Boost.Algorithm is a collection of useful algorithms, most from the "Library in a week" session from BoostCon 2008. The code (and tests) are available in the sandbox. -- Marshall

4 4

[filesystem][spirit] problems with scoped enums with GCC 4.4 in C++0x mode
by Richard Webb 24 Jul '09

24 Jul '09

(forwarding from the Spirit list) As discussed in the thread @ http://www.nabble.com/-Spirit2--Regression-test-failures-on-GCC-4.4-in-C%2B…, the regression tests for Filesystem and Spirit 2 are pretty much all failing in GCC 4.4 in C++0x mode, due to problems with scoped enums and operator ==. Does anyone have any other ideas about the problem? Thanks, Richard Webb -- View this message in context: http://www.nabble.com/-filesystem--spirit--problems-with-scoped-enums-with-… Sent from the Boost - Dev mailing list archive at Nabble.com.

3 3

[TR1][Hash] New failures?
by John Maddock 24 Jul '09

24 Jul '09

Anyone any idea what's causing the TR1:Hash tests to fail on the release branch? The TR1 code hasn't changed so I assume that a change in Boost::hash has broken these? Cheers, John.

2 4

[python] "Boost.Python Build and Test HOWTO" doc suggestion
by Beman Dawes 24 Jul '09

24 Jul '09

In the Requirements section, change: Boost.Python requires Python 2.2 or newer. to: Boost.Python requires Python 2.2 or newer. Both the Python runtime and the development (i.e. header) packages must be installed. --Beman

1 0

[mpi][serialization] Compilation broken
by Juergen Hunold 24 Jul '09

24 Jul '09

Hi ! Boost.MPI is currently broken on trunk due to r54934 | ramey | 2009-07-13 23:37:49 +0200 (Mon, 13 Jul 2009) | 2 lines which removed D /trunk/boost/archive/detail/archive_pointer_iserializer.hpp D /trunk/boost/archive/detail/archive_pointer_oserializer.hpp and now MPI fails to compile with: gcc.compile.c++ /build/bjam/boost_1.40.0/libs/mpi/build/gcc-4.4/debug/content_oarchive.o $BOOST_ROOT/libs/mpi/src/content_oarchive.cpp:10:62: error: boost/archive/impl/archive_pointer_oserializer.ipp: No such file or directory It seems that the regression tests don't catch this because no regression tester has MPI configured... It would be nice if at least the Linux testers could install MPI on their machines... I don't know enough about MPI and/or serialization to fix this myself, I just have MPI installed to get less warnings from older Boost.Build versions... Yours, Jürgen -- * Dipl.-Math. Jürgen Hunold ! Ingenieurgesellschaft für * voice: ++49 511 262926 57 ! Verkehrs- und Eisenbahnwesen mbH * fax : ++49 511 262926 99 ! Lister Straße 15 * juergen.hunold(a)ivembh.de ! www.ivembh.de * * Geschäftsführer: ! Sitz des Unternehmens: Hannover * Prof. Dr.-Ing. Thomas Siefer ! Amtsgericht Hannover, HRB 56965 * PD Dr.-Ing. Alfons Radtke !

3 4

Important: Subversion upgrade on Saturday, July 25
by Doug Gregor 23 Jul '09

23 Jul '09

We will be upgrading Boost's Subversion server and the Boost Subversion repository to Subversion 1.6.3. This upgrade will bring the new features provided by the Subversion 1.5.x and 1.6.x released to Boost, including merge tracking: http://subversion.tigris.org/svn_1.5_releasenotes.html http://subversion.tigris.org/svn_1.6_releasenotes.html The upgrade will begin on Saturday, July 25 at 8:00AM EST, and is likely to take all day. During this upgrade, the Boost Subversion repository, Trac, and mailing list archives will be inaccessible. However, the Boost mailing lists should still function normally. I will send a note to the Boost list when the upgrade is complete. Thank you for your patience. - Doug

2 2