Archive for June, 2012

Nokia’s Big Drop

Thursday, June 14th, 2012

They started the day off with bad news, and it just hurt. Ouch! Nokia is not looking very happy right now. They reported this morning that they are cutting 10,000 jobs - 20% of their workforce, and closing three research facilities. Then this happened:

Nokia Drop

It's a bad day for Nokia.

Which leads me to wonder what they'll be doing with NAVTEQ - the mapping company they bought not too long ago. If it's making money for them, then they might bleed it dry. I doubt they'd sell it as it cost them a bundle and they need the cash to stop the hemorrhaging. I hope things stabilize for them. And soon.

Refreshed My Web Site

Thursday, June 14th, 2012

Today I spent time scouring the web looking for the basis of a good HTML/CSS design for my web site. I know my limitations, and designing a nice web site is one of them. But if you can get me close, I can fine tune things to be exactly what I want them to be. So it happens that I came across the Minimalist theme, and I was off to the races.

Bob Beaty Home

This is a lot more professional looking than the old "fields of dreams" style that I was using for more than a year. Probably more than two. In any case, it wasn't as processional as I wanted. I wanted a clean interface. Something that was not a fixed width. I wanted a lot of white, and very little graphics. There's no need on my personal site - it's just the information in a nice, easy-to-read format.

I'm very pleased with the design, and while I was in the pages, I added a few things like a complete page for DKit including the links to GitHub where they can get the code. I wanted to have the site be more of a showcase than it was. I think it's looking a ton better already.

Nice upgrade.

[6/20] UPDATE: this morning I went back in and fixed up a bit of the CSS to make it look quite a bit nicer. There were a lot of named class values that just didn't exist in the CSS, and I'm thinking it was planning as opposed to oversight, but we'll never really know. It's looking a lot better now, and that's what matters.

Java 1.6.0_33 Update from Apple

Wednesday, June 13th, 2012

Software Update

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.

Worrying About Friends

Wednesday, June 13th, 2012

This morning I'm a little concerned about a good friend of mine. I've known him for more than a decade, and he's never been someone that I worried about - until now. I was chatting with him this morning when he dropped this one on me:

I'm expecting to get fired sometime this year.

and when I asked him why on earth his company of more than 5 years would dump him, he said:

They'll fire me when they decide that I am an obstructionist.

That doesn't sound like him at all. Not in the least.

He's never been one to do something negative or bad without a solid reason for doing it. He's just not that emotional a guy. I'm the emotional one. I'm the one that gets fired for being extreme. Not him. So I'm really concerned about my friend.

I'm not one to give advice to anyone - I learned my lesson decades ago. I'm more of the "there are too many sides to a story to know what's right", so I just try to support my friends and let them know that they have a friend in me, even if it seems to them that they are in the middle of a huge, black hole.

I'm going to hope it's temporary with him… that it's just a string of bad days, and maybe a little stress from home. We've all felt it. We allow our work lives to define the life we think we have. I know I'm guilty of that. This forced time off has been wonderful for me to realize that I have a life outside of work. It's been painful, but I'd like to think that I can take this painful part of life and extract some useful lessons from it as well.

I sure hope my friend does too… I'd hate to see him go through what I've gone through. But if it's going to go that route, I'll be standing right there beside him letting him know that he's not alone.

No one should be alone.

Has Facebook Finally Stabilized?

Tuesday, June 12th, 2012

I'm looking at the chart of Facebook, and I'm thinking that maybe it's possible that it's stabilized out in the middle to upper 20's range. It had to stabilize at some point, and this looks to be a nice solid run for a couple of days, so maybe so… I'm sure there are a lot of folks that want it to.

Facebook Stable

There are plenty of ways to make a system exist, for a short time, in a state of dis-equilibrium… hype is certainly one of them. But in the end, the system will adjust to all factors, and achieve it's equilibrium. Feedback - it's a great thing.

Built Templated Conflation Queue in DKit

Tuesday, June 12th, 2012

DKit Laboratory

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 217 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.

iPhoto, iMovie, Thunderbolt – Lots of Updates from Apple

Tuesday, June 12th, 2012

Software Update

This morning I saw that there were updates to iPhoto, iMovie, Thunderbolt drivers, and even the AirPort stuff… so of course I had to update all that. This is nice, but I'm not really using iPhoto all that much, and I haven't had the time or material to really get into iMovie, so the updates are really just so-so to me. But what wasn't so-so was the reboot.

For the first time ever, when I logged back in, BBEdit was back in the right place on Spaces. Xcode was too. The only exception was MacVim. Everything else was back in place and just where I left it. This was awesome!

The updates in OS X Lion that started this "clean reboot" were really nice, but a few apps never really worked with it, and BBEdit was one of them. It'd restart, but it wouldn't put the windows back where they "came from". It wasn't a horrible issue, but there were just a few apps that didn't do it right. Well… no more.

Now BBEdit and Xcode are back where they were, and the only thing I have to do is get back into the directories I was in with my Terminal.app sessions. Too bad they don't save that, but who knows? Maybe they will in 10.8?

Google Chrome dev 21.1171.0 is Out – Fixes Finance Rendering

Tuesday, June 12th, 2012

Google Chrome

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.

Adding a Flexible Sized Key Templated Trie to DKit

Saturday, June 9th, 2012

DKit Laboratory

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.

Facebook Continues It’s Amazing Opening Slide

Monday, June 4th, 2012

Facebook

I was talking to a friend on chat this morning, and he pointed me to some code on GitHub that supposedly comes from Facebook, and has some interesting data structures designed for very high performance on highly threaded applications. It's similar to DKit, but larger, and I had a look at what was there. It's not that it's bad, but it's Facebook, and there's still something about that place that makes me think of Used Car Salesmen, and not in a good way.

While this code base has some interesting things, it's nothing that I haven't seen in TBB and other places, or that you could make with a simple TBB read/write spin lock, and a simple STL data structure. But it got me to thinking, and so I checked this morning, and the Facebook slide continues:

Facebook Slides Again

It's hard to get behind a company, and a person, that seems to act with such arrogance, and at the same time is in the middle of such a horrible IPO. I mean I'm betting there are people in Facebook that are close to jumping out the windows a la 1929. There are governmental investigations, lawsuits filed, and the stock still keeps sliding.

As some point, it has to match the real value of the company and stop, but I have no idea where that is. They have a ton of code (IP), and they have data centers, so it's not like they have no valuable assets - it's just that their valuation is based on their user base and expected returns and growth. But that's not necessarily anything like what the company is really worth.

I just wonder when it'll stop the slide.