What's it all about, Alfie?

This morning I noticed that Google Chrome dev 21.0.1180.0 was out with several changes for the Retina MacBook Pro as well as the latest V8 javascript engine. These are really nice updates, but what I noticed right off is the mistake in the rendering with the previous version left a slight tell-tale horizontal line in the background every "page" or so. It wasn't horrible, and wasn't even directly repeatable all the time, but it was somewhere on the page, and it was enough that it made me wonder if my machine was bad.

So it seems to be gone, and that's great news, but so are all the other fixes. These HiDPI changes are nice for a lot of people getting the new MacBook Pros, and one day I'm sure I'll have one too… but it's not where I'd hoped Chrome were adding features right now. But that's OK… it'll all work out I'm sure.

UPDATE: Spoke too soon:

Interestingly enough, these disappear if I scroll this section out of range, but will return to another location on the page if I just keep scrolling. Nasty bug, but it's in Chrome, and I'm not going to worry too much about them fixing it. They'll get to it - just like they did with the rendering of the Finance page on Zoom.

[6/22] UPDATE: this morning I see 21.0.1180.4 is out and this time, they say they fixed several "alignment issues", and I'm hoping they mean these lines. They also put in the V8 javascript engine 3.11.10.10, which is nice. I'm hoping these lines are gone.

This afternoon I wanted to get a few things going on the new Rackspace Cloud Server Joel had reconfigured to run Ubuntu 12.04. Specifically, I wanted to get the latest JDK 1.6.0 installed on the box as we need that for Mingle, which is the point of all this reconfiguration and such.

As it turns out, it's not that bad you just have to know where to go and what to get, and what to do with it. Isn't that the same thing with all new software for linux? Yes.

OK, first, get the latest JDK 6 download from Oracle here. Then it's a simple matter of unpacking it:

  $ chmod +x jdk-6u32-linux-x64.bin
  $ ./jdk-6u32-linux-x64.bin

Then you need to move that to someplace useful. For me, that's /usr/local and then make a few symlinks to make it easy to upgrade:

  $ sudo mv jdk1.6.0_32 /usr/local/
  $ cd /usr/local
  $ sudo ln -s jdk1.6.0_32 jdk1.6
  $ sudo ln -s jdk1.6.0_32 jdk

Then we can put it into the path using the alternatives system on Ubuntu 12.04:

  $ sudo update-alternatives --install /usr/bin/javac javac /usr/local/jdk1.6/bin/javac 1
  $ sudo update-alternatives --install /usr/bin/java java /usr/local/jdk1.6/bin/java 1
  $ sudo update-alternatives --install /usr/bin/javaws javaws /usr/local/jdk1.6/bin/javaws 1

and then set the default JDK (if needed):

  $ sudo update-alternatives --config javac
  $ sudo update-alternatives --config java
  $ sudo update-alternatives --config javaws

Finally, we can verify that the JDK was installed properly:

  $ java -version
  java version "1.6.0_32"
  Java(TM) SE Runtime Environment (build 1.6.0_32-b05)
  Java HotSpot(TM) 64-Bit Server VM (build 20.7-b02, mixed mode)

Today I needed to create a few new users on a fresh Ubuntu 12.04 install from the command line. Thankfully, I was in as root, so all I needed were the commands to get these accounts set up and ready to go. For each account I did the following steps - doing them twice for the two accounts isn't all that hard to do.

First, create the user (and make the home directory if not there):

  $ useradd -m drbob

next, change the password on the new account:

  $ passwd drbob

next, change the default login shell for the account: (/bin/bash)

  $ chsh drbob

finally, add the user to the sudo group so this user can, well… sudo:

  $ adduser drbob sudo

At this point, I was able to login, make sure I was there, then tar up my .ssh directory and what I needed from my Ubuntu 12.04 home directory on another box, and put it all on the new server with a simple sep command.

When I logged in next, it was all there and I was ready to go. Sweet!

