title: C++11 std::function slower than virtual calls?
body: <p>I am creating a mechanism which allows users to form arbitrary complex functions from basic building blocks using the <a href="http://en.wikipedia.org/wiki/Decorator_pattern#C.2B.2B" rel="noreferrer">decorator pattern</a>. This works fine functionality wise, but I don't like the fact that it involves a lot of virtual calls, particularly when the nesting depth becomes large. It worries me because the complex function may called often (>100.000 times).</p>
  
  <p>To avoid this problem, I tried to turn the decorator scheme into a <code>std::function</code> once it was finished (cfr. <code>to_function()</code> in the SSCCE). All internal function calls are wired during construction of the <code>std::function</code>. I figured this would be faster to evaluate than the original decorator scheme because no virtual lookups need to be performed in the <code>std::function</code> version.</p>
  
  <p>Alas, benchmarks prove me wrong: the decorator scheme is in fact faster than the <code>std::function</code> I built from it. So now I am left wondering why. Maybe my test setup is faulty since I only use two trivial basic functions, which means the vtable lookups may be cached?</p>
  
  <p>The code I used is included below, unfortunately it is quite long.</p>
  
  <hr>
  
  <h1>SSCCE</h1>
  
  <pre class="lang-cpp prettyprint-override"><code>// sscce.cpp
  #include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;memory&gt;
  #include &lt;functional&gt;
  #include &lt;random&gt;
  
  /**
   * Base class for Pipeline scheme (implemented via decorators)
   */
  class Pipeline {
  protected:
      std::unique_ptr&lt;Pipeline&gt; wrappee;
      Pipeline(std::unique_ptr&lt;Pipeline&gt; wrap)
      :wrappee(std::move(wrap)){}
      Pipeline():wrappee(nullptr){}
  
  public:
      typedef std::function&lt;double(double)&gt; FnSig;
      double operator()(double input) const{
          if(wrappee.get()) input=wrappee-&gt;operator()(input);
          return process(input);
      }
  
      virtual double process(double input) const=0;
      virtual ~Pipeline(){}
  
      // Returns a std::function which contains the entire Pipeline stack.
      virtual FnSig to_function() const=0;
  };
  
  /**
   * CRTP for to_function().
   */
  template &lt;class Derived&gt;
  class Pipeline_CRTP : public Pipeline{
  protected:
      Pipeline_CRTP(const Pipeline_CRTP&lt;Derived&gt; &amp;o):Pipeline(o){}
      Pipeline_CRTP(std::unique_ptr&lt;Pipeline&gt; wrappee)
      :Pipeline(std::move(wrappee)){}
      Pipeline_CRTP():Pipeline(){};
  public:
      typedef typename Pipeline::FnSig FnSig;
  
      FnSig to_function() const override{
          if(Pipeline::wrappee.get()!=nullptr){
  
              FnSig wrapfun = Pipeline::wrappee-&gt;to_function();
              FnSig processfun = std::bind(&amp;Derived::process,
                  static_cast&lt;const Derived*&gt;(this),
                  std::placeholders::_1);
              FnSig fun = [=](double input){
                  return processfun(wrapfun(input));
              };
              return std::move(fun);
  
          }else{
  
              FnSig processfun = std::bind(&amp;Derived::process,
                  static_cast&lt;const Derived*&gt;(this),
                  std::placeholders::_1);
              FnSig fun = [=](double input){
                  return processfun(input);
              };
              return std::move(fun);
          }
  
      }
  
      virtual ~Pipeline_CRTP(){}
  };
  
  /**
   * First concrete derived class: simple scaling.
   */
  class Scale: public Pipeline_CRTP&lt;Scale&gt;{
  private:
      double scale_;
  public:
      Scale(std::unique_ptr&lt;Pipeline&gt; wrap, double scale) // todo move
  :Pipeline_CRTP&lt;Scale&gt;(std::move(wrap)),scale_(scale){}
      Scale(double scale):Pipeline_CRTP&lt;Scale&gt;(),scale_(scale){}
  
      double process(double input) const override{
          return input*scale_;
      }
  };
  
  /**
   * Second concrete derived class: offset.
   */
  class Offset: public Pipeline_CRTP&lt;Offset&gt;{
  private:
      double offset_;
  public:
      Offset(std::unique_ptr&lt;Pipeline&gt; wrap, double offset) // todo move
  :Pipeline_CRTP&lt;Offset&gt;(std::move(wrap)),offset_(offset){}
      Offset(double offset):Pipeline_CRTP&lt;Offset&gt;(),offset_(offset){}
  
      double process(double input) const override{
          return input+offset_;
      }
  };
  
  int main(){
  
      // used to make a random function / arguments
      // to prevent gcc from being overly clever
      std::default_random_engine generator;
      auto randint = std::bind(std::uniform_int_distribution&lt;int&gt;(0,1),std::ref(generator));
      auto randdouble = std::bind(std::normal_distribution&lt;double&gt;(0.0,1.0),std::ref(generator));
  
      // make a complex Pipeline
      std::unique_ptr&lt;Pipeline&gt; pipe(new Scale(randdouble()));
      for(unsigned i=0;i&lt;100;++i){
          if(randint()) pipe=std::move(std::unique_ptr&lt;Pipeline&gt;(new Scale(std::move(pipe),randdouble())));
          else pipe=std::move(std::unique_ptr&lt;Pipeline&gt;(new Offset(std::move(pipe),randdouble())));
      }
  
      // make a std::function from pipe
      Pipeline::FnSig fun(pipe-&gt;to_function());   
  
      double bla=0.0;
      for(unsigned i=0; i&lt;100000; ++i){
  #ifdef USE_FUNCTION
          // takes 110 ms on average
          bla+=fun(bla);
  #else
          // takes 60 ms on average
          bla+=pipe-&gt;operator()(bla);
  #endif
      }   
      std::cout &lt;&lt; bla &lt;&lt; std::endl;
  }
  </code></pre>
  
  <hr>
  
  <h1>Benchmark</h1>
  
  <p>Using <code>pipe</code>:</p>
  
  <pre><code>g++ -std=gnu++11 sscce.cpp -march=native -O3
  sudo nice -3 /usr/bin/time ./a.out
  -&gt; 60 ms
  </code></pre>
  
  <p>Using <code>fun</code>:</p>
  
  <pre><code>g++ -DUSE_FUNCTION -std=gnu++11 sscce.cpp -march=native -O3
  sudo nice -3 /usr/bin/time ./a.out
  -&gt; 110 ms
  </code></pre>