2008 May 29 - Thu

Evaluating Inter-Process Communication Frameworks

I'm reposting some comments regarding IPC frameworks that I made to the Boost-Users listserve today. It is in response to someone making unsubstantiated remarks regarding the relative merits of ACE and Boost, and another looking for some substatiated remarks. What follows are some substantiated remarks, based upon my personal experience with it and several other libraries.

I've started working on a number of distributed system projects. As a consequence, I started looking for distributed system libraries. References to ACE were most pervasive. I implemented a number of trial applications with the library. That was after plowing through relevant sections in the three primary ACE reference books. That was a good learning experience, if only to find out the various patterns in distributed architecture definition. I had the inter-process/inter-server communications (which only sent simple stuff) working well within ACE's Acceptor/Connector framework. ACE has a number of other patterns one can use. I was really impressed with the fact that the examples I used from the books worked as advertised, and I was able to bend them to my will.

ACE is based upon an interaction of classes, macros, and templates. One has to spend some time with the environment in order to become proficient with it. It has a large API. A number of lower level API's upon which higher level API's are based. For example the Acceptor/Connector uses constructs described earlier in the books.

Once I had my basic communications going, I realized I needed to get some form concrete messaging infrastructure in place. I had an impression that TAO, which is a layer above ACE, would be quite extravagant to implement, with it being an implementation of the CORBA specification. I wanted something a little lighter (a whole lot lighter actually).

As I worked through that project, I started hearing about ASIO, indirectly through some other libraries I was using. ASIO is now a member of Boost. I read a review somewhere that ASIO is a 'modern' replacement for ACE. If you want to get into real template structures and Boost oriented philosophy, I'd say that is a valid statement. I'd also say that ASIO is 'more to the point' and straight forward than is ACE, at least for the things I want to accomplish. But like ACE, ASIO is the basic communications infrastructure, no real messaging capability, which is what distributed computing is all about. ASIO turned out to be a little harder to get my head wrapped around as it uses a number of advanced C++ and Boost related idioms. For a run-of-the-mill C++ programmer, ACE would be better. For someone steeped in the power and obscurity of advanced C++, and is looking to advance their skill set, ASIO would be better.

I came across RCF - Interprocess communication for C++, which is a messaging framework riding atop of ASIO. Flexible, lightweight, and to the point. I worked through the examples and things worked as advertised. It has the encryption, publisher/subscriber, oneway/twoway idioms, and a few other nifty features.

At the same time I was doing that, seemingly coincidently, I learned a few more interesting facts. Going into this, I realized that I need a message dispatcher/proxy, some decent failover techniques, and some additional event handling for non-IPC related activities.

Someone suggested ICE from www.zeroc.com for an RCF-like solution, but working to a larger scale. I've heard that the library's originator is someone who spent much time on CORBA standards and redid the concept without the 'benefit' of committee involvement. I think the library has all the bases covered in terms of lightweight message handling, dispatching, resiliency, and higher level distributed processing philosophies. The drawback is that it will have a steeper learning curve than would an implementation using RCF. I like RCF, but I think I.m going to have to tilt towards ICE (itself, like RCF, developed and focused towards C++ in a multiple license environment).

On the non-IPC front, Qt's QCoreApplication looks to be a good substrate on which to build event driven daemons.

In the end, I think my solutions are going to involve:

• ZeroC's ICE for primary inter-process communications
• Qt QCoreApplication as a base for daemon development (which has built-in stuff for threads/locks, slots/signals)
• Wt, a C++ based web toolkit for distributed GUI development
• Boost Libraries to fill in all the holes
• a little legacy layer 3/4 ACE in one library I'm using, but with some work, I think I can convert the ACE stuff to ASIO

2008 May 24 - Sat

A Keyword Matching Algorithm

