Core Architecture

Generalizing version control systems

2011-10-02T16:17:00.001+03:00

Continuing on the version control system ~~hatred~~ criticism topic

When VCS does not fit

On GDCE 2011 I've attended a talk of a guy from CCP Games ("Addressing Human Scalability Through Multi-User Editing Using Revision Databases" by John Rittenhouse) where he told about how they addressed the problem of the artists editing their levels \ galaxies. We in Crytek have relatively small levels, so when artist wants to make some modifications to it he just locks it for exclusive edit in Perforce. Their levels are huge and do not have a distinctive partitioning. In CCP, it is common for multiple artists to make changes to the same level simultaneously, so exclusive locks are unacceptable.

Their solution was to move out from files in Perforce and store levels in MySQL database. To stop artists from messing each-others work they have implemented the object-level locking, so, for example, if one artist moves a box on a level the corresponding row in DB will marked as locked. In level editor other artists will see that this object is being worked on and will not be able to change it. They have traded the file-level atomicity of Perforce for row-level in MySQL, well I guess you've got the idea.

Anyway, the most interesting takeaway from the talk was how they have struggled with this technology to fit it into their production pipeline. First of all, the described approach is similar to working on code without revision control at all, so they have added support for changelists, submits and reverts from the beginning. Then they had a real headache adding branching, but they have only supported a simplified "promotional branching" model where there is only one flow of changes. But their production were moving towards the "mainline branching" (see the slides) so their system could not keep up with this. And, as I understood, at the time of talk this issue was not solved yet. Basically by making this move they have condemned themselves to implement the analogue of Perforce on top of MySQL which is a damn hard thing to do.

VCS hell

In the previous post I've expressed my doubts about having separate version control systems for code and assets, related to how it affects the atomicity of changes and consistency of changelists. Essentially CCP added one more VCS for the level data. This is insane.

I'm not saying that CCP made a wrong move by doing this, in fact I can't think of any simple alternative. But having several VCS is a dead end. In fact CCP guys are aware of this, and, talking to a colleague of mine, mentioned that they had thoughts about using actually putting all their code into MySQL to use it as single VCS.

Solution (?)

So above is one example of requirements that can't be reasonably fulfilled by any of the existing version control system, but I bet it is not the only one of its kind. As an architect (well I like to think of myself as one) when making some, especially spontaneous, decision I always question it from multiple sides "Why this is best?", "How will it work with X?", "How can it be generalized?". And related to contemporary VCS following question always comes to my mind "Why do they have to operate on files?".

Choosing a file as the unit of atomicity was probably one of those spontaneous decisions made when the first VCS was born, it is just a legacy. I want to be able to customize the behaviour of VCS, want to be able to change the atomicity unit any way I need, but keep the changelists, submits, reverts and branching untouched. Leaving the file as a primary atomicity unit (I can live with that :) why not to add handlers for a specific file types which will know which sub-units it consists of, how to diff and merge them etc? Lots of opportunities are opened this way, for example you can implement a handler for a video file, allowing you to edit each frame as a bitmap image, checkout separate tracks from a music pack, lock a single box on the level at last. You can go even more crazy with hierarchical atomicity levels: basic level is a directory (you merge it by choosing which files to keep), next level is file (you merge them like you do this now), deeper levels are your custom handlers like area on level, which in its turn breaks down to objects.

Sadly, this becomes a tradition that each time I analyse some technology the conclusion is mostly "there's no such thing yet - write it yourself". Adding version control to my TODO list.

Git vs. Perforce from game development viewpoint

2011-09-29T16:03:00.000+03:00

Recently been wondering about would how our infrastructure would've looked like if we were using Git instead of Perforce as version control system. So here's the summary:

~~Assets~~ Version control for the real world
We store all of our assets in Perforce. Can git handle it? No.
Many say that Git was created for different purposes. Indeed, distributed nature and the conceptual model that require rehashing of local files on most operations does not suite for big files at all. But I do not assess Git and Perforce for the 'things they meant to be used for', I am looking at how they satisfy my needs, and how they can be used in real projects. If you were 'making it for other purpose' and it does not satisfy common needs, maybe you were making the wrong tool.
I think of a VCS as a heart of a company. It is not just code or just assets, everything should be there. If artifact is not in version control - it does not exist. Every tool, script you write, every configuration file, everything should be backed up and (preferably) automatically syncing with VCS. It's convenient, it protects you from cases when machine fails and important scripts are lost, it simplifies understanding of tools and processes as you do not need to access the specific machine and reverse all the file dependencies to find out which configs, scripts etc. are actually used.

Assets (cont.)
Back to the topic, Git can't handle big files, what can we do about it? Often mentioned the approach with using separate VCS for code and assets. But one of important things VCS gives us is the consistency of the project. By consistency I mean the ability to sync Main to ANY changelist number, build it, and start the application. All changes ideally should be atomic and leave project in a working state. This also means that when we submit a new feature to Main this have to be done in single changelist, both code and data. How do you achieve consistency using multiple VCS when there is always a state when either data or code is out-of-sync? It would be interesting to hear some success stories about setup like this.

Clientspecs

We use a lot of Perforce clientspec magic in our infrastructure. Automated builds, resource compilers, stress-testing, submit checkers etc. All those tools designed to operate on some subset of depot, sync the data, perform some operation, and submit the result. Clientspecs allow to specify which portions of depot to get and where to place them.

How do you do something like that in Git? You surely don't want to clone the whole repository on every server. Event if it is vanilla source-code-only repository which is relatively small, I don't want to fetch things I do not need! Cloning with zero-depth history will save some space, but it is not a full solution.

Advanced Clientspecs

