What's it all about, Alfie?

This evening I finished up adding pools to DKit, and there are a few things that make it so bloody cool I had t write about it. In short, the problem is one that I've had to deal with before: How to make a simple pool of things such that I only create what I need, but don't over create, and can use a manageable set of things from a pool.

Like say I wanted to have a messaging system. I might want to have a bunch of std::string values that are created with a minimum size to make it easy to move things around. Then, all I would need to do is to get one from the pool, clear it out, add in the data, and then when I'm done, return it to the pool. The location in the code that gets from the pool is at a totally different place than the place that recycles these instances, and it's possible that due to threading or queueing, we may need to have several in play all at once. But eventually they will all come back to be recycled.

In the past, I had one class for a std::string pool, and another for datagrams, and so on. Each of these was almost identical to the other, just in how the instance was created. Typically, I'd have some sense of the 'default' size of the container I was creating. I based each off a single type of FIFO queue, so that it would always be a SP/SC pool, etc. This was necessary because I hadn't super classed the FIFO queues as I have in DKit.

Still… this was a lot of copy-n-paste reuse, and it was clear that it wasn't anywhere near as flexible as it could be. So today I decided to try and see what I could get away with if I tried to make a complete template pool class. The challenges were pretty clear:

• Include the Type of the Queue in the Template - I knew that now that I had the FIFO abstract template class in DKit, it was going to be possible to have the constructor make a queue of the right type, and then just "use it" via the FIFO abstract template class and be able to allow the user to define what access type they wanted for the pool.
• Include the Max Size of the Pool as a Power of Two - this was in keeping with the queues I'd be creating, and so shouldn't prove to be too hard.
• Allow Pointers and Non-Pointers to be Pooled - this was the biggest challenge I faced, to be sure. In the pool, I wanted to have two basic methods: next() to get a new one from the pool, and recycle(T) to return it to the pool. The problem is what if the type 'T' is a pointer versus a non-pointer? How do we make sure we can delete a pointer, but simply let a uint64_t fall on the floor and be cleaned up?

Thankfully, I was able to look on Stack Overflow and see this interesting question which lead me to the answer I needed. What it really boiled down to was that I could use the boost::is_pointer(), but that only really lets me know if I need to clean up the contents of the queue in the clear() method. The trick to constructing and destructing was to realize that the templates worked outside the scope of the class definition, and so after the class definition, I added in these functions:

  namespace dkit {
  namespace pool_util {
  /**
   * In order to handle both pointers and non-pointers as data
   * types 'T' in the pool, we need to take advantage of the
   * template methods and make create() and delete() methods
   * for pointers and non-pointers.
   *
   * For create(), it's pretty easy - we allow for nothing to be
   * done for the non-pointer, and a standard 'new' for the pointer.
   * For delete(), it's the same - we delete it and then NULL it
   * out if it's a pointer, if it's not, we do nothing.
   */
  template <typename T> void create( T t ) { }
  template <typename T> void create( T * & t )
  {
    t = new T();
  }
 
  template <typename T> void destroy( T t ) { }
  template <typename T> void destroy( T * & t )
  {
    if (t != NULL) {
      delete t;
      t = NULL;
    }
  }
  }      // end of namespace pool_util
  }      // end of namespace dkit

Then, in the critical next() and recycle() methods, I simply used these functions:

  /**
   * This method is called to pull another item from the pool, or
   * create a new one if nothing is in the pool. This is the classic
   * way of getting the "next" item to work with.
   */
  T next()
  {
    T      n;
    // see if we can pop one off the queue. If not, make one
    if ((mQueue == NULL) || !mQueue->pop(n)) {
      pool_util::create(n);
    }
    // return what we have - new or used
    return n;
  }
 
 
  /**
   * This method is called when the user wants to recycle one of
   * the items to the pool. If the pool is full, then we'll simply
   * delete it. Otherwise, we'll put it back in the pool for use
   * the next time.
   */
  void recycle( T anItem )
  {
    if ((mQueue == NULL) || !mQueue->push(anItem)) {
      pool_util::destroy(anItem);
    }
  }

