Using queues with boost::asio - Part I

There are things known, and there are things unknown... and in between there are the doors

-- The Doors adopted the saying of William Blake

Ones in a while I stumble when a boost::asio based design suddenly requires me to listen on an in-memory queue or any other queue for that matter. Usually the way out is adding one or more threads to the design. A better way would be to have an actual boost::asio queue listener available. This is what this blog item is about.

Introduction

Some time ago I finally sat down and hacked in a small queue listener aligned with the boost::asio framework. The design is simple and somewhat generic and is described in this blog entry together with the code and sample tests.

Also, as you will see, there is no magic in the machinery behind boost::asio IO objects - they are in fact rather simple and just require some thought before designing and coding them.

This blog entry describes a simple extension to boost::asio which listens on queues. The queue must have certain characteristics. A simple queue tailored for working with the queue listener is provided in the code. A small example shows how the queue listener can be used.

In case you find bugs or blatant errors in design, code or both please feel free to contact me. Also, if you want to get directly to the code skip the following sections and go to the end of this blog item.

The code is a first cut, it works but there are some features that are missing and some parts that should probably be thought through more carefully.

What I want

I'll start with an example showing what I would like to be able to do:

// queue listener handler for queue 1
template<typename T>
void qhandler1(boost::system::error_code const&ec,T item,boost::asio::simple_queue_listener<T>*asioq,shared_ptr<boost::asio::simple_queue<string>>q1){
  if(!ec){
    // process queue item
    // ...

    // re-charge queue listener
    asioq->async_deq(q1,std::bind(qhandler1<T>,_1,_2,asioq,q1));
  }
}
// test program
int main(){
  try{
    // underlying queue
    shared_ptr<boost::asio::simple_queue<string>>q1{new boost::asio::simple_queue<string>};

    // asio io service
    boost::asio::io_service ios;

    // asio queue listeners
    boost::asio::simple_queue_listener<string>qlistener1(ios);
    qlistener1.async_deq(q1,std::bind(qhandler1<string>,_1,_2,&qlistener1,q1));

    // ... setup other asio objects

    // run io service
    ios.run();
  }
  catch(exception const&e){
    BOOST_LOG_TRIVIAL(debug)<<"cought exception: "<<e.what();
  }
}

The queue I use here, boost::asio::simple_queue, is a simple queue which supports the requirements of boost::asio::simple_queue_listener. However, any queue should do as long as it implements the required functionalities. I'll describe boost::asio::simple_queue later on.

The queue listener behaves like any other asio objects when there is no more work to be done. When boost::asio detects that there is no more pending work it will no longer generate asynchronous events by calling the handler. The listener also supports creation of multiple IO objects listening on the same or on different queues.

The code runs a separate thread for each IO object to ensure that the thread managing the main io_service object is not blocked. There are other ways to handle it but this way works and is simple to code and understand.

Structure: the rules of the game

Many developers have worked with boost::asio but have not really looked under the hood to see how the IO objects actually work. The best way to understand what's going on inside boost::asio is to read the code of existing extension as well as reading the boost::asio code itself.

Underneath each type of IO object is a single instance of a service object, the boost::asio::io_service::service. Each instance of an IO object has a corresponding implementation object. The service object is responsible for managing the implementation objects. For example, when an implementation object should be destroyed a destroy(Impl) method is called on the service object.

The implementation object is responsible for actually performing the asynchronous operation. In this case the implementation object waits for a message on a queue and pops the message off the queue when one is available.

The code in the boost::simple_queue_listener runs a separate thread for each implementation object so the thread managing the main io_service object is not blocked. There are other ways to design it, but here I've chosen one which is simple and straight forward.

All in all we need to implement three classes: one for the IO object, one for the underlying service and one for the implementation. I'll also implement a simple queue class which will serve as the default queue when using the queue listener. However, the queue listener could also use any other queue implementation as long as it satisfies certain requirements which I'll go through later. It should be noted that the queue class can be used as a standalone class without any dependency on boost::asio.

Behaviour: the rules of the game

There are a few points related to what happens when that are important to understand when implementing an extension to boost::asio. I'll describe a few of them here.

First, service objects are destroyed when the corresponding boost::asio::io_service object is destroyed. This means that service objects may hang around long after there is no more work to be done. Therefore, some care should be taken to ensure that we don't hang onto resources even if there is no work to be done.

It does makes sense that service objects hang around even when there is no more work. After all, we don't know if there will be more work later on for an IO object.

Conceptual when writing an boost::asio extension a simple view to take is a see the boost::asio::io_service as an even loop listening on an internal queue. Other objects, typically the service objects posts events on the queue. Once an event appears in the queue, boost::asio::io_service dispatches the event to a handler.

In the implementation of an asio service, we should be aware of that as long as the service has not been activated, in this case, the boost::asio::async_deq has not been called, the service should not be listening on the underlying queue.

If at the application level there is outstanding work to do (we are blocking on the underlying queue) and we need to stop blocking queue listeners, it is convenient to be able to stop them and receive an aborted error code in the corresponding handler. I have implemented this in the boost::asio::simple_queue even though it is not mandatory to be compatible with boost::simple_queue_listener. I'll show how it works in an example :

// timer pop function
constexpr static size_t tmoSec{3};
void timerPopped1(const boost::system::error_code&ec,boost::asio::deadline_timer*tmo,shared_ptr<boost::asio::simple_queue<string>>q1){
  // disable dequeing (will stop async listener on q1)
  q1->disable_deq(true);
}
  ...

  // create a deadline timer and register it
  boost::asio::deadline_timer tmo(ios,boost::posix_time::seconds(10));
  tmo.async_wait(std::bind(timerPopped1,_1,&tmo,q1));

  ...

The IO object

Implementing the IO object is formulaic:

// forward decl
class queue_listener_impl;
template<typename Impl=queue_listener_impl>class basic_queue_listener_service;

// --- IO Object (used by client) -----------------------------
template<typename Service,typename Queue>
class basic_queue_listener:public boost::asio::basic_io_object<Service>{
public:
  // ctor
  explicit basic_queue_listener(boost::asio::io_service&io_service):
      boost::asio::basic_io_object<Service>(io_service) {
  }
  // async deq operation
  template <typename Handler>
  void async_deq(std::shared_ptr<Queue>q,Handler handler) {
    this->service.async_deq(this->implementation,q,handler);
  }
};
// typedef for using standard service object
template<typename T>
using simple_queue_listener=basic_queue_listener<basic_queue_listener_service<>,simple_queue<T>>;

The main points to notice are:

1. there are two forward declarations, one for an implementation class and one for the service class
2. the basic_queue_listener base class knows about the boost::asio::io_service instance
3. the async_deq method is non-blocking and invokes the service object passing the implementation object as parameter

The Service object

Only a single instance of the service object is created for one type of service. In this case, only one instance of boost::asio:: basic_queue_listener_service is created for one Impl type. The implementation is straight forward :

// --- service class -----------------------------
// (for one io_service, only one object created)
template<typename Impl>
class basic_queue_listener_service:public boost::asio::io_service::service{
public:
  // required to have id of service
 static boost::asio::io_service::id id;

  // ctor
  explicit basic_queue_listener_service(boost::asio::io_service&io_service):
      boost::asio::io_service::service(io_service){
  }
  // dtor
  ~basic_queue_listener_service(){
  }
  // get a typedef  for implementation
  using implementation_type=std::shared_ptr<Impl>;

  // mandatory (construct an implementation object)
  void construct(implementation_type&impl){
      impl.reset(new Impl(this->get_io_service()));
  }
  // mandatory (destroy an implementation object)
  void destroy(implementation_type&impl){
    impl.reset();
  }
  // async sync deq operation
  template <typename Handler,typename Queue>
  void async_deq(implementation_type&impl,std::shared_ptr<Queue>q,Handler handler){
    // this is a non-blocking operation so we are OK calling impl object in this thread
    impl->async_deq(impl,q,handler);
  }
private:
  // shutdown service (required)
  void shutdown_service(){
  }
};
// definition of id of service (required)
template <typename Impl>
boost::asio::io_service::id basic_queue_listener_service<Impl>::id;

The two interesting methods are construct and destroy. In construct I pass the io_service down to the implementation object since I will let the implementation post responses directly to the main io_service. Some people have mentioned that it would be cleaner if I run an io_service directly in the service in a separate thread and let the implementation post responses back to the service. I chose not to do this in order to keep the code as simple as possible.

The destroy method makes sure that we release the implementation object. Notice that the destroy method is called when the io_service object is destructed.

The async_deq method does a non-blocking call which in the implementation object triggers a blocking wait on the underlying queue. This is important since we must ensure that we don't block the main thread of execution. Clearly, by running one or more threads in the service object we could have achieved the same thing. But again, I went for the simplest solution that is both clean, easy to follow and understand.

Also notice that we start the io_service with an asio::io_service::work object so that the run method will continue to run even if when no work is available.

The boost::asio::io_service::id is required even though we don't use it directly.

The Implementation object

The implementation object does the actual work. In this implementation it performs two tasks. First it blocks for an item to appear on a queue. Ones it has the item it posts it on an io_service. The io_service was passed to the implementation object by the service object and corresponds to the main io_service. That is, the de-queued items will appear in a handler specified by the client of the IO object.

The code kicks of a thread in the constructor. It also sets up an io_service which makes it simpler to pass information from the async_deq method to the thread. Remember, the async_deq cannot block since blocking would block the client thread.

// --- implementation -----------------------------
class queue_listener_impl{
public:
  // ctor (set up work queue for io_service so we don't bail out when executing run())
  queue_listener_impl(boost::asio::io_service&post_io_service):
      impl_work_(new boost::asio::io_service::work(impl_io_service_)),
      impl_thread_([&](){impl_io_service_.run();}),
      post_io_service_(post_io_service){
  }
  // dtor (clear work queue, stop io service and join thread)
  ~queue_listener_impl(){
    impl_work_.reset(nullptr);
    impl_io_service_.stop();
    if(impl_thread_.joinable())impl_thread_.join();
  }
public:
  // deque message (post request to thread)
  template<typename Handler,typename Queue>
  void async_deq(std::shared_ptr<queue_listener_impl>impl,std::shared_ptr<Queue>tq,Handler handler){
    impl_io_service_.post(deq_operation<Handler,Queue>(impl,post_io_service_,tq,handler));
  }
private:
  // function object calling blocking deq() on queue
  template <typename Handler,typename Queue>
  class deq_operation{
  public:
    // ctor
    deq_operation(std::shared_ptr<queue_listener_impl>impl,boost::asio::io_service &io_service,std::shared_ptr<Queue>tq, Handler handler):
        wimpl_(impl),io_service_(io_service),work_(io_service),tq_(tq),handler_(handler) {
    }
    // function calling implementation object - runs in the thread created in ctor
    void operator()(){
      // make sure implementation object is still valid
      std::shared_ptr<queue_listener_impl>impl{wimpl_.lock()};

      // if valid, go ahead and do blocking call on queue, otherwise post aborted message
      if(impl){
        std::pair<bool,typename Queue::value_type>ret{tq_->deq()};
        boost::system::error_code ec=(!ret.first?boost::asio::error::operation_aborted:boost::system::error_code());
        this->io_service_.post(boost::asio::detail::bind_handler(handler_,ec,ret.second));
      }else{
        this->io_service_.post(boost::asio::detail::bind_handler(handler_,boost::asio::error::operation_aborted,typename Queue::value_type()));
      }
    }
  private:
    std::weak_ptr<queue_listener_impl>wimpl_;
    boost::asio::io_service&io_service_;
    boost::asio::io_service::work work_;
    std::shared_ptr<Queue>tq_;
    Handler handler_;
  };
  // private data
  boost::asio::io_service impl_io_service_;
  std::unique_ptr<boost::asio::io_service::work>impl_work_;
  std::thread impl_thread_;
  boost::asio::io_service&post_io_service_;
};

The std::weak_ptr is used in the thread to protect against the implementation object being destroyed while the thread is running. It's a simple hack which ensures that the thread won't access data in a non-existing object.

Notice that a thread is created in the constructor which runs the boost::asio::io_service run method. The thread when executing operator() is waiting for request to de-queue items from the underlying queue. It is also interesting to notice that, should the async_deq be called multiple times on the same implementation object, the requests will queue up in the local io_service queue. Even though not recommended because it is confusing, it is possible to make multiple async_deq calls on the same IO object which will then translate to multiple calls to the same implementation object.

