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

[test]
by Jochen Heckl 17 May '09

17 May '09

Hi, I think I stumbled over a problem in the boost unit test library. I'm running MSVC 2008 SP1. Maybe also worth mentioning is, that I use _HAS_TR1=0 with any msvc build. Also I compile boost using bjam define=_HAS_TR1=0 ... Well straight to the problem: this code (boost\test\utils\basic_cstring\basic_cstring.hpp, around line 170) template<typename CharT> inline basic_cstring<CharT>::basic_cstring( std_string const& s ) : m_begin( s.c_str() ) , m_end( m_begin + s.size() ) { } will result in a corrupted basic_cstring, if the source string s goes out of scope, which is the case here ( \boost\test\impl\unit_test_main.ipp, around line 179 ) ... int BOOST_TEST_DECL unit_test_main( init_unit_test_func init_func, int argc, char* argv[] ) { try { framework::init( init_func, argc, argv ); if( !runtime_config::test_to_run().is_empty() ) { test_case_filter filter( runtime_config::test_to_run() ); // <--- parameter will become corrupted traverse_test_tree( framework::master_test_suite().p_id, filter ); } ... because of the temporal std::string return from retrieve_parameter (boost\test\impl\unit_test_parameters.ipp, around line 353 ) const_string test_to_run() { return retrieve_parameter( TESTS_TO_RUN, s_cla_parser, s_empty ); } as quick and very very dirty fix I currently use: test_to_run() { static std::string TTR = retrieve_parameter( TESTS_TO_RUN, s_cla_parser, s_empty ); return TTR; } However, I would welcome, if somebody could supply a more suitable solutions. Best Jochen

2 1

[gsoc] Proposal for Generic Trie, Radix Tree, and Suffix Array Data Structures
by Chris Wagner 17 May '09

17 May '09

Hello, I am interested in writing a library consisting of generic implementations of several common data structures and algorithms primarily useful in text-processing. I believe these would be useful additions to Boost and would like to work on them for GSoC. Before I submit my proposal, I would like to hear whether or not the community agrees that this is a good idea, and I would appreciate any suggestions or comments offered. My plan is to implement a trie / prefix tree data structure, STL set/map-like classes implemented over the trie, a radix tree, a suffix tree implemented over the radix tree, and a suffix array. These would be instantiable over arbitrary sequence types, and use iterator traits to determine the contained type. I am a student at Kent State University, working on an M.S. in Computer Science in a combined undergraduate/graduate program. I have a particular interest in computational linguistics, and I will admit that am especially interested in this project because of how it could be applied to my own field, but I believe that these types would be of general utility to the programming community as a whole. Thank you for your time, Chris Wagner

5 5

[1.39.0] Beta candidate
by Beman Dawes 15 May '09

15 May '09

The beta candidate files are up at http://boost.cowic.de/rc/ Before pushing these out to SourceForge, it would be great if a few Boosters could download and try them out as a final QA check. Post your experiences here. Thanks, --Beman

9 24

Review Request: Algorithm.Sorting
by Steven Ross 15 May '09

15 May '09