Some of the tools use complex mappings to compose the completely custom view of depot. For example stress testing system can operate on any of the feature branches we have, so on start it generates clientspec for specified branch, that maps all needed binaries and configuration files to the server. It maps all stress-testing scenarios and configs from 'Main' overriding with branch-specific configs if they are present (using '+' in clientspec). Pretty complex.
You can't have two branches opened in Git simultaneously, so in would require branching all configs from Main which is probably not a big deal. But you still unable to customize the layout of things. This can be a serious issue when you bind you version control with 3rd party tools, and probably will require symbolic links twiddling.

Locks

Locks are another interesting topic. In distributed version control you just don't have them. Now imagine having several designers tweaking the weapon parameters, or developers editing the localization files. Even if those files are in text format, such tools as Excel put huge amount of meta data in it, so it is practically becomes unmergeable. Our Perforce is configured to lock such file types for exclusive editing.

Permissions
As I said earlier, I'm thinking of VCS as one of the central systems in the company, not the developers' toy only. When you have project planning docs, agreements, publisher SDKs etc. checked in to VCS the access control is crucial.

But hey, even if you take the vanilla case for git (source code in repo only) how will you organize the stabilization process? Git manages permissions only on repository basis, so you would have to manage permission on push-pull level between Stabilization, Main, and Release repositories.

Decentralized!
Git is decentralized! Haha! Eat this Perforce! ...you may say.
Yes, it is, so what? Take the most popular hosting for Git - Github, take the branching models for Git, all they do is centralize it. Of course you can do a peer-to-peer exchange, but do you really need it? Most people just fork the existing projects and working on them, again, as in centralized VCM.
So why do you need to throw away all the benefits of centralization like simple solution for big files, changes tracking, shelves etc.? Yes, I will not be able to read the whole history of the project while flying in the plane, but hey, I prefer to read a book while flying anyway. And I feel safer when I know that whole project can't be stolen that easily :)

Still have some thoughts left, but I'll leave them for the next post.

Explicit class import

2010-10-16T21:13:00.005+03:00

In this post I want to describe a small step every language should take on its way to modularity. I will describe the basic idea and applications of explicit class import, how this feature (implicitly) works in Java and the ways of implementing this vital feature in C++-like languages.

Here's what brought me to all this thoughts. I'm not a Java person in any way, but I was reading a book about OSGi and speciffically about how it treats the classpath and class loaders. Basically class path is a root namespace. When the Jar is loaded, its classes are merged into the class path, allowing you to instantiate them. In pure Java it often creates a class path hell. Class names from different Jars can collide when being added to class path. OSGi solves this problem elegantly at the bundle resolution stage by manipulating class paths and creating isolated environments for each bundle.

