Sunday, November 4, 2012

Concurrent Hello World in Go, Erlang and C++

This week I started taking a deeper look at the Go programming language since I am somewhat addicted to scalability, reliability, concurrency and message passing :-). The first thing I always do when playing around with a new software platform is to write a concurrent "Hello World" program. The program works as follows: One active entity (e.g. thread, Erlang process, Goroutine) has to print "Hello " and another one "World!\n" with the two active entities synchronizing with each other so that the output always is "Hello World!\n". Here is the concurrent Hello World program in Go, Erlang and in C++ using the Mindroid framework.

Go
package main

import "fmt"

func main() {
    sayHello := make(chan string)
    sayWorld := make(chan string)
    quitter := make(chan string)

    go func() {
        for i := 0; i < 1000; i++ {
            fmt.Print("Hello ")
            sayWorld <- "Do it"
            <-sayHello
        }
        sayWorld <- "Quit"
    }()

    go func() {
        for {
            var reply string
            reply = <- sayWorld
            if (reply == "Quit") {
                break
            }
            fmt.Print("World!\n")
            sayHello <- "Do it"
        }
        quitter <- "Done"
    }()
 
    <-quitter
}

Erlang
-module(hello_world).

-export([start/0, say_hello/2, say_world/0]).

say_hello(0, WorldPid) ->
    WorldPid ! quit;

say_hello(N, WorldPid) ->
    io:format("Hello ", []),
    WorldPid ! {sayWorld, self()},
    receive
        sayHello ->
            say_hello(N - 1, WorldPid)
    end.

say_world() ->
    receive
        quit ->
            quit;
        {sayWorld, HelloPid} ->
            io:format("World!~n", []),
            HelloPid ! sayHello,
            say_world()
    end.

start() ->
    WorldPid = spawn(hello_world, say_world, []),
    spawn(hello_world, say_hello, [1000, WorldPid]).

C++ (Mindroid)
#include <stdio.h>
#include "mindroid/os/Message.h"
#include "mindroid/os/Handler.h"
#include "mindroid/os/LooperThread.h"

using namespace mindroid;

static const int SAY_HELLO = 0;
static const int SAY_WORLD = 1;
static const int QUIT = 2;

class HelloHandler : public Handler
{
public:
  HelloHandler(const sp<Handler>& worldHandler) : 
    mWorldHandler(worldHandler), mCounter(0) {}

  virtual void handleMessage(const sp<Message>& msg) {
    switch (msg->what) {
      case SAY_HELLO:
        mCounter++;
        if (mCounter <= 1000) {
          printf("Hello ");
          sp<Message> sayWorld =
            mWorldHandler->obtainMessage(SAY_WORLD);
          sayWorld->metaData()->putObject("SayHello",
            obtainMessage(SAY_HELLO));
          sayWorld->sendToTarget();
        } else {
          mWorldHandler->obtainMessage(QUIT)
            ->sendToTarget();
          Looper::myLooper()->quit();
        }
        break;
    }
  }

private:
  sp<Handler> mWorldHandler;
  int mCounter;
};

class WorldHandler : public Handler
{
public:
  virtual void handleMessage(const sp<Message>& msg) {
    switch (msg->what) {
      case SAY_WORLD:
        printf("World!\n");
        msg->metaData()
          ->getObject<Message>("SayHello")
          ->sendToTarget();
        break;
      case QUIT:
        Looper::myLooper()->quit();
        break;
    }
  }
};

int main() {
  sp< LooperThread<WorldHandler> > wlt =
    new LooperThread<WorldHandler>();
  wlt->start();

  Looper::prepare();
  sp<Handler> hh =
      new HelloHandler(wlt->getHandler());
  hh->obtainMessage(SAY_HELLO)->sendToTarget();
  Looper::loop();

  return 0;
}

I think I really like Go (although Erlang is a bit more crafty :-)). Go eases developing scalable and reliable distributed systems while being a good to read language. Since you can also handle much more concurrent activities with one machine using Goroutines (compared to plain operating system threads) it also helps in saving energy.

