std::function optimization

Discussion in 'C++' started by Matt Fioravante, Feb 21, 2013.

  1. I have this function defined:

    bool walk_directory_tree(const char* dirname,
    std::function<bool(const char*, const char*)> cb,
    bool recurse=false,
    const char* match_suffix=nullptr,
    bool returndots=false);

    In this particular case, the std::function object never outlives its caller.
    Therefore we would like to pass it a reference instead of a full function
    object to save on copies and possible memory allocation.

    An example call would be:
    auto cb = [&](const char* full, const char* base) { //lots of stuff };
    walk_directory_tree("some/directory/path", std::cref(cb));

    With std::cref, the lambda is passed into the function object by reference
    instead of by value. Since the lambda exists for the lifetime of the
    walk_directory_tree() call, this is always safe to do.

    My question is there any way to make it so that the std::function object always
    takes its argument by reference without requiring the caller to remember to do
    std::ref or std::cref? I don't see any possible use case here for pass by
    value.

    Or am I not understanding something about std::function?
     
    Matt Fioravante, Feb 21, 2013
    #1
    1. Advertising

  2. Matt Fioravante

    Luca Risolia Guest

    On 21/02/2013 02:35, Matt Fioravante wrote:
    > I have this function defined:
    >
    > bool walk_directory_tree(const char* dirname,
    > std::function<bool(const char*, const char*)> cb,
    > bool recurse=false,
    > const char* match_suffix=nullptr,
    > bool returndots=false);
    >
    > In this particular case, the std::function object never outlives its caller.
    > Therefore we would like to pass it a reference instead of a full function
    > object to save on copies and possible memory allocation.
    >
    > An example call would be:
    > auto cb = [&](const char* full, const char* base) { //lots of stuff };
    > walk_directory_tree("some/directory/path", std::cref(cb));
    >
    > With std::cref, the lambda is passed into the function object by reference
    > instead of by value. Since the lambda exists for the lifetime of the
    > walk_directory_tree() call, this is always safe to do.
    >
    > My question is there any way to make it so that the std::function object always
    > takes its argument by reference without requiring the caller to remember to do
    > std::ref or std::cref? I don't see any possible use case here for pass by
    > value.
    >
    > Or am I not understanding something about std::function?


    std::cref generates an object of type std::reference_wrapper, so in your
    case the std::function object will be built from the (temporary)
    reference_wrapper. So I don't clearly see any benefits in building and
    moving a wrapper compared to copying the callable object directly. Since
    the types of lambda-expressions are unique, if you really think that
    passing them by reference makes any difference in terms of efficiency,
    you could try to get rid of the std::function parameter type and make
    your walk_directory_tree() a function template accepting references to
    lambdas.
     
    Luca Risolia, Feb 21, 2013
    #2
    1. Advertising

  3. Matt Fioravante

    SG Guest

    On Feb 21, 2:35 am, Matt Fioravante wrote:
    > I have this function defined:
    >
    > bool walk_directory_tree(const char* dirname,
    > std::function<bool(const char*, const char*)> cb,
    > bool recurse=false,
    > const char* match_suffix=nullptr,
    > bool returndots=false);
    >
    > In this particular case, the std::function object never outlives its caller.
    > Therefore we would like to pass it a reference instead of a full function
    > object to save on copies and possible memory allocation.
    >
    > An example call would be:
    > auto cb = [&](const char* full, const char* base) { //lots of stuff };
    > walk_directory_tree("some/directory/path", std::cref(cb));


    This seems to be a bad example because the size of the lambda should
    be rather small and it is efficiently copyable. So, in this case,
    there is actually no reason to add an extra layer of indirection.

    > With std::cref, the lambda is passed into the function object by reference
    > instead of by value. Since the lambda exists for the lifetime of the
    > walk_directory_tree() call, this is always safe to do.


    Yes, it's safe. But I suggest that you actually do some profiling. I
    can only come up with one scenario where your example would benefit
    from this extra layer of indirection: It's when a compiler is not able
    to optimize the size of a lambda with [&] capture and hence the lambda
    object includes the addresses of all the local variables you use
    (instead of just a single stack frame pointer) so that the SFO (small
    function optimization) of std::function won't kick in. Without SFO
    std::function will create a copy of your functor on the free store
    instead of inside itself.

    > My question is there any way to make it so that the std::function object
    > always takes its argument by reference without requiring the caller to
    > remember to do std::ref or std::cref? I don't see any possible use case
    > here for pass by value.


    You do realize that the "value" in case of a lambda which captures its
    variables by reference is effectivly like a reference since it just
    stores one (or more adresses), right?

    If, however, your compiler is not able to keep the size of this lambda
    expression small enough (because your vendor hasn't yet included the
    stack frame pointer optimization) std::ref sounds like an option.

    I assume that you can't turn your function into a template like this:

    template<class Func>
    inline bool walk_directory_tree(
    const char* dirname,
    Func && cb,
    bool recurse=false,
    const char* match_suffix=nullptr,
    bool returndots=false)
    {
    ...
    }

    because you want the implementation to reside in a cpp file rather
    than a header file (otherwise it would be THE solution to avoid any
    unnecessary overheads).

    In this case, you could write a function template as a wrapper in your
    header file that adds std::ref and invokes your other function:

    bool walk_directory_tree(
    const char* dirname,
    std::function<bool(const char*, const char*)> cb,
    bool recurse=false,
    const char* match_suffix=nullptr,
    bool returndots=false); // implemented somewhere else

    template<class Func>
    inline bool walk_directory_tree(
    const char* dirname,
    Func && cb,
    bool recurse=false,
    const char* match_suffix=nullptr,
    bool returndots=false)
    {
    return walk_directory_tree(
    dirname,
    std::function<bool(const char*, const char*)>(std::ref(cb)),
    recurse,match_suffix,returndots
    );
    }

    Cheers!
    SG
     
    SG, Feb 21, 2013
    #3
  4. On Thursday, February 21, 2013 8:15:16 AM UTC-5, SG wrote:
    > This seems to be a bad example because the size of the lambda should
    > be rather small and it is efficiently copyable. So, in this case,
    > there is actually no reason to add an extra layer of indirection.


    I guess thats the tradeoff huh? An extra pointer dereference vs compact storage.

    > > With std::cref, the lambda is passed into the function object by reference
    > > instead of by value. Since the lambda exists for the lifetime of the
    > > walk_directory_tree() call, this is always safe to do.

    >
    >
    > Yes, it's safe. But I suggest that you actually do some profiling. I
    > can only come up with one scenario where your example would benefit
    > from this extra layer of indirection: It's when a compiler is not able
    > to optimize the size of a lambda with [&] capture and hence the lambda
    > object includes the addresses of all the local variables you use
    > (instead of just a single stack frame pointer) so that the SFO (small
    > function optimization) of std::function won't kick in. Without SFO
    > std::function will create a copy of your functor on the free store
    > instead of inside itself.


    The free store allocation is exactly what I want to avoid. This seems rather
    tricky considering that the size of the pre-allocated storage in the
    std::function object varies from implementation to implementation and there
    doesn't appear to be any way to automatically check. You're right that the only
    real way to handle this is to debug it yourself and see what the compiler does.

    It would be nice if there was some way to automagically at compile time do
    something like the following:

    auto cb = [](const char* full, const char* partial) { //stuff };
    if(sizeof(cb) > std::function::max_size_without_heap_alloc) {
    walk_directory_tree("path", std::cref(cb));
    } else {
    walk_directory_tree("path", cb);
    }

    Might it be safe to assume std::functions's storage most likely large enough
    on most modern platforms (gcc, clang, msvc) to store lambdas with requiring a
    memory allocation?

    Other than copying local variables by value, are there any other common cases
    or heuristics to follow where capture clauses might create a large lambda? I
    imagine even if you capture a couple local variables like [&a, &b], the lambda
    could still just grab a single pointer to the stack frame.

    > > My question is there any way to make it so that the std::function object
    > > always takes its argument by reference without requiring the caller to
    > > remember to do std::ref or std::cref? I don't see any possible use case
    > > here for pass by value.

    >
    > You do realize that the "value" in case of a lambda which captures its
    > variables by reference is effectivly like a reference since it just
    > stores one (or more adresses), right?


    Yes, copying a few pointers is no problem, heap allocation potentially is.

    > If, however, your compiler is not able to keep the size of this lambda
    > expression small enough (because your vendor hasn't yet included the
    > stack frame pointer optimization) std::ref sounds like an option.




    > I assume that you can't turn your function into a template like this:
    >
    > template<class Func>
    > inline bool walk_directory_tree(
    > const char* dirname,
    > Func && cb,
    > bool recurse=false,
    > const char* match_suffix=nullptr,
    > bool returndots=false)
    > {
    > ...
    >
    >
    > because you want the implementation to reside in a cpp file rather
    > than a header file (otherwise it would be THE solution to avoid any
    > unnecessary overheads).


    That's exactly why I used std::function. I don't want this function in header
    files which makes them less readable and slows down compile times. I also don't
    want the compiler to stamp out 20 different versions of the function for 20
    different uses with 20 different lambdas.

    > In this case, you could write a function template as a wrapper in your
    > header file that adds std::ref and invokes your other function:


    That sounds like the start of a good solution to the problem I posed earlier
    about checking the size of the function object and automatically choosing
    whether or not to use a std::cref. There doesn't appear to be any compile-time
    way of getting the SFO max size though. Perhaps such a thing should be added to
    the standard.

    >
    > bool walk_directory_tree(
    > const char* dirname,
    > std::function<bool(const char*, const char*)> cb,
    > bool recurse=false,
    > const char* match_suffix=nullptr,
    > bool returndots=false); // implemented somewhere else
    >
    >
    > template<class Func>
    > inline bool walk_directory_tree(
    > const char* dirname,
    > Func && cb,
    > bool recurse=false,
    > const char* match_suffix=nullptr,
    > bool returndots=false)
    > {
    >
    > return walk_directory_tree(
    > dirname,
    > std::function<bool(const char*, const char*)>(std::ref(cb)),
    > recurse,match_suffix,returndots
    > );
    > }
    >
    >
    > Cheers!
    >
    > SG


    Thank you very much for your response. I learned a lot from this.
     
    Matt Fioravante, Feb 22, 2013
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Peter Jansson
    Replies:
    5
    Views:
    6,328
    Ivan Vecerina
    Mar 17, 2005
  2. Vinu
    Replies:
    4
    Views:
    367
    Jim Langston
    Jul 7, 2005
  3. Vinu
    Replies:
    0
    Views:
    358
  4. Geoffrey S. Knauth
    Replies:
    6
    Views:
    1,007
    Earl Purple
    Jan 18, 2006
  5. Ravikiran

    Zero Optimization and Sign Optimization???

    Ravikiran, Nov 17, 2008, in forum: C Programming
    Replies:
    22
    Views:
    876
    Thad Smith
    Nov 24, 2008
Loading...

Share This Page