Showing posts with label CPP. Show all posts
Showing posts with label CPP. Show all posts

Wednesday, February 05, 2014

Implement Data Parallelism on a GPU Directly in C++

Download: https://github.com/dimitrs/cpp-opencl

The cpp-opencl project provides a way to make programming GPUs easy for the developer. It allows you to implement data parallelism on a GPU directly in C++ instead of using OpenCL. See the example below. The code in the parallel_for_each lambda function is executed on the GPU, and all the rest is executed on the CPU. More specifically, the “square” function is executed both on the CPU (via a call to std::transform) and the GPU (via a call to compute::parallel_for_each). Conceptually, compute::parallel_for_each is similar to std::transform except that one executes code on the GPU and the other on the CPU.

#include <vector>
#include <stdio.h>
#include "ParallelForEach.h"

template<class T> 
T square(T x)  
{
    return x * x;
}

void func() {
  std::vector<int> In {1,2,3,4,5,6};
  std::vector<int> OutGpu(6);
  std::vector<int> OutCpu(6);

  compute::parallel_for_each(In.begin(), In.end(), OutGpu.begin(), [](int x){
      return square(x);
  });

  
  std::transform(In.begin(), In.end(), OutCpu.begin(), [](int x) {
    return square(x);
  });

  // 
  // Do something with OutCpu and OutGpu …..........

  //

}

int main() {
  func();
  return 0;
}


Function Overloading 

Additionally, it is possible to overload functions. The “A::GetIt” member function below is overloaded. The function marked as “gpu” will be executed on the GPU and other on the CPU.

struct A {
  int GetIt() const __attribute__((amp_restrict("cpu"))) {
    return 2;
  }
  int GetIt() const __attribute__((amp_restrict("gpu"))) {
    return 4;
  }
};

compute::parallel_for_each(In.begin(), In.end(), OutGpu.begin(), [](int x){
    A a; 
    return a.GetIt(); // returns 4
});



Build the Executable 

The tool uses a special compiler based on Clang/LLVM. 

cpp_opencl -x c++ -std=c++11 -O3 -o Input.cc.o -c Input.cc 

The above command generates four files: 
1. Input.cc.o 
2. Input.cc.cl 
3. Input.cc_cpu.cpp 
4. Input.cc_gpu.cpp 

Use the Clang C++ compiler directly to link: 

clang++ ./Input.cc.o -o test -lOpenCL 


Then just execute: 

./test

Friday, December 27, 2013

Writing OpenCL Kernels in C++

Download: https://github.com/dimitrs/cpp-opencl/tree/first_blog_post

In this post I would like to present my C++ to OpenCL C source transformation tool. Source code written in the OpenCL C language can now be written in C++ instead (even C++11). It is even possible to execute some of the C++ standard libraries on the GPU.

The tool compiles the C++ source into LLVM byte-code, and uses a modified version of the LLVM 'C' back-end to disassemble the byte-code into OpenCL 'C'. You can see how it is used by looking at the tests provided in the project.

This code using std::find_if and a lambda function is executed on the GPU.

#include <algorithm>

extern "C" void _Kernel_find_if(int* arg, int len, int* out) {
    int* it = std::find_if (arg, arg+len, [] (int i) { return ((i%2)==1); } );
    out[0] = *it;
}

This code using C++11's std::enable_if is executed on the GPU.

#include <type_traits>

template<class T>
T foo(T t, typename std::enable_if<std::is_integral<T>::value >::type* = 0)
{
    return 1;
}

template<class T>
T foo(T t, typename std::enable_if<std::is_floating_point<T>::value >::type* = 0)
{
    return 0;
}

extern "C" void _Kernel_enable_if_int_argument(int* arg0, int* out)
{
    out[0] = foo(arg0[0]);
}

Please not that this project is experimental. It would require a lot more work to make it a production quality tool. One limitation of the tool is that containers such as std::vector are not supported (without a stack-based allocator) because OpenCL does not support dynamically or statically allocated memory. The tool does not support atomics which disallows the use of std::string. It does not have support for memcpy and memset which means that some standard algorithms can not be used; std::copy's underlying implementation sometimes uses memcpy.

Thursday, December 26, 2013

C++ Generic Programming: Implementing Runga-kutta

Download: https://github.com/dimitrs/odes

Below, listing 1. is an implementation of a generic algorithm – the Runga-kutta method which is well known for its use in the approximation of solutions of ordinary differential equations. Although the Runga-kutta method is well known and relatively simple, the generic algorithm implementation below is difficult to read. I won't attempt to explain how it works; I wrote it several months ago and I don't remember all the details. The reason why I list it here is to be able to compare it with a non-generic implementation of the algorithm I wrote in listing 2. 

Listing 2. is far easier to read and understand. It is almost a carbon copy of the mathematical equations for the Runga-kutta4 method (see listing 3). The non-generic implementation is easy to read (assuming you are familiar with the equations) and it was very easy to write. I was done in about 30 minutes, whereas the generic version took me a couple of days to complete. So why make the effort ? The generic version allows you to use any container that supports forward iterators e.g. std::array, std::vector, C array, boost::ublas vectors, Blitz++. With the non-generic version you are tied into using only boost::ublas vectors. 

