June Meeting: Template Metaprogramming for numerical problems

Dear C++ Lovers,

in our next meetup we will have a talk from Mario Mulansky about C++ Template Metaprogramming (TMP) for numerical problems. The talk will explain how a TMP can be used to create highly generic and highly performant numerical algorithms, see below. As usual we meet in the C-Base a 7p.m., the talks starts at 8.

May meeting - C++ in the demo scene

Hi,

for our next meeting we are happy to announce a very interesting talk about C++ in the demo-scene from David Geier and Eivind Liland, see below. The meeting will take place at 20th  May, 7 p.m. in the C-Base.
As always talks will start at 8 p.m.

"The demoscene is a computer art subculture that specializes in producing demos, which are audio-visual presentation that run in real-time on a computer. The main goal of a demo is to show off programming, artistic and musical skills." (Wikipedia)

Eivind and David are demosceners since decades. In this talk they're going to show you two of their award-winning, real-time graphics demos, both highly optimized for different limitations and platforms, and both written in C++.

Turtles all the Way Down by Brain Control (2013) is a 64k-intro for the PC. It's an almost 5 minutes long audio-visual journey using cutting edge algorithms in the areas of computer graphics, generative art and music synthesis. Being a 64k-intro, all textures, 3D objects and music fit into a single executable of merely 65.536 bytes.

Matt Current by Shitfaced Clowns (2007) is a demo for the Gameboy Advance. It features at that time never-seen-before graphics effects and a software-rendered 3d engine that pushes the device's hardware to their limits. One prevailing opinion is that only by coding in 100% assembly one can push such platforms beyond their limits. Eivind will explain how they used C++ to carefully squeeze the maximum out of every cycle of the GBA's 16 MHz CPU.

Though seemingly esoteric, all the techniques employed to realize these demos have their application in professional software development nowadays. In times of GHz multi-core processors, GPUs and terabyte hard-drives, performance critical code and compact code for embedded and mobile platforms still plays an important role. Eivind and David are going to guide you through the process of creating these graphics demos. They talk about the used algorithms and tools keeping the focus of how C++ was used to do the job.

April Meeting – Slides & code examples

————————————————————————————————————————————————————————————
Talk 1: Martinho Fernandes - Unicode
link: flamingdangerzone.com/resources/mojibake.pdf



————————————————————————————————————————————————————————————
Talk 2: Fabio Fracassi - Perfect forwarding
------------------------------------------------------------

  Perfect Forwarding

  by     Arno Schödl
  and   Fabio Fracassi

------------------------------------------------------------

  Moving

    auto bar()->Foo {
        Foo foo1(1);
        Foo foo2(2);
        if( ...cond... ) {
          ...
          return foo1;
        } else {
          ...
          return foo2;
        }
      }

    Compiler cannot predict if foo1 or foo2 is returned
      -> no RVO    

    How can we make this case faster?

      All local variables of fooX go out of scope

      They won't be accessed anymore

      We can steal from them and they won't mind!

      Idea: tell the constructor of Foo, maybe he can be
        faster if he can steal

------------------------------------------------------------

  Rvalue references

      Foo && foo

    Reference (address) of a Foo which is no longer needed.
      May scavenge its resources
      Must leave in valid state.
        dtor will still run
        may assign to it

    Why it is called an rvalue?
      Expressions on the _r_ight-hand
      side of assignments are rvalues.
      -> after the assignment, they cannot be accessed
      -> can be scavenged

        int x=bar(1); // bar(1) return value is rvalue

    What's this? Useful?
      Foo const && foo

------------------------------------------------------------

  Special Member Function: Move Constructor

  teddy( Foo && foo );

  Foo::Foo(Foo && foo) {
    teddy(foo);
    // Inside function, foo is Foo & !
    // But we know we scavenge foo's resources!
    // (as long as we leave foo in a valid state)
  }
    compiler generated
      if the user does not provide any
       copy/move constructor or copy/move assignment or dtor
      move-constructs all members

