Archive for October, 2008

Distributed version control systems

Friday, October 31st, 2008

One of the projects I’m working on right now involves two developers in different continents.

For various reasons it would be awkward to set up a proper source code repository on a mutually accessible server, so instead I’m experimenting with a distributed version control system: Mercurial. For those who haven’t come across these before, the idea is that each developer has their own complete repository. Into this repository they check in their own changes. They can also ‘pull’ changes from anyone else’s repository.

There are no restrictions on where you can pull changes from, nor the order in which you take them (apart from the inevitable merging pain if you do something illogical).

So far, it’s looking really good! What’s really surprised me is how similar the command-line syntax is to Subversion. If you’re familiar with Subversion, you might want to try playing with Mercurial, as I think distributed systems are probably going to be the way of the future…

PS it will be interesting to see what the Symbian Foundation does for this sort of thing.

How to parallelise Symbian programs without changing the code

Thursday, October 23rd, 2008

The Smartphone Show this year seemed to have a lot of emphasis on different types of ‘runtime’ which can be used on Symbian phones. In this instance a ‘runtime’ seems to mean any programming environment: be it native Symbian C++, Java, Flash, Python or even AJAX stuff in the browser.

There was also a lot of emphasis on multi-processing, since it seems pretty clear that SMP is going to be the best way to save power on phones in the future. (Two slow processors use less power than one fast one).

Symbian OS provides all the usual techniques for multi-processing: threads, semaphores, and mutexes. Yet we all know these make programming difficult. So here are some miscellaneous thoughts on other things which could be done.

A declarative run-time

I tend to think that, as we get to a world with dozens or hundreds of cores on the desktop, we programmers are going to have to give up on issuing specific sequences of instructions, and instead just describe the desired relationships between our variables. The runtime then figures out how to calculate this based on the available hardware resources.

Such a scheme requires these relationships to be described in a functional or declarative programming language like Haskell. Maybe we need a Haskell runtime for Symbian OS?

I can imagine that working quite well to calculate the screen image of a game, for example. But interfacing with the rest of the system would probably need to be done using traditional programming techniques.

Software transactional memory

STM is an alternative to locks. In short, you just go ahead and make your writes to memory, and if they conflict with somebody else’s writes, the system will roll them back.

Ideally we need a paging system which somehow makes copies of pages automatically for each thread, and only merges them together upon a commit.

Parallelising active objects

Most Symbian OS programmes are specified as a series of active objects, which define how the thread responds to certain incoming events. A parallelised active scheduler could simply distribute the active objects across multiple threads in order that they can run in parallel on multiple cores. But, there would need to be restrictions: it’s always been assumed that active objects run one-at-a-time, and hence there’s no need for locking of data structures. Either all active objects would need to use locks whenever accessing potentially shared data structures, or each object would need to be annotated to give rules about which ones the scheduler could run simultaneously.

Still, the fact that Symbian programmes do have this semi-declarative way of saying what code to run in response to which stimulus does give them an advantage over other operating systems where event loops can be structured in myriad ways. It does open the door to thinking about parallelising programs automatically.

In practice, I think it’s probably hopeless. Except…

Paralellising active objects + software transactional memory

If you imagine each active object as a single transaction in STM, then each one can run independently, operating on its own copy of the data. When the active object has completed, if no other active object has operated on the same data, then its changes are committed. Otherwise, they’re reverted and the active object is run again.

Then, the restrictions needed get much less: just making sure each active object doesn’t do any input/output operations (otherwise it can’t be reverted). (Non-blocking operations can simply be postponed until the transaction is committed).

So, all we need to do, is find a way to annotate the behaviour of active objects like that; implement a paging scheme and APIs for STM, and write an active scheduler which can distribute active objects across threads… and suddenly we have a way of parallelising all existing Symbian programmes.

Ha ha ha. Of course there are millions of complications. But it’s interesting to muse.