cds::algo::flat_combining Namespace Reference

Flat combining. More...

Namespaces
	wait_strategy
	Wait strategies for flat_combining technique.

Data Structures
struct	empty_stat
	Flat combining dummy internal statistics. More...
class	kernel
	The kernel of flat combining. More...
struct	make_traits
	Metafunction converting option list to traits. More...
struct	publication_record
	Record of publication list. More...
struct	stat
	Flat combining internal statistics. More...
struct	traits
	Type traits of kernel class. More...

Enumerations
enum	request_value { req_EmptyRecord, req_Response, req_Operation }
	Special values of publication_record::nRequest. More...
enum	record_state { inactive, active, removed }
	publication_record state More...

Detailed Description

Flat combining.

Flat combining (FC) technique is invented by Hendler, Incze, Shavit and Tzafrir in their paper [2010] "Flat Combining and the Synchronization-Parallelism Tradeoff". The technique converts a sequential data structure to its concurrent implementation. A few structures are added to the sequential implementation: a global lock, a count of the number of combining passes, and a pointer to the head of a publication list. The publication list is a list of thread-local records of a size proportional to the number of threads that are concurrently accessing the shared object.

Each thread t accessing the structure to perform an invocation of some method f() on the shared object executes the following sequence of steps:

1. Write the invocation opcode and parameters (if any) of the method f() to be applied sequentially to the shared object in the request field of your thread local publication record (there is no need to use a load-store memory barrier). The request field will later be used to receive the response. If your thread local publication record is marked as active continue to step 2, otherwise continue to step 5.
2. Check if the global lock is taken. If so (another thread is an active combiner), spin on the request field waiting for a response to the invocation (one can add a yield at this point to allow other threads on the same core to run). Once in a while while spinning check if the lock is still taken and that your record is active (you may use any of wait_strategy instead of spinning). If your record is inactive proceed to step 5. Once the response is available, reset the request field to null and return the response.
3. If the lock is not taken, attempt to acquire it and become a combiner. If you fail, return to spinning in step 2.
4. Otherwise, you hold the lock and are a combiner.
   • Increment the combining pass count by one.
   • Execute a fc_apply() by traversing the publication list from the head, combining all non-null method call invocations, setting the age of each of these records to the current count, applying the combined method calls to the structure D, and returning responses to all the invocations. This traversal is guaranteed to be wait-free.
   • If the count is such that a cleanup needs to be performed, traverse the publication list from the head. Starting from the second item (we always leave the item pointed to by the head in the list), remove from the publication list all records whose age is much smaller than the current count. This is done by removing the node and marking it as inactive.
   • Release the lock.
5. If you have no thread local publication record allocate one, marked as active. If you already have one marked as inactive, mark it as active. Execute a store-load memory barrier. Proceed to insert the record into the list with a successful CAS to the head. Then proceed to step 1.

As the test results show, the flat combining technique is suitable for non-intrusive containers like stack, queue, deque. For intrusive concurrent containers the flat combining demonstrates less impressive results.

List of FC-based containers in libcds.

List of intrusive FC-based containers in libcds.

Enumeration Type Documentation

record_state

enum cds::algo::flat_combining::record_state

publication_record state

Enumerator
inactive	Record is inactive.
active	Record is active.
removed	Record should be removed.

request_value

enum cds::algo::flat_combining::request_value

Special values of publication_record::nRequest.

Enumerator
req_EmptyRecord	Publication record is empty.
req_Response	Operation is done.
req_Operation	First operation id for derived classes.