------------------------------------------------------------

  When do we get rvalue references?

    Automatically

      return makes its argument rvalue reference
      (if copy is not elided anyway)

      auto bar()->Foo {
        Foo foo1(1);
        Foo foo2(2);
        if( ...cond... ) {
          ...
          return foo1; // rvalue, calls move ctor
        } else {
          ...
          return foo2; // rvalue, calls move ctor
        }
      }

      int main() {
        Foo foo=bar();
        return 0;
      }

------------------------------------------------------------

    Manually

      std::move turns lvalue (normal) reference
      into rvalue reference

      void eats_foo( Foo && foo, int i );

      int main() {
        Foo foo;
        eats_foo(
          foo,                 // copy ctor
          foo.returns_int()
        );
        eats_foo(
          std::move(foo),     // move ctor
          foo.returns_int()   // ok?
        );
        return 0;
      }

      auto move( Foo & foo )->Foo && {
        return static_cast<Foo &&>(foo);
      }

------------------------------------------------------------

  Special Member Functions: Move Assignment


  auto operator=(Foo &&)->Foo& {...; return *this;}
    move assignment operator
    compiler generated
      if the user does not provide any
       copy/move constructor or copy/move assignment or dtor
      move-assigns all members

    foo=barX(); // always move assignment,
                // copy-elision does not help

------------------------------------------------------------

  Copy-And-Swap Idiom

    Goal: implement 2 functions (copy ctor and swap)
      instead of 4 (copy/move ctor and copy/move assign)

    struct Foo {
      Foo() {
        std::cout << "construct empty" << std::endl;
      }
      Foo(int) {
        std::cout << "construct real" << std::endl;
      }
      ~Foo() {
        std::cout << "destroy" << std::endl;
      }

      Foo( Foo const& foo ) {
        std::cout << "copy" << std::endl;
      }
      friend void swap( Foo& lhs, Foo& rhs ) {
        std::cout << "swap" << std::endl;
      }

      // boilerplate possible if default-constructible
      Foo( Foo && foo )
      : Foo() // delegating constructor
      {
        swap( *this, foo );
      }

      // boilerplate always possible and saves self-
      // assignment check
      auto operator=( Foo foo )->Foo& {
        swap( *this, foo );
        return *this;
      }
    };

    int main() {
      Foo foo(1);
        construct real

      Foo foo2;
        construct empty

      foo2=std::move(foo1);
        construct empty (by move ctor)
        swap (by move ctor)
        swap (by operator=)
        destroy: when foo goes out of scope

      return 0;
        destroy
        destroy
    }

------------------------------------------------------------

  Perfect Forwarding

    Revelation:
      std::array<int,10> is just a template instantiation

      template< typename T, std::size_t N >
      struct array {
        array( ...uh?... ): m_at{ ...uh?... } {}
        auto operator[](std::size_t i) ->T & {
          return m_at[i];
        }
        auto operator[](std::size_t i) const->T const& {
          return m_at[i];
        }
      private:
        T m_at[N];
      };

    First attempt:
      array(    T const& a0,  T const& a1,   T const& a2 )
        : m_at{ a0,           a1,             a2 } 
      {}

    More overloads for move support:

      array(    T && a0,       T const& a1,   T const& a2 )
        : m_at{ std::move(a0), a1,            a2 }
      {}
      array(    T const& a0,   T && a1,       T const& a2 )
        : m_at{ a0,            std::move(a1), a2 }
      {}
      array(    T && a0,       T && a1,       T const& a2 )
        : m_at{ std::move(a0), std::move(a1), a2 }
      {}
      // ... too many ...

    Idea:
      Use a function template to generate
      the right contructor when it is called

    C++ rule:
      An rvalue reference of an lvalue reference
      collapses to the lvalue reference:

      Foo & && -> Foo &
      Foo const& && -> Foo const&

      template< typename A0, typename A1, typename A2 >
      array( A0 && a0, A1 && a1, A2 && a2 )
        : m_at{
          static_cast<A0 &&>(a0),
          static_cast<A1 &&>(a1),
          static_cast<A2 &&>(a2)
        }
      {}

      Foo foo1;
      Foo const foo2;
      array<Foo,3> arr={
        foo1,
// If compiler would make A0 = Foo &,
//    A0 &&                 would be              Foo &
//    static_cast< A0 && > would be static_cast< Foo & >
        foo2,
// If compiler would make A0 = Foo const&,
//    A0 &&                 would be              Foo const&
//    static_cast< A0 && > would be static_cast< Foo const& >
        Foo()
// If compiler would make A0 = Foo,
//    A0 &&                 would be              Foo &&
//    static_cast< A0 && > would be static_cast< Foo && >
      };

    OMG! PERFECT FORWARDING!

    (Slightly) less obscure:

      template< typename A0, typename A1, typename A2 >
      array( A0 && a0, A1 && a1, A2 && a2 )
        : m_at{
          std::forward<A0>(a0),
          std::forward<A1>(a1),
          std::forward<A2>(a2)
        }
      {}

