- Boost - lists.boost.org

[xint] review
by Phil Endecott 10 Mar '11

10 Mar '11

Dear All, Here is my review of the proposed XInt library. There seem to be several issues with the design of this library; all have been discussed before at length so I will simply summarise: 1. Performance of small and fixed-length integers is poor. This could be resolved by storing fixed-length values on the stack, or by using some sort of small buffer optimisation. 2. There is no assembler, and there are no "hooks" in the implementation where a contributor could insert assembler fragments for critical code. 3. Performance is hindered by the creation of temporaries in expressions such as a = b+c+d+e; a system of expression templates that allowed the expression to be computed "slicewise" would eliminate the need for temporaries. 4. The interface is not very generic; for example the is_(probably)_prime function cannot be used on a regular int; the implementation operates on the internal representation of the integer for no apparent reason. (If the reason is performance, then that itself indicates a deficiency in the interface.) (Aside: I feel that is_(probably)_prime would be better in Boost.Math, which is apparently already organised into sub-libraries.) Also the basic algorithms (addition, multiplication...) are not generic, i.e. they cannot be used other than on the provided integer type (this would matter much less if the provided type were more performant). 5. Although I don't have strong views either way on COW, I do feel that in 2011 we should focus primarily on thread-safe code i.e. single-thread code is now the special case, not the norm. So if COW is to be used it should be thread-safe COW. 6. Apparently sign-magnitude is used without tweaks for bitwise operations, giving "wrong" answers for negatives (in contrast to e.g. GMP which stores sign-mag yet gives "right" answers, IIUC). 7. Choice of algorithms for some operations (e.g. sqrt) seems to have poor big-O complexity. In view of these issues, I do not believe that this library should be accepted. I am not suggesting that all of these issues need to be fixed for the library to be acceptable. Boost libraries do not have to be perfect. I just believe that the current state is below the required threshold. Standard answers: - What is your evaluation of the design? See above. - What is your evaluation of the implementation? It seems reasonably bug-free. - What is your evaluation of the documentation? I'm not a huge fan of doxygen, but that's mostly my problem. The docs would benefit hugely from some benchmarks. - What is your evaluation of the potential usefulness of the library? I've never needed a large integer library. - Did you try to use the library? With what compiler? Did you have any problems? Yes, g++ (ARM Linux), no problems. - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? Two or three hours work, running benchmarks, reading a few bits of the source, and following the discussion. - Are you knowledgeable about the problem domain? More so now than a week ago, but fundamentally no. One final comment: many reviews end with some sort of "accepted subject to changes" result. This indicates some trust that the author would be able to make the required changes without further review. I do not believe that this would be appropriate in this case. Regards, Phil.

2 1

Fwd: Re: [move] You can do it better: implementing push_back and handling implicit conversions
by Jeffrey Lee Hellrung, Jr. 10 Mar '11

10 Mar '11

