Wednesday, October 10, 2012

C++11 Idioms @ 2012 Silicon Valley Code Camp

The slides for my C++11 Idioms talk @ 2012 Silicon Valley Code Camp are now available. If you attended the talk please evaluate it. The slides for  many other talks in the C++/C++11 track are also available.



Wednesday, September 19, 2012

C++/C++11 Track @ Silicon Valley Code Camp 2012

For the first time in 7 years, 2012 Silicon Valley Code Camp will have a track dedicated to C++ and C++11. Code Camp is a conference of developers, by developers, for developers. Attendance is free! This year, the number of attendees is expected to exceed 2200 to attend 223 sessions on a variety of topics related to software technology. Code Camp will be held @ Foothill College on Oct. 6th and 7th (weekend) in Silicon Valley.

CodeCamp at FootHill College.


C++ is clearly one of the big things at Code Camp this year. The track has sessions on exception-safe coding, generic programming, logic programming, Windows 8 development, and the Clang compiler. There are sessions focused on C++11 too. Purely on the language side, two sessions on rvalue references, move semantics, perfect forwarding, and modern idioms of using them in your programs should whet the appetite of any C++11 programmer. On the standard library side, how about C++11 threading library!

On Sunday, I'll present two sessions: "C++11 Idioms" and "Using Data-centric Publish/Subscribe for Request-Reply Communication". The first one is focused on rvalue references, move semantics, and perfect forwarding. If you have been following this blog, you might get glimpse of what's coming. However, more than a third of the talk will be about techniques that are never discussed on this blog. The second talk will discuss how you can implement the request-reply communication pattern using Data Distribution Service (DDS) API, which is fundamentally publish/subscribe.

So far, the idioms session is among the top sessions in the C++ track. So, guys, thanks for showing so much interest; and keep it up! Just click "Will Attend" if you plan to. Remember, it is free! 

Sunday, June 03, 2012

Perfect Forwarding of Parameter Groups in C++11

C++11 offers a great new feature called Perfect Forwarding, which is enabled via the use of rvalue references. Perfect forwarding allows a function template to pass its arguments through to another function while retaining the original lvalue/rvalue nature of the function arguments. It avoids unnecessary copying and avoids the programmer having to write multiple overloads for different combinations of lvalue and rvalue references. A class can use perfect forwarding with variadic templates to "export" all possible constructors of a member object at the parent's level.
class Blob
{
  std::vector<std::string> _v;
public:

  template<typename... Args>
  Blob(Args&&... args) 
   : _v(std::forward<Args>(args)...)
  {  }

};

int main(void)
{
  const char * shapes[3] = { "Circle", "Triangle", "Square" };

  Blob b1(5, "C++ Truths");  
  Blob b2(shapes, shapes+3);
}
The Blob class above contains a std::vector, which has many different constructors. Using a perfect forwarding constructor, the Blob class allows its clients to pass variable number of parameters that different constructors of std::vector would use. For example, object b1 uses std::vector's constructor that takes a count and an initial value where as object b2 uses the constructor that takes an iterator pair. Also note that std::forward allows us to perfect-forward the parameters.

[Note: Strictly speaking, this specific example does not require perfect forwarding because Blob constructor could take a std::vector by value and move it into the member vector object. But lets carry on!]

In practice, however, you would encounter classes that would have several members. Naturally, you may want to "export" their different constructors at its parent's level. This is particularly true if object construction is heavy and does not support efficient move. The motivation behind this is no different than that of the emplace operations on containers. Just like the standard emplace operations, our perfect forwarding constructor allows us to construct an object in-place. We don't even pay the cost of a move (which is often negligible for types such as std::vector). An interesting problem arises when we want to perfect forward arguments to more than one constructor. How do we decide which parameters are for which object? For example, the following Blob class has a vector of strings and a list of doubles. How do we group the parameters to the respective constructors? How do we know the programmer's intent?
class Blob
{
  std::vector<std::string> _v;
  std::list<double> _l;
public:

  template<typename... Args>
  Blob(Args&&... args) 
   : _v(???)
     _l(???)
  {  }
};

int main(void)
{
   Blob b3(5, 10, 10.0); // Three parameters and two constructors. How do we group?
}
Fortunately there is a way out and a very interesting one.