Links

Thursday, June 21, 2012

Android Transporter on the Raspberry Pi

The Android Transporter which we have developed at E.S.R.Labs now also runs on the Raspberry Pi. It allows you to easily share and display the contents of an Android gadget wirelessly with a television set or a beamer.

The demo video shows how the Android Transporter turns your smartphone or tablet together with the Raspberry Pi into a powerful media hub to watch movies, play games, or do slideshows.
This way, the Raspberry Pi becomes the cheapest gaming console or set-top box :-).

The Android Transporter for the Raspberry Pi is based on my Android messaging and concurrency (a.k.a. Mindroid) C++ library. The source code of this library is available on GitHub.

Tuesday, May 8, 2012

Android Transporter WiFi Display



The video above shows the Android Transporter, a realtime WiFi Display for Android which I and some other guys have implemented during the last few days. We have done this for our new software startup company called E.S.R.Labs, which is short for Embedded Software Research Labs.
The WiFi Display mirror mode beams the display contents of your smartphone or tablet onto other gadgets, TVs, beamers, or other devices. Soon, there will also be a dual screen mode with an accompanying SDK.
I think WiFi Displays will find their firm place for interconnecting devices to make the world around you a bit smarter :-).

Saturday, March 31, 2012

Android's C++ reference counting

#include <stdio.h>
#include "android/os/Ref.h"

using namespace android::os;

class RefTest : public Ref {
public:
    RefTest(int32_t id) : mID(id) {
        printf("RefTest ctor: %d\n", mID);
    }

    virtual ~RefTest() {
        printf("RefTest dtor: %d\n", mID);
    }

    int32_t id() const {
        return mID;
    }

private:
    int32_t mID;
};

int main() {
    sp<RefTest> ref1 = new RefTest(1);

    {
    sp<RefTest> ref2 = new RefTest(2);
    }

    wp<RefTest> ref3 = ref1;
    sp<RefTest> ref4 = ref3.toStrongRef();
    if (ref4 == NULL) {
        printf("RefTest object is destroyed\n");
    } else {
        printf("RefTest object %d is still around\n",
            ref4->id());
    }
    ref4 = NULL;

    ref1 = NULL;
    ref4 = ref3.toStrongRef();
    if (ref4 == NULL) {
        printf("RefTest object is destroyed\n");
    } else {
        printf("RefTest object %d is still around\n",
            ref4->id());
    }

    return 0;
}

To use the reference counting mechanism for (non Android) C++ projects check out the Ref class of my native Android messaging and concurrency framework. It contains Google's C++ reference counting class from the Android project along with some fixes and refactorings for code readability.

To get started you have to inherit (virtual) public from the Ref base class so that each object of a particular class that derives from Ref contains reference counters and the necessary management methods to increment and decrement them.
Afterwards you are able to create instances of types like RefTest as in the example above and assign them to strong (smart) pointers of type sp<RefTest>. There also is a wp<> template class for weak pointers when you have to get around circles of strong references.

Each Ref object has a WeakRefImpl object that keeps two reference counters, one for weak references and one for strong references. Whenever the strong reference counter is incremented or decremented then the weak reference counter also gets incremented or decremented. But when you create a wp<> to some object only the object's weak reference counter is incremented. Therefore, managed objects live as long as there is some strong pointer referring to it. However, the managed object's WeakRefImpl object may live longer than the object itself because it lives as long as there is some weak pointer referring to the object. If that is the case and the object itself is already destroyed the weak pointer's toStrongRef method returns NULL to indicate that the object is not available anymore.

The Ref base class is thread-safe without needing expensive locks. It completely synchronizes the access to the reference counters using atomic operations. The sp<> and wp<> template classes are not thread-safe. So always make sure you copy the strong and weak pointers when you share managed objects with different threads.