[My original reply went directly to Ion, due to me being cc'ed in the original email. Hence forwarding... (pun intended)] -------- Original Message -------- Subject: Re: [move] You can do it better: implementing push_back and handling implicit conversions Date: Tue, 08 Mar 2011 17:23:58 -0800 From: Jeffrey Lee Hellrung, Jr. <jhellrung(a)ucla.edu> Reply-To: jhellrung(a)ucla.edu To: Ion Gaztañaga <igaztanaga(a)gmail.com> On 3/8/2011 1:57 PM, Ion Gaztañaga wrote: > Hi to all, > > Are you a C++ expert? Do you like Boost.Move? I have a challenge for you. > > During Boost.Move review, Jeffrey Lee Hellrung suggested adding > "techniques to capture (implicitly created) rvalues with emulated rvalue > references in C++03, e.g., for push_back, when you have knowledge of the > types of objects you want to capture". Yes, you know, I do seem to remember suggesting that... > I've worked on this problem these days and the solution is less than > obvious (several compilers have has problems with > ::boost::is_convertible and non-copyable types). I found a solution > (attached test and required boost/move/move.hpp header) after several > tries but it's complex (it needs several overloads and enable_if tricks) > but I'm sure boosters will find a easier solution ;-) Yes, a bit more complex than the solution I've been using for a while now (rough idea attached and explained below). > Current solution seems to work on these compilers: MSVC 7.1, 8.0, 9.0, > Intel 11.0, GCC 4.3.4, 4.4, 4.4 c++0x mode, 4.5, 4.5 c++0x mode. I've gotten your test cpp to compile and run with no assertion failures on MSVC9 (with a slight modification to assertions; see below), and I've used this same technique on gcc, but I don't work nearly as much on gcc, so it may be that some corner cases fail. > Problem: MSVC 10.0 (Visual 2010) with real rvalue references seems to > have bugs and does not compile the test. I can't find a workaround, a > future Service Pack might solve these errors, but maybe we should stick > to emulation code in this compiler, unless someone could shed some light > on this, of course. Well...that sucks :( > Waiting your proposals, > > Ion Okay, here is the summary. Ion, I count 5 overloads of push_back in C++03 and 4 overloads in C++0x for your solution. I believe one can get by with just 3 overloads in C++03, and 1 in C++0x, but the path to "T construction" in my solution is a little bit different than yours. I delay any T construction until the placement new statement in priv_push_back. I don't know what your requirements are in general, but for push_back, I think this should be fine. The solution I sent you has maybe a slight disadvantage over yours in that conversion errors would likely end up pointing to priv_push_back, but if this is a concern, the template overloads of push_back can be restricted (further) with enable_if (I think). This has the effect that push_back'ing a conversion_source object x directly constructs the storage with x, rather than constructing a temporary and copying or constructing a temporary and moving. For push_back, it seems this is definitely desirable, and I'm having a hard time coming up with a situation where it is *not* desirable to delay the construction as long as possible. In any case, this explains the change in your assertions. I also added a Default value to the ConstructionType enum because...it was bugging me ;) The 3 overloads in C++03 are basically: // captures const lvalues and rvalues that are *not* T template< class U > typename boost::disable_if< is_same_sans_const_sans_reference<U,T> >::type push_back(const U& x) { ... as_lvalue(x) ... } // captures non-const lvalues and T lvalues template< class U > void push_back(U& x) { ... x ... } typedef typename add_reference_add_const< typename add_rvalue_reference<T>::type >::type rv_param_type; // captures T rvalues (if T is movable) void push_back(rv_param_type x) { ... x ... } In C++0x, a single overload is sufficient, I think: template< class U > void push_back(U&& x) { ... boost::forward<U>(x) ... } Let me know what you think of this framework. - Jeff

2 6

[XInt] Review
by Joachim Faulhaber 10 Mar '11

10 Mar '11