This morning I saw that Apple had updated Java to 1.6.0_33 for OS X Lion (10.7), and while I know in the back of my mind that Java is now in the hands of Oracle, and for Mountain Lion (10.8), I'm going to have to be at the complete mercy of Oracle for Java, I'm secretly hoping that some folks at Apple see that it's in their best interests to keep Java in Apple's hands.

To me, Oracle is a database company, and a very specialized one at that. Sun was desperate to sell out to them, and in that I wish they hadn't. I'm not at all sure about the Java coming out of Oracle. Maybe it's OK, maybe it's only part of the JVM/JRE - hard to say. I just wish Apple hadn't passed on Java for OS X like they did. Makes me nervous.

This morning I finished up work on a conflation queue for DKit. The idea is pretty simple - take a queue and a trie, and based on the key value for the elements in the trie, allow updates to the values still in the queue, but keeping their relative placement in the queue such that when they are popped off, the latest value is pulled off, and the element is considered removed from the queue. It's a very common thing to have in processing market data when you don't need every tick, but what you do need is the very latest information when you can get it. Such would be great for risk systems, but not so great for execution systems - depending on the strategy.

Anyway, the key to all this was really that I had all the elements of the conflation queue in DKit - I just needed to bring them all together. For instance, since it's a FIFO queue, we based it off the FIFO superclass, and it's template signature supports this:

  namespace dkit {
  /**
   * This is the main class definition. The paramteres are as follows:
   *   T = the type of data to store in the conflation queue
   *   N = power of 2 for the size of the queue (2^N)
   *   Q = the type of access the queue has to have (SP/MP & SC/MC)
   *   KS = the size of the key for the value 'T'
   *   PN = the power of two of pooled keys to have in reserve (default: 2^17)
   */
  template <class T, uint8_t N, queue_type Q, trie_key_size KS,
            uint8_t PN = 17> class cqueue :
    public FIFO<T>
  {
  };
  }  // end of namespace dkit

The idea is simple: you have to know:

• What to store - this is the type of data you're going to place in the queue, and if it's a pointer, then the conflation queue is going to automatically destroy the old copies when new values come in and overwrite the old
• How many to store - this is a maximum number, as we're using the efficient circular queues. In practice, this isn't a real limitation as memory is pretty cheap and a queue meant to hold 2¹⁷ elements is not all that expensive
• The type of access - this is so you can control how many producers and now many consumers there are going to be. This is important as you can get higher performance from limiting the producers and consumers.
• The key size of the trie - this is really what you're going to use to uniquely identify the values you are putting in the queue. If you know how you'll identify them, then you can choose the correct sized key to make that as efficient as possible.
• (Optionally) The size of the pool of keys - this implementation allows for a set of pooled keys for the queue. This is nice in that you don't have to worry about getting keys into or out of the queue, but in order to be as efficient as possible, it makes sense to have a pool of them around. This optional parameter allows you to specify how many to hold onto at any one time.

Things went together fairly well because I had all the components: the different queues, even how to use the different access types in the pool. I had the pool, and so it was just a matter of putting things together and testing them out.

One thing I did find out was that when I call key_value() I'm not sure what exactly I'm going to be getting back. If we assume that we're using a key structure like this:

  struct key_t {
    uint8_t    bytes[KS];
  };

and the reason being is that we want to be able to create and destroy these without having to put the array form of the delete operator, then we can't simply do this:

  key_t      *key = _pool.next();
  if (key == NULL) {
    throw std::runtime_error("Unable to pull a key from the pool!");
  }
  // copy in the value for this element
  *(key->bytes) = key_value(anElem);

because the compiler is going to think that the LHS is just a uint8_t and not a series of bytes, capable of holding whatever is returned from key_value(). We also can't do this:

  // copy in the value for this element
  memcpy(key->bytes, key_value(anElem), eKeyBytes);