By using the create(n) and destroy(n) functions, I allow the compiler to see the template functions and pick which one to use. In the case of a pointer for 'T', it chooses the pointer-reference argument, in the case of a non-pointer, it's the pass-by-value argument. This selectivity allows me to partially implement these any time I want in order to make the actual construction and destruction as complicated as I need without requiring it for the simple default constructor and destructor.

Once I had this, the remaining problems weren't too bad at all.

I created an enum for the type of access to use:

  /**
   * We need to have a simple enum for the different "types" of queues that
   * we can use for the pool - all based on the complexity of the access. This
   * is meant to allow the user to have complete flexibility in how to ask for,
   * and recycle items from the pool.
   */
  namespace dkit {
  enum queue_type {
    sp_sc = 0,
    mp_sc,
    sp_mc,
  };
  }       // end of namespace dkit

and then it was pretty simple to make the template and the constructor:

  template <class T, uint8_t N, queue_type Q> class pool
  {
    public:
      pool() :
        mQueue(NULL)
      {
        switch (Q) {
          case sp_sc:
            mQueue = new spsc::CircularFIFO<T, N>();
            break;
          case mp_sc:
            mQueue = new mpsc::CircularFIFO<T, N>();
            break;
          case sp_mc:
            mQueue = new spmc::CircularFIFO<T, N>();
            break;
        }
      }
 
  …
  };

In the end, the code worked wonderfully. I built a test app that made sure the destructor was properly being called when recycle() was being called and the queue was full - check. I also made sure that when the pool was destructed, any remaining elements were properly destructed - if they were pointers.

It was really an amazing little bit of code. This is far more flexible and better than the previous single-purpose pools I've written. Less code is always better.

Today I wanted to add a little bit more to DKit, so I decided that the next best thing to add were the concepts of a template source and sink. When I built the MessageSource and MessageSink back at PEAK6, I did it in the context of a Message object. That was fine, because that's all we needed, but this time I wanted to make it a little better - no a lot better, so I made the source and sink template classes.

This will allow me to use the pointers like I did before, but it will also make it very easy to use integers, or doubles - or anything. This will be a far better solution to the problem than a fixed class, or pointer to a class.

The only real problem I ran into - if there was indeed any real problems, was the syntax for specifying the template class methods in the implementation file. The header was pretty clear and straight forward, but the implementation was a bit trickier.

Thankfully, I was able to find some examples on the web, but the syntax was pretty bad. I mean really bad. For example, let's say I had the following template class:

  namespace dkit {
  template <class T> class source
  {
    public:
 
      virtual void setName( const std::string & aName );
      virtual const std::string & getName() const;
      virtual bool addToListeners( sink<T> *aSink );
 
  };
  }     // end of namespace dkit

then the implementation file would have to look something like this:

  namespace dkit {
 
  template <class T> void source<T>::setName( const std::string & aName )
  {
    boost::detail::spinlock::scoped_lock  lock(mMutex);
    mName = aName;
  }
 
 
  template <class T> const std::string & source<T>::getName() const
  {
    return mName;
  }
 
 
  template <class T> bool source<T>::addToListeners( sink<T> *aSink )
  {
    bool       added = false;
    // first, make sure there's something to do
    if (aSink != NULL) {
      // next, see if we can add us as a source to him
      if (aSink->addToSources(this)) {
        // finally, make sure we can add him to us
        added = addToSinks(aSink);
      }
    }
    return added;
  }
 
  }     // end of namespace dkit

Now I understand the need to clearly identify the class - hence the template <class T> on the front, but then it seems to really go overboard there. While I'm sure there's a wonderful reason for all this, it seems to have not undergone any simplification over the years. That's probably part of the problem that folks have with C++ - it's complicated looking. And if you don't get it just right, you're not going to even get it to compile.

But for me, it's just what has to be done in order to have template programming. It's a pain, yes, but it's so incredibly worth it.