Dear Chad, Volodya, list, This is my review on the XInt library. On the outset I'd like to thank Chad for his work and stamina in providing the XInt library. It is not only a big effort to provide a portable, functional and well documented library like this, but it also takes a great deal of courage to undergo a review process on the boost list. As far as I can see from some tests and use cases the library is useful, functional, correct and portable. The library implements the interface that is about to be part of the new standard. So many things are looking good and independent of the final result of the review, XInt is already a valuable tool and a great contribution. While this is more than is needed for many purposes, I come to the conclusion that it is not enough for boost. Integer is a very central prototypical data structure that should be and will be expected to be a model for the design of other libraries. I expected its design to be very clear and simple and very flexible and generic at the same time. While I was looking more deeply into the code and structures of XInt I came more and more to the conclusion that the current design is insufficient for a boost library in general even more so for an Infinite Precision Integer Library. So my vote is NO for acceptance of XInt with its current design. Even though, I'd like to encourage Chad to solve the questions around concept based generic design for XInt and to resubmit his project, when design and other issues raised in this review are solved. Maybe a deal of patience and reflection and openness to the information provided by others was helpful. Maybe the person with the most unpleasant critique has the most valuable insights for you. At the same time I'd like to call on the boost community to support Chad and to see an Integer library as an opportunity to develop more common understanding how a state of the art generic design looks like in this specific case. Best regards, Joachim ============== Review Details ============== 1.1 Naming: Library =================== An unlimited integer is an int that is not limited to a size restriction. So it conforms the mathematical notion of an integer better than built in ints. My favorite name for such a library was Boost.Integer Where would a (new) user expect such a library, exactly there. IMO Boost.Integer is much better than Boost.Xint. Boost.Integer already exists. So why not integrate new (unlimited) integer types into Boost.Integer? For simple concise naming and intuitive structuring according to user expectations, that would be the best choice. 1.2 Naming: Namespace ===================== Components of Boost.Integer are relatively old and located directly within namespace boost. So for the new Integer library we can choose namespace integers completely consistent to the official boost naming conventions: http://www.boost.org/development/requirements.html#Naming_consistency which says: The library's primary namespace (in parent ::boost) is given that same name [as the library], except when there's a component with that name (e.g., boost::tuple), in which case the namespace name is *pluralized*. which is specifically consistent since we know that Chads Integer library offers *different* integer types such that declarations integers::pure<> i; // limitless "pure" integers integers::fixed<512> j; // limited to fixed size are pretty intuitve. 1.3 Naming: Types ================= What I like about boost, compared to many other libraries, is the culture of short and concise naming. This includes the absence of cryptic pre and suffixes. But there are exceptions. One of those is the _t suffix used for a variety of types, namely int<n>_t types from Boost.Integer. I am opposed to any pre or suffixing, since it is not inline with general boost naming conventions, that discourages cryptic names or name components. My guess is that the _t suffix has been chosen as an emergency measure once: The name of choice had been used already and overloading was not possible. Where no such conflict is present, I propose to use concise and simple names without pre or suffixes. One of the reasons why I dislike pre/suffixes is that they are cryptic abbreviations most of the time. The second reason is that they, even if non cryptic, introduce useless redundancy: // "type" is used 5 times as pre or suffix typedef typename foo_type::key_type mykey_type; // instead of def foo::key mykey; // or type mykey = foo::key 2. Design ========= As other reviewers have pointed out before the design does not allow for decoupled integer types that can be models of integer concepts, such that appropriate sets of free standing functions will serve to operate on those types and the library can be extended for any other type that will be implemented as model of the integer concepts that the library defines. I think such a design would implement the ideas that can be found in [Järvi et.al. 2003, Concept Controlled Polymorphism] http://parasol.tamu.edu/~jarvi/papers/concept-controlled.pdf and that is implemented in modern boost libraries like e.g. Boost.Polygon. (Boost.Geometry is also a good example, but not so close to the Järvi paper) Because of its fundamental character, a general Boost.Integer should serve as a model, a prototype for other libraries and it should represent the current state of the art in this field. Because everyone understands integers, people will probably look at Boost's Integer design to understand modern design from a concise example. This is an opportunity and a challenge for the author but more so for the boost community. It could also be an opportunity to converge and synthesize different points of view in a prototypical design. The current design does not meet my requirements here. This is not a shortcoming of the author alone. In the discussions that have taken place around xint's design, the concept based paradigm and techniques obviously were not communicated in such a way that they found their way into a state of the art design. 2.2 Boost.Parameter considered unfavorable ========================================== Although flexible, the options feature based on Boost.Parameter comes with an unnecessary and undesired level of abstraction and indirection. It obfuscates the different kinds of parameters and makes the implementation much more difficult to read. Moreover the meta code involved with Boost.Parameter imposes a compile time penalty. IIUC all of the option parameters are compile time constants designed to steer implementation variants. There are much simpler and clearer ways to do that. Also integers::fixed<512> myVar; //is very intuitive, while xint::integer_t<xint::options::fixedlength<512> > myVar; // can't probably be done without consulting the docs // and it is more verbose 2.3 Policy based design ======================= I think policy based design is a very good and powerful technique that is specifically useful to separate implementation variants of class templates in clear and flexible ways. Unfortunately I can not see that you are actually using policy based design here. Because your design lacks typical policy classes that encapsulate implementation variants in a way that reduces codereplication and enhances flexibility. What your intended policy classes say, nan_functions<..>, only do is to encapsulate the functions that other implementation variants do not need. But this can be done by simple object inheritence alone. 2.4 Do we really want to be nanied ================================== Recently I met a guy named Larry from Huston Texas who introduced me to the notion of a nanny state. Germany, for example is a nanny state, because it imposes coercive health inshurance on its citizens. This may be totally unnecessary for some, who are always able to perform surgery on themselves. In a similar sense we could introduce the notion of a nany class, for thouse of us, who are not able to control their program logic ;-) To come to the point. I still don't really see the the indispensable benefits of nan and an exception free bigint class. We happiely work with ints for decades, that throw interrupts for division by zero. So why do we need a protection against that case that can be easily controlled through program logic? If we let go of the nan idea, everything is a great deal simpler and less ugly. The rationale given by the docs does not convince me either. 3. Implementation ================= 3.1. Codestyle ============== 3.1.1 Codestyle: Layout ======================= The library aheres to a restricion of a line length of 80 characters, which is still official boost policy. In many instances the lines are just broken before length 81 regardless of syntactical structure and readability. I dislike this coding style since it obscures structure and easy readability for no obvious reason. At some points the reader needs extra efforts to scan the text. E.g. the inheritence list of class template integer_t is an amorph textblock template<BOOST_XINT_INITIAL_APARAMS> class integer_t: virtual public detail::integer_t_data <BOOST_XINT_APARAMS>, public detail::nan_functions<detail:: integer_t_data<BOOST_XINT_APARAMS>::NothrowType::value, integer_t<BOOST_XINT_APARAMS>, BOOST_XINT_APARAMS>, public detail::fixed_functions<detail::integer_t_data <BOOST_XINT_APARAMS>::BitsType::value, integer_t <BOOST_XINT_APARAMS>, BOOST_XINT_APARAMS>, public detail::unsigned_negative_functions<detail::integer_t_data< BOOST_XINT_APARAMS>::SignType::value, BOOST_XINT_APARAMS> instead of a structured text template<BOOST_XINT_INITIAL_APARAMS> class integer_t: virtual public detail::integer_t_data<BOOST_XINT_APARAMS>, public detail::nan_functions < detail::integer_t_data<BOOST_XINT_APARAMS> ::NothrowType::value, integer_t<BOOST_XINT_APARAMS>, BOOST_XINT_APARAMS >, public detail::fixed_functions < detail::integer_t_data<BOOST_XINT_APARAMS> ::BitsType::value, integer_t<BOOST_XINT_APARAMS>, BOOST_XINT_APARAMS >, public detail::unsigned_negative_functions < detail::integer_t_data<BOOST_XINT_APARAMS> ::SignType::value, BOOST_XINT_APARAMS > that facilitates readability. 3.1.2 Codestyle: Filesize ========================= integer.hpp is too long. It should be separated in smaller named entities according to structural aspects. Filesizes can also be reduced by decomposition of the design and by reduction of redundancies and code replication. 3.1.3 Redundancies and Codereplication ====================================== There is a great deal of code replication in the current implementation of xint::integer_t. This code replication reflects the insufficient degree of decoupling of the libraries components. Not only is the code bloated by this. Also conditional expressions that are computable at compile time seem to be checked redundantly at runtime many times unless compilers are smart enough to optimize them away. But even if they do, as a developer I desire to write more elegant code in the first place and I try to use code replication as a guidepost to detect design flaws. template<BOOST_XINT_CLASS_APARAMS> integer_t<BOOST_XINT_APARAMS>& integer_t<BOOST_XINT_APARAMS> ::some_xint_fun (const integer_t<BOOST_XINT_APARAMS> b) { if (Nothrow) { if (b.is_nan()) data.make_nan(); if (!is_nan()) { BOOST_XINT_TRY { some_xint_fun(data, b.data);//#1 if (Threadsafe == true) data.make_unique(); } BOOST_XINT_CATCH { data.make_nan(); } } } else { some_xint_fun(data, b.data);//#2 if (Threadsafe == true) data.make_unique(); } return *this; } This skeleton (and some variations of it) occurs over and over again only to propagate the call of the function to the implementing class at positions #1 and #2. 3.2 Implementation issues ========================= 3.2.1 Operator template overloading conflicts ============================================= In integer.hpp 2399 and 2426, there are template macros with an unrestricted template parameter 'typename N' in template <typename N, BOOST_XINT_CLASS_APARAMS> this leads to ambiguities in overload resolution with other types that allow to combine values via operator o. icl::interval_set<xint::integer> xi_set; xint::integer xi; xi_set + xi; // Adds a single value Compilers say things like: constructor overload resolution was ambiguous. 3.2.2 Specialization of std::numerical_limits fails =================================================== When used with other Boost libraries, namely Boost.Rational and Boost.Icl metacode using std::numeric_limits fails: BOOST_AUTO_TEST_CASE(xint_and_rational) { rational<xint::integer> xrat; //error C2975: 'x' : invalid template argument for //'boost::STATIC_ASSERTION_FAILURE' //boost/rational.hpp (127) //BOOST_STATIC_ASSERT( ::std::numeric_limits<IntType>::is_specialized ); //Although is_specialized is defined in integer.hpp(2605) } I used msvc-9. I looks as if the compiler fails to recognize the code template<BOOST_XINT_CLASS_APARAMS> const bool numeric_limits<boost::xint::integer_t<BOOST_XINT_APARAMS> >:: is_specialized = true; as proper compile time constant. When assigned directly with the declaration, it works. xint/integer.h (2543) static const bool is_specialized = true; Unfortunately a similar problem occurs with numeric_limits<T>::digits //-------------------------------------------------------------- //Problems with constants from std::numeric_limits template <class Type> struct test_is_fixed_numeric { typedef test_is_fixed_numeric type; BOOST_STATIC_CONSTANT(bool, value = (0 < std::numeric_limits<Type>::digits)); //rev_xint.cpp(49) : error C2057: expected constant expression }; BOOST_AUTO_TEST_CASE(xint_std_numeric_limits) { typedef xint::integer_t<options::fixedlength<8> > fixn8; BOOST_CHECK_EQUAL(test_is_fixed_numeric<fixn8>::value, true); } //-------------------------------------------------------------- 3.2.3 Specialization of boost::is_integral<T> ============================================= You'd have to provide an instantiation of boost type trait boost::is_integral for xint::integral_t, so meta code that is implemented for all intergal types will be able to work with xint instantly. -- Interval Container Library [Boost.Icl] http://www.joachim-faulhaber.de