Such class-pathish loading model means that classes are manipulated entirely at runtime, and if, for example, you used class A from package a_lib.jar then a_lib can be completely substituted by b_lib.jar if it contains class A with matching interface. If not - only runtime exception will occure. All this means that Inversion of Control (here I'm talking about IoC of classs instantiation) can be acheived transparently, without bringing the complexity of OSGi services.

Ok, that might've been confusing, but bare with me. Let's see how this would look like in C++ world. All this behavior could've been achieved by explicit class import/export. All of you probably used the implicit dll linkage In this approach entire classes can be exported and imported from dll (although class export is non-standard thus compiler-specific). it's the easiest and transparent way to link to dll. But modular systems can't use implicit linkage because the dll you link to is gennerally not known at compile time. Here C++ suddenly limits our abilities. Just like you using LoadLibrary/GetProcAddress (dlopen/dlsym) to bind functions from dynamically loaded library, why there is no way to link whole classes?

What we need to know to use the class is its methods, members, constructor and destructor. Member export is quite difficult (it will require the recursive export of types) so best way would be to limit class export to methods only. So this leaves methods, ctor, dtor and class size (so that we could allocate a correct ammount of memory for its instances on client side).

Instantiation procedure of exported class will generally look like this:

Load a dll with a class you want to use (done explicitly)
Bind ctor, dtor, and all methods of class to their implementation in dll
Allocate suitable ammount of memory on the stack or heap
Call a placement constructor

Here's how it may look like:


//----------------------
// my.dll
//----------------------

export class MyClass
{
public:
  void Foo();
private:
  int m_bar;
}

//----------------------
// my_client.exe
//----------------------

#include "my/myclass.h"

int main()
{
  import("my.dll"); // Binds class loader chain
  return 0;
}

void foo()
{
  MyClass mc; // Triggers lazy type binding
  mc.Foo();
}

This technique can be implemented in C++, but it would require specifying explicitly which methods to bind, and it will be just too ugly to use. Where it can be used without a tonns of boilerplate code is in D. D has a neat feature, which in my opinion beats the shit out of C++, it's a compile-time reflection. This means that you can iterate over all members of a class for example without writing some ugly method tables etc. Theoretically it can be implemented without being a core language feature, but adding it to the language makes a lot more sense to me.

Listeners caveats

2010-09-07T22:15:00.001+03:00

Want to tell about one design problem I keep suffering from day after day. And the problem is in the something as simple as listeners (Observer design pattern).

If you'll ask some programmer to implement listener facility the response would be like: "Ha, peace of cake!". And he instantly writes something like this - an interface and std::vector of pointers. But this design is initially broken!

Scenario:
We have a simple game Console system that stores lots of console variable (CVars). Of course Console provides listener facility to track changes of variables (OnBeginChange, OnEndChange). We have a some_variable registered in console, and all we want to do is to listen its changes, do some logic in OnEndChange and if necessary change its value right there. Changing variable from the on change handler naturally results in recursion, and if you lucky you can eliminate recursion with redundant assignment checks. But in my case a complex server logic was done in handler and values I want to assign vary from call to call.

Natural quick fix was to unregister my listener before changing the var in the handler and register it back right away. But with typical implementation approach any registration operation will result in hard to diagnose bug, because we end up changing the container while iterating it up on the call stack. Because console was built in release mode I've noticed the bug only because breakpoint in change handler was hit twice during notification (listener was erased and then pushed back on registration).

How to do it right:
Simplest way that will always get you out of trouble is copying the listeners container before the iteration. This way we will only call handlers of those who was registered on the moment of event and allow registration without any side effects.

Copying approach is simple, but if you are as mush eager for performance as I am, you will feel uncomfortable copying containers every time the event fires. In this case CoW comes to the rescue. CoW stands for Copy-on-Write which is exactly what it does, copies container only in the case when some modification is done. COW can be implemented by wrapping container into shared_ptr. When notifying listeners you create another shared_ptr on stack initializing it with the member. On each registration operation you check for shared_ptr::unique(), if it is false then notification is running, so we need to duplicate the container, simple!

Listeners and multithreading:
Consider OSGi event service for example, which asynchronously dispatches bundle events (like BundleStarted, BundleStopped, BundleResolved etc.) to other bundles. Simplest implementation would be to store all events in the queue and allocate a thread job that dispatches events in background. Using a bit of locking we can successfully adapt CoW listener list from previous example, all seems fine. But the is a fault, and it is very tricky! Here's the scenario:

Bundle A started (event raised, placed in event queue, thread job allocated)
Bundle B started (event raised, placed in event queue)
Bundle B registers as a listener
Finally dispatcher thread is scheduled and delivers events
Bundle B receives A:Started and B:Started event (!!!!)

An OSGi standard dictates that event should be delivered only to those listeners which were registered at the time when event was fired. So Bundle B should not see its start event and, of course, not the started event of Bundle A. This means event service should maintain a list of events + listeners registered at the moment it was raised. Sounds very inefficient, but CoW helps here a lot too. Whether it efficient or not, it's not an optimization if you sacrifice correctness, anyway.

On the second thought you can also use alloca() to copy the list of listeners without any heap allocations, but it is not suited for multithread case.

Dynamic dispatch in D

2010-08-07T15:37:00.000+03:00

Just discovered one more neat feature of D, the opDispatch() operator. Whenever compiler encounters a call to non-existing method such as myObj.Blah(a1, ..., aN) and type has an opDispatch overload, it transforms a call into myObj.opDispatch!"Blah"(a1, .., aN), making it a function call with a string template argument that contains a function name. It's just a blessing for those who did some script language interop.

Some time ago I've implemented a script binding generation library for my engine which were using my C++ Reflection library to create Python type proxies at runtime (a big plus comparing to boost.python, because this model easily works with plug-in and modular design).

Exposing C++ types to Python was challenging, but I've managed to hide all complexity in the library. The reverse integration, exposing Python types to C++, was a hard thing to do without forcing the user to write a lot of boilerplate code.

I'm sure in D with this dynamic dispatch feature it is a peace of cake. All script objects can be represented with a single class with opDispatch overload in it. A little runtime validation, and you're in scripting haven.

Hmm, or event better pattern, for stable types with compile-time type checking:

Define the D interface that describes the Python type
Make the ScriptObject class accept interfaces as a template parameters
ScriptObject inherits this interface and generates all method implementations using traits (D's compile-time reflection) and mixin feature.

...wow, D really lets your design imagination run wild :)

Client-Server Engine Architecture

2010-08-04T22:00:00.002+03:00

You really want to separate client and server parts of your engine. Belive me, because I've been on the other side.

Simply put, by client side I mean the part responsible for user input and rendering, and by server - part that contains all game logic, physics simulation, AI and stuff. The dumber the client side - the better. Here's an overview of Source Engine's networking architecture which elaborates things a bit.

By separation I mean that the client and server parts are separate entities in the engine (even in single player mode), communicating through well defined message passing system. The separation step isn't always the obvious one, because a lot of code is shared between those two parts. For example take physics simulation. Apart that I said that it runs on server side, there can be client-side simulation as well. It would be a waste to simulate particles and small debries on the server, because those simulation have almost no effect on gameplay, but will consume A LOT of network traffic.

Clean separation gives an advantage of easily creating dedicated servers for the game later and helps avoiding the hell of presentation and logic coupling. Without it you just end-up with millions of if(bDedicated).

Typical issues of late separation:

Lost control over things that should only work on server or only on client
Performance penalty because server runs unnecessary subsystems
Bandwidth penalty for synchronization of objects that should be client-only
Presentation info used in logic (pierceability and other physics properties depend on material used for rendering)

It is challenging sometimes, here's a funny example. Consider the rag-doll animation, when player dies his body is physicalized and falls obeying the laws of Newton. Should rag-doll work on client or server?

Server-side means that all clients see the same picture, but in a cost of huge bandwidth. Client-side simulation is cheap, dead bodies have low impact on gameplay, so it should work...

But few moth later you receive a request from designers "we want medic to be able to revive fallen comrades by coming near the body and..." you name it. The issue here that the "near the body" part is different on all clients because of non-deterministic behaviour of rag-doll. And yet better, there's no body on the server at all. Also remember that we cannot trust any information from the client besides its input, so no "revived" messages are allowed.

Your comments on the puzzle are welcome ;)

First impressions of D

2010-07-25T23:11:00.000+03:00

I'm a happy owner of Alexandrescu's new book "The D Programming Language", due to the lack of time I'm only through one third of it, but already I can say that it turned out pretty good.

I was really amazed by the D's expressiveness, for example:

auto input = [ 2, 6, 4, 2, 3, 9 ];
auto res = reduce!( min, max, (s, x) { return s + x; } ) (input);
writefln("min=%s, max=%s, sum=%s", res._0, res._1, res._2);

Computing the minimum, maximum and a sum across the slice all in one iteration and in a single line, superb.
The other impressive thing for me are tuples, variadic functions and templates.

Playing with delegates and function pointers I did not really get yet why function pointer is not implicitly convertible to delegate with same signature. Delegates differ only by carrying along the context where they were created, so there no obvious reason to deny the conversion.

