Concurrency & scalability

If you are working on a concurrent application you will have to mind one very important non-functional requirement which is scalability.

If you are writing a multi threaded application where you handle one job per thread, for example a server application that spawns a thread per connection, then at a point when the server is handling a few thousand connections, your OS will be  spending a signification portion of time in context switching rather than precessing the connections. This causes a plateauing of performance after a few thousand concurrent threads.   If you want you application to be scalable and concurrent this article is a good read: C10K problem

If your application is simple, in the sense you have a very little processing on each connection between you requests and responses you can choose between a simple reactor vs proactor

If your application does a lot of processing on each connection and is going to handle thousands of such connections you can go in for for a proactor infrastructure on top of which your connection handling logic goes into a finite state machine like the Boost Meta State machine. For all potential slow activities like disk read etc, you have Boost ASIO for asyncronous read and write from within your state machine as you can not make blocking calls in it. Boost MSM documentation has a lot of info about how a state machine works.

But, if your requirement is not scalability and your thread usage is not going to increase proportional to the number of connections or if you do not intend to handle too many connections, the a reactor/proactor/FSM may not help because this many not hold to much of advantage, but debugging them can be difficult and are not as straight forward as multi threaded programs. 

Exception guarantees as a design time contract

Reading through GOTW challenges 8 and 59  on exception safety, Tom Cargill's article on exception safety and Herb Sutter's exception safe stack solution to this, etc, the conclusion one comes to is that  exceptions in C++ necessitate a level of extra caution not only during programming but also during design.

The following challenge on GOTW demonstrates different hidden control flows you can stumble upon because of exceptions and so the need to watch every implicit function call with a degree of caution. For example a simple assignment would call an operator= implicitly which might throw an exception. Also the order in which state variables are changed matters so as to make sure an exception does not render the object in an unstable state.

But the key thing to note is that basic guarantee, strong guarantee, no throw guarantee are levels of safety one has to decide on for an interface at design time. This is because it is a contractual agreement with the client code just like any other functional requirements.Not only that, exception safety can sometimes result in a compromise on performance guarantees. So, based on the situation it is necessary to decide on which way to go.

In a generic component it becomes more challenging because exception guarantee of the classes depends on exception guarantees of types on which this class is templatized on, which is not available at the time class is written.STL, for example provides basic guarantee in many places because a user code can wrap around this to provide stronger guarantees if needed. It also makes a few assumptions like the destructor of the type we templatise on, should not throw, if its assignment operator and copy constructor doesn't throw then a vector::erase will provide a strong guarantee, etc.

I also realised a question I had for a long time. If you wondered why std::stack and std::queue have a pop() function that doesn't return anything but rather have a front() or top() function to be used later. This is to provide exception safety again. If pop() had returned the popped out object and if the operator= of that object threw an exception then we would have lost that object for ever. 

All boost APIs explicitly mention about their exception guarantees in the documentation.

Generic programming & OOAD

Template and OOAD can help design genericity in different ways. One can not replace the other.

The template way is to provide templatized data structures and templatized algorithms and have iterators that connect the two. Based on the category of iterator that algorithm decides at compile time as to which implementation of the algorithm is most efficient for this data structure and operates on it. It may also decide that a particular algorithm is not best suited for a datastructure.

For example std::sort accepts two random access iterators and sorts everything between them. If passed iterators to a range in a linked list you will get a complier error. The algorithm can also choose the most efficient implementation based on the iterator category. When copying one range to another using std::copy, if you passed a random access iterator, the entire chunk between them is copied with a native memmove or some such function. If passed a less powerful iterator, it iterate and copy the range as expected. It can vary based on the implementation in your STL library, but that's the general idea.

If you look at it, the algorithms are generic, they don't know which data structure they are operating on. On the other hand the each one of the data structures did not have to provide these algorithms as member functions. So, the commonality is lifted out as generic algorithms.