4 5

[MPL] Maintenance, patch applciation etc
by Joel Falcou 10 Mar '11

10 Mar '11

As a huge user of MPL all along, i'm a bit saddened by the speed of patching/evolution of the thingy. Currently there is 36 trac item on MPL and I remember a page with a ncie list of future work to go to. Instead of bitching around, i want to propose me as a "co-maintainer" or w/e the proper term is. I have a small amount of free time i want to dedicate to this. So here is the proposal ;)

6 9

[Review] Phoenix V3: review results
by Hartmut Kaiser 09 Mar '11

09 Mar '11

All, The review of Phoenix V3 ended on March 2nd. We've got quite some discussion, even if we hoped for more. Overall, 3 people have confirmed that the Phoenix rewrite addresses all issues raised during the original review back in 2008. Nobody raised any concerns or serious issues. So here is the result of the mini-review: Boost.Phoenix is ready to be moved to the Boost SVN trunk! All other discussions were about minor inconsistencies, which Thomas has already fixed by now. There are a couple of suggestions related to the documentation, which he agreed to address as soon as possible: 1) The Phoenix documentation should have a "What's New" section 2) Compile time is often a concern with libraries that make heavy use of expression templates. Adding a compile time test would be ideal. This should be easily invoked and results from various compilers reported within the documentation. The only thing, which needs to be decided (and which has not been discussed yet) is how the migration from Boost.Bind, Boost.Lambda, and Phoenix V2 has to be organized, ensuring minimal disruption for the users of those libraries. I see several possible ways of doing so, but would like to open up the discussion. Any suggestions and comments are welcome. With high likelihood this migration process will be implemented using forwarding headers. Therefore, this point has not to be resolved before moving the main code base to trunk. On the other hand, this migration strategy needs to be in place before merging to the release branch. -------------------- This mini-review wraps up the review process of Boost.Phoenix. Congratulations to Thomas for this version of the excellent library, which will contribute to the unification of the functional landscape in Boost. At the same time I would like to mention a couple of names which are related to the development of Phoenix since its inception, and without those Boost.Phoenix wouldn't have happened. - Joel de Guzman, who wrote the initial V1 and since then was actively involved and driving the development of Boost.Phoenix - Dan Marsden, who is the main developer (with Joel) of Phoenix V2 - Angus Leeming and Daniel Wallin who contributed to V2 - Eric Niebler, the author of Boost.Proto, who contributed to V2 and was actively driving and supporting the development of V3, he also mentored Thomas Heller's GSoC project. Regards Hartmut Review Manager --------------- http://boost-spirit.com