I usually don't spend a lot of time talking about the industry that is the source of my livelihood, but this story is just too good to pass up. Seems that some brilliant trader decided to hedge his positions with exceptionally bad positions. So bad, in fact, that these hedges - not the original positions, but the hedges, have cost the bank $2 billion, and it's estimated that it might cost them another billion before it's all said and done.

What's even more amazing is that JP Morgan has the cash to take the loss and not post a loss for the quarter. Amazing. First, that they believed the hedges were, in fact, hedges, and that they had more than $2 billion to waste.

If they were, indeed hedges, then they were designed to cancel the loss of the original positions. This means that if the hedges lost value, then it should have been the case that the original positions gained value. So they must have picked the most horrific hedging instruments and then held far too much of them to loose that kind of money.

Really. That's almost impressive.

I've used JUnit and the Unit Testing Framework in Xcode 4, and both are pretty nice - they allow you to write tests, not headers and a lot of boilerplate code. Just the tests. Lots of simple assertions and tests, and it's really not bad at all to use these guys. But with C++ I'm finding it a lot harder to start using a testing framework. Maybe it's me, maybe it's just the language, but it's not a lot less than writing test apps, and having explicit return codes.

I'm not saying that testing isn't useful, what I'm wondering is if C++ as a language is really set up to have a nice, simple, unit testing framework like JUnit or SenTesting Framework. After all, there's a lot of flexibility in Java and Obj-C that simply isn't in C++. You can add methods to Java and Obj-C in the implementation file and run with it. Reflection (introspection) allows the language and framework to see what's available to run, and then run it. Not so for C++.

So I'm wondering if there's really any better solution than a series of good testing apps with proper return codes, and then you just run one after the other until you have what you need. Not ideal, to be sure, and it takes some effort and discipline to make sure the test apps are done properly, but I just don't see a way to make it happen in a significantly easier way.

I'll keep looking, though. Maybe someone is going to crack this nut soon.

This morning I finished up a little coding I was doing on DKit and was really happy about the outcome. The thing that really set the stage was the building of boost for OS X 10.7. It was really pretty simple, and it allows me the flexibility to use boost in DKit. Now there was nothing really stopping me before, but without it running on my MacBook Pro, it was a little hard to know that it was going to work.

I suppose I could have pulled out my old Intel laptop and downloaded Ubuntu 12 and put it on there, and run it in a terminal, but I didn't really feel like bring that guy out of the closet, but maybe it's time. I could really use to have Ubuntu 12 working now.

In any case, boost is built, and I was able to make the "hammer" and "drain" thread tests on the LinkedFIFO queues. The idea is that I have a "hammer" that can place items on a queue, and then a drain that can empty a queue. By putting these in different combinations, I can test a multi-producer/single-consumer queue as well as a single-producer/multi-consumer queue.

Starting with the Right Base Class

One of the neat things I did this morning was to make a base abstract template class for all the FIFO queues, as they all (on purpose) have the same basic API. This then allows me to treat all the different implementations as just that - implementations and not as something of significant difference.