void callFoo(void delegate(int x) deleg)
{
deleg(10);
}

void main()
{
callFoo(delegate (int x) { writeln(x); }); // OK
callFoo(function (int x) { writeln(x); }); // ERROR
}

So it presumably will add some small overhead even in case of context-free callbacks, but fortunately it is not the issue with templates, both delegates and functions can be used there interchangeably. So to make previous example work callFoo can be changed this way:

void callFoo(T)(T deleg)
if(is( typeof( T(0) ) )) // Tricky check for type validity
{
deleg(10);
}

While reading the book I often stress-test some cool features using the Visual D plug-in for Visual Studio. Lacking in intellisense support, it nicely integrates with IDE, providing all set of properties and project wizards, very convenient. The plug-in seems to be under heavy development, so, at last, my journey for a decent IDE (integration) for D language came to an end.

Inheritance and lifetime inversion

2010-07-15T14:37:00.000+03:00

The misuse of inheritance is a common mistake. Previously I thought of it as a thing that leads to a poor and complicated design, but recently found a good example of how it can cause the logical error. The example is especially valuable because illustrates an error made in a heart of the engine - in memory allocator.

So suppose we need to make a lot of allocations of objects of some type. This is the ideal situation to apply a free-list allocator. So the author of that code defined a class called FixedSizePoolAllocator. This class maintains a free-list of objects so it can give them out when they needed. If the list is empty it allocates an object through Heap instance (an allocation strategy class), passed to allocator in a constructor by reference. So everything looks peachy now, you create an allocator in your code, pass him a Heap instance, thats it.

This design is flexible in that way, that user can share instances of Heap between multiple pools, so if a Heap is some constant-size buffer, all objects will be allocated from it. But for most cases you don't need that flexibility, you just want a pool. With this thought in ming same or another author creates PoolAllocator class, which supposed to wrap FixedSizeAllocator and provide a Heap to it. He inherits PoolAllocator from FixedSizeAllocator, adds a member Heap object to it, and passes m_heap reference to parent constructor.

Here's the code that illustrates this "solution":

template<typename THeap>
class FixedSizeAllocator
{
   FixedSizeAllocator(THeap& pHeap) : m_pHeap(&pHeap)
   {
   ...
   }

   ~FixedSizeAllocator( )
   {
   ...
   }

   THeap* m_pHeap;
};

template<typename THeap>
class PoolAllocator : FixedSizeAllocator
{
   PoolAllocator( )
   : m_heap(...)
   , FixedSizeAllocator(m_heap)
   {
   ...
   }

   THeap m_heap;
};

Take a second and you should be able to identify at least two huge problems in this wrapper (think of an ellipsis as of any operations you can imagine).

So, design issues aside, here they are:

1. Compiler don't give a damn in which order you place the statements in constructor initialization list, the order is always the same: first, the constructor of base class is called, then, all members initialized in top-down order as they were written in class (not initialization list). So if FixedSizeAllocator will decide to do some operations on heap object, it would do them on yet not constructed invalid object.

GCC is actually has a warning about wrong order of initialization list

2. Because destructors called in reverse to construction order, PoolAllocator dtor will be called first, and respectively the destructor of m_heap. So if FixedSizeAllocator is doing some operations with m_pHeap in his destructor (which it certainly did), you, again, has a big problems.

So in fact our wrapper never even wraps anything properly, that's what I've called a "lifetime inversion". Maybe there's some another name for it.

I hope you will now be able to identify such bad patterns in code and won't run into the same problem. It took me at least an hour to get to the core of the problem, navigating through huge call-stacks, partially because I believed that such code is always written by pros and well tested.

Conclusions:
- Prefer composition over inheritance
- Keep initialization and destruction order in mind
- Test your code (unit-tests, valgrind)

Biggest blog I ever saw

2010-07-12T22:17:00.002+03:00

A colleague of mine recommended me a Cbloom Rants blog. When I got home I decided to check it out and stuck reading for the whole evening.

I have this habit of reading all blogs from the very bottom up to the newest post, so I was surprised to see that first post is dated with December 2000.

Author is a physicist and programmer, mainly working in gamedev. This guy writes with admirable stability, I've counted 3275 posts in total now, each of which worth reading. It is really amazing how you can just spend one evening reading the 10 years of someone's life, his thoughts on politics, capitalism, war, guns and drugs, bicycles, cars, dating with girls... Some posts are funny, some are sad, some filled with happiness, some with anger.

"Sometimes I just want to get crazy, to be poor, broke, live in the big city, and do something important, do something to change the world, do something different, like art or music or *something*, to be addicted to drugs, or a criminal. To not just be a cog in the machine, to not just do the same crap that everyone in the world is doing, to not be replaceable, to not enjoy nice wine, to not have a nice car, to not watch television. But then that feeling passes and I go back to doing all those things that I despised a moment ago, because after all, I do like them so."

Where else would you find a detailed instruction of how to act if someone tries to hang you?

"My oven exploded again. Every time I cook Italian sausage in wine (the only way to do it), the alcohol in the wine explodes in my oven. The first time I did it, it burned off my eye lashes. I wonder if this is common or am I doing something wrong?"

At first I wanted to make my blog as consecutive as possible, one thought comes out from another etc. But after reading this blog now I'm convinced - you should just write everything that comes to your mind.

Being busy all the time at work, at home, I don't really have the time to make (and keep) my blog up-to-date with things I am thinking about. Perhaps later there will be time to gather some posts and build articles about things I've been working on all this time. If not - I bet it will be just awesome even for me to take a look at what I was writing about ten years ago :)

OSGi Future: OSGi-enabled kernel

2010-07-12T00:21:00.001+03:00