As far as performance is concerned, the generic version using boost::ublas vectors is about 20% slower than Ublass non-generic version. However, if I substitute the container for a std::array, the generic-algorithm is 40% faster. 

Runga-kutta4 Performance of the generic-algorithm using different containers compared to the non-generic version: 

std::vector: 25% faster
Blitz: about the same
ublas:       20% slower
std::array: 40% faster

template <class InputIterator, class ForwardIterator, class T, class Time=double>
std::pair<std::vector<Time>, ForwardIterator> __runge_kutta4(
    InputIterator inBegin, InputIterator inEnd, 
    Time x0, Time x1, int nr_steps, T f, ForwardIterator yout)
{
  typedef typename std::iterator_traits<InputIterator>::value_type 
      value_type;
  auto delta_t = static_cast<Time>((x1-x0)/nr_steps);
  auto nr_equations = std::distance(inBegin, inEnd);
  ForwardIterator youtP = yout;
  yout = std::copy(inBegin, inEnd, yout);
  std::vector<Time> ytime(nr_steps);

  for (auto ii=0; ii< nr_steps; ++ii) {
    typedef typename std::vector<value_type> vec;

    // K1 = f(x, u(x))
    vec v1(nr_equations);
    typename vec::iterator k1 = f(yout-nr_equations, x0, begin(v1));

    // K2 = f(x+deltaX/2, u(x)+K1*deltaX/2)
    vec v2(nr_equations);
    vec y2(nr_equations);
    std::transform(yout-nr_equations, yout, k1, begin(y2), 
      [delta_t](value_type& y,value_type& k) {
          return y+0.5*delta_t*k;
      });
    typename vec::iterator k2 = 
        f(begin(y2), 0.5*delta_t+x0, begin(v2));

    // K3 = f(x+deltaX/2, u(x)+K2*deltaX/2)
    vec v3(nr_equations);
    vec y3(nr_equations);
    std::transform(yout-nr_equations, yout, k2, begin(y3), 
      [delta_t](value_type& y,value_type& k){
          return y+0.5*delta_t*k;
      });
    typename vec::iterator k3 = 
        f(begin(y3), 0.5*delta_t+x0, begin(v3));

    // K4 = f(x+deltaX, u(x)+K2*deltaX)
    vec v4(nr_equations);
    vec y4(nr_equations);
    std::transform(yout-nr_equations, yout, k3, begin(y4), 
      [delta_t](value_type& y, value_type& k){ return y+delta_t*k; });
    typename vec::const_iterator k4 
        = f(begin(y4), delta_t+x0, begin(v4));

    // u(x+deltaX) = u(x) + (1/6) (K1 + 2 K2 + 2 K3 + K4) * deltaX
    for (auto i=0; i<nr_equations; ++i,++yout) {
      *yout = *(yout-nr_equations) + 
        (1.0/6.0) * (k1[i] + 2.0*k2[i] + 2.0*k3[i] + k4[i]) * delta_t;
    }
    ytime[ii] = x0;
    x0 += delta_t;
  }

  return std::make_pair(ytime, yout);
}

Listing 1: Generic Implementation of Runga-kutta4

template <class T, class Vector=boost::numeric::ublas::vector<double> >
Vector rk4(const Vector& init, double x0, double x1, int nr_steps, T f)
{
 Vector y = init;
 auto h = static_cast<double>((x1-x0)/nr_steps);
 double xn = x0;

 for (auto ii=0; ii< nr_steps; ++ii) {
   Vector k1 = f(y, xn);
   Vector k2 = f(y+0.5*h*k1, 0.5*h+xn);
   Vector k3 = f(y+0.5*h*k2, 0.5*h+xn);
   Vector k4 = f(y+h*k3, h+xn);

   xn += h;
   y = u + (1.0/6.0) * (k1 + 2.0*k2 + 2.0*k3 + k4) * h;
 }
 return y;
}

Listing 2: Non-Generic Implementation of Runga-kutta4 (using ublas)

for n = 0,1,2,3,..., using
 k1 = h f(xn, yn)
 k2 = h f(xn + h/2, yn + k1/2)
 k3 = h f(xn + h/2, yn + k2/2)
 k4 = h f(xn + h, yn + k3)

 xn+1 = xn + h
 yn+1 = yn + h(1/6)(k1 + 2k2 + 2k3 + k4)

Listing 3: Runga-kutta4 equations. 

Saturday, June 15, 2013

Memory Ordering and Atomics in C++11

I recommend watching these two videos: atomic<> Weapons and Threads & Shared Variables. Below, you can read my summary notes from these sources and others.


Compiler optimization, processor out of order execution and cache coherency could cause the sequence of operations that a processor executes to be changed from the order specified by the source code.

For example, below you can see an optimization a compiler might apply,
From this:                        To this:
for (p=q; q!=0; p=p->next)        r1 = count;
  if (p->data > 0) ++count;       for (p=q; q!=0; p=p->next)
                                      if (p->data > 0) ++r1;
                                  count = r1;

In the above example, the compiler loads the global variable 'count' into a register before the loop and then writes the register to the global variable after the loop. This transformation is not safe with more than one thread because a data-race is introduced. Assuming one thread loops through data that is always '0' and the other thread has some positive data values, the final count value could be overwritten by the thread with '0' in r1.

