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
  • 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
  • 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
  • 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
  • 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
  • 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
  • Linker Errors: undefined reference to std::__cxx11::basic_string<>...

    Linker Errors: undefined reference to std::__cxx11::basic_string<>...

    I statically-linked Junction and Turf into a shared library and am getting the following linker errors when linking my shared library into another executable. Generally these errors are due to compiling the library with an older GLIBCXX version than the final app, but I'm building everything with g++ 7.3.0

    ../lib/libreference_data_driver.so: undefined reference to `std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::c_str() const'
    ../lib/libreference_data_driver.so: undefined reference to `std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::find_first_of(char, unsigned long) const'
    ../lib/libreference_data_driver.so: undefined reference to `std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::substr(unsigned long, unsigned long) const'
    ../lib/libreference_data_driver.so: undefined reference to `std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string()'
    ../lib/libreference_data_driver.so: undefined reference to `std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&&)'
    ../lib/libreference_data_driver.so: undefined reference to `std::basic_istream<char, std::char_traits<char> >& std::getline<char, std::char_traits<char>, std::allocator<char> >(std::basic_istream<char, std::char_traits<char> >&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&)'
    ../lib/libreference_data_driver.so: undefined reference to `std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::~basic_string()'
    ../lib/libreference_data_driver.so: undefined reference to `std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::find_last_not_of(char const*, unsigned long) const'
    ../lib/libreference_data_driver.so: undefined reference to `std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::compare(char const*) const'
    ../lib/libreference_data_driver.so: undefined reference to `std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::compare(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) const'
    ../lib/libreference_data_driver.so: undefined reference to `std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(char const*, std::allocator<char> const&)'
    

    My Junction/Turf config:

    #define JUNCTION_WITH_FOLLY 0
    #define JUNCTION_WITH_CDS 0
    #define JUNCTION_WITH_NBDS 0
    #define JUNCTION_WITH_TBB 0
    #define JUNCTION_WITH_TERVEL 0
    #define JUNCTION_WITH_LIBCUCKOO 0
    #define NBDS_USE_TURF_HEAP 0
    #define TBB_USE_TURF_HEAP 0
    #define JUNCTION_TRACK_GRAMPA_STATS 0
    #define JUNCTION_USE_STRIPING 1
    ---
    #define TURF_HAS_STDINT 1
    #define TURF_PREFER_CPP11 0
    #define TURF_WITH_BOOST 0
    #define TURF_PREFER_BOOST 0
    #define TURF_WITH_EXCEPTIONS 0
    #define TURF_HAS_NOEXCEPT 1
    #define TURF_HAS_CONSTEXPR 1
    #define TURF_HAS_OVERRIDE 1
    #define TURF_HAS_LONG_LONG 1
    #define TURF_HAS_STATIC_ASSERT 1
    #define TURF_HAS_MOVE 1
    #define TURF_REPLACE_OPERATOR_NEW 0
    #define TURF_USE_DLMALLOC 0
    #define TURF_DLMALLOC_DEBUG_CHECKS 0
    #define TURF_DLMALLOC_FAST_STATS 0
    

    Has anyone else run into this?

    opened by jklghsadf 2
  • Type limitation on values arbitrary?

    Type limitation on values arbitrary?

    I'm trying to use the leapfrog hashmap in the context of packet processing and flow tracking. Ideally the flow data would be stored directly in the hash table to mitigate the whole issue of memory allocations. But according to your blog posts and the readme, value types are limited to integers and pointers. I understand the restrictions on key types because of the hash reversibility requirement, but do not see why value types are limited as well. As long as I provide a ValueTraits::NullValue and ValueTraits::Redirect any value could work, right?

    For reference, a value would essentially be a POD struct:

    struct flow_data {
        uint64_t timestamp;
        bool someflag;
        uint16_t another_value;
    };
    
    opened by pudelkoM 2
  • issue when inserting into concurrent map

    issue when inserting into concurrent map

    Hi,

    I have a seemingly simple test program which hangs on my machine under certain circumstances:

    #include <junction/ConcurrentMap_Leapfrog.h>
    #include <iostream>
    
    struct Value
    {
        int v;
    };
    
    using ConcurrentMap = junction::ConcurrentMap_Leapfrog<int,Value*>;
    
    int main()
    {
        ConcurrentMap cmap(10000);
        Value value{ 0 };
    
        //for (int i = 0; i < 1000000; ++i) // locks in 158th assign
        for (int i = 999999; i >= 0; --i) // works as expected
        {
            cmap.assign(i, &value);
            std::cout << "inserted " << i << "\n";
        }
    
        std::cout << "done\n";
    }
    

    As you can see from the comment around the for loops, one case works as expected (completes without error) while the other one hangs. I am at a loss to explain why. Is this a bug, or a known issue? Or am I doing something stupid?

    Thanks for your time.

    opened by mdevico 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 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
Owner
Jeff Preshing
Jeff Preshing
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 Jun 15, 2022
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 2.1k Jun 16, 2022
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 309 Jun 19, 2022
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.8k Jun 24, 2022
: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 347 Jun 5, 2022
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 724 Jun 30, 2022
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 705 Jun 27, 2022
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 295 Jun 10, 2022
Concurrency Kit 2.1k Jun 18, 2022
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 Jun 15, 2022
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 2.1k Jun 16, 2022
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 309 Jun 19, 2022
Static analysis of structures is a fundamental step for determining the stability of structures

StAnD: A Dataset of Linear Static Analysis Problems [Abstract] [Paper] Static analysis of structures is a fundamental step for determining the stabili

Zuru Tech 3 Jan 20, 2022
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 63 May 24, 2022
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.8k Jun 24, 2022
: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 347 Jun 5, 2022
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 724 Jun 30, 2022
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 72 Jun 26, 2022
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.9k Jun 27, 2022
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 722 Jun 23, 2022
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 398 Jun 27, 2022
The Wren Programming Language. Wren is a small, fast, class-based concurrent scripting language.

Wren is a small, fast, class-based concurrent scripting language Think Smalltalk in a Lua-sized package with a dash of Erlang and wrapped up in a fami

Wren 5.7k Jun 27, 2022
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 705 Jun 27, 2022
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 307 Jun 28, 2022
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.4k Jun 26, 2022
🔗 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 40 Jan 28, 2022