[Bind] Interoperability of bind/mem_fn with transform_iterator
Hello all, I'm scratching my head about the correct way to use transform_iterator with bind and mem_fn. In brief, bind and mem_fn return object functions that are not Default Constructible, which means that, when used to construct a transform_iterator, the resulting transform_iterator is not even a Trivial Iterator. Most of the case, it's not a problem because the transform_iterator is never default constructed... until some libs that do concept checking on their template parameters are used. See the following code for exemple : #include <vector> #include <boost/bind.hpp> #include <boost/iterator/transform_iterator.hpp> #include <boost/iterator/iterator_concepts.hpp> #include <boost/concept/requires.hpp> struct foo { size_t id_; size_t get_id() const {return id_;} }; template <class ForwardIterator> void check(ForwardIterator _it) { using namespace boost; function_requires< boost_concepts::ForwardTraversalConcept<ForwardIterator> >(); } int main(int argc, char* argv[]) { using namespace boost; std::vector<foo> foo_vec; //Fail to compile since mem_fn is not Default Constructible check(make_transform_iterator( foo_vec.begin(), mem_fn(&foo::get_id))); //Fail to compile since mem_fn is not Default Constructible check(make_transform_iterator( foo_vec.begin(), mem_fn(&foo::id_))); return 0; } What would be the best way to handle the "problem" ? Patch the bind library to add some default constructors ? Best Regards, Samuel
On Fri, Apr 30, 2010 at 3:37 AM, Samuel Debionne <debionne@hydrowide.com> wrote:
Hello all, I'm scratching my head about the correct way to use transform_iterator with bind and mem_fn. In brief, bind and mem_fn return object functions that are not Default Constructible, which means that, when used to construct a transform_iterator, the resulting transform_iterator is not even a Trivial Iterator.
Most of the case, it's not a problem because the transform_iterator is never default constructed... until some libs that do concept checking on their template parameters are used. See the following code for exemple :
Right, mem_fn_t is not DefaultConstructible, so a transform_iterator with mem_fn_t does not model ForwardTraversalIterator. Likewise with the return type of bind, which c++0x requires to be MoveConstructible (and CopyConstructible when it's args are) but not DefaultConstructible. In your specific example, however, you can still build a valid ForwardTraversalIterator by using boost::function to erase the return type of mem_fn. The same should work with bind. check(make_transform_iterator( foo_vec.begin(), function<size_t(foo&)>(mem_fn(&foo::get_id)))); check(make_transform_iterator( foo_vec.begin(), function<size_t(foo&)>(mem_fn(&foo::id_)))); Daniel Walker
On Fri, Apr 30, 2010 at 3:37 AM, Samuel Debionne<debionne@hydrowide.com> wrote:
Hello all, I'm scratching my head about the correct way to use transform_iterator with bind and mem_fn. In brief, bind and mem_fn return object functions that are not Default Constructible, which means that, when used to construct a transform_iterator, the resulting transform_iterator is not even a Trivial Iterator.
Most of the case, it's not a problem because the transform_iterator is never default constructed... until some libs that do concept checking on their template parameters are used. See the following code for exemple :
Right, mem_fn_t is not DefaultConstructible, so a transform_iterator with mem_fn_t does not model ForwardTraversalIterator. Likewise with the return type of bind, which c++0x requires to be MoveConstructible (and CopyConstructible when it's args are) but not DefaultConstructible. In your specific example, however, you can still build a valid ForwardTraversalIterator by using boost::function to erase the return type of mem_fn. The same should work with bind.
check(make_transform_iterator( foo_vec.begin(), function<size_t(foo&)>(mem_fn(&foo::get_id))));
check(make_transform_iterator( foo_vec.begin(), function<size_t(foo&)>(mem_fn(&foo::id_))));
Daniel Walker
Daniel, thank you for your solution. But doesn't type erasure avoid some optimisations to take place (inlining) ? That could be a problem since the function is called each time the iterator is deferred. I just did some benchmarking that consists in accumulating a large range of foo id. Here are the results with vc10 : Boost.Function vs Hand Written : 9 time slower Boost.MemFn vs Hand Written : 3.7 time slower Boost.Function vs Boost.MemFn : 1.6 time slower Anyway, in my opinion, using bind/mem_fn/lambda with transform_iterator is a common use case. That would be great to have an option to add a default constructor in those libs... or is it to risky ? Samuel
On Mon, May 3, 2010 at 5:48 AM, Samuel Debionne <debionne@hydrowide.com> wrote:
On Fri, Apr 30, 2010 at 3:37 AM, Samuel Debionne<debionne@hydrowide.com> wrote:
Hello all, I'm scratching my head about the correct way to use transform_iterator with bind and mem_fn. In brief, bind and mem_fn return object functions that are not Default Constructible, which means that, when used to construct a transform_iterator, the resulting transform_iterator is not even a Trivial Iterator.
Most of the case, it's not a problem because the transform_iterator is never default constructed... until some libs that do concept checking on their template parameters are used. See the following code for exemple :
Right, mem_fn_t is not DefaultConstructible, so a transform_iterator with mem_fn_t does not model ForwardTraversalIterator. Likewise with the return type of bind, which c++0x requires to be MoveConstructible (and CopyConstructible when it's args are) but not DefaultConstructible. In your specific example, however, you can still build a valid ForwardTraversalIterator by using boost::function to erase the return type of mem_fn. The same should work with bind.
check(make_transform_iterator( foo_vec.begin(), function<size_t(foo&)>(mem_fn(&foo::get_id))));
check(make_transform_iterator( foo_vec.begin(), function<size_t(foo&)>(mem_fn(&foo::id_))));
Daniel Walker
Daniel, thank you for your solution. But doesn't type erasure avoid some optimisations to take place (inlining) ?
Not necessarily. All of boost::function can be inlined. I suppose results may vary according to your particular compiler's optimization strategy, but it is not immediately clear to me that boost::function precludes any optimizations.
That could be a problem since the function is called each time the iterator is deferred. I just did some benchmarking that consists in accumulating a large range of foo id. Here are the results with vc10 :
Boost.Function vs Hand Written : 9 time slower Boost.MemFn vs Hand Written : 3.7 time slower Boost.Function vs Boost.MemFn : 1.6 time slower
A code sample that demonstrates these performance changes would be more informative.
Anyway, in my opinion, using bind/mem_fn/lambda with transform_iterator is a common use case. That would be great to have an option to add a default constructor in those libs... or is it to risky ?
Well, the downside of default constructible call wrappers is that certain errors are hard to detect prior to runtime; i.e. a default constructed call wrapper would throw a bad_function_call when invoked. When you use a mem_fn or bind object, you know you won't get those sorts of exceptions at runtime, since neither are default constructible. However, boost::function _is_ default constructible. Consequentially, it gives users a way to make that trade-off in some situations; i.e to sacrifice some compile time error detection in favor of more runtime error detection. With respect to transform_iterator, boost::function can bridge the conceptual gap between non-default constructible call wrappers and iterators, which are necessarily default constructible. Daniel Walker
Daniel, thank you for your solution. But doesn't type erasure avoid some optimisations to take place (inlining) ?
Not necessarily. All of boost::function can be inlined. I suppose results may vary according to your particular compiler's optimization strategy, but it is not immediately clear to me that boost::function precludes any optimizations.
That could be a problem since the function is called each time the iterator is deferred. I just did some benchmarking that consists in accumulating a large range of foo id. Here are the results with vc10 :
I meant to say deferenced, not defered. But I think you understood.
Boost.Function vs Hand Written : 9 time slower Boost.MemFn vs Hand Written : 3.7 time slower Boost.Function vs Boost.MemFn : 1.6 time slower
A code sample that demonstrates these performance changes would be more informative.
I attached the code that produces these numbers. I compiled the code with visual studio express 2010 in release mode with the default options. The benchmark accumulates a range of number, where the numbers are accessed through a member function (see class foo). The following versions are compared : 1. hand written loop 2. std::accumulate with hand written member function call wrapper 3. std::accumulate with boost::mem_fn call wrapper 4. std::accumulate with boost::function call wrapper 5. std::for_each with a c0x lambda There are a few interesting things : - 1, 2, 5 are the fastest (about the same speed) - using boost::mem_fn (3) really makes a difference (3 times slower) - using boost::function (4) makes things a little bit worse (4.5 times slower)
Anyway, in my opinion, using bind/mem_fn/lambda with transform_iterator is a common use case. That would be great to have an option to add a default constructor in those libs... or is it to risky ?
Well, the downside of default constructible call wrappers is that certain errors are hard to detect prior to runtime; i.e. a default constructed call wrapper would throw a bad_function_call when invoked. When you use a mem_fn or bind object, you know you won't get those sorts of exceptions at runtime, since neither are default constructible. However, boost::function _is_ default constructible. Consequentially, it gives users a way to make that trade-off in some situations; i.e to sacrifice some compile time error detection in favor of more runtime error detection. With respect to transform_iterator, boost::function can bridge the conceptual gap between non-default constructible call wrappers and iterators, which are necessarily default constructible.
So, boost::function is definitely the solution. In the context of transform_iterator, it could be interesting to "systematically" wrap unary function objects that have no trivial constructor with boost::function so that the resulting iterator models the expected concept. A proposed implementation that uses the has_trivial_constructor trait is in the attached file. What about a warning in the usage section of the documentation of transform_iterator ? Samuel Debionne
Make your std::vector a global static variable or the compiler may fidn fun to remove all the hand-written code applied to it if no other operation liek i/o or whatever are done, thus giving you very fast execution time for no reason -- ___________________________________________ Joel Falcou - Assistant Professor PARALL Team - LRI - Universite Paris Sud XI Tel : (+33)1 69 15 66 35
Make your std::vector a global static variable or the compiler may fidn fun to remove all the hand-written code applied to it if no other operation liek i/o or whatever are done, thus giving you very fast execution time for no reason
Joel, thank you for the tip, I'm no benchmark expert. I made the change you suggest. It seems that the penalty is a bit less for boost::mem_fn (2.3 times slower) while boost::function remain 4.5 times slower. Samuel Debionne
Samuel Debionne:
Anyway, in my opinion, using bind/mem_fn/lambda with transform_iterator is a common use case. That would be great to have an option to add a default constructor in those libs... or is it to risky ?
The proper fix would be to make transform_iterator not require a default-constructible function object, by using boost::optional or an equivalent.
On Tue, May 4, 2010 at 1:49 PM, Peter Dimov <pdimov@pdimov.com> wrote:
Samuel Debionne:
Anyway, in my opinion, using bind/mem_fn/lambda with transform_iterator is a common use case. That would be great to have an option to add a default constructor in those libs... or is it to risky ?
The proper fix would be to make transform_iterator not require a default-constructible function object, by using boost::optional or an equivalent.
That's a great idea! I took a look at it, and the required changes seem to be minor. I made a ticket and attached a patch. https://svn.boost.org/trac/boost/ticket/4189 I ran Boost.Iterator regression tests with gcc 4.2 and it passed without error. Daniel Walker
On 5/4/2010 3:49 PM, Daniel Walker wrote:
On Tue, May 4, 2010 at 1:49 PM, Peter Dimov<pdimov@pdimov.com> wrote:
Samuel Debionne:
Anyway, in my opinion, using bind/mem_fn/lambda with transform_iterator is a common use case. That would be great to have an option to add a default constructor in those libs... or is it to risky ?
The proper fix would be to make transform_iterator not require a default-constructible function object, by using boost::optional or an equivalent.
That's a great idea! I took a look at it, and the required changes seem to be minor. I made a ticket and attached a patch. https://svn.boost.org/trac/boost/ticket/4189 I ran Boost.Iterator regression tests with gcc 4.2 and it passed without error.
Daniel Walker
Maybe you should only conditionally wrap in a boost::optional, e.g., if has_trivial_constructor<F> is false (I don't think there's a standard is_default_constructible trait, right?). - Jeff
On Tue, May 4, 2010 at 6:55 PM, Jeffrey Lee Hellrung, Jr. <jhellrung@ucla.edu> wrote:
On 5/4/2010 3:49 PM, Daniel Walker wrote:
On Tue, May 4, 2010 at 1:49 PM, Peter Dimov<pdimov@pdimov.com> wrote:
Samuel Debionne:
Anyway, in my opinion, using bind/mem_fn/lambda with transform_iterator is a common use case. That would be great to have an option to add a default constructor in those libs... or is it to risky ?
The proper fix would be to make transform_iterator not require a default-constructible function object, by using boost::optional or an equivalent.
That's a great idea! I took a look at it, and the required changes seem to be minor. I made a ticket and attached a patch. https://svn.boost.org/trac/boost/ticket/4189 I ran Boost.Iterator regression tests with gcc 4.2 and it passed without error.
Daniel Walker
Maybe you should only conditionally wrap in a boost::optional, e.g., if has_trivial_constructor<F> is false
What would that gain? It's a little hairy to implement on old compilers. I'm not sure that it's worth it.
(I don't think there's a standard is_default_constructible trait, right?).
Not to my knowledge. Daniel Walker
On 05/04/2010 06:20 PM, Daniel Walker wrote:
On Tue, May 4, 2010 at 6:55 PM, Jeffrey Lee Hellrung, Jr. <jhellrung@ucla.edu> wrote:
On 5/4/2010 3:49 PM, Daniel Walker wrote:
On Tue, May 4, 2010 at 1:49 PM, Peter Dimov<pdimov@pdimov.com> wrote:
Samuel Debionne:
Anyway, in my opinion, using bind/mem_fn/lambda with transform_iterator is a common use case. That would be great to have an option to add a default constructor in those libs... or is it to risky ?
The proper fix would be to make transform_iterator not require a default-constructible function object, by using boost::optional or an equivalent.
That's a great idea! I took a look at it, and the required changes seem to be minor. I made a ticket and attached a patch. https://svn.boost.org/trac/boost/ticket/4189 I ran Boost.Iterator regression tests with gcc 4.2 and it passed without error.
Daniel Walker
Maybe you should only conditionally wrap in a boost::optional, e.g., if has_trivial_constructor<F> is false
What would that gain? It's a little hairy to implement on old compilers. I'm not sure that it's worth it.
The gain is you don't have to pay the cost of a boolean in space. The boolean also has to be checked upon assignment and copy construction, so there is some amount of additional runtime overhead. What is "it" in "it's a little hairy to implement on old compilers"? The has_trivial_constructor metafunction, or a has_trivial_constructor-aware transform_iterator? For the former, I'd believe it, but I would expect the Boost.TypeTraits version to be good enough. For the latter, (and I could be very very wrong here, but) seems like the only thing you have to do is put an indirection layer when calling the function held by the transform_iterator, e.g., unwrap_optional(f)( ...args... ). In fact, there may be such a function provided by Boost.Optional... - Jeff
On Tue, May 4, 2010 at 11:59 PM, Jeffrey Lee Hellrung, Jr. <jhellrung@ucla.edu> wrote:
On 05/04/2010 06:20 PM, Daniel Walker wrote:
On Tue, May 4, 2010 at 6:55 PM, Jeffrey Lee Hellrung, Jr. <jhellrung@ucla.edu> wrote:
On 5/4/2010 3:49 PM, Daniel Walker wrote:
On Tue, May 4, 2010 at 1:49 PM, Peter Dimov<pdimov@pdimov.com> wrote:
Samuel Debionne:
Anyway, in my opinion, using bind/mem_fn/lambda with transform_iterator is a common use case. That would be great to have an option to add a default constructor in those libs... or is it to risky ?
The proper fix would be to make transform_iterator not require a default-constructible function object, by using boost::optional or an equivalent.
That's a great idea! I took a look at it, and the required changes seem to be minor. I made a ticket and attached a patch. https://svn.boost.org/trac/boost/ticket/4189 I ran Boost.Iterator regression tests with gcc 4.2 and it passed without error.
Daniel Walker
Maybe you should only conditionally wrap in a boost::optional, e.g., if has_trivial_constructor<F> is false
What would that gain? It's a little hairy to implement on old compilers. I'm not sure that it's worth it.
The gain is you don't have to pay the cost of a boolean in space. The boolean also has to be checked upon assignment and copy construction, so there is some amount of additional runtime overhead.
Thanks for the clarification. That seems like reasonable justification for the change.
What is "it" in "it's a little hairy to implement on old compilers"? The has_trivial_constructor metafunction, or a has_trivial_constructor-aware transform_iterator? For the former, I'd believe it, but I would expect the Boost.TypeTraits version to be good enough. For the latter, (and I could be very very wrong here, but) seems like the only thing you have to do is put an indirection layer when calling the function held by the transform_iterator, e.g., unwrap_optional(f)( ...args... ). In fact, there may be such a function provided by Boost.Optional...
Boost.Optional doesn't have an unwrap that I could find. I uploaded a new patch that conditionally uses optional based on has_trivial_constructor per your suggestion. It has a simple unwrap that should suffice. It passes regressions with gcc 4.2. My concern with older compilers is that I know the authors of Boost.Iterator went to some effort to support deficient compilers, but, unfortunately, I am unable to test this patch on nearly as many. Still, this is a start at least. Daniel Walker
Le 05/05/2010 00:55, Jeffrey Lee Hellrung, Jr. a écrit :
On 5/4/2010 3:49 PM, Daniel Walker wrote:
On Tue, May 4, 2010 at 1:49 PM, Peter Dimov<pdimov@pdimov.com> wrote:
Samuel Debionne:
Anyway, in my opinion, using bind/mem_fn/lambda with transform_iterator is a common use case. That would be great to have an option to add a default constructor in those libs... or is it to risky ?
The proper fix would be to make transform_iterator not require a default-constructible function object, by using boost::optional or an equivalent.
That's a great idea! I took a look at it, and the required changes seem to be minor. I made a ticket and attached a patch. https://svn.boost.org/trac/boost/ticket/4189 I ran Boost.Iterator regression tests with gcc 4.2 and it passed without error.
Daniel Walker
Maybe you should only conditionally wrap in a boost::optional, e.g., if has_trivial_constructor<F> is false (I don't think there's a standard is_default_constructible trait, right?).
I add a boost::optional use case in my "benchmark" and, performance wise, boost::optional is a much better option than boost::function to wrap non Default Constructible object function. I would say the game isn't worth the candle to wrap it conditionnaly, at least under vc10. I used the following wrapper : template <class UnaryFunc> struct optional_function { optional_function() {} optional_function(UnaryFunc _func) : func_(_func) {} template <class Arg1> struct result {typedef typename boost::result_of<UnaryFunc(Arg1)>::type type;}; template <class Arg1> typename result<Arg1>::type operator()(Arg1 _a1) const {return (*func_)(_a1);} boost::optional<UnaryFunc> func_; }; template <class UnaryFunc> optional_function<UnaryFunc> make_optional_function(UnaryFunc _func) {return optional_function<UnaryFunc>(_func);} Note that, to use a polymorphic object function like optional_function with transform_iterator, you need to apply the patch I suggested in https://svn.boost.org/trac/boost/ticket/1427 Finally, for my use case, the definitive solution is fast_mem_fn, an example of the function_type library. It's inlinable (and correctly inlined by vc10) and Default Constructible without the draw back of undefined runtime behaviour. I believe that this example could be a seed of a premium Boost library. Samuel Debionne
participants (5)
-
Daniel Walker -
Jeffrey Lee Hellrung, Jr. -
joel falcou -
Peter Dimov -
Samuel Debionne