Race condition: A memory location (variable) can be simultaneously accessed by two threads, and at least one thread is a writer.

In the example below, assume x and y are global variables and initially set to '0'. One possible inter- leaved execution could be x=1, y=1, r1=y, r2=x, with r1 and r2 set to '1'. A different inter-leaved execution could result in either one of the r values set to '1' and the other set to '0'. That would be a sequentially consistent execution. However, in reality both r1 and r2 could read '0' -- the initial values. This is because the result of the store instruction in hardware is not made immediately visible to other processors. This is not the behaviour a programmer would expect i.e. it is not sequentially consistent. The result is that we can not predetermine what operations are actually executed and the order in which they are executed by any particular thread.

Thread 1                Thread 2
x = 1;                  y = 1;
r1 = y;                 r2 = x;

Sequential consistency (SC): Executing the program you wrote. Defined as “the result of any execution is the same as if the reads and writes occurred in some order, and the operations of each individual processor appear in this sequence in the order specified by its program ”

The goal is a correctly synchronized program (no race conditions) with the help of atomics and mutexes and that behaves as if:
  • memory operations are actually executed in an order that appears equivalent to some sequentially consistent inter-leaved execution of the memory operations of each thread in your source code;
  • including that each write appears to be atomic and globally visible simultaneously to all processors.
By correctly synchronizing your program (no race conditions), “the system” will provide the
illusion of executing the program you wrote. 

Mutex & Atomics:

Locks (mut_x is a mutex protecting x):
{ lock_guard<mutex> hold(mut_x); // enter critical region (lock “acquire”)
   ... read/write x ...
   x = 42;
} // exit critical region (lock “release”)

Ordered atomics (whose_turn is a std::atomic<> variable protecting x):
while( whose_turn != me ) { } // enter critical region (atomic read “acquires” value)
  ... read/write x ...
  x = 42;
whose_turn = someone_else; // exit critical region (atomic write “release”)

Note:
read atomic variable <=> enter critical section (acquire )
write atomic variable <=> exit critical section (release)

Declaring a variable as atomic, in addition to ensuring that the variable is accessed indivisibly, prevents both the compiler and the hardware from reordering memory accesses in ways that are visible to the program. As far as optimizing is concerned, the compiler can not move code out of a Critical section but can move code into a Critical section. Atomics provide one-way barriers: An “acquire barrier” and a “release barrier.” A release store makes its prior accesses visible to a thread performing an acquire load that sees (pairs with) that store.

This explains why the following example is not a data-race. Although x and done are unrelated variables, the memory model specifies that the assert cannot fail. The store to 'x' happens-before the store to done in thread 1. Also, the load of 'done' in thread 2 synchronizes with the store of 'done' in thread 1. Therefore, load of 'x' in thread 2 gets the results of the store that happened in thread 1. It must all see all operations that happened before the store in thread 1, even unrelated ones. That means the optimizer is not free to reorder the two stores in thread 1 since thread 2 must see the store to done as well. There cannot be an interleaving of the steps in which the actions x = 42 and r = x are adjacent -- a sequentially consistent execution.

int x; // initially zero
atomic<bool> done;// initially false

Thread 1                            Thread 2
x = 42;                               while (!done) {}
done = true;                        r = x; // assert(x==42)

Transitivity/causality: x and y are std::atomic, all variables initially zero. It is impossible for the assertion to fail in a sequentially consistent program.

Thread 1                            Thread 2                      Thread 3
g = 1;                                 if( x == 1 )                   if( y == 1 )
x = 1;                                    y = 1;                         assert( g == 1 );

Below, is a single-producer/single-consumer queue. The use of a dummy node for an empty queue is a technique that is commonly used. The idea is to only use the tail pointer in the producer thread except to check if the queue is empty in the consumer thread, which also synchronizes the threads. And only use the head pointer in the consumer thread.

Globally, the tail pointer is always pointing to the dummy node. The store to tail in the push thread, makes the stores to memory locations 3 and 4 (data & next) globally visible to the loads of the same memory locations 1 and 2. Since the tail store in push and tail load in pop are synchronized, 3 and 4 happens-before 1 and 2.
class spsc_queue
{
private:
  struct node
  {
      node* next_;
      int value_;
    node() : next_(0), value_(0) {}
    node(node* next, T value) : next_(next), value_(value) {}
  };

  std::atomic<node*> tail_; // tail of the queue
  std::atomic<node*> head_; // head of the queue

public:
  spsc_queue() : head_(new node), tail_(head_.load())  {}  <-- create dummy node

  bool pop(int& v) 
  { 
    if(head_.load() == tail.load()) {     <---------------- acquire load of tail
      return false;  // queue is empty
    } 
    node* const old_head = head_;   
    head_ = old_head->next_;   // 1
    v = old_head->data_;       // 2
    delete old_head; 
    return true; 
  } 