OOAD on the other hand is about using a generic interface in the user code and the implementation detail is pushed to run time. OOAD helps where you expect conformance to an interface. This can not be done with the generic programming techniques above. If you want to ensure a Thread object should have a run function in it, you will have to write a abstract base class with a pure virtual function called run() and based on the kind of thread the implementation detail can vary as late as run time.

As a general rule iterators and algorithms are used when youo have a collection of data to operate on and they can be present in different kids of datastructures. OOAD is a more structural concept which concentrates on how a class hierarchy is designed and what functionality a class must provide, etc. One of the drawbacks of OOAD is that sometimes you may run into a situation where you a derived class is a kind of a base class, but you do not want to provide the functionality that you are enforced to.

My favorite links

How do type_traits work?

If you have used Boost's type_traits header (or what's in C++ standard now) you might have wondered as to how these could have been implemented. If you haven't, type traits are like a jacket to any type that provide meta information about them without actually modifying the type/class itself. I will dig into the type_traits header of Boost to see how its done.

To demonstrate how it's used, lets assume you are writing a generic algorithm that works on a range of iterators. But your assumption it that it is an iterator to a numeric type, because you do a lot of numeric operation on them. So, here is how you write it.

<br /> template <typename Iterator><br /> typename iterator_traits<Iterator>::value_type total(Iterator begin_, Iterator end_)<br /> {<br />         //Check if the type this function is parameterized on is an arithmetic type.<br />         // If not we throw a compiler error.<br />         BOOST_STATIC_ASSERT(( typename is_arithmetic<typename iterator_traits<Iterator>::value_type>::value ));<br /> <br /> ..... rest of the code..... <br /> }<br />

This should throw a compiler error if any non-arithmetic type is passed to total(). Let's look at how is_arithmetic is implemented so as to see how it identifies arithmetic types from others.

Let's go down to: /usr/include/boost/type_traits.cpp. It includes a lot of internal headers from /usr/include/boost/ which have the same name as the trait class they provide.

If you go down to /usr/include/boost/type_traits/is_arithmetic.hpp

You see a lot of arcane pre-processor stuff, but the key thing to observe is:

<br /> ::boost::detail::is_arithmetic_impl<T>::value<br />

You might notice all internal details in Boost goes into an internal namespace.

So, is_arithmetic_impl<T> is another internal type trait class, which is wrapped around by the one we use.

It looks as follows:

<br /> template< typename T ><br /> struct is_arithmetic_impl<br /> {<br />     BOOST_STATIC_CONSTANT(bool, value =<br />         (::boost::type_traits::ice_or<<br />             ::boost::is_integral<T>::value,<br />             ::boost::is_float<T>::value<br />         >::value));<br /> };<br />

This structure again wraps around more type traits is_integral, is_float and does a compile time logical OR of the results. They mean that an arithmetic type should be integral or one of the float types.

Let's explore is_integral.hpp. It provides a traits class that returns a type true when parametrized on  intergal types and false for any other type. Basically, it tells whether a type is integral or not.

Again if you skim through all the pre-processor magic to come down to what they are implementing you see a set of declarations:

<br /> BOOST_TT_AUX_BOOL_TRAIT_DEF1(is_integral,T,false)<br />

followed by:

<br /> BOOST_TT_AUX_BOOL_TRAIT_CV_SPEC1(is_integral,unsigned char,true)<br /> BOOST_TT_AUX_BOOL_TRAIT_CV_SPEC1(is_integral,unsigned short,true)<br /> BOOST_TT_AUX_BOOL_TRAIT_CV_SPEC1(is_integral,unsigned int,true)<br /> BOOST_TT_AUX_BOOL_TRAIT_CV_SPEC1(is_integral,unsigned long,true)<br />

and many more other integral types.

If you look for what BOOST_TT_AUX_BOOL_TRAIT_CV_SPEC1 macro expands to in boost/type_traits/detail/bool_trait_def.hpp, it looks as follows:


<br /> #define BOOST_TT_AUX_BOOL_TRAIT_DEF1(trait,T,C) \<br /> template< typename T > struct trait \<br />     BOOST_TT_AUX_BOOL_C_BASE(C) \<br /> { \<br />     BOOST_TT_AUX_BOOL_TRAIT_VALUE_DECL(C) \<br />     BOOST_MPL_AUX_LAMBDA_SUPPORT(1,trait,(T)) \<br /> }; \<br />



To explain this in simple terms, all what's being done here is explicit template specialization


You can think of is_integral to be implemented as follows in simple terms:

<br /> template <typename T><br /> struct is_integral<br /> {<br />         enum{value=false};<br /> };<br /> <br /> template <><br /> struct is_integral<int><br /> {<br />         enum {value=true};<br /> };<br /> <br /> template <><br /> struct is_integral<long><br /> {<br />         enum {value = true};<br /> };<br />

.... and so on for each integral type. So, the value is going to be true for each type they specialize on, but false for all other types..

Why std::distance and std::advance?

Why use STL advance and distance given in <iterator> rather than hand crafting that code? The simple answers are:

• Why hand craft it when its already given to you?
• It can be more bug free than an average programmer's code.
• Why get into the nitty-gritties? You may rather want to concentrate on the problem at hand.

If all these aren't reason enough for you, here is the clincher: EFFICIENCY!

Let's look at each of them one by one.

std::distance()

Let's assume you are writing a generic function that takes in two iterators as the parameter and works on the range between them. If you are a beginner, your function would look something like this:

template <typename Iterator> foo(Iterator begin_, Iteraror end_)
{
      size_t dist = 0;

      while(begin_ !=   end_)
      {
            ++dist;
            ++begin_;
      }

      //Use dist in the rest of the code
      ...............
}

The time complexity of such an operation is O(n) for all categories of iterators passed to you.

If you are an advanced programmer and want to make a decision based on the iterator category, you will have to write helper functions overloaded on the different iterator categories and do a random access subtraction between the two iterators if it is a random access iterator. If not, you will iterate linearly through the range until the end. Something like...

template <typename Iterator>
typename iterator_traits<Iterator>::difference_type __mydistance(Iterator begin_, Iterator end_, random_access_iterator_tag)
{
        return end_ - begin_;
}

template <typename Iterator>
typename iterator_traits<Iterator>::difference_type __mydistance(Iterator begin_, Iterator end_, bidirectional_iterator_tag)
{
        typename iterator_traits<Iterator>::difference_type dist = 0;
        while(begin_ != end_)
        {
                ++begin_;
                ++dist;
        }

        return dist;
}


template <typename Iterator>
typename iterator_traits<Iterator>::difference_type mydistance(Iterator begin_, Iterator end_)
{

        return  __mydistance(begin_, end_, iterator_traits<Iterator>::iterator_category);

}


If your code looks something like the above, this is what std::distance gives you already.

If you go down to where the function is defined:
/usr/include/c++/4.4.2/bits/stl_iterator_base_funcs.h

It looks as follows:


template<typename _InputIterator>
    inline typename iterator_traits<_InputIterator>::difference_type
    distance(_InputIterator __first, _InputIterator __last)
    {
      // concept requirements -- taken care of in __distance
      return std::__distance(__first, __last,
                             std::__iterator_category(__first));
    }
If you observe, it calls std::__distance, a function for internal use, and passes the iterator category as the last parameter. This is called tagged dispatch. If you scroll around that file, you will notice multiple overloaded  __distance functions for different iterator categories.


The __distance function accepting random_access_iterator_tag is implemented as:
return __last - __first;

The __distance function accepting input_iterator_tag is implemented as:
      while (__first != __last)
        {
          ++__first;
          ++__n;
        }
      return __n;

How does boost::bind work?

If you are not already familiar with Boost::bind you may want to explore: http://www.boost.org/doc/libs/1_44_0/libs/bind/bind.html

To understand how bind works, I would write a simple example binder first and then start digging into boost::bind.

struct placeholder{};
placeholder _1;

template
struct mybinder_t
{
A ma;
T* mt;
R (T::*fn) (A);
R operator() ( )
{
return (mt->*fn)(ma);
}
};

template
mybinder_t mybind(R (T::*f)(A), T* t, A a, placeholder p)
{
mybinder_t tmp;
tmp.fn = f;
tmp.ma = a;
tmp.mt = t;

return tmp;
}


class IsItEvenObj
{
public:
bool is_even(int i)
{
return (i%2 == 0);
}
};

int main()
{
IsItEvenObj obj;
  mybinder_t<bool, IsItEvenObj, int> is_5_even = mybind(&IsItEvenObj::is_even, &obj, 5, _1);

cout << boolalpha ; cout << is_5_even() << endl; } 

When you used bind the first time,  you might have wondered what _1, _2 etc meant. These are placeholder variables of type boost::arg. So, you can declare variables with different names if you want. Boost bind uses placeholders as declare in /usr/include/boost/bind/placeholders.hpp. 


They are declared as follows: 

boost::arg<1> _1;
boost::arg<2> _2; 
boost::arg<3> _3;
boost::arg<4> _4;
boost::arg<5> _5;
boost::arg<6> _6;
boost::arg<7> _7;
boost::arg<8> _8;
boost::arg<9> _9;
There are 9 placeholders because bind supports upto 9 parameters to be bound. But what do these placeholders do? Let's dig into what boost::arg does. 

It is defined in /usr/include/boost/bind/arg.hpp It looks like: 

template< int I > struct arg
{     
arg()     {     }     
template< class T > arg( T const & /* t */ )     
 {
        // static assert I == is_placeholder<T>::value         
        typedef char T_must_be_placeholder[ I == is_placeholder<T>::value? 1: -1 ];
  } 
}; 


To be honest there is nothing much in there. And that is the fact, placeholders are only dummy variables. They are only there to help bind pick up the right overload. (I will explain what this means below) Having actually told what placeholders are, let's look into bind itself.

Let's go into /usr/include/boost/bind/bind.hpp. 

The first thing to note is:

// bind
#ifndef BOOST_BIND
#define BOOST_BIND bind
#endif 

So, bind is BOOST_BIND in here. Now let's look at the bind function itself. This is how boost::bind actually looks:

template<class R, class F>
    _bi::bind_t<R, F, _bi::list0>
    BOOST_BIND(F f)
{
    typedef _bi::list0 list_type;
    return _bi::bind_t<R, F, list_type> (f, list_type());
}

template<class R, class F, class A1>
    _bi::bind_t<R, F, typename _bi::list_av_1<A1>::type>
    BOOST_BIND(F f, A1 a1)
{
    typedef typename _bi::list_av_1<A1>::type list_type;
    return _bi::bind_t<R, F, list_type> (f, list_type(a1));
}

template<class R, class F, class A1, class A2>
    _bi::bind_t<R, F, typename _bi::list_av_2<A1, A2>::type>
    BOOST_BIND(F f, A1 a1, A2 a2)
{
    typedef typename _bi::list_av_2<A1, A2>::type list_type;
    return _bi::bind_t<R, F, list_type> (f, list_type(a1, a2));
}

So on upto 9 overloads:

template<class R, class F, class A1, class A2, class A3, class A4, class A5, class A6, class A7, class A8, class A9>
    _bi::bind_t<R, F, typename _bi::list_av_9<A1, A2, A3, A4, A5, A6, A7, A8, A9>::type>
    BOOST_BIND(F f, A1 a1, A2 a2, A3 a3, A4 a4, A5 a5, A6 a6, A7 a7, A8 a8, A9 a9)
{
    typedef typename _bi::list_av_9<A1, A2, A3, A4, A5, A6, A7, A8, A9>::type list_type;
    return _bi::bind_t<R, F, list_type>(f, list_type(a1, a2, a3, a4, a5, a6, a7, a8, a9));
}