junction

Concurrent data structures in C++

1,399

151

1,399

View on GitHub

Top Related Projects

concurrentqueue

9,815

A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

MPMCQueue

1,174

A bounded multi-producer multi-consumer concurrent queue written in C++11

folly

28,056

An open-source C++ library developed and used at Facebook.

oneTBB

5,580

oneAPI Threading Building Blocks (oneTBB)

libcds

2,546

A C++ library of Concurrent Data Structures

Quick Overview

Junction is a high-performance concurrent data structure library for C++. It provides lock-free and wait-free algorithms for common data structures, designed to maximize performance in multi-threaded environments. The library aims to offer efficient alternatives to traditional synchronization primitives.

Pros

High performance in multi-threaded scenarios
Lock-free and wait-free algorithms for reduced contention
Thoroughly tested and benchmarked implementations
Modern C++ design with template-based interfaces

Cons

Limited documentation and examples
Relatively small community and ecosystem
May require advanced knowledge of concurrent programming to use effectively
Not actively maintained (last commit was in 2018)

Code Examples

Creating and using a ConcurrentMap:

#include <junction/ConcurrentMap_Leapfrog.h>
#include <string>

junction::ConcurrentMap_Leapfrog<int, std::string> map;
map.assign(42, "Hello");
std::string* value = map.find(42);
if (value) {
    std::cout << *value << std::endl; // Outputs: Hello
}

Using a ConcurrentQueue:

#include <junction/ConcurrentQueue_Bounded.h>

junction::ConcurrentQueue_Bounded<int> queue(100); // Queue with capacity 100
queue.push(10);
queue.push(20);

int value;
if (queue.pop(value)) {
    std::cout << "Popped: " << value << std::endl; // Outputs: Popped: 10
}

Implementing a thread-safe counter:

#include <junction/Core.h>
#include <turf/Atomic.h>

turf::Atomic<uint64_t> counter(0);

// In multiple threads:
uint64_t value = counter.fetchAdd(1);
std::cout << "Counter value: " << value << std::endl;

Getting Started

To use Junction in your C++ project:

Clone the repository:

git clone https://github.com/preshing/junction.git

Add the junction/include directory to your include path.

Include the desired headers in your C++ code:

#include <junction/ConcurrentMap_Leapfrog.h>
#include <junction/ConcurrentQueue_Bounded.h>

Compile your code with C++11 or later standard enabled.

Note: Junction uses CMake for building tests and benchmarks, but you can use the headers directly in your project without additional build steps.

Competitor Comparisons

concurrentqueue

9,815

A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

Pros of concurrentqueue

Higher performance in many scenarios, especially for single-producer/single-consumer cases
More extensive documentation and benchmarks available
Simpler API with fewer dependencies

Cons of concurrentqueue

Limited to queue data structures, while Junction offers a broader range of concurrent containers
May have higher memory usage in some cases due to its lock-free design
Less flexibility in terms of memory allocation strategies

Code Comparison

concurrentqueue:

moodycamel::ConcurrentQueue<int> q;
q.enqueue(42);
int item;
bool success = q.try_dequeue(item);

Junction:

junction::ConcurrentQueue<int> q;
q.push(42);
int item;
bool success = q.pop(item);

Summary

Both concurrentqueue and Junction provide concurrent data structures for C++, but they have different focuses. concurrentqueue specializes in high-performance lock-free queues, while Junction offers a broader range of concurrent containers. concurrentqueue may be simpler to use and perform better in many scenarios, especially for queue-specific use cases. However, Junction provides more flexibility and a wider variety of concurrent data structures if needed.

MPMCQueue

1,174

A bounded multi-producer multi-consumer concurrent queue written in C++11

Pros of MPMCQueue

Simpler implementation, focusing solely on multi-producer, multi-consumer queues
Potentially lower memory footprint due to its specialized nature
More recent development and maintenance

Cons of MPMCQueue

Limited to queue data structures, while Junction offers a broader range of concurrent containers
May have less extensive testing and real-world usage compared to Junction

Code Comparison

MPMCQueue:

template <typename T>
class MPMCQueue {
public:
  explicit MPMCQueue(const size_t capacity);
  bool try_push(const T& value);
  bool try_pop(T& value);
};

Junction:

template <typename T, typename Traits = DefaultTraits>
class ConcurrentMap {
public:
  bool assign(const Key& key, const T& value);
  bool get(const Key& key, T& result) const;
  bool erase(const Key& key);
};

Summary

MPMCQueue is a specialized, lightweight solution for multi-producer, multi-consumer queues, while Junction offers a more comprehensive set of concurrent containers. MPMCQueue may be preferable for projects requiring simple queue implementations, whereas Junction provides more versatility for complex concurrent data structures. The choice between the two depends on the specific requirements of the project and the desired balance between simplicity and feature richness.

folly

28,056

An open-source C++ library developed and used at Facebook.