  void push(int new_value) 
  { 
    node* p = new node; 
    tail_->data_ = new_data;   // 3
    tail_->next_= new node;    // 4
    tail_.store(p);   <---------------- release store to tail
  } 

Atomics support various memory_order specifications. In the above examples, the default specification is used i.e. memory_order_seq_cst. Since it is essentially a thread-to-thread communication using a shared flag (tail_), memory_order_acquire (used for accesses) and memory_order_release (used for updates) could have been used to provide the required visibility guarantees. This allows for a relaxing of the synchronization required between independent reads of independent writes.

Assuming 'x' and 'y' are initially 0:
Thread 1 y.store (20, memory_order_release);
Thread 2 x.store (10, memory_order_release);
Thread 3 assert(y.load(memory_order_acquire)==20 && x.load(memory_order_acquire)==0)
Thread 4 assert(y.load(memory_order_acquire)==0 && x.load(memory_order_acquire)==10)

Both of these asserts can pass since there is no ordering imposed between the stores in thead 1 and thread 2. If this example were written using the sequentially consistent model i.e. the default (memory_order_seq_cst), then one of the stores must happen-before the other (although the order isn't determined until run-time), the values are synchronized between threads, and if one assert passes, the other assert must therefore fail.

Some other atomic operations:

T atomic<T>::exchange( T desired ) { 
    T oldval = this->value; this->value = desired; return oldval; }

bool atomic<T>::compare_exchange_strong( T& expected, T desired ) {
    if( this->value == expected ) { this->value = desired; return true; }
    expected = this->value; return false;
}
Pronounced: “Am I the one who gets to change val from expected to desired?”

_weak vs. _strong compare exchange:
  • _weak allows spurious failures.
  • Prefer _weak when you’re going to write a CAS loop anyway.
  • Almost always want _strong when doing a single test.   
The following boost code is a multi-producer, single consumer queue:
template<typename T>
class waitfree_queue {
public:
  struct node {
    T data;
    node* next;
  };
  void push(const T &data)
  {
    node* n = new node;
    n->data = data;
    node* stale_head = head_.load(std::memory_order_relaxed);
    do {
      n->next = stale_head;
    } while (
        !head_.compare_exchange_weak(
                stale_head, n, std::memory_order_release));
  }

  // pop in reverse order
  node* pop_all(void)
  {
    return head_.exchange(0, std::memory_order_aquire);
  }

  waitfree_queue() : head_(0) {}

private:
  std::atomic<node *> head_;
};
Assuming that for a particular thread, the 'stale_head' is no longer equal to 'head' by the time compare_exchange_weak is called, then its 'stale_head' will be updated to the current 'head' and it will continue looping in the while loop until 'n' can be made the new head in the compare_exchange_weak atomic call. Note the use of memory_order_aquire and memory_order_release.

Tuesday, May 14, 2013

Sorting Large Objects


As far as I know, the standard sort, is partially implemented with a merge-sort algorithm which has a O(n log(n)) worst case running time. Quick-sort is also inexpensive with an average running time of O(n log(n)). There is an important detail to remember when sorting large objects: 'std::swap' is called allot for both merge-sort and quick-sort. Below, is a possible implementation of quick-sort. Note the use of "std::swap" in the partition function.

template <class ForwardIterator, typename _Compare>
void __quick_sort(ForwardIterator first, ForwardIterator last, _Compare __comp)
{
    if (std::distance(first, last) <= 1) return;

    ForwardIterator mid = __partition(first, last, __comp);
    ForwardIterator first1 = first;
    ForwardIterator last1 = mid;
    ForwardIterator first2 = mid;
    ForwardIterator last2 = last;
    std::advance(first2, 1);    

    __quick_sort(first1, last1, __comp);
    __quick_sort(first2, last2, __comp);
}

template <class ForwardIterator, typename _Compare>
ForwardIterator __partition(
       ForwardIterator first, ForwardIterator last, _Compare __comp)
{
    ForwardIterator pivot = first;  // randomly choose pivot
    auto idx = rand() % std::distance(first, last);
    std::advance(pivot, idx);
    std::swap(*pivot, *first);
    pivot = first;
    
    ForwardIterator i = first;
    ForwardIterator j = first;
    std::advance(i, 1);
    std::advance(j, 1);
    ForwardIterator i_prev=i;
    for ( ;j!=last; ++j) {
        if (__comp(*j, *pivot)) {
            i_prev = i;
            std::swap(*j, *i);
            std::advance(i, 1);
        }
    }
    std::swap(*pivot, *i_prev);
    return i_prev;
}

Each call to 'std::swap' can potentially mean three copies. This can make sorting large objects stored by value an expensive task. See the std::swap function below.

template <typename T>
void swap( T& x, T& y )
{
    T tmp( std::move(x) ); // a hint to use move constructor
    x = std::move(y);
    y = std::move(tmp);
}

The compiler will use the move constructor (or move assignment) if possible and default to the copy constructor otherwise. For example, if class T does not have a move constructor the copy constructor is used. According to my measurements, copying large objects log n times adds at least 2 orders of overhead to the sorting algorithm. I compared sorting large objects by value against sorting large objects by pointer. Swapping pointers is done in constant time. No move or copy constructors are called. When you do not want to deal with raw pointers, you can use std::unique_ptr which provides similar results to ordinary pointers (std::swap is overloaded for unique_ptr).

        by ptr       :         2155  us  
        by unique_ptr:         2732  us  
        by value     :       791678  us     

Below, you can see the "large object" and the test. The large object is implemented in terms of an array which does not have a move constructor and therefore is copied when std::swap is called.

struct LargeArrayObject {
    LargeArrayObject(int id) : id(id) {}
    int id;
    std::array<int,10000> array;
};

std::vector<LargeArrayObject> byval;
std::vector<LargeArrayObject*> byptr;
std::vector<unique_ptr<LargeArrayObject>> byuniqptr;

for (int i = 0; i < 10000; ++i) {
   int id = rand() % 100000;
   byval.push_back(LargeArrayObject(id));
   byptr.push_back(new LargeArrayObject(id));
   byuniqptr.push_back(unique_ptr<T>(new LargeArrayObject(id)));
}

auto start = std::chrono::high_resolution_clock::now();
quick_sort(byval.begin(), byval.end(), [](const T& a, const T& b) {
   return a.id<b.id; });
//quick_sort(byptr.begin(), byptr.end(), [](const T* a, const T* b) {
//   return a->id<b->id;});
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = end - start;

An alternative to using pointers for speeding-up swap operations is to implement the large object class in terms of dynamic memory allocation, effectively making it a small object. One could use a std::vector instead of the std::array:

struct LargeVectorObject {
    LargeVectorObject(int id) : id(id), array(10000, 0) {}
    int id;

    // Swap exchanges the elements between two vectors in constant time.
    std::vector<int> array;
};

Below, you can see the measurements I made using LargeVectorObject instead of LargeArrayObject:


        by ptr       :                2155  us  
        by unique_ptr:                2732  us  
        by value     :                1500  us     

Wednesday, February 22, 2012

Encode and Decode Video from Memory

Download: https://github.com/dimitrs/video_coding

OpenCV provides a very simple api to connect to a camera and show the images in a window. It is also very simple to encode those images and store them on disk. However, the simple api provides no means by which to encode an image without storing it on disk and even worse, no means to decode an image stored in memory instead of on disk. Assuming I want to capture an image from a camera and send it over a socket to a receiver, one might want to first compress the image before sending it. A simple test I did indicated that an image can be compressed by a factor of 10 using the mpeg-4 codec. This is really important for streaming applications.

On Linux and Windows, OpenCV’s underlying implementation uses the ffmpeg library to encode/decode frames to and from disk. I found the implementation in opencv\modules\highgui\src\cap_ffmpeg_impl.hpp. In this post, I provide a small test project with a modified version of cap_ffmpeg_impl.hpp. This version allows you to encode/decode images to and from a buffer instead of disk. Warning: The code is a proof of concept and not production ready. You can find the project in github.

Below, you can see how to encode/decode video:

Initializing capture from a camera:

CvCapture* capture = cvCaptureFromCAM(CV_CAP_ANY);

Capturing a frame:

cvGrabFrame(capture); // capture a frame
IplImage* img = cvRetrieveFrame(capture); // retrieve the captured frame

Initialize a video encoder:

int fps = 10;
int width = 320;
int height = 320;
CvVideoWriter_FFMPEG writer;
writer.init();
writer.open("x.mpg", CV_FOURCC('D', 'I', 'V', 'X'), fps, width, height, true);

Encoding the previously captured image:

int wStep = img->widthStep;
int w =  img->width;
int h = img->height;
int c = img->nChannels;
writer.writeFrame((const uchar*)img->imageData, wStep, w, h, c, img->origin);

Initialize a video decoder:

CvCapture_FFMPEG cap;
cap.open(width, height);

Decoding the previously encoded image:

uint8_t* buffer = &writer.outbuf[0];
int length = writer.out_size;
cap.grabFrame(buffer, length);
IplImage* img2 = cap.retrieveFrame();

Show image in a window:

if (img2)
{
    cvShowImage("My Window", img2 );
    cvWaitKey();
}

Wednesday, November 23, 2011

DCI Sample Implementation

Download: https://github.com/dimitrs/DCI-NIDS/tree/DCI-NIDS-1

In this post I present an experimental network protocol analyzer implementation (in C++) based on the Data, context and interaction (DCI) paradigm and code snippets from Snort. My intention was to get first hand experience with DCI in C++, understand its benefits and its limitations, and evaluate its applicability to full-scale projects. Since I was unsuccessful in finding DCI C++ examples anywhere, my code represents the understanding of DCI that I have gained from piecing together the various code fragments from documentation. I admit that I find it a bit strange that there are no examples (that I could find). Is there an impediment to using DCI in C++ ? I did come across a couple of issues in my implementation. But first, let me list the goals of DCI as described by the DCI wiki entry and to state that to some degree or another I did experience the benefit of these goals:


  • To improve the readability of object-oriented code by giving system behavior first-class status;
  • To cleanly separate code for rapidly changing system behavior (what the system does) from code for slowly changing domain knowledge (what the system is), instead of combining both in one class interface;
  • To help software developers reason about system-level state and behavior instead of only object state and behavior;
  • To support an object style of thinking that is close to peoples' mental models, rather than the class style of thinking that overshadowed object thinking early in the history of object-oriented programming languages.


DCI consists of three parts: Data, context and interaction. Each of which I list below together with some observations about each one concerning the implementation I present in this post. One thing I should mention first is that I took most of the underlying code from Snort. My goal is not to re-design Snort. After all, it only took me about half and hour to find and understand the TCP/IP decoding and processing parts of the code, which could be a sign that it is fairly well designed even though its implemented in C. What’s more, I have re-implemented a very small part of Snort – just enough to take DCI out for a test-run. Take a quick look at the source code before reading on.

Data

The domain objects. They contain very little interaction code and mainly consist of getter and setter methods. I have used the prefix “Do” to denote data classes e.g. DoIPv4Packet, DoIPv6Packet and DoTCPpacket. They represent the IPv4, IPv6, TCP parts of the packet. You will notice that DoIPv4Packet and DoIPv6Packet are practically identical (see “Interaction”).


Context

Implements the use cases of the system. A context includes the roles and data objects and knows how to bind them. The context also provides a mechanism by which any role executing within that context can refer to the other roles in that context. I have used the prefix “Context” to denote context classes e.g. ContextIP. The ContextIP context decodes IP packet headers and applies IP layer rules and includes the specific roles and data objects specific to those tasks. A single data object may simultaneously play several roles. In the ContextIP context, a DoIPv4Packet object can play the Role_IPv4decoder and Role_IPrules roles (see “Interaction”).

The context knows which roles and data objects are to be used within its scope. Data objects are retrieved or created by the context. Below, is the ContextIP constructor. It creates the relevant data object and assigns the roles they are to play.


ContextIP::ContextIP(const void* packet) :
    decode_(NULL), rules_(NULL), pkt_(packet)
{
    const iphdr* hdr = static_cast<const iphdr*>(packet);   
    if (hdr->version == 4)
    {
        DoIPv4Packet* obj = new DoIPv4Packet;        
        decode_ = obj;
        rules_ = obj;
    }
    else if (hdr->version == 6)
    {
        DoIPv6Packet* obj = new DoIPv6Packet;        
        decode_ = obj;
        rules_ = obj;
    }
}


In one context I had a difficult time implementing the creation/retrieval of the data objects. The type of data object to be created/retrieved depends on what came before i.e. the state of previous data objects. Is it permissible to use a role from within a context constructor ? In the end I ended up in the strange situation where a role has no SELF because it has not been created yet, but uses other roles (see ContextStream). ContextStream creates or retrieves a TCP/UDP stream (or 5-tuple flow) and processes it. I am sure that this part needs to be reworked.


Interaction 


The Interaction is "what the system does." and is implemented as roles objects play at run time. I have used the prefix “Role” to denote role classes e.g. Role_IPv4decoder, Role_IPv6decoder, Role_TCPdecoderImpl.
Role objects combine the state and methods of a Data object with methods (but no state, as Roles are stateless) from one or more Roles. Role methods are injected into Data objects by use of traits. Unfortunately, the injection can not be done at run-time. The IP packet data object could play either the Role_IPv4decoder role or the Role_IPv6decoder role depending on the IP version. However, since both roles can not be injected onto the same data object, I had to duplicate data object itself – hence DoIPv4Packet and DoIPv6Packet are practically identical.
According to DCI documentation, a Role should only address another object in terms of its methodless Role i.e. a pure virtual base class. I found that it was essential to do this if only to compile successfully because of the dependencies between the Role, Data and Context classes. That is the reason for Role_TCPdecoder and Role_TCPdecoderImpl. Even though there may never be a different kind of TCP decoder I had to give the Role_TCPdecoderImpl a pure base class.
Below, you can see an IPv4 decoder role method. The role uses SELF which binds to the object playing the current Role. Code within the method invokes methods of the Data part of the object using SELF. Methods of other roles can also be invoked. RULES binds to the Role_IPrules role and allows one role to invoke methods on another role. A single data object may simultaneously play several roles. The DoIPv4Packet object play the Role_IPv4decoder and Role_IPrules roles.

template <class ConcreteDerived>

void Role_IPv4decoder<ConcreteDerived>::accept(const void* packet)
{
    const iphdr* ip = static_cast<const iphdr*>(packet);
   
    SELF->data(packet);
   
    SELF->srcip()->setAddr(ip->saddr);
    SELF->dstip()->setAddr(ip->daddr);
       
    if (ip->protocol==6)
    {
        SELF->proto(TCP_PROTO);
    }
    else if (ip->protocol==17)
    {
        SELF->proto(UDP_PROTO);       
    }
    else {
        SELF->proto(UNKNOWN_PROTO);               
    }
   
    SELF->totallength(ntohs(ip->tot_len));
    SELF->headerLength(ip->ihl*4);
    SELF->id(ntohs(ip->id));
    SELF->frag_flag(ntohs(ip->frag_off) & 0x3fff);
    SELF->frag_offset(ntohs(ip->frag_off));
   
    // Apply IP header rules
    RULES->match();
                   
    if (Role_IPv4decoder<ConcreteDerived>::getProto() == TCP_PROTO)
    {
        ContextTCP context(SELF, packet);
        context.doit();      
    }
}

Friday, September 02, 2011

A case for replacing polymorphism with switch-statements

Download: switch_benchmark.tar.gz

In this post I benchmark and compare virtual function calls to functionally equivalent if-else and switch statements. In object oriented design switch statements are substituted by polymorphism. The reason is to make the code more compact, readable and maintainable. However, the benchmark indicates that there is a case for doing the opposite -- replacing polymorphism with switch statements, if only for very specific and limited applications where performance considerations are the highest priority. Of course, switch statements can be made more compact, readable and maintainable using other C++ techniques such as metaprogramming. The source code for these techniques and the benchmark is available for download. Tested with gcc version 4.3.2.


The polymorphic benchmark uses a container (an array) that holds pointers to a base class from which several classes are derived. The time taken to make a virtual function call is measured for arrays of between 2 and 10 objects. An array of 2 objects takes 14 ns on average and 18 ns for 10 objects.

A functionally equivalent if-else function varies between 10 ns and nearly 18 ns.

The switch statement was the best performing at a constant 4 ns irrespective of number of objects. The switch statement is obviously being optimized by the compiler with the construction of a jump table.   

Should I care about a 14 ns virtual function call overhead? For most applications a few nanoseconds here or there make no difference. However, there are probably some software applications that might need to make every nanosecond count. For example, a network device may be described as having a performance of 10 gigabits per second (Gb/s). A 10-Gb/s Ethernet interface can deliver packets at between 812,740 and 14,880,960 p/s depending on the size of the packet, or on average it delivers packets every 67 ns - 1.2 us (see this article). In this context, a 14 ns overhead is significant. Therefore, if you are building a software application on top of 10 gigabits Ethernet interfaces, if-else and especially switch-statements might be the way to go. You can not make too many virtual function calls in 67 ns. Granted, my hardware may not be cutting-edge but I think a case can be made for switch-statements over polymorphism. Function call overhead can be improved  by a factor of at least 4.

Getting back to compactness, readability and maintainability of the code; we can improve the if-else and switch statements using Boost’s mpl, preprocessor and tuple libraries. You can see below a typical switch-statement and how it is used in place of an array of pointers.

struct SwitchBase
{
    void function(long* x, int type)
    {
        switch(type) {
            case 0:
                obj1.function(x);   
                break;
            case 1:
                obj2.function(x);   
                break;
            case 2:
                obj3.function(x);   
                break;               
            case 3:
                obj4.function(x);   
                break;
            case 4:
                obj5.function(x);   
                break;
            case 5:
                obj6.function(x);   
                break;               
            case 6:
                obj7.function(x);   
                break;
            case 7:
                obj8.function(x);   
                break;
            case 8:
                obj9.function(x);   
                break;               
            case 9:
                obj10.function(x);   
                break;               
        }
    }

    ImpOfStatic1 obj1;
    ImpOfStatic2 obj2;
    ImpOfStatic3 obj3;   
    ImpOfStatic4 obj4;
    ImpOfStatic5 obj5;
    ImpOfStatic6 obj6;   
    ImpOfStatic7 obj7;
    ImpOfStatic8 obj8;
    ImpOfStatic9 obj9;   
    ImpOfStatic10 obj10;
};

long sum=0; 
SwitchBase sw;
sw.function(&sum, 2); // calls object 3 with a 4 ns overhead
sw.function(&sum, 0); // calls object 1 with a 4 ns overhead


Writing switch-statements like this by hand is tedious and error prone. Instead we can automate its construction. I provide a class called “switch_case”. The compiler automatically constructs all the case statements required and the performance (Switch-Boost) is exactly the same as the hand written version.


Usage: Create instances of each class and add them to a container (a Boost tuple).

// Instantiate the class instances
ImpOfStatic1 s1;
ImpOfStatic2 s2;
ImpOfStatic3 s3;   
ImpOfStatic4 s4;
ImpOfStatic5 s5;
ImpOfStatic6 s6;   
ImpOfStatic7 s7;
ImpOfStatic8 s8;
ImpOfStatic9 s9;   
ImpOfStatic10 s10;

// Create a tuple and store the instances
typedef boost::tuple<
      ImpOfStatic1*,
      ImpOfStatic2*,
      ImpOfStatic3*,
      ImpOfStatic4*,
      ImpOfStatic5*,
      ImpOfStatic6*,
      ImpOfStatic7*,
      ImpOfStatic8*,
      ImpOfStatic9*,
      ImpOfStatic10*> StatTuple;

// Store the instances in the tuple
StatTuple tup(&s1,&s2,&s3,&s4,&s5,&s6,&s7,&s8,&s9,&s10);
           

// Crreate a switch-statement for all types in the tuple.
switch_case<StatTuple> call(tup);
Func f;
call(f, 2, &sum);    // calls object s3 with a 4 ns overhead
call(f, 0, &sum);    // calls object s1 with a 4 ns overhead


In this case, you do not have to write a switch-case function by hand. The compiler does it automatically. It is almost as elegant as the polymorphic solution and comes with a couple of real advantages:

1) Function call overhead is improved by a factor of four.
2) Functions can be in-lined -- virtual functions can not.
3) No loss of type identity specific to derived classes. 
4) No derived classes are needed. Classes can have different member function names.