I have uploaded algorithm_sorting.zip for a formal review to become Boost.Algorithm.Sorting, if people feel that is appropriate. It is 3 templated hybrid radix-based/comparison-based algorithms, specialized to sort certain types of data more efficiently. All 3 have superior worst-case and average-case performance to std::sort, based upon my testing. None of these algorithms use much additional memory. All of them can sort key + data, and as they do fewer swaps, tend to do so much faster than std::sort. As a general rule, the speedup of these algorithms relative to std::sort increases as data set size increases. These algorithms tend to be faster relative to std::sort when comparisons are slow, as they do less (or no) comparisons. string_sort, which sorts strings in O(n*length) time, as compared to O(n*length*log(n)) for pure comparison-based algorithms. It is consistently faster than std::sort in string sorting, by a little more than a factor of 2 based upon my testing. float_sort, which sorts IEEE floating-point numbers as integers, but attaining the same ordering as std::sort, with the exception of -0.0 and NaNs, both of which cannot be ordered based upon their comparison function. float_sort is roughly twice as fast as std::sort on UNIX-type OSes I've tested on, and roughly 7X as fast on Windows. I believe this speedup to be because floating-point comparisons are slow on Windows. integer_sort, which sorts integers around 60% faster than std::sort on UNIX-type OSes, and 25% faster on Windows. On Windows with MSVC, std::sort sorts already-sorted and small range data extremely quickly, and integer_sort processes already-sorted data slower than it by as much as a factor of 3X. I believe this to be due to some optimization for already-sorted data, as integer_sort takes substantially less absolute time on already-sorted data than unsorted data. So integer_sort on Windows has a tradeoff: better worst-case and average-case performance, but worse best-case performance. integer_sort and float_sort share some tuning parameters. I have set values that seem to work well on both UNIX-type and Windows OSes, but people are welcome to try to see what values are best for their system and problem type. The ideal values for integers and floats may be different on some systems (such as Windows), but for simplicity they are kept the same. A tuning/testing script named tune.pl is included, for those who wish to see how fast these algorithms are on their system (and verify correctness). I don't recommend using it for tuning without the -large option, and that takes days. If you do use it for tuning, I also recommend the -verbose option, to see what it's doing.

6 19

[RFC] thread::access_monitor
by Gregory Petrosyan 14 May '09

14 May '09