The C++0x shared_ptr class is similar to Android's C++ reference counting class but there are also some differences. E.g. while C++0x keeps the reference counter outside of the managed object in the shared_ptr class Android's reference counting mechanism keeps the counter in the object itself.

Saturday, February 4, 2012

The Erlang Design Pattern

Over the last couple of weeks I did an OO programming experiment. I call it the Erlang design pattern. It is based on the Actor model but goes some steps further. At its core just like the Actor model there are active entities (objects) that have a thread and a message queue with the thread waiting on the message queue to do some stuff.

The Erlang design pattern extends the Actor model by first dividing the software program into active (actors, that have their own thread) and passive (objects, whose methods are called by other actors) objects.
Second, I enforced that all methods of an active or passive object are always called by the same thread context (e.g. actor). So for each object there is no shared state between different thread contexts anymore. Two different objects of the same class could as a matter of course be used by two different actors.
Third, if two or more actors want to share data they have to explicitly do this via message passing. To avoid a lot of copying I shared data using smart pointers in C++ and references in Java and C#. When one actor sends such a data structure to another actor it loses its reference to that data structure to make sure that it is only owned by one actor at a time (see also Microsoft Singularity's exchange heap).

Building software systems using the Erlang design pattern was very interesting because it helped to write concurrent, modular, scalable and readable code :-). Maybe you will try it at your next code retreat.
Of course there also were some quirks. E.g. I couldn't use my C++ closures (which I really like) anymore because they delegate methods of an object from one thread context to another.
To sum this up, the Erlang design pattern was an interesting experiment which I will most probably not use every day in its pure form. But it helps to better understand how ideas of functional programming result in modular, scalable and readable (OO) software systems.

For C++, I used my Android messaging and concurrency (a.k.a. Mindroid) framework to play around with the Erlang design pattern and for Java I just used the Android SDK.

Of Joe Armstrong's Erlang design principles, the Actor model "solves" the first and third point. The Erlang Design pattern also "solves" the second point and goes a step further on the third one.
  • The world is concurrent.
  • Things in the world don't share data.
  • Things communicate with messages.
  • Things fail.
To achieve to same degree of concurrency as Erlang does with its lightweight processes one definitely needs to build its own virtual machine, OS thread abstractions and libraries.
But for smartphone and tablet software development one will most probably not need that degree of concurrency and is able to stick with OS threads :-).

See also:

Sunday, January 1, 2012

How do you read source code?

If software is eating the world as Marc Andreessen and I think, how do you [r]ea(d|t) source code?
Well, let's first answer why you should be good at reading source code at all.
First it's always great fun to figure out how things work. By reading source code one is exactly doing that to learn about interesting software systems and projects.
Another reason for reading source code may be to get better (and faster) at reading and writing software by learning from others and sometimes also from their mistakes.
If you join a new software company or an open source project you are probably going to work on a huge existing codebase and therefore you should be able to get into it quickly, e.g. to implement tests and features or to fix bugs.
The primary goal of reading source code always is to be able to think and reason about all aspects of a software system's codebase. In this article I put together some advise and patterns for reading source code which made my life as software engineer a lot easier :-).

Now the big question is: How do you read source code?
Before you begin to dive deep into the source code of a software project you should make sure to have enough domain specific knowledge to understand the particular piece of software. Hence, you should start to get the big picture by reading documentation and computer science literature about the software platform/product or field of computer science (e.g. Windows apps, Mac OS X and iOS apps, Android apps, operating systems, computer networks, browsers, search engines, databases, etc.).
You don't have to know everything about the topic, but you have to understand the core abstractions and the basic building blocks of the software platform/product. E.g. you should know what processes, threads, semaphores, etc. are before you write your own scheduling algorithm for Linux (see Modern Operating Systems by Andrew S. Tanenbaum). You should also know about Linux specific process management before doing this (see Linux Kernel Development by Robert Love and Linux Kernel Architecture by Wolfgang Mauerer).
But most probably you have already done this before investigating a particular piece of software. So let's get started...