It's not too exciting, but I was pretty pleased after I had created it and then used it as the base class for all the FIFO implementations I had in DKit. The really important part was to make sure that the core API methods were pure virtual methods - a.k.a. virtual abstract methods:

  /*******************************************************************
   *
   *                        Accessor Methods
   *
   *******************************************************************/
  /**
   * This method takes an item and places it in the queue - if it can.
   * If so, then it will return 'true', otherwise, it'll return 'false'.
   */
  virtual bool push( const T & anElem ) = 0;
  /**
   * This method updates the passed-in reference with the value on the
   * top of the queue - if it can. If so, it'll return the value and
   * 'true', but if it can't, as in the queue is empty, then the method
   * will return 'false' and the value will be untouched.
   */
  virtual bool pop( T & anElem ) = 0;
  /**
   * This form of the pop() method will throw a std::exception
   * if there is nothing to pop, but otherwise, will return the
   * the first element on the queue. This is a slightly different
   * form that fits a different use-case, and so it's a handy
   * thing to have around at times.
   */
  virtual T pop() = 0;
  /**
   * If there is an item on the queue, this method will return a look
   * at that item without updating the queue. The return value will be
   * 'true' if there is something, but 'false' if the queue is empty.
   */
  virtual bool peek( T & anElem ) = 0;
  /**
   * This form of the peek() method is very much like the non-argument
   * version of the pop() method. If there is something on the top of
   * the queue, this method will return a COPY of it. If not, it will
   * throw a std::exception, that needs to be caught.
   */
  virtual T peek() = 0;
  /**
   * This method will clear out the contents of the queue so if
   * you're storing pointers, then you need to be careful as this
   * could leak.
   */
  virtual void clear() = 0;
  /**
   * This method will return 'true' if there are no items in the
   * queue. Simple.
   */
  virtual bool empty() = 0;
  /**
   * This method will return the total number of items in the
   * queue. Since it's possible that multiple threads are adding
   * to this queue at any one point in time, it's really at BEST
   * a snapshot of the size, and is only completely accurate
   * when the queue is stable.
   */
  virtual size_t size() const = 0;

Then it was easy to use these methods in place of the actual methods in the subclasses. It's just a better way to define the API. With that done, I was able to make the Hammer and Drain because when I needed to reference a Queue, I just used dkit::FIFO and that was good enough. Pretty nice.

Handling the Logging

One of the problems with multi-threaded testing is that the output tends to garble itself pretty totally at times, and it makes it near impossible to determine what was really meant by the output of the code. For example, I had the following in the Drain:

  std::cout << "[Drain::doIt(" << mID << ")] - popped "
            << mCount << " items off the queue" << std::endl;

but because it was dealt with as six different components, there was more than adequate time to have another thread jump into the output stream and have its output intermingle with the message I was trying to send.

So what's a better way? Well… have all the components in one place, like this:

  std::ostringstream msg;
  msg << "[Drain::doIt(" << mID << ")] - popped "
      << mCount << " items off the queue";
  std::cout << msg.str() << std::endl;

What I realized was that this still looks like two items, and the newlines were getting intercepted and causing the output to look bad. The final result I went with was the "all-in-one" idea:

  std::ostringstream msg;
  msg << "[Drain::doIt(" << mID << ")] - popped "
      << mCount << " items off the queue" << std::endl;
  std::cout << msg.str();

At this point, things looked a lot better, and I wasn't getting the scrambled messages. Now this is only good if the console writer is atomic, but it's a lot better bet doing it this way than hoping that the entire streaming operation was going to be atomic. That's just not happening.

Adding a Little Polish

Once I had the LinkedFIFO tests done, and the classes all ready to go, I checked it all in and then updated the docs to reflect the addition of the base class as well as the new dependency on boost and the rationale for it. I'm not sure that many are going to care - it's pretty isolated, if you really don't want to use boost - even though it's on even platform you could imagine, so it's not hard to remove. But it makes life and portability much easier.

It's been a productive morning. I need to go back and put the tests in for the CircularFIFO implementations, but that's not going to be too hard - after all, the same code will work on them that did on the LinkedFIFOs. I just need to move it over and let it run.

Just saw on Twitter that 10.7.4 was released and includes a few bug fixes that even effect Acorn, my favorite image editing application. I'm not sure now much it'll effect me, as I'm not loading Photoshop images with more than 200 layers, but it's nice to see that it's getting fixed, and all these fixes will be going into 10.8 Mountain Lion this Summer.

I'm glad that it's all coming together today - a few updates, a building of boost, and then I'm starting to feel like the day hasn't been a waste.

I wanted to add in threading to DKit, but in order to do that I needed a threading model, and I had no desire to use straight pthreads, nor to include all I needed to encapsulate pthreads into a decent threading library. So I decided to give boost on OS X a try. I didn't want to use the Homebrew stuff as it's an entire package maintenance system, and I didn't want to even go near MacPorts. So I decided to do a simple boost install myself.

