Not just high performance Objective-C

Addendum to my article on implementing a high performance Postscript interpreter in Objective-C: not just is performance better, so is accuracy. Despite the fact that we are optimizing the heck out of the Objective-C objects we are using, they still give us encapsulation and polymorphism, allowing us to choose arbitrary representations. For example, most Postscript interpreters use a fixed-size value object (polymorphic in a C-union type of way) that constraints floating point precision to 32 bits. With Objective-C, we have no such constraints, so EGOS floats are actually 64 bit doubles, so running the modified benchmark below in PostView doesn't just yield the result 75% faster than Preview, it also produces it with 7 orders of magnitude less error. Not that that is necessarily important in Postscript, but it is a pleasant side effect and shows the power of combining performance with abstraction.

%!
  usertime
  1000 0 1 10000000 { pop 0.0001 sub  } bind for
  exch usertime exch sub dup ==
  20 20 moveto /Times-Roman 24 selectfont
  100 string cvs show ( ms) show ( error:  ) show 
  1000.0 div 100.0 mul abs  100 string cvs show ( %) show
  showpage

Better HOM selects

Wincent Colaiuta discusses a variant of the select HOM that takes an arbitrary number of argument messages. I like it!

My initial implementation actually had arbitrary nesting, but as he discusses with collect, that requires a trigger message to start, as there is no way of knowing at runtime when the expression terminates. It never occurred to me that this limitation did not apply to select, which can look at the return type of the messages sent and stop when it reaches a BOOL (char).

Nice.

p.s.: the arbitrary nesting is still in the implementation, with each of the collection processing HOMs actually running an enumerator and those enumerators stackable, and this is two of the reasons the implementation is so gnarly: (1) there is extra generality that is not needed and (2) making that more general mechanism run fast was really, really tricky.

p.p.s: He actually discussed it almost a year ago, but I just saw it now.

Reading Helps

James Robertson slams the proposal by the EU free market institute to unbundle the OS from PCs sold in the EU.

I've seen a lot of stupid ideas float past, but this one from the EU's Globalization Institute makes it into the top 5 - only the existence of the RIAA and the MPAA prevent a complete victory for these morons:

[..] The think tank recommended to the EU that all computers be sold without an operating system and sees no reason "why computer operating systems could not follow the same model as computer hard drives and processors."

Yes, installing an OS from scratch is exactly what most buyers long to do - it's such a productive use of their time.

Hmmm, what could they mean with the "same model as computer hard drives and processors"?

Well, of course! We all buy processors and hard drives separately, mount the CPU on our separately purchased motherboard, hook up hard-drive and power-supply and stick it all in a chassis. That *must* be what they meant with that phrase.

Or maybe, they meant that you can configure your computer with different CPUs and hard drives, and have the vendor ship you a machine configured to your specifications, whereas you cannot actually get a computer and not pay the Microsoft tax? Nah, that's just *crazy*:

IT professionals are being forced to adopt Microsoft's operating systems — even if they tell their PC supplier they want a system free of Microsoft software, ZDNet UK's research has revealed.

Oh.

'Thousands' or transistor²

The Alan Kay quote in my previous post made me think of Montecito, the new Itanic version with 1.72 billion transistors. Compare that to the ARM6, which had a measly 35K transistors, including its 4K cache.

Dividing the two numbers gets you almost 50K. That's how many ARM6 CPUs you could get on the same chip with the same transistor budget as the Montecito. A processor for every object. Or viewed another way, more ARM6-equivalents than the ARM6 has transistors. Which begs the question: is the Montecito proportionally as much an improvement in computational capacity as an ARM6 is over a single transistor?

Objective-C future(s)

Via LtU, I got alerted to the fact that theEtoile project now has an implementation of futures. Cool.

However, their implementation has specific objects reacting asynchronously to messages, making it more similar to the actor model,which as they mention is also very much Alan Kay's original conceptual model for Smalltalk:

Bob Barton, the main designer of the B5000 and a professor at Utah had said in one of his talks a few days earlier: "The basic principle of recursive design is to make the parts have the same power as the whole." For the first time I thought of the whole as the entire computer and wondered why anyone would want to divide it up into weaker things called data structures and procedures. Why not divide it up into little computers, as time sharing was starting to? But not in dozens. Why not thousands of them, each simulating a useful structure? [Emphasis mine]

Actors are inherently asynchronous, each actor runs in a separate process/thread and messages arealso asynchronous, with the sender not waiting for the message to be delivered or ever gettinga return value. Of course the actor model also makes all objects active, so the Etoile model, whichonly makes objects of specific classes active, is somewhere inbetween.

Futures, on the other hand, as introduced in MULTLSIP (pdf), tryto integrate asynchronous execution into a traditional call/return control- and data-flow. So messages(or functions in MULTILSIP) appear to have normal synchronous semantics and immediately yielda return value, but when annotated with the future keyword execution of that return valueis done in a background thread and the immediate return value is just a proxy for the value that is still being computed.

In the HOM paper (pdf) presented at OOPSLA 2005, I also describe a Future implementationbased on Higher Order Messaging that comes very close to the way it was done in MULTILSIP. A -futureHOM is all that is needed to indicate that you would like a result computed in a background thread:

  result = [anObject lengthyOperation:parameter];           //  synchronous
  result = [[anObject future] lengthyOperation:parameter];  //  asynchronous with future

I am probably biased, but this seems about as easy-to-use as possible,with all the nasty machinery (worker-queues, lockless FIFOs, etc.)hidden behind a single -future message.