More than half a year passed since I've started working on OSGi topic, implementing OSGi Core first in C++ and now in C#. All this time I read and heard about multiple applications of this technology ranging from embedded devices integration to enterprise application architecture and SOA. There is a positive shift going on in the industry from simple OOP to component-oriented architectures. So I just wanted to share my opinion about what all this leading us to.

Plug-in-oriented architecture
First of all a bit of my personal experience - plug-in-oriented architecture rocks!
Right now I have four large and middle-scale applications successfully built with this approach. There are my game engine, IDE with VHDL compiler, and few tools I've wrote on my job, all built using Eclipse extensions-like approach. By this time I've implemented extension graph for C++, C# and Python languages.

Judging from examples you can see, that plug-in architecture clearly doesn't have a narrow range of appliances. It helps to structure the program in clearly-defined layers, prevents tight coupling and really helps with reuse. It will definitely help any project that has some considerable development time.

OSGi
OSGi adds a dynamics to component-based architecture. By dynamics I mean a system-wide notion about that any service in it can go "up" and "down" in any minute. This adds a noticeable amount of complexity, comparing to Eclipse extensions, but the gained benefits definitely worth it. Now all bundles (components/modules/plug-ins in OSGi terminology) can correctly react on presence of some service. Although such dynamics doesn't seem quite useful in a single-process scale, it really shines when R-OSGi comes to stage.

R-OSGi
R-OSGi (remote OSGi) is a communication framework in OSGi that adds a possibility to connect OSGi containers running on different machines. Similarly to CORBA or DCOM it implemented in such way that remoting is absolutely transparent to services' user. Remoting layer is fairly similar to WCF, but in contrast, in OSGi it fits to the whole framework concept so seamlessly, that it hides complexity from the user, not introduces it. Dealing with remote machines, the complete component life-cycle helps to react correctly to connection problems etc.

Simple example of the power of OSGi is Eclipse, which starting from version 3.0 picked it as its runtime architecture. Since then it clearly benefited in distributed sphere. Eclipse Communication Framework grows fast, adding support of new transport protocols (REST, SOAP, XMPP, and even ICQ), support for communication with non-Eclipse web services and more.

Android example
Recently, thanks to some sneaky-thievy-bastard I was thinking about buying a new phone. Naturally, I was looking for an Android device, and even though I am not, and never been interested in mobile development, just out of curiosity I took a look what it has to offer to developers. I was slightly disappointed by Google's choice of Java as primary development language and Android's API architecture in general.

First of all Java is clearly looses its positions to .Net. Given that for Android Google implemented their own virtual machine for Java (so they were not forced by some huge amount of legacy code or something) the choice is even stranger. With all their PR talks about freedom of software etc. why not invest those resources in Mono? The obvious win here - much bigger language support (C#, VB, F#, IronPython ... ), instead they limited themselves (and developers) to just one.

From API-side things are disappointing too. Google takes a limited "program only those things we will let you to" API approach. This means that when phones with some new cool feature come out you can't do nothing with it, not until it will be exposed in Android API. This is very limiting, where is the promised freedom I ask?

OSGi-based kernel
I was able to find some posts about OSGi being ported to Android, but no info on most obvious move from my point of view - integrating OSGi to Androids kernel. Basically cell phone is a large collection of services, communicational (GSM, CDMA, WiFi, Bluetooth ... ), multimedia (Camera, Accelerometer) and so on. All this perfectly fits to the main purpose of OSGi - dynamic service discovery and binding.

This would greatly improve the API - all you need to do is provide the list of available services with their interfaces and contracts. Service API could be exposed my 3rd-party vendors of some hardware or software feature, significantly decreasing the workload on core system API writers. It will even give developers the ability to program to non-existing yet feature by substituting in development time with a stub-service, so when new feature comes out application will immediately detect and use it!

Thinking about OSGi-enabled mobile OS, I came to idea of finishing my C++ OSGi implementation and trying to integrate it to the Linux kernel. With some improvements (like security, contexts and service discovery domains) it would be a solid application development platform.

Judging from Eclipse, which is already overloaded with Twitter, ICQ, Jabber and other plug-ins there is a big demand for a system-wide component framework of this kind.

With this whole OSGi OS idea it seems to me that I'm coming towards the micro-kernel approach, but I can't define a clear boundary right now. "The time will show": I could've said, but time is definitely not working in my favour :)

References:

D vs. C++

2010-05-09T22:32:00.001+03:00

Few weeks ago I've stumbled onto the new language named "D". I was very sceptical about all new languages that were released recently, but when I saw that D aims to be a successor of C++ I just had to take a look at it.

Because last year I mostly been dealing with the darkest corners of C++ implementing reflection, delegates, data marshalling I was very frustrated that none of the core language problems were addressed in the upcoming C++0x standard (at least standardized layout of pointers to member function would have saved me a lot of nerves). Of course such decisions of committee are understandable, on C++ lays the burden of zillions lines of existing code, so breaking changes seem unacceptable.

Creator of D made a much bigger step than filling C++ with a bunch of syntactic sugar, although D has a similar set of paradigms its features assembled into a whole new level of programming techniques.

Features

I really don't want to repeat all the numerous articles about D, so I'll just name most arguable and most pleasant features from my point of view:

D is a compiled language, it compiles to the assembly code, what is definitely awesome.

D has a built-in Unicode support, interfaces, delegates and closures, what is awesome.

D is a garbage collected language, what is awe... Ehm, isn't this too much for a successor of C++ you may ask? At first I was sceptical about this decision, because in the past spent a great deal of time fighting with GC in C# in one memory-hungry application.

Stroustrup claimed that in C++ you can easily implement your own garbage collection if you really want to. Unfortunately, this is not an easy task, especially when you interfacing with 3rd party libraries. You have to constantly track all the data exchange, making sure that objects passed into the libraries from your code will not be garbage collected, and objects that you receive are deallocated by the rules of the library who created them. With language-wide garbage collection this is not the issue any more.

So now GC looks totally reasonable to me. Yeah, and most importantly, despite the GC you still get the beloved RAII (see the scope feature)!

D doesn't have a preprocessor, it uses totally different compilation model which is more efficient than raping the compiler with millions of #include's.

D addresses multithreading problems by making all variables implicitly thread-local.

D has a really powerful templates and meta-programming mechanisms, on top of that the standard library is written by Andrei Alexandrescu and features his range concepts.

Here's the small example of its power:
int[] arr1 = [ 1, 2, 3, 4 ];
int[] arr2 = [ 5, 6 ];
auto squares = map!("a * a")(chain(arr1, arr2));
assert(equal(squares, [ 1, 4, 9, 16, 25, 36 ]));

You can see here following features:

type inference with auto keyword
chaining of two ranges
new template syntax !( ... ) that solves the >> issue
mixin is used under the hood to generate code from a string passed as a template argument
lazy evaluation - mapping operation will be delayed til' the result of operation is actually needed

Also there are mind-blowing features like static if, a compile-time function evaluation and compile-time foreach!! And here's the craziest proof of its meta-programming power http://h3.gd/ctrace/ - a compile-time (!) raytracer (!!) ... no words :)

Downsides

There's a lot more features out there, so go ahead and see for yourself, but now I have to tell my opinion about D's downsides.

First of all is a god damn name. What do those people think about naming their languages D or Go?! As a result it's very difficult to google info about it.

Second - I've spend few days just trying to setup a decent working environment to try it out. I was using both Windows and Linux, tried Eclipse, Code::Blocks and Poseidon, but none of them felt right. Code::Blocks felt the best, but when I decided to play with shared libraries in D I've discovered that DMD (one of the D compiles) simply doesn't have a shared libraries support yet... Good thing that supposedly GDC (GCC front-end for D (what a name... :)) had, but the bad thing that it was the end of my patience.

Now I have some Internet connection problems, so I left D and GDC aside for a while, but anyway, the toolset level just seems immature. However, many people claim that they already have released or ongoing commercial projects with D as a main language. There is a hope that D will soon be available for Visual Studio, thanks to Visual D plug-in.

As a downside I can add a slow migration of tools from D 1.0 to D 2.0, and the existence of two competing standard libraries: Phobos and Tango.

Phobos is a minimalistic library in C++ style and its style is very appealing to me.

Tango is more like a Java-style huge "I-can-do-everything" library. Another example of such rich standard library is my beloved Python.

From my point of view the ideal solution for them is to coexist. Taking of the "standard" part from the Tango and making it reside on top of low-level Phobos features would be a way to go.

Summary

D looks very promising to me, and I think a great future awaits us with it. D hits the spot satisfying the need of the modern and powerful system programming language. I've already pre-ordered a new Alexandrescu's book, so somewhere in July I will definitely take a deeper look on this great language :)

