C++ Soup!

Elements of Programming: A Review (Part 3)

2009-10-03T07:07:00.001-07:00

In Part 2 I showed the beginnings of a generic Range library implementation that approaches the problem by implementing a generic algorithm that deals with a Concept of a Range. In this third installment to the review of the book Elements of Programming by Alexander Stepanov and Paul McJones, I intend to present a logical thesis on how to approach application development at a higher level using generic programming techniques along with the strong mathematics and Concept-based approach that the book advocates.

Set-Up

So first, let's assume we're writing a simple application that takes a file input that contains a set of coordinates in a cartesian plane. These coordinates show a set of points connected to each other. This is a fully-connected graph.

Our application is supposed to read all the coordinates and then store it in memory when the application starts. First we don't specify what kind of data structure we use, just that we're going to put it in memory. Second, we don't assume how we store it in memory or whether we put it in a database of some sort -- just that we store it somewhere. Third, we don't know yet how each coordinate is stored but rather that we're just going to assume we're going to have it stored somehow.

At this point of the description, the application isn't really that interesting. However what it's supposed to do is what's interesting.

Ready for Input

Once the application has read all the coordinates from the file, the application is then ready for input. At this state, the application will take the input from the standard input device (or std::cin) in the form of three numbers separated by white space -- which signifies another cartesian coordinate, and a threshold distance value.

First, we assume that the numbers are within the range [-INTMAX,+INTMAX) where INTMAX is the largest possible value represented in an 'int'. Second, we assume that we can store the coordinate the same way we store a coordinate we read from the file. Third, the absolute value of the threshold is used -- therefore negative values become positive values.

So far so good, but then we get to the meat of the application.

The Problem/Solution

What we want to do is find all the coordinates that are within the threshold distance from the input coordinate and print to standard output the coordinates in the form "[x,y] d" where 'x' is the coordinate on the x axis, y is the coordinate on the y axis, and d is the distance to the input coordinate. If you draw a circle around the input coordinate at its center with radius of the threshold distance, then the coordinates that lie within the circle are those coordinates we're looking for.

If you can imagine it in your head, what we're going to have to do is:

Compute the distance between each coordinate and the source coordinate.
Filter out the coordinates that aren't within the threshold distance.
Display each coordinate in the prescribed format through standard output.

Understandably, we should be able to use already available STL containers and algorithms to do this. We can even model each coordinate as a std::pair<int,int> -- and then store them in a list.

In this first incarnation of the solution, we have a few distinct steps which are:

Load the coordinates from the file.
Get the distances and store it along with the pair into another list.
Filter this list and remove the lists that aren't within a certain distance.
Print the filtered list.

There is nothing wrong with this implementation per se -- however I see that we have three lists. We can optimize this implementation by removing the filtered list, and then hand-writing the iteration of the list of coordinates and distances.

Concepts

So in this implementation we're seeing that there is a certain concept called the coordinate. These are some basic operations defined against a Coordinate that should be valid (via ADL perhaps):

coord_x(c)
coord_y(c)
distance(c1, c2)

In these operations, we assume that 'c', 'c1', and 'c2' are instances of a type that models the Coordinate concept. This gives us a set of primitive operations which we can work with in our application. In this domain of coordinates, we can then count on having the distance between two coordinates and retrieving the x and y components of the coordinate.

Algorithms

Here we can then define the algorithms we need to implement. In a generic (and orthogonal) fashion we find that we have a few basic algorithms required to satisfy the end result that we want to achieve in the program:

read_coordinates(input_stream) -> range<input_iterator>
copy_filtered(coordinates, filter, render, output) -> void

The read_coordinates(input_stream) algorithm returns a range of values. For this case we use the Boost.Range concept of a Range which is a pair of iterators for the sake of brevity. Below is a simple implementation of the read_coordinates algorithm:

template <class InputStream>
iterator_range<typename InputStream::iterator>
read_coordinates(InputStream & input_stream) {
  return iterator_range<typename InputStream::iterator>(
   istream_iterator<coordinate>(input_stream),
   istream_iterator<coordinate>()
   );
}

template <class InputStream>
InputStream & operator>>(InputStream & is, coordinate & c) {
  is >> c.x >> c.y;
  return is;
}

This version of read_coordinates relies on the std::istream_iterator<> template that relies on an overloaded shift right (operator>>) implementation that works with an istream and an instance of a coordinate type. This is why we overload the operator>> too above.

The we look at the algorithm for copy_filtered(coordinates, filter, renderer, output). Below is this generic implementation that takes four arguments:

template <class CoordinateRange, class Filter, class Renderer, class OutputIterator>
void copy_filtered(CoordinateRange coordinates, Filter filter, Renderer render, OutputIterator output) {
  typename iterator_traits<CoordinateRange>::type iter = begin(coordinates),
   end_ = end(coordinates);
  while (iter != end_) {
   if (filter(*iter)) {
   *output++ = render(*iter++);
   }
  }
}

In the above algorithm we see that we treat coordinates as a range, and then iterate through each item to check if the filter algorithm returns true, we copy the rendered item to the output iterator. This is a very generic filter algorithm that we can use not only in the scope of the program we're building but also other programs. However, in our domain, we may encounter a few snags in terms of efficiency. Let me try and help by pointing out a few things:

In our application, we intend to filter based on the distance between a certain coordinate and the coordinates we read from the file. This means we have to compute the distance in the filter function and the render function.
The algorithm above assumes that the filter function will return only a bool. We can change it to get a pair of values instead, a boolean to indicate that it qualifies and the distance. The problem with that approach is that the algorithm then becomes very narrow and specific to our application.
The renderer's return type should be convertible to the output iterator's value type -- this kind of undue coupling is something that is a fact of generic programming (even the STL does this with the copy algorithm). However in our application, the renderer -- which presumably will turn a coordinate into a string given the format we intend to output, will also need to compute the distance.

This isn't turning out very well for our approach; although we've identified the algorithms we'll be requiring and the concepts we're going to work with, we aren't able to make an implementation yet that is as efficient as hand-coding everything into a single loop. The first incarnation made too much use of memory by making different lists -- that approach won't scale if we have a huge list of coordinates to go through and we keep making extra lists. This second approach eliminates the intermediate lists but computes the distances between the input coordinate and each coordinate from the file twice.

Third Time's the Charm

So let's back up a bit here. Up until this point we've been trying to make generic algorithms from our simple program. Our first incarnation would work although it consumed too much memory. Our second incarnation was a little alright although we're doing multiple computations of the distance. Let's then see how we can do if we can introduce some laziness in our implementation.

First, let's look at our mathematical requirements:

We have a tuple (x,y) which represents a point in a two dimensional integral plane.
We have a function distance(p1, p2) which represents the distance between two points.
We want to filter the points whose distance from a source point is within a certain threshold value.
We want to print these points and their distance from the source point.

From here we then transform this into a nested pseudocode representation:

print( filter( _ < threshold, transform(distance(source, _), points) ) )

The idea above is that we want to "print" all "filtered" points, where the distance from a source is less than a threshold.

First problem we encountered (and dealt with) was that we had intermediate lists. We then imaging dealing instead with iterators in this solution. Second problem was that we computed distance twice -- first in the filtering, and second time in the rendering.

To solve both problems, we want to be able to transform each point as just a single tuple (x,y), into a bundling of the coordinate and the distance. So now we're looking at a tuple ((x,y), d) where d is the distance -- the reason we want to do this is so that we bundle the coordinate with the distance, so that we can filter them efficiently using our filter algorithm.

Let's see how we can implement our 'distance_bundler' function object:

template <class C>
struct distance_bundler {
  typedef tuple<C, double> result_type;
  distance_bundler(C const & source) : source_(source) {}
  tuple<C, double> operator() (C coord) {
   return make_tuple(coord, distance(source_, coord));
  }
  C source_;

};

So here we've made an effort already to make a specific data representation using our approach. However, consider that we are using a generic 'distance' function which can be easily retrieved via Argument Dependent Lookup (ADL) based on the type C's namespace.

Next we implement a unary predicate function that takes a coordinate-distance bundle, and returns true if the distance is within a threshold value. This is how we can implement that filtering predicate:

struct within_threshold {
  typedef bool result_type;
  within_threshold(double threshold) : threshold_(threshold) {}
  template <class C>
  bool operator() (tuple<C, double> distance_bundle) {
   return get<1>(distance_bundle) < threshold_;
  }
  double threshold_;
};

In both the preceding implementations, we can choose to use BCCL to make sure the type 'C' models the Coordinate concept. I purposely left that out here to yield more readable examples.

Our next step would be to transform a qualified coordinate and the distance to the source into a string which we can then output. Here we require a 'render' function which will turn a coordinate bundle into an STL string which we also implement:

template <class C>
string render(C const & c) {
  ostringstream output_stream;
  output_stream << "[" << coord_x(c) << "," << coord_y(c) << "]";
  return output_stream.str();
}

struct bundle_printer {
  typedef string result_type;
  template <class C>
  string operator() (tuple<C, double> bundle) {
   ostringstream output_stream;
   output_stream << render(get<0>(bundle)) << " " << get<1>(bundle);
   return output_stream.str();
  }
};

Again above we can use the BCCL to enforce that the type 'C' models Coordinate.

Next thing we do is we combine these elements into a lazily-applied construction that uses Boost.Iterators to stitch together the individual moving parts. The code follows, which is explained in greater detail later.

transform(
  make_filter_iterator(
   within_threshold(threshold),
   make_transform_iterator(
   begin(input_range),
   distance_bundler(source)
   )
  ),
  make_filter_iterator(
   within_threshold(threshold),
   make_transform_iterator(
   end(input_range),
   distance_bundler(source)
   )
  ),
  ostream_iterator<string>(
   cout, "\n"
  ),
  bundle_printer()
);