Wednesday, June 15, 2011

Benchmarking function call overhead in C++

Download: benchmark.tar.gz

The are two types of function calls I benchmark here:

1) Virtual functions
2) CRTP, used to simulate dynamic binding (with and without inlining)

One particular use of the CRTP is to simulate dynamic binding. The technique achieves a similar effect to the use of virtual functions, without the costs of dynamic polymorphism. The reason for this stems from the ability to inline function calls which is not possible with virtual functions bound at run-time. The use of CRTP is only worthwile when the cost of calling a funcion is not dominated by call and return overhead. Getter and Setter funcionts are good candidates for inlined CRTP.

Dynamic.h
#ifndef _Dynamic_H
#define _Dynamic_H

struct DynamicBase
{
    DynamicBase() {}
    virtual ~DynamicBase() {}
    virtual void function(long*) = 0;
};

DynamicBase* createDynamic();

#endif  /* _Dynamic_H */
Dynamic.cc
#include "Dynamic.h"
struct ImpOfDynamic : public DynamicBase
{
    void function(long* x);
};

void ImpOfDynamic::function(long* x) { ++*x; }

DynamicBase* createDynamic() {
    return new ImpOfDynamic;
}
Static.h
#ifndef _Static_H
#define _Static_H

template 
struct StaticBase
{
    void function(long* x)
    {
        static_cast(this)->function(x);
    }
};