Links

Interfaces: Type identification and casting

2010-04-04T15:24:00.002+03:00

As we continue our way towards C++ modularity, there's a few problems yet need to be solved. In this post I will describe type casting between interfaces, and type identification in general.

In my previous post I've describe how to export interface implementations from a dynamic library. This solution is sufficient for a beginning, but when your interface hierarchies grow there will be a time when you will have a need to downcast a pointer (cast from base interface to a specific child). Note, that dynamic_cast will not work in this case, because we do not export any type (and therefore no type info) from the modules. So this problem is unsolvable without additional facilities.

QueryInterface method

The main subject now will be a QueryInterface method. QueryInterface is one of the three methods of IUnknown, which is the base type for all interfaces in COM. Last two methods was mentioned earlier: AddRef and Release, used to manipulate the reference count. This is how IUnknown looks like:

struct IUnknown

{

virtual HRESULT QueryInterface(const GUID& iid, void **ppObject) = 0;

virtual unsigned long AddRef() = 0;

virtual unsigned long Release() = 0;
};

QueryInterface receives two parameters:

iid - unique identifier (GUID) of the interface we want to cast to
ppObject - acts as return parameter that will receive a pointer to interface in case of successful cast
finally, QueryInterface returns HRESULT - a result code of operation.

First thing to notice is that types are identified using GUIDs, this means that we should be able to associate a GUID with a type. Since goal of this post is to give you an idea about type casting, I will sacrifice portability for the sake of brevity, and use a Microsoft's compile extension for this. A portable solution will be presented in later posts, but now we will just change our interface like this:

struct __declspec(uuid("00000000-0000-0000-c000-000000000046")) IUnknown

{
...
};

With GUIDs we now have a way to uniquely identify interfaces in a separately compiled modules. Now that we have all data, the simplest implementation of QueryInterface could look like this:

class CMyClass: public IMyInterface
{
HRESULT QueryInterface(const GUID& iid, void **ppObject)
{
if(iid == __uuidof(IUnknown))
{
*ppObject = static_cast(this);
return S_OK;
}
if(iid = __uuidof(IMyInterface))
{
*ppObject = static_cast<IMyInterface*>(this);
return S_OK;
}
return E_NOINTERFACE;
}
};

A thing to note here is a casting of this pointer before assigning it to *ppObject. This looks redundant to explicitly cast a this pointer to a base class interface, but this is necessary, because in cases of diamond-shaped hierarchies or inheriting the implementation class those pointers would differ, so returned pointer should point exactly to that type of queried interface.

Optimizing QuryInterface
This would be very tiring to write implementation of QI every time by hand, and also not performance-wise. The approach used by COM is a table version of QI. In it all supported interfaces are defined using a set of macros. Those macros compile to a static array of entries containing interface ID and corresponding offset that should be applied to this pointer when queried. The implementation can be found in the Don Box book, or in ATL source code, I will just provide a sample how it changes code from previous example.