Pros of Folly

Extensive library with a wide range of utilities and data structures
Actively maintained by Facebook with frequent updates
Large community support and extensive documentation

Cons of Folly

Larger codebase and potential overhead for smaller projects
Steeper learning curve due to its extensive feature set
May introduce dependencies on other Facebook libraries

Code Comparison

Junction (Concurrent Map):

junction::ConcurrentMap_Linear<int, int> map;
map.assign(42, 100);
int value = map.get(42);

Folly (Concurrent Map):

folly::ConcurrentHashMap<int, int> map;
map.insert(42, 100);
int value = map.find(42)->second;

Key Differences

Junction focuses specifically on concurrent data structures, while Folly is a more comprehensive utility library
Junction emphasizes lock-free algorithms, whereas Folly provides a broader range of concurrency tools
Folly has a larger ecosystem and integration with other Facebook projects, while Junction is more standalone

Use Cases

Choose Junction for projects requiring high-performance concurrent data structures with minimal dependencies
Opt for Folly when working on larger projects that can benefit from its extensive utility set and integration with other Facebook libraries

oneTBB

5,580

oneAPI Threading Building Blocks (oneTBB)

Pros of oneTBB

More comprehensive library with a wider range of parallel programming tools
Actively maintained by Intel with regular updates and optimizations
Extensive documentation and community support

Cons of oneTBB

Steeper learning curve due to its broader scope
May be overkill for projects requiring only simple concurrent data structures

Code Comparison

Junction:

junction::ConcurrentMap_Linear<int, int> map;
map.assign(42, 100);
int value = map.get(42);

oneTBB:

tbb::concurrent_hash_map<int, int> map;
{
    tbb::concurrent_hash_map<int, int>::accessor accessor;
    map.insert(accessor, 42);
    accessor->second = 100;
}
int value = map.find(42)->second;

Key Differences

Junction focuses specifically on concurrent data structures, while oneTBB offers a broader range of parallel programming tools
Junction's API is generally simpler and more straightforward for basic concurrent operations
oneTBB provides more advanced features and optimizations for complex parallel scenarios

Use Cases

Junction: Ideal for projects requiring efficient, lock-free concurrent data structures with a simple API
oneTBB: Better suited for large-scale parallel applications that can benefit from its comprehensive set of parallel programming tools and optimizations

libcds

2,546

A C++ library of Concurrent Data Structures

Pros of libcds

More comprehensive collection of concurrent data structures
Better documentation and examples
Active development and maintenance

Cons of libcds

Steeper learning curve due to more complex API
Potentially higher memory overhead for some data structures

Code Comparison

libcds:

#include <cds/container/michael_list_hp.h>

cds::container::MichaelList<cds::gc::HP, int> list;
list.push_front(42);
list.push_back(10);

junction:

#include <junction/ConcurrentMap_Linear.h>

junction::ConcurrentMap_Linear<int, int> map;
map.assign(42, 10);
int value = map.get(42);

Summary

libcds offers a wider range of concurrent data structures and better documentation, making it suitable for more complex concurrent programming scenarios. However, it may have a steeper learning curve and potentially higher memory usage for some structures. Junction, on the other hand, provides a simpler API focused on concurrent hash maps, which may be easier to use for specific use cases but less versatile overall. Both libraries aim to provide efficient, lock-free data structures for concurrent programming in C++.

Convert designs to code with AI

Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.

Try Visual Copilot

README

Junction is a library of concurrent data structures in C++. It contains several hash map implementations:

junction::ConcurrentMap_Crude
junction::ConcurrentMap_Linear
junction::ConcurrentMap_Leapfrog
junction::ConcurrentMap_Grampa

CMake and Turf are required. See the blog post New Concurrent Hash Maps for C++ for more information.

License

Junction uses the Simplified BSD License. You can use the source code freely in any project, including commercial applications, as long as you give credit by publishing the contents of the LICENSE file in your documentation somewhere.

Getting Started

If you just want to get the code and look around, start by cloning Junction and Turf into adjacent folders, then run CMake on Junction's CMakeLists.txt. You'll want to pass different arguments to cmake depending on your platform and IDE.

$ git clone https://github.com/preshing/junction.git
$ git clone https://github.com/preshing/turf.git
$ cd junction
$ mkdir build
$ cd build
$ cmake <additional options> ..

On Unix-like environments, cmake will generate a Makefile by default. On Windows, it will create a Visual Studio solution. To use a specific version of Visual Studio:

$ cmake -G "Visual Studio 14 2015" ..

To generate an Xcode project on OS X:

$ cmake -G "Xcode" ..

To generate an Xcode project for iOS:

$ cmake -G "Xcode" -DCMAKE_TOOLCHAIN_FILE=../../turf/cmake/toolchains/iOS.cmake ..

The generated build system will contain separate targets for Junction, Turf, and some sample applications.

Solution Explorer