Turns out, it's exceptionally easy.

First, simply get the latest package from the Boost web site. Then put it in a directory - any directory, and then run the following:

  $ cd path/to/boost
  $ ./bootstrap.sh
  … some config output …
  $ sudo ./b2 architecture=x86 address-model=32_64 install

And what you'll get is everything built as 32- and 64-bit universal binary libraries and deposited in /usr/local/include/boost and /usr/local/lib. It's all there, and it's trivial to uninstall:

  $ cd /usr/local/include
  $ sudo rm -rf boost
  $ cd /usr/local/lib
  $ sudo rm -rf libboost_*

What could be more simple?

At this point, you can write simple little apps that use boost:

  #include <string>
  #include <boost/unordered_map.hpp>
 
  int main(int argc, char *argv[]) {
    boost::unordered_map<int, std::string>   a;
    a[4] = "yoyo";
    return 0;
  }

and then simply compile them without any unusual flags:

  $ g++ boost.cpp

Because it's all in /usr/local/include and /usr/lib - GCC automatically finds them. Sweet!

Now I can get to adding those threading ideas to DKit.

[5/23] UPDATE: if you plan to do any debugging, you need to make sure that the built shared, debug, versions of the libraries are available to you. This is easily done with the following after you build:

  $ cd path/to/boost
  $ sudo chown -R your_login:staff bin.v2

When the build is done as 'sudo', the directories created are all owned by root. You just need to revert them to you, and then gdb works wonderfully.

I just noticed that the Google Chrome team has released a new dev version: 20.0.1130.1, and the release notes say that it's focusing on a new version of the V8 javascript engine (3.10.8.4), and a raft of stability fixes. Glad that they are still working on things, but it's been a while since I've seen a really new feature or capability released that even remotely impacts me. Still… it's to be expected, really. The browser has become stable. There's HTML5, and it's widely supported in WebKit, and that's in Chrome, Safari, and many others. It's just not that dynamic a platform any more. And that is good news. Stable platforms are nice to write for.

I know it's a long shot to say the least, but I saw in the GitHub RSS feed about how they use Pull Requests for their work flow, that they had open jobs. I really like what they are doing, and thought Why not? and sent it in.

I don't expect a lot, but I do have to say that GitHub is one of the most amazing places I've heard about in recent years. It's very decentralized, and the work they are doing is just amazing to me. So I figured it's only a few minutes to write a nice email, send my resume, and hope for the best.

Like I said, I'm not expecting a lot, but it was fun thinking about the possibilities.

I had no idea it'd be this hard to find a new job. Others with a lot less experience are finding jobs faster. In fact, a lot of folks that got laid off from PEAK6 have already found jobs. Yet I haven't. Maybe it's me. Maybe it's just not my time. I really don't know, but it's certainly a test of faith to keep my spirits up in these trying times.

It's effected my writing here, that's for sure. I had no idea how much it might be effected, and for a few days there, I was back on track - writing code for an iOS/OS X library and having a lot of fun with XML-RPC and PHP. It's not that I thought it'd be a million dollar idea, but it was a lot of fun getting into ARC in OS X 10.7 and seeing how it plays out as opposed to the old retain/release work that I've been used to using on OS X.

There was also a lot of fun learning the ins and outs of the XML-RPC implementation built-in to PHP, and how simple it was to really make something quite powerful and easy to use. Lots of fun.

But then I pretty much ran out of ideas to keep myself busy.

Sure, I added a few new lockless data structures to DKit, and that was nice - but without a common thread library, I can't really go a lot further with this library. I'm not going to attempt the lockless list or map - Intel's TBB already has those. And there's no reason to create a spinlock - boost and TBB have them already. So I'd just be duplicating code from someone that's probably done a lot more work on it than I have.

So I'm trying to find something to make the time pass quickly between calls to recruiters and waiting to hear back from companies. I know it'll end soon. I have faith that this can't go on forever. It's just making the best of a bad time that's challenging.

I'm glad I at least have the faith.