because the return value of key_value() is a value and not a pointer. So we have to be a little more involved than this. What I decided on was to use the fact that the compiler will choose the right form of the method and function, so I added in setters to the key:

  struct key_t {
    uint8_t    bytes[KS];
    // these are the different setters by size
    void set( uint16_t aValue ) { memcpy(bytes, &aValue, 2); }
    void set( uint32_t aValue ) { memcpy(bytes, &aValue, 4); }
    void set( uint64_t aValue ) { memcpy(bytes, &aValue, 8); }
    void set( uint8_t aValue[] ) { memcpy(bytes, aValue, eKeyBytes); }
  };

and with this, I can say:

  key_t      *key = _pool.next();
  if (key == NULL) {
    throw std::runtime_error("Unable to pull a key from the pool!");
  }
  // copy in the value for this element
  key->set(key_value(anElem));

and the compiler will pick the right set() method based on the right key_value() function the user provides. This is not as nice as simply copying bytes, as there's a call here, but it's not horrible, either. I need it to make the code simple and make it work.

Other than that, things went together very well. The tests are nice, and it's all ready to be hammered to death in a real setting. I'm so happy to have gotten to this point in DKit. These things took me a long time to get right before, and they aren't nearly as nice as what I've got now, and these will be out there for me to use no matter what. That's a very nice feeling.

This morning saw that there was an update to Google Chrome dev to 21.0.1171.0, and I needed to get it and check to see if they had gotten my bug report on the rendering of the Google Finance page. As I pulled it up, I was very happy to see that they had, indeed, fixed the problem. It seemed to be related to the zoom out level, but I can't be sure. In any case, it's nice to see the fix back to the way it was.

The release notes don't say a lot, but that's OK. The proof is in the rendering.

Today I spent a good chunk of time writing a 64-bit key trie as the next basic component of re-writing the exchange feeds in a lot better component library than I had previously written. The purpose of the trie is to have a lockless storage mechanism that has very fast insertion and access methods. The last version I'd written was based on a specific element being stored - a pointer to a Message. In this version I wanted to be able to store any template type - including pointers, and handle the disposal as needed.

I've made adjustments like this for the dkit::pool where I handled plain-old-datatypes as well as pointers, and disposed of the pointer values properly. I needed to be able to do the same thing for the trie.

The second improvement this time around is to stop trying to make the trie do everything associated with processing of its contents. In the past, I'd had the trie scan the Messages for symbol limits, values, etc. This was very inefficient, as it was all in the trie, and therefore very specific. I needed to move away from this and use functors that could be passed into the trie, and then operated on each of the valid elements in the trie. This is a far better scheme as it allows the user to make any processing on the Nodes in the trie, and this is far more flexible than trying to implement the methods in the trie itself.

The solution to this was to define a class within the templates trie so that I could create functors like this:

  class counter : public dkit::trie<blob *, dkit::uint64_key>::functor
  {
    public:
      counter() : _cnt(0) { }
      virtual ~counter() { }
      virtual bool process(
          volatile dkit::trie<blob *, dkit::uint64_key>::Node & aNode )
      {
        ++_cnt;
        return true;
      }
      uint64_t getCount() { return _cnt; }
    private:
      uint64_t     _cnt;
  };

They are easy to create, and you can apply them to all the elements in the trie with a simple call:

    counter    worker;
    m.apply(worker);

The final improvement was to switch from loop-based indexing into the trie to recursion-based accessing. There are a few reasons for this - but the most is flexibility and code simplicity. When you have a fixed key length, and you use looping to traverse the trie, you have a fixed series of nested for loops. This seems all well and good, but it makes for a very fixed structure and the code isn't all the easy to read.

By going with a better class structure for building the trie, we're able to take advantage of recursion, and then the only parameter to the "depth" of the trie, and the corresponding size of the key, is the number of branches used in the construction of the tree in the trie. If we put the parameter in the creation method then there's a single point where we stop creating branches, and instead make the leaf nodes. From this point, the same code that traverses a 64-bit key trie works for a 128-bit trie.

At least insofar as the movement in the trie.

Once I got it all working, the next thing was to look at the recursion vs. looping design. I wanted to make sure that I had the most performant design. What I found was that the recursion was about 25% faster than the looping structure. I'm guessing it's due to tail-recursion optimization by the compiler, but I'm not positive. I repeated the tests, and the difference is real, that's good enough for me.