6 5

[config][clang] Does <boost/config/compiler/clang.hpp> need updating?
by Beman Dawes 09 Mar '11

09 Mar '11

http://clang.llvm.org/cxx_status.html now has a table for C++0x features. rvalue references, variadic templates, and static_asserts are showing as green. Does <boost/config/compiler/clang.hpp> need updating? Is there a maintainer for <boost/config/compiler/clang.hpp>? --Beman

6 15

[move] You can do it better: implementing push_back and handling implicit conversions
by Ion Gaztañaga 09 Mar '11

09 Mar '11

Hi to all, Are you a C++ expert? Do you like Boost.Move? I have a challenge for you. During Boost.Move review, Jeffrey Lee Hellrung suggested adding "techniques to capture (implicitly created) rvalues with emulated rvalue references in C++03, e.g., for push_back, when you have knowledge of the types of objects you want to capture". I've worked on this problem these days and the solution is less than obvious (several compilers have has problems with ::boost::is_convertible and non-copyable types). I found a solution (attached test and required boost/move/move.hpp header) after several tries but it's complex (it needs several overloads and enable_if tricks) but I'm sure boosters will find a easier solution ;-) Current solution seems to work on these compilers: MSVC 7.1, 8.0, 9.0, Intel 11.0, GCC 4.3.4, 4.4, 4.4 c++0x mode, 4.5, 4.5 c++0x mode. Problem: MSVC 10.0 (Visual 2010) with real rvalue references seems to have bugs and does not compile the test. I can't find a workaround, a future Service Pack might solve these errors, but maybe we should stick to emulation code in this compiler, unless someone could shed some light on this, of course. Waiting your proposals, Ion