struct ImpOfStatic : StaticBase
{
    // Without inlining  
    // void function(long* x);    

    // With inlining 
    inline void function(long* x);
};

void ImpOfStatic::function(long* x) { ++*x; }

#endif

main.cc
#include "Static.h"
#include "Dynamic.h"
#include 
#include 

Benchmark Results:

Without CRTP inlining:
6.01975 Virtual function (ns)
6.0212 CRTP function (ns)

With CRTP inlining:
6.16391 Virtual function (ns)
1.99611 CRTP function (ns)

There is no point in using CRTP instead of virtual functions unless inlining is used.

Wednesday, March 02, 2011

Test Code Coverage with Objdump and Valgrind

I was working on a C++ project recently where gcov inexplicitly failed to report correct results, especially for template files. Some templated code was incorrectly being reported as not-covered by my tests. Instead of doing the right thing by finding out why gcov was not working with my source code, I decided to write a python script that combined the outputs of objdump and valgrind into a test coverage report. It worked well enough and I thought I would share it.  Here is an extract of a test coverage report:

---------------------------------
File: HTTPmsg.h
Code not executed in: HTTPmsg<TCPfragmsg>::getContentEncoding() const
line no: 110

Code not executed in: HTTPmsg<TCPfragmsg>::DJBHash(char const*, char const*)
line no: 271