For starters, all software systems or at least all subsystems of huge software systems have some basic building blocks and core abstractions that you will notice all over the place. These components (e.g. classes, modules, actors, data structures, etc.) are also known as hubs. The hubs are simultaneously part of various aspects or subsystems of the whole codebase. Therefore the hubs interlink the subsystems and yet make huge codebases look like small worlds.
Hubs form the contexts around which software engineers build the software architecture. They also implement quite a lot of the core features and functionality. As software systems grow, more and more other components will depend on the hubs. Therefore look for the hubs first and learn about their responsibilities. Usually even huge software systems only have a relatively small number of hubs. Hence, you don't have to fear millions of lines of source code because the hubs will guide you through the codebase. E.g. if we take a look at Google's Android OS, I would say that the following classes (active objects and processes) are the hubs: Zygote, ActivityManagerService, WindowManagerService, PackageManagerService, ConnectivityService and the SurfaceFlinger. You see, just 6 components :-).
You can also repeat the game at a smaller scale, e.g. for Android's widget framework where the View, ViewGroup and ViewRoot classes are the hubs upon which a lot of other UI components build.
This reductionist approach also works for other software systems such as operating systems, filesystems, networking stacks, web backend platforms, etc.
For more details on hubs and network theory I suggest Albert-Laszlo Barabasi's book Linked.

Next, after identifying the hubs you should try to understand the interaction patterns between the hubs. The interactions may rely on different mechanisms like pure API calls or message passing (e.g. message queues or IPC calls). To get the idea of how hubs depend on each other I suggest to just draw some pictures of the hubs, their dependencies and their interactions.
As an example just take a look at one of my previous blog posts about Andoid Architecture Patterns.
On the 7th slide there is a picture about how Android starts activities, services and content providers within their own Linux OS processes. It does so by several interactions between the ActivityManagerService, the Zygote process and the app's process.

As you see, getting the big picture is done by identifying the hubs and understanding their interactions using a top-down approach. To dig deep into specific parts or aspects of software systems we have to change our source code reading patterns. Therefore we will switch to a bottom-up approach to inspect modules, classes, data structures, methods, functions, etc. Later we are able to combine both code reading approches. This strategy of summarizing the findings of the top-down and the bottom-up approach is called downward causation.

I think the bottom-up approach works best by starting with the active entities (threads, actors, processes) that breathe life into the hubs. This is because to be able to think and reason about some piece of source code you really need to understand the environment in which the hubs run.
So always make sure which active entities run which parts of a system's source code and try to understand how and when they interact with each other. This will help you to achieve the primary goal of reading source code, that is to be able to think and reason about all aspects of a software system's codebase (solely with your brain and without the help of external tools like a debugger :-)).
Getting into the details of some piece of source code always starts with trying things out. I do that by adding some logging code or by making assumptions about the code's behavior which I verify with tests afterwards. Another method is to do modifications to the source code just to check how the code behaves under the new circumstances. Breaking or damaging the code may also help you to learn about it ;-).
While reading source code always ask yourself: "How does it work?" and "Why have the developers done it that way?". This will most probably cause you some sleepless nights but it will also make you a better software engineer and software architect.
Everything you do to get better at thinking and reasoning about the source code will help you to develop stronger debugging and analytical skills which in turn enable you to implement new features, fix bugs or do refactorings.

By thinking and reflecting about the source code you are reading you will learn a lot about how to write software systems and platforms. Besides, from bad software you will also learn what to avoid when developing software systems.
Furthermore, there are two great articles about how to write great source code and software systems. Rich Hickey's talk about "Simple made easy" at InfoQ and Erlang's programming rules and conventions. These two guides are outstanding no matter which programming language you use.
So, reading code really is fun. Maybe next time instead of reading another software engineering book just read some source code. (GitHub is really great for that.)

Since you need some staying power to get into a huge codebase I suggest to pick a software project that provides some fun and purpose along the way :-). Maybe the list below contains an interesting software project for you...

Software projects