Monthly Archives: February 2014

Synchronous and Asancronous binary tree comparison

if you have not taken “Principles of reactive programming” course about advanced Scala and Aker framework, probably you are not using internet properly, think again. It is a wonderful course from EPFL, one of the hardest in Coursera.

To pass this course you have to complete some programming excersized. One of them is “Actor Binary Tree”, In this example you have to implement an asynchronous search binary tree. When you insert a node, it is distributed asynchronously through the tree. Nothing is locked and this makes it really fast. The sender actor gets acknowledged when the insertion is done.

In theory the idea is really beautiful,  but how useful is it in reality? Why we have to use this relatively complex architecture. The answer is that because it is asynchrouns nothing is locked and you should have a very high performance.

But how it comares with a similar pure java implementation ? For consistency usually we lock the tree. That definitely will not compete. But if we use an immutable version we do not need to worry about the consistency.

To do the comparison I searched and found an immutable binary tree in Kansas State University.

To compare I will insert large numbers of nodes in both implementations and wait untill all are acknowledged and measure the time. In Java implementation different number of threads is tried.

BinarySearchComparison

 

The maximum TPS of Scala version is 2952 and java version 2701739, more than 90 times.

So the conclusion is, at least if the operation itself is fast and not IO intensive, it is no use in usage of asynchronous type of programming. The overhead of aker is considerable if the operations themselves are fast.

 

The source for java implementation is available in github.