Once it was all done, I wondered how hard it might be to make the key size another parameter in the template. Well… since we're using recursion, and therefore, the size of the key space is only used in one space, the solution was pretty simple. Start by defining the different sizes we'll accept:

  namespace dkit {
  enum trie_key_size {
    uint16_key = 2,
    uint32_key = 4,
    uint64_key = 8,
    uint128_key = 16,
  };
  }      // end of namespace dkit

and then we convert this to the test we need in the branch creation:

  enum {
    eLastBranch = (N - 2)
  };

In the code, we then have:

  virtual volatile Node *getOrCreateNodeForKey( const uint8_t aKey[],
                                                uint16_t aStep )
  {
    volatile Node   *n = NULL;
 
    // get the index we're working on (re-used a few times)
    uint8_t     idx = aKey[aStep];
    Component   *curr = __sync_or_and_fetch(&kids[idx], 0x0);
    if (curr == NULL) {
      // create a new Branch or Leaf for this part of the trie
      bool    createBranch = true;
      if (aStep < eLastBranch) {
        curr = new Branch();
      } else {
        curr = new Leaf();
        createBranch = false;
      }
      // throw a runtime exception if we couldn't make it
      if (curr == NULL) {
        if (createBranch) {
          throw std::runtime_error("[Branch::getOrCreateNodeForKey] "
                   "Unable to create new Branch for the trie!");
        } else {
          throw std::runtime_error("[Branch::getOrCreateNodeForKey] "
                   "Unable to create new Leaf for the trie!");
        }
      }
      // see if we can put this new one in the right place
      if (!__sync_bool_compare_and_swap(&kids[idx], NULL, curr)) {
        // someone beat us to it! Delete what we just made...
        delete curr;
        // ...and get what is there now
        curr = __sync_or_and_fetch(&kids[idx], 0x0);
      }
    }
 
    // now pass down to that next branch the request to fill
    if (curr != NULL) {
      n = curr->getOrCreateNodeForKey(aKey, (aStep + 1));
    }
 
    // return what we have dug out of the tree
    return n;
  }

This little test allows us to place the key size as a parameter to the template, and that makes it very easy to make different sized keys. For convenience, I added in the convenience methods to deal with the different sized keys from the contained values. It's not strictly necessary, but it'll make using the template class a lot nicer.

I was a little shocked to see that Google Chrome dev has a serious rendering bug in it. I think it's most obvious (to me) on the Google Finance page, but I'll bet it's a lot of places. The blocking for the graphs is way off for the page. Hugh blank spaces in the layout should have been filled up with content:

I'm sure they have people working on it now, as I can't have been the first person to notice this, but it's a little surprising still… I find it hard to believe this got through Q/A. Or even simple checks of common web sites - like their own!

I have been thinking about decommissioning my wonderful G5 iMac, as I just don't use it any more, and pulling a spare Gateway laptop out of the closet and installing the latest Ubuntu release for a platform to test DKit on in a more generic C++/linux environment. My iMac has been a blast. It's been with me for a long time, and I've really done a lot of great things with it. But the truth is that with Mac OS X 10.7 or even 10.6 running on it, it's long in the tooth, and there's no real need to keep it around. It's not hitting the dumpster, but I've got very limited desk space these days, and it really makes more sense to have the Ubuntu machine on the desk than the iMac.

So today's the change.

Last night I downloaded the Ubuntu 12.04 32-bit and AMD64 distributions and burned them onto DVDs. I think CD's would have worked, but I didn't have any, and a spindle of DVDs is something we almost never go through, so it was easy to burn off two copies. I'm glad I got both, as I remembered that the laptop in question had an AMD64 CPU in it, and so I'll be able to make the 64-bit and 32-bit libraries for DKit. Also, I'm sure I'll be able to fire up WindowMaker on Ubuntu 12.04, as I had it working on Ubuntu 10 at my last job. So all in all, it should be just what I wanted to test out the builds and compiles of DKit.

