Archive

Archive for July, 2012

A Lightweight Approach to Coroutine/Continuation in C/C++

July 24, 2012 Leave a comment

It is considered to be useful to support efficient user-level thread scheduling, which is usually referred as Coroutine or Continuation. Its key building block is about leaving an execution point and getting back to that point, as if leaving does not happen. The common translation of the building block leads to CPU level context switch just as threads. Based on this wrong understanding, it typically requires primitives from native OS or runtime VM, such as fiber in Windows. The building block, however, is about the semantics of control flow.

When the requirement is clarified, the whole thing can be simplified as follows. Let’s start with a piece of simple runnable code.

#include <stdio.h>

struct Run {
    int cc;
    int i;
    Run() : cc(0) {}

    bool operator ()() {
        switch (cc) {
        case 0:;
            puts("a");
            cc = 1;
            return true;
        case 1:;
            for (i = 0; i < 2; ++i) {
                puts("b");
                cc = 2;
                return true;
        case 2:;
            }
            cc = 3;
            return true;
        case 3:;
            puts("c");
            cc = 4;
            return true;
        }
        return false;
    }
};

int main() {
    Run run;
    while (run());
    return 0;
}

This looks silly. Why not use function pointers to build a blazing beautiful dispatch table? The reason is simple. Function boundaries truncate program flow information and lose semantics of continuation. The following code is cleaned by using MacrO.

#include <stdio.h>

#define CallccBegiN(cc) switch (cc) { case 0:
#define YielD() cc = __LINE__; return true; case __LINE__:
#define CallccEnD() } return false

struct Run {
    int cc;
    int i;
    Run() : cc(0) {}

    bool operator ()() {
        CallccBegiN(cc);
            puts("a");
            YielD();
            for (i = 0; i < 2; ++i) {
                puts("b");
                YielD();
            }
            YielD();
            puts("c");
        CallccEnD();
    }
};

int main() {
    Run run;
    while (run());
    return 0;
}

The trick here is the feature of switch-case in C/C++ that can branch into if/for flow structures. This limits the user code from using switch-case. If compiler extension supports the address of label operator &&label, such as gcc, it could be a better trick.

Advertisements
Categories: C++, Dev

v-table on the reinterpret_cast

July 22, 2012 Leave a comment

In this small writing, I’ll show you a trick to implement multiple copies of an interface by a single class. Let’s consider two interfaces I1 and I2.

struct I1 {
   virtual void foo() = 0;
};

struct I2 {
   virtual void bar() = 0;
};

When a pointer of I1 * is cast to I2 * by reinterpret_cast, it’s still safe to call its method from v-table perspective, well, as long as memory layout (though there is none in this example). Thus, this kind of pointer cast can be considered as casting two compatible interface pointers.

It’s not a complex trick and a piece of instantly runnable code is more than many words.

#include <stdio.h>

// Infrastructure {
// IFooX is a meta generator to ensure that interfaces are generated compatible
#define IFooX(id) \
struct IFoo##id {\
    virtual void invoke##id() = 0;\
    IFoo *getIFoo##id() {\
        return reinterpret_cast<IFoo *>(this);\
    }\
}

IFooX(); // define the infrastructure level interface IFoo that can be
         // shared among modules or crossing applications.
// }

// Application {
IFooX(1);
IFooX(2);

struct Application : IFoo1, IFoo2 {
    virtual void invoke1() {
        puts("invoke1");
    }

    virtual void invoke2() {
        puts("invoke2");
    }
};

int main() {
    Application application;
    application.getIFoo1()->invoke();
    application.getIFoo2()->invoke();
    return 0;
}
// }
Categories: C++, Dev

static_cast for inherited customization

July 17, 2012 Leave a comment

Traditionally, virtual is used for a class that can be customized partially. Let’s work with the following design.

class Base {
public:
    void action() {
        puts("action");
        customized();
    }

protected:
    virtual void customized() {
        puts("no customization");
    }
};

When the class is used with MyApp.

class MyApp : public Base {
protected:
    virtual void customized() {
        puts("customized by my app");
    }
};

This use of virtual is perfect from design perspective, although the class Base is not designed as an interface. The only problem is that calling the method customized() cannot be optimized as inline. Well, this is not a problem when customized() is only called once in the method action(). But what if it’s going to be called many times with a trivial implementation? The jump call could simply waste lots of CPU power.

One approach to solve the problem is to use a function object as an argument. Note that it should not be something taking address of a function address like std::mem_fun.

class Base {
public:
    template <typename T>
    void action(T customized) {
        puts("action");
        customized();
    }
};

This change brings a little bit trouble when we just want the inherited class to implement the method customized(). Since when a function object is bound to the method, the method is then on-the-fly to generate new code depending on the customization. If the class Base is not actually an interface, it should not be a problem to bind the whole thing to it’s application customization.

Here goes the final design.

template <typename T>
class Base {
public:
    void action() {
        puts("action");
        static_cast<T *>(this)->customized();
    }

    void customized() {
        puts("no customization");
    }
};

The new code driving the class Base.

class MyApp : public Base<MyApp> {
public:
    void customized() {
        puts("customized by my app");
    }
};

It’s a rule of static_cast playing some magic here. It has a strong guarantee that an object pointer of class/struct being cast to a pointer of new type must have inheritance relationship. The following code will fail to compile when action() is called if class MyApp1 is not inherited from class MyApp, so we are going to make neither wrong use of library classes nor typo mistakes.

class MyApp : public Base<MyApp1> {
// ...
};
Categories: C++, Dev