class CMyClass: public IMyInterface
{
DECLARE_IMPLEMENTATION(CMyClass)

BEGIN_INTERFACE_MAP()
INTERFACE_ENTRY(IMyInterface)
END_INTERFACE_MAP()
};

Class identification
Imagine that you have a module that contains two implementations of one system, lets say OpenGL and DirectX renderers. They both implement same interface and intended to be used interchangeably. But now user has no way to choose between them, because all he sees is an interface. This brings us to a solution, that implementation classes should be also identified by GUIDs. We will not use the __declspec(uuid(...)) in this case of course, because header with implementation class should be inaccessible to the user. Instead, we just define a class ID in some other header file:

static const GUID CLSID_COGLRenderer =
{ 0x637b1ed1, 0x12e5, 0x4a4b, { 0xb6, 0x9d, 0xed, 0xf6, 0xea, 0xd5, 0xc4, 0x78 } };

static const GUID CLSID_CDX9Renderer =
{ 0x07a4b5f9, 0x495c, 0x45b1, { 0xbb, 0x91, 0xe8, 0xfb, 0x11, 0x44, 0x7c, 0x05 } };

Factory functions
Class ID solution presented above is cool in two ways: first, it allows us to specify which implementation to use exactly, second, we can reduce the amount of functions exported from a DLL to one.

extern "C" HRESULT create_instance(const GUID& clsid, const GUID& iid, void** ppObject)
{
...
}

We use three parameters here: the class ID that should be created, an interface ID the pointer should be cast to before returning it, and the output parameter itself.

Interfaces: Modules and Lifetime

2010-03-14T14:56:00.007+02:00

The PImpl is a practical and easy to use solution. It is suitable for simple utility libraries, but it definitely cannot satisfy all needs of modular architecture. In this post i will describe how a greater flexibility can be achieved by separating interface and implementation.

PImpl limitations

Modular (or plug-in) architecture assumes that one type of functionality (a service) can be implemented by multiple modules in a different way. For example, lets take a configuration persistence service. A single interface to this service can have a variety of different underlying implementations: an xml or ini-file serialization, SQLite or another database connector, etc.

Ideally, we should be able even switch implementations without recompiling the application. This is of course impossible task for a PImpl. There are two reasons for this:

PImpl implies implicit linking, what means that we always define a concrete shared library to link with
With PImpl we always specify a concrete type of class to instantiate

Interfaces

All mentioned above brings us to first conclusion: we should unify "module interfaces" first, ie a set of functions exported from them. The solution here is to export a factory function, something like create_cfgstorage_instance().

Hmm, but what should be return type of such function? If we are trying to generalize all configuration storage types, naturally, it should be some base type of those (a superclass). This superclass won't have any default implementation, so all functions should be pure virtual.