First of all, we've to group the parameters. An obvious candidate comes to mind: std::tuple! We could ask programmers to group the parameters in a sequence of tuples and each parameter grouped in the tuples are passed to the respective constructors.
 
Blob b3(std::make_tuple(5), std::make_tuple(10, 99.99)); 
 
The intent of the programmer is pretty clear in the above groupings. The vector will have 5 empty strings and the list will have 10 doubles each initialized to value = 99.99. However, we've a new problem now. std::vector and std::list do not accept std::tuple as parameters. We've to ungroup them before calling their constructors. This is far from trivial but it also makes the whole thing very interesting.

Note that retrieving values from a std::tuple requires calling std::get<i> where i is a compile-time constant that varies from 0 to the tuple_length-1. Somehow, we've to call std::get on each tuple with increasing values of i. To do that, we've to create a compile-time list of tuple indices. Here is a way to do it. Thanks sigidagi!
template<unsigned...> struct index_tuple{};

template<unsigned I, typename IndexTuple, typename... Types>
struct make_indices_impl;

template<unsigned I, unsigned... Indices, typename T, typename... Types>
struct make_indices_impl<I, index_tuple<Indices...>, T, Types...>
{
  typedef typename 
    make_indices_impl<I + 1, 
                      index_tuple<Indices..., I>, 
                      Types...>::type type;
};

template<unsigned I, unsigned... Indices>
struct make_indices_impl<I, index_tuple<Indices...> >
{
  typedef index_tuple<Indices...> type;
};

template<typename... Types>
struct make_indices 
  : make_indices_impl<0, index_tuple<>, Types...>
{};
make_indices is a collection of recursive meta-fuctions that compute a list of indices given a tuple type. For example, if you have (42, true, 1.2), which is tuple<int, bool, double>, make_indices<int,bool,double>::type gives index_tuple<0, 1, 2>. Here is how to use make_indices in a simple program.
template <unsigned... Indices, class... Args, class Ret>
Ret forward_impl(index_tuple<Indices...>,
                 std::tuple<Args...> tuple,
                 Ret (*fptr) (Args...))
{
  return fptr(std::get<Indices>(tuple)...);
}

template<class... Args, class Ret>
Ret forward(std::tuple<Args...> tuple, Ret (*fptr) (Args...))
{
   typedef typename make_indices<Args...>::type Indices;
   return forward_impl(Indices(), tuple, fptr);
}

int myfunc(int i, bool, double)
{
  return 5 + i;
}

int main()
{
  std::cout << forward(std::make_tuple(42, true, 1.2), myfunc) << std::endl;
}
Line #6 above is the place where the actual function is called where the list of indices and the tuple come together and two parameter packs are expanded in lockstep to yield the complete list of parameters. Note that we're not using perfect forwarding in this case. Moreover, tuple is also copied by value. That's fine for scalar builtin types like int, bool, and double. For large types, however, unnecessary copies may be created. The above program is simplified for the purpose of illustration.

Back to class Blob

The make_indices utility is pretty clever. But we're not done yet. We've to achieve the same effect while calling the member constructors from the initialization list. We've to compute two lists of indices (one for vector and one for list) and expand them with the respective tuples. The question is how do we compute the list of indices before calling member constructors?

Delegated constructors come to rescue!

class Blob
{
  std::vector<std::string> _v;
  std::list<double> _l;

public:

  template <typename... Args1,
            typename... Args2>
  Blob(std::tuple<Args1...> tuple1,
       std::tuple<Args2...> tuple2)
  : Blob(tuple1,
         tuple2,
         typename make_indices<Args1...>::type(),
         typename make_indices<Args2...>::type())
  {}

private:
  template <typename... Args1,
            typename... Args2,
            unsigned... Indices1,
            unsigned... Indices2>
  Blob(std::tuple<Args1...> tuple1,
       std::tuple<Args2...> tuple2,
       index_tuple<Indices1...>,
       index_tuple<Indices2...>)
    : _v(std::forward<Args1>(std::get<Indices1>(tuple1))...),
      _l(std::forward<Args2>(std::get<Indices2>(tuple2))...)
  { }
};
The new Blob class has a public constructor that delegates to a private constructor that expects not only the tuples but also the list of indices. The private constructor is not only templatized on the tuple arguments but also on the list of indices. Once we've the tuples and lists of indices together, passing them to the member constructors is pretty straight forward. We simply expand the two variadic lists in unison.

