C++ QD Locking Library

This is the C++ QD Locking library, which provides implementations of Queue Delegation (QD) locks for C++11 programs as described in the following two publications:

David Klaftenegger, Konstantinos Sagonas, and Kjell Winblad. Queue Delegation Locking. In IEEE Transactions on Parallel and Distributed Systems, 29(3):687-704, March 2018. IEEE. DOI: 10.1109/TPDS.2017.2767046
David Klaftenegger, Konstantinos Sagonas, and Kjell Winblad. Delegation Locking Libraries for Improved Performance of Multithreaded Programs. In Euro-Par 2014, Proceedings of the 20th International Conference, pp. 572-583, Volume 8632 in LNCS, August 2014. Springer. DOI: 10.1007/978-3-319-09873-9_48

The QD Locking library is distributed under the Simplified BSD License. Details can be found in the LICENSE file.

QD locks allow programmers to delegate critical sections to a lock. If the lock is currently free, this will use an efficient lock implementation. However, if the lock is already in use, the critical section will be delegated to the thread currently holding the lock, who becomes the helper. The helper will continue to execute critical sections for other threads until either it finds no more work, or some maximum number of executions has been reached.

This scheme results in drastically higher throughput than with traditional locking algorithms that transfer execution and shared data between threads.

For more details on QD locks see this website.

Requirements

This library makes use of libnuma, available on Linux. For other operating systems support can be turned off, at potential performance costs for NUMA machines. To install libnuma on Debian/Ubuntu and derivatives, run

sudo apt-get install libnuma-dev

For gentoo, run

sudo emerge sys-process/numactl

The following compilers are currently supported:

GCC: g++ versions 4.9 -- 10.2.1
Clang: clang++ versions 3.8 -- 11.0.1

Installation

mkdir build
cd build
cmake ../
make -j8
make test
make install

Usage

To use this library, include qd.hpp in your programs.

Here is a minimal example for how to use them:

#include<iostream>
#include<qd.hpp>
int main() {
	int counter = 0;
	qdlock lock;
	std::thread threads[4];
	for(auto& t : threads) {
		t = std::thread(
			[&lock, &counter]() {
				lock.delegate_n([&counter]() { counter++; });
			}
		);
	}
	for(auto& t : threads) {
	  t.join();
	}
	std::cout << "The counter value is " << counter << std::endl;
}

To compile and run a program it may be required to add /usr/local/include/ to your include path and /usr/local/lib to your library path. Compiling and running should then work using

g++ -I/usr/local/include/qd/ -L/usr/local/lib/ -Wl,-rpath=/usr/local/lib/ myprogram.cpp -pthread -lqd -o myprogram
./myprogram

Advanced Configuration

If required, you can adjust some settings in CMake:

cmake -DQD_DEBUG=OFF                     \
      -DQD_TESTS=ON                      \
      -DQD_USE_LIBNUMA=ON                \
      -DCMAKE_INSTALL_PREFIX=/usr/local  \
      ../

C library