Search code examples
c++optimizationfunctional-programmingc++11mathematical-optimization

Optimizing composite std::functions


Is it possible to optimize a series of "glued together" std::functions and/or is there any implementation that attempts to do this?

What I mean is most easily expressed mathematically: say I want to make a std::function that is a function of a function:

f(x,y,z) = x^2 * y^3 * z^4
g(x,y,z) = f(x,y,z) / (x*y^2)

Is there a way for an STL/compiler implementor to optimize away parts of the arithmetic is calling a function object of g, created from a function object of f?

This would be a kind of symbolic simplification of the functions, but because this is a std::function, it would have to be spotted on a machine level.

Due to this being an optimization, which takes time, and probably isn't free (in clock cycles and/or memory), it probably isn't allowed by the Standard? It leans very close to a language that is typically ran through a VM. (I'm thinking LLVM more than Java here, with runtime optimizations).

EDIT: In order to make the discussion "more useful", here's a short code snippet (I understand a lambda is not a std::function, but a lambda can be stored in a std::function, so assuming auto below means std::function<T> with the appropriate T will express perfectly what I meant above):

auto f = [](const double x, const double y, const double z){ return x*x*y*y*y*z*z*z*z; };
auto g = [](const double c, const double y, const double z){ return f(x,y,z)/(x*y*y); };

A "trivial" compiler would make g equivalent to

double g(const double x, const double y, const double z){ return x*x*y*y*y*z*z*z*z/(x*y*y); }

While an optimized std::function could make it (mathematically and in every other sense correct!):

double g( const double x, const double y, const double z){ return x*y*z*z*z*z; }

Note that although I'm talking about mathematical functions here, similar transformations could be made for functions in the general sense, but that would take more introspection, which means overhead.

I can see this being very important when designing mathematical and physics simulations, where the generality of compositing existing library functions into user-case functions, with all the usual mathematical simplifications could make for a nice method of expressive, yet performant calculation software.


Solution

  • This is why you leave the optimizing to the compiler. They're algebraically equivalent but not equivalent due to FP imprecision. Your two versions of g would yield subtly different answers, which could be very important if called in an inner loop- not to mention the behavioural difference if x, y, z was 0.

    Secondly, as the contents of function are unknown until run-time, there's no way the compiler could perform such optimizations as it doesn't have the data it needs.