If the async_deq would be called using the same IO service but with different queues, the second call would block until the first one de-queues a message from the queue. This is not an ideal way of programming since from the client side it would appear as if the second queue is blocking. A better way is to dedicate one IO object per queue which then will de-queue in its own separate threads.

An alternative design would have been to store the queue in the implementation object and not pass it as a parameter to the async_deq call. This causes its own problems which must be solved but would be an alternative and possibly better design.

Queue requirements

The underlying queue must satisfy some requirements:

1. the queue must have a method deq which must be thread safe
2. the value_type in the queue must be default constructible
3. the value_type in the queue must be copy constructible

A simple example

The example spawns a thread which starts inserting messages in a queue. At the same time a boost::asio::queue_listener picks up messages form the queue. When the receiver has received all messages it does not re-load the async_deq method:

#include "queue_listener.h"
#include <boost/asio.hpp>
#include <boost/log/trivial.hpp>
#include <boost/lexical_cast.hpp>
#include <string>
#include <memory>
#include <thread>
using namespace std;
using namespace std::placeholders;

// some constants
constexpr size_t maxmsg1{10};
constexpr size_t tmoSeleepBetweenSendMs1{100};

// queue listener handler for queue 1
size_t nreceived1{0};
template<typename T>
void qhandler1(boost::system::error_code const&ec,T item,boost::asio::simple_queue_listener<T>*asioq,shared_ptr<boost::asio::simple_queue<string>>q1){
  // print item if error code is OK
  if(ec)BOOST_LOG_TRIVIAL(debug)<<"received item in qhandler1 (via asio), item: <invalid>, ec: "<<ec;
  else{
   BOOST_LOG_TRIVIAL(debug)<<"received item in qhandler1 (via asio), item: "<<item<<", ec: "<<ec;
   if(++nreceived1!=maxmsg1)asioq->async_deq(q1,std::bind(qhandler1<T>,_1,_2,asioq,q1));
  }
}
// queue sender for queue 1
size_t nsent{0};
void senderq1(shared_ptr<boost::asio::simple_queue<string>>q1){
  for(;nsent<maxmsg1;++nsent){
    string item{boost::lexical_cast<string>(nsent)};
    BOOST_LOG_TRIVIAL(debug)<<"sending item \""<<item<<"\"in separate thread ...";
    q1->enq(item);
    this_thread::sleep_for(std::chrono::milliseconds(tmoSeleepBetweenSendMs1));
  }
}
// test program
int main(){
  try{
    // underlying queue
    shared_ptr<boost::asio::simple_queue<string>>q1{new boost::asio::simple_queue<string>};

    // asio io service
    boost::asio::io_service ios;

    // asio queue listeners
    boost::asio::simple_queue_listener<string>qlistener1(ios);
    qlistener1.async_deq(q1,std::bind(qhandler1<string>,_1,_2,&qlistener1,q1));

    // run a sender thread, run io service and join sender thread
    std::thread thrq1{senderq1,q1};
    ios.run();
    thrq1.join();
  }
  catch(exception const&e){
    BOOST_LOG_TRIVIAL(debug)<<"cought exception: "<<e.what();
  }
}
}

Compilation and linking

I compiled the code using gcc4.9 on RedHat and gcc4.10 on Ubunto 12.04.04 with options: -DBOOST_ALL_DYN_LINK -DASIO_STANDALONE. The DASIO_STANDALONE is needed when using C++11 feautures within boost::asio.

Conclusions

There are some improvements that could be made. For example, some mechanisms preventing calls to the deq_async method while there are still outstanding requests could be implemented. This is not as easy as it seems because of raise condition and I therefore skipped it in this implementation.

I didn't bother with implementing synchronous operations. Neither did I implement methods which throw exceptions as opposed to returning an error code. In a full fledge implementation these functionalities must be added. But so far, I see this implementation as an extension to a specific implementation I did for a specific project. But no doubt, the queue extension will evolve to include more features and functionalities.

There is a piece of functionality that is missing: there is no asio support on the side adding items to the queue. Say we want to throttle on the queue. That is, say we want to ensure that there are no more than 10 items at any time in the queue. This could be achieved by implementing a boost::asio::queue_sender which generates events whenever there is room to add another item to the queue. I haven't implemented this yet but will probably do it in the near future and post it as the next blog entry.

The default queue boost::asio::simple_queue should no doubt contain more features. Here I minimized the queue just to save some space in the blog entry. Methods like size, capacity etc. should be added as well as the possibility to incorporate moving of objects as opposed to copying them. This will have to wait until the next round.

The full implementation

boost::asio::queue_listener

#ifndef __QUEUE_LISTENER_H__
#define __QUEUE_LISTENER_H__
#include "simple_queue.h"
#include <boost/asio.hpp>
#include <boost/system/error_code.hpp>
#include <cstddef>
#include <thread>
namespace boost{
namespace asio{

// forward decl
class queue_listener_impl;
template<typename Impl=queue_listener_impl>class basic_queue_listener_service;

// --- IO Object (used by client) -----------------------------
template<typename Service,typename Queue>
class basic_queue_listener:public boost::asio::basic_io_object<Service>{
public:
  // ctor
  explicit basic_queue_listener(boost::asio::io_service&io_service):
      boost::asio::basic_io_object<Service>(io_service) {
  }
  // async deq operation
  template <typename Handler>
  void async_deq(std::shared_ptr<Queue>q,Handler handler) {
    this->service.async_deq(this->implementation,q,handler);
  }
};
// typedef for using standard service object
template<typename T>
using simple_queue_listener=basic_queue_listener<basic_queue_listener_service<>,simple_queue<T>>;

// --- service class -----------------------------
// (for one io_service, only one object created)
template<typename Impl>
class basic_queue_listener_service:public boost::asio::io_service::service{
public:
  // required to have id of service
 static boost::asio::io_service::id id;

  // ctor
  explicit basic_queue_listener_service(boost::asio::io_service&io_service):
      boost::asio::io_service::service(io_service){
  }
  // dtor
  ~basic_queue_listener_service(){
  }
  // get a typedef  for implementation
  using implementation_type=std::shared_ptr<Impl>;

  // mandatory (construct an implementation object)
  void construct(implementation_type&impl){
      impl.reset(new Impl(this->get_io_service()));
  }
  // mandatory (destroy an implementation object)
  void destroy(implementation_type&impl){
    impl.reset();
  }
  // async sync deq operation
  template <typename Handler,typename Queue>
  void async_deq(implementation_type&impl,std::shared_ptr<Queue>q,Handler handler){
    // this is a non-blocking operation so we are OK calling impl object in this thread
    impl->async_deq(impl,q,handler);
  }
private:
  // shutdown service (required)
  void shutdown_service(){
  }
};
// definition of id of service (required)
template <typename Impl>
boost::asio::io_service::id basic_queue_listener_service<Impl>::id;

// --- implementation -----------------------------
class queue_listener_impl{
public:
  // ctor (set up work queue for io_service so we don't bail out when executing run())
  queue_listener_impl(boost::asio::io_service&post_io_service):
      impl_work_(new boost::asio::io_service::work(impl_io_service_)),
      impl_thread_([&](){impl_io_service_.run();}),
      post_io_service_(post_io_service){
  }
  // dtor (clear work queue, stop io service and join thread)
  ~queue_listener_impl(){
    impl_work_.reset(nullptr);
    impl_io_service_.stop();
    if(impl_thread_.joinable())impl_thread_.join();
  }
public:
  // deque message (post request to thread)
  template<typename Handler,typename Queue>
  void async_deq(std::shared_ptr<queue_listener_impl>impl,std::shared_ptr<Queue>tq,Handler handler){
    impl_io_service_.post(deq_operation<Handler,Queue>(impl,post_io_service_,tq,handler));
  }
private:
  // function object calling blocking deq() on queue
  template <typename Handler,typename Queue>
  class deq_operation{
  public:
    // ctor
    deq_operation(std::shared_ptr<queue_listener_impl>impl,boost::asio::io_service &io_service,std::shared_ptr<Queue>tq, Handler handler):
        wimpl_(impl),io_service_(io_service),work_(io_service),tq_(tq),handler_(handler) {
    }
    // function calling implementation object - runs in the thread created in ctor
    void operator()(){
      // make sure implementation object is still valid
      std::shared_ptr<queue_listener_impl>impl{wimpl_.lock()};

      // if valid, go ahead and do blocking call on queue, otherwise post aborted message
      if(impl){
        std::pair<bool,typename Queue::value_type>ret{tq_->deq()};
        boost::system::error_code ec=(!ret.first?boost::asio::error::operation_aborted:boost::system::error_code());
        this->io_service_.post(boost::asio::detail::bind_handler(handler_,ec,ret.second));
      }else{
        this->io_service_.post(boost::asio::detail::bind_handler(handler_,boost::asio::error::operation_aborted,typename Queue::value_type()));
      }
    }
  private:
    std::weak_ptr<queue_listener_impl>wimpl_;
    boost::asio::io_service&io_service_;
    boost::asio::io_service::work work_;
    std::shared_ptr<Queue>tq_;
    Handler handler_;
  };
  // private data
  boost::asio::io_service impl_io_service_;
  std::unique_ptr<boost::asio::io_service::work>impl_work_;
  std::thread impl_thread_;
  boost::asio::io_service&post_io_service_;
};
}
}

boost::asio::simple_queue

#ifndef __SIMPLE_QUEUE_H__
#define __SIMPLE_QUEUE_H__
#include <utility>
#include <queue>
#include <mutex>
#include <condition_variable>
namespace boost{
namespace asio{

// a simple thread safe queue used as default queue in boost::asio::queue_listener
template<typename T,typename Container=std::queue<T>>
class simple_queue{
public:
  // typedef for value stored in queue
  // (need this so we can create an item with default ctor)
  using value_type=T;

  // ctors,assign,dtor
  simple_queue()=default;
  simple_queue(simple_queue const&)=delete;
  simple_queue(simple_queue&&)=default;
  simple_queue&operator=(simple_queue const&)=delete;
  simple_queue&operator=(simple_queue&&)=default;
  ~simple_queue()=default;

  // put a message into queue
  void enq(T t){
    std::lock_guard<std::mutex>lock(mtx_);
    q_.push(t);
    cond_.notify_all();
  }
  // dequeue a message (return.first == false if deq() was disabled)
  std::pair<bool,T>deq(){
    std::unique_lock<std::mutex>lock(mtx_);
    cond_.wait(lock,[&](){return !deq_enabled_||!q_.empty();});

    // if deq is disabled or queue is empty return 
    if(!deq_enabled_||q_.empty()){
      return std::make_pair(false,T{});
    }
    // check if we have a message
    std::pair<bool,T>ret{std::make_pair(true,q_.front())};
    q_.pop();
    return ret;
  }
  // cancel deq operations (will also release blocking threads)
  void disable_deq(bool disable){
    std::unique_lock<std::mutex>lock(mtx_);
    deq_enabled_=!disable;
    cond_.notify_all();
  }
  // check if queue is empty
  bool empty()const{
    std::unique_lock<std::mutex>lock(mtx_);
    return q_.empty();
  }
private:
  mutable std::mutex mtx_;
  mutable std::condition_variable cond_;
  bool deq_enabled_=true;
  Container q_;
};
}
}
#endif

Separation of Concerns and Components

Do you use any modern technologies such as Java or do you just use older ones like C++?

-- Interviewer

Stating the obvious - or writing out of frustration

I'm writing this because of the apparent confusion between separation of unrelated concerns in relationship to design of features in IT systems and between separation of unrelated concerns related to packaging of IT features into executable components.

There is, especially among WEB developers, a tendency to 'over componentize' architectures. Many relatively small systems (which some years ago would have been called C hacks) contains http servers, database servers, service brokers and application servers, just to mention a few, when in fact the very same IT systems could be written as compact small executable UNIX programs.

Not only does it add to the cost (maintenance, operability, development etc.) to develop systems containing more components than is needed. But it is also ugly and an abomination to the very core of elegant IT design. This is especially true when small internal IT systems contains multiple application servers, several relational databases and other heavy weight components which, twenty years ago would have been written within a few days as small C programs.