If you happen to be using Boost.RangeEx you can use the algorithm version that supports ranges:

transform(
  make_filtered_range(
   within_threshold(threshold),
   make_transformed_range(
   input_range,
   distance_bundler(source)
   )
  ),
  ostream_iterator<string>(cout, "\n"),
  bundle_printer()
);

Or:

transform(
   input_range
   | transformed(distance_bundler(source))
   | filtered(within_threshold(threshold)
   , ostream_iterator<string>(cout, "\n")
   , bundle_printer()
);

So in the preceding three sample listings, instead of applying the algorithms to different containers we turn them into lazily-applied functions to each element in the input range. Here we feed directly from the file into memory (in the form of a coordinate object that has been read from the input stream) then apply the transformations and filtering as we go through the coordinates.

We also preserve the information required from the initially applied function 'distance_bundler' by bundling it with the result so that it can be used in the filtering -- and therefore have the computed value of the distance only computed once. This chaining approach and using generic algorithms to solve problems is a key theme being proposed by the book at varying levels.

Conclusions

Using the techniques espoused by the book "Elements of Programming" we can come up with a means of showing how we can use these techniques and apply them when building applications. Using generic algorithms and functions that do specific things at varying levels for both efficiency and correctness is a good practice that yields the desired result.

One of the biggest thrusts of the book is that of composition using building block functions in order to solve problems without having to resort to overly complex structural solutions. Instead of relying on object oriented programming alone, we can leverage functional programming and generic programming techniques to achieve efficient and expressive code. The role of composition in problem solving and extending software in general is something developers should be using more and more.

Instead of trying to re-inventing algorithms we should strive first to see if there are already algorithm implementations out there that we can leverage to allow us to solve problems faster by implementing the parts that are specific to our application. Short of using frameworks, libraries that are generic enough lend themselves to better re-use in more contexts than niche targeted solutions in the form of frameworks and platforms.

This concludes the three-part series on the coverage of the "Elements of Programming" book by Alexander Stepanov and Paul McJones. Post comments for questions, suggestions, clarifications, and further elaboration.

Memcache++ Updates (New Releases!)

2009-08-28T23:04:00.000-07:00

The past week has been a big open source week for me which started from the weekend that spilled into the week. I've been updating and improving the implementation of the Memcache++ Client which I've released the first version of (0.9) last February 2008. One full year and some months afterwards I got an email from a former client who asked me if I can improve the client to handle newer memcache protocols that I first didn't need, and some older ones which he does need. Needless to say, I went at it and the product of which is a cleaner implementation that also supports more commands than it used to.

Before I go dive into the details of the implementation, let me first give you a history on the Memcache protocol, why it's important, and the project that led to the development (and release) of the memcache++ client library.

History

So back in February 2007, I started work with one of the largest social networking sites in the world. While there, I found myself in the middle of a project that was meant to increase the performance and scalability of an internal service that was crucial to the proper functioning of the site. One of the approaches taken was to leverage memcached to store frequently accessed and seldom changing data.

Without going through the whole project's history, we first used libmemcache which was the easiest thing to do at the time. It worked for a while, until we saw that there were some issues with the library because it made too many connections to the memcached server and this degraded performance over time. This may have been addressed with tuning the server on which the software we wrote (which was in C++) was running on, but then that meant operational overhead if we added machines or later encountered a spike that causes the number of connections to balloon to an insane number. While it worked, it was not the scalable solution that we were looking for.

For a while we tried to stick with it, but performance and stability tests kept complaining that over time the application (because it opened and closed lots of connections to the memcached servers) became unstable and performance numbers would suffer. This meant we either had to abandon the memcached idea altogether or we just write our own library to access the memcached servers from scratch. So we tried the writing our own library approach, and we did it from the ground-up with C++ forgoing the C implementation.

After a month or so of heavy development and integration work, we were finally able to meet the performance requirements of the internal service. Not only that, we were also able to make the library a separate component that just did what we needed -- access memcached, pool a set of connections to many servers, and re-use long-lived connections instead of opening and closing new sockets everytime we need to issue requests. The performance numbers were impressive and so we were happy that we got to where we needed.

Open Source

Then the idea came to mind: why don't we open source this library that we worked so hard to implement internally to get us to the point where we wanted to be (in a position to succeed) -- after all, memcached was instrumental to the success of other sites and was open source, why not the client library? Besides, it's one way for us to give back to the open source community on which a lot of the software we've written is running on.

So after a short discussion with the powers that be, the library was open sourced on January 2008 -- the project was registered on Sourceforge and the first release was uploaded on February 2008. This was met with some buzz, but apparently there aren't a lot of C++ projects that required the use of a memcache client out in the open. It seems most of the web projects that needed memcache were written in languages other than C++ -- hardly disheartening, because just a short few days later some hits came through and there were some users out there who were thinking about using the client in their C++ applications too.

Why Memcache?

So is memcached just for the web? I'd say hardly so. Let me give you a few examples where you'd want to be able to use memcache in your non-web (C++) applications:

Multiple Reads, Minimal Writes -- if you have an application that does a huge number of selects from a database from multiple sources (maybe different threads or different machines) and the data being queried rarely changes or is not time-critical data, then that means you can safely cache this either in your application or to an external cache provider. This external cache provider can be memcached and since you can store practically anything in memcache, you can definitely leverage this and alleviate your database from the strain of multiple readers and infrequent writers.
Shared Data -- Say you have an application which appends information to a queue or a file and you'd like to be able to share this across many instances of your application, you might think about putting this data straight to a database and then querying the database anytime you need that data. The problem here is that your bottleneck becomes the Database and it's pretty hard to fix that bottleneck if you rely on it for your shared data needs. Enter memcached which supports "append" and "prepend" operations -- so instead of just writing to the DB, you can also append or prepend the data to a key in memcached and just query that across instances of your application.
Atomic Counters -- Sometimes you might want to keep just a count of the number of times something is done (say the number of times a particular piece of data is accessed or modified). Typically you'll use a DB too so that you can query this information anytime you need it -- problem is that sometimes operations where you do COUNT() on primary keys from a DB would be resource-intensive especially if you have a large table. Enter memcached's 'incr' and 'decr' operations where you can set a key to be '0' and merely increment that key when a piece of data is accessed or modified. You can then query this information as often as you like alleviating the strain this introduces to your database.

There are all sorts of places in Enterprise or High Performance applications where you may opt to cache data and usually this is where memcached would be a good fit. Of course, if you just keep in mind that the data is just cache data and data you can afford to lose, then it fits perfectly into a solution where you can access the cache first (if it's not there, then go to the canonical source -- usually a database server).

The Client

Memcached is the server which maintains a hash map in memory -- mapping keys to values. Values can be anything, and keys can be strings that don't have control characters or spaces in it. It can be a UUID, an aggregated string, a random value, an MD5 hash, or just any string you want to associate data to. Although there's a lot of cool technology in the memcached server, the client we've released (and now I maintain) leverages this server-side technology by offering a fast and stable interface to setting and retrieving the data.

The Memcache++ client offers the following features:

Support for memcached's 'get', 'set', 'add', 'replace', 'append', and 'prepend' commands.
Supports redundancy pools where you can associate more than one memcached server to a pool identifier and when getting data from this pool you try all the members of the pool to retrieve the data; when setting data on this pool, all 'set', 'add', 'replace', 'append', and 'prepend' operations are mirrored across members of the pool for redundancy.
Uses persistent connections per memcache client handle: using one handle per thread allows you to maximize multi-core machines without having to synchronize operations on a single handle.

The latest release (came out last Wednesday, August 26, 2009) is version 0.11.1 which supports all the above features mentioned. In the following days I may release version 0.11.2 which adds a little more polish to the implementation.

These releases are just gearing up for release 1.0 which should support the "compare and set" (cas) operation, multiple get support, proper 'incr' and 'decr' support, among other performance and implementation enhancements.

Try it Out!

So if you have a C++ application that you think would greatly benefit from a separate cache provider like memcached, try out the library and let me know what you think! Hopefully it allows you to achieve performance and stability too like it allowed us to have back then -- and up until now.

You can get the source code through two means:

Download the latest from Sourceforge.net.
Checkout the Git repository: git://memcachepp.git.sourceforge.net/gitroot/memcachepp/memcachepp

The author is also available for consulting in case you need to extend the library for your own needs and would rather not have the changes released as open source. The library is released under the Boost Software License which allows for the library to be used in commercial and proprietary applications. It is a header-only library and requires Boost 1.38 and higher to use. Consulting or support inquiries may be sent through this form.

Elements of Programming: A Review (Part 2)

2009-08-09T01:35:00.000-07:00

In Part 1 I covered three major foundational concepts being put forth by Alexander Stepanov and Paul McJones in Elements of Programming, their latest book published by Pearson Education. This post then attempts to apply the concepts in the book by putting forth some examples that were not lifted from the book, because it's already full of concrete samples and applications. In this installment in a three part series, I attempt to apply the generic programming foundational approach to building a simple range composition library.

After reading the book I got more and more interested in programming in the style that Generic Programming [1][2] prescribes and to apply the concepts being taught. The highlight of the elements of programming is the deliberate and evolutionary process in which algorithms are implemented to be both efficient and generic. However, to get to the generic part we will need to start with the specific implementation.

Concepts in Action

Even if we won't be having language level support for Concepts in C++0x, we can still enforce concept checking using the Boost Concept Check library. This library has been around for quite a while already and provides an easy means of defining concepts and enforcing them on your algorithms with the C++98 and C++0x. I've in-lined a simple example of how we can use Concepts in our programs:


#include <boost/concept_check.hpp>

template <class T>
struct Foo : boost::DefaultConstructible<t> {
  private:
      T t;
  public:
      BOOST_CONCEPT_USAGE(Foo)
      {
          T c(t);     // T must be copy constructible
          c.foo();    // T must have a nullary function foo
      }
};

template <class T>
void call(T & t) {
  BOOST_CONCEPT_ASSERT((Foo<t>));
  t.foo();
}

struct a_foo {
  void foo() { /* do nothing */ }
};

struct not_a_foo {
  void foo_() { /* do nothing */ }
};

int main(int argc, char * argv[]) {
  a_foo foo_thing;
  not_a_foo bar;

  call(foo_thing); // ok
  call(bar); // not ok, will fail
}

In the above sample, what's interesting is that the code will not compile and that's by design. This example is also meant to show how much more readable error messages are with Concepts:


concepts_example.cpp: In function ‘void call(T&) [with T = not_a_foo]’:
concepts_example.cpp:34:   instantiated from here
concepts_example.cpp:18: error: ‘struct not_a_foo’ has no member named ‘foo’
concepts_example.cpp: In destructor ‘Foo<t>::~Foo() [with T = not_a_foo]’:
/home/dean/boost/boost/concept/detail/general.hpp:38:   instantiated from ‘static void boost::concepts::requirement<boost::concepts::failed************>::failed() [with Model = Foo<not_a_foo>]’
concepts_example.cpp:17:   instantiated from ‘void call(T&) [with T = not_a_foo]’
concepts_example.cpp:34:   instantiated from here
concepts_example.cpp:11: error: ‘struct not_a_foo’ has no member named ‘foo’

This is something that's worth paying for (and having) if you write a lot of code that depends on concepts -- and if you intend to write generic algorithms. From here on I'll make use of implementations that expressly use concepts implemented using the Boost Concept Check Library (BCCL).

Ranges

One of the main theses of the book is that generic algorithms build upon basic Concepts and implement generic enough abstractions to make implementations re-usable and powerful in their own rights. The book talks a lot about the Iterator concept hierarchy in the Standard Template Library (STL) and how you can write algorithms that build upon these Iterator concepts and some "refinements" (or more narrow specific types of Iterator concepts).

Briefly the book also covers a topic on Ranges that are represented as a pair of Iterators. Looking at this concept of a Range and the thoughts shared lately by Andrei Alexandrescu in his keynote address [3] in the recently concluded BoostCon 2009, I'm inclined to think that there is merit in what Andrei has been proposing -- that there may be something to be gained by making Ranges the primitive Concept to deal with when implementing generic algorithms that deal with a collection of data. Having said this, let me give you a short discourse into how you can implement this using a similar approach shown in the book.

First let us define a simple concept we want to deal with: a Range. A Range allows us to do a finite number of things to it:

Pop the element at the front of the range (pop_front(range)).
Get the element at the front of the range (front(range)).
Check if a range is empty (empty(range)).

To put this in code, we need a Range concept that we should be able to check programmatically. The following listing shows a candidate definition of the minimal Range concept using BCCL:


template <class R>
struct Range : boost::DefaultConstructible<R>, boost::EqualityComparable<R> {
    private:
        R r;
        typedef typename R::value_type value_type;
    public:
        BOOST_CONCEPT_USAGE(Range)
        {
            R c(r); // R must be copy constructible
            pop_front(c); // support a pop_front action
            value_type ref = front(c); // support a front action
            bool result = empty(c); // check if a range is empty
        }
};

In the code above we define the syntactic requirements for a type R to model the Range Concept. We then implement a very simple range, a counted_range which defines the numeric range from [0,max).


struct counted_range {
    counted_range(size_t max = 0) : count_(0), max_(max) {}
    counted_range(counted_range const & other) : count_(other.count_), max_(other.max_) {}
    bool operator==(counted_range const & rhs) {
        return ((rhs.count_ == count_) && (rhs.max_ == max_));
    }
    bool operator!=(counted_range const & rhs) {
        return !(*this == rhs);
    }
    typedef size_t value_type;
    private:
    friend void pop_front(counted_range &);
    friend size_t front(counted_range &);
    friend bool empty(counted_range &);
    size_t count_, max_;
};

void pop_front(counted_range & range) {
    ++range.count_;
}

size_t front(counted_range & range) {
    return range.count_;
}

bool empty(counted_range & range) {
    return range.count_ >= range.max_;
}

Note in the implementation that we didn't define member functions but rather relied upon free functions -- this is by design because our Range Concept definition requires free functions pop_front, empty, and front. Now that we have a simple definition of a counted_range all we need to do is write an algorithm that actually requires the Range concept. Let's see a simple algorithm named count which will just count the number of elements in a Range.


template <class R>
BOOST_CONCEPT_REQUIRES(
        ((Range<R>)),
        (size_t)
        )
count(R range) {
    size_t result = 0;
    while (!empty(range)) {
        pop_front(range);
        ++result;
    }
    return result;
}

We can see here that we have a function count that takes as a parameter an object range of type R which models the Range Concept and returns a value of type size_t. Note that we're dealing with a copy of the range, which allows us to mutate the range within the algorithm without having to deal with the original range.

We can then call the count algorithm a regular function -- one that will return the same value given the same input. Because it is a regular function, we can then be sure that it will return the same value given a range of the same properties, and then use it in our higher level functions and be sure that we can count on count (pardon the pun) to do the right thing every time it is called. Our only worry is that the codomain of the function is the set of values that can be represented with the size_t type. That means, if you have a Range type that represents a range that has more than the maximum value that a size_t can handle then either you have an invalid Range type or count is ill-defined for that input.

We then have two choices here: 1) we require the Range to support a distance_type nested class which defines the type for the distance between the first and last element of a Range or 2) we refine the Range concept with another concept called a FiniteRange which defines a finite range (meaning the number of elements in the range can be counted) and has the distance_type part of each type that models the FiniteRange Concept.