Astute readers will likely notice that the Blob class is no longer using perfect forwarding because it accepts two tuples by value as opposed to an argument list in a perfect forwarding fashion shown at the beginning. That's is on purpose. And it is not any less efficient either! Even for large types! How's that possible?

Well, who says copying a tuple by value means copying its original parameters by value? C++ standard library provides a very convenient helper called forward_as_tuple, which perfect-forwards its parameters types as tuple members. It constructs a tuple object with rvalue references to the elements in arguments suitable to be forwarded as argument to a function. That is, the tuple member types are T&& and copying references is blazing fast. So we can afford to pass the tuples by value. Alternatively, we could use rvalue references to the tuples because in this case they are always (!) created by calling std::forward_as_tuple, which returns a temporary tuple. Here is how we use our final Blob class.

I compiled this program on g++ 4.8. Clang 3.2 with the latest libcxx did not work for me.
int main(void) 
{
  Blob b3(std::forward_as_tuple(5, "C++ Truths"),
          std::forward_as_tuple(10, 99.99));
  // b3._v has 5 strings initialized to "C++ Truths" and
  // b3._l has 10 doubles initialized to 99.99

  Blob b4(std::forward_as_tuple(5),
          std::forward_as_tuple(10, 99.99));
  // b4._v has 5 empty strings and
  // b4._l has 10 doubles initialized to 99.99

  Blob b5(std::forward_as_tuple(),
          std::forward_as_tuple(10, 99.99));
  // b5._v is an empty vector 
  // b5._l has 10 doubles initialized to 99.99
}

Using std::piecewise_construct

The Blob class looks fine and dandy so far. But the use of forward_as_tuple looks somewhat weird and does not say what it is for: in-place construction of a Blob object from its pieces. So in the final installment of the Blob class, we say what we mean. We just decorate the class with a standard (!) dummy class called std::piecewise_construct_t. The public constructor of the Blob is modified like below. We use std::piecewise_construct, a predefined object of std::piecewise_construct_t, at the call site where we create Blob objects.
#include <utility>
// ...
  template <typename... Args1,
            typename... Args2>
  Blob(std::piecewise_construct_t,
       std::tuple<Args1...> tuple1,
       std::tuple<Args2...> tuple2)
  : Blob(tuple1,
         tuple2,
         typename make_indices<Args1...>::type(),
         typename make_indices<Args2...>::type())
  {}

//...

Blob b3(std::piecewise_construct,
        std::forward_as_tuple(5, "C++ Truths"),
        std::forward_as_tuple(10, 99.99));