Why has development of relatively small IT systems taken this path? I can only guess. Myself I believe that the fundamental problem is that WEB technologies has become industry standard regardless of if the problem is a Web related problem or not and regardless of if Industry Standards matters in the context at hand.

Maybe one reason could also be that calling something an IT System has far more significance when it comes to influencing upper management to cut you a slice of the budget than simply calling it what it maybe should be called: a small stanalone application or maybe just simply a C hack.

What's a component?

What I mean by a Component is something that can be deployed on a computer and made to execute and perform some (hopefully) useful activity.

For example, an HTTP server such as Apache httpd is a component. My program printing 'hello world' is also a component. A more useful component is my Queue Manager routing messages from one queue to another. Yet another component is an Oracle server.

Grey areas

In other words, for something to qualify as being component it must be executable. It cannot be a snippet of C++ code, a piece of Java code or something that cannot be executed by an execution environment. Of course, there are grey areas. Should a (compiled) EJB be seen as a component? Here I consider an EJB to be a component since it can be deployed in a jar file, the jar file deployed in an application server and executed by a JEE app server which runs on top of the underlying operating system.

As a side note, surely something is wrong here - why build such a large stack of execution layers (unix, jee container, jar/war files) just to execute a single component. I love UNIX linkers since I do not have to write nor generate XML files to tell - in an old fashioned JCL IBM way (did we just step back 30 years with the introduction of modern application servers?) - exactly how my software should run. The linker is my friend, the jar/war configuration files are not.

Is separation of concern always applicable?

Separation of concerns usually means separation of unrelated concerns. What unrelated means here is of course highly subjective and belongs in the realm of IT system design. I say subjective since it is dependent on what the focus on an abstraction is. However, I won't make much fuss over if concerns, in general, are unrelated or not, since when it comes to components it doesn't really matter.

It would appear that separation of concerns is always applicable in IT development. After all, we have all been brainwashed to believe by schools, by dogmatic colleagues, managers that have picked up a buzz word here or there or colleagues and IT developers with decades of experience in IT architecture even though only on paper (bah ... why are requests tied to processing through a queue ... don't you know about 'separation of concerns). Of course separation of concern is important in certain contexts but is in fact less important and often harmful in many other contexts.

When is it useful to separate unrelated concerns

Clearly when I design a piece of software drawing boxes, mapping boxes to classes and functions I'll separate an audit log from some machinery translating text from one language to another.

So far so good. But here is the crux. Many developers extend this separation to the component level. That is, logging in an audit log is done by making a call to a separate program. The translation of text from one language to another is done in yet another program. Every single concern that is non-related is separated at the component level. Sometimes one of the most blatantly wrong separation of concern at the component level is the separation of the user interface - possibly a WEB service WSDL based interface - into a separate JEE application server or an http server.

Now, before calling me names ... after all, not using an off the shelf standalone http server or a JEE server for WEB based stuff is blasphemy ... I am not saying that embedding web based interfaces in an application is a general soltion that solves all problems. But I am saying, that it does solve many more problems than most developers and architects are often aware off.

So, what's the problem I'm trying to get at here? The problem is that it is really difficult to deal with systems that have quite a few parts and where the parts are all mostly different. The normal way of solving problems with such systems is to use separation of concern. Typically software systems fall in to this category

Medium number systems