------------------------------------------------------------

  Universal Reference

      template< typename T >
      auto func( ..., T && ,... ) ...

      is called "universal reference".

    Watch out:

      template< typename T >
      ... complex<T> && ...

      is just a regular rvalue reference to complex<T>.

------------------------------------------------------------

    Watch out even more:
      do not overload on universal references:

      template<typename T>  // lvalues supposed to go here
      auto func ( T const & t ) -> ... {/*...*/}

      template<typename T>  // rvalues supposed to go here
      auto func( T && t ) -> ... {/*...*/}

    But they do not do as they are supposed to!

      the second overload matches mutable lvalues

------------------------------------------------------------

    Need a dispatcher: 

      template<typename T>
      auto func_impl( T && t, std::true_type ) -> ... {
        // lvalues DO go here
      }

      template<typename T>
      auto func_impl( T && t, std::false_type ) -> ... {
        // rvalues DO go here
      }

      template<typename T>
      auto func( T && t ) -> ... {
        return func_impl( std::forward<T>(t),
                          std::is_lvalue_reference<T>() );
      }      

------------------------------------------------------------

    Worse when special member functions are involved:

      template<typename T>
      struct wrapper {
        T value;
        template<typename U>
        wrapper( U && u )
          : value( std::forward<U>(u) ) {}
      };

    compiler still generates copy ctor

    =delete'ing ctor does not do what we want

    no way of disableing the copy ctor - we hope for C++17
      (solution will break lots of old code)

    need rather involved enable_if :(

------------------------------------------------------------

  Parameter Packs

    template< typename T, std::size_t N >
    struct array {
      template<
        typename A0
      > array(
        A0 && a0
      ): m_at{
        std::forward<A0>(a0)
      } {}

      template<
        typename A0,
        typename A1
      > array(
        A0 && a0,
        A1 && a1
      ): m_at(
        std::forward<A0>(a0),
        std::forward<A1>(a1)
      ) {}

      template<
        typename A0,
        typename A1,
        typename A2
      > array(
        A0 && a0,
        A1 && a1,
        A2 && a2
      ): m_at(
        std::forward<A0>(a0),
        std::forward<A1>(a1),
        std::forward<A2>(a2)
      ) {}
      // ... still not insanely great ...

      auto operator[](std::size_t i) ->T & {
        return m_at[i];
      }
      auto operator[](std::size_t i) const->T const& {
        return m_at[i];
      }
    private:
      T m_at[N];
    };

  We would like to write:

    template< typename T, std::size_t N >
    struct array {
      template< typename ...As >
      array( As &&... as )
      : m_at{ std::forward<As>(as)... } {}

      auto operator[](std::size_t i) ->T & {
        return m_at[i];
      }
      auto operator[](std::size_t i) const->T const& {
        return m_at[i];
      }
    private:
      T m_at[N];
    };

  WE CAN!

------------------------------------------------------------
















------------------------------------------------------------

template<typename A, typename B>
using disable_if_same_or_derived =
    typename std::enable_if<
        !std::is_base_of<A,typename
             std::remove_reference<B>::type
        >::value
    >::type;

template<typename T>
struct wrapper
{
    T value;
    template<typename U, typename X =
        disable_if_same_or_derived<wrapper,U>>
    wrapper( U && u )
      : value( std::forward<U>(u) )
    {}
};

————————————————————————————————————————————————————————————
Talk 3: André Bergner - Mechanics of std.function


------------------------------------------------------------
function_int_int.test.cpp


#include <iostream>
#include "function_int_int.h"

int foo(int x)   { return x + 1; }
int bar(int x)   { return x * x; }
struct { int operator()( int x ) { return x * 100; } } baz;

my::function_int_int  f;   // we can store functions:  int -> int
void use_f()  { std::cout << f(2) << std::endl; }

int main()
{
   f = foo;          // store function 1
   use_f();          // should return: 3

   f = bar;          // store function 1
   use_f();          // should return: 4

   f = baz;          // store functor
   use_f();          // should return: 200

   f = [](int x) { return x - 123; };   // store lambda
   use_f();          // should return: -121
}

------------------------------------------------------------

function_int_int.h

#include <memory>

namespace my {

   class function_concept { public: virtual int call( int ) = 0; };

   template < typename Function >

   class function_model : public function_concept

   {

      Function f_;

   public:

      function_model( Function &f ) : f_(f) {}

      int call( int i )   {  return f_( i );  }

   };

   class function_int_int

   {

      std::unique_ptr<function_concept>  f_;

   public:

      function_int_int(){}

      template < typename F >

      function_int_int( F f ) : f_( new function_model<F>(f) ) {}

      template < typename F >

      function_int_int& operator= ( F f )
      { f_.reset( new function_model<F>(f) ); return *this; }

      int operator()( int i )   {  return f_->call( i );  }

   };
}

------------------------------------------------------------

function.test.cpp

#include <iostream>

#include "function.h"

using namespace std;

int    foo(int x)            { return x + 1; }

float  bar(int x, char c)    { cout << c << endl;  return float(x*x); }

struct { int operator()( int x ) { return x * 100; } } baz;

int main()

{

   my::function< int(int) >  f = foo;          // store free function 1

   cout << f(2) << endl;                       // should return: 3

   f = baz;                                    // store functor

   cout << f(2) << endl;                       // should return: 200

   my::function< float(int,char) >  g = bar;   // store free function 2

   cout << g(2,'x') << endl;                   // should print: x  4

   g = [](int x, char) { return x - 123.f; };  // store lambda functor

   cout << g(2,'x') << endl;                   // should return: -121

   //  works with generic lambdas as well (clang 3.4 with option -std=c++1y)

   my::function< float( float, float ) >
      h = [](auto x , auto y) { return x+y; };

   cout << h(3,4) << endl;                     // should return: 7

}

------------------------------------------------------------

function.h

#include <memory>

namespace my {

   //--------- class template prototypes ---------------------------------------

   template < typename Signature >                      class function_concept;

   template < typename Signature , typename Function >  class function_model;

   template < typename Signature >                      class function;

   //--------- class template specializations ----------------------------------

   //  The classes get specialized only for function signatures.

   template < typename Ret , typename... Args >

   class function_concept< Ret(Args...) >
   {  public: virtual  Ret call( Args&&... ) = 0; };

   template < typename Function , typename Ret , typename... Args >

   class function_model< Ret(Args...) , Function >
         : public function_concept< Ret(Args...) >

   {

      Function f_;

   
   public:

      function_model( Function &f ) : f_(f) {}

      Ret call( Args&&... args )
      {  return f_( std::forward<Args>(args)... );  }

   };

   template < typename Ret , typename... Args  >

   class function< Ret(Args...) >

   {

      using Signature = Ret( Args... );

      std::unique_ptr< function_concept<Signature> > f_;

   public:

      function(){}

      template < typename F >

      function( F f ) : f_( new function_model<Signature,F>(f) ) {}

      Ret operator()( Args&&... args )
      {  return f_->call( std::forward<Args>(args)... );  }

      template < typename F >

      function& operator= ( F f )
      { f_.reset( new function_model<Signature,F>(f) ); return *this; }

   };

}

------------------------------------------------------------

member.test.cpp

#include <iostream>

#include "function.h"
#include "member.h"
using namespace std;

struct C {
   bool greater( int a , int b ) { return a > b; }
   bool smaller( int a , int b ) { return a < b; }
};


int main()
{
   C c;
   my::function< bool(int,int) >  f;

   f = my::bind_member( c , &C::greater );

   cout << "greater" << endl;
   cout << f(1,2) << endl;
   cout << f(2,1) << endl;

   using my::operator&&;   // using syntactic sugar notation

   f = c &&& C::smaller;

   cout << "smaller" << endl;
   cout << f(1,2) << endl;
   cout << f(2,1) << endl;

}

------------------------------------------------------------

member.h

namespace my {

   template < typename Function , class Class >

   struct MemberFunction

   {

      using MemFun =  Function Class::*;

      MemFun  f_;

      Class*  c_;

 

   public:

 

      MemberFunction( MemFun  f , Class* c ) : f_(f) , c_(c) {}

 

      template < typename... Args >

      auto operator()( Args&&... args)

      { return (c_->*f_)( std::forward<Args>(args)... ); }

   };

   template < typename Function , class Class >

   auto bind_member( Class& c , Function Class::* f )

   {

      return MemberFunction<Function, Class>( f , &c );

   }

   // syntactic sugar

   template < typename Function , class Class >

   auto operator&& ( Class& c , Function Class::* f )

   {

      return MemberFunction<Function, Class>( f , &c );

   }

}

------------------------------------------------------------

test_function_performance.cpp

#include <iostream>

#include <memory>

#include <chrono>

#include <functional>

#include <boost/function.hpp>

#include "function.h"

using namespace std;

using namespace std::chrono;

inline int  foo(int x)  { return x + 1; }

int         bar(int x)  { return x + 1; }

class SomeInterface { public: virtual int foo(int) = 0; };

class V : public SomeInterface { public: virtual int foo(int x) { return x + 1; } };

V v;

SomeInterface* w = new V;

int main()

{

   my   ::function< int( int ) >  mf;

   std  ::function< int( int ) >  sf;

   boost::function< int( int ) >  bf;

   #define  MEASURE_PERFORMANCE( info , fun )                 \

                                                              \

      cout << info << "    ";                                 \

      size_t n = 0;                                           \

                                                              \

      auto tick = steady_clock::now();                        \

                                                              \

      for ( size_t k = 0  ;  k < 100000000 ; ++k )            \

         n += fun(n);                                         \

                                                              \

      auto tock = steady_clock::now();                        \

      cout << "time needed: "                                 \

           << duration_cast<milliseconds>(tock-tick).count()  \

           << " millisec.   result = "                        \

           << n                                               \

           << endl;                                           \

   {                   MEASURE_PERFORMANCE( "plain foo         " , foo )     }

   {                   MEASURE_PERFORMANCE( "virtual mem foo   " , v.foo )   }

   {                   MEASURE_PERFORMANCE( "polymorphic foo   " , w->foo )  }

   {  mf = foo;        MEASURE_PERFORMANCE( "my::fun foo       " , mf )      }

   {  mf = bar;        MEASURE_PERFORMANCE( "my::fun bar       " , mf )      }

   {  sf = foo;        MEASURE_PERFORMANCE( "std::fun foo      " , sf )      }

   {  sf = bar;        MEASURE_PERFORMANCE( "std::fun bar      " , sf )      }

   {  bf = foo;        MEASURE_PERFORMANCE( "boost::fun foo    " , bf )      }

   {  bf = bar;        MEASURE_PERFORMANCE( "boost::fun bar    " , bf )      }

   {  mf = [](int i) { return foo(i); };

                       MEASURE_PERFORMANCE( "my::fun( /l foo)  " , mf )      }

   {  mf = [](int i) { return i+1; };

                       MEASURE_PERFORMANCE( "my::fun( /l )     " , mf )      }

}