C++ User Group Berlin

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.

————————————————————————————————————————————————————————————
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 ) }

}

C++ User Group Berlin

Samstag, 11. Oktober 2014

October meeting - Designing a message bus wit type depended static dispatch

Montag, 1. September 2014

September meetup - lightning talks

Freitag, 8. August 2014

Donnerstag, 3. Juli 2014

July Meeting "The what why and how of modern CMake"

Dienstag, 10. Juni 2014

June Meeting: Template Metaprogramming for numerical problems

Montag, 5. Mai 2014

May meeting - C++ in the demo scene

Freitag, 18. April 2014

April Meeting – Slides & code examples

Links

Beitragende