I would like to hear your comments on the idea behind access_monitor template, which ensures (at compile-time) that data, protected by it, can be accessed only with associated lock held. It can be useful when you want to expose all the native interface of your data type (STL container, for example): in such a case, using ordinary monitor pattern is almost impossible. Example usage: typedef access_monitor<data_type, mutex_type> data_access_monitor; void f(data_access_monitor const& d) { data_access_monitor::value_type const* data; data_access_monitor::lock_type lock; boost::tie(data, lock) = d.const_lock(); // do something with data here } Code: #include <boost/thread.hpp> #include <boost/tuple/tuple.hpp> template <typename T, typename Lockable> struct access_monitor { typedef T value_type; typedef boost::unique_lock<Lockable> lock_type; private: typedef boost::detail::thread_move_t<lock_type> lock_move_type; public: boost::tuple<value_type const*, lock_move_type> const_lock() const { lock_type lock(mutex_); return boost::make_tuple(&data_, lock.move()); } boost::tuple<value_type*, lock_move_type> lock() { lock_type lock(mutex_); return boost::make_tuple(&data_, lock.move()); } private: // mutex_ is guaranteed to be locked when you access data_ mutable Lockable mutex_; T data_; }; Sorry for draft-quality code (however, something like the above compiles with MSVC 9). Please CC me, because I am not subscribed. Gregory

2 1

[scope_exit] Boost.ScopeExit capturing 'this'
by adam.butcher＠selex-comms.com 11 May '09

11 May '09

I wasn't sure whether I had the correct address for Boost.ScopeExit's author Alexander Nasonov, so I've submitted to this list just in case and to get feedback from other users. I have been playing with BOOST_SCOPE_EXIT -- it it very convenient. One thing I would have liked would be to capture 'this' inside member functions. I have created a patch which adds BOOST_SCOPE_EXIT_THIS to do just that. It provides an operator->() in the generated struct which can be used to access the enclosing class's members. The syntax is: BOOST_SCOPE_EXIT_THIS( (&a) (&b) ) { a; b; // local captures (*this)->member; // member access } BOOST_SCOPE_EXIT_END; and can be BOOST_SCOPE_EXIT_THIS() { (*this)->member; } BOOST_SCOPE_EXIT_END; providing the preprocessor allows for empty parameter lists (which gcc does and vc does albeit after disabling a warning to remove noise). The type pointed to by the result of operator->() is correctly cv qualified. It has been tested on gcc 4.3, gcc 4.2, msvc 7.1 and msvc 9.0. I don't have access to other compilers. Boost.Typeof worked fine on gcc for typeof(this) -- mostly because gcc has a native typeof I guess. On visual studio (vc71 and vc90) it was not so good -- a compiler bug ( http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?Feedba… , http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?Feedba… ) that has been marked as 'Won't fix' means that 'this' cannot be used in expressions within template argument lists -- even if those expressions are innocuous typeid()s or sizeof()s for type-inference. The common workaround (capturing a compile-time integer with an enumerator and using the enumerator in the template parameter list) doesn't work with the vc71-specific implementation of Boost.Typeof since it is based on typeid() -- this cannot be captured in a compile-time expression (or I know of no way to that doesn't involve the expression existing in a template argument list). All is not lost though -- the general-purpose sizeof() based approach for the other VC versions works fine for VC71 for determining the typeof 'this'. As such my patch includes a VC>=1300 specific workaround for typeof 'this' determination. This is unfortunate but I couldn't think of any other non-intrusive way of doing it. Please find the attached patch and let me know what you think -- I'm sure this feature would be useful to users -- it saves having to do: TypeOfMyClassWhichCouldBeTedious* self = this BOOST_SCOPE_EXIT( (&self) ) { self->member; } BOOST_SCOPE_EXIT_END; which removes the convenience of BOOST_SCOPE_EXIT in these contexts since something like: struct at_end { TypeOfMyClassWhichCouldBeTedious* self; ~at_end() { self->member; } } at_end = {this}; can be done without any dependencies to achieve the same result. Regards, Adam. ------------------------------------------------------------ This email and any attached files contains company confidential information which may be legally privileged. It is intended only for the person(s) or entity to which it is addressed and solely for the purposes set forth therein. If you are not the intended recipient or have received this email in error please notify the sender by return, delete it from your system and destroy any local copies. It is strictly forbidden to use the information in this email including any attachment or part thereof including copying, disclosing, distributing, amending or using for any other purpose. In addition the sender excludes all liabilities (whether tortious or common law) for damage or breach arising or related to this email including but not limited to viruses and libel. SELEX Communications Limited is a Private Limited Company registered in England and Wales under Company Number 964533 and whose Registered Office is Lambda House, Christopher Martin Rd, Basildon, SS14 3EL. England.

4 8

[iostreams] regression - Missing include guard in boost/iostreams/device/mapped_file.hpp
by Bjørn Roald 10 May '09

10 May '09

Hi, Seems like the trunk@46692 commit, 25 june 2008, removed the include guard in boost/iostreams/device/mapped_file.hpp This breaks gcc43 compilation of sources directly including this header. Eg. http://www.mapnik.org/ trunk code. -- Bjørn

2 4

[thread] on_tls_prepare in win32\tss_pe.cpp incompatible with static linkage to a /clr object
by Matthew Chambers 06 May '09

06 May '09

I'm very interested in being able to have a native C++ executable which makes use of boost's TSS and also be able to wrap .NET modules with C++/CLI (i.e. /clr). And I much prefer it to be statically linked. The C++/CLI wrappers work fine when they are dynamically linked, but they cause a runtime initialization error (0xc000007b) whenever they are connected in only static links. It doesn't matter whether the host executable is compiled with /clr or not - somehow the MSVC linker knows to add some CLR initialization voodoo to the PE header whenever a static link to a /clr-enabled object is made. And that PE header voodoo seems to be incompatible with some of boost::thread's own brand of PE header voodoo which appears to be intended to provide TLS support for Windows. But as far as I can tell, I was able to get TLS working with MSVC9 even after commenting out the on_tls_prepare lines in tss_pe.cpp - commenting out the other lines wasn't necessary: > #if (_MSC_VER >= 1400) > //#pragma section(".CRT$XIU",long,read) > #pragma section(".CRT$XCU",long,read) > #pragma section(".CRT$XTU",long,read) > #pragma section(".CRT$XLC",long,read) > static __declspec(allocate(".CRT$XLC")) _TLSCB > __xl_ca=on_tls_callback; > // static __declspec(allocate(".CRT$XIU"))_PVFV p_tls_prepare = > on_tls_prepare; > static __declspec(allocate(".CRT$XCU"))_PVFV p_process_init = > on_process_init; > static __declspec(allocate(".CRT$XTU"))_PVFV p_process_term = > on_process_term; > #else I put together a test case that I'm pretty sure shows that TLS still works without that function. At the very least, can there be some preprocessor define to manually disable it for CLR compatibility? Or perhaps there is a way to adjust this voodoo to be compatible with the CLR initialization? I'm hosting the test case at: http://fenchurch.mc.vanderbilt.edu/files/TLS_CLR_Test.7z It includes a main function which runs a test of the TSS semantics, and a CLR class which tests console output via C++/CLI. I included binaries and the boost_thread.lib files for both the broken and "fixed" versions of tss_pe.cpp. Thanks, Matt Chambers

2 2

[aligned storage] support for empty storage
by Thorsten Ottosen 06 May '09

06 May '09

Hi all, Currently the following fails: typedef boost::aligned_storage< 0, 4u > storage; storage s; because this will try to create an empty array. Does anybody have anything against adding the following specialization: template< std::size_t alignment_ > struct aligned_storage_imp<0u,alignment_> { /* intentionally empty */ }; Also, I would like to derive from aligned_storage_imp to get the EBO: template < std::size_t size_ , std::size_t alignment_ = std::size_t(-1) > class aligned_storage : private detail::aligned_storage::aligned_storage_imp<size_, alignment_> { ... } The above changes enable the following program typedef boost::aligned_storage< 0, 4u > storage; struct simple : storage { int i; }; #include <iostream> int main() { std::cout << sizeof(storage) << " " << sizeof(simple); } to output "1 4" instead of "1 8" on gcc. In case your are wondering, then I need this functionality in boost::auto_buffer to get rid of the extra word when the stack-buffer is empty (thus making auto_buffer as small as vector). Comments? -Thorsten

2 4

[Review Results] Range.Ex library accepted into boost
by Thorsten Ottosen 04 May '09

04 May '09

Dear all, It is my pleasure that Neil Groves' RangeEx library has been accepted into boost. Congratulations Neil! There are quite a number of minor issues that need to be resolved before the library is release ready, see below for a summary. Review statistics ----------------- Full Reviews: 8. Discussion: extensive. I had the clear impression that everybody that participated in the discussion were in favor of this library, albeit they did not have time to submit a full review. I did not hear a single statement saying that this library should be rejected. Thanks to everybody that participated in the review and its discussions. Issue Summary ------------- Below is given a list of topics that must be adressed before the library can be included into boost. In general, we should try to discuss them one at a time in seperate threads. Many people suggested various extensions, new algorithms (e.g. from adope), etc. **In general we should not require Neil to add all these if he does not have the time currently: the basic infrastructure, the concepts, the naming and organization of the library is much more important. Then we can add all these things later.** 1: documentaion =============== The documentation should clearly reflect if an algorithm delegates to a standard algorithm. If the algorithm is new, then it should state complety and exception-safety. More examples would be welcome. Sometimes the rationale and explanations could be improved, e.g for operator|(). 2: return type specification for find() etc =========================================== There where no major objection to the mechanism, but some found the syntax ugly. I believe the suggested syntax (e.g.) boost::find[_f,_e]( range, x ) boost::find[_f+1,_e]( range, x ) was considered good by most. 3: namespace organization ========================= Currently the library uses the namspaces boost boost::adaptors Some raised concern about putting the algorithms straight in the boost namespace before we have a general agreement on where to put algorithms (e.g. in boost::algorithm or boost::ranges or whatever). I think it will make sense to put each algorithm in its own header, since we might have to include additional standard library headers for calling algorithms that are implemented as member functions (but see 7 below). Feedback is most welcome. 4: naming convention for adaptors ================================= The following have been proposed throughout the review (here examplified with "transform"): | transformed( fun ) | transform( fun ) | transform_view( fun ) | view::transform( fun ) There where no consensus during the review. Other libraries seem to use the _view suffix, which is a strong argument for that candidate (in that case, I suggest to drop the adaptors namespace). 5: naming convention for the adaptor generators =============================================== Many people like to be able to say make_transform_range(r,fun) instead of r | transformed( fun ). There was no concensus on how to name these functions. Here are some candidates: make_transform_range( r, fun ) transformed( r, fun ) transform( r, fun ) (*) transform_view( r, fun ) (*) was dislike by some because it has exactly the same spelling as the algorithm transform. Many felt that the confusion is too big if view generators are not named different from the actual algorithms. 6: reintroducing _if variants of algorithms =========================================== An important problem with the suggested approach was the the iterator returned by an algorithm after applying | filtered( pref ) are now filtered iterators and so one needs to manually unwrap the return iterator. This provided enough justification for reintroducing these algorithms. (One could imagine that this unwrapping was done automatically by a conversion operator such that iterator i = boost::find( r | boost::filtered( pred ), x ); "just worked". However, the syntax is still slightly worse than just using the original algorithm). Generic programming is concerned with the use of orthogonal concepts which put together yields all possible combinations of algorithms. If we reintroduce all _if algorithms, we have to aks ourselves "when does it end?". Should all new algorithms then simply add _if variants? This seems very much against the spirit of generic programming. The problem with the iterators being changed (as in the find example) seems to suggest the following guideline: "If the algorithm returns an iterator, it makes sense to provide an _if overload. Otherwise it does not." Under this guideline, find_if() should be there, but count_if() should not be provided. 7: should algorithms call member function when possible? ======================================================== I heard one strong voice against this. The reason was that the algorithm implemented as member function often has quite different guarantees w.r.t. complexity, reference and iterator stabililty. I think this is a very strong argument. Also, we can add this later if good arguments appear, but it is much harder to take away. We also have to remember Scott Meyers item "Beware of container independent code" which also suggest that this is a bad idea. At the very menimum, the original algorithm and the member function should have similar semantics. This seems to suggest that we can call set::lower_bound() from boost::lower_bound(). In that case, the best way would probably be to add these as overloads in the boost namespace: template< class T, class A > typename std::set<T,A>::iterator lower_bound( std::set<T,A>& s ); template< class T, class A > typename std::set<T,A>::const_iterator lower_bound( const std::set<T,A>& s ); 8: making return values of algorithms consistent/intuitive ========================================================== For example, sort(r) returns the sorted range, but sort_heap(r) does not. Similar issues for partial_sort(). Please go through all algorithms to see if this done correctly. 9: output range concept? ========================= It appears that the only use for an output iterator in the library was for boost::copy(rng,iter), and the only use for that function was for "sinks" like std::ostream_iterator<T>(...). This seems to be the only safety hole left in the library. Here's an idea to how we might remove that: create a new "copy sink" concept: struct array_copy_sink { ... template< class Iterator > copy( Iterator begin, Iterator end ) { ... } }; Then we might imagine boost::copy( rng, boost::ostream_sink(std::cout) ); boost::copy( rng, boost::array_sink(an_array) ); boost::copy( rng, boost::ptr_sink(begin,end) ); boost::copy( rng, boost::front_insert_sink(a_deque) ); ... For optimal performance, we also need a "nonoverlapping copy sink" concept, and an algorithm that expects that sink (or that boost::copy() determines the type of the sink automatically). 10: automatic projection ======================= Adope has algorithms overloaded such that projection is very easy: struct my_type { int member; double another_member; }; //... my_type a[] = { { 1, 2.5 }, ... }; // sort the array by the first member: sort(a, less(), &my_type::member); my_type* i = lower_bound(a, 5, less(), &my_type::member); We should be able to express this well, albeit not as concise, with my_type* i = boost::lower_bound( a | project( &my_type::member ), 5, less() ); where project( ... ) could simply return a transform iterator constructed with boost::bind(). There is another problem, however, because now the return value is a tranform_iterator of some form. Appending .base() would solve it, albeit it is somewhat ugly. Again this might raise the question of an implicit conversion. I just want to say this is not a critical issue as we can always add these overloads. --- End of Issues ---- Again, I would like to thank everybody that participated in the review. best regards Thorsten, review manager

2 1