Guards! Guards!

(no, this post is not about the Discworld novel)

Guards are a new feature in libcppa. More precisely, it's an adaption of Erlangs guard sequences for patterns. A guard is an optional expression that evaluates to either true or false for a given input (message). Guards can be used to constrain a given match statement by using placeholders (_x1 - _x9) as shown in the example below.

using namespace cppa;
using namespace cppa::placeholders;
receive_loop(
  on<int>().when(_x1 % 2 == 0) >> []() {
    // int is even
  },
  on<int>() >> []() {
    // int is odd
  }
);

Guard expressions are a lazy evaluation technique (somewhat like boost lambdas). The placeholder _x1 is substituted with the first value of an incoming message. You can use all binary comparison and arithmetic operators as well as "&&" and "||". In addition, there are two functions designed to be used in guard expressions: gref and gcall. The function gref creates a reference wrapper. It's similar to std::ref but it is always const and 'lazy'. A few examples to illustrate some pitfalls:

int ival = 42;
receive(
  on<int>().when(ival == _x1) // (1) ok, matches if _x1 == 42
  on<int>().when(gref(ival) == _x1) // (2) ok, matches if _x1 == ival
  on<int>().when(std::ref(ival) == _x1) // (3) ok, because of placeholder
  on<anything>().when(gref(ival) == 42) // (4) ok, matches everything as long as ival == 42
  on<anything>().when(std::ref(ival) == 42) // (5) compiler error
);

The statement std::ref(ival) == 42 is evaluated immediately and returns a boolean, whereas gref(ival) == 42 creates a guard expression. Thus, you should always use gref instead of std::ref to avoid subtle errors.

By the way, gref is a great way to reduce verbosity of receive loops:

bool done = false;
do_receive(
  // ...
  on<atom("shutdown")>() >> [&]() {
    done = true;
  }
)
.until(gref(done));
//equal to: .until([&]() { return done; })

The second function, gcall, encapsulates a function call. It's usage is similar to std::bind, but there is also a short version for unary functions: gcall(..., _x1) is equal to _x1(...).

auto vec_sorted = [](std::vector<int> const& vec) {
  return std::is_sorted(vec.begin(), vec.end());
};
receive(
  on<std::vector<int>>().when(gcall(vec_sorted, _x1)) // equal to:
  on<std::vector<int>>().when(_x1(vec_sorted))) // ...
);

Placeholders provide some more convenience member functions besides operator(). A few code snippets:

_x1.starts_with("hello")
_x1.size() > 10
_x1.in({"abc", "def"})
_x1.not_in({0, 10, 100})
_x1.empty()
_x1.not_empty()
_x1.front() == 42

A final note: you don't have to check if a container is empty before calling _x1.front(), because front() returns an option for a reference to the first element.

Have fun!

A Few Words About Theron

Theron is currently the only existing actor library for C++ besides libcppa. It implements event-based message processing without mailbox, using registered member functions as callbacks. I wanted to include Theron to my three benchmarks, but I had some trouble to get Theron running on Linux. I've compiled Theron in release mode, ran its PingPong benchmark ... and got a segfault. GDB pointed me to the DefaultAllocator implementation and I could run the benchmarks after replacing the memory management with plain malloc/free. Thus, the shown results might be some percentages better with a fixed memory management. However, I was unable to get results for the Actor Creation Overhead benchmark because Theron crashed for more than 2¹⁰ actors.

Theron has two ways of sending a message to an actor, because it distincts between references and addresses. The push method can be used only if one has a reference to an actor. This is usually only the case for the creator of an actor. The send method uses addresses and is the general way to send messages.

The results for the Mixed Scenario benchmark are as follows.

Theron yields good results on two and four cores. However, the more concurrency we add, the more time Theron needs in the mixed scenario. I don't know about Theron's internals, but this is a common behavior of mutex-based software in many-core systems and cannot be explained by the "missing" memory management.

I used Theron in version 3.03. As always, the benchmarks ran on a virtual machine with Linux using 2 to 12 cores of the host system comprised of two hexa-core Intel® Xeon® processors with 2.27GHz. All values are the average of five runs.

The sources can be found on github in the benchmark folder (theron_mailbox_performance.cpp and theron_mixed_case.cpp).

Mailbox Part 2

It's been a while since I've posted Mailbox Part 1 and I promised a benchmark for a 1:N communication scenario for up to 12 cores. So here it is. This benchmark compares libcppa to Erlang and Scala with its two standard library implementations and Akka.

The benchmark uses 20 threads sending 1,000,000 messages each, except for Erlang which does not have a threading library. In Erlang, I spawned 20 actors instead. The minimal runtime of this benchmark is the time the receiving actor needs to process 20,000,000 messages and the overhead of passing the messages to the mailbox. More hardware concurrency leads to higher synchronization between the sending threads, since the mailbox acts as a shared resource.

Both libcppa implementations show similar performance to Scala (receive) on two cores but have a faster increasing curve. The message passing implementation of Erlang does not scale well for this use case. The more concurrency we add, the more time the Erlang program needs, up to an average of 600 seconds on 12 cores. The results are clipped for visibility purposes in the graph. The increase in runtime for libcppa is similar to the increase seen in the Actor Creation Overhead benchmark and is caused by the scheduler (the cached stack algorithm scales very well and is not a limiting factor here). The overhead of stack allocation is negligible in this use case. Thus, the run time of both libcppa implementations is almost identical.

The benchmarks ran on a virtual machine with Linux using 2 to 12 cores of the host system comprised of two hexa-core Intel® Xeon® processors with 2.27GHz. All values are the average of five runs.

The sources can be found on github (MailboxPerformance.scala, mailbox_performance.erl and mailbox_performance.cpp).

RIP invoke_rules

The class invoke_rules was among the first classes of libcppa. In fact, it received a lot of refactoring even before the first commit on github. However, it's finally gone. If your code fails to compile with the current version, this is how to fix your code:

invoke_rules → partial_function
timed_invoke_rules → behavior

The class invoke_rules had too much changes in the past and its name isn't very well chosen. In fact, the implemented behavior of it already was identical to a partial function. But it had a brother called timed_invoke_rules that was a partial function with a timeout. That's pretty much the definition of an actor's behavior, isn't it? It's an old remains from the time I've implemented on() and after(). The new partial_function/behavior interface is straightforward and much more intuitive.

Actor Creation Overhead

libcppa provides two actor implementations: a context switching and an event-based implementation.

The context-switching implementation is easier to use from a user's point of view. One has to write less code and receives can be nested. But there is a downside to this approach: each actor allocates its own stack. As an example for a current mainstream system: Mac OS X Lion defines the two constants SIGSTKSZ = 131072 and MINSIGSTKSZ = 32768 in its system headers. SIGSTKSZ is the recommended stack size in bytes and MINSIGSTKSZ is the minimum allowed stack size in bytes. Assuming a system with 500,000 actors, one would require a memory usage of at least 15 GB of RAM for stack space only. This would rise up to 61 with the recommended stack size instead in use. This clearly does not scale well for large systems. The event-based implementation uses fewer system resources, allowing developers to use hundreds of thousands of actors. Creating an event-based actor is cheap and lightweight but you have to provide a class-based implementation. Furthermore, you cannot use receive() since this would block the calling worker thread. However, the behavior-based approach is slightly different to use but fairly easy to understand and use (see the Dining Philosophers example).

The following benchmark measures the overhead of actor creation. It recursively creates 2¹⁹ (524,288) actors, as the following pseudo code illustrates.

spreading_actor(Parent):
  receive:
    {spread, 0} =>
      Parent ! {result, 1}
    {spread, N} =>
      spawn(spreading_actor, self)) ! {spread, N-1}
      spawn(spreading_actor, self)) ! {spread, N-1}
      receive:
        {result, X1} =>
          receive:
            {result, X2} =>
              Parent ! {result, X1+X2}

main():
  spawn(spreading_actor, self)) ! {spread, 19}
  receive:
    {result, Y} =>
      assert(2^19 == Y)

This measurement tests how lightweight actor implementations are. We did not test the thread-mapped actor implementation of Scala, because the JVM cannot handle half a million threads. And neither could a native application.

It is not surprising that Erlang yields the best performance, as its virtual machine was build to efficiently handle actors. Furthermore, we can see the same increase in runtime caused by more hardware concurrency for the event-based libcppa implementation as in our previous benchmark. However, the context-switching (stacked) implementation clearly falls short in this scenario. Please note that this benchmark used the minimal stack size to be able to create half a million actors. Per default, libcppa uses the recommended stack size! Consider using event-based actors whenever possible, especially in systems consisting of a large amount of concurrently running actors.

The benchmarks ran on a virtual machine with Linux using 2 to 12 cores of the host system comprised of two hexa-core Intel® Xeon® processors with 2.27GHz. All values are the average of five runs.

The sources can be found on github (ActorCreation.scala, actor_creation.erl and actor_creation.cpp).

libcppa vs. Erlang vs. Scala Performance (Mixed Scenario)

Remark

Please note that the results of the original post are heavily outdated. The graph below illustrates some newer benchmark results using Scala 2.10, Erlang 5.10.2, and libcppa 0.9. Rather than running the benchmark on a 12-core machine, we have used a 64-core machine (4 CPUs with 16 cores each). Furthermore, we have used a slightly different set of parameters: 100 rings, 50 actors each, initial token value of 1000, and 5 repetitions. We will publish a more throughout evaluation in the near future.

Original Post

This benchmark simulates a use case with a mixture of operations. The continuous creation and termination of actors is simulated along with a total of more than 50,000,000 messages sent between actors and some expensive calculations are included to account for numerical work load. The test program creates 20 rings of 50 actors each. A token with initial value of 10,000 is passed along the ring and decremented once per iteration. A client receiving a token always forwards it to the next client and finishes execution whenever the value of the token was 0. The following pseudo code illustrates the implemented algorithm.

chain_link(Next):
  receive:
    {token, N} =>
      next ! {token, N}
      if (N > 0) chain_link(Next)

worker(MessageCollector):
  receive:
    {calc, X} =>
      MessageCollector ! {result, prime_factorization(X)}

master(Worker, MessageCollector):
  5 times:
    Next = self
    49 times: Next = spawn(chain_link, Next)
    Next ! {token, 10000}
    Done = false
    while not Done:
      receive:
        {token, X} =>
          if (X > 0): Next ! {token, X-1}
          else: Done = true
  MessageCollector ! {master_done}

Each ring consists of 49 chain_link actors and one master. The master recreates the terminated actors five times. Each master spawns a total of 245 actors and the program spawns 20 master actors. Additionally, there is one message collector and one worker per master. A total of 4921 actors (20+(20∗245)+1) are created but no more than 1021 (20+20+(20∗49)+1) are running concurrently. The message collector waits until it receives 100 (20∗5) prime factorization results and a done message from each master. Prime factors are calculated to simulate some work load. The calculation took about two seconds on the tested hardware in our loop-based C++ implementation. Our tail recursive Scala implementation performed at the same speed, whereas Erlang needed almost seven seconds.

As expected, the thread-based Scala implementation yields the worst performance though the runtime increase for eight and more cores surprises. Akka is significantly faster than both standard library implementations of Scala. Erlang performs very well, given the fact that its prime factorization is more than three times slower. The very efficient scheduling of Erlang, which is the only implementation under test that performs preemptive scheduling, is best at utilizing hardware concurrency. The current overhead of the libcppa scheduler hinders better performance results. The overhead of stack allocation and context switching is about 10-20% in this benchmark for up to six cores where the scheduler is stretched to its limits.

This benchmark shows that libcppa is competitive and performs at comparable speed to well-tested and established actor model implementations. Nevertheless, the current scheduling algorithm is not able to utilize more than six cores efficiently by now.

The benchmarks ran on a virtual machine with Linux using 2 to 12 cores of the host system comprised of two hexa-core Intel® Xeon® processors with 2.27GHz. All values are the average of five runs.

The sources can be found on github (MixedCase.scala, mixed_case.erl and mixed_case.cpp).

Dining Philosophers

The Dining Philosophers Problem is a well-known exercise in computer science for concurrent systems. Recently, I've found an implementation for Akka that's an adaption of this algorithm of Dale Schumacher. I think it's a pretty nice example program to introduce libcppa's event-based actor implementation. The following source code is an adaption of the Akka example implementation.


Let's start with the straightforward chopstick implementation.

#include "cppa/cppa.hpp"
using std::chrono::seconds;
using namespace cppa;
// either taken by a philosopher or available
struct chopstick : sb_actor<chopstick> {

  behavior& init_state; // a reference to available
  behavior available;

  behavior taken_by(const actor_ptr& philos) {
    // create a behavior new on-the-fly
    return (
      on<atom("take"), actor_ptr>() >> [=](actor_ptr other) {
        send(other, atom("busy"), this);
      },
      on(atom("put"), philos) >> [=]() {
        become(&available);
      }
    );
  }

  chopstick() : init_state(available) {
    available = (
      on<atom("take"), actor_ptr>() >> [=](actor_ptr philos) {
        send(philos, atom("taken"), this);
        become(taken_by(philos));
      }
    );
  }

};

The class fsm_actor uses the Curiously Recurring Template Pattern to initialize the actor with the behavior stored in the member init_state. We don't really have an initial state. Thus, init_state is a reference to the behavior available. You also could inherit from event_based_actor and override the member function init() by hand. But using an fsm_actor is more convenient. You change the state/behavior of an actor by calling become. It takes either a pointer to a member or an rvalue. The member function taken_by creates a behavior "on-the-fly". You could achieve the same by using a member storing the 'owning' philosopher. But why use member variables if you don't have to? This solution is easier to understand than manipulating some internal state.

Btw: you should always use [=] in lambda expressions for event-based actors. This copies the this pointer into the lambda and you have access to all members. You should never use references, because become always immediately returns. If your lambda finally gets called, everything that was previously on the stack is gone! All your references are guaranteed to cause undefined behavior.


The implementation of philosopher is a little bit longer. Basically, we implement the following state diagram.

/*
 *                +-------------+  {(busy|taken), Y}
 *      /-------->|  thinking   |<------------------\
 *      |         +-------------+                   |
 *      |                |                          |
 *      |                | {eat}                    |
 *      |                |                          |
 *      |                V                          |
 *      |         +-------------+ {busy, X}  +-------------+
 *      |         |   hungry    |----------->|   denied    |
 *      |         +-------------+            +-------------+
 *      |                |
 *      |                | {taken, X}
 *      |                |
 *      |                V
 *      |         +-------------+
 *      |         | wait_for(Y) |
 *      |         +-------------+
 *      |           |    |
 *      | {busy, Y} |    | {taken, Y}
 *      \-----------/    |
 *      |                V
 *      | {think} +-------------+
 *      \---------|   eating    |
 *                +-------------+
 *
 *
 * [ X = left  => Y = right ]
 * [ X = right => Y = left  ]
 */

This is a simplification of the original diagram. A philosopher becomes hungry after receiving an atom("eat") and then tries to obtain its left and right chopstick. A philosopher eats if it obtained both chopsticks, otherwise it will think again.

struct philosopher : sb_actor<philosopher> {

  std::string name; // the name of this philosopher
  actor_ptr left;   // left chopstick
  actor_ptr right;  // right chopstick

