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, int i = TUPLE_SIZE)
: tuple(&t),
current_(i),
last_(i-1),
ref_(&TupleAt<Tuple>::get(*tuple, last_))
{}
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.

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.