There are a number of well known algorithms out there for taking in a set of keywords and matching them against test. Aho and Corasick comes to mind, as does the Wu Manber algorithm (the latter I've implemented, and the code resides elsewhere on this site).

For another project, I didn't need something quite so fancy. Actually two projects come to mind. One is that I have a input comma separated value file which includes stock symbols, a description, and the associated exchange. I wanted to keep statitics on what is read in on an exchange basis. My first kick at the can on this was to implement a string look up table using

In another part of the file, to do some special computing, and in a fit of late night programming, I went so far as to implementing a multi-stage strcmp on each exchange to do something special for each.

I knew from the outset, that would be horribly inefficient, but I didn't have a nice algorithm at hand to do it with.

After being reminded of Aho Corasick in another context, I decided to take another stab at improving efficiency. I ended up implementing half of Aho Corasick's algorithm, the 'go' function. Since I'm always matching from the beginning of the string, and am not stepping through text, the exclusion of the 'fail' function works quite well, and keeps the code smaller.

At some point in time the code can be coverted to something using templates in order to accept various string types, various element matches, and return codes.

Since the 'fail' function isn't implemented, the lookup table can be updated dynamically without being rebuilt from scratch.

The library is quite easy to use. With AddPattern, add new keywords along with some sort of index or object. When using FindMatch with the target keyword, the appropriate object will be returned on a successful match. If no match is found NULL will be returned. A modification to the class would add a default object for use when no matches are found.

Here is the header file.

#pragma once

// Copyright (2008) Ray Burkholder
// Matching against multiple keywords

#include <vector>
#include <string>

class CKeyWordMatch {
public:
  CKeyWordMatch(void);
  virtual ~CKeyWordMatch(void);
  void ClearPatterns( void );
  void AddPattern( const std::string 
&sPattern, void *object );
  void *FindMatch( const std::string 
&sMatch );
protected:
  struct structNode {
    size_t ixLinkToNextLevel;  // next letter of same word
    size_t ixLinkAtSameLevel;  // look for other letters at same location
    void *object;  // upon match, (returned when 
keyword found)
    char chLetter;  // the letter at this node
    structNode() : ixLinkToNextLevel( 0 ), ixLinkAtSameLevel( 0 ), 
      object( NULL ), chLetter( 0 ) {};
  };
  std::vector<structNode> m_vNodes;
private:
};

Here is the code file:

#include "StdAfx.h"
#include "KeyWordMatch.h"

// Copyright (2008) Ray Burkholder
// Matching against multiple keywords

#include <stdexcept>

CKeyWordMatch::CKeyWordMatch(void) {
  ClearPatterns();
}

CKeyWordMatch::CKeyWordMatch(size_t size) {
  m_vNodes.reserve( size );
  ClearPatterns();
}

CKeyWordMatch::~CKeyWordMatch(void) {
  m_vNodes.clear();
}

void CKeyWordMatch::ClearPatterns() {
  m_vNodes.clear();
  structNode node;
  m_vNodes.push_back( node ); // root node with nothing
}

void CKeyWordMatch::AddPattern( 
              const std::string &sPattern, void *object ) {
  std::string::const_iterator iter = sPattern.begin(); 
  if ( sPattern.end() == iter ) {
    throw std::runtime_error( "zero length pattern" );
  }
  size_t ixNode = 0;
  size_t ix;
  bool bDone = false;
  while ( !bDone ) {
    char ch = *iter;
    ix = m_vNodes[ ixNode ].ixLinkToNextLevel;
    if ( 0 == ix ) { // end of chain, so add letter
      structNode node;
      node.chLetter = ch;
      m_vNodes.push_back( node );
      ix = m_vNodes.size() - 1;
      m_vNodes[ ixNode ].ixLinkToNextLevel = ix;
      ixNode = ix;
    }
    else { // find letter at this level
      //ix = m_vNodes[ ixNode ].ixLinkToNextLetter;  // already set
      bool bLevelDone = false;
      size_t ixLevel = ix;  // set from above
      while ( !bLevelDone ) {
        if ( ch == m_vNodes[ ixLevel ].chLetter ) { 
          // found matching character
          ixNode = ixLevel;
          bLevelDone = true;
        }
        else {
          // move onto next node at this level to find character
          size_t ixLinkAtNextSameLevel 
            = m_vNodes[ ixLevel ].ixLinkAtSameLevel;
          if ( 0 == ixLinkAtNextSameLevel ) {
            // add a new node at this level
            structNode node;
            node.chLetter = ch;
            m_vNodes.push_back( node );
            ix = m_vNodes.size() - 1;
            m_vNodes[ ixLevel ].ixLinkAtSameLevel = ix;
            ixNode = ix;
            bLevelDone = true;
          }
          else {
            // check the new node, nothing to do here
            // check next in sequence
            ixLevel = ixLinkAtNextSameLevel;
          }
        }
      }
    }
    ++iter;
    if ( sPattern.end() == iter ) {
      if ( NULL != m_vNodes[ ixNode ].object ) {
        std::runtime_error( "Pattern already present" );
      }
      m_vNodes[ ixNode ].object = object;  // 
assign and finish
      bDone = true;
    }
  }
}