Obviously, the C++ library working group anticipated such situations. But are there use cases in the standard library that require the piecewise_construct idiom? As it turns out, the std::map and std::unordered_map face a very similar issue while using emplace operations. Note that std::map and std::underorder_map use a std::pair as their value_type. The pair's .first and .second members must be constructed from a list of perfectly forwarded parameters. Obviously, the question arises what parameters go where. To solve this issue, the parameters of each member's constructor must be wrapped as a tuple and indicate so using std::piecewise_construct so that the right pair constructor (#6) can be invoked.

So on an ending note, perfect forwarding is, well, not perfect; but gets the job done with some help from the programmers!

Comments? Feedback? Post them below in the comments section or check out the previous comments on Reddit.

Friday, March 09, 2012

Rvalue references in constructor: when less is more

I've seen a recurring mistake made by well-versed C++03 programmers when they set out to use rvalue references for the first time. In fact, as it turns out, better you are at C++03, easier it is to fall in the trap of rvalue reference anti-pattern I'm gonna talk about.

Consider the following C++03 class:

class Book {
public:
  Book(const std::string & title,
       const std::vector<std::string> & authors,
       const std::string & pub,
       size_t pub_day
       const std::string & pub_month,
       size_t pub_year)
    : _title(title),
      _authors(authors),
      _publisher(pub),
      _pub_day(pub_day),
      _pub_month(pub_month),
      _pub_year(pub_year)
     {}

     // ....
     // ....

private:
  std::string _title;
  std::vector<std::string> _authors;
  std::string _publisher;
  size_t      _pub_day;
  std::string _pub_month;
  size_t      _pub_year;
};


The Book class above is as dull as it can be. Now lets C++11'fy it! C++11 gives us shiny new rvalue references and std::move. So lets add them.

class Book {
public:
  Book(const std::string & title,
       const std::vector<std::string> & authors,
       size_t pub_day
       const std::string & pub_month,
       size_t pub_year)
    : _title    (title),
      _author   (author),
      _pub_day  (pub_day),
      _pub_month(pub_month),
      _pub_year (pub_year)
     {}

  Book(std::string && title,
       std::vector<std::string> && authors,
       size_t      && pub_day
       std::string && pub_month,
       size_t      && pub_year)
    : _title    (std::move(title)),
      _authors  (std::move(authors)),
      _pub_day  (pub_day),
      _pub_month(std::move(pub_month)),
      _pub_year (pub_year)
     {}

     // ....
     // ....

private:
  std::string _title;
  std::vector<std::string> _authors;
  size_t      _pub_day;
  std::string _pub_month;
  size_t      _pub_year;
};


Is our constructor optimally move-enabled? It's far from it! More often that not, programmers' legit code will end up calling the old constructor instead of the the new one, which probably means lost opportunities for optimization. It could be hard to see what's wrong in the new class to an untrained eye. We've test it to see what's really wrong with it.

std::string & toUpper(std::string & s)
{
  std::transform(s.begin(), s.end(), s.begin(), toupper);
  return s;
}
const std::string & January()
{
  static std::string jan("January");
  return jan;
}
int main(void)
{
  std::vector<std::string> authors { "A", "B", "C" };
  Book b1("Book1", authors, 1, "Jan", 2012);   // old c-tor

  size_t year = 2012
  Book b2("Book2", { "A", "B", "C" }, 1, "Jan", year); // old c-tor

  std::string month = "Mar";
  Book b3("Book3", { "Author" }, 1, toUpper(month), 2012); // old c-tor

  Book b4("Book4", { "Author" }, 1, January(), 2012); // old c-tor

  std::string book = "Book";
  Book b5(std::move(book), std::move(authors), 1, std::move(month), year); // old-ctor

  Book b6("Book", { "Author" }, 1, "Jan", 2012); // new c-tor!
}


It may come as a surprise that in all but one case above, the old constructor is called. Only in the last case, the new-ctor is called, which makes the minimum number of copies. So what's the gotcha?

As it turns out, the Book constructors are stopping the compiler from doing a better job. The first constructor takes all the parameters as const reference and the second one takes all the parameters as rvalue reference. Unless and until all the the parameters passed to the constructor are temporary objects (rvalues) or literals, the second constructor does not kick in. This implies lost optimization opportunities for parameters that are temporary (so can be moved) but won't be moved because some other parameter botched the soup. These two constructors give you very limited options: all-or-nothing.

In case of b1, authors is an lvalue and it does not bind to an rvalue ref.
In case of b2, year is an lvalue and does not bind to an rvalue ref.
In case of b3, toUpper returns a string reference; Does no good.
In case of b4, January returns a const string reference; same story!
In case of b5, year is an lvalue that prevents calling the second constructor although programmer tries to explicitly move all the string and vector parameters. In reality, the actual moves do not happen and if the remaining program depends on the moves being successful may not be very happy.

Only in case of b6, all actual parameters are rvalues or literals. Therefore, the "all-rvalue-ref" constructor is called. Note that temporary string objects will be implicitly created where string literals are used.

So lets fix it. What we really need is just one constructor that accepts all the parameters by value. As a side-effect, the overall code is much simpler.

class Book {
public:
  Book(std::string title,
       std::vector<std::string> authors,
       size_t      pub_day
       std::string pub_month,
       size_t      pub_year)
    : _title    (std::move(title)),
      _authors  (std::move(authors)),
      _pub_day  (pub_day),
      _pub_month(std::move(pub_month)),
      _pub_year (pub_year)
     {}

  // ....
  // ....
};


That's it! This is our the constructor that works optimally. All strings, vectors, integral types are passed by value. Within the constructor, the pass-by-value parameters that are on the stack-frame must be moved to the respective data members. The reason is that the lifetime of pass-by-value parameters is anyways limited to the lifetime of the constructor call itself. We want to tie their lifetime to the object and not the constructor.

This constructor does no more deep copies of than necessary. And that number really depends on how it is called. Due to pass-by-value semantics, each object individually is an opportunity for the compiler to perform a move when a temporary is involved. Lets revisit our b1 to b4 objects.

In case of b1, except for authors all other parameters are copied and moved once.
In case of b2, all strings and vectors are copied and moved once. That's what matters.
In case of b3, toUpper returns an string reference; everything else copied and moved only once.
In case of b4, January returns a const string reference; everything else copied and moved once.
In case of b5, strings are vector are moved as expected and in fact the b5 object the local parameters are created using move-constructor and moved again into the data member. Hence the object is created without any deep copies (like zero-copy).

Using pass-by-value also opens other opportunities to eliminate temporaries when functions return by value and are used as actual parameters. However, I won't discuss that in detail here.

Finally, I want to conclude saying that this whole thing assumes that a move is much cheaper than a deep-copy. This is generally true for std::vector and std::string where memory is allocated dynamically. For small strings however small-string-optimization may make copy and move practically equivalent.

Sunday, January 22, 2012

Array-like access and Iterators for Homogeneous Tuples

Question often comes up whether tuples can have traditional iterators? In general, the answer is: No! They cannot. That's because tuples typically contain different types and traditional iterators, which are modeled after pointers, can not dereference to objects of multiple types. However, homogeneous tuples can have iterators. So I thought it would be a fun exercise to write one. I wonder why one would use a homogeneous tuples instead of just plain arrays. But lets do it anyways because we can.

Although this exercise sounds rather naive and unnecessary, I stumbled upon two very interesting topics along the way.

  • A need for new iterator concepts to separate the notions of element access from iterator traversal. Yes! iterators for homogeneous tuples can't be modeled accurately using conventional iterator categories. Don't believe me? Please read on...

  • How inherited constructors may be simulated on compilers that don't support them today.


From this point onward a tuple is assumed to be a homogeneous tuple. First thing we need is a way of accessing tuple's contents using a run-time integer instead of a compile-time integer. We need an adapter that uses a run-time integer index to return the n-th element in a homogeneous tuple. If n is larger than the bounds of the tuple, the adapter will throw a std::out_of_range exception.

template <typename Tuple,
size_t I = std::tuple_size<Tuple>::value-1>
class TupleAt
{
typedef typename std::tuple_element<0, Tuple>::type T;

public:
static T & get(Tuple & tuple, size_t index)
{
return (index == I)? std::get<I>(tuple) : TupleAt<Tuple, I-1>::get(tuple, index);
}
};

template <typename Tuple>
class TupleAt<Tuple, 0>
{
typedef typename std::tuple_element<0, Tuple>::type T;
public:

static T & get(Tuple & tuple, size_t index)
{
if(index == 0)
return std::get<0>(tuple);
else
throw std::out_of_range("Tuple iterator dereferenced out of valid range.");
}
};

The TupleAt template takes the type of the tuple and its size as template parameters. It assumes that the type of the first element is also the type of the rest of the elements in the tuple (i.e. a homogeneous tuple). TupleAt::get function returns a reference to the n-th element in the tuple. It does that using repeated comparisons from the size of the tuple (std::tuple_size<Tuple>::value) down to zero. TupleAt is specialized for zero so that the recursion ends. If the index does not fall in the expected range, std::out_of_range exception is thrown.

Note that this access pattern is linear in complexity. For a tuple of N elements, it may take up to N comparisons to return the right element.

Array-like access to Homogeneous Tuples



I created a tuple_array class to provide array-like access to the elements of the tuple. It uses TupleAt internally.

template <typename... T>
class tuple_array : public std::tuple<T...>
{
typedef std::tuple<T...> Tuple;
typedef typename std::tuple_element<0, Tuple>::type HeadType;
enum { TUPLE_SIZE = std::tuple_size<Tuple>::value };

HeadType * ref_;
size_t last_;

public:
USING(tuple_array, Tuple)
{
ref_ = & TupleAt<Tuple>::get(*this, TUPLE_SIZE-1);
last_ = TUPLE_SIZE-1;
}

HeadType & operator [] (size_t index)
{
if(last_ != index)
{
ref_ = & TupleAt<Tuple>::get(*this, index);
last_ = index;
}
return *ref_;
}
};


Class tuple_array inherits from std::tuple and just provides operator [] function. It always returns a reference to HeadType typedef, which is the type of the first element in the tuple. To improve efficiency, the tuple_array class caches a pointer to the last dereferenced index in the tuple. std::tuple has a zillion constructors to create a tuple. To avoid repeating the constructors in the derived tuple_array class, I wanted to use inherited constructors. However, g++ 4.7 does not support it at this moment. So I'm using a variadic template constructor to mimic the behavior of inherited constructors.

#define USING(Dervied, Base)                                       \
template<typename ...Args, \
typename = typename std::enable_if \
< \
std::is_constructible<Base, Args...>::value \
>::type> \
Dervied(Args &&...args) \
: Base(std::forward<Args>(args)...) \


The inherited constructor trick is captured in a macro, which I stole shamelessly from here. The USING macro defines a variadic template constructor and forwards all the arguments to the underlying base constructor. To avoid being overly greedy, it enables instantiation only if the base is constructible from the given parameters. std::is_constructible<Base, Args...>::value provides a neat way of checking that at compile-time.

Finally, we need a simple function to create the tuple_array. Function make_tuple_array is a factory function to create tuple_arrays from a list of arguments. Note how it uses the uniform initialization syntax without specifying the actual type. Using make_tuple_array is just like an array. However, note that element access is linear and not constant-time.

template <typename... T>
tuple_array<T...> make_tuple_array(T... args)
{
return { std::forward< T&& >(args)... };
}

int main(void)
{
auto ta = make_tuple_array(20, 30, 40);
printf("%d %d %d", ta[0], ta[1], ta[2]); // prints 20 30 40
}


Iterators for Homogeneous Tuples



Now lets turn our attention to iterators.

What category would an iterator for homogeneous tuple belong? Random access? Bidirectional? It appears to me that the homogeneous tuple iterator could simply use an internal index to remember what position it is at and use the TupleAt::get to return the element when dereferenced. Arbitrary arithmetic can be performed in constant-time on the internal index to move the iterator. This indicates that the iterator is a random access iterator.

However, the dereference function is not constant-time as discussed earlier. As a result, it is not a random access iterator. Clearly, traversal is random access but element access is not. Existing iterator categories do not support this distinction. The standard random access iterator [5] requires all operations to be amortized constant time.

What we really need is a way to distinguish between the categories of element access and the categories of traversal. This is precisely the point of new iterator concepts in boost.

For now, we'll just consider that the iterator for homogeneous tuple is a random access iterator. Here is how it looks like with a lot of boilerplate overloaded operators.

template <typename Tuple>
class tuple_iterator
: public std::iterator<std::random_access_iterator_tag,
typename std::tuple_element<0, Tuple>::type>
{
typedef typename std::tuple_element<0, Tuple>::type T;
enum { TUPLE_SIZE = std::tuple_size<Tuple>::value };

Tuple * tuple;
int current_;
int last_;
T * ref_;

T * update_ref()
{
if(current_ != last_)
{
ref_ = & TupleAt<Tuple>::get(*tuple, current_);
last_ = current_;
}
return ref_;
}

public:

typedef int difference_type;

explicit tuple_iterator(Tuple & t, size_t i = TUPLE_SIZE)
: tuple(&t),
current_(i),
last_(-9999),
ref_(nullptr)
{}
T & operator *() {
return *update_ref();
}
T * operator ->() {
return update_ref();
}
T & operator [] (int offset) {
return TupleAt<Tuple>::get(*tuple, current_+offset);
}
tuple_iterator & operator ++ () {
if(current_ < TUPLE_SIZE)
++current_;
return *this;
}
tuple_iterator operator ++ (int) {
tuple_iterator temp(*this);
++(*this);
return temp;
}
tuple_iterator & operator -- () {
if(current_ >= 0)
--current_;
return *this;
}
tuple_iterator operator -- (int) {
tuple_iterator temp(*this);
--(*this);
return temp;
}
tuple_iterator operator - (int i) const {
tuple_iterator temp(*tuple, current_-i);
return temp;
}
tuple_iterator & operator -= (int i) {
current_-=i;
return *this;
}
tuple_iterator operator + (int i) const {
tuple_iterator temp(*tuple, current_+i);
return temp;
}
tuple_iterator & operator += (int i) {
current_+=i;
return *this;
}
difference_type operator - (const tuple_iterator & ti) const {
return current_ - ti.current_;
}
bool operator < (const tuple_iterator &ti) const {
return index < ti.index;
}
bool operator > (const tuple_iterator &ti) const {
return index > ti.index;
}
bool operator <= (const tuple_iterator &ti) const {
return index <= ti.index;
}
bool operator >= (const tuple_iterator &ti) const {
return index >= ti.index;
}
bool operator == (tuple_iterator const & ti) const {
return (tuple == ti.tuple) && (index == ti.index);
}
bool operator != (tuple_iterator const & ti) const {
return !(*this == ti);
}
};

template <>
class tuple_iterator <std::tuple<>>
{
public:
tuple_iterator(std::tuple<>, size_t i = 0) {}
};


The tuple_iterator class provides the usual typedefs (e.g., difference_type, value_type, pointer, reference, and iterator_category) and overloaded operators (e.g., *, ->, [], +, -, +=, -=, -, +, <, >, <=, >=, ==, !=) to support the requirements of random access iterator. Just like tuple_array class it caches a pointer to the last element that was dereferenced. It goes through O(N) comparisons only if the tuple iterator is dereferenced at a different index than what is cached. A specialization of tuple_iterator for empty tuple is also provided. It has no members other than a constructor because there is nothing to dereference to!

Finally, we need a way to create the begin and end iterator from a non-empty tuple. We add the corresponding functions.

template <typename... Args>
tuple_iterator <std::tuple<Args...>> begin(std::tuple <Args...> &t)
{
return tuple_iterator <std::tuple<Args...>>(t, 0);
}

template <typename... Args>
tuple_iterator <std::tuple<Args...>> end(std::tuple <Args...> &t)
{
return tuple_iterator <std::tuple<Args...>>(t);
}


If no index is passed to the iterator constructor, it points to the end of the tuple. The internal index of such an iterator is same as the size of the tuple. An iterator at the beginning has index = 0 -- the first element. Using the iterators is now straightforward. I do not discuss constant and reverse iterators here.

int main(void)
{
auto tuple = std::make_tuple(10, 20, 30, 40);
auto ta = make_tuple_array(4, 2, 1);

std::copy(begin(tuple), end(tuple), std::ostream_iterator<int>(std::cout, " "));
std::sort(begin(ta), end(ta));

for(int i : ta)
{
std::cout << i << std::endl;
}

return 0;
}


I think, this rather naive exercise turned out to be quite interesting. Hopefully, you enjoyed as much as I did. Live code.

Wednesday, January 11, 2012

General-purpose Automatic Memoization for Recursive Functions in C++11

Memoization is a widely known optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs. Repeated calculations are avoided by reusing previously computed results, which must be cached such that look-up is faster than recomputing.

Consider a simple fibonacci program
unsigned long fibonacci(unsigned n)
{
return (n < 2) ? n : fibonacci(n - 1) + fibonacci(n - 2);
}
This algorithm is a frustratingly slow way of computing the Nth fibonacci number (N starting at 0). It does a lot of redundant recomputations. But the beauty of this program is that it is really simple. To speed it up without changing its logic significantly, we could use memoization.

Using some clever C++11 techniques, it is possible to memoize this function, which looks like below.
unsigned long fibonacci(unsigned n)
{
return (n < 2) ? n :
memoized_recursion(fibonacci)(n - 1) +
memoized_recursion(fibonacci)(n - 2);
}
To solve this problem, I took inspiration from this post on automatic memoization. I'll go in lot more detail here including recursive functions and memory management. Here we go!

The memoize function I'm using is slightly different than that of the post above.
template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)>
memoize(ReturnType (*func) (Args...))
{
auto cache = std::make_shared<std::map<std::tuple<Args...>, ReturnType>>();
return ([=](Args... args) mutable {
std::tuple<Args...> t(args...);
if (cache->find(t) == cache->end())
(*cache)[t] = func(args...);
return (*cache)[t];
});
}
Function memoize accepts a pointer to a free function, wraps it in a lambda, and turns the lambda into a std::function. Returning a a std::function is a common C++11 idiom of returning a lambda from a function that creates it. The implementation of the lambda is pretty straight forward if you are familiar with C++11 variadic templates. It creates a tuple of arguments and checks if it exists in the cache. In that case, the stored result is returned instead of recomputing it. The cache used for mapping arguments to the return value, is allocated dynamically. A std::shared_ptr manages the memory. The lambda copies the std::shared_ptr by value. As long as there is at least one std::function alive, the cache will remain intact.