Alternatively, you can run CMake on a specific sample only:

$ cd junction/samples/MapCorrectnessTests
$ mkdir build
$ cd build
$ cmake <additional options> ..

Adding Junction to Your Project

There are several ways to add Junction to your own C++ project.

Add Junction as a build target in an existing CMake-based project.
Use CMake to build Junction and Turf, then link the static libraries into your own project.
Grab only the source files you need from Junction, copy them to your project and hack them until they build correctly.

Some developers will prefer approach #3, but I encourage you to try approach #1 or #2 instead. It will be easier to grab future updates that way. There are plenty of files in Junction (and Turf) that you don't really need, but it won't hurt to keep them on your hard drive either. And if you link Junction statically, the linker will exclude the parts that aren't used.

Adding to an Existing CMake Project

If your project is already based on CMake, clone the Junction and Turf source trees somewhere, then call add_subdirectory on Junction's root folder from your own CMake script. This will add both Junction and Turf targets to your build system.

For a simple example, see the junction-sample repository.

Building the Libraries Separately

Generate Junction's build system using the steps described in the Getting Started section, then use it to build the libraries you need. Add these to your own build system. Make sure to generate static libraries to avoid linking parts of the library that aren't needed.

If you build the install target provided by Junction's CMake script, the build system will output a clean folder containing only the headers and libs that you need. You can add this to your own project using a single include path. Choose the output directory by specifying the CMAKE_INSTALL_PREFIX variable to CMake. Additionally, you can specify JUNCTION_WITH_SAMPLES=OFF to avoid building the samples. For example:

$ cmake -DCMAKE_INSTALL_PREFIX=~/junction-install -DJUNCTION_WITH_SAMPLES=OFF ..
$ cmake --build . --target install --config RelWithDebInfo

Notes:

Instead of running the second cmake command, which runs the build system, you could run your build system directly. For example, make install on Unix, or build the INSTALL project in Visual Studio.
If using makefiles, you'll probably want to pass the additional option -DCMAKE_BUILD_TYPE=RelWithDebInfo to the first cmake command.

This will create the following file structure:

Install folder

Configuration

When you first run CMake on Junction, Turf will detect the capabilities of your compiler and write the results to a file in the build tree named turf/include/turf_config.h. Similarly, Junction will write include/junction_config.h to the build tree. You can modify the contents of those files by setting variables when CMake runs. This can be done by passing additional options to cmake, or by using an interactive GUI such as cmake-gui or ccmake.

For example, to configure Turf to use the C++11 standard library, you can set the TURF_PREFER_CPP11 variable on the command line:

$ cmake -DTURF_PREFER_CPP11=1 ..

Or, using the CMake GUI:

CMake GUI

Many header files in Turf, and some in Junction, are configurable using preprocessor definitions. For example, turf/Thread.h will switch between turf::Thread implementations depending on the values of TURF_IMPL_THREAD_PATH and TURF_IMPL_THREAD_TYPE. If those macros are not defined, they will be set to default values based on information from the environment. You can set them directly by providing your own header file and passing it in the TURF_USERCONFIG variable when CMake runs. You can place this file anywhere; CMake will copy it to Turf's build tree right next to include/turf_config.h.

$ cmake -DTURF_USERCONFIG=path/to/custom/turf_userconfig.h.in ..

The JUNCTION_USERCONFIG variable works in a similar way. As an example, take a look at the Python script junction/samples/MapScalabilityTests/TestAllMaps.py. This script invokes cmake several times, passing a different junction_userconfig.h.in file each time. That's how it builds the same test application using different map implementations.

Rules and Behavior

Currently, Junction maps only work with keys and values that are pointers or pointer-sized integers. The hash function must be invertible, so that every key has a unique hash. Out of all possible keys, a null key must be reserved, and out of all possible values, null and redirect values must be reserved. The defaults are 0 and 1. You can override those defaults by passing custom KeyTraits and ValueTraits parameters to the template.

Every thread that manipulates a Junction map must periodically call junction::DefaultQSBR.update, as mentioned in the blog post. If not, the application will leak memory.

Otherwise, a Junction map is a lot like a big array of std::atomic<> variables, where the key is an index into the array. More precisely:

All of a Junction map's member functions, together with its Mutator member functions, are atomic with respect to each other, so you can safely call them from any thread without mutual exclusion.
If an assign happens before a get with the same key, the get will return the value it inserted, except if another operation changes the value in between. Any synchronizing operation will establish this relationship.
For Linear, Leapfrog and Grampa maps, assign is a release operation and get is a consume operation, so you can safely pass non-atomic information between threads using a pointer. For Crude maps, all operations are relaxed.
In the current version, you must not assign while concurrently using an Iterator.

Feedback

If you have any feedback on improving these steps, feel free to open an issue on GitHub, or send a direct message using the contact form on my blog.

Top Related Projects

Convert designs to code with AI

Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.

Try Visual Copilot