Flat Combiner

This project offers to include synchronization primitives based on the original 2010 paper by Hendler et al.

Introduction

The core idea of flat combining is the cost of obtaining a lock to a shared data structure is amortized by threads publishing a request to a publication list and a combiner (a thread that acquired the lock)is made aware of requests published by other waiting threads by scanning a shared publication list

Usage

This library exposes two combiner classes: FlatCombiner and HandoffCombiner through a shared Combiner interface and three structures that use these combiners as their sync primitives through the standard JDK interfaces

• Using a raw combiner

    Combiner<Integer> combiner = new FlatCombiner<>(0);
    int i = combiner.combine(i -> ++i);   

• Using an inbuilt List combiner

    List<Integer> list = Combiners.list();
    list.add(1); 

• Using an inbuilt Set combiner

    Set<Integer> set = Combiners.set();
    set.add(1); 

• Using an inbuilt Queue combiner

    Queue<Integer> queue = Combiners.queue();
    queue.offer(1); 

Both combiner implementations use thread local variables and might be susceptible to memory leaks based on how they're used in a system.

Benchmarks

This project is benchmarked using JMH. It includes benchmarks against the inbuilt JDK implementations for lock-free/lock-based <= O(N) structures.

The benchmarks are recorded using WaitStrategy#park(1), prune threshold as 500 and max combining pass as 20. These show the best performance of all params tested overall and perform similarly and sometimes better than the built-in JDK concurrent implementations.

The results using spin wait / yield WaitStrategy are competitive against the JDK implementations up to number of threads = no. of available CPU cores.

Running the benchmarks

You can run all the benchmarks as so.

    mvn clean package
    cd fc-jmh
    java -jar benchmark.jar 

Testing

This project is tested using both JUnit and JCStress to ensure sequential and concurrent correctness.

Running the tests

You can run all the JCStress tests as so.

    mvn clean package
    cd fc-stress
    java -jar jcstress.jar 

LICENSE

MIT