Friday, January 3, 2014

Lambdas and the Left-Right technique

PS: We had a copy-paste error on our benchmark that significantly altered the results for LEFTRIGHT_Lambda. this has now been fixed and the plots shown here are now correct.

Last week we posted a link to the Left-Right technique on the JSR-166 mailing list. This is a mailing list devoted to concurrency, mostly from the practical side, with lots of experts in it, and it is managed by Doug Lea.
We've had some good feedback from some of the experts, and even some cool improvements.
One of the ideas was by Peter Levart and he was kind enough to make an implementation of the LR technique using lambdas, that is, a very "functional like" implementation:
http://cr.openjdk.java.net/~plevart/misc/LeftRight/LeftRight.java

The LR technique is particularly suited for this kind of functional approach because it requires the same (write) operation to be applied twice on the two instances. By providing a functional API like Peter has done, it simplifies the coding and usage of LR in your own data structures and objects.
In his implementation he used two LongAdders as the readIndicators, like we had done for the LongAdderRWLock, but it is possible to use other readIndicators, which is pretty cool, I think!
You can access his code here: http://cr.openjdk.java.net/~plevart/misc/LeftRight/

This kind of "generality" and ease of coding is a big advantage, and yesterday, Andreia spent the afternoon to get this code integrated into our microbenchmark suite so we could compare it against our own non-functional implementations, and even a (mostly) functional implementation that we had done earlier last year, that we never made public (mostly because working with netbeans-lambda sucked... and still does, but I'm sure it will get better with time, as the tool matures).

The result of her hard work is show below, where the names in the legend have the following correspondence:
LongAdderExtRWLock: A TreeSet protected with a Reader-Writer lock, whose implementation is based on the algorithm we described a year ago (same as C-RW-WP on the "NUMA Aware Reader Writer Locks" paper), using a single LongAdderExt as readIndicator.
http://sourceforge.net/projects/ccfreaks/files/java/src/com/concurrencyfreaks/locks/LongAdderExtRWLock.java
LEFTRIGHT_Lambda: "Functional" approach with LongAdders as readIndicators
https://sourceforge.net/projects/ccfreaks/files/java/src/com/concurrencyfreaks/experimental/leftright/
LRLongAdderCollection: "Semi-functional" approach using the LRCollections interface and LongAdderExt as readIndicators
https://sourceforge.net/projects/ccfreaks/files/java/src/com/concurrencyfreaks/collections/
LRLongAdderTreeSet: Non-functional implementation, using LongAdderExt as readIndicator
LRScalableTreeSet: Non-functional implementation, using a CLQ+array as readIndicator
http://sourceforge.net/projects/ccfreaks/files/papers/LeftRight/LRScalableTreeSet.java

The microbenchmark used to make these plots can be obtained here:
https://sourceforge.net/projects/ccfreaks/files/java/src/com/concurrencyfreaks/tests/TestTreeSetFullRebalanceLambda.java










The horizontal axis shows the number of threads on the 32-core opteron, and the vertical axis show the summed up number of operations per second (reads plus modifys), for different (statistical) ratios of modify operations: 30%, 10%, 1% and 0.1%. The operations were done on a small TreeSet with 1000 elements.
Unlike what we had seen on the previous version of this post (with the incorrectly made plots) the LEFTRIGHT_Lambda provides just as good performance as the "hard-coded" methods, which is pretty cool, because it is much easier to use.

So I guess lambdas are cool!

No comments:

Post a Comment