Memoized functions may be called from different places. It is quite cumbersome to pass the memoized function everywhere it is called. There should be a way to look up a memoized version of the function without loosing the state. So our next step is to make the same memoized function available from anywhere in the program. We need a map of function pointer to a memorized std::function. Specifically, we need a std::unordered_map for fast lookup.
template <typename F_ret, typename...  F_args>
std::function<F_ret (F_args...)>
memoized_recursion(F_ret (*func)(F_args...))
{
typedef std::function<F_ret (F_args...)> FunctionType;
static std::unordered_map<decltype(func), FunctionType> functor_map;

if(functor_map.find(func) == functor_map.end())
functor_map[func] = memoize(func);

return functor_map[func];
}
Here I introduce "memoized_recursion" function that our recursive fibonacci function is calling. It has a static std::unordered_map. It simply looks up the memorized std::function based on the function pointer value. If it does not find one, it creates it and stores it for subsequent access. Function pointers are unique; so there are no collisions possible. Here is how to call it.
memorized_recursion(fibonacci)(10);
The solution is not finished yet though. Memoization obviously builds up state very fast. If many functions are memoized with a large number of parameters, the state grows explosively. There must be some way to reclaim the memory.

Remember that the memoized state grows in the lambda. The dynamically allocated map stores the cache for corresponding function. We need to access the object that is hidden inside a lambda. Lambda has a compiler-defined type and only thing you can do with it is call it. So how would we clear the cache it is building up?