void *CKeyWordMatch::FindMatch( const std::string &sPattern ) {
  // traverse structure looking for matches
  std::string::const_iterator iter = sPattern.begin(); 
  if ( sPattern.end() == iter ) {
    throw std::runtime_error( "zero length pattern" );
  }
  void *object = NULL;
  size_t ixNode = 0;
  size_t ix;
  bool bOpFound = true;
  bool bDone = false;
  while ( !bDone ) {
    char ch = *iter;
    ix = m_vNodes[ ixNode ].ixLinkToNextLevel;
    if ( 0 == ix ) {
      bDone = true;  // no more matches to be found so exit
    }
    else {
      // compare characters at this level
      bool bLevelDone = false;
      size_t ixLevel = ix;  // set from above
      while ( !bLevelDone ) {
        if ( ch == m_vNodes[ ixLevel ].chLetter ) {
          ixNode = ixLevel;
          bLevelDone = true;
        }
        else {
          ixLevel = m_vNodes[ ixLevel ].ixLinkAtSameLevel;
          if ( 0 == ixLevel ) {  // no match so end 
            bLevelDone = true;
            bDone = true;
          }
        }
      }
    }
    ++iter;
    if ( sPattern.end() == iter ) {
      object = m_vNodes[ ixNode ].object;
      bDone = true;
    }
  }
  return object;
}

2008 May 23 - Fri

RCF - Interprocess Communications for C++

For a couple of distributed computing projects, I've been trying to come up with a feasible and easy to use method for making applications talk to each other, whether they be on the same machine or across a network.

I started off doing some work with Douglas C. Schmidt's ACE: The ADAPTIVE Communication Environment. I plowed through ACE's three primary programming books to see what would be the best bit of the environment I would need. I ended up implementing a demo with the Acceptor - Connector framework, just to see how things worked.

I then started on thinking on the messaging structure and the event handling structures. ACE's mixture of macros and classes turned out to be a little overwhelming for what I wanted to accomplish.

During my stint with ACE, I started to use ASIO, from the Boost libraries. I was first introduced to ASIO through working with WT: WebToolKit. I used Wt as a frontend to a voip call sign in server.

The next step in the evolution is to present a real time call summary report to authorized management as the calls are authenticated, authorized, and accounted for from a Radius server. This means sending call detail messages from the Radius server to a central dispatch server, and then publish to active web clients (with the clients written with Wt).

As Wt uses ASIO for its underlying network communications, and I had read a remark somewhere that ASIO is the new improved ACE, I started to look into it as the mechanism for my inter-process communications. I even got a good chunk of messaging infrastructure written as was about to get it testing when I found it was all for nought.

I came across RCF - Interprocess Communications for C++. It is a library that has been in development for the last few years by a talented fellow by the name of Jarl Lindrud. The library has implemented all the stuff that I only dreamed about doing: publish/subscribing, stream encryption, payload filtering, and any number of other nifty features.

I had a few painful moments in getting the library built. After a couple of messages back and forth to the author, I realized I was trying to build the whole thing into a static library rather than using an 'include' technique to get the platform specific files built.

The client and server examples built and ran without a hitch. I must admit that I was impressed by the examples in the ACE books as well: they compiled and ran with little or no messing about.

The RCF library is better because it deals with serializing native values back and forth, something that ACE only accomplishes when you get into the TAO and CORBA levels of the environment.

So now with Boost (which includes ASIO), RCF (which uses ASIO), and Wt (which also uses ASIO), I think I have all the interprocess tools I need to make my modules talk to each other. Now I can get on with the meat of my projects.

2008 Mar 26 - Wed

C++ Custom Containers and Iterators

I'm using the HDF5 File System for holding time series information. Rather than writing my own binary search implementation to find particular elements within a particular saved time series, I thought it would be clever if I designed the interface so I could use the Standard Template Library's 'find' iterator. If I can make the STL's 'find' work, then all the other iterators should work just as well, and thus I'll have an easy mechanism to access time series with very little programming involved.

I can find any number of web sites containing information on how to work with C++'s standard containers and iterators. When it comes to finding information on custom containers and iterators, the information is not quite so plentiful.

The first article I came across was one from TechRepublic called Extending the C++ STL with custom containers. It didn't quite have the meat I was expecting.

Bjarne Stroustrup's book, The C++ Programming Language, does have a section on iterators and a section on containers. In retrospect, they are quite good introductions to the concept, but I didn't feel the examples were as informative as I would have liked.