Message-oriented persistence

The good folks at Omni posted an interesting discussion of their persistence strategy for OmniFocus. In short they found that using a database, specifically a CoreData data store, was not exactly ideal for their primary public data format.

Instead, they appear to be using a pattern that Martin Fowler calls EventPoster. After reading David Reed's thesis, I think I prefer to call it message-oriented persistence.

I first stumbled on this pattern when designing a replacement for a feed processor at the BBC. The basic task was to process a feed of information snippets encoded as XML and generate/update web and interactive TV (Ceefax) pages.

Like a good little enterprise architect, and similar to the existing system, I had originally planned to use a central SQL database for storage, though designing a data model for that was proving difficult due to the highly irregular nature of the feed data. As an auditing/logging measure, I also wanted to keep a copy of the incoming feed data, so when the time came to do the first implementation spikes, I decided we would implemented the display, update and XML feed processing logic, but not the datastore. Instead, we would just re-play the feed data from the log we had kept.

This worked so well that we never got around to implementing the central database.

Leaving out the database vastly simplified both our code-base and the deployed system, which I could run in its entirety on my 12" AlBook whereas the system we were replacing ran around a dozen networked machines. Apart from making us popular with our sysadmin team both in terms of reliability and deployment/maintenance complexity (essentially a jar and a working directory was all it needed), a fringe benefit was being able to work on the system on said AlBook while disconnected from the network, working from home or from a sunny patch of grass outside the office.

In addition to personal happiness, systen performance was also positively affected: since we kept our working state completely in memory, the AlBook mentioned outperformed the original cluster by 2-3 orders of magnitude, producing hundreds of pages per second versus taking from several seconds to several minutes to produce a single page.

Performance and simplicity are exactly the benefits claimed for prevlayer, a persistence layer for Java based on the same principles.

TeaTime, the theoretical foundation and actual engine working underneath Croquet, takes this idea to a whole different level: objects do not have state, but are simply names for message histories. This is truly "objects [and messages] all the way down". Turtles need not apply.

More on MPWObjectCache

Now that I've motivated why an MPWObjectCache might be useful, let's go into some more detail as to how it actually works. To follow along, or if you'd rather just read the source code than my ramblings, MPWObjectCache is part of MPWFoundation, which can be downloaded here: http://www.metaobject.com/downloads/Objective-C/.

As I mentioned before, the algorithm for MPWObjectCache is quite simple: there is a circular buffer of object slots. We try to get pre-allocated objects from this circular buffer if possible. If we find an object in the cache and it is available for reuse, we just return it and have just saved the cost of allocation. Two things can prevent this happy state of affairs: (1) we don't have an object yet or (2) we cannot reuse the object because it is still in use. In both cases we will need to allocate a new object, but in the second case we also remove the old object from the cache position.

#if  SLOW_SAMPLE_IMPLEMENTATION_WANTED
-getObject
{
    id obj;
    objIndex++;
    if ( objIndex >= cacheSize ) {
        objIndex=0;
    }
    obj=objs[objIndex];
    if ( obj==nil ||  [obj retainCount] > 1 ) {
        if ( obj!=nil ) {
            [obj release];
        }
        obj = [[objClass alloc] init];
        objs[objIndex]=obj;
    }
    return [[obj retain] autorelease];
}
#else

This is what a naive implementation looks like. A couple of notes on the code:

• objects must be reinitialized by the client (and reinitializable in the first place)
• only one attempt is made to find an object
• the retain/autorelease will prevent the cache from working unless a fairly tight autorelease pool regime is maintained
• there are quite a few message sends
• it's not what is used in production

The effectiveness of the cache obviously depends on your allocation patterns and the size of the object-cache. Larger caches take longer to be filled up before they start wrapping around with the potential for reuse, but smaller sizes can mean that the object will still be in use when we do wrap around. The actual implementation is very similar to the one presented above, except that it does a little more probing and uses IMP-caching for all the messages sent on the critical path. These optimizations ensure that object-caches are no slower than normal allocations even in worst-case situations such as every allocated object being retained. In addition the cache can also be set to not do the retain/autorelease, which is safe when you are pushing objects and have control over the cache:

-doSomething:target
{
 // cache is an ivar
 id obj=GETOBJECT(cache);
 // target does not have access to cache
 [target doSomethingWithObject:obj];
 // obj now either has an extra retain or can be reused
}

This pleasant property is a side effect of the decision to turn the object-cache into an object that can be instantiated and placed in an instance variable, rather than the typical object pools that are implemented as class methods. The class method that maintains such a pool usually has no information about the lifetime of objects, so to be safe such an implementation always has to protect the objects it returns, negating much of the advantage of caching. Similar caveats apply to multi-threading and locking. Those caveats notwithstanding, MPWObjectCache also provides the CACHING_ALLOC macro for creating class-side allocation methods backed by an object cache, which is used in the HOM implementation to reduce the cost of allocating trampolines:

 CACHING_ALLOC( quickTrampoline, 5, YES )

This creates a +quickTramplone method backed by an object cache with 5 entries. The YES flag allows objects to be returned from the cache without the retain/autorelease despite the fact that it isn't one of the safe "push" patterns described above. However, this use is also safe because the trampoline is used only temporarily to catch and forward the message, all of which is code controlled by the implementation. It is no longer needed once any client code implementing the actual HOM is run. So, this is how and why object-caches can make your (temporary) object allocations much, much faster.