The boot directly into Ubuntu 12.04 is nice, but it might have been nice to have been given the option of boot or install a little earlier in the process. Here nor there, it's up, and this is not fast hardware, so I'm willing to cut Ubuntu a lot of slack here. It's nice that it has to run/install option, and so easy to get going.

I've been doing a lot of linux installs in the last decade, and they all have come to the point that a nice GUI is standard. I think Ubuntu's installer is no different. I do think that the use of the twitter feed on the install screen is very clever. It's an easy way to see what's happening, and what people are saying about Ubuntu as you're waiting for the files to copy and download. Clever.

Interesting Installation Challenges

The first thing I ran into is that sshd is not enabled by default on Ubuntu 12.04 - so I had to google how to install it:

  $ sudo apt-get install openssh-server

Once I had sshd installed on mao, I was able to log in from my MacBook Pro and move over my ~/.ssh directory so I could have my keys. After that, I needed to make sure that I had Vim:

  $ sudo apt-get install vim vim-gtk

then I moved over my .vimrc, and ~/.vim directory. In order to use the gists from Vim, I needed to have curl:

  $ sudo apt-get install curl

and then to have nice bitmapped fonts, I needed to remove the "don't" condition on them and regenerate the font table:

  $ sudo rm /etc/fonts/conf.d/70-no-bitmaps.conf
  $ sudo dpkg-reconfigure fontconfig

I certainly needed to have the compilers and source control tools:

  $ sudo apt-get install g++
  $ sudo apt-get install libboost-all-dev
  $ sudo apt-get install git

And then finally, I wanted to have the 'dev' channel of Goggle Chrome:

  $ sudo dpkg -i Downloads/google-chrome-unstable_current_amd64.deb
  $ sudo apt-get install libxss1

One thing I noticed is that the motd was a little verbose, and I wanted to trim it up. Turns out in Ubuntu 12.04, it's a symlink to /var/run/motd, so I needed to do a little to set things up right. First, copy the motd to motd.static, then relink the /etc/motd to the static version, and finally edit the static version for content:

  $ sudo cp /etc/motd /etc/motd.static
  $ sudo rm /etc/motd
  $ sudo ln -s /etc/motd.static /etc/motd
  $ sudo vi /etc/motd.static

With this, I get the leaner and cleaner motd and things are good again. I just wanted to put all this here so I had something to work off of, if I decided to do this all again.

After I got all this down and installed, I was able to go to work on making sure DKit compiled and ran on Ubuntu 12.04. It wasn't all that hard, but there was one thing I was a little surprised about. In LLVM gcc 4.2.1 I was able to have the following struct and use it in the boost::unordered_set container:

  typedef struct {
    boost::thread   thread;
    auint32_t       use_count;
  };

But gcc 4.6.3 on Ubuntu 12.04 didn't like this at all. It didn't like the default constructor or the default copy constructor. What I needed to do was to explicitly include them in order to make the compiler happy:

  typedef struct base_thread_info {
    mutable boost::thread   thread;
    auint32_t               use_count;
    /**
     * We should throw down the default constructor and copy constructor
     * as the boost container is going to need these, and we can't allow
     * the thread itself to be copied. That's just not right. So we mask
     * that and just let the count be copied. This isn't great, but we
     * have to have this capability, and this is the simplest way to
     * make it work.
     */
    base_thread_info() :
      thread(),
      use_count(0)
    { }
    base_thread_info( const base_thread_info &anOther ) :
      thread(),
      use_count(anOther.use_count)
    { }
    virtual ~base_thread_info()
    { }
  } thread_info;

The problem appeared to be that the copy constructor for the boost::thread was private, and that meant that we couldn't just "use it". In this case, we didn't even try, and that was OK. We aren't really trying to copy these, anyway, but the container needed to have this so that it could create and then copy into, as needed.

Interesting, but it's all cleared up now. Good.