Microsoft's MSDN has an article called C++ and STL: Take Advantage of STL Algorithms by Implementing a Custom Iterator, but this article only covers the custom iterator side of things, it doesn't discuss how it would interact with a custom container.

Dr. Dobbs inherited an article entitled Custom Containers & Iterators for STL-Friendly Code: A pair of approaches for creating custom containers from the March 2005 issue of C++ Users Journal. Some code extracts are included but there are some pieces missing, such as the begin() and end() methods and how they are put together. The link in the article to the original code no longer works. However, I did find that I have the Dr. Dobbs Developer Library DVD Release 4. On it resides the full example code. That was much more informative.

Now that I have a better understanding for what I'm looking, I see that the STL compliant container example has some useful information. In the same vein, CodeProject has another example: An STL compliant sorted vector.

Finally, I came across Ulrich Breymann's book called Desiging Components with the C++ STL. It provided all the necessary background to pull it all together. I always thought there was more to it, but custom containers and iterators may not be so hard after all. Once I have the code finished, I'll try to have it posted one way or another.

2008 Mar 25 - Tue

Who Needs a SafeD Net?

Bartosz Milewski, a member of the 'D' design team, wrote an article about making the programming language D even safer than it purportedly already is. He called that subset: SafeD. In the process of making D and SafeD look good, the failings of C++ were highlighted in comparison. To his credit, the author was able to list a few good features: performance, low-level access, and powerful abstractions (the latter being slighted at the same time for apparently only being useful in operating systems or large systems design).

On the other hand, it is nice to hear that whenever people feel they have to make their language-of-choice look good, inevitably some subset of C++ comes in as a benchmark. I include the word 'subset' on purpose. There are specialized, productive, easy to learn languages out there. I've even used a few of them. Each of them is better than some specific aspect of C++, but few if any, can beat C++ in many areas. Ok, maybe Lisp does better.

B Milewski did acknowledge that "There are many other simplifications and safety improvements over C++. Unfortunately they all come at the expense of expressive power and performance." well said.

I used C# for a couple of years, buying into the theory that automated memory management and suborned pointers would be a good thing for me. Ah, no. I like the ability to be able to 'shoot myself in the foot'. Really good gun-slingers know their guns, know where to point them, know how to maintain them, know their useful range, and clean often to ensure good performance. Would a gunslinger hand his gun over to an acolyte for cleaning and maintenance? The same could be said of a programmer handing over memory management and object manipulation to some hidden behind-the-scenes mechanism which may not be optimal for the job.

Perhaps I'm just a control freak, but I had to depart C# and return to the wild west of C++ programming in order to feed my adrenalin requirement of walking the fine edge of writing elegant, flexible code.

Isaac Asimov wrote a book called the End of Eternity. The moral of that story was that if humanity is not allowed to push the boundaries, and get hurt a little in the process, stagnation sets in. Also, the hero of the story wouldn't have been able to look off into the sunset with the heroine at his side.

Perhaps C++ is indeed a difficult language to master. It's flexibility may be its undoing, but the for the tenacious learners, it provides a high level of satisfaction for allowing one to come up with good solutions for tough problems, big or small... and for being able to devise an appropriate solution from an excellent collection of varied tools.

Scott Meyers, in his book, Effective C++, eloquently expresses why C++ has the feel of an elephant being touched by a number of blind men. C++ is actually a federation of languages.

• Deep down, C++ is the structured programming language known as C.
• C++ is C with Object Orientedness added on.
• C++ is Generic Programming, template metaprogramming, which is said to rarely interact with mainstream C++ programming.
• STL is a sub-language of C++ based upon algorithmic programming, as defined by Alexander Stepanov.

In the referenced article from the last point above, a few enlightning quotations about Stepanov's strong views of C++ strengths and weaknesses: "STL is the result of a bacterial infection", "STL is not object oriented. I think that object orientedness is almost as much of a hoax as Artificial Intelligence.", "Always start with algorithms.", "Generic programming is a programming method that is based in finding the most abstract representations of efficient algorithms", and "So far, C++ is the best language I've discovered to say what I want to say".

          O how they cling and wrangle, some who claim 
          For preacher and monk the honored name! 
          For, quarreling, each to his view they cling. 
          Such folk see only one side of a thing. 

          Jainism and Buddhism. Udana 68-69: 
          Parable of the Blind Men and the Elephant 

For those hoping to find the perfect language, here is what The Architect has to say about that:

"Hope, it is the quintessential human delusion, simultaneously the source of your greatest 
strength, and your greatest weakness."

