A Little Bit of History and Why Restrictions Breed Creativity

If you think about the (original) actor model, you'll find that it's defined by what you are not allowed to do. You are not allowed to share state. You are not allowed to use everything else but message passing for communication. You are not allowed to randomly change your state, because you shall change your state only in response to a received message. If you think about functional programming, you'll find the exact same mindset. Functional programming is all about immutability (read: "you are not allowed to change objects") and prohibition of side-effects (read: "you are not allowed to manipulate your arguments or some global state"). There are good reasons for such restrictions, but let's talk about Erlang first.

If you are familiar with Erlang, you've probably noticed that the word "actor" is not used at all. Neither in function names nor in its documentation. In fact, the dissertation of Joe Armstrong (the inventor of Erlang) doesn't even include the word "actor". Why? Erlang is always referred to as the reference implementation of the actor model, isn't it?

Well, Erlang is based on a simple observation. In the "old days", people started implementing operation systems able to execute multiple programs in parallel. Mostly because punched cards and batch processing don't make fun. But this led to trouble. Serious trouble. In a naive mutlitasking-OS, you are limited by the amount of freedom you (and other developers) have, because if you are free to write everywhere you want, you can easily corrupt someone else's program. That's why we need an MMU in our computer. It's impossible to write a program if you know that someone else might manipulate your state (memory) at any point in time. So, the OS organized running programs into processes that do not share state and the world was sane again. You can start a program ten times and each of it will have a unique state. Pipes were added to allow processes to communicate. A process also can create a new process using fork. But then, people wanted concurrent execution of a single program, e.g., to keep GUI's responsive while doing background work. Threads were added, because fork is expensive and communicating via a pipe is complicated ... and the concurrency nightmare begun.

Erlang had the simple idea to fix the real issue here: processes are too expensive in modern OS's and communication between processes is too complicated. Do you know why Erlang does not have a threading library? Because no language should! Programs are written by humans and humans cannot think concurrently. Erlang's VM provides lightweight processes with a simple way to exchange messages. And it abstracts away all the dirty details. Plus, message passing is network transparent.

Message passing is something people can imagine. It is something people can reason about. Abstraction is always the answer in computer science. And abstraction means to build a simple model of something inherently complicated. Small systems communicating via message passing is something we can reason about. We can build large systems by "plugging" small systems together and we are still able to handle it. But hundreds of thousands of objects floating around, sharing state and run in parallel is hard to comprehend. To quote Rich Hickey (have a look at this channel9 video if you don't know him): "Mutable stateful objects are the new spaghetti code".

By not sharing memory, some problems just disappear. Isolation is a restriction, but it allows you to focus on your problems and you can use all your creativity and skill to do this. Threads are broken by design. Some bright minds are trying to fix them, but I think threads are best avoided. Unfortunately, we cannot "undo" threads and we cannot go back in time to implement OS's more suitable to write concurrent software. However, we can treat "std::thread" (and friends) the way we treat "goto". It's in the language/STL, but you should not use it in production code. Well, maybe someone implements something that's useful and safe on top of it (libcppa for example).

But let's get back to actors. Karl Hewitt et al. published an article about isolated computational entities, "actors", in the year 1973 (btw. there's an interesting video featuring Hewitt on channel9). It's a theoretically point of view to answer the question "what is the minimum set of axioms we need to describe concurrency?" Erlang came from the opposite direction. They said "writing concurrent, fault-tolerant software in traditional programming models is extremely difficult, how can we provide a better model?" Interestingly enough, Erlang developers came up with a programming paradigm that's in fact based on the axioms of the actor model. So to speak, the wheel was invented twice. But Armstrong didn't came up with a remarkable name for the programming paradigm while Hewitt did.

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).