I like choice 2 better because we can then have two more specific kinds of Ranges -- an InfiniteRange and a FiniteRange. We can then have classifications of FiniteRange concepts that refine further the FiniteRange type and possibly see ForwardRange, BidirectionalRange, RandomAccessRange, InputRange, etc.; I can then also imagine another set of InfiniteRange concepts that refine InifiniteRange and see a GeneratorRange, OutputRange, IdentityRange and others like so.

Further Thoughts

What I attempted to show here without quoting entries from the book (which I definitely encourage everyone to get at least a copy of) is that using the techniques of being able to understand the relationship between concrete classes and the notion of Concepts allows us to approach problem solving in a more formal and generic manner. Being able to put requirements on the types of the parameters of functions and understanding the limitations and capabilities of our algorithms gives us better foundations to write solutions on top of.

This means we should be able to reason about our solutions and enforce the reasoning with the help of libraries like the BCCL. Because we are then able to reason about our solution we can build better software with more confidence that we actually know what is going on. Combine this with the generic programming approach of working from specifics to generics and you then have a method of building libraries and solutions that will withstand the test of time.

Adopting a mindset of understanding the requirements on inputs of a function and also the implications of the output of a function gives us an understanding of the limitations and applicability of our solutions on a broad range of problems. Maybe we have an algorithm that will be efficient for a certain class of Concepts and better algorithms that will be more efficient with more refined classes of Concepts. Using both the Object Oriented nature along with the Functional and Generic nature of C++, we can then have a better chance of writing algorithms, programs, solutions, and applications that we can be confident about using equational reasoning.

Part 3

In Part 3 I will attempt to construct a logical thesis that will show how to approach application development using the concepts put forth in the book. In the next (and last) installment of my review of the book I will put together an example that uses the BCCL, Boost.Test, and Boost.Asio.

References

[1] Generic Programming : Wikipedia Definition

[2] generic-programming.org

[3] BoostCon 2009: Iterators Must Go!

This is part 2 of a three-part series on the review of the Elements of Programming book by Alexander Stepanov and Paul McJones. Comments, suggestions, and questions are welcome in the comments section. In case you prefer email, send them to the author through me@deanberris.com or dean.berris@cplusplus-soup.com.

Elements of Programming: A Review (Part 1)

2009-08-04T07:06:00.000-07:00

Over the course of the past few months much has happened to me in my life. Besides getting married to the love of my life (twice) and moving to a new job, I've received a review copy of the recently released Elements of Programming by Alexander Stepanov and Paul McJones. What follows is my take on what I think of the book and why everyone -- and I say absolutely everyone -- who has been doing software engineering for quite a while already should get a copy of this book.

I personally think this book is as important to the field of software engineering (and programming in general) as how the Principia Mathematica was to mathematics. This is the book which will give those who care about the craft of software engineering and problem solving with software the fundamental insight into how libraries and software packages meant to deal with real-life projects should be written. Consequently after reading this book you'd want to look at all your source code you ever wrote before and see how you can apply the concepts being taught in the book.

This is how valuable I think this book is: I'll actually get multiple copies of the book as foundational reading for my team -- and pay for the copies myself if I have to. This is one of those books that I've come across where I think the price I pay to have a copy of it is definitely worth every penny if not even more.

Enough of what I think; now I want to talk about what the book contains and why I'm raving about the book so much it's taken three paragraphs of this entry for me to get to this point. But first, let me give some "prerequisites":

If you haven't been programming in C++ before, get into it now if only to be able to understand what the principles and techniques being taught are. It's not a prerequisite that you are an expert in C++, but if you understand how to use templates in your own code that would be great.
If you didn't have a major in mathematics, you might want to keep an elementary algebra and discrete mathematics reference around. Having been a computer science major at one point in my life, I can now appreciate the application of Set Theory and Group Theory to practical software development. It would really help if you have solid mathematical background.
If you think this will be an easy read, adjust your expectations now. It's going to be really hard to just skim through without thinking and focusing. Remember how you read (or tried to read) your high school textbooks to prepare for an exam? Well I do, and I'd recommend you use the same focus and techniques to read and digest what this book is all about.
Keep a notebook close so that you can take notes about how your brain is changing the way you look at software engineering. I'm also recommending that you keep a notebook handy also so that you can paraphrase what you're thinking while going through the book and just keep track of the thoughts.