With this decision, in fact, we solve two problems simultaneously, because virtual functions all have a unified call procedure on all compilers (ie taking an pointer to a virtual table and jumping to N'th entry of it). This means that compiler can generate code for vcall, without knowing the true type of the object.

This abstract type is our interface! To clarify here's the example:

// IConfigStorage.h

struct IConfigStorage

{

virtual void WriteValue(

const char* key,

const char* value) = 0;

virtual const char* ReadValue(const char* key) = 0;

...

};

// CINIConfig.h

class CINIConfig : public IConfigStorage

{

// Implementation

...

};

// CINIConfig.cpp

...

extern "C" __declspec(dllexport)

IConfigStorage* create_cfg_instance()

{

return new CINIConfig();

}

Nice! Now you can create objects from shared libraries using explicit linking. All you need is to load a library using LoadLibrary / dlopen and get the address of create_cfg_instance() with GetProcAddress / dlsym.

Object Lifetime

You can use your object now, but you can't delete it yet by two reasons:

First, you should never try delete anything allocated in another module (because this module could be compiled with different CRT version, what will cause the memory corruption)
Second, we did not exported a destructor for the object, so compiler will give us an 'unresolved external' error

You may think that adding a virtual destructor to the interface might help, but it won't, because standard specifies only the layout of pure virtual functions, but not the virtual destructor. There are two simple solutions here:

add second exported function destroy_cfg_instance()
or add a interface member function Free(), that can be implemented as delete *this

Reference counting

COM offers more practical solution - an embedded reference counter. This means that interface has two methods: AddRef and Release - first increments the reference count, second decrements, and if it reaches zero calls delete *this.

At first glance this reference counting can be made non-intrusive, by using special type of shared_ptr, that calls Free instead of delete. But shared_ptr implementation involves one more allocation for reference counter, that should be deallocated too, so we can't pass this shared_ptr across different subsystem modules by the reasons described earlier. And this brings us to the same problem we were trying to solve :)

First step completed!

Congrats, we already achieved a lot, compared to PImpl:

We can create a simple modular applications with substitutable components
We maintain binary encapsulation of modules, while greatly reducing the size of library export table

All comes with the price of course, interfaces add cost of virtual call to all methods, but assuming that we mainly export only a subsystem facade's, this is often negligible compared to the gained flexibility.

Interfaces have much more hidden power. In my next post I will describe the type casting between interfaces, introduce the IUnknown, and generalize the factory functions of our modules.

References:

The PImpl idiom

2010-03-07T22:56:00.009+02:00

In my previous post I've described how dangerous implicit linking is. Now I'll show a simple way to make your implicitly-liked libraries safe to modify, without braking the clients who depend on it. This way is called the PImpl idiom. PImpl stands for a "pointer to implementation". So, let's see what this idiom implies.

As was earlier said, the binary encapsulation violation occurs when object exported form DLL changes its size, thereby corrupting memory inside binary who links to it. What we need is to isolate user's code from changes of data members of the exported classes (this often called a compilation firewall). PImpl does this by separating data members into another object, adding a level of indirection. Consider following class:

// MatrixStack.h

#include "Matrix.h"

#include <vector>

class UTILS_API MatrixStack

{

public:

void push_back(const Matrix& m);

...

private:

std::vector<Matrix> m_stack;

};

// MatrixStack.cpp

#include "MatrixStack.h"

void MatrixStack::push_back(const Matrix& m)

{

m_stack.push_back(m);

}

You may think that this/yours class is simple and will not likely ever be changed, and you don't need any compilation firewall. But be careful, in this case, for example, we have a std::vector as data member of our class, and its size can vary, based on a compilation options, so firewall is a MUST.

// MatrixStack.h

#include "Matrix.h"

#include <vector>

#include <memory>

class UTILS_API MatrixStack

{

public:

MatrixStack();

~MatrixStack();

void push_back(const Matrix& m);

...

private:

struct MatrixStack_Impl;

std::auto_ptr m_pimpl;

};

// MatrixStack.cpp

#include "MatrixStack.h"

struct MatrixStack::MatrixStack_Impl

{

std::vector<Matrix> stack;

};

MatrixStack::MatrixStack()

: m_pimpl(new MatrixStack_Impl)

{ }

MatrixStack::~MatrixStack()

{ }

void MatrixStack::push_back(const Matrix& m)

{

m_pimpl->stack.push_back(m);

}

That simple! Let's break into the steps what we did.

First we forward-declare the *_Impl structure, we implement it in a cpp file, where user cannot see it, and move all data members to it. Then we add an auto_ptr pointing to that struct (thus the only member of our class will always be a single pointer). Last thing - we add an initialization of the pointer in class constructor and redirect all data manipulations to the Impl struct.

The interesting thing to note here is, on the first thought redundant destructor, which does nothing. But, in fact, it is necessary, and should be implemented in cpp file after the definition of Impl struct. This is all because default destructor will be generated in place, where definition of Impl is not accessible, so auto_ptr will not be able to destroy it properly.

Using auto_ptr is convenient, however compiler may generate a warning, complaining that auto_ptr is not exported from the DLL. This happens because it tries to export all members of class, including private. You can either ignore the warning, or just use plain pointer. I personally prefer last option, and, thanks to test driven development, it is always noticeable when delete call in destructor is missing.

Drawbacks of PImpl:

Additional allocation
Makes code more difficult to read
Performance hit due to indirection
Doesn't work for protected data members

References:

* Beware, the trick for eliminating the allocation overhead, presented in this book, will break the compilation firewall, it is only can be used (but not recommended) for minimizing a build time.

Flaws of the C++

2010-03-07T15:25:00.011+02:00

Being a huge C++ fan, it should be weird to name my first post like that. Nevertheless, every developer must clearly understand the limitations of the tools he uses, and that's what this post all about.

Those limitations I will discuss were nicely covered by Don Box in his book "Essential COM".

Some may say that COM is now obsolete, what is probably true, but the problems it addressed are still not solved, and a lot of large-scale C++ projects use COM-like techniques to deal with them.

COM is more a programming discipline than a technology

Fundamental weakness of C++ is a lack of standardization at the binary level. If you used C++ mostly for development of stand-alone single executable applications you've never faced those issues before. But for a large-scale projects, that involve multiple binaries, each evolving on it's own, the knowing of those is a mandatory.

Dynamic Binding and Name Mangling

As your project grows, you want to minimize the amount of duplicated code by extracting it to shared libraries. As you know, there are two ways of binding: implicit (using a generated static library), and explicit (using LoadLibrary/dlopen and GetProcAddress/dlsym). The first is the easiest, it allows to export whole classes form dll, and then link to them in user binary.

The problem arises when you try to distribute your library. C++ compilers use technique known as a name mangling to allow export multiple functions with the same name, but from a different namespaces, and with different types and number of parameters, without braking the C-based linkers. Unfortunately, many compiler vendors decided to implement their own mangling scheme. This means that library compiled with one compiler will likely not be able to link used with another compiler. Needless to say, how that complicates the deployment process for middleware.

Binary Encapsulation

So you are a good programmer, you carefully design your classes and hide data using private and protected areas. Unfortunately, this is all useless on binary level. C++ provides only a syntactic encapsulation, leaving your data bare exposed when code is compiled. This problem arises when you deal with shared libraries. Choosing an implicit binding and exporting classes from your shared libraries you bring yourself to a nightmare of binary incompatibility.

Class export allows you creating instances of those on the stack or as members of other classes, what makes user code dependent on size of exported objects. Imagine you have a utility shared library (called MyUtils) and a executable project which uses it (called MyProject). MyUtils exports class called UtilityClasss. In first version of MyUtils UtilityClass had 8 bytes size. You compile your project with this version of library and it works great, so great in fact that you decide to ship it.

Some time later you discover a neat way to improve performance of UtilityClass by adding some caching, thus increasing its size to 12 bytes. You compile your solution and test it, and it works fine. Being enthusiastic, you want to send a new version of MyUtils.dll to users so that they will benefit from improved performance, and immediately your mailbox are full of crash reports.

The problem is illustrated below.

Being separately compiled, the deployed version of MyProject believes UtilityClass size to be 8 bytes. So when you replaced the DLL with new one it started to corrupt the memory around.

Exception model

Don Box refers to exceptions as objects "untouchable" by code generated with another compiler. A C++ exception thrown from DLL compiled with mingw cannot be caught reliably by program generated by Microsoft compiler. "Cannot be caught reliably" in many cases means that when the exception is thrown the application will most likely crash and burn.
Exception catching of a user defined type in a binary other than the one which threw the exception requires a typeinfo lookup, so you need assure that exception types are exported properly. The same thing is required for dynamic_cast to work.

Whew, this post has grown huge. The compilers have much more surprises for you, in addition to those described here. In my next posts I will describe few more of them, and most importantly, the ways to deal with them.

References: