September 2009 - Boost - lists.boost.org

14 Sep '09

i'd like to present some kind of micro optimization towards pipelined cpus traditionaly min() has an implementation like template<typename type> inline type min(type a, type b) { return a<b ? a : b; } this function (even if inlined) introduces a branch in a sequence of instructions though branch prediction algorithms do exist they will guess at most 50% of them because routine input is arbitrary since a wrong branch prediction causes pipeline stall i thought that such a useful routine like min() MUST have non-stalling (read 'non-branching') implementation i thought hard and in the end recalled a simple implementation which is called LUT (for 'look-up table') here's what i finally got: template<typename type> inline type min(type a, type b) { const type c[2] = {a, b}; return c[b<a]; } intuitively this implementation should work slower than the first one but in real life it runs faster (roughly by a factor of 2 for 4 byte types on core2duo) here's a test code: #include <vector> int main() { typedef int type; const int n = 1000000; std::vector<type> v1(n), v2(n); //filling v1 and v2 somehow type min = BIG_VALUE; for (size_t i = 0; i<n; ++i) a = min(a, min(v1[i], v2[i])); //searching minima of v1 and v2 return 0; } however for 'double' it runs ~2% slower (i think it's because creating a lut for 2 elements 8 bytes each is slower than a branch on c2d) nevertheless i think it's a great approach at least for ints also max() can implemented very similar you may skip the rest example of usage imagine we want to implement a symmetric matrix that stores only half of its elements (say upper triangle) a00 a01 a02 --- a11 a12 --- --- a22 then access requests to the lower triangle elements would be redirected to upper triangle ones here we have a constraint that actually we only have access to elements a(i, j) where i<=j must always be true (look at indices above) if we use a branch like //... return i<=j ? a(i, j) : a(j, i); we get a pipeline stall almost every time we want to access an arbitrary element however if we rewrite it carefully as //... const size_t m = min(i, j); //non-branching min() here return a(m, m + abs(int(i) - int(j))); //abs() is also //non-branching we get rid of branches at all! and we can hope a pipelined cpu will handle it better than the other (branched) implementation -- pavel

9 14

Re: [boost] Are warnings acceptable artifacts from builds?
by Vinnie 14 Sep '09

14 Sep '09

>From http://sqlite.org/testing.html#coverage "Static analysis means analyzing code at or before compile-time to check for correctness. Static analysis consists mostly of making sure SQLite compiles without warnings, even when all warnings are enabled. SQLite is developed primarily using GCC and it does compile without warnings on GCC using the -Wall and -Wextra flags. There are occasional reports of warnings coming from VC++, however. Static analysis has not proven to be helpful in finding bugs. We cannot call to mind a single problem in SQLite that was detected by static analysis that was not first seen by one of the other testing methods described above. On the other hand, we have on occasion introduced new bugs in our efforts to get SQLite to compile without warnings. Our experience, then, is that static analysis is counter-productive to quality. In other words, focusing on static analysis (being concerned with compiler warnings) actually reduces the quality of the code. Nevertheless, we developers have capitulated to pressure from users and actively work to eliminate compiler warnings. We are willing to do this because the other tests described above do an excellent job of finding the bugs that are often introduced when removing compiler warnings, so that product quality is probably not decreased as a result."

16 31

[pool] Thread specific pool allocator
by James Bremner 14 Sep '09

14 Sep '09

I develop code to run on multiple processor machines. Moderate use of the standard template library (STL) containers cause programs to slow down when the work is split between threads running on different processors. This is because the STL default memory allocator is a thread-safe singleton and causes contention between the threads. The memory allocator provided by boost::pool_allocator is also a thread safe singleton. I have coded a thread specific memory allocator based on boost::pool and boost:thread_specific_pointer. My allocator creates a new instantiation for each thread it is used in, and so avoids contention between threads. The containers created with this allocator must be used carefully, not written to by more than one thread, because the allocator is not thread-safe ( that is the point! ) - however they provide dramatic performance improvements when my code runs on multiple processors. I do not expect my coding is to the high standard of the boost libraries, but I do believe it shows that something very useful can be done with a few lines of code. Any chance of a boost:thread_specific_pool_allocator in the near future? James Bremner

7 11

[serialization] Calling basic_streambuf::sync in basic_binary_iprimitive destructor
by Andrey Upadyshev 14 Sep '09

14 Sep '09

Hi, All! Anybody knows, does we really need to call std::basic_streambuf::sync in boost::archive::basic_binary_iprimitive destructor? Is it possible to not call it? I ask it because the call of sync with file stream buffer leads to skipping of the unreaded input data. I think it is not good, or al least it must be clear described in documentation, that binary_iarchive when used with file stream skips to the end of a stream. Andrey Upadyshev P.S. Sorry for my English

2 2

Re: [boost] C++ Manifesto
by christophe henry 14 Sep '09

14 Sep '09

> Why is there no Boost.ANTLR? Good question. I mean, if Spirit seems to you such a disservice to the community that you write the xth post about it, why not show how to do it right? I'm sure we would all benefit from it, because right now, I haven't read anything constructive in this post. At least Joel spent lots of time to offer a great library to the C++ community and I think he deserves better than such unconclusive criticism as "I think that it represents a disservice to the C++ community". Seeing from his user base, I respectfully allow myself some to disagree on that point. Now the challenge is simple: Make it better and you'll earn yourself some respect. Don't provide any alternative and land from now on in my spam box. Regards, Christophe _________________________________________________________________ Show them the way! Add maps and directions to your party invites. http://www.microsoft.com/windows/windowslive/products/events.aspx

2 1

[thread] Obtaining thread id on Windows
by Agustín K-ballo Bergé 13 Sep '09

13 Sep '09

I've found a need to retrieve a thread id rather than a thread handle on Windows. There is no documented way to get it from the handle on XP (see http://social.msdn.microsoft.com/Forums/en-US/vcgeneral/thread/89728ee1-d9d… ). Would it make sense to add a get_native_id member function? Thank you. Agustín K-ballo Bergé.-

2 3

[variadic_templates][mpl]announcement:sandbox now has variadic_templates directory
by Larry Evans 12 Sep '09

12 Sep '09

There is now a sandbox directory for variadic templates: https://svn.boost.org/trac/boost/browser/sandbox/variadic_templates The tests in variadic_templates/libs/mpl/test/Jamfile have all passed. Some of those tests have been slightly modified to accommodate the variadic template version of mpl sequences. BTW, it's important to apply the gcc patch mentioned here: https://svn.boost.org/trac/boost/browser/sandbox/variadic_templates/README.… All sequences have been changed to use a new template: foldr_pack whose last argument is a parameter pack. That change also required a new binary template for each sequence: X_item_fold where X is one of: v l s m One reason for that change was to highlight the similarites of the sequences. Some other fold additions were: foldr_iter.hpp foldl_iter.hpp The foldr and foldl correspond roughly to iter_fold and reverse_iter_fold (or the other way around, I can't remember which). The reason for these additions is that they reflect more closely the way foldr and foldl are done in haskell, as indicated by the comments in the .hpp files. One useful application of the pattern expansion mentioned in section 3.6.1 of: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2242.pdf is their use to easily define SEQ_c in terms of SEQ, where SEQ is any sequence. For example: template < typename Integral , Integral... Values > struct list_c : list < integral_c<Integral,Values>... > { typedef Integral value_type; }; Another addition is package_range_c.hpp which can be used to do something similar to range_c. The main motivation for this was the make_indexes on p. 16 of: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2006/n2080.pdf It was used in a prototype tuple implementation in: variadic_templates/libs/mpl/sandbox/tuple_non_recur.package_range_c.cpp Package_range_c was also useful in the implementation of unpack_args. A really interesting application of these pattern expansions might be another implementation of the cross_product template: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?CPPTM_Answer… The reason I think it would be useful is because the expansion of: integral_c<Integral,Values>... results in: integral_c<Integral,Value1> integral_c<Integral,Value2> ... integral_c<Integral,ValueN> where ValueI is the i-th element in Values... Now this is a cross product of a single element, Integral, with each element in Values...; hence, I would think that it would be a simple matter to just repeat this for any number of elements. IOW, instead of integral_c, there could be: template<typename Left, typename...Rights> struct pair_rights : pair<Left,Rights>... {}; and then that, somehow, could be done for each element in some list of Left's. Would somebody like to try this? Hope somebody else finds this useful. -regards, Larry

1 0

[iterators] zip_iterator requires random_access_iterator?
by Dean Michael Berris 12 Sep '09

12 Sep '09

Hi Everyone, According to the documentation (http://www.boost.org/doc/libs/1_40_0/libs/iterator/doc/zip_iterator.html) All iterator types in the argument IteratorTuple shall model Readable Iterator. When I use a BidirectionalIterator (list<...>::iterator) zip_iterator fails to compile, while when I use a RandomAccessIterator (vector<...>) it compiles just fine. I have a nesting like this: make_filter_iterator( filter(), make_zip_iterator( make_tuple( container.begin(), make_transform_iterator( container.begin(), function() ) ) ) The first line in the error logs is: /home/dean/boost/boost/iterator/detail/minimum_category.hpp: In instantiation of ‘boost::detail::minimum_category_impl<false, false>::apply<boost::detail::iterator_category_with_traversal<std::input_iterator_tag, boost::bidirectional_traversal_tag>, boost::random_access_traversal_tag> I'm using Boost SVN trunk updated to revision 56153 -- did I find a bug? HTH -- Dean Michael Berris blog.cplusplus-soup.com | twitter.com/mikhailberis linkedin.com/in/mikhailberis | facebook.com/dean.berris | deanberris.com

1 0

Build files locations, try 2
by Vladimir Prus 12 Sep '09

12 Sep '09

Some time ago, I have raised the concern that CMakeList.txt files violate directory structure requirements. See: http://thread.gmane.org/gmane.comp.lib.boost.devel/189496/ Back then, the discussion did not lead anywhere, and no further progress was made for 2.5 months. So, let me try to phrase this a bit differently. Is it fine with everybody if I move Jamfiles out of 'build' folder of every library one level higher? Thanks, Volodya

4 4

MSVC decorators still in autoconfig?
by Stephan Menzel 11 Sep '09

11 Sep '09

Hi, I am just about to migrate to 1.40 and I noticed the changed naming scheme. So the TOOLSET and BOOST_LIB_VERSION defines are missing when I build the libs (even when using layout=tagged in bjam) but the autoconfig, specifically auto_link.hpp, still includes this in MSVC's autolink feature. So as far as I can see autolink will not work in Windows, right? At least, it doesn't for me unless I change auto_link.hpp line 312 so skip this. Is this a bug or am I overlooking something important? Cheers, Stephan

3 4