  // note: we have to define all behaviors in the constructor because
  //       non-static member initialization are not (yet) implemented in GCC
  behavior thinking;
  behavior hungry;
  behavior denied;
  behavior eating;
  behavior init_state;

A philosopher has a name, a left and a right chopstick and a bunch of possible behaviors. Hopefully, GCC has non-static member initialization in the next version. For now, we have to define all behavior in the constructor, except for wait_for, which is realized as a function similar to taken_by of chopstick.

  // wait for second chopstick
  behavior waiting_for(const actor_ptr& what) {
    return (
      on(atom("taken"), what) >> [=]() {
        // create message in memory to avoid interleaved
        // messages on the terminal
        std::ostringstream oss;
        oss << name
            << " has picked up chopsticks with IDs "
            << left->id()
            << " and "
            << right->id()
            << " and starts to eat\n";
        cout << oss.str();
        // eat some time
        delayed_send(this, seconds(5), atom("think"));
        become(&eating);
      },
      on(atom("busy"), what) >> [=]() {
        send((what == left) ? right : left, atom("put"), this);
        send(this, atom("eat"));
        become(&thinking);
      }
    );
  }

Our constructor defines all behaviors as well as the three member variables storing name and left and right and chopstick.

  philosopher(const std::string& n, const actor_ptr& l, const actor_ptr& r)
  : name(n), left(l), right(r) {
    // a philosopher that receives {eat} stops thinking and becomes hungry
    thinking = (
      on(atom("eat")) >> [=]() {
        become(&hungry);
        send(left, atom("take"), this);
        send(right, atom("take"), this);
      }
    );
    // wait for the first answer of a chopstick
    hungry = (
      on(atom("taken"), left) >> [=]() {
        become(waiting_for(right));
      },
      on(atom("taken"), right) >> [=]() {
        become(waiting_for(left));
      },
      on<atom("busy"), actor_ptr>() >> [=]() {
        become(&denied);
      }
    );
    // philosopher was not able to obtain the first chopstick
    denied = (
      on<atom("taken"), actor_ptr>() >> [=](actor_ptr& ptr) {
        send(ptr, atom("put"), this);
        send(this, atom("eat"));
        become(&thinking);
      },
      on<atom("busy"), actor_ptr>() >> [=]() {
        send(this, atom("eat"));
        become(&thinking);
      }
    );
    // philosopher obtained both chopstick and eats (for five seconds)
    eating = (
      on(atom("think")) >> [=]() {
        send(left, atom("put"), this);
        send(right, atom("put"), this);
        delayed_send(this, seconds(5), atom("eat"));
        cout << (  name
             + " puts down his chopsticks and starts to think\n");
        become(&thinking);
      }
    );
    // philosophers start to think after receiving {think}
    init_state = (
      on(atom("think")) >> [=]() {
        cout << (name + " starts to think\n");
        delayed_send(this, seconds(5), atom("eat"));
        become(&thinking);
      }
    );
  }

};

The source code is a straightforward implementation of the state diagram. Our main starts five chopsticks and five philosophers. We use an anonymous group to send the initial {think} message to all philosophers at once. You could send five single messages as well.

int main(int, char**) {
  // create five chopsticks
  cout << "chopstick ids:";
  std::vector<actor_ptr> chopsticks;
  for (size_t i = 0; i < 5; ++i) {
    chopsticks.push_back(spawn<chopstick>());
    cout << " " << chopsticks.back()->id();
  }
  cout << endl;
  // a group to address all philosophers
  auto dinner_club = group::anonymous();
  // spawn five philosopher, each joining the Dinner Club
  std::vector<std::string> names = { "Plato", "Hume", "Kant",
                                     "Nietzsche", "Descartes" };
  for (size_t i = 0; i < 5; ++i) {
    spawn_in_group<philosopher>(dinner_club,
                                names[i],
                                chopsticks[i],
                                chopsticks[(i+1) % chopsticks.size()]);
  }
  // tell philosophers to start thinking
  send(dinner_club, atom("think"));
  // real philosophers are never done
  await_all_others_done();
  return 0;
}

The full source code can be found in the examples folder on github.

Have fun!