Code not executed in: HTTPmsg<TCPmsg>::isCandidateRequest() const
line no: 215

Code not executed in: HTTPmsg<TCPfragmsg>::isCandidateResponse() const
line no: 236 238 239 242 248 251 252

Code not executed in: HTTPmsg<TCPfragmsg>::getContentDirection() const
line no: 105

Compiled lines: 82, Not executed: 11
Code coverage:  86%
---------------------------------

The script can be found here: coverage

Tested on objdump (GNU Binutils for Ubuntu) 2.20.1 and valgrind-3.6.0.SVN-Debian.


Below, you can see the output of objdump and valgrind's for the 'isCandidateRequest' member function. The objdump output describes what code was compiled and the output of callgrind describes what code was executed. The script works by checking for common line numbers between them. Line numbers that appear in the object dump and not in the valgrind output are marked as non-executed source code.

objdump:  'isCandidateRequest' member function:

080e9498 <HTTPmsg<TCPmsg>::isCandidateRequest() const>:
_ZNK7HTTPmsgI6TCPmsgE18isCandidateRequestEv():
/projects/conduits/conduits/HTTPmsg.h:203
 80e9498:       55                       push   %ebp
 80e9499:       89 e                    mov    %esp,%ebp
 80e949b:       83 e28                sub    $0x28,%esp