The answer is surprisingly simple! Just assign the memoizer (the lambda) with another default initialized memoizer.

We already have memoize function, which returns a default initialized memoizer. We simply assign the new one in place of the old one. Here’s how the new memoized_recursion looks like
enum class Cache : unsigned int { NO_RECLAIM, RECLAIM };

template <typename F_ret, typename... F_args>
std::function<F_ret (F_args...)>
memoized_recursion(F_ret (*func)(F_args...), Cache c = Cache::NO_RECLAIM)
{
typedef std::function<F_ret (F_args...)> FunctionType;
static std::unordered_map<decltype(func), FunctionType> functor_map;

if(Cache::RECLAIM == c)
return functor_map[func] = memoize(func);

if(functor_map.find(func) == functor_map.end())
functor_map[func] = memoize(func);

return functor_map[func];
}
I’m using strongly typed enums to pass programmer’s intent to clear the cache. Here is how you call it.
memoized_recursion(fibonacci, Cache::RECLAIM);

Purely Static Memoizer


Strictly speaking, using an std::unordered_map in memoized_recursion function is not necessary. It is an O(1) mapping of function pointers to their corresponding memoized function objects (lambda wrapped in a std::function). An alternative way of achieving the same mapping is using purely static memoizer. I call it pure because there is no dynamic allocation like in std::unordered_map. The functors are stored as static objects only. This is possible only if memoized_recursion can be specialized individually for all possible free functions! Note that each free function is guaranteed to have a unique pointer value and pointer values can be used as template parameters. So here is how to combine all these things in a static_memoizer.
template <typename Sig, Sig funcptr>
struct static_memoizer;

template <typename F_ret, typename... F_args, F_ret (*func)(F_args...)>
struct static_memoizer<F_ret (*)(F_args...), func>
{
static
std::function<F_ret (F_args...)> &
get(Cache c = Cache::NO_RECLAIM)
{
static std::function<F_ret (F_args...)> mfunc (memoize(func));

if(Cache::RECLAIM == c)
mfunc = memoize(func);

return mfunc;
}
};

#define STATIC_MEMOIZER(func) static_memoizer<decltype(&func), &func>


The STATIC_MEMOIZER macro simplifies the use of the static_memoizer. It extracts the type of the function pointer using decltype and passes it (the type) as the first parameter of the template. The second parameter is the actual function pointer. Passing the function pointer as a template parameter is important because many functions potentially share the same signature but never the same pointer.

The static objects used by the static_memoizer are different from that of memoized_recursion. So we've to rewrite the fibonacci function to use the static_memoizer.
unsigned long fibonacci(unsigned n)
{
return (n < 2) ? n :
STATIC_MEMOIZER(fibonacci)::get()(n - 1) +
STATIC_MEMOIZER(fibonacci)::get()(n - 2);
}
That's all for now. I hope you enjoyed it.