3 6

[iostreams][filesystem] v3 adapter uploaded to ticket #4485
by Jeff Flinn 09 Mar '11

09 Mar '11

I've uploaded an adapter allowing filesystem V3 path to be passed to the iostreams library constructors and methods taking paths. I'm using it with boost 1.44 on MSVC8 and Xcode3.1.2 with gcc4.0.1. It currently requires that BOOST_FILESYSTEM_VERSION is defined to be 3, and that users manually use the adapter like: #include <boost/iostreams/device/mapped_file.hpp> #include <boost/iostreams/filesystem_v3_path_adapter.hpp> ... boost::filesystem::path p(...); namespace io = boost::iostreams; io::mapped_file_source mf_src(io::filesystem_v3_path_adapter(p)); Filesystem V3 is deprecated in the upcoming boost 1.47, and will NOT be included in boost 1.48. Has anyone started updating iostreams to account for the removal of filesystem V2? IIRC, Steven Watanabe has been doing some iostreams maintenance. It looks like Jonathan Turkanis is no longer around, is there a new iostreams maintainer? I can take this on if no one else is/has. In my view, and as a few others have stated as well, filesystem V3 path is the common/portable path currency in boost today. The iostreams interface/implementation can be simplified by utilizing path's portability. The windows implementation would always call CreateFileW passing path.wstring().c_str. Thoughts? Thanks, Jeff

2 1

Boost.Thread: Support for variadic templates
by Daniel Neuberger 09 Mar '11

09 Mar '11

Are there plans for Boost.Thread to support variadic templates sometime soon? We'd use c++0x, but it looks like there's no plan to support timed_join and interruption/cancellation. Will Boost.Thread continue to do so though or is there something I'm missing in regards to c++0x? Thanks! - Daniel P.S. I asked basically the same question on the boost user list, but go no response. See http://thread.gmane.org/gmane.comp.lib.boost.user/66171.

2 3

[spirit] alert when backtracking?
by Arno Schödl 09 Mar '11

09 Mar '11

Hello, is there any way to detect at runtime or compile time whether Boost.Spirit needs backtracking? It would be nice to be alerted to the fact that the grammar is not LL(1) and thus has potential for optimization. Regards, Arno -- Dr. Arno Schödl | aschoedl(a)think-cell.com Technical Director think-cell Software GmbH | Chausseestr. 8/E | 10115 Berlin | Germany http://www.think-cell.com | phone +49 30 666473-10 | US phone +1 800 891 8091 Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl

4 7