[6/6] UPDATE: I forgot about PostgreSQL, PHP and Apache on the box. In order to get these guys going, I needed to install the relevant packages:

  $ sudo apt-get install postgresql-9.1
  $ sudo -u postgres createuser --superuser $USER

This gets me PostgreSQL installed, and me as a super user on the database instance - as long as I log in from the box. It also starts up the instance with the default parameters that are good enough for what I need at the moment. If I need to mess with the security permissions later, that's OK. But I think it's pretty much default behavior for now.

Then I needed to get Apache, PHP, and include the integration pieces for these so that they all work together:

  $ sudo apt-get install apache2
  $ sudo apt-get install php5 libapache2-mod-php5 php5-pgsql
  $ sudo /etc/init.d/apache2 restart

In order to get rid of an annoying warning, I needed to make a config file with the fully qualified domain name of the server:

  $ cd /etc/apache2/conf.d
  $ sudo vi fqdn

and include the single line:

  ServerName mao.themanfromspud.com

and then restart apache again. At this point, a simple info.php file shows that I have everything up and running and it's all wired up so that it all works from within apache web pages and PHP. Nice. Now I'm ready to do the other XML-RPC work I've got going right now.

This morning I wrote a simple, yet effective, UDP transmitter for DKit. The idea is simple - if we have a UDP receiver for datagrams, then it makes sense to have a transmitter of the same. Simple make it a subclass of the sink and we should be ready to go. We can have it share io_service threads like the receivers, but since the transmitters have a slightly different usage on the io_service threads, it's probably a good idea to leave them separate for now.

We can certainly make a simple io_service base class for both the receiver and transmitter and pull these into this base class if we need to, but since the transmitter's need to have a boost::io_service::work defined for them - lest the io_service's run() method return too quickly due to nothing to do, it's different than the receivers, and simple enough to pool on the transmitters, as needed.

The one trick was the virtual template classes problem that I solved previously. I do not want to make the inclusion of the UDP transmitter require that the user know what type to use, so I made a very simple, and very clean subclass that then becomes the basis of the UDP transmitter:

  namespace detail {
  template <class T> class basic_udp_transmitter :
    public sink<T>
  {
    public:
      basic_udp_transmitter() { }
      virtual ~basic_udp_transmitter() { }
 
      /**
       * This is the main receiver method that we need to call out to
       * a concrete method for the type we're using. It's what we have
       * to do to really get a virtual template class working for us.
       */
      virtual bool recv( const T anItem )
      {
        return onMessage(anItem);
      }
 
      /**
       * This method is called when we get a new datagram, and because
       * we are expecting to instantiate this template class with the
       * type 'T' being a <datagram *>, this is the method we're expecting
       * to get hit. It's just that simple.
       */
      virtual bool onMessage( const datagram *dg )
      {
        /**
         * This method will be overridden by the specialization of
         * this template class.
         */
        return true;
      }
  };

and then the main class looks like this:

  class udp_transmitter :
    public detail::basic_udp_transmitter<datagram*>
  {
 
    // …
 
    /********************************************************
     *
     *                Processing Methods
     *
     ********************************************************/
    /**
     * This is the specialized template method that will be called from
     * the generalized recv() method, above, and will, in fact, be the
     * place where we do all the work of sending out the datagram to the
     * UDP multicast channel.
     */
    virtual bool onMessage( const datagram *aDatagram );
 
    // …
 
  };

At this point, it's easy to use the udp_transmitter because I've wired it all up to send the datagrams out via boost ASIO:

  udp_transmitter  xmit(multicast_channel("udp://239.255.1.1:30001"));
  rcvr.addToListeners(&xmit);

The threads are all handled in the same manner as the UDP receiver, so we know they are clean with the reference counting and the clearing of the sockets. It's a nice, clean implementation. You just need to wire it up to a source and it's going to send out those datagrams as they arrive.

Sweet.

It's nice to get this done and really get the next cut of the library done. It's now got receivers and transmitters, and I can build on these as needed or add in more receivers and transmitters (ZeroMQ, etc.) as needed.