One general word of caution: if you think the concepts are going way over your head, go back to the basics and the fundamentals. This is one general rule that you'd like to go back to when reading this book. If you don't understand one part, do your research and go back to the material -- it generally helps if you have time to actually digest it and focus as you read it.

First, the general style of the book is that of a textbook. There are no anecdotes and personal notes from the authors -- it feels like you're reading a collection of papers and building up a very grand case for the techniques and concepts to be shared. Alexander and Paul do a great job of keeping the material terse and yet be expressive enough to keep a reader engaged.

Second, the subject mater and tone is serious. This book does a great job of being timeless in its treatment of the subject. This is as clear cut as you'd want to get when you're dealing with the fundamentals of programming and software engineering. The authors keep it very serious and very "matter-of-fact" throughout the book and it drives the point that this book is definitely something that everyone should be able to understand and benefit from. They keep to facts and the subject very effectively without being clever about anything.

Third, the C++ they use is just the subset of the whole language; if C++0x would contain Concepts (which it won't as of the most recent developments) then the code in the book are the definitive examples of how to use the proposed feature set. Having said this, the authors provide an appendix that deals with the syntax used and the features you can leverage in C++ to make the code compile without Concepts support from the compiler.

Having done the preliminaries, I'll go into some of the details in the book. In part 2 I will attempt to apply the concepts in the book, while in part 3 I will attempt to construct a logical thesis on how to approach application development using the techniques taught in the book. In this part I will highlight some of the important foundational concepts put forth by the book in three sections: Concepts, Composition, and Generalization.

Concepts

Although C++0x won't contain Concepts, the book starts out with laying the foundations of types and values then graduates to Concepts. After laying the groundwork down for the foundations, the concept of Concepts wherein you describe a meta-class (a class of Types) that abide by a set of rigid qualifications are then described. Essentially, they introduce the concept of a Concept by looking at data, classes (types), and then by creating a generalization of types that model a Concept.

This clear treatment and discussion of Concepts is one of the most if not the only definitive text I've come across that deals with the subject matter. Short of the book on Generic Programming, the concise and matter-of-fact approach to describing and defining Concepts is the best I've read bar none.

What the whole book then depends upon is the notion that a higher level (or more generic) treatment of classes instead of dealing with a hierarchical view of types (as in Object Oriented Programming) by defining the requirements on a type -- that it supports certain operations applied to the type, that there are certain axioms that hold against a type, and that there are consistent complexity requirements on the algorithms that deal with instances of the type -- that we can write generic, efficient, and effective algorithms relying on types modelling Concepts. The Type Theory aspects relevant to generic programming become evident if we draw parallels between Haskell Type Classes and C++ Concepts; we can then begin to see how transformational and important Concepts can be for sufficiently complex software engineering projects.

Composition

One of the big things that the book promotes is the approach to composition: that higher level or higher order functions can be (and most probably should be) composed of smaller specific functions. The type of composition is not very far from the functional programming concept of composition, but rather the notion that you solve bigger problems by solving other problems with relatively smaller solutions.

The kind of composition being promoted by the book is the generic kind where once you define and operate with Concepts, that the algorithms that you compose are then generic enough to be applied to any instance of a type that models the Concepts the algorithm was meant to work with. This is very powerful because this means that if you have an algorithm that deals with a broad range of types instead of just types that derive from a certain base, this increases the re-use value for the algorithms you implement (or the library you've written).

Much like how bottom-up programming is meant to make complex tasks easier to solve by solving smaller tasks first, the composition approach applies very well to complex application development projects. The book gives you a good and clear idea of how to go about doing this in your own project albeit in a subtle manner that lets you formulate the solutions by showing the techniques and allowing you to run away with it.

Generalization

What the book doesn't do is come straight at you with generalizations, but rather it deals with foundations and specifics first before generalizing. The reasoning behind this is like with Set or Group Theory, you can only extend to a greater set by defining rules and building upon predicates that apply to an individual. What the book teaches is that you first go specific then get generic progressively.

The book also doesn't first show you what the generic "formula" or "technique" is, but rather it deals with a specific area first and the solutions that pertain to that area and then extends it to a more generic setting. By building on previously developed concepts and techniques readers get a very good example of how to correctly generalize -- by using mathematical logic and foundations and different techniques of proof at an abstract level to reason about the solution.

Just like how the math and computer science majors are taught in discrete mathematics, your generalization should always apply true for the specific cases covered by the generalization. Unless you can prove that your generalization is logically sound, then you don't have an assurance that your generalization is correct -- therefore it would make your generalization invalid. Knowing this and applying it to software engineering is nothing short of brilliant.

Parting Shots

So if you've read through this (lengthy) post up to here, I'll say it once more: get this book if you're looking to improve the way you do software engineering and programming. If you care for the art/science of programming and problem solving with programming languages, pick this book up and I'm positive you will come to the same conclusions as I've reached. It took me a while to write this because mainly I wanted to do the book justice by doing an in-depth look and understanding how important this book is to the field.

More to come in the next parts where I attempt to apply the concepts and techniques promoted by the book in real-world application development projects.

The author would like to thank Pearson Education for sending a copy of this very important piece of literature for review. For questions and suggestions, please post in the comments or send email to me@deanberris.com or dean.berris@cplusplus-soup.com.

Update: Minor typographical edits from "discreet" to "discrete" mathematics.

Bloom Filters

2009-06-08T05:42:00.000-07:00

During the weekend I was fascinated by a simple utility called a Bloom Filter. From the Wikipedia entry:

The Bloom filter, conceived by Burton H. Bloom in 1970, is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Elements can be added to the set, but not removed (though this can be addressed with a counting filter). The more elements that are added to the set, the larger the probability of false positives.

So I tried implementing my own generic Bloom Filter in C++ and submitted it to the Boost C++ Libraries. My email went a little something like this:


During the weekend, I got acquainted with and excited about Bloom
Filters and the utility of such a data structure. I then proceeded to
look at generic implementations of a bloom filter and I thought about
implementing one myself instead as a simple exercise.

Attached is what I came up with which I'm submitting as a library for
review (and uploading to the vault). Also attached is a sample program
which uses the bloom_filter.

This then led to a few responses, and now I'm proud to say that my implementation can now be checked out and tracked from Boost Sandbox! The URL to the subversion repository is:

https://svn.boost.org/svn/boost/sandbox/bloom_filter/trunk/

Have fun with the library, and I would definitely like to know what you think about it!

MapReduce without using MapReduce?

2009-05-27T02:48:00.000-07:00

Recently I had the chance to work on a few distributed parallel computing solutions for data analytics. One of the interesting choices I've had to make is whether to use the MapReduce computing model (using Hadoop) or whether to come up with an adhoc way of doing it.

At first it wasn't a very easy decision to make the forces I was facing were:

I haven't had experience working with Hadoop before, and the last thing I did with it is the sample program that comes with it. Although I can understand that it is easy to use, there are other operational issues to consider.
Hadoop requires that you put the data into the DFS and while this is convenient to deal with in a program, operationally that's usually not an option. Imagine dumping data from a huge (production) database and then massaging it into a format that you can deal with through Hadoop.
The MapReduce model works as a parallel computing model and is simple enough for the kinds of analytics I intend to do. However, implementing a framework from scratch seemed like a daunting challenge especially since there was already an existing solution in Hadoop.

Given the above thought process, I started looking elsewhere. One of the first things I turned to was the Boost C++ Library and remembered that Boost.MPI is available to be used. Since I was already using Boost in my projects, it seemed a logical choice to stick with it.

I then proceeded to install OpenMPI which Boost.MPI had been tested against. At first I was skeptical whether it would be possible to use it in a data-parallel solution granted that it is a message passing implementation. Then I wrote the code and found out that it was definitely possible to do MapReduce with MPI.

The MapReduce Pattern

Basically there is a simple pattern behind the MapReduce computing model. There are two steps: the Map step and the Reduce step. In between you have shuffles, etc. but the gist is that you need a way to map computation to data, and the results of the individual computations are then reduced to yield the answer. It's basically a divide-and-conquer approach to dealing with data in parallel.

If you were doing this with MPI, you'd start with the 'scatter' function call. In Boost.MPI, you'd have some code like this:

vector<int,int> ranges;
// populate ranges
pair<int,int> range;
scatter(world, ranges, range, 0);

Once you have your ranges scattered, you then deal with the data you get in the individual nodes. Your ranges may represent bounds in the database, maybe a part of a file shared accross the cluster, or just a range of numbers. This is the easy part, now the challenge becomes the reduce part.

With that you need to think a little bit about what kind of data structure you're going to be transmitting from the worker nodes to the root node -- and how to actually "merge" the results to yield what you need in the end. Once you're settled with that, you can then implement the merge (or the reduction step) as a function object. In the following example I implement a merge of maps of counts as a functor:

struct merge_maps {
map operator() (map<int,int> l, map<int,int> const & r) {
l.insert(r.begin(), r.end());
return l;
}
};

namespace boost { namespace mpi {
template <>
struct is_commutative<merge_maps,map<int,int> > : true_ {};
}}

We then use it with the Boost.MPI 'reduce' implementation:

map<int,int> partial_map; // partial from the nodes
map<int,int> final_map; // the "merged" map
reduce(world, partial_map, final_map, merge_maps(), 0);

After this step, you basically have the final results in the 'final_map'.

And that's it! You have an adhoc MapReduce implementation using Boost.MPI!

Of Course...

This isn't really MapReduce, but with all this talk about parallel computing and massively parallel distributed computing you can say that there are many ways of addressing the issue using alternative technologies.

It'd be nice to know how you deal with your parallel distributed computing needs.

Function Input Iterator (Boost Submission)

2009-04-10T09:42:00.000-07:00

A couple of weeks ago I've submitted an implementation of a "Function Input Iterator" that builds upon the implementation of the generator iterator adaptor. The function input iterator implementation uses a separate state object that tracks the state of the iterator. The state encapsulated by the iterator is used to compare whether two iterators are equal.

The library has been submitted as an additional library to the Boost.Iterators library and is part of the Trac ticket #2893. From the ticket submission, the following details are then quoted.

Simply put a the function input iterator implementation wraps a nullary function object and allows for bounded iterators using an embedded state variable. The use case is for something like the following:
struct generator {  typedef int result_type;  generator() { srand(time(0)); }  result_type operator() () const { return rand(); } };  using namespace std; using namespace boost;  int main(int argc, char * argv[]) {  generator f;  copy(    make_function_input_iterator(f, infinite()),    make_function_input_iterator(f, infinite()),    ostream_iterator(cout, " ")    );  return 0; } 
And if you don't want an infinite range, you can simply bound it:
copy(   make_function_input_iterator(f, 0),   make_function_input_iterator(f, 10),   ostream_iterator(cout, " ") );

GCC C++0x Features Exploration

2009-03-15T15:39:00.001-07:00

In the interest of exploration, I played around one Sunday afternoon with the C++0x features available from GCC 4.3.2 [1] -- to better see what I can use at work when I migrate the application I'm writing from the C++98 standard to the C++0x standard. To gauge the differences, I tried implementing a simple stream-fusion approach to simultaneously compute the the mean, minimum, and maximum in a collection of integers.

For a little background, let me try and describe what stream fusion is briefly. Simply:

Stream Fusion

Technique of removing multiple loops over a container and performing the required computations in a single pass. This technique is meant to minimize the number of loop iterations hopefully to improve the performance of an application. [2]

Stream fusion is a good way to improve performance in applications that deal with huge containers and that perform multiple passes on the container to do multiple things. Sometimes the technique is a little more tideous to apply than the naive solutions but when performance matters it's something you can try.

Let's look at a naive version of getting the mean, minimum, and maximum of
an array of integers:

 
int numbers[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int min = min_element(numbers, numbers + 10);
int max = max_element(numbers, numbers + 10);
double mean =
    static_cast<double>(accumulate(numbers, numbers + 10))
    / 10.0
    ;

Here, we have three loops that compute the mean, minimum, and maximum from
the same container. From the way it looks, it's just fine that we have three loops since we just have 10 elements in the array.

But what if for example we were reading the integers from a file and we have millions of integers to deal with, then going over the file three times doesn't seem like a viable solution especially if performance matters. At that scale of the problem, you can count on performance being a big deal. It also doesn't make sense for us to keep everything in memory either because the data may not fit in memory or the data actually comes from an input
iterator bound to a stream.

Stream fusion then becomes more obvious because the reason it's called stream fusion is because usually the computations are associated with going through data that comes from a stream. Going "back" in a stream usually doesn't make sense or performance-wise is very costly, so we try and keep
the computation going as we consume items in the stream to save on space consumption and to get the performance enhancements.

Stream Fusion, C++98 Style

So first thing we try is to do stream fusion with the C++98 standard. We'll use the TR1 tuple implementation that comes with GCC and the standard algorithms as well as a special computation type we'll callmean_min_max. First, we'll think about how to simultaneously compute the mean, minimum, and maximum.

To do this, we'll have to be able to keep track of the following variables:

minimum so far : we'll call this MIN

maximum so far : we'll call this MAX

total so far : we'll call this ACC

count of elements dealt with so far : we'll call this COUNT

What we want to do is for each iteration of the loop, we'll look at one element and see if it's the minimum so far, maximum so far, add it to ACC, and increment COUNT. To do this in functional programming means we'll have to rely on a left-fold and make mean_min_max a binary function object taking a state variable and an element as the respective arguments to the function operator overload.

To make it as generic as possible, we implement mean_min_max as a polymorphic function object type. We come up with the C++98 compliant version of mean_min_max below:

 
struct mean_min_max {
    template <class T, class U>
         T operator() (T const & state, U const & element) const {
            enum { MEAN, MIN, MAX, ACC, COUNT };
            return make_tuple(
                // This is the running mean...
                static_cast<double>(get<ACC>(state) + element)
                / static_cast<double>(get<COUNT>(state) + 1),
 
                // This is the minimum so far
                (get<COUNT>(state) == 0)?
                    element
                    : (get<MIN>(state) > element)?
                        element
                        : get<MIN>(state),
 
                // This is the maximum so far
                (get<COUNT>(state) == 0)?
                    element
                    : (get<MAX>(state) < element)?
                        element
                        : get<MAX>(state),
 
                // This is the new value of ACC
                get<ACC>(state)+element,
 
                // This is the new value of the COUNT
                get<COUNT>(state) + 1
                );
        }
};

We can then use this as the fourth argument to the call to accumulate while we use the tuple (0.0, 0, 0, 0uL, 0) as the initial state of the left fold:

 
double mean = 0.0;
int min = 0, max = 0;
tie(mean, min, max, ignore, ignore) =
    accumulate(numbers, numbers + 10,
            make_tuple(mean, min, max, 0uL, 0),
            mean_min_max()
            );

If we notice the call to accumulate we'll see that there's nothing special about this construct. Sure, we've accomplished what we want to accomplish with just the C++98 standard. You might be wondering what the problem with the above implementation could be, and in the next section I'll detail what those issues are.

Stream Fusion, C++0x Style

Now in the above solution, we have quite a number of inefficiencies that aren't readily obvious. First of these are the inordinate number of copies we'll be doing when returning the tuple from mean_min_max. In C++98 we're stuck with copies when returning data from functions. Unless we use something like an auto_ptr<...> as a return and use the heap, we don't have move semantics.

But in C++0x, we now have support for move semantics as an addition to the language. We rely on two features: r-value references and the move library function. So first, let's talk a little about what r-value references are and why they're important.

R-Value References

R-value references are denoted by && right after a type. This is used to denote that only temporary values and literal constants can be referred to by an r-value reference. These r-value references actually take on the storage of the temporary value thereby not needing to allocate new storage for a new variable. It is then said that the temporary is 'moved' from the original scope to the new scope without relying on copies and additional temporaries. [3]

With a C++0x implementation of the mean_min_max we can change a few things that would allow the solution to minimize on copies:

 
struct mean_min_max {
    template <class T, class U>
         T && operator() (T const & state, U const & element) const {
            enum { MEAN, MIN, MAX, ACC, COUNT };
            return move(
                    make_tuple(
                        // same as before
                        )
                   );
        }
};

Here we change the result of the function call operator to be an r-value reference of type T and that we should move the temporary created in the body to be returned into the storage of wherever the result is to be put. Instead of the compiler calling the copy constructor of the tuple, it then relies on the move constructor (or a constructor that takes a T && as
the sole argument instead of a T const &) to initialize the values of the appropriate members.

If you have enough iterations and are dealing with heavy objects, r-value reference returns and move semantics will save you a lot of unnecessary copies. The less copies you make, the better the performance you get.

Another chance where we can use this technique is at the call to accumulate where we move the initial temporary tuple instead of letting the compiler copy the tuple for us:

 
double mean = 0.0;
int min = 0, max = 0;
tie(mean, min, max, ignore, ignore) =
    accumulate(numbers, numbers + 10,
            move(
                make_tuple(mean, min, max, 0uL, 0)
            ),
            mean_min_max()
            );

GCC and C++0x Lambda's

Unfortunately, GCC 4.3.2 doesn't yet support C++0x Lambda's [4]. I haven't checked yet if GCC 4.4.x [5] already supports it, but since lambda's aren't supported by the compiler I was testing, I'm not yet able to show a solution to the problem without testing it. However, if your compiler already supports the C++0x lambda's, you can go ahead and move body of the mean_min_max function into a lambda like this:

 
double mean = 0.0;
int min = 0, max = 0;
typedef tuple<double, int, int, unsigned long, size_t> accumulator_tuple;
tie(mean, min, max, ignore, ignore) =
    accumulate(numbers, numbers + 10,
            move(make_tuple(mean, min, max, 0uL, 0)),
            accumulator_tuple &&
            [](accumulator_tuple & const state, int const & element) {
                enum { MEAN, MIN, MAX, ACC, COUNT };
                return move(
                    make_tuple(
                        // same as before
                        )
                    );
            }
            );

If you're just making throw-away functions, lambda's are an attractive approach to keep the context of the computation closer to the point where you need the computation to be done. This is great if you are adept at using the STL algorithms and are comfortable with functional programming principles.

In this example the Lambda's noticeably don't have parametric types in the construction. This is because C++0x are monomorphic -- which means they only have one form. This makes C++0x lambda's a little less flexible compared to hand-coded function objects that have template member overloads of the function call operator (like our version).

More to Come

In this article I've highlighted important new features of C++0x which should allow developers to be more productive and be able to produce better performing code with R-value references, move semantics, and lambda's. There are a handful more new features upcoming at the language level which I would like to explore as well in upcoming articles.

All in all, C++0x allows you to write powerful and performant code that when combined with powerful idioms (like stream fusion) yields superior solutions. Even though the C++98 standard allows you to write good code, C++0x just allows you to write better code in more ways than one.

[1]	GCC 4.3.2 http://gcc.gnu.org/gcc-4.3/

[2]	Stream Fusion http://www.cse.unsw.edu.au/~dons/papers/CLS07.html

[3]	R-value References http://www.open-std.org/JTC1/sc22/wg21/docs/papers/2004/n1690.html

[4]	Lambda's http://en.wikipedia.org/wiki/C%2B%2B0x

[5]	GCC 4.4.x http://gcc.gnu.org/gcc-4.4/changes.html

New Specification Library Release (0.2.1)

2009-03-09T04:20:00.000-07:00

Recently, a few people have asked about my C++ implementation of a Behavior Driven Development library which was previously hosted at the Orange and Bronze website under my home directory. Apparently, there were a few changes made to the O&B site which disallowed my serving of the file releases from there so I thought about moving the file releases to my own domain. Having said that, there are a few things which have happened since the move, and I'm documenting those changes (and the new releases) in this blog entry.

If you haven't checked the site recently, I've added a dedicated file storage location for the Specification Library (which I've unimaginatively named as spec-cpp). From there you can get the latest releases of the library as well as get a sneak peak into what the library offers and supports.

The latest version line is the 0.2.x version which adds early container inspection support in the form of statements like:

container(some_container).should.contain(value);
container(some_container).should.not_contain(value);
container(some_container).should.not_be_empty();
container(some_container).should.have_size(value);

More releases along the 0.2.x line will concentrate on inspecting STL and STL-conformant containers. As of the moment I develop the library on my free time and release all the source code as open source using the Boost Software License.

This release has been tested against Boost 1.38.0 using the GCC 4.3.2 compiler in Linux.

If you'd like to contribute or just get the latest and greatest version of the code, please head on over to the github repository at http://github.com/mikhailberis/spec-c--.

This blog post is cross-posted in deanberris.com and blog.cplusplus-soup.com -- if you have questions or comments regarding the library, please send them to me@deanberris.com.

Update: Adding correct link.

Update: BDD in C++

2009-03-05T00:31:00.000-08:00

Because of recent changes in the Orange and Bronze Software Labs website, I had to move the source code for the Behavior Driven Development library that I wrote in C++ to a different host. Now, you can download the source code from http://www.deanberris.com/spec-cpp/.

It's been a while since this library has been used (last used it three years ago) and it would be nice to actively develop it again someday. Hopefully I can find the time to do it because it's a nice concept to play around it.

Have fun, and I hope this helps!

Update: The Git repository is now hosted at Github, http://github.com/mikhailberis/spec-c--/tree/master and adding link to O&B website.

Intel Parallel Programming Talk: Featuring My Question

2009-03-03T19:13:00.001-08:00

Recently, I sent a question to the Intel Parallel Programming Talk podcast about auto-parallelization at the compiler level. Yesterday, the episode aired and my question was picked and answered!

You can listen to the episode online here.

FP and C++: A Left Fold Fibonacci Implementation

2009-03-03T00:58:00.000-08:00

So today, I was tinkering around with doing functional programming in C++ and thought about implementing one of the traditionally recursively implemented Fibonacci sequence generator. The classic problem is how would you write a function "fib" such that given a parameter "n" it will yield the nth fibonacci number.

The traditional implementation (recursive) would look like this:


unsigned long fib(int n) {
  if (n <= 1uL) return 1uL;
  return fib(n - 2) + fib(n - 1);
}

So that's not particularly surprising nor efficient (space or runtime-wise). So we then think about how we can optimize it. Some people will think about memoization where we'll remember previously computed fibonacci numbers so the next time we compute it we'll benefit form cached values. That's alright because it amortizes the running time as you call the fib function more and more.

If you don't know it yet, there's actually a way to get fibonacci numbers with an linear (O(n)) running time algorithm. It's no fun implementing a loop ourselves, and to show that it's possible in C++, we use the existing numeric algorithm 'accumulate' which behaves precisely as a left fold.

First, we need to implement the function object that will actually perform the binary operation that will yield the accumulated value. The good thing with the binary function object we're going to write is that the left parameter can have a different type from the right parameter. We can then use this to return a 'state' variable that is preserved as the left parameter of the next invocation of the function object.

Let's see the code as we would write it:


struct fibonacci_folder {
  template <class T, class U>
  pair<U,U> operator()(pair<U,U> const & state, T) const {
    return make_pair(state.second, state.first + state.second);
  }
};

So given the above implementation, the first (or left) parameter to the call to the fibonacci_folder function object is a pair which we can call the state object. This state object carries two values which are the 'previous' and 'current' value in the computation being used by the fibonacci fold. The second parameter though is ignored in this computation.

If we can visualize it somehow, we can start with just two numbers (0,1). As we call fibonacci_folder()( (0,1), ignored ), it will return a pair (1, 1). The next call will become then fibonacci_folder()( (1,1), ignored ), and yield (1, 2). You can continue this as long as we're iterating.

Next thing we need to do is setup our boundary iterators. If you notice, accumulate requires that you have forward iterators as the first two arguments giving the bounds upon which the function F(accumulated, *iterator) where F is the function object, accumulated is the state, and iterator is a forward iterator. We can do this simply with a Boost.Iterator called a counting_iterator<T> which simply yields a value of type T. We can then see that we can set up the left fold using accumulate with the fibonacci_folder this way:


unsigned long fib(int n) {
  return accumulate(
    make_counting_iterator(0),
    make_counting_iterator(n),
    make_pair(0uL,1uL),
    fibonacci_folder()
    ).second; // we want the "current" value in the state
}

This now allows us to compute the nth fibonacci number in linear time using a left fold implementation.

Do you know any other interesting algorithms that are effectively converted to and are more efficient as folds instead of recursive or simply loop-based implementations? Do you think writing in this style is more elegant than simply using imperative programming principles?

I'd love to know what you think!

Alternate Data Stream

2009-02-16T00:22:00.000-08:00

So recently I've been involved with quite a number of little projects (personal and tech related) that I would like to share with the readers of this blog. First, a backgrounder on the situation.

I've always been thinking about revamping the C++ Soup blog and adding more content in the form of audio/video and maybe hosting a forum of sorts. In the quest to get this process moving, I tried out Square Space which provides a nice interface for creating your own website without having to write a single piece of code. So far, my experiments have yielded the move of my personal blog to a new domain (deanberris.com) and a new host.

In that process, I would like to open up the topic to you and ask what would you like to see more of from C++ Soup. I have my own list of things I'd like to put up which I'm listing down here:

A weekly/monthly podcast of interesting C++ discussions -- featuring book and library authors.
An FAQ section with specific tutorials dedicated to specific topics -- specifically I plan to collect idioms and good ideas/snippets separated out from the blog posts.
Industry news and opinion articles -- news specific to C++ and related technologies like parallel high performance computing, gaming, etc.
More authors and contributors -- I may be opening up C++ soup to accept outside contributors and other authors to contribute fresh content to the site.

With regard to a podcast, I recently took part in the pilot episode of the Pinoy Tech Podcast* featuring some prominent Internet figures from the Philippines (namely Jerome Gotangco, Miguel Paraz, Jon Limjap, and Aileen Apolo). I felt really confident about being part in one that I'm seriously considering making it part of my regular internet activities -- and maybe developing a C++-centric podcast of my own. Hopefully I can get that started sooner than later.

* NOTE: The podcast uses some Tagalog language in the discussion, although most of the discussion is spoken in English.

So I would like to know what you think about the plans -- please feel free to post comments so that I can consider what you think. If you prefer email, you can send them to dean.berris@cplusplus-soup.com or me@deanberris.com.

Update: Adding tags to the post.

Auto-Vectorization and C++

2009-02-11T18:42:00.000-08:00

It's been a while since I last wrote about parallel programming and C++ and recently I've been really seeing quite a lot of articles about the subject. As the days pass by it seems that C++ becomes more and more relevant in the multi-core and parallel computing/programming scene and with the upcoming new standard the renewed interest in the subject is more visible even in online discussion.

Today, I just saw in my reading list an article on auto-vectorization posted on Dr. Dobb's Journal that's available in the recent Intel C++ Compilers. It's interesting that there apparently are quite a lot of things the compiler can do for you in between making sure that your code is syntactically correct and translating it to machine code.

The Intel compiler has a feature that can make some applications run much faster -- auto-vectorisation. With a flick of the switch, some code can be sped up significantly. A number of times I have seen programs run much faster just by using this option without changing a line of code. With vectorisation, the compiler uses a set of advanced Single Instruction Multiple Data (SIMD) instructions, which ornate most modern CPUs.

from "I've Fallen In Love With the Vectoriser".

I personally can vouch for the effectiveness of leveraging the processor's performance in mission critical performance-sensitive applications. I however had been using the tree vectorization optimization that's been present in the GCC compiler since version 4.1.x (through the -ftree-vectorize option).

Vectorization talks about the technique of transforming code to work in a vector processor -- that is, processor that can perform a single instruction on multiple data (SIMD) and hence the root of the SSE instruction set (SSE stands for Streaming SIMD Extensions). This makes repetitive mathematical instructions that can be performed in parallel to be done in fewer instructions than it would normally take if they were done in sequence.

To those that have read about parallel computing in the early days (around the '70s or '80s) will know that there has been a wealth of research dealing with how to do parallel programming in many different types of computers. Recently, these techniques seem to be coming up again in the midst of the move to parallel programming -- and this is to no surprise. Apparently the evolution from sequential processors (Von Neumann architecture) to parallel processors (systolic arrays, hypercubes, and meshes) translate to even the commodity processors of today.

Let's take the vector processors: it might be a surprise to some to find out that the GPUs in the modern day graphics cards are actually SIMD processors and that it leverages research that has been done on the parallel computing field. This is the reason why it can perform blazingly fast computations on the fly to generate life-like 3D images at high frame rates. This is also the same reason why the cheapest way to get your hands on a supercomputer today to perform repetitive mathematical computations on large data sets is to get a handful of these GPUs together and program to utilize these processors.

Because of the popularity of these SIMD instruction sets, the modern day multi-core processors actually have a small vector processor embedded that knows how to do practically the same thing albeit at a smaller scale. Actually, this trend has started earlier in the higher performance single-core processors (as early as Pentium III). The first application was for improving processor performance for games that require these sorts of instructions to make certain things feasible.

In the case of the hypercube architecture, you can look at the modern day multi-core processor as a simple case of a 1-dimensional hypercube of processors (dual core) or 2-dimensional hypercube of processors (quad core). In the early days of the hypercube architecture, each processor had dedicated communication channels to each other and did not share data. Today, you can look at multi-core processors as an evolution of this early-day hypercube architecture but with a shared memory space. Starting with the current and next generation many-core processors though, you'll see NUMA and have each processor be responsible for managing certain memory modules.

This is all interesting from the hardware architectural perspective, but how does it concern C++? For instance the compilers which have greater insight into the target architecture of the machine on which you'll be running your code will be able to leverage the available instruction sets and generate more efficient code. Knowing the architecture of the processors will also give programmers greater insights about how to leverage the available cache, layout, and memory management characteristics of the system to write effective high-level code in a guided and informed manner. Certain decisions and predictions can be made through deliberate examination of the available technology and tools at your disposal as a C++ programmer (threads, synchronization primitives, memory usage, etc.).

There's more to come in the coming months and years ahead as we start getting more and more immersed in the reality that multi-core and parallel programming is the future. I forget where I read/heard it before, but this is the classic case where "Resistance is Futile" would definitely apply.

Programming: Principles and Practice Using C++

2009-02-01T09:42:00.000-08:00

I’ve been lucky enough to be contacted by Pearson Education (Addison-Wesley) and given a review copy of Bjarne Stroustrup’s latest book titled Programming: Principles and Practice Using C++. In the past few days, I’ve been reading this book of considerable size chock full of knowledge poured out directly by the creator of C++ himself.

If you haven’t read a book by Bjarne yet be prepared to be treated to well-thought out examples and a very expressive presentation of concepts and techniques. The book is an easy read especially if you’re new to programming and want to really learn how to think like a programmer. The overall presentation approach that the book takes is very light and the exercises are aimed definitely for the novice.

Advanced developers will definitely gain lots of insights into how Bjarne thinks about programming—and how potentially you can present programming to novices. If you’re working in a team with junior developers, this book is a great addition to the library. If you’re a teacher teaching introduction to programming, this is a great reference and textbook because you get to teach/learn programming with a considerably powerful real world programming language.

The 27 chapters of the book are broken down into four logical parts. The first part is aimed at developers looking to pick up programming from the ground up dealing with foundational issues like variables, classes, functions, and programs in general. The second part is aimed at dealing with real-world issues dealing with input and output and how you can deal with the data using various constructs provided by the C++ language and libraries (like the Standard Template Library). The third part deals more specifically with issues of working with the Standard Template Library in greater detail particularly with the data structures and algorithms. Part four is a survey of the kinds of things you’ll be encountering when you go into professional programming—as well as one chapter on the relationship between C and C++.

I particularly like the way Bjarne adresses the reader as an active participant in the learning process. He puts in as much detail as he can without belaboring a point too much. His examples are interesting and representative of the kinds of challenges programmers will be facing in the real world but not too complex to be a hindrance to the learning.

This is the book I wish I read while I was in college studying computer science—and this is a book I will really recommend to educators and students alike looking for a good foundation book on programming and C++. If you’re thinking of learning C++ from scratch, invest in this book and I guarantee you will not be disappointed. If you’re a freshman or sophomore in college looking to a career in programming after college, pick up this book and I assure you that you will learn many gems from this book.

I definitely think the industry is in need of a good book on the “how-to” of programming using a powerful real world language—and Programming: Principles and Practice Using C++ can definitely be that book.

Parallel Computing: Microsoft or Intel

2009-01-15T00:22:00.000-08:00

Until recently, I personally didn't give Microsoft (R) much props for parallel computing research and development. I always equated their efforts in the developer community to desktop development productivity tools (which are top notch by the way) and considerably "unreliable" products (like Vista).

However nowadays it seems like they are becoming really serious with dealing with the multi-core and concurrent development movement. I see lots of room for improvement, but I think I would be convinced finally when Visual Studio 2010 with better C++0x support and better concurrent programming tools come from their well-guarded gates. Some of the evidence that's starting to sway me towards giving big MS more credit is shown in the smart and insightful discussion between hotshots from within Microsoft in this Channel 9 video by Charles on Parallel Computing in Native Code: New Trends and Old Friends.

I personally give Intel a lot more credit for their superior C++ compilers for their platform and the widely-accepted (not to mention Open Source) Threading Building Blocks. In a recent video about OpenSolaris and Core i7, I see Intel really playing well with the open source community by doing lots for the OpenSolaris operating system and making it work better for the Core i7 (codename Nehalem) micro-architecture.

Looking at the situation as a semi-outsider, I think how Microsoft and Intel are playing the industry is very complementary -- Microsoft has great tools for developing software for their platform that work on Intel's hardware while Intel works with Microsoft by making sure Windows works well on Intel hardware. It's hard to miss how these two big players in C++ will definitely shape how the future of programming will look like especially with a new low-level architecture and better-looking and productivity-enhancing tools.

Now what about the competition? Sun's play into the High Performance Computing and Cloud Computing market is showing how they want to play at a higher level than low-level concurrency and better developer tools. Although I know Sun has been offering x86-based servers, I still think their focus on a higher level is both good and bad. Good because they're trying to take a foothold in a vigorously emerging sector of the industry. Bad because that means they might be relying on other people's efforts (Intel and the open source community) to advance technology.

At any rate I see big blue IBM being the most to gain in the field -- their mix of research and development for hardware and years worth of expertise in the consulting business is like a good 1-2 punch for staying relevant in any market. So while I see Microsoft and Intel pushing the envelope with C++ and parallel computing, I see lots of other people and companies getting most of the benefit.

Maybe someday I can get in on the action too providing much a crucial service to those who need it. But that's not in my horizon yet as far as I can tell.

What do you think about the current software and hardware movement towards parallelism?

C++0x Atomics and Concurrency Woes

2009-01-13T01:00:00.001-08:00

If you've been through Java programming before, you'd know that one of the nice features would be the clear semantics for concurrency of the volatile keyword. If you wanted to say that a variable may change at any given time but be assured that changes to it would be atomic, you'd name it volatile. Not only that, if you wanted to make sure a method was executed atomically within the virtual machine, you'd mark it synchronized.

Until recently C++ lacks a volatile keyword that makes variables behave like atomic variables. The C++ volatile keyword is a directive to the compiler that says "hey, you can't assume anything about the storage/location of this variable -- so don't try and deduce and optimize away changes to this one". Herb Sutter has recently posted a summary of the explanation to the C++0x standard atomic template in his latest installment titled aptly "volatile vs. volatile".

If you look at illustrated table comparison between the semantics of Java/.NET's volatile keyword and C++'s volatile keyword it would be easy to see why people (like me included) are usually confused with what "volatile" is really about. Thankfully, C++0x has the atomic template to give us C++ developers the capability to use the same volatile semantics protecting types from unsynchronized access. Not only does this allow people to write essentially lock-free (in the normal sense using considerably heavy-weight mutexes) code and get the performance benefits of being really close to the metal.

Much is to be said about the upcoming C++0x implementation and what's really exciting for me are the concurrency-specific changes to be made part of the language and the standardization of libraries pertaining to concurrency -- threading, futures, among many other things. Right now it's a waiting game to find out who among the many vendors out there will be able to come up with reasonably compliant C++0x compilers first, and I for one am going to be trying out the new features of GCC 4.3.x to get a feel for C++0x for myself.

In your case, how will the next C++ standard affect the way you do concurrency-aware programming? Do you think the new features will really be helpful or do you think there are still many things lacking? I'd love to hear what you think!

C++0x Threading Library Released

2009-01-10T22:14:00.000-08:00

Recently, Anthony Williams (author of C++ Concurrency in Action which I also reviewed recently) has recently released version 1.0 of his threading library that is C++0x compliant.

From his blog post about the release, the following is just a list of features available from the library:

The just::thread library is a complete implementation of the new C++0x thread library as per the current C++0x working paper. Features include:

std::thread for launching threads.

Mutexes and condition variables.

std::promise, std::packaged_task, std::unique_future and std::shared_future for transferring data between threads.

Support for the new std::chrono time interface for sleeping and timeouts on locks and waits.

Atomic operations with std::atomic.

Support for std::exception_ptr for transferring exceptions between threads.

Special deadlock-detection mode for tracking down the call-stack leading to deadlocks, the bane of multithreaded programming.

The library works with Microsoft Visual Studio 2008 or Microsoft Visual C++ 2008 Express for 32-bit Windows.

from just::thread C++0x Thread Library V1.0 Released.

I'm not sure whether this will be also ported to become Boost.Thread (which Antony also maintains) but I do know that there are currently two versions of a futures library implementation that's ongoing in the Boost C++ Developers Mailing list.

You can get your copy of just::thread commercially from the order site.

Holiday Greetings

2008-12-26T11:32:00.000-08:00

I know it's already days past but I just want to wish everyone subscribed to and following the blog "Happy Holidays!".

I'm looking forward to a productive and very interesting 2009!

Windows 7 : A Game Changer?

2008-12-12T02:59:00.000-08:00

Doug Holland (Intel) posted a coverage of this Channel 9 talk about the upcoming Windows 7 operating system. I personally am not a big Microsoft fan, but I appreciate that the company is still focused on the goal of delivering innovative and (arguably) technically superior products. Mark Russionovich was interviewed by "Charles" on Channel 9, and here's an excerpt on the details of the discussion:

... One very important change in the Windows 7 kernel is the dismantling of the dispatcher spin lock and redesign and implementation of its functionality. This great work was done by Arun Kishan (you've met him here on C9 last year). The direct result of the reworking of the dispatcher spin lock is that Windows 7 can scale to 256 processors. Further, this enabled the great Landy Wang to tune the Windows Memory Manager to be even more efficient than it already is. ...

from Going Deep > Mark Russinovich: Inside Windows 7

While watching the video it's amazing how forthcoming and how much detailed that kernel architect of Windows is willing to go regarding the development process and the changes that were made. I wouldn't have expected this sort of openness from an employee of a company started by Bill Gates who practically made sure things in Microsoft were kept proprietary.

Enough about that commentary, the technical details are very interesting indeed. It makes me think about how I approach the operating system kernel when I write multi-threaded applications. Although I don't program on the Windows platform I see how changes in the Operating Systems will definitely play a bigger role in the future when people get their hands on machines with many cores available.

I definitely look foward to having the equivalent of "user mode scheduling" in Linux or if just something emulated to have work-stealing wait()'s to maximize thread time slices and minimize waiting on highly concurrent applications. Server applications running on the Windows platform will definitely get a big boost just from the description of what the changes in store for Windows 7 when it does come out.

Does anybody know if there's something similar happening in the Linux kernel space?

Update: Added missing link to reference article.

OpenCL : Shifting Tides

2008-12-09T21:31:00.000-08:00

While going through my reading list, I came across a news article from Dr. Dobb's Journal about the release of the OpenCL 1.0 specifications.

From the Khronos Group article:

OpenCL supports a wide range of applications, from embedded and consumer software to HPC solutions, through a low-level, high-performance, portable abstraction. By creating an efficient, close-to-the-metal programming interface, OpenCL will form the foundation layer of a parallel computing ecosystem of platform-independent tools, middleware and applications.

What we can look forward to given this release is the boom of parallel-aware compilers which are not only able to do auto-vectorization to leverage the Streaming SIMD extensions available in both (modern) Intel and AMD processors. We also may be able to see better performance from TR2-slated libraries for parallel counterparts to the STL algorithms.

This release of OpenCL is very significant since most of the major hardware and software vendors are part of the group that developed the specifications. This means one day (in the not so distant future) hardware vendors that support OpenCL on their devices will be able to run applications that depend on the OpenCL spec -- imagine your 4-core-8-thread-capable application will be able to seamlessly scale to 32-core-128-thread machines. We'll also start seeing compilers which will be able to leverage the OpenCL specifications to create binaries that take advantage of OpenCL aware architectures.

It has been noted that Apple is a driver in this space. I just wonder though how the LLVM development happening in Apple has anything to do with their wanting to develop an open standard for leveraging parallel computing systems. At any rate, with a slowly-but-surely maturing Clang frontend to an LLVM compiler, a growing set of literature and implementations on automatic vectorization of code in C++ compilers, it's just evidence that we should really start paying attention to the parallel computing space if we want to remain relevant.

Update: Adding links to SSE extensions definition and Intel (R) /AMD (R).

The Optimization Game

2008-12-03T06:25:00.000-08:00

Herb Sutter has written recently about optimizing parallel performance of a concurrent queue as part of his ongoing series of articles about concurrency and parallel programming. In his article, he shows how you can empirically test the performance of a parallel component (in this case, a concurrent queue) and then adjust the implementation to maximize the available parallelism from the solution.

How would you write a fast, internally synchronized queue, one that callers can use without any explicit external locking or other synchronization? Let us count the ways...or four of them, at least, and compare their performance. We'll start with a baseline program and then successively apply three optimization techniques, each time stopping to measure each change's relative performance for queue items of different sizes to see how much each trick really bought us.

from Measuring Parallel Performance: Optimizing a Concurrent Queue

I haven't finished reading through the article yet but I definitely think this is going to be another good read. He mentions the necessity of really avoiding races at any cost (as far as using spinlocks on a supposedly lock-free concurrent queue implementation through atomics) and I for one agree that in the interest of stability and correctness, there are some concessions that have to be made.

One other thing that he follows very prudently is the carpenter's advice which is: measure twice, cut once. He doesn't just go blindly guessing where and how performance improvements can be gained in the implementation, but rather use measurements and small incremental changes and sees what kind of performance gains are made.

More about my thoughts on the article in the coming post.

Parallel Cryptography

2008-11-25T06:53:00.000-08:00

I was again going through my reading list (lately I've had a lot of time to catch up with my reading) and an article from Dr. Dobb's journal caught my eye: an article about a parallel implementation of MD6. It's not really rocket science that some of these algorithms can be parallelized, but what is more important is how they did it. The following snippet doesn't do much justice to how easy possibly the future of parallel programming with C++ can be.

The full MD6 application has over 3,000 lines of code. Adding two Cilk keywords (at the bottom of the code snippet below) was sufficient to multicore-enable the algorithm. MD6 is recursive, and adding the Cilk++ keywords exposes a great deal of parallelism.

from Multicore and Cryptographic Hash Functions

Imagine being able to multi-core enable your code with just keywords instead of thinking about how to implement/use threads and thread pools. Of course you still have to know where to introduce the parallelism, where the problem can usually be.

It takes some effort in designing and implementing algorithms that will be able to take advantage of the parallelism available in the hardware and it's no joke implementing a robust cryptographic function at the same time. It's really something else when an algorithm is designed to be implemented in parallel.

I would think it's just a matter of time before we start seeing more of the upcoming implementations be more parallelism aware than we currently are seeing.

Diagonal Scaling?

2008-11-22T03:33:00.000-08:00

While reading through my reading list, I ran into this article from CloudN which hit a nerve with the kinds of things I've been trying to accomplish in the day job. This pertains to scaling your infrastructure not just in a horizontal manner (scaling out, adding more machines) or just in a vertical manner (adding more power to a single processing unit), but rather in a diagonal direction:

... we are starting to see a third general model of scaling emerging over and over again. This third model can be conveniently characterized as “scaling diagonally”. In diagonal scaling, a small fraction of the total number of servers (say 1% or 0.1%) are highly stateful and highly reliable. The other 99% or 99.9% are very low-cost (inherently unreliable) commodity machines that carry out the bulk of the work, but are not responsible for maintaining complex metadata or complex state.
from CloudN post How to Scale? - Up, Out, or Diagonally

This makes sense definitely since most (if not all) of the time you're constrained with a budget and a set of requirements for both performance/throughput and reliability. This model serves the requirements of a lot of massively parallel computations that have any sort of business relevance.

There have been a lot of similarly built architectures with C++ -- most notably Hypertable where you have a single name host which knows where the other range servers are and a single "lock server" (called Hyperspace) which coordinates changes across the cluster. If you haven't yet, you should read more about the Hypertable architecture.

If you're in an industry where you find yourself dealing with massive amounts of data and are required to do it in a very fast and reliable manner, you should definitely check out these newer technologies for both storing and processing your data.

C++ Concurrency in Action - A (P)Review

2008-11-21T11:37:00.000-08:00

Recently I had been contacted by a representative from Manning Publishing to do a book review about an upcoming book about C++ Concurrency in Action by Anthony Williams. I’ve been lucky enough to get access to preview of the book while it’s being written—and now I’m posting a public review of my thoughts on the book.

I for example have in the past written a lot about parallel programming ranging from observations in the changes to come in parallel computing and parallel computing on the desktop to code samples on parallel programming . I was fortunate enough to get a preview of the book and in this post I note down my take on it.

Anthony Williams (maintainer of Boost.Thread) has been one of the main proponents of the push to include a threading library as part of the C++ Standard Template Library. In his upcoming book he writes very eloquently and in a very readable manner about the good, bad, ugly, and beautiful aspects of writing concurrent programs. He uses a conversational style of writing to make his point which is a delight to read especially since the subject matter is fairly complex.

His book is chock full of insights from various levels in designing and implementing concurrent C++ applications using the upcoming C++ standard threading library. He also points out implementations already available in Boost.Thread as well as idioms and techniques into writing effective solutions to common issues faced with concurrency and C++.

He also writes very well about common pitfalls in adapting certain data structures and algorithms from a purely sequential and single-threaded view to thead-safe equivalents. For instance he writes about the problems you’ll encounter when locking mutexes and certain design decisions that have to be made when implementing concurrency-aware abstract data types.

Interestingly he takes the reader through a well thought out series of evolutions of solutions and approaches written in succinct and very representative “real world” C++ code. He uses this style when introducing new concepts as well as going back into earlier slightly discussed and deferred topics. This is welcome especially for those who have been doing concurrent programming for a long time already and should work equally well for those who have not yet been exposed to much of the intricacies of concurrency-aware programming in C++.

When the book does come out, expect to see a thorough discourse and handy manuscript on the evolution of C++ into the concurrent application development space, new tools for every C++ programmer’s toolbox, great tips and insights, and overall great advice when approaching concurrent application development in C++. It is very well written and definitely worth every penny you invest in it especially if you intend to future-proof yourself from the challenges of multi-core programming with C++.

Overall it’s a must-read if you intend to ride the wave of developing concurrent applications that take advantage of the new multi-core processor architectures. It’s a book you shouldn’t pass up if you intend on being productive with C++ for a long time to come.

I will definitely look forward to this book when it does go out for distribution. Do not miss this opportunity to learn from one of the recognized experts in C++ as far as concurrency programming is concerned. You can pre-order your copy today.