From a system theoretical view point, when designing software systems, we enter the realm of medium number systems - system consisting of a medium number of parts where the parts are different from each other. Such systems are are notoriously difficult to design, analyse and manage. We are dealing with a medium number system when designing the software (that's why it is important to separate unrelated concerns when designing), but there is no need to extend the problematic issues to the component level.

Since the parts are all different and we don't have lots and lots of them - here I mean many millions or billions - we can't use statistical methods to solve our problems. Even worse, since the parts are different and we do have quite a few of them we can't setup equation to analytical come up with a solution (assuming that we actually could formulate the problem as a set of equations).

One solution to the problem is to package functionalities into components so we get fewer parts to manage - even though the parts will still be different from each other.

What do we solve by packaging stuff into components?

First, we end up with fewer parts. We can focus on getting the components right and stop worrying what's inside them.

The second problem we solve is that we don't expose connections between parts that don't need to be managed by operators. For example, internal queues which really are internal implementation details are not exposed and do not need to be managed through configuration files and complex queuing servers. The same is often true for databases which can be embedded inside a component. In other words, the 'dirty' environment outside a component will not have an impact on the internal work being done inside the component.

It's worthwhile to make a mental analogy with electronic integrated circuits. Connections between capacitors, transistors and other gadgets are not exposed to the polluted and dangerous environment outside the integrated circuit.

This is not only true for electronic components. Just imagine that a car engine did not come as a single component - a block containing valves, cylinders, fuel injection electronics etc., - but was distributed across a system communicating through some sort of electronic mechanical bus. Most likely a 20K car would cost at least 200K if that was the case.

A small text processing system

I want to design a system processing text. Specifically I want to translate files containing text from one language to another language.

The design concerns I have are a user interface, requests from users, auditing and billing, internal representation of jobs to be executed (a job represents a file to be translated), segmentation of text in to sentences, translation of sentences and distribution of sentences to be translated across a limited set of resources that can translate sentences.

At a high level it is pretty straight forward. I can separate the various concerns and the design becomes simple

Now, the typical WEB based system (I assume I'll expose the service as a WEB service) consists of a web server and/or JEE server, a number of asynchronous communication mechanisms, a relational database, a backend system and some logging system. The point I will make here is that there are far too many components for such a simple application. Instead of separating the various concerns at the component level, I propose to simple build a single application which internally encapsulates the various concerns.

As an example of the component explosion I don't want to achieve is what I saw a few years ago in a relatively simple system (again, in the old days it would have been called a C hack). Most communication between components in the system were done via one or another asynchronous communication mechanism or, even though the mechanism was not asynchronous it was used in an asynchronous way. I stopped counting at 8 where some of the way to communicate asynchronously were ftp, web services (with call-backs), http, file system queues (using both polling and inotify),JMS, database tables, email etc.

The design

Now, how would I go ahead and design my text processing system? Of course it depends on the scale of the processing. If the system is not too large, say I process a ten or twenty thousand request per day, I would design my classes as usual by separating unrelated concerns. I would implement them and test them. Ones I'm happy that my various 'concerns' do their job right I would simply package them all in a single application.

First and foremost I would avoid, as far as is possible to separate the web service interface from the rest of the system. If I can build single application containing an embedded HTTP server handling the http service request I've come a long way towards making the system simple and operable.

The idea of packaging multiple concerns inside a single executable (component) may of course not scale if the system grows over some limit. However, the almost idiotic notion that everything has to be scalable to any limit without first analysing if the system will ever reach a limit where scalability really matters has killed more than one system.

If we know that we'll never have more than a few thousand of requests per day, why bother to build a full blown industrial system which would scale to 100s of millions of requests per day? If the day would ever come when that happens, we keep our core design which is based on separation of concern and repackage the system using separate HTTP servers and external databases.

Conclusions

Even though being heavily criticized by JEE indoctrinated colleagues and friends, I have yet to hear valid logical arguments why web based system - as if web based is something special as far as IT design is concerned - should not be written as single monolithically applications where it makes sense. The answer I usually get is: everyone knows Apache httpd/JEE. However, even with exhausting ones brain it's clear that just because everyone knows Apache httpd/JEE is simply not a good eneough reason to use them where they don't fit in.

It appears that the 'industry standard' (which by the way benefits the Industry, not the Customer), is hell bent on ensuring that web based applications are broken up into as many separate components as is possible. Typically, a simple web service based application based on JEE has an application server, a relational database, a queuing system, a backend system plus a few more axillary services for generation of identifiers and other goodies.

I am a architect/developer/programmer working mostly in C++ trying to maintain the idea of writing compact, fast IT systems with small foot print which are easy to maintain. Using C++ together with tools such as GSOAP and embedded databases I've built simple web based services written as single applications, having small foot print, being many times faster than JEE based ones, are operable and are scalable up to a certain point.

In the old days such applications would have been called C hacks not IT Systems. For in house use and often for applications exposed on the WEB this is often more than enough.

Heterogeneous return values from thread pools

To perform an analysis means decomposing a situation or problem into its constituents. However, there are not any “primitives” that naturally exist. The components defined are arbitrary and depend on individual goals and methods of calculation. The basic elements of a fire are different to a fire fighter, an insurance claims adjuster, and an arson investigator.

-- Gary Klein, Sources of Power

This blog item is about a small extension to a simple thread pool which makes life a little more bearable when writing code running many tasks in parallel where the tasks have return values of different types.

The code from this entry and some of the previous entries can be retrieved from: https://github.com/hansewetz/blog

A simple thread pool (found somewhere on the Web)

Thread pools are useful constructs. When quickly scribbling down prototype code for multi-threaded applications or experimenting with how to best manage parallelisation of code, having a couple of good flexible thread pools is indispensable.

The thread pool I'll use as a base can be found all over the Internet. It's a simple pool managing a queue of pending tasks and a collection of threads. It does not use condition variables to wake up threads when more work is available. Instead a thread when finding the task queue empty simply yields until the next time the system wakes it up. The pool implementation is fairly standard so I'll just give the code here:

#include <iostream>
#include <thread>
#include <atomic>
#include <queue>
#include <vector>
#include <tuple>
#include <mutex>
#include <future>
#include <chrono>

// task class (hides actual type of function to be executed)
class task{
    struct base{
      virtual void call()=0;
    };
    template<typename F>
    struct derived:base{
      derived(F&&f):f_(std::move(f)){}
      void call(){f_();}
      F f_;
    };
    std::unique_ptr<base>impl_;
public:
    // ctor, assign, dtor
    task()=default;
    template<typename F>task(F&&f):impl_(new derived<F>(std::move(f))){}
    task(task&&other):impl_(std::move(other.impl_)){}
    task&operator=(task&&tsk){impl_=std::move(tsk.impl_);}

    // call
    void operator()(){impl_->call();}
};
// thread pool class
class tpool{
public:
  // ctor
  tpool(std::size_t nthreads):nthreads_(nthreads),done_(false){
    for(std::size_t i=0;i<nthreads_;++i){
      std::thread thr(&tpool::thread_func,this);
      threads_.push_back(std::move(thr));
    }
  }
  // dtor
  ~tpool(){
    done_=true;
    for(auto&t:threads_)t.join();
  }
  // get #of threads
  std::size_t nthreads()const{return nthreads_;}

  // submit task
  template<typename F,typename R=typename std::result_of<F()>::type>
  std::future<R>submit(F f){
    std::packaged_task<R()>pt(f);
    auto ret=std::move(pt.get_future());
    add_task(task(std::move(pt)));
    return ret;
  }
private:
  // thread function
  void thread_func(){
    while(!done_){
      try{
        task tsk;
        if(try_get(tsk))tsk();
        else std::this_thread::yield();
      }
      catch(...){
        done_=true;
      }
    }
  }
  // get next task
  bool try_get(task&tsk){
    std::unique_lock<std::mutex>lock(qmtx_);
    if(taskq_.empty())return false;
    tsk=std::move(taskq_.front());
    taskq_.pop();
    return true;
  }
  // add task to queue
  void add_task(task&&tsk){
    std::unique_lock<std::mutex>lock(qmtx_);
    taskq_.push(std::move(tsk));
  }
  // state
  std::size_t nthreads_;
  std::vector<std::thread>threads_;
  std::atomic_bool done_;
  std::queue<task>taskq_;
  std::mutex qmtx_;
};

The submit method wraps the user function in a std::packaged_task, retrieves the std::future from the packaged_task, wraps the std::packaged_task in a task and finally enqueues the task in the task queue. The std::future is returned to the caller.

Once a task is in the task queue, a thread picks it up and executes it. The caller retrieves the return value of the task by waiting for the future:

#include <functional>
using namespace std;

// main test program
int main(){
  // create function returning a string
  auto f=[]()->string{return "Hello";};

  // submit task
  tpool tp(2);
  auto fut=tp.submit(f);
  cout<<fut.get()<<endl;
}

Being lazy and letting others do the waiting

Being a lazy person I would like to be able to submit multiple tasks in one shot, have the thread pool wait for the tasks to complete and have all return values handed to me in one go. Now, again, since I'm lazy I don't want to worry about the tasks having different return types – I just want all return values, regardless of types, to be returned to me in one blob. The solution is clearly to bundle them in a std::tuple.

I'll add the functionality as follows. First I'll expose a variadic template member function taking a variable number of callable objects, possible each returning a different type. Second, I'll submit the tasks while collecting the future for each task. After this I'll wait for the tasks and create a tuple containing the return values. Finally I'll return the tuple:

…
// submit a set of tasks and return a tuple containing results of tasks
  template<typename...F,typename RET=std::tuple<typename std::result_of<F()>::type...>>
  RET submitTasksAndWait(F...f){
    auto futs=submitTasksReturnFuts(f...);
    RET ret;
    waitForFutures(ret,std::move(futs));
    return ret;
  };
private:
  // submit tasks and return futures in a tuple
  template<typename F,typename...G,typename RET=std::tuple<std::future<typename std::result_of<F()>::type>,std::future<typename std::result_of<G()>::type>...>>
  RET submitTasksReturnFuts(F f,G...g){
    auto tu1=make_tuple(std::move(submit(f)));
    auto tu2=submitTasksReturnFuts(g...);
    return std::tuple_cat(std::move(tu1),std::move(tu2));
  }
  template<typename F,typename FUTS=std::tuple<std::future<typename std::result_of<F()>::type>>>
  FUTS submitTasksReturnFuts(F f){
    return std::make_tuple(std::move(submit(f)));
  }
  // wait for futures stored in a tuple and return results
  template<typename R1,typename...R2,typename F1,typename...F2>
  void waitForFutures(std::tuple<R1,R2...>&ret,std::tuple<F1,F2...>&&futs){
    auto r1=std::make_tuple(std::get<0>(futs).get());
    auto r2=tutils::popn_front_tuple<1>(ret);
    auto t2=tutils::popn_front_tuple<1>(futs);
    waitForFutures(r2,std::move(t2));
    ret=std::tuple_cat(std::move(r1),std::move(r2));
  }
  template<typename R1,typename F1,typename RET=std::tuple<R1>>
  void waitForFutures(std::tuple<R1>&ret,std::tuple<F1>&&fut){
    std::get<0>(ret)=std::move(std::get<0>(fut).get());
  }
…

The code uses tutils::popn_front_tuple which pops the first element off a tuple. The function is part of the tutils namespace and can be retrieved from https://github.com/hansewetz/blog. The code can be used as follows:

// main test program
int main(){
  // create function returning another function
  auto f=[]()->string{return "Hello";};
  auto g=[]()->std::size_t{return 17;};

  // create and submit tasks
  tpool tp(2);
  auto res=tp.submitTasksAndWait(f,f,g,f,g,g,g,g,f,f,g,g,g);
  cout<<transform_tuple(type2string_helper(),res)<<endl;
  cout<<"res: "<<res<<endl;
}

What if a task returns void?

The problem with the code in the previous section is that it cannot handle return types of void. I'll solve that by injecting a dummy type void_t in the return tuple when the tasks return value is void.

Before listing the code I'll make a few points. First, I moved the class task inside the tpool class. I also add a meta function fret_type which I use when deducing the return type of a function. Two overloaded functions for retrieving the return value from a future are also added. One returns the actual return value whereas the other returns an object of void_t. Two submit functions are exposed: one taking a tuple containing functions to be submitted and one taking a variadic list of functions (as in the previous example).

For clarity I'll show the entire piece of code in one shot here:

#ifndef __TPOOL_H__
#define __TPOOL_H__
#include "type-utils/type_utils.h"
#include <iosfwd>
#include <thread>
#include <atomic>
#include <queue>
#include <vector>
#include <tuple>
#include <mutex>
#include <future>
#include <chrono>
#include <type_traits>

namespace tutils{

// ------------------- tpool --------------
class tpool{
private:
  // forward decl.
  template<typename F,typename R=typename std::result_of<F()>::type>struct fret_type;
  class task;
public:
  // return type for functions returning void
  struct void_t{};

  // ctor
  tpool(std::size_t nthreads):nthreads_(nthreads),done_(false){
    for(std::size_t i=0;i<nthreads_;++i){
      std::thread thr(&tpool::thread_func,this);
      threads_.push_back(std::move(thr));
    }
  }
  // dtor
  ~tpool(){
    done_=true;
    for(auto&t:threads_)t.join();
  }
  // get #of threads
  std::size_t nthreads()const{return nthreads_;}

  // submit task
  template<typename F,typename R=typename std::result_of<F()>::type>
  std::future<R>submit(F f){
    std::packaged_task<R()>pt(f);
    auto ret=std::move(pt.get_future());
    add_task(task(std::move(pt)));
    return ret;
  }
  // submit tuple of tasks and return a tuple containing results of tasks
  template<typename...F,typename RET=std::tuple<typename fret_type<F>::type...>>
  RET submitTaskTupleAndWait(std::tuple<F...>ftu){
    auto futs=submitTasksReturnFuts(std::forward<decltype(ftu)>(std::move(ftu)));
    RET*dummy=nullptr;
    return waitForFutures(dummy,std::move(futs));
  };
  // submit list of tasks and return a tuple containing results of tasks
  template<typename...F,typename RET=std::tuple<typename fret_type<F>::type...>>
  RET submitTasksAndWait(F...f){
    std::tuple<F...>ftu{std::move(f)...};
    return submitTaskTupleAndWait(std::move(ftu));
  };
private:
  // submit tasks and return futures in a tuple
  template<typename F,typename...G,typename RET=std::tuple<std::future<typename std::result_of<F()>::type>,std::future<typename std::result_of<G()>::type>...>>
  RET submitTasksReturnFuts(std::tuple<F,G...>ftu){
    auto tu1=make_tuple(std::move(submit(std::get<0>(ftu))));
    auto tu2=submitTasksReturnFuts(tutils::popn_front_tuple<1>(ftu));
    return std::tuple_cat(std::move(tu1),std::move(tu2));
  }
  template<typename F,typename FUTS=std::tuple<std::future<typename std::result_of<F()>::type>>>
  FUTS submitTasksReturnFuts(std::tuple<F>ftu){
    return std::make_tuple(std::move(submit(std::get<0>(ftu))));
  }
  // wait for futures stored in a tuple and return results
  template<typename R1,typename...R2,typename F1,typename...F2>
  std::tuple<R1,R2...>waitForFutures(std::tuple<R1,R2...>*,std::tuple<F1,F2...>&&futs)const{
    // use references to futures
    auto&fu1=std::get<0>(futs);
    auto r1=std::make_tuple(get_fut(static_cast<R1*>(nullptr),fu1));
    auto t2=tutils::popn_front_tuple<1>(futs);
    std::tuple<R2...>*dummy;
    auto r2=waitForFutures(dummy,std::move(t2));
    return std::tuple_cat(std::move(r1),std::move(r2));
  }
  template<typename R1,typename F1>
  std::tuple<R1>waitForFutures(std::tuple<R1>*,std::tuple<F1>&&fut)const{
    // use reference to future
    auto&fu1=std::get<0>(fut);
    return std::make_tuple(get_fut(static_cast<R1*>(nullptr),fu1));
  }
  // wait for future and return result
  template<typename R,typename FU>
  R get_fut(R*,FU&fu)const{
    return fu.get();
  }
  template<typename FU>
  void_t get_fut(void_t*,FU&fu)const{
    fu.get();
    return void_t();
  }
  // thread function
  void thread_func(){
    while(!done_){
      try{
        task tsk;
        if(try_get(tsk))tsk();
        else std::this_thread::yield();
      }
      catch(...){
        done_=true;
      }
    }
  }
  // get next task
  bool try_get(task&tsk){
    std::unique_lock<std::mutex>lock(qmtx_);
    if(taskq_.empty())return false;
    tsk=std::move(taskq_.front());
    taskq_.pop();
    return true;
  }
  // add task to queue
  void add_task(task&&tsk){
    std::unique_lock<std::mutex>lock(qmtx_);
    taskq_.push(std::move(tsk));
  }
  // meta function returning 'void_t' as return type if F returns void, else as std::result_of<F>::type
  template<typename F,typename R>
  struct fret_type{
    using type=typename std::conditional<std::is_same<R,void>::value,void_t,R>::type;
  };
  // task class (hides actual type of function to be executed)
  class task{
      struct base{
        virtual void call()=0;
      };
      template<typename F>
      struct derived:base{
        derived(F&&f):f_(std::move(f)){}
        void call(){f_();}
        F f_;
      };
      std::unique_ptr<base>impl_;
  public:
      // ctor, assign, dtor
      task()=default;
      template<typename F>task(F&&f):impl_(new derived<F>(std::move(f))){}
      task(task&&other):impl_(std::move(other.impl_)){}
      task&operator=(task&&tsk){impl_=std::move(tsk.impl_);}

      // call
      void operator()(){impl_->call();}
  };
  // state
  std::size_t nthreads_;
  std::vector<std::thread>threads_;
  std::atomic_bool done_;
  std::queue<task>taskq_;
  std::mutex qmtx_;
};
// print operator for tpool::void_t;
std::ostream&operator<<(std::ostream&os,tpool::void_t const&){return os<<'.';}
}
#endif

I can use the code as follows (notice one of the functions have a void return type):

#include "tpool.h"
#include <functional>
#include <iostream>

using namespace std;
using namespace tutils;

struct Foo{
  Foo(){cout<<"ctor"<<endl;}
  Foo(string const&str){cout<<"string ctor"<<endl;}
  Foo(Foo const&f){cout<<"copy ctor"<<endl;}
  Foo(Foo&&f){cout<<"move ctor"<<endl;}
  Foo&operator=(Foo const&f){cout<<"copy assignment"<<endl;}
  Foo&operator=(Foo&&f){cout<<"move assign"<<endl;}
  ~Foo(){cout<<"dtor"<<endl;}
};
ostream&operator<<(ostream&os,Foo const&foo){return cout<<"foo ";};

// main test program
int main(){
  // create function returning another function
  auto f=[]()->Foo{return Foo("Hello");};
  auto g=[]()->void{cout<<"world"<<endl;};
  function<Foo()>ff=f;

  // create and submit tasks
  {
    tpool tp(2);
    auto res=tp.submitTasksAndWait(ff,f,[]()->int{return 6;},g);
    cout<<transform_tuple(type2string_helper(),res)<<endl;
    cout<<"res: "<<res<<endl;
  }
  {
    tpool tp(2);
    auto tu=make_tuple(ff,f,[]()->int{return 6;},g);
    auto res=tp.submitTaskTupleAndWait(tu);
    cout<<transform_tuple(type2string_helper(),res)<<endl;
    cout<<"res: "<<res<<endl;
  }
}

Conclusions

In this item I only gave a mini example of how to customise a simple thread pool. However, with features from C++11 such as variadic templates and tuples together with utilities in type_traits it's relatively simple, in general, to implement flexible compile time polymorphic data structures. Getting used to developing code on both sides of the fence dividing compile time from runtime requires quite a lot of painful late night coding, often pushing ones patience to the limit. However, ones the Aha! moment hits you, you might wonder why didn't I code like this all along.

Variadic templates and all that stuff

In general, we mean by any concept nothing more than a set of operations; the concept is synonymous with a corresponding set of operations.

-- Percy Bridgman, The Logic of Modern Physics, paper

The last year or so I've drifted towards using variadic templates, tuples and meta function in my day to day programming. It's not clear if this is a good thing or not, but the reality is that it's fun and I continuously find new ways of solving old problems. Ones in a while I also find elegant ways of solving new problems using variadic templates, tuples and meta programming techniques.

This entry is about a small collection of functions which I tend to use regularly.

Downloading the code

The code from this entry and some of the previous entries can be retrieved from: https://github.com/hansewetz/blog

A few examples before starting to code

Here is an example showing basic printing of a tuple:

// create a tuple and print it
auto tu=std::make_tuple(1,"Hello",string("world"));
cout<<tu<<endl;

The result is: [1 Hello world ]

Sometimes it's also useful to print the types of tuples elements:

auto z1=make_tuple(1,"hello",2,std::plus<int>());
cout<<type2string(z1)<<endl;

The result is: (std::tuple<int, char const*, int, std::plus<int> >)

Another way to print the element types, avoiding printing the tuple type is as follows:

auto z2=std::make_tuple(1,"hello",2,std::plus<int>());
cout<<transform_tuple(type2string_helper(),z2)<<endl;

The result is: [(int) (char const*) (int) (std::plus<int>) ]

The function transform_tuple is a function, I'll get to later, which generates a new tuple by applying a function object to each one of the tuples elements.

Another type of example folds the tuple into a single value:

auto c=make_tuple(1,2,3,4,5,6);
cout<<"six factorial: "<<foldl_tuple(multiplies<int>(),c)<<endl;

The result is: six factorial: 720.

Clearly any binary function can be used. For example, a function which stringifies it's parameters and concatenates them or a function adding two values often comes handy.

Sometimes its useful to rearrange elements in a tuple. For example, say we want to create a tuple which have element 5 first and element 2 last:

auto z3=make_tuple(0,1,2,3,4);
cout<<"rearanged tuple: "<<transform_tuple(indlist<4,0,1,3,2>(),z3)<<endl;

The result is: rearranged tuple: [4 0 1 3 2 ]

The indlist is a template struct which will be part in one way or another of most of the tools in this blog entry.

Before getting started with implementations I'll give a code sample of a very powerful idea. The example below shows how a tuple can be chopped up into individual types and passed as a set of arguments to a function:

// add tuple elements together
auto z5=make_tuple(1,2.3,7);
cout<<apply_tuple(adder(),z5)<<endl;

The output is: 10.3.

The type adder is a utility struct (which I'll show later) calculating the sum of its' input arguments.

The indlist type

It turns out that a compile time list of integers is very helpful when manipulating tuples. An indlist is a simple struct defined as:

template<std::size_t...i>struct indlist{};

With indlists it's possible to manipulate tuple elements in pretty amazing ways. So before starting to make use of indlists let's develop a few tools for managing them. First I need to be able to create indlists. A straight forward way is to write something like:

using IL=indlist<0,4>;

It will become tedious to always manually create them by enumerating integers. Instead I want create a couple of utilities for creating them based on some patterns. Before doing this I'll create two meta functions :

// push front an index to an indlist
template<std::size_t a,typename IL>struct push_front;
template<std::size_t a,size_t...i>
struct push_front<a,indlist<i...>>{
  using type=indlist<a,i...>;
};
// push back an index to an indlist
template<std::size_t a,typename IL>struct push_back;
template<std::size_t a,size_t...i>
struct push_back<a,indlist<i...>>{
  using type=indlist<i...,a>;
};

Now it's easy to define a few indlist creation functions:

// make an indlist from [start ... end]
template<std::size_t start,std::size_t end>
struct make_indlist_from_range{
  using type=typename push_front<start,typename make_indlist_from_range<start+1,end>::type>::type;
};
template<std::size_t i>
struct make_indlist_from_range<i,i>{
  using type=indlist<i>;
};
// make an indlist with N elements of value V
template<std::size_t N,std::size_t V>
struct make_uniform_indlist{
  using type=typename push_back<V,typename make_uniform_indlist<N-1,V>::type>::type;
};
template<std::size_t V>
struct make_uniform_indlist<0,V>{
  using type=indlist<>;
};
// make an indlist from a tuple
template<typename Tuple>struct make_indlist_from_tuple;
template<typename...Args>
struct make_indlist_from_tuple<std::tuple<Args...>>{
  using type=typename make_indlist_from_range<0,sizeof...(Args)-1>::type;
};
template<>
struct make_indlist_from_tuple<std::tuple<>>{
  using type=indlist<>;
};

Some readers may have seen other ways of constructing indlists. For example, it is possible to construct an indlist as follows:

// indlist
template<std::size_t...i>struct indlist{};

// make an indlist from [start ... end]
template<std::size_t endind,std::size_t ind,std::size_t...i>
struct indlist_builder:indlist_builder<endind,ind+1,i...,ind>{
};
template<std::size_t endind,std::size_t...i>
struct indlist_builder<endind,endind,i...>{
  using type=indlist<i...,endind>;
};
template<std::size_t start,size_t end>
struct make_indlist_from_range{
  using type=typename indlist_builder<end,start>::type;
};

Manipulating indlists

Now that we know how to create indlists it's time to code up a few tools for manipulating them. The tools will come in handy later on so it's not a bad idea to have them ready. I've already coded push_front and push_back. Before coding the related a few more push functions together with and pop functions I'll code a helper function reversing an indlist:

// reverse an indlist (re-use push_back)
template<std::size_t i,size_t...j>
struct reverse<indlist<i,j...>>{
  using R=typename reverse<indlist<j...>>::type;
  using type=typename push_back<i,R>::type;
};
template<>
struct reverse<indlist<>>{
  using type=indlist<>;
};

It's now easy to code the push and pop functions:

// pop front index from indlist
template<typename IL>struct pop_front;
template<std::size_t i,std::size_t...j>
struct pop_front<indlist<i,j...>>{
  using type=indlist<j...>;
};
// pop back element from indlist
// (reverse, pop front, reverse)
template<typename IL>
struct pop_back{
  using R0=typename reverse<IL>::type;
  using R1=typename pop_front<R0>::type;
  using type=typename reverse<R1>::type;
};
// pop n elements from front
template<std::size_t N,typename IL>
struct popn_front{
  using TMP=typename pop_front<IL>::type;
  using type=typename popn_front<N-1,TMP>::type;
};
template<typename IL>
struct popn_front<0,IL>{
  using type=IL;
};
// pop n elements from back
template<std::size_t N,typename IL>
struct popn_back{
  using TMP=typename pop_back<IL>::type;
  using type=typename popn_back<N-1,TMP>::type;
};
template<typename IL>
struct popn_back<0,IL>{
  using type=IL;
};

By now it should be clear that I've not always coded the most efficient solution. Since compilation of meta programming code often generates obscure error messages I prefer code which is simple to read.

A predicate which can be used with std::enable_if is sometimes useful when we want to enable a function to be used only for indlists:

// check if a type is an indlist
template<typename T>struct is_indlist:std::false_type{};
template<std::size_t...i>struct is_indlist<indlist<i...>>:std::true_type{};

I'll also add (unrelated to is_indlist) a predicate for checking if a type is a tuple:

// check if a type is a tuple;
template<typename T>struct is_tuple:std::false_type{};
template<typename...T>struct is_tuple<std::tuple<T...>>:std::true_type{};

For debugging purposes printing an indlist is indispensable:

// print an indlist object
template<std::size_t i,std::size_t...j>
std::ostream&operator<<(std::ostream&os,indlist<i,j...>const&){
  return os<<i<<" "<<indlist<j...>();
}
std::ostream&operator<<(std::ostream&os,indlist<>const&){
  return os;
}

Below are a couple of other useful meta functions:

// get size of an indlist
template<typename IL>struct size;
template<std::size_t...i>
struct size<indlist<i...>>{
  static std::size_t const value=sizeof...(i);
};
// get first element as an indlist
template<typename IL>struct front;
template<std::size_t i,std::size_t...j>
struct front<indlist<i,j...>>{
  using type=indlist<i>;
};
// get last element as an indlist
template<typename IL>
struct back{
  using R=typename reverse<IL>::type;
  using type=typename front<R>::type;
};
// get first N elements as an indlist
template<std::size_t N,typename IL>
struct firstn{
  using type=typename popn_back<size<IL>::value-N,IL>::type;
};
// get last N elements as an indlist
template<std::size_t N,typename IL>
struct lastn{
  using R1=typename reverse<IL>::type;
  using R2=typename firstn<N,R1>::type;
  using type=typename reverse<R2>::type;
};
// get an element as a size_t gven the index
template<std::size_t IND,typename IL>struct get;
template<std::size_t IND,std::size_t i,std::size_t...j>
struct get<IND,indlist<i,j...>>{
  static constexpr std::size_t value=get<IND-1,indlist<j...>>::value;
};
template<std::size_t i,std::size_t...j>
struct get<0,indlist<i,j...>>{
  static constexpr std::size_t value=i;
};
// append an indlist to another indlist
template<typename IL1,typename IL2>struct append;
template<typename IL1,std::size_t i,std::size_t...j>
struct append<IL1,indlist<i,j...>>{
  using type=typename append<typename push_back<i,IL1>::type,indlist<j...>>::type;
};
template<typename IL1>
struct append<IL1,indlist<>>{
  using type=IL1;
};

A few esoteric indlist functions

Just to show how easy it is (and also just because we can) here are a few more – not so useful – meta functions:

// get a slice of an indlist
template<std::size_t IND,std::size_t LEN,typename IL>
struct slice{
  using IL1=typename popn_front<IND,IL>::type;
  using type=typename popn_back<size<IL1>::value-LEN,IL1>::type;
};
// reverse elements starting from I and N elements forward
template<std::size_t IND,std::size_t N,typename IL>
struct reverse_slice{
  using IL_LEFT=typename slice<0,IND,IL>::type;
  using IL_MID=typename slice<IND,N,IL>::type;
  using IL_RIGHT=typename slice<IND+N,size<IL>::value-(IND+N),IL>::type;
  using IL_MID_R=typename reverse<IL_MID>::type;
  using A=typename append<IL_LEFT,IL_MID_R>::type;
  using type=typename append<A,IL_RIGHT>::type;
};
// rotate an indlist left N steps
template<std::size_t N,typename IL>
struct rotate_left{
  using R1=typename slice<0,N,typename reverse_slice<0,N,IL>::type>::type;
  using R2=typename slice<N,size<IL>::value-N,typename reverse_slice<N,size<IL>::value-N,IL>::type>::type;
  using A=typename append<R1,R2>::type;
  using type=typename reverse<A>::type;
};
// add +1 to each index in indlist
template<typename IL>struct add1;
template<std::size_t i,std::size_t...j>
struct add1<indlist<i,j...>>{
  using type=typename push_front<i+1,typename add1<indlist<j...>>::type>::type;
};
template<>
struct add1<indlist<>>{
  using type=indlist<>;
};
// fold list to an int with a binary meta function (taking two ints)
//                  foldl1 f [x]      = x
//                  foldl1 f (x:y:xs) = foldl1 f (f x y : xs)
template<template<std::size_t,std::size_t>class FBIN,typename IL>struct foldl_indlist2int;
template<template<std::size_t,std::size_t>class FBIN,std::size_t i,std::size_t j>
struct foldl_indlist2int<FBIN,indlist<i,j>>{
  constexpr static std::size_t value=FBIN<i,j>::value;
};
template<template<std::size_t,std::size_t>class FBIN,std::size_t i,std::size_t j,std::size_t...k>
struct foldl_indlist2int<FBIN,indlist<i,j,k...>>{
  constexpr static std::size_t value=foldl_indlist2int<FBIN,indlist<FBIN<i,j>::value,k...>>::value;
};

That's it for functions managing indlists. At this point it should be easy to write other customised indlist functions.

Putting indlists to work – the basics

One of the work horses when dealing with tuples is a function which takes a callable object and a tuple as parameters. The function passes the tuple elements to the function as a list of arguments:

// dummy meta function returning 'return type' for 'apply_tuple_with_indlist'
template<typename IL,typename F,typename T>struct apply_tuple_with_indlist_ret;
template<std::size_t...i,typename F,typename T>
struct apply_tuple_with_indlist_ret<indlist<i...>,F,T>{
  using type=typename std::result_of<F(decltype(std::get<i>(std::forward<T>(std::declval<T>())))...)>::type;
};
// pass tuple to a function taking list of arguments (controll which args and the order using indlist)
template<std::size_t...i,typename F,typename T,typename R=typename apply_tuple_with_indlist_ret<indlist<i...>,F,T>::type>
constexpr auto apply_tuple_with_indlist(indlist<i...>const&,F f,T&&tu)->R
{
  return f(std::get<i>(std::forward<T>(tu))...);
}

Notice that the apply_tuple_with_indlist_ret only serves the purpose of evaluating the return type.

A simple application of the function is to create a new tuple from an old one by picking elements from the tuple. Given the function maketuple:

// create a tuple from a list of args (not same as make_tuple - this is a structure)
struct maketuple{
  template<typename...T>
  constexpr std::tuple<T...>operator()(T&&...t){
    return std::tuple<T...>(std::forward<T>(t)...);
  }
};

I can do the following :

// create a tuple with elements in reverse order
auto ttu1=make_tuple(1,2,3,4,5);
using IL2=make_indlist_from_tuple<decltype(ttu1)>::type;
cout<<apply_tuple_with_indlist(reverse<IL2>::type(),maketuple(),ttu1)<<endl;

The output is: [5 4 3 2 1 ]

Another application is to shave off or add elements to a tuple. For instance, say I want to pop the first element of a tuple:

// pop first element of a tuple
auto ttu1=make_tuple(1,2,3,4,5);
using IL2=make_indlist_from_tuple<decltype(ttu1)>::type;
cout<<apply_tuple_with_indlist(pop_front<IL2>::type(),maketuple(),ttu1)<<endl;

The output is: [2 3 4 5 ]

I can simplify the use of apply_tuple_with_indlist by directly passing a meta function as a parameter:

// transformation of a tuple to another tuple
// (template template parameter can be 'reverse', 'pop_front', ... but must transform an indlist)
template<template<class>class FIT,
         typename T,
         typename TD=typename std::decay<T>::type,
         typename IL=typename make_indlist_from_tuple<TD>::type,
         typename IR=typename FIT<IL>::type,
         typename F=maketuple,
         typename R=typename apply_tuple_with_indlist_ret<IR,F,T>::type>
constexpr R transform_tuple(T&&t){
  return apply_tuple_with_indlist(IR(),F(),std::forward<T>(t));
}

Now I can simply write the previous reverse examples as:

// reverse tuple elements
auto ttu1=make_tuple(1,2,3,4,5);
cout<<transform_tuple<reverse>(ttu1)<<endl;

Of course I can also create a genuine utility function for reversing tuples as:

// reverse tuple (utility function)
template<typename T,
         typename TD=typename std::decay<T>::type,
         typename IL=typename make_indlist_from_tuple<TD>::type,
         typename IR=typename reverse<IL>::type,
         typename F=maketuple,
         typename R=typename apply_tuple_with_indlist_ret<IR,F,T>::type>
constexpr R reverse_tuple(T&&t){
  return apply_tuple_with_indlist(IR(),F(),std::forward<T>(t));
}

Continuing along the same lines I'll create utility functions for popping elements off a tuple:

// pop front
template<std::size_t N,typename T,
         typename F=maketuple,
         typename TD=typename std::decay<T>::type,
         typename IL=typename popn_front<N,typename make_indlist_from_tuple<TD>::type>::type,
         typename R=typename apply_tuple_with_indlist_ret<IL,F,T>::type>
constexpr auto popn_front_tuple(T&&t)->R{
  return apply_tuple_with_indlist(IL(),F(),std::forward<T>(t));
}
// pop back
template<std::size_t N,typename T,
         typename F=maketuple,
         typename TD=typename std::decay<T>::type,
         typename IL=typename popn_back<N,typename make_indlist_from_tuple<TD>::type>::type,
         typename R=typename apply_tuple_with_indlist_ret<IL,F,T>::type>
constexpr auto popn_back_tuple(T&&t)->R{
  return apply_tuple_with_indlist(IL(),F(),std::forward<T>(t));
}

An example is shown here:

// pop 2 elements from fron of tuple
auto a1=make_tuple(1,2,3,4);
cout<<"popn_front<2>: "<<popn_front_tuple<2>(a1)<<endl;

The result is: popn_front: [3 4 ]

So far I've exploded a tuple into elements before passing the elements to the function. Sometimes it may be useful to call a function by passing a list of arguments directly but controlling the order in which the arguments are passed to the function. Or, picking the arguments we want to forward to the function. The code looks lie:

// pass list of types to a function (control order of arguments to F with an 'indlist')
template<std::size_t...i,typename F,typename...T,
         typename IL=indlist<i...>,
         typename TU=std::tuple<T...>,
         typename R=typename apply_tuple_with_indlist_ret<IL,F,TU>::type>
constexpr auto apply_with_indlist(IL,F f,T&&...t)->R
{
  // cannot have more than one statement here (won't compile: gcc4.8 ?)
  return apply_tuple_with_indlist(IL(),f,TU{std::forward<T>(t)...});
}

For example:

// test function for tuple
struct PrintNValues{
  template<typename...T>
  void operator()(T&&...t){
    auto tu=make_tuple(std::forward<T>(t)...);
    cout<<tu<<endl;
  }
};
…
// call a function by reversing arguments
using IL8=make_indlist_from_range<0,5>::type;
apply_with_indlist(reverse<IL8>::type(),PrintNValues(),0,1,2,3,4,5);

The output is: [5 4 3 2 1 0 ]

Applying a tuple element- function before calling a function

It's convenient to apply an element specific function to a tuple element before forwarding the transformed element to a function. This is easily done as follows:

// dummy meta function returning 'return type' for 'fapply_tuple_with_indlist'
template<typename IL,typename F,typename FX,typename T>struct fapply_tuple_with_indlist_ret;
template<std::size_t...i,typename F,typename FX,typename T>
struct fapply_tuple_with_indlist_ret<indlist<i...>,F,FX,T>{
  using type=decltype(std::declval<F>()(std::declval<FX>()(std::get<i>(std::forward<T>(std::declval<T>())))...));
};
// pass tuple to a function taking list of FX(arguments) (controll which args and the order using indlist)
template<std::size_t...i,typename F,typename FX,typename T,typename R=typename fapply_tuple_with_indlist_ret<indlist<i...>,F,FX,T>::type>
constexpr auto fapply_tuple_with_indlist(indlist<i...>const&,F f,FX fx,T&&tu)->R
{ 
  return f(fx(std::get<i>(std::forward<T>(tu)))...);
}

I'll use this function when implementing a function which transforms each element in a tuple and returns a new transformed tuple:

// transform a tuple by applying a function to each element
// (may return a tuple having different element types)
template<typename FX,typename T,
         typename ISCALL=typename std::enable_if<is_callable<FX>::value>::type,
         typename TD=typename std::decay<T>::type,
         typename IL=typename make_indlist_from_tuple<TD>::type,
         typename R=typename fapply_tuple_with_indlist_ret<IL,maketuple,FX,T>::type>
auto transform_tuple(FX fx,T&&t)->R{
    return fapply_tuple_with_indlist(IL(),maketuple(),fx,std::forward<T>(t));
}

where is_callable is implemented as:

// check if a type is callable
template<typename T>
struct is_callable {
private:
    typedef char(&yes)[1];
    typedef char(&no)[2];
    struct fallback{void operator()();};
    struct derived:T,fallback{};
    template<typename U,U>struct check;
    template<typename>static yes test(...);
    template<typename C>static no test(check<void(fallback::*)(),&C::operator()>*);
public:
    static const bool value =sizeof(test<derived>(0))==sizeof(yes);
};

Here is an example multiplying each element in the tuple by 2 generating a new tuple:

  // transform each element in a tuple generating a new tuple
  auto z7=make_tuple(1,2,3,4);
  cout<<"mulyiply by 2: "<<transform_tuple([](int val){return val*2;},z7)<<endl;

The output is: mulyiply by 2: [2 4 6 8 ]

Applying a function on each tuple element one at a time

A reoccurring task when programming with tuples is to apply a function to each element of the tuple. This is easily accomplished as:

// pass each element of a tuple to a function (control call order using 'indlist')
template<std::size_t i,std::size_t...j,typename F,typename T>
constexpr void apply_tuple_ntimes_with_indlist(indlist<i,j...>const&,F f,T&&tu)
{
  f(std::get<i>(std::forward<T>(tu)));
  apply_tuple_ntimes_with_indlist(indlist<j...>(),f,std::forward<T>(tu));
};
template<typename F,typename T>
constexpr void apply_tuple_ntimes_with_indlist(indlist<>const&,F f,T&&tu){
}

The following snippet prints the tuple elements in reverse order, one on each line:

// print 1 value
struct Print1Value{
  template<typename T>
  void operator()(T&&t){cout<<t<<endl;}
};
...
// call a function for each element in a tuple in reverse order
auto z6=make_tuple(1,2,"three");
using IL6=make_indlist_from_tuple<decltype(z6)>::type;
apply_tuple_ntimes_with_indlist(reverse<IL6>::type(),Print1Value(),z6);

The output is:
three
2
1

Folding a tuple

Folding a tuple can be done in a neat and elegant way. The code I not so pleasing to the eye but is pretty straight forward. Most likely the code should be refactored into a more readable form. Being too lazy I'll keep this brute force implementation:

// fold a a tuple (binary function)
// (truly horrific syntax)
struct foldl_tuple_helper{
  template<typename F,typename T,typename U,typename...V,
           typename TU=std::tuple<T,U,V...>,
           typename FRONT=decltype(std::declval<F>()(std::get<0>(std::declval<TU>()),std::get<1>(std::declval<TU>()))),
           typename TAIL=decltype(popn_front_tuple<2>(std::declval<TU>()))>
  auto operator()(F f,std::tuple<T,U,V...>const&tu)->decltype((*this)(f,std::tuple_cat(std::tuple<FRONT>(std::declval<FRONT>()),std::declval<TAIL>()))){
    FRONT front=f(std::get<0>(tu),std::get<1>(tu));
    TAIL tail=popn_front_tuple<2>(tu);
    return operator()(f,std::tuple_cat(std::tuple<FRONT>(front),tail));
  }
  template<typename F,typename T>
  constexpr auto operator()(F f,std::tuple<T>const&tu)->T{
    return std::get<0>(tu);
  }
};
template<typename F,typename T>
constexpr auto foldl_tuple(F f,T&&t)->decltype(foldl_tuple_helper()(std::declval<F>(),std::forward<T>(std::declval<T>()))){
  return foldl_tuple_helper()(f,std::forward<T>(t));
}

A simple example is shown here:

  auto c=make_tuple(1,2,3,4,5,6);
  cout<<"six factorial: "<<foldl_tuple(multiplies<int>(),c)<<endl;

The output is: six factorial: 720

Another example concatenating all elemnts into a string can be written as:

// concatenate arguments into a string
struct Concatenate2{
  template<typename T1,typename T2>
  string operator()(T1&&t1,T2&&t2){
    stringstream str;
    str<<t1<<t2;
    return str.str();
  }
};
...
// fold tuple
auto b=make_tuple("one=",1," two=",2," five=",5);
cout<<"fold to strings: "<<foldl_tuple(Concatenate2(),b)<<endl;

Using fold to code tuple inner product

Just for fun, I'll write a function taking the inner product of two (or more) tuples. First I'll code two general functions for multiplying and adding elements:

// binary adder
struct binadd{
  template<typename T1,typename T2>
  constexpr auto operator()(T1&&t1,T2&&t2)->decltype(t1+t2){return t1+t2;}
};
// binary multiplier
struct binmul{
  template<typename T1,typename T2>
  constexpr auto operator()(T1&&t1,T2&&t2)->decltype(t1*t2){return t1*t2;}
};
// general adder
struct adder{
  template<typename...T>
  constexpr auto operator()(T&&...t)->decltype(foldl_tuple(binadd(),maketuple()(std::forward<T>(t)...))){
    return foldl_tuple(binadd(),maketuple()(std::forward<T>(t)...));
  }
};
// general multiplier
struct multiplier{
  template<typename...T>
  constexpr auto operator()(T&&...t)->decltype(foldl_tuple(binmul(),maketuple()(std::forward<T>(t)...))){
    return foldl_tuple(binmul(),maketuple()(t...));
  }
};

Next I'll code a function multiplying elements i of a a list of tuples and then summing the results up. Clearly the multiply and sum does not have to be the usual arithmetic operations. Here is the implementation:

// inner product of tuples 
template<typename ADDER,typename MULTIPLIER>
struct tuple_inner_product_helper{
  template<std::size_t...i,typename...TU>
  constexpr auto operator()(indlist<i...>const&,TU&&...tu)
      ->decltype(foldl_tuple(ADDER(),maketuple()(apply_tuple(MULTIPLIER(),transform_tuples<i>(std::forward<TU>(tu)...))...))){
    return foldl_tuple(ADDER(),maketuple()(apply_tuple(MULTIPLIER(),transform_tuples<i>(std::forward<TU>(tu)...))...));
  }
};
template<typename ADDER=adder,typename MULTIPLIER=multiplier,typename T1,typename...T2,
         typename TD=typename std::decay<T1>::type,
         typename IL=typename make_indlist_from_tuple<TD>::type,
         typename HELPER=tuple_inner_product_helper<ADDER,MULTIPLIER>>
constexpr auto tuple_inner_product(T1&&t1,T2&&...t2)->decltype(HELPER()(IL(),std::forward<T1>(t1),std::forward<T2>(t2)...)){
  return HELPER()(IL(),std::forward<T1>(t1),std::forward<T2>(t2)...);
}

Yes, I know it looks pretty bad but the implementation is really easier to write than to read! However, I'm pretty sure that a simpler implementation can be written s folding. Again I'm too lazy to rewrite it so I'll stick to one above.

Here is a simple example:

  // do a inner product (1^4+2^4+...)
  auto w1=make_tuple(1,2,3,4);
  cout<<tuple_inner_product(w1,w1,w1,w1)<<endl;

Dealing with multiple tuples

So far I've only dealt with a single tuple at a time. I'll start off with a function which takes a list of tuples, picks one element from each tuple and passes them to a function:

// call a function passing one element from each of a set of tuples (control which elemnt using an indlist)
template<std::size_t...i,typename F,typename...T>
constexpr auto apply_elem_tuples(indlist<i...>const&,F f,T&&...t)->decltype(f(std::get<i>(std::forward<T>(t))...))
{
  return f(std::get<i>(std::forward<T>(t))...);
}

The function is useful when building a new tuple from the elements of a set of tuples. Here I'll build a new tuple by picking the second elements from a set of tuples:

// build a tuple by picking the second element from each tuple
auto x1=make_tuple(1,2,3,4,5,6);
auto x2=make_tuple(3,4,5,6,7);
auto x3=make_tuple(10,11);
cout<<apply_elem_tuples(indlist<1,1,1>(),maketuple(),x1,x2,x3);

The output is: [2 4 11 ]

Often we'll want to pick the same element from each tuple. Having a tailored function for this makes the task simpler:

// apply a function on the nth element of a list of tuples
template<std::size_t N,typename F,typename...T,typename IL=typename make_uniform_indlist<sizeof...(T),N>::type>
constexpr auto apply_nth_elem_tuples(F f,T&&...t)->decltype(apply_elem_tuples(IL(),f,std::forward<T>(t)...))
{
  return apply_elem_tuples(IL(),f,std::forward<T>(t)...);
}

The previous example can then be written as:

// build a tuple by taking the first element from a set of tuples
auto x1=make_tuple(1,2,3,4,5,6);
auto x2=make_tuple(3,4,5,6,7);
auto x3=make_tuple(10,11);
cout<<apply_nth_elem_tuples<1>(maketuple(),x1,x2,x3);

The output is again: [2 4 11 ]

Simplifying it even more I can write:

// pick one element in order from a set of tuples creating a new tuple
// (first elemnt is picked from first tuple at index specified by first index in indlist)
template<typename IL,typename...T,
         typename R=decltype(apply_elem_tuples(IL(),maketuple(),std::forward<T>(std::declval<T>())...))>
constexpr R transform_tuples(IL&&il,T&&...t)
{
  return apply_elem_tuples(std::forward<IL>(il),maketuple(),std::forward<T>(t)...);
}

Conclusions

indlists turns out to be critical when controlling tuple elements – the order in which they are passed to functions, which elements to select etc. Once a set of function are available for manipulating indlists manipulation of tuple elements works almost looks like magic.

A curious thing when writing meta functions is that most of the time it's easier to write the code than to read it and understand it afterwards. Maybe this is because the syntax is rather convoluted. As a consequence debugging meta functions is often a non-trivial task.

Writing a large set of meta functions becomes tiresome after a while. Hundreds of compiler errors for even minor bugs and the somewhat cryptically notation becomes exhausting when pounding the keyboard after midnight.

However, ones the decision has been taken to code in C++ there is not really any way out of learning meta programming techniques. It's pointless to code in C++ if only techniques from the 80s and 90s are used. Meta programming is here to stay – it's just a matter to decide if you want to be left behind or stay on the path C++ has taken. A valid question to ask is how much meta programming should be used in day to day work. Should it only be reserved for coding libraries or should it seep into application code?

The use of meta functions is simple enough. Using meta functions is often elegant and makes the tiresome work of coding them looking like a worthwhile endeavour. A question that lingers though is if the ratio between benefits and costs (in terms of frustration, anger and obsession trying to decipher compilation errors) is large enough to justify the type of work described in this blog entry?

Compact C++11 code for Oracle - Part III

Newton was a genius, but not because of the superior computational power of his brain. Newton’s genius was, on the contrary, his ability to simplify, idealize, and streamline the world so that it became, in some measure, tractable to the brains of perfectly ordinary men.

-- G. Weinberg, An Introduction to General Systems Thinking

In this blog entry I'll show a utility which simplifies modifications to data in an Oracle database table. However, before starting I'll quickly show a few changes to the code from the previous entry.

Changes to code from previous blog entries

First, based on a few comments from colleagues I renamed the classes. Specifically I use source as opposed to collection mostly because my previous OcciSelectCollection was not really a collection. I also added a constructor which creates an OCCI environment and a connection in order to simplify quick prototyping. Finally I made the collection (now called occi_source) movable.

Here is a small program using the renamed classes and the new constructor printing data specified by a select statement to standard out:

#include "occi_utils.h"
#include <iostream>
#include <string>
#include <tuple>
using namespace std;

// --- main test program
int main(){
  // auth credentials
  occi_auth const auth{"hans","ewetz","mydb"};

  // sql statement, row and bind types, bind data
  typedef tuple<int,string,string,string>row_t;
  typedef tuple<string>bind_t;
  string sql{"select rownum,dbid,tab,cutoff_dt from MT_DBSYNC_CUTOFF_DT where dbid=:1"};
  bind_t bind{"Policy"};

  // read data specified by select statement
  occi_source<row_t,bind_t>rows{auth,sql,bind};
  for(auto r:rows)cout<<r<<endl;
}

Letting the occi_source manage all OCCI resources is not a realistic choice for most applications. However, when writing code for tests and prototypes, pushing as much OCCI specific code to the occi_source speeds up development significantly.

Modelling database access

The implementation of the occi_input_iterator was based on the boost::iterator_facade. A better alternative would have been to use the boost boost::function_input_iterator. In the next blog I'll revisit the implementation and will most likely change it to use the boost::function_input_iterator.

It's worth noticing that there are other ways to model access to a database. For example, the concept of streams could be used as opposed to the use of source. Yet another way would be to create a thick layer which models a generic database interface.

I'll continue to stick with a thin layer over OCCI which hides the actual database access but lets the user have control over OCCI resources. Specifically I don't want to invent new ways of specifying SQL statements and I definitely don't want my utilities to look inside SQL statements. Anything related to parsing SQL statements I'll gladly pass along to Oracle.

I will continue to stay close to core C++11 features such as tuples and strings instead of building special classes for rows, bind variables, SQL statements etc. For those interested in more generic alternatives, the Database Template Library (DTL) may be of interest.

An iterator for modifying data

Now, let's take a look at how to model modifications to data in an Oracle table. I'll follow along the same lines as before where I used an occi_source for managing OCCI resources (now I'll use an occi_sink) and an iterator for executing SQL statements. However, this time around I'll use the boost function_output_iterator as the base for implementing an output iterator.

The model where I assign bind variables to an iterator worked fine for select statements. It turns out that the model is OK for modification statements also. However, as you'll see later the code executing a modification statement without bind variables looks a little awkward.

OK, let's start with piece of code showing what I would like to be able to do:

#include "occi_tools.h"
#include <string>
#include <algorithm>
#include <tuple>

using namespace std;

// --- test insert
void update(occi_auth const&auth){
  typedef tuple<int,string>bind_t;
  string sql{"insert into names (id,name,isrt_tmstmp) values(:1,:2,sysdate)"};
  occi_sink<bind_t>sink(auth,sql);
  vector<bind_t>b{bind_t{1,"hans"},bind_t{2,"ingvar"}, bind_t{3,"valdemar"}};
  copy(b.begin(),b.end(),sink.begin());
}
// --- main test program
int main(){
 // auth credentials
  occi_auth const auth{"hans","ewetz"",mydb"};
  update(auth);
}

The code snippet inserts 3 rows in the table names by creating a occi_sink, getting an output iterator from the occi_sink and finally copying a vector of tuples corresponding to the bind variables to the iterafunction_input_iterattor. In the sample code I let the sink manage any OCCI resources including the environment and the connection. As will be clear soon I'll define a set of occi_sink constructors which will allow me to manage some of the OCCI resources.

A boost::function_output_iterator requires a function which will be called each time an item is assigned to the iterator. I'll write it as a function which simply delegates back to the iterator:

// forward decl
template<typename Bind>class occi_output_iterator;
  
// function called for each modification
// (function delegates back to iterator to do work)
template<typename Bind>
class occi_unary_output:std::unary_function<Bind const&,void>{
public:
  // ctors
  occi_unary_output(occi_output_iterator<Bind>*it):it_(it){}

  // modification function
  void operator()(Bind const&bind){
    it_->operator()(bind);
  }
private:
  occi_output_iterator<Bind>*it_;
};

The actual iterator is coded as follows:

// wrapper around boost::function_output_iterator
template<typename Bind>
class occi_output_iterator:public boost::function_output_iterator<occi_unary_output<Bind>>{
friend class occi_unary_output<Bind>;
public:
  // typedef for simpler declarations (tuple<int,int,...> with as many elements a Bind)
  using Size=typename uniform_tuple_builder<std::tuple_size<Bind>::value,std::size_t>::type;

  // ctors, assign, dtor
  occi_output_iterator(oracle::occi::Connection*conn,std::string const&sql,std::size_t batchsize=1,Size const&size=Size()):
      boost::function_output_iterator<occi_unary_output<Bind>>(occi_unary_output<Bind>(this)),
      conn_(conn),sql_(sql),batchsize_(batchsize),nwaiting_(0){

    // create statement, set batch modification, create statement and binder
    stmt_=std::shared_ptr<oracle::occi::Statement>{conn_->createStatement(sql_),occi_stmt_deleter(conn_)};
    stmt_->setMaxIterations(batchsize_);

    // set max size of bind variables which have variable length
    if(batchsize==0){
      throw std::runtime_error("invalid batchsize: 0 while constructing occi_output_iterator");
    }else
    if(batchsize>1){
      // set size for variable size bind variables (will throw exception if size==0 for variable size bind variable)
      occi_bind_sizer<Bind>sizer{stmt_};
      apply_with_index_template(sizer,size);
    }
    // create binder object
    binder_=occi_data_binder(stmt_);
  }
  occi_output_iterator(occi_output_iterator const&)=default;
  occi_output_iterator(occi_output_iterator&&)=default;
  occi_output_iterator&operator=(occi_output_iterator&)=default;
  occi_output_iterator&operator=(occi_output_iterator&&)=default;
  ~occi_output_iterator()=default;

  // explicitly execute buffered statements
  void flush(){flushAux();}
private:
  // modification function
  void operator()(Bind const&bind){
    // check if weed to add previous row, bind new row and check if we need to flush (execute)
    ++nwaiting_;
    if(nwaiting_>1)stmt_->addIteration();
    apply_with_index(binder_,bind);
    if(nwaiting_==batchsize_)flushAux();
  }
  // flush remaining statements
  void flushAux(){
    if(nwaiting_>0){
      stmt_->executeUpdate();
      nwaiting_=0;
    }
  }
private:
  oracle::occi::Connection*conn_;
  std::string const&sql_;
  std::shared_ptr<oracle::occi::Statement>stmt_;
  occi_data_binder binder_;
  std::size_t batchsize_;
  std::size_t nwaiting_;
};

The code requires some explanations. OCCI provides a feature that batches requests and sends them to the server in one go. The batchsize_ and nwaiting _ members keeps track of when it's time to flush a batch of statements to the server. A flush method is provided so a user can explicitly flush remaining statements. For example, if the batch size is set to 3 and 4 items have been assigned to the iterator, 1 statement is buffered. Therefore, a user can explicitly call flush forcing the iterator to send any remaining statements to the server.

There is a little more to managing batching of statements. OCCI must know beforehand the maximum size of a statement. To calculate the size OCCI requires the maximum size of any variable length bind variables. For fixed length bind variables OCCI can calculate the size. To pass this information through the iterator to OCCI I use a tuple having the same number of items but each item having the type size_t. A user must then set the maximum length of a variable length bind variable in the tuple. The functionality for informing OCCI about the size of a variable length bind variable is implemented in occi_bind_sizer:

// set maximum size a bind variable can have (used in update/insert/delete statements)
template<typename T>struct occi_bind_sizer_aux;
template<>struct occi_bind_sizer_aux<int>{
  static void setsize(std::size_t ind,std::shared_ptr<oracle::occi::Statement>stmt,size_t size){
    // nothing to do - not a variable size type
  }
};
template<>struct occi_bind_sizer_aux<std::string>{
  static void setsize(std::size_t ind,std::shared_ptr<oracle::occi::Statement>stmt,std::size_t size){
    // don't allow string length to have max size == 0
    if(size==0)throw std::runtime_error("invalid size: 0 for std::string bind variable while setting 'stmt->setMaxParamSize(ind,size)'");
    stmt->setMaxParamSize(ind+1,size);
  }
};
// TODO: add more types to sizer 
// ...
template<typename ... Args>class occi_bind_sizer;
template<typename ... Args>
class occi_bind_sizer<std::tuple<Args ...>>{
public:
  // get bind type
  using Bind=std::tuple<Args ...>;

  occi_bind_sizer(std::shared_ptr<oracle::occi::Statement>stmt):stmt_(stmt){}
  occi_bind_sizer()=default;
  occi_bind_sizer(occi_bind_sizer const&)=default;
  occi_bind_sizer(occi_bind_sizer&&)=default;
  occi_bind_sizer&operator=(occi_bind_sizer&)=default;
  occi_bind_sizer&operator=(occi_bind_sizer&&)=default;
  ~occi_bind_sizer()=default;
  template<std::size_t Ind>
  void apply(size_t size){
    using T=typename std::decay<decltype(std::get<Ind>(Bind()))>::type;
    occi_bind_sizer_aux<T>::setsize(Ind,stmt_,size);
  }
private:
  std::shared_ptr<oracle::occi::Statement>stmt_;
};

That's all there is to the iterator implementation.

An occi_sink

Once the idea of assigning a tuple representing a bind variable to an iterator is clear, the implementation is straight forward and the iterator can be used as is. However, I started to write the code to show that it was possible to write a small C++ library which would be a typesafe alternative to using PERL for DB access. Using the occi_output_iterator directly is simple but not simple enough. I'll make it simple enough by adding a sink which main responsibility is to create iterators and manage OCCI resources.

The implementation of occi_sink is rather long mostly because it's meant to provide a simple to use interface – not because it's complicated. A large part of the code consists of constructors and move support. The occi_sink is movable but not copyable.

Here is the code:

// sink 
template<typename Bind=std::tuple<>>
class occi_sink{
public:
  // typedef for simpler declarations (tuple<int,int,...> with as many elements a Bind)
  using Size=typename uniform_tuple_builder<std::tuple_size<Bind>::value,std::size_t>::type;

  // enum for controlling commit, rollback or do nothing
  enum commit_t:int{Rollback=0,Commit=1,Nop=2};
  // typedefs
  typedef typename occi_output_iterator<Bind>::value_type value_type;
  typedef typename occi_output_iterator<Bind>::pointer pointer;
  typedef typename occi_output_iterator<Bind>::reference reference;
  typedef occi_output_iterator<Bind>iterator;

  // ctor taking authentication (commit default == true since sink manages resources)
  explicit occi_sink(occi_auth const&auth,std::string const&sql,std::size_t batchsize=1,Size const&size=Size(),commit_t commit=Commit):
      conn_(nullptr),connpool_(nullptr),env_(nullptr),auth_(auth),sql(sql),closeConn_(true),
      releaseConn_(false),terminateEnv_(true),batchsize_(batchsize),size_(size),commit_(commit){
    check_batchsize(batchsize_);
    env_=oracle::occi::Environment::createEnvironment(oracle::occi::Environment::DEFAULT);
    conn_=env_->createConnection(std::get<0>(auth_),std::get<1>(auth_),std::get<2>(auth_));
  }
  // ctor taking environment + authentication (commit default == true since sink manages resources)
  explicit occi_sink(oracle::occi::Environment*env,occi_auth const&auth,std::string const&sql,std::size_t batchsize=1,Size const&size=Size(),commit_t commit=Commit):
      conn_(nullptr),connpool_(nullptr),env_(env),auth_(auth),sql(sql),closeConn_(true),
      releaseConn_(false),terminateEnv_(false),batchsize_(batchsize),size_(size),commit_(commit){
    check_batchsize(batchsize_);
    conn_=env_->createConnection(std::get<0>(auth_),std::get<1>(auth_),std::get<2>(auth_));
  }
  // ctor taking an open connection (commit default == false since sink does not manage resources)
  explicit occi_sink(oracle::occi::Connection*conn,std::string const&sql,std::size_t batchsize=1,Size const&size=Size(),commit_t commit=Nop):
      conn_(conn),connpool_(nullptr),env_(nullptr),sql(sql),closeConn_(false),
      releaseConn_(false),terminateEnv_(false),batchsize_(batchsize),size_(size),commit_(commit){
    check_batchsize(batchsize_);
  }
  // ctor taking a stateless connection pool (commit default == false since sink does not manage resources)
  explicit occi_sink(oracle::occi::StatelessConnectionPool*connpool,std::string const&sql,std::size_t batchsize=1,Size const&size=Size(),commit_t commit=Nop):
      conn_(nullptr),connpool_(connpool),env_(nullptr),sql(sql),closeConn_(false),
      releaseConn_(true),terminateEnv_(false),batchsize_(batchsize),size_(size),commit_(commit){
    check_batchsize(batchsize_);
    conn_=connpool_->getConnection();
  }
  // ctors, assign (movable but not copyable)
  occi_sink()=delete;
  occi_sink(occi_sink const&)=delete;
  occi_sink(occi_sink&&s):
      conn_(s.conn_),connpool_(s.connpool_),env_(s.env_),
      closeConn_(s.closeConn_),releaseConn_(s.releaseConn_),terminateEnv_(s.terminateEnv_),
      auth_(s.auth_),sql(s.sql){
    // reset all relevant state
    reset_state(std::forward<occi_sink<Bind>>(s));
  }
  occi_sink&operator=(occi_sink const&)=delete;
  occi_sink&operator=(occi_sink&&s){
    // std::swap with no throw and reset state of parameter
    swap(s);
    reset_state(std::forward<occi_sink<Bind>>(s));
  }
  // dtor - close occi resources if needed
  ~occi_sink(){
    // check if we should commit
    if(commit_==Commit)conn_->commit();else
    if(commit_==Rollback)conn_->rollback();

    // take care of connection
    if(closeConn_)env_->terminateConnection(conn_);else
    if(releaseConn_)connpool_->releaseConnection(conn_);

    // take care of environment
    if(terminateEnv_)oracle::occi::Environment::terminateEnvironment(env_);
  }
  // get begin/end iterators
  iterator begin()const{return iterator(conn_,sql,batchsize_,size_);}

  // swap function
  void swap(occi_sink&s)noexcept(true){
    std::swap(s.conn_,conn_);std::swap(s.connpool_,connpool_);std::swap(s.env_,env_);
    std::swap(s.closeConn_,closeConn_);std::swap(s.releaseConn_,releaseConn_);std::swap(s.terminateEnv_,terminateEnv_);
    std::swap(s.auth_,auth_);std::swap(s.sql,sql);swap(s.batchsize_,batchsize_);swap(s.size_,size_);swap(s.commit_,commit_);
  }
private:
  // check if batchsize is valid
  void check_batchsize(std::size_t batchsize){
    if(batchsize==0)throw std::runtime_error("invalid batchsize: 0 while constructing occi_sink");
  }
  // reset state for a sink (only called with r-value)
  void reset_state(occi_sink&&s){
    s.conn_=nullptr;s.connpool_=nullptr;s.env_=nullptr;
    s.closeConn_=false;s.releaseConn_=false;s.terminateEnv_=false;
    s.auth_=occi_auth{};s.sql="";s.batchsize_=0;s.size_=Size{};s.commit_=false;
  }
  // occi resources
  oracle::occi::Connection*conn_;
  oracle::occi::StatelessConnectionPool*connpool_;
  oracle::occi::Environment*env_;

  // authentication + sql statement
  occi_auth auth_;
  std::string sql;
  std::size_t batchsize_;
  Size size_;

  // controll of what to do with occi resources
  bool closeConn_;
  bool releaseConn_;
  bool terminateEnv_;
  commit_t commit_;
};

A few examples

1 - Deleting without bind variables

Here is an example showing how to execute a delete statement without bind variables :

  string sql{"delete from names"};
  occi_sink<tuple<>>sink(auth,sql);
  *sink.begin()=tuple<>();

I mentioned earlier in this blog item that executing statements without bind variables would look a little awkward. I could probably build in some feature in the occi_sink to execute simple statements like the one here. However, I prefer to see it as a feature that there is a single consistent way of executing modification statements.

2 - Using plain iterator without sink

Here is a (slightly modified) production example using both an occi_source and an occi_output_iterator directly. The function is part of a class holding a connection in a shared_ptr attribute conn_:

// add a package to database
int PackageMetadata::addPackage(string const&name,string const&location,string const&clientid,string const&docformat){
  // get new package odentifier
  using row_t=tuple<int>;
  occi_source<row_t>rows(conn_.get(),"select EXMT_PACKAGE_ID_SEQ.nextval from dual");
  int pkgid{get<0>(*rows.begin())};

  // insert package into db
  using bind_t=tuple<int,string,string,string,string>;
  string sql{"insert into EXMT_PACKAGE (ID,NAME,PKG_LOCATION,CLIENT_ID,DOC_FORMAT,ISRT_TMSTMP,LST_UPD_TMSTMP)VALUES(:1,:2,:3,:4,:5,sysdate,sysdate)"};
  occi_output_iterator<bind_t>it{conn_.get(),sql,1};
  *it=bind_t{pkgid,name,location,clientid,docformat};

  // return package identifier
  return pkgid;
}

3 - Batching statements

Finally here is an example which sets the batch size, inserts some rows and and flushes remaining (buffered) statements:

  typedef tuple<int,string>bind_t;
  typedef tuple<int,int>size_t;
  string sql{"insert into names (id,name,isrt_tmstmp) values(:1,:2,sysdate)"};
  occi_sink<bind_t>sink(auth,sql,2,size_t(0,100));
  vector<bind_t>b{bind_t{1,"hans"},bind_t{2,"ingvar"},bind_t{3,"valdemar"}};
  auto it=sink.begin();
  copy(b.begin(),b.end(),it);
  it.flush();

Notice that when explicitly setting the batch size to a number greater than 1, statements will be buffered and flushed. When buffering statements, OCCI must have information available so it can calculate the maximum size of a single statement. Because of this OCCI must know the maximum size of any variable length bind variables. That information is passed to the occi_sink as a tuple holding size_t types. For non-variable length bind variables the corresponding length is ignored by the occi_output_iterator.

Conclusions

OCCI contains a large number of features. Here I only support a few of them such as batching of statements sent to the Oracle server. It's clear that there is room for supporting more of the OCCI features.

An alternative to adding more features would be to expose the statement type to a user. A user would then be able to retrieve the statement from an occi_output_iterator and call various OCCI methods on the statement. The risk here is of course that it would interfere with the function of the occi_output_iterator. Until there is time to analyse what should be added (and possibly removed) I'll leave the wrappers alone

Even though it took a little while before I had time to punch out the blog entries the code was written in a hurry. I'm sure that there are issues and bugs in the code. I'm also sure that some of the design decisions were not optimal. For example, some constructors take default parameters and I got a feeling that I didn't declare them in the correct order when I last used the code.

Overall I'm pretty happy that by using some of the basic C++11 features such as tuples and variadic parameters it was possible to write a thin, relative non-intrusive, wrapper around OCCI making Oracle access in C++ as simple as Oracle access in PERL.

I'll probably write one more entry about this topic once I've had more time to think about what should and could be done better. A few things I'll modify as soon as time allows is to use boost::function_input_iterator when implementing the occi_input_iterator. I'll also take a look at possibly modify the tuple utilities to use index lists to manage recursions.

I should mention that when showing the code using the occi_sink and the occi_source to a PERL developer the reaction was 'so what's the advantage?. Well … let's start with type safety …