Perhaps C++'s flexibility is both its greatest strength as well as its greatest weakness.

Programming Chaos on the Wings of a Butterfly

From xkcd, a webcomic of romance, sarcasm, math, and language.

2008 Mar 16 - Sun

Don't Use Defined Macros, Use Templated Inline Functions Instead

In the olden C days, one would use #define MACRO .... to build an inline macro for computationally quick evaluation of some calculation. When using that method of programming, one needed to remember to parenthesize extensively in order to prevent wierd things from happening when calling the function with an expression.

The modern approach is to use a template for an inline function, which yields all the efficiency of a macro, plus all the predictable behavior and type safety of a regular function (item #2 in the book Effective C++. An example declaration follows:

template<typename T>
  inline void DoWithMax( const T& a, const T& b ) {
    f( a > b ? a : b );
  }

2008 Jan 18 - Fri

C++ Tools: Face Detection, Artificial Neural Networks

Today I came across a couple of C++ projects relating to Neural Network usage. One is located at CodeProject called Face Detection C++ Library with Skin and Motion Analysis. The author has used a number of interesting statistical and analytical methods for face detection. To quote his mouth-full: "An understanding of wavelet-analysis, dimensionality reduction methods (PCA, LDA, ICA), artificial neural networks (ANN), support vector machines (SVM), SSE programming, image processing, morphological operations (erosion, dilation), histogram equalization, image filtering, C++ programming and some face detection background would be desirable.".

From a C++ library perspective, here is a Fast Artificial Neural Network Library (FANN). I believe the library is written in C, but has API bindings in about 13 different programming language formats, of course with one being C++. The author's description goes as follows: "Fast Artificial Neural Network Library is a free open source neural network library, which implements multilayer artificial neural networks in C with support for both fully connected and sparsely connected networks. Cross-platform execution in both fixed and floating point are supported. It includes a framework for easy handling of training data sets. It is easy to use, versatile, well documented, and fast."

They Can't be Better Than Sliced Bread

On dzone, there were a couple of language related articles. Well, ok, the whole site is devoted to programming languages. Perhaps what I was trying to say is that I detected a mild language war brewing. Well, maybe skirmish. Maybe mild skirmish.

Linux.com has an article on D, called New D language pumps up programmer productivity. The writer does a lot of comparing against C++. I still fail to see why D shines though. What makes it special?

C# is supposed to be a better C++. When you couple C# with Microsoft's CLI (Common Language Interface) libraries, it is a nice development environment. C# takes away some nice things from C++, but adds its own nice things.

Java is also supposed to be a better C++. Java does indeed do a good job of of being platform independent. For instance, I liked the way of being able to install Eclipse, the Java based IDE, on a Linux platform or a Windows platform and being up and running in minutes. I havn't programmed in Java, so can't make a fair comparison of what makes Java a nice place in which to program.

In an article by Rick Hightower, he mentions Java, Ruby, Python, and Scala. In the article is a graph showing language usage. Java ranks first and C++ second.

I have an insurance modelling friend who swears by Python, which ranks a low sixth in the chart.

Anyway, what got me started on this all was an article called The Great Language Backlash. I thought, oh cool, someone is going to do an impressive rant on what is missing in all the world's programming languages. it ended up being some little rant about Ruby and Groovy, with Ruby being last in the chart I mentioned above. I'm glad the writer redeemed himself with his final phrase of the article: use the best tool for the job. Well, I suppose that phrase, in and of itself, is worthy of many a rant all by its lonesome.

I just can't resist: C++ rocks!! Maybe the version 0x should be changed to C!!! I'll leave it up to the reader to determine how many '!' belong to the C and how many belong to sentence punctuation.

2007 Oct 19 - Fri

C++ Libraries from Scaling Web

Scaling Web has a number of open source libraries that may be of use:

• Template based B+ Tree: Implemented in C++, B+ Tree is template based, so it can be used with any types of data. Memory based B+ Tree is much faster than STL containers like map, hash_map.
• Embedded File System: Embedded File System (EFS) is a library that allows you to create virtual file system in a single file.
• Mork Parser in C++: MorkParser is an efficient C++ implementation of Mork database format reader. The Mork format is used in most Mozilla-based projects, including the Mozilla browser suite, SeaMonkey, Firefox and Thunderbird.
• Mime Email Parser in C++: C++ implementation of RFC 2045 - Multipurpose Internet Mail Extensions (MIME) standard.
• C++ IO Streams Library: IO Streams library provides different Java-like interface streams in C++.