std::function optimization

[Matt Fioravante]

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?

 

[Luca Risolia]

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.

 

[SG]

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

 

[Matt Fioravante]

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.

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.