/projects/conduits/conduits/HTTPmsg.h:205
 80e949e:       8b 45 08              mov    0x8(%ebp),%eax
 80e94a1:       8b 80 e0 00         mov    0xe0(%eax),%eax
 80e94a7:       85 c0                   test   %eax,%eax
 80e94a9:       75 26                   jne    80e94d1 <HTTPmsg<TCPmsg>::isCandidateRequest() const+0x39>
/projects/conduits/conduits/HTTPmsg.h:206
 80e94ab:       b9 00 00 00 00    mov    $0x0,%ecx
 80e94b0:       a1 e8 7e 26 08    mov    0x8267ee8,%eax
 80e94b5:       8b 15 ec 7e 26    mov    0x8267eec,%edx
 80e94bb:       83 c0 01              add    $0x1,%eax
 80e94be:       83 d2 00              adc    $0x0,%edx
/projects/conduits/conduits/HTTPmsg.h:215
 80e9624:       b9 00 00 00 00    mov    $0x0,%ecx
 80e9629:       a1 20 7f 26 08     mov    0x8267f20,%eax
 80e962e:       8b 15 24 7f 26     mov    0x8267f24,%edx
 80e9634:       83 c0 01              add    $0x1,%eax
 80e9637:       83 d2 00              adc    $0x0,%edx
 80e963a:       a3 20 7f 26 08     mov    %eax,0x8267f20


Callgrind: 'isCandidateRequest' member function:

fn=HTTPmsg<TCPmsg>::isCandidateRequest() const
203 87
205 116
jcnd=29/29 206
205
206 174