Concurrent data structures in C++

Overview

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.

  1. Add Junction as a build target in an existing CMake-based project.
  2. Use CMake to build Junction and Turf, then link the static libraries into your own project.
  3. 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.

Issues
  • Freeing dynamically allocated values

    Freeing dynamically allocated values

    How do you free dynamically allocated values when, for example, SingleMap_Linear is destroyed. I see that the cell's destructors are run, but that doesn't free the Value if the Value is a pointer. And without a way to iterate over entries, it seems there would just me a memory leak.

    opened by weshoke 8
  • Unexpected behavior on unit test with assign/erase/assign

    Unexpected behavior on unit test with assign/erase/assign

    Apologies if this turns out to be due to my own mishandling of the library.

    I've written a test in some of my own code to see what container I should use for a concurrent hash map. The test is as follow (adapted to junction):

    template <typename Pool>
    void bash_junction_map(Pool& pool, const char* name)
    {
    	using namespace ::testing;
    	using namespace stk;
    
    	junction::ConcurrentMap_Leapfrog<int, int> m;
    
    	auto nItems = 10000;
    	for (auto i = 2; i < nItems + 2; ++i)
    	{
    		m.assign(i, i * 10);
    	}
    
    	using future_t = typename Pool::template future<void>;
    	std::vector<future_t> fs;
    	fs.reserve(100000);
    	{
    		GEOMETRIX_MEASURE_SCOPE_TIME(name);
    		for (unsigned i = 2; i < 100000 + 2; ++i) {
    			fs.emplace_back(pool.send([&m, i]() -> void
    			{
    				for (int q = 0; q < nsubwork; ++q)
    				{
    					m.assign(i, i * 20);
    					m.erase(i);
    					m.assign(i, i * 20);
    				}
    			}));
    		}
    		boost::for_each(fs, [](const future_t& f) { f.wait(); });
    	}
    
    	for (auto i = 2; i < 100000 + 2; ++i)
    	{
    		auto r = m.find(i);
    		EXPECT_EQ(i * 20, r.getValue());
    	}
    }
    

    My understanding is that an assign operation followed by an erase and then another assign ought to essentially cancel each other out. However, I'm getting spurious failures with junction:

    Note: Google Test filter = timing.work_stealing_thread_pool_moodycamel_concurrentQ_bash_junction
    [==========] Running 1 test from 1 test case.
    [----------] Global test environment set-up.
    [----------] 1 test from timing
    [ RUN      ] timing.work_stealing_thread_pool_moodycamel_concurrentQ_bash_junction
    G:\Projects\simulation_suite\test\fiber_timing_tests.cpp(150): error: Expected equality of these values:
      i * 20
        Which is: 1032520
      r.getValue()
        Which is: 0
    G:\Projects\simulation_suite\test\fiber_timing_tests.cpp(150): error: Expected equality of these values:
      i * 20
        Which is: 540200
      r.getValue()
        Which is: 0
    G:\Projects\simulation_suite\test\fiber_timing_tests.cpp(150): error: Expected equality of these values:
      i * 20
        Which is: 1032520
      r.getValue()
        Which is: 0
    [  FAILED  ] timing.work_stealing_thread_pool_moodycamel_concurrentQ_bash_junction (35310 ms)
    [----------] 1 test from timing (35311 ms total)
    
    [----------] Global test environment tear-down
    [==========] 1 test from 1 test case ran. (35313 ms total)
    [  PASSED  ] 0 tests.
    [  FAILED  ] 1 test, listed below:
    [  FAILED  ] timing.work_stealing_thread_pool_moodycamel_concurrentQ_bash_junction
    
     1 FAILED TEST
    Press any key to continue . . .
    

    Are my expectations incorrect?

    opened by brandon-kohn 4
  • Multithreaded Migration and the implicit lock ?

    Multithreaded Migration and the implicit lock ?

    I am asking this based on the article http://preshing.com/20160222/a-resizable-concurrent-map/ not based on the code. If you coordinate multithreaded migration with a lock, the whole thing can't be fully concurrent anymore (by definition ?).

    Also you write: "In the current version of Linear, even get calls don’t read from the new table until the migration is complete." That sounds like a (b)lock to me, if your get API does not want to return the redirect marker.

    My current belief is, that you have to do things optimistically otherwise, you lose being concurrent.

    opened by mulle-nat 4
  • Help reproducing benchmark values

    Help reproducing benchmark values

    I came across this post and I'm trying to run the benchmarks on my machine (2x16-core xeon e5 2620v4 @2.1Ghz). I expect to get worse performance at lower core-counts due to the lower clock speed, but I currently get substantially (>2x) worse performance than the post running MapScalabilityTest (where I believe time is reported in seconds):

    {
    'mapType': 'Junction Grampa map',
    'population': 32000,
    'readsPerWrite': 4,
    'itersPerChunk': 10000,
    'chunks': 200,
    'keepChunkFraction': 1.000000,
    'labels': ('numThreads', 'mapOpsDone', 'totalTime'),
    'points': [
        (1, 20000000, 3.130913),
        (2, 39271012, 6.792609),
        (3, 60127378, 10.934400),
        (4, 80936978, 15.173613),
        (5, 102136528, 20.520561),
        (6, 122053852, 25.645662),
        (7, 142280994, 30.308151),
        (8, 162408667, 35.968076),
        (9, 183720392, 44.163389),
        (10, 203532431, 52.606002),
        (11, 223287034, 60.265506),
        (12, 241929131, 68.742479),
        (13, 260322337, 75.837455),
        (14, 278162335, 82.871782),
        (15, 297701998, 88.851133),
        (16, 316862143, 96.579740),
    ],
    }
    

    Are there any tests I can perform to ensure that I'm building this correctly (e.g. that optimizations are turned on)?

    opened by ezrosent 4
  • Crash in first table migration (QSBR.enqueue)

    Crash in first table migration (QSBR.enqueue)

    gcc 4.8.2 c++11 (g++ (GCC) 4.8.2 20140120 (Red Hat 4.8.2-15))

    I declare a Leapfrog map and begin inserting into the map. After a few successful inserts, a migration is attempted and the program is faulting.

    The call stack is below. If I break prior to the crash, say in the call to enqueue, the m_deferredActions._M_impl seems to have been corrupted, with _M_start = 0x1,_M_finish = 0x0, _M_end_of_storage = 0x0. My gut is telling me that the swap calls in QSBR.update(), but i haven't caught it with a watch point. Watch indicates the _M_start member alternating between 0x1 and 0x0.

    It is possible that I have missed some step in getting the QSBR set up? I created a single context and call update() from the thread that is adding to the table when it is quiet. Currently I haven't enabled consumers of the data.

    Callstack below:

    
    [Switching to Thread 0x7ffff63d3700 (LWP 13122)]
    
    0x0000000000716fef in __gnu_cxx::new_allocator<junction::QSBR::Action>::construct<junction::QSBR::Action<junction::QSBR::Action> > (
    
        this=0xb95578 <junction::DefaultQSBR+88>, __p=0xfffffffffffffff8)
    
        at /opt/rh/devtoolset-2/root/usr/include/c++/4.8.2/ext/new_allocator.h:120
    
    120 in /opt/rh/devtoolset-2/root/usr/include/c++/4.8.2/ext/new_allocator.h
    
    (gdb) bt
    
    #0  0x0000000000716fef in __gnu_cxx::new_allocator<junction::QSBR::Action>::construct<junction::QSBR::Action<junction::QSBR::Action> > (
    
        this=0xb95578 <junction::DefaultQSBR+88>, __p=0xfffffffffffffff8)
    
        at /opt/rh/devtoolset-2/root/usr/include/c++/4.8.2/ext/new_allocator.h:120
    
    #1  0x0000000000716e03 in std::allocator_traits<std::allocator<junction::QSBR::Action> >::_S_construct<junction::QSBR::Action<junction::QSBR::Action> >(std::allocator<junction::QSBR::Action>&, std::allocator_traits<std::allocator<junction::QSBR::Action> >::__construct_helper*, (junction::QSBR::Action<junction::QSBR::Action>&&)...) (__a=..., __p=0xfffffffffffffff8)
    
        at /opt/rh/devtoolset-2/root/usr/include/c++/4.8.2/bits/alloc_traits.h:254
    
    #2  0x0000000000716b77 in std::allocator_traits<std::allocator<junction::QSBR::Action> >::construct<junction::QSBR::Action<junction::QSBR::Action> >(std::allocator<junction::QSBR::Action>&, junction::QSBR::Action<junction::QSBR::Action>*, (junction::QSBR::Action<junction::QSBR::Action>&&)...) (__a=..., 
    
        __p=0xfffffffffffffff8)
    
        at /opt/rh/devtoolset-2/root/usr/include/c++/4.8.2/bits/alloc_traits.h:393
    
    #3  0x0000000000716c0f in std::vector<junction::QSBR::Action, std::allocator<junction::QSBR::Action> >::_M_emplace_back_aux<junction::QSBR::Action>(junction::QSBR::Action&&) (this=0xb95578 <junction::DefaultQSBR+88>)
    
        at /opt/rh/devtoolset-2/root/usr/include/c++/4.8.2/bits/vector.tcc:408
    
    #4  0x0000000000716add in std::vector<junction::QSBR::Action, std::allocator<junction::QSBR::Action> >::emplace_back<junction::QSBR::Action>(junction::QSBR::Action&&) (this=0xb95578 <junction::DefaultQSBR+88>)
    
        at /opt/rh/devtoolset-2/root/usr/include/c++/4.8.2/bits/vector.tcc:101
    
    #5  0x0000000000716996 in std::vector<junction::QSBR::Action, std::allocator<junction::QSBR::Action> >::push_back(junction::QSBR::Action&&) (
    
        this=0xb95578 <junction::DefaultQSBR+88>, 
    
        __x=<unknown type in /home/matt.weiss/poc/engine_debug, CU 0x3a0c7d, DIE 0x3f3621>)
    
        at /opt/rh/devtoolset-2/root/usr/include/c++/4.8.2/bits/stl_vector.h:920
    
    #6  0x0000000000716799 in junction::QSBR::enqueue<junction::details::Leapfrog<junction::ConcurrentMap_Leapfrog<unsigned long, engine::Vehicle*, junction::DefaultKeyTraits<unsigned long>, junction::DefaultValueTraits<engine::Vehicle*> > >::TableMigration> (this=0xb95520 <junction::DefaultQSBR>, 
    
        pmf=(void (junction::details::Leapfrog<junction::ConcurrentMap_Leapfrog<unsigned long, engine::Vehicle*, junction::DefaultKeyTraits<unsigned long>, junction::DefaultValueTraits<engine::Vehicle*> > >::TableMigration::*)(junction::details::Leapfrog<junction::ConcurrentMap_Leapfrog<unsigned long, engine::Vehicle*, junction::DefaultKeyTraits<unsigned long>, junction::DefaultValueTraits<engine::Vehicle*> > >::TableMigration * const)) 0x7165f6 <junction::details::Leapfrog<junction::ConcurrentMap_Leapfrog<unsigned long, engine::Vehicle*, junction::DefaultKeyTraits<unsigned long>, junction::DefaultValueTraits<engine::Vehicle*> > >::TableMigration::destroy()>, target=0x7fffe0003160)
    
        at /home/mweiss/src/simplified_simplification/build/engine/Debug/../../Debug/include/junction/QSBR.h:80
    
    #7  0x0000000000715e16 in junction::details::Leapfrog<junction::ConcurrentMap_Leapfrog<unsigned long, engine::Vehicle*, junction::DefaultKeyTraits<unsigned long>, junction::DefaultValueTraits<engine::Vehicle*> > >::TableMigration::run (
    
        this=0x7fffe0003160)
    
        at /home/mweiss/src/simplified_simplification/build/engine/Debug/../../Debug/include/junction/details/Leapfrog.h:568
    
    #8  0x000000000070c705 in junction::SimpleJobCoordinator::participate (
    
        this=0xb99410)
    
        at /home/mweiss/src/simplified_simplification/build/engine/Debug/../../Debug/include/junction/SimpleJobCoordinator.h:69
    
    #9  0x00000000007108d7 in junction::ConcurrentMap_Leapfrog<unsigned long, engine::Vehicle*, junction::DefaultKeyTraits<unsigned long>, junction::DefaultValueTraits<engine::Vehicle*> >::Mutator::Mutator (this=0x7ffff63d2b20, map=..., 
    
        key=3314346713558739690)
    
        at /home/mweiss/src/simplified_simplification/build/engine/Debug/../../Debug/include/junction/ConcurrentMap_Leapfrog.h:128
    
    #10 0x000000000070e8c1 in junction::ConcurrentMap_Leapfrog<unsigned long, engine::Vehicle*, junction::DefaultKeyTraits<unsigned long>, junction::DefaultValueTra---Type <return> to continue, or q <return> to quit---
    
    its<engine::Vehicle*> >::insertOrFind (this=0xb993b8, key=3314346713558739690)
    
        at /home/mweiss/src/simplified_simplification/build/engine/Debug/../../Debug/include/junction/ConcurrentMap_Leapfrog.h:250
    
    #11 0x000000000070d557 in engine::Cache::impl::addToLookups (this=0xb99380, 
    
        veh=0x7fffe00039e0)
    
        at /home/mweiss/src/simplified_simplification/engine/src/Cache.cpp:174```
    
    
    opened by mdw55189 3
  • Limitations

    Limitations

    1. "Hash function must be invertible, so that every key has a unique hash". This seems like a severe limitation. std::map deals with collisions without issues. Why not use a thread-safe queue to remove the limitation ?

    2. How about TTL, LRU and LFU ?

    opened by squader 3
  • Deadlock when using Iterator

    Deadlock when using Iterator

    I found out that this example deadlocks in insert():

    uint32_t random(uint32_t min, uint32_t max) {
        return min + (((double) rand() / (double(RAND_MAX) + 1)) * (max - min));
    }
    int main() {
        struct Data {
            Data(uint64_t id) : Id(id) { }
            uint64_t Id;
        };
    
        junction::ConcurrentMap_Leapfrog<uint64_t, Data *> map;
        std::mutex mut;
    
        std::vector<std::thread> threads;
        for (int i = 0; i < 16; ++i) {
            threads.push_back(std::thread([&] {
                auto qsbrCtx = junction::DefaultQSBR.createContext();
                while (true) {
                    auto type = random(0, 5);
                    switch (type) {
                        case 0: {
                            auto item = new Data(random(0, 1000));
                            std::lock_guard<std::mutex> lock(mut);
                            map.assign(item->Id, item);
                        } break;
                        case 1: {
                            if (auto *item = map.get(random(0, 1000))) {
                                // std::lock_guard<std::mutex> lock(mut);
                                map.erase(item->Id);
                            }
                        } break;
                        case 2: {
                            std::lock_guard<std::mutex> lock(mut);
                            junction::ConcurrentMap_Leapfrog<uint64_t, Data *>::Iterator it(map);
                            while (it.isValid()) {
                                if (it.getValue()->Id < 2) putchar('a');
                                it.next();
                            }
                        } break;
                        default: {
                            if (random(0, 10000) < 2)
                                printf("Thread %lx is running\n", std::hash<std::thread::id>()(std::this_thread::get_id()));  
                        } break;
                    }
                    junction::DefaultQSBR.update(qsbrCtx);
                }
            }));
        }
        threads.push_back(std::thread([&] {
            auto qsbrCtx = junction::DefaultQSBR.createContext();
            auto j = 0u;
            while (j++ < 10000000u) {
                if (auto *item = map.get(random(0, 1000))) {
                    if (item->Id > 998) {
                        putchar('b');
                    }
                }
                junction::DefaultQSBR.update(qsbrCtx);
            }
        }));
        for (auto &t : threads) {
            t.join();
        }
    
        return 0;
    }
    

    After running this deadlocks in junction/details/Leapfrog.h:235:

    do {
        probeHash = cell->hash.load(turf::Acquire);
    } while (probeHash == KeyTraits::NullHash);
    

    If I remove case 2: from the example, there is no deadlock, so it appears that the iterator is causing some race condition. I used mutex on insert and iterator since comment for Iterator says

    // The easiest way to implement an Iterator is to prevent all Redirects. // The currrent Iterator does that by forbidding concurrent inserts.

    In my case I insert and erase values very frequently from different threads, but occasionally I need to be able to iterate through all items (and inserts and erases may happen and that time too, hence the mutex).

    Could you investigate and see if this is a bug in Junction or my mistake?

    I'm attaching my complete example with makefile: junction-deadlock.zip

    opened by AdrianEddy 3
  • insertOrFind unexpected behavior

    insertOrFind unexpected behavior

    Hi,

    First of all, thank you for the great library and blog, they are great material ! I'm currently using ConcurrentMap_Leapfrog and got excellent performances and results. But, when I integrated with one of my libraries, my tests started to fail spuriously. I started looking at the issue, and after a look of debugging, I was surprised by the behavior of insertOrFind. I expect insertOrFind to work as follow:

    mut = insertOrFind(k)
    assert(mut.getValue() == ValueTraits<>::NullValue)
    mut = insertOrFind(k)
    assert(mut.getValue() == ValueTraits<>::Redirect)
    

    But, I encounter sometimes, that on the second getValue I get a NullValue instead of Redirect.

    I made the following concrete :

    #include <mutex>
    #include <thread>
    #include <vector>
    #include <atomic>
    #include <cassert>
    #include <junction/ConcurrentMap_Leapfrog.h>
    
    using Key = size_t;
    using Value = int64_t;
    
    template <typename T>
    struct ValueTraits {
        using IntType = T;
        using Value = T;
    
        static constexpr IntType NullValue = 0;
        static constexpr IntType Redirect = static_cast<T>(-1); // I want -1, not 1 by default for redirect value
    };
    
    using hash_map = junction::ConcurrentMap_Leapfrog<Key, Value, junction::DefaultKeyTraits<Key>,
          ValueTraits<Value>>;
    using vec_t = std::vector<std::atomic<size_t>>;
    
    void insert(hash_map& m, vec_t& vec, size_t len) {
        for (size_t i = 0; i < len ; ++i) {
            auto mutator = m.insertOrFind(i + 1);
            auto to_insert = mutator.getValue() == ValueTraits<Value>::NullValue;
    
            if (to_insert)
            {
                mutator.exchangeValue(i + 1);
                ++vec[i];
            }
            assert(vec[i]!=2); // can assert here
        }
    }
    
    int main()
    {
        constexpr size_t map_size = 2048;
        hash_map m(map_size<<1);
        vec_t vec(map_size);
    
        for (auto& v : vec)
            v = 0;
    
        auto t1 = std::thread(insert, std::ref(m), std::ref(vec), map_size);
        auto t2 = std::thread(insert, std::ref(m), std::ref(vec), map_size);
    
        t1.join();
        t2.join();
    
        return 0;
    }
    

    The example does not use directly the value of Redirect but I should normally only insert one time in the map (It reproduce the behavior of my use case). When you run this example, sometimes in does thrown an assert, sometimes it fails in the assert.

    Do I make a wrong assumption somewhere or did I implement something wrong?

    Thank you for any help you can provide me with. I tried with Grampa too, same behavior.

    Best, Julián

    opened by MonkeyBreaker 3
  • can't compile with g++ 4.4.7

    can't compile with g++ 4.4.7

    in turf/cmake/Macros.cmake, you set(CMAKE_CXX_FLAGS "-g -std=c++11...) this doesn't make sense. because this lib suppose to work without c++11

    opened by spetrel 3
  • Consider prividing insert_or_assign method as in C++17 std lib.

    Consider prividing insert_or_assign method as in C++17 std lib.

    In C++17, there will be an insert_or_assign method in associative containers. Consider renaming set to inset_or_assign or providing an alias for consistency with std library.

    opened by ilyapopov 2
  • How to use a non-number type as a key for maps (for example std::bitset)

    How to use a non-number type as a key for maps (for example std::bitset)

    I'm certain that this is a feature unsupported by junction, but just in case, I'll provide some system details.

    OS: Ubuntu 20.04.2 LTS
    Build system: CMake (used through CLion IDE). Not sure which CMake version it uses under the hood though.
    

    I'm trying to create something like a transposition table for a chess engine. So the following code compiles:

    #include <junction/ConcurrentMap_Leapfrog.h>
    
    struct Foo {};
    
    int main() {
        typedef junction::ConcurrentMap_Leapfrog<unsigned long long, Foo*> ConcurrentMap;
        ConcurrentMap map;
        return 0;
    }
    

    However, in my case, I'm unable to use unsigned long long as the position hash, because it can't hold enough values. So I use std::bitset. But there is a problem, the following won't compile:

    #include <bitset>
    #include <junction/ConcurrentMap_Leapfrog.h>
    
    struct Foo {};
    
    int main() {
        typedef junction::ConcurrentMap_Leapfrog<std::bitset<100>, Foo*> ConcurrentMap;
        ConcurrentMap map;
        return 0;
    }
    

    The error is the following:

    In file included from /path/to/project/main.cpp:2:
    /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h: In instantiation of ‘class junction::ConcurrentMap_Leapfrog<std::bitset<100>, Foo*>’:
    /path/to/project/main.cpp:8:19:   required from here
    /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:33:57: error: invalid use of incomplete type ‘struct turf::util::BestFit<std::bitset<100> >’
       33 |     typedef typename turf::util::BestFit<Key>::Unsigned Hash;
          |                                                         ^~~~
    In file included from /path/to/project/junction/junction/details/Leapfrog.h:20,
                     from /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:17,
                     from /path/to/project/main.cpp:2:
    /path/to/project/turf/turf/Util.h:22:8: note: declaration of ‘struct turf::util::BestFit<std::bitset<100> >’
       22 | struct BestFit;
          |        ^~~~~~~
    In file included from /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:17,
                     from /path/to/project/main.cpp:2:
    /path/to/project/junction/junction/details/Leapfrog.h: In instantiation of ‘static junction::details::Leapfrog<Map>::Table* junction::details::Leapfrog<Map>::Table::create(turf::intTypes::ureg) [with Map = junction::ConcurrentMap_Leapfrog<std::bitset<100>, Foo*>; turf::intTypes::ureg = long long unsigned int]’:
    /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:40:97:   required from ‘junction::ConcurrentMap_Leapfrog<K, V, KT, VT>::ConcurrentMap_Leapfrog(turf::intTypes::ureg) [with K = std::bitset<100>; V = Foo*; KT = junction::DefaultKeyTraits<std::bitset<100> >; VT = junction::DefaultValueTraits<Foo*>; turf::intTypes::ureg = long long unsigned int]’
    /path/to/project/main.cpp:8:19:   required from here
    /path/to/project/junction/junction/details/Leapfrog.h:81:37: error: ‘struct junction::details::Leapfrog<junction::ConcurrentMap_Leapfrog<std::bitset<100>, Foo*> >::Cell’ has no member named ‘hash’
       81 |                     group->cells[j].hash.storeNonatomic(KeyTraits::NullHash);
          |                     ~~~~~~~~~~~~~~~~^~~~
    In file included from /path/to/project/junction/junction/details/Leapfrog.h:21,
                     from /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:17,
                     from /path/to/project/main.cpp:2:
    /path/to/project/junction/junction/MapTraits.h: In instantiation of ‘struct junction::DefaultKeyTraits<std::bitset<100> >’:
    /path/to/project/junction/junction/details/Leapfrog.h:81:21:   required from ‘static junction::details::Leapfrog<Map>::Table* junction::details::Leapfrog<Map>::Table::create(turf::intTypes::ureg) [with Map = junction::ConcurrentMap_Leapfrog<std::bitset<100>, Foo*>; turf::intTypes::ureg = long long unsigned int]’
    /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:40:97:   required from ‘junction::ConcurrentMap_Leapfrog<K, V, KT, VT>::ConcurrentMap_Leapfrog(turf::intTypes::ureg) [with K = std::bitset<100>; V = Foo*; KT = junction::DefaultKeyTraits<std::bitset<100> >; VT = junction::DefaultValueTraits<Foo*>; turf::intTypes::ureg = long long unsigned int]’
    /path/to/project/main.cpp:8:19:   required from here
    /path/to/project/junction/junction/MapTraits.h:24:55: error: invalid use of incomplete type ‘struct turf::util::BestFit<std::bitset<100> >’
       24 |     typedef typename turf::util::BestFit<T>::Unsigned Hash;
          |                                                       ^~~~
    In file included from /path/to/project/junction/junction/details/Leapfrog.h:20,
                     from /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:17,
                     from /path/to/project/main.cpp:2:
    /path/to/project/turf/turf/Util.h:22:8: note: declaration of ‘struct turf::util::BestFit<std::bitset<100> >’
       22 | struct BestFit;
          |        ^~~~~~~
    In file included from /path/to/project/junction/junction/details/Leapfrog.h:21,
                     from /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:17,
                     from /path/to/project/main.cpp:2:
    /path/to/project/junction/junction/MapTraits.h:25:22: error: ‘constexpr’ needed for in-class initialization of static data member ‘const Key junction::DefaultKeyTraits<std::bitset<100> >::NullKey’ of non-integral type [-fpermissive]
       25 |     static const Key NullKey = Key(0);
          |                      ^~~~~~~
    In file included from /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:17,
                     from /path/to/project/main.cpp:2:
    /path/to/project/junction/junction/details/Leapfrog.h: In instantiation of ‘static junction::details::Leapfrog<Map>::Table* junction::details::Leapfrog<Map>::Table::create(turf::intTypes::ureg) [with Map = junction::ConcurrentMap_Leapfrog<std::bitset<100>, Foo*>; turf::intTypes::ureg = long long unsigned int]’:
    /path/to/project/junction/junction/ConcurrentMap_Leapfrog.h:40:97:   required from ‘junction::ConcurrentMap_Leapfrog<K, V, KT, VT>::ConcurrentMap_Leapfrog(turf::intTypes::ureg) [with K = std::bitset<100>; V = Foo*; KT = junction::DefaultKeyTraits<std::bitset<100> >; VT = junction::DefaultValueTraits<Foo*>; turf::intTypes::ureg = long long unsigned int]’
    /path/to/project/main.cpp:8:19:   required from here
    /path/to/project/junction/junction/details/Leapfrog.h:81:21: error: ‘NullHash’ is not a member of ‘junction::details::Leapfrog<junction::ConcurrentMap_Leapfrog<std::bitset<100>, Foo*> >::KeyTraits’ {aka ‘junction::DefaultKeyTraits<std::bitset<100> >’}
       81 |                     group->cells[j].hash.storeNonatomic(KeyTraits::NullHash);
          |                     ^~~~~
    make[3]: *** [CMakeFiles/test.dir/build.make:82: CMakeFiles/test.dir/main.cpp.o] Error 1
    make[2]: *** [CMakeFiles/Makefile2:136: CMakeFiles/test.dir/all] Error 2
    make[1]: *** [CMakeFiles/Makefile2:143: CMakeFiles/test.dir/rule] Error 2
    make: *** [Makefile:137: test] Error 2
    

    To my understanding, the error is caused by turf being unable to hash std::bitset. Also, C++11 supports hashing std::bitset and a few other types by default so maybe using std::hash in junction implementation could help. I could submit a PR, if you gave me a bit of guidance.

    opened by Jaimies 0
  • how can i access all items in ConcurrentLeapfrogMap(or others) in parallel?

    how can i access all items in ConcurrentLeapfrogMap(or others) in parallel?

    I notice that the iterator in junction is not concurrent !do they have other method to access all items in a concurrent_hash_map? And if have! I will appreciate if you can give me the tips! If Not, can you give me some suggestions on it?

    opened by Edassap 0
  • Is it possible to get the smallest key in the map?

    Is it possible to get the smallest key in the map?

    Or in other words, is it possible to iterate entries in the order of keys?

    opened by chxdeng 0
  • Is there exist a fixed-size hash table's scenes ?

    Is there exist a fixed-size hash table's scenes ?

    I have already seen the source code, When erase it do not set the key to null and I guess it's in order to keep the chain. This cell will not be occupied by others, resulting in a larger hash table until it is rewritten. In our project, we assign a fixed-size hash table at initialization time and when running, it can not be changed. Is there a fixed-size hash table implement Or How to handle the deletion ?

    opened by lucky-wavespider 0
  • Correct use of Garbage collection

    Correct use of Garbage collection

    In the blog/docs it says

    To make QSBR work, each thread must periodically call junction::DefaultQSBR.update at a moment when that thread is quiescent – that is, not in the middle of an operation that uses the map. In a game engine, you could call it between iterations of the main loop.

    I am experimenting with the leapfrog map, and inserted a call to junction::DefaultQSBR.flush() (since there is no update()). However, when I add the flush call, my code throws exceptions due to empty states in some objects retrieved from the map. There is no single place in the code where I can guarantee that the map is not accessed since everything is completely asynchronous. When one thread is calling flush() another thread might decide to insert or remove something from the map.

    Is there a recommended way of dealing with this? (Also please clarify "each thread must periodically call" - do you mean that all threads must call it individually, or can any one single thread call it from time to time).

    opened by biddisco 2
  • bad_alloc in QSBR.h with Visual Studio

    bad_alloc in QSBR.h with Visual Studio

    Hi, I am facing a problem when using Leapfrog concurrent map. I have created Visual Studio project with cmake, linked libs to my project and added include folders. After that I did a small setup to test if everything works and it stared failing on bad_alloc, even when I used different versions of Visual Studio or switched to 32/64bit. With initial size of the map equal to 8, after adding 10th element to map it fails on bad_alloc at QSBR.h:80 (notice the m_deferredActions capacity at first screenshot) when push_back is executed. I have also attached whole project (2.5MB) with all the libraries prepared. Please help me in resolving this issue. Thanks!

    1. screenshot (QSBR.h) image

    2. screenshot (bad_alloc) image

    3. screenshot (main.cpp) image

    DummyProject.zip

    opened by asdf-qwert 0
  • Added the insert operation

    Added the insert operation

    This pull-request adds an insert operation (which simply fails when a mapping already exists). This operation simplifies the usage and avoids unnecessary locking on the user side and it specially helps when the value is dynamically allocated (as opposed to the solutions provided in http://preshing.com/20160201/new-concurrent-hash-maps-for-cpp).

    opened by mdashti 1
  • Conan package

    Conan package

    Hello, Do you know about Conan? Conan is modern dependency manager for C++. And will be great if your library will be available via package manager for other developers.

    Here you can find example, how you can create package for the library.

    If you have any questions, just ask :-)

    opened by zamazan4ik 0
  • Any reason to call a member function of the object in QSBR?

    Any reason to call a member function of the object in QSBR?

    https://github.com/preshing/junction/blob/5e0de1150b2aff1cf4a5b5c47a7cc9b06d50663c/junction/QSBR.h#L74

    Since QSBR accepts a member function of the object here it's not clear how we can use this for object destruction. We cannot pass it the destructor of the object since that is forbidden in C++. It would be nice if we could pass arbitrary function here which takes the pointer (i.e. map element's value) as a parameter like this:

    void enqueue(void (T::*func)(T*), T* target) {
           struct Closure {
                void (T::*func)(T*);
                T* target;
                static void thunk(void* param) {
                    Closure* self = (Closure*) param;
                    self->(*func)(target);
                }
            };
            Closure closure = {func, target};
            turf::LockGuard<turf::Mutex> guard(m_mutex);
            TURF_RACE_DETECT_GUARD(m_flushRaceDetector);
            m_deferredActions.push_back(Action(Closure::thunk, &closure, sizeof(closure)));
    }
    

    Then we could just call delete value in the callback function to free the object. For example:

    struct Foo {
      static void destroy(Foo *ptr) {
        delete ptr;
      }
    }
    
    auto value= map.erase(key);
    junction::DefaultQSBR.enqueue(&Foo::destroy, value);
    

    I was wondering if there is any reason to enforce a member function in enqueue().

    opened by abhinav04sharma 4
Owner
Jeff Preshing
Jeff Preshing
A C++ library of Concurrent Data Structures

CDS C++ library The Concurrent Data Structures (CDS) library is a collection of concurrent containers that don't require external (manual) synchroniza

Max Khizhinsky 2k Dec 3, 2021
A C++ library providing various concurrent data structures and reclamation schemes.

xenium xenium is a header-only library that provides a collection of concurrent data structures and memory reclamation algorithms. The data structures

Manuel Pöter 274 Dec 4, 2021
A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

moodycamel::ConcurrentQueue An industrial-strength lock-free queue for C++. Note: If all you need is a single-producer, single-consumer queue, I have

Cameron 6.2k Dec 3, 2021
:copyright: Concurrent Programming Library (Coroutine) for C11

libconcurrent tiny asymmetric-coroutine library. Description asymmetric-coroutine bidirectional communication by yield_value/resume_value native conte

sharow 344 Nov 22, 2021
A bounded multi-producer multi-consumer concurrent queue written in C++11

MPMCQueue.h A bounded multi-producer multi-consumer concurrent queue written in C++11. It's battle hardened and used daily in production: In the Frost

Erik Rigtorp 598 Dec 1, 2021
stdgpu: Efficient STL-like Data Structures on the GPU

stdgpu: Efficient STL-like Data Structures on the GPU Features | Examples | Documentation | Building | Integration | Contributing | License | Contact

Patrick Stotko 624 Nov 22, 2021
An optimized C library for math, parallel processing and data movement

PAL: The Parallel Architectures Library The Parallel Architectures Library (PAL) is a compact C library with optimized routines for math, synchronizat

Parallella 289 Dec 6, 2021
Concurrent data structures in C++

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

Jeff Preshing 1.2k Nov 30, 2021
A C++ library of Concurrent Data Structures

CDS C++ library The Concurrent Data Structures (CDS) library is a collection of concurrent containers that don't require external (manual) synchroniza

Max Khizhinsky 2k Dec 3, 2021
A C++ library providing various concurrent data structures and reclamation schemes.

xenium xenium is a header-only library that provides a collection of concurrent data structures and memory reclamation algorithms. The data structures

Manuel Pöter 274 Dec 4, 2021
The bit level data interchange format for serializing data structures.

bitproto Bitproto is a fast, lightweight and easy-to-use bit level data interchange format for serializing data structures. Website: https://bitproto.

Chao Wang 54 Nov 18, 2021
A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

moodycamel::ConcurrentQueue An industrial-strength lock-free queue for C++. Note: If all you need is a single-producer, single-consumer queue, I have

Cameron 6.2k Dec 3, 2021
:copyright: Concurrent Programming Library (Coroutine) for C11

libconcurrent tiny asymmetric-coroutine library. Description asymmetric-coroutine bidirectional communication by yield_value/resume_value native conte

sharow 344 Nov 22, 2021
A bounded multi-producer multi-consumer concurrent queue written in C++11

MPMCQueue.h A bounded multi-producer multi-consumer concurrent queue written in C++11. It's battle hardened and used daily in production: In the Frost

Erik Rigtorp 598 Dec 1, 2021
RemixDB: A read- and write-optimized concurrent KV store. Fast point and range queries. Extremely low write-amplification.

REMIX and RemixDB The REMIX data structure was introduced in paper "REMIX: Efficient Range Query for LSM-trees", FAST'21. This repository maintains a

Xingbo Wu 50 Nov 18, 2021
Async & Concurrent Servers implemented in C

Concurrent servers in c Imlementation of concurrent severs in c from scratch using this awesome blog as a tutorial. Project Structure . ├── readme.md

Rupanshu Yadav 7 Jun 21, 2021
A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

moodycamel::ConcurrentQueue An industrial-strength lock-free queue for C++. Note: If all you need is a single-producer, single-consumer queue, I have

Cameron 6.2k Nov 29, 2021
A bounded multi-producer multi-consumer concurrent queue written in C++11

MPMCQueue.h A bounded multi-producer multi-consumer concurrent queue written in C++11. It's battle hardened and used daily in production: In the Frost

Erik Rigtorp 598 Dec 6, 2021
asyncio is a c++20 library to write concurrent code using the async/await syntax.(developing in progress)

asyncio Asyncio is a C++20 coroutine library to write concurrent code using the await syntax, and imitate python asyncio library. Hello world Task<> h

Netcan 17 Nov 28, 2021
stdgpu: Efficient STL-like Data Structures on the GPU

stdgpu: Efficient STL-like Data Structures on the GPU Features | Examples | Documentation | Building | Integration | Contributing | License | Contact

Patrick Stotko 624 Nov 22, 2021
Template Library of Tree Data Structures in C++17

Template Library of Tree Data Structures in C++17 Implementations AVL Tree Binary Search Tree BTree KD-Tree Splay Tree Trie Notes This project is for

George Fotopoulos 149 Feb 8, 2021
Easy to use, header only, macro generated, generic and type-safe Data Structures in C

C Macro Collections Easy to use, header only, macro generated, generic and type-safe Data Structures in C. Table of Contents Installation Contributing

Leonardo Vencovsky 258 Dec 1, 2021
A library of generic data structures.

Collections-C A library of generic data structures including a list, array, hashtable, deque etc.. Examples Building and Installing Using the library

Srđan Panić 2.3k Nov 24, 2021
🔗 Common Data Structures and Algorithms

?? Data Structures and Algorithms This library provides common data structures. It will also provide some data structures which needed in render or ga

Recep Aslantas 39 Oct 31, 2021
A collecton of generic reference counted data structures, tools to create compatible C style classes, and demo applications

The Offbrand library is a collection of reference counted generic data structures written in C for C. The library includes bash scripts to assist in t

Tyler Heck 81 Jul 22, 2021
Easy to use, header only, macro generated, generic and type-safe Data Structures in C

C Macro Collections Easy to use, header only, macro generated, generic and type-safe Data Structures in C. Table of Contents Installation Contributing

Leonardo Vencovsky 258 Dec 1, 2021
Repository of problems and solutions of labsheets used for Data Structures and Algorithms (CS F211) in Semester 2, 2020-21 at BITS Pilani - Hyderabad Campus.

CS F211 Data Structures and Algorithms (BITS Pilani - Hyderabad Campus) This repository contains the problems, solution approaches & explanations and

Rohit Dwivedula 22 Aug 29, 2021
An assortment of commonly used algorithms and data structures implemented with C++.

Algorithms-And-Data-Structures This repo contains C++ implementations of common algorithms and data structures, grouped by topics. The list will be sp

